Add queues will alternative fetch orders (priority based and stack based).
diff --git a/Lib/Queue.py b/Lib/Queue.py
index ce34024..7b0b328 100644
--- a/Lib/Queue.py
+++ b/Lib/Queue.py
@@ -2,8 +2,9 @@
from time import time as _time
from collections import deque
+import heapq
-__all__ = ['Empty', 'Full', 'Queue']
+__all__ = ['Empty', 'Full', 'Queue', 'PriorityQueue', 'LifoQueue']
class Empty(Exception):
"Exception raised by Queue.get(block=0)/get_nowait()."
@@ -196,7 +197,7 @@
def _init(self, maxsize):
self.queue = deque()
- def _qsize(self):
+ def _qsize(self, len=len):
return len(self.queue)
# Put a new item in the queue
@@ -206,3 +207,38 @@
# Get an item from the queue
def _get(self):
return self.queue.popleft()
+
+
+class PriorityQueue(Queue):
+ '''Variant of Queue that retrieves open entries in priority order (lowest first).
+
+ Entries are typically tuples of the form: (priority number, data).
+ '''
+
+ def _init(self, maxsize):
+ self.queue = []
+
+ def _qsize(self, len=len):
+ return len(self.queue)
+
+ def _put(self, item, heappush=heapq.heappush):
+ heappush(self.queue, item)
+
+ def _get(self, heappop=heapq.heappop):
+ return heappop(self.queue)
+
+
+class LifoQueue(Queue):
+ '''Variant of Queue that retrieves most recently added entries first.'''
+
+ def _init(self, maxsize):
+ self.queue = []
+
+ def _qsize(self, len=len):
+ return len(self.queue)
+
+ def _put(self, item):
+ self.queue.append(item)
+
+ def _get(self):
+ return self.queue.pop()
diff --git a/Lib/test/test_queue.py b/Lib/test/test_queue.py
index 66977e6..2a76cda 100644
--- a/Lib/test/test_queue.py
+++ b/Lib/test/test_queue.py
@@ -181,8 +181,13 @@
raise RuntimeError, "Call this function with an empty queue"
# I guess we better check things actually queue correctly a little :)
q.put(111)
+ q.put(333)
q.put(222)
- verify(q.get() == 111 and q.get() == 222,
+ target_order = dict(Queue = [111, 333, 222],
+ LifoQueue = [222, 333, 111],
+ PriorityQueue = [111, 222, 333])
+ actual_order = [q.get(), q.get(), q.get()]
+ verify(actual_order == target_order[q.__class__.__name__],
"Didn't seem to queue the correct data!")
for i in range(QUEUE_SIZE-1):
q.put(i)
@@ -260,18 +265,20 @@
raise TestFailed("Did not detect task count going negative")
def test():
- q = Queue.Queue()
- QueueTaskDoneTest(q)
- QueueJoinTest(q)
- QueueJoinTest(q)
- QueueTaskDoneTest(q)
+ for Q in Queue.Queue, Queue.LifoQueue, Queue.PriorityQueue:
+ q = Q()
+ QueueTaskDoneTest(q)
+ QueueJoinTest(q)
+ QueueJoinTest(q)
+ QueueTaskDoneTest(q)
- q = Queue.Queue(QUEUE_SIZE)
- # Do it a couple of times on the same queue
- SimpleQueueTest(q)
- SimpleQueueTest(q)
- if verbose:
- print "Simple Queue tests seemed to work"
+ q = Q(QUEUE_SIZE)
+ # Do it a couple of times on the same queue
+ SimpleQueueTest(q)
+ SimpleQueueTest(q)
+ if verbose:
+ print "Simple Queue tests seemed to work for", Q.__name__
+
q = FailingQueue(QUEUE_SIZE)
FailingQueueTest(q)
FailingQueueTest(q)