Welcome, guest | Sign In | My Account | Store | Cart

This module provides a simple criteria-based priority queue with "priority cascading".

Python, 29 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from Queue import Queue
from sets import Set

class PriorityQueue:
    """Simple criteria-based priority queue. Not thread-safe.
    
    The criteria argument should be a sequence of callables that return
    boolean values. There is no need to add an "all pass" criterion at the
    end; the queue will add all non-matching items with the least priority.
    
    The items are retrieved highest-rank first."""
    def __init__(self, criteria):
        self.qs = [Queue(0) for i in range(len(criteria)+1)]
        self.cr = criteria
    def empty(self):
        for q in self.qs:
            if not q.empty():
                return False
        return True
    def put(self, item):
        for i, c in enumerate(self.cr):
            if c(item):
                self.qs[i].put(item)
                return
        self.qs[-1].put(item)
    def get(self):
        for q in self.qs:
            if not q.empty():
                return q.get()

This is a very simple queue that automatically sets item priorities using the criteria functions provided by the user. If a given item doesn't match any of the criteria, it is added with the lowest priority.

The term "priority cascading" simply means that items with a given priority will only be retrieved when higher ranked items have been exhausted. This is useful when some of the items must be retrieved with absolute priority.

Note that low-ranking items are only guaranteed to be retrieved if items are consumed faster produced.

This implementation is not thread-safe.

1 comment

Grant Jenks 7 years, 2 months ago  # | flag

If you're looking for an API similar to that provided by this priority queue, check out the sortedcontainers module. It implements sorted list, sorted dict, and sorted set data types in pure-Python and is fast-as-C implementations (even faster!). Learn more about sortedcontainers, available on PyPI and github.