ActiveState Code

Recipe 364952: Criteria-based cascading priority queue

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

Python 
 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()

Discussion

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.

Sign in to comment