This module provides a simple criteria-based priority queue with "priority cascading".
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.