From 9e1bc982ffa454dc3002ec9cb1f01d2d0ce5f255 Mon Sep 17 00:00:00 2001
From: Raymond Hettinger <python@rcn.com>
Date: Wed, 16 Jan 2008 23:40:45 +0000
Subject: Add queues will alternative fetch orders (priority based and stack
 based).

---
 Lib/Queue.py           | 40 ++++++++++++++++++++++++++++++++++++++--
 Lib/test/test_queue.py | 31 +++++++++++++++++++------------
 2 files changed, 57 insertions(+), 14 deletions(-)

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 @@ class Queue:
     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 @@ class Queue:
     # 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 @@ def SimpleQueueTest(q):
         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 @@ def QueueTaskDoneTest(q):
         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 = 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 = 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 = FailingQueue(QUEUE_SIZE)
     FailingQueueTest(q)
     FailingQueueTest(q)
-- 
cgit v0.12