This module provides a simple criteria-based priority queue with "priority cascading".
Python, 29 lines
Download
Copy to clipboard1 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.
Tags: algorithms
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.