* Move collections.deque() in from the sandbox

* Add unittests, newsitem, and whatsnew
* Apply to Queue.py mutex.py threading.py pydoc.py and shlex.py
* Docs are forthcoming

3 files changed, 25 insertions, 21 deletions

diff --git a/Doc/lib/libbisect.tex b/Doc/lib/libbisect.tex
index 3241891..516e5cf 100644
--- a/Doc/lib/libbisect.tex
+++ b/Doc/lib/libbisect.tex
@@ -80,22 +80,5 @@ breakpoints: 85 and up is an `A', 75..84 is a `B', etc.
 'C'
 >>> map(grade, [33, 99, 77, 44, 12, 88])
 ['E', 'A', 'B', 'D', 'F', 'A']
-\end{verbatim}
-
-The bisect module can be used with the Queue module to implement a priority
-queue (example courtesy of Fredrik Lundh): \index{Priority Queue}
-
-\begin{verbatim}
-import Queue, bisect
-
-class PriorityQueue(Queue.Queue):
-    def _put(self, item):
-        bisect.insort(self.queue, item)
 
-# usage
-queue = PriorityQueue(0)
-queue.put((2, "second"))
-queue.put((1, "first"))
-queue.put((3, "third"))
-priority, value = queue.get()
 \end{verbatim}
diff --git a/Doc/lib/libqueue.tex b/Doc/lib/libqueue.tex
index 0770bfe..52c1125 100644
--- a/Doc/lib/libqueue.tex
+++ b/Doc/lib/libqueue.tex
@@ -12,10 +12,6 @@ information must be exchanged safely between multiple threads.  The
 semantics.  It depends on the availability of thread support in
 Python.
 
-\begin{seealso}
-    \seemodule{bisect}{PriorityQueue example using the Queue class}
-\end{seealso}
-
 The \module{Queue} module defines the following class and exception:
 
 
diff --git a/Doc/whatsnew/whatsnew24.tex b/Doc/whatsnew/whatsnew24.tex
index f435b87..ed4a57f 100644
--- a/Doc/whatsnew/whatsnew24.tex
+++ b/Doc/whatsnew/whatsnew24.tex
@@ -322,6 +322,31 @@ euc-jisx0213, iso-2022-jp, iso-2022-jp-1, iso-2022-jp-2,
  \item Korean: cp949, euc-kr, johab, iso-2022-kr
 \end{itemize} 
 
+\item There is a new \module{collections} module which currently offers
+   just one new datatype, \class{deque}, which offers high-performance,
+   thread-safe, memory friendly appends and pops on either side of the
+   deque resulting in efficient stacks and queues:
+
+\begin{verbatim}
+>>> from collections import deque
+>>> d = deque('ghi')        # make a new deque with three items
+>>> d.append('j')           # add a new entry to the right side
+>>> d.appendleft('f')       # add a new entry to the left side
+>>> d                       # show the representation of the deque
+deque(['f', 'g', 'h', 'i', 'j'])
+>>> d.pop()                 # return and remove the rightmost item
+'j'
+>>> d.popleft()             # return and remove the leftmost item
+'f'
+>>> list(d)                 # list the contents of the deque
+['g', 'h', 'i']
+>>> 'h' in d                # search the deque
+True  
+\end{verbatim}
+
+Several modules now take advantage of \class{collections.deque()} for
+improved performance:  \module{Queue}, \module{mutex}, \module{shlex}
+\module{threading}, and \module{pydoc}.
 
 \item The \module{heapq} module has been converted to C.  The resulting
    ten-fold improvement in speed makes the module suitable for handling