Add more examples.

2 files changed, 103 insertions, 1 deletions

diff --git a/Doc/lib/libcollections.tex b/Doc/lib/libcollections.tex
index c4ba84c..148ddea 100644
--- a/Doc/lib/libcollections.tex
+++ b/Doc/lib/libcollections.tex
@@ -130,6 +130,35 @@ IndexError: pop from an empty deque
 deque(['c', 'b', 'a'])
 \end{verbatim}
 
+\subsection{Recipes \label{deque-recipes}}
+
+This section shows various approaches to working with deques.
+
+The \method{rotate()} method provides a way to implement \class{deque}
+slicing and deletion:
+
+\begin{verbatim}
+def delete_nth(d, n):
+    "del d[n]"
+    d.rotate(-n)
+    d.popleft()
+    d.rotate(n)
+
+>>> d = deque('abcdef')
+>>> delete_nth(d, 2)   # remove the entry at d[2]
+>>> d
+deque(['a', 'b', 'd', 'e', 'f'])
+
+\end{verbatim}
+
+For slicing, the idea is the same.  Use \method{rotate()} to bring a target
+element to the left side of the deque.  Remove old entries with
+\method{popleft()}, add new entries with \method{extend()}, and then
+reverse the rotation.
+
+With minor variations on that approach, it is easy to implement Forth style
+stack manipulations such as \code{dup}, \code{drop}, \code{swap}, \code{over},
+\code{pick}, \code{rot}, and \code{roll}.
 
 A roundrobin task server can be built from a \class{deque} using
 \method{popleft()} to select the current task and \method{append()}
@@ -147,7 +176,7 @@ def roundrobin(*iterables):
         pending.append(task)
 
 >>> for value in roundrobin('abc', 'd', 'efgh'):
-        print value
+...     print value
 
 a
 d
@@ -159,3 +188,25 @@ g
 h
 
 \end{verbatim}
+
+
+Multi-pass data reduction algorithms can be succinctly expressed and
+efficiently coded by extracting elements using multiple calls to
+\method{popleft()}, applying the reduction function, and using
+\method{append()} for adding the result back to the queue.
+
+For example, building a balanced binary tree of nested lists entails
+reducing two adjacent nodes into one by grouping them in a list:
+
+\begin{verbatim}
+def maketree(iterable):
+    d = deque(iterable)
+    while len(d) > 1:
+        pair = [d.popleft(), d.popleft()]
+        d.append(pair)
+    return list(d)
+
+>>> print maketree('abcdefgh')
+[[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]]
+
+\end{verbatim}
diff --git a/Lib/test/test_deque.py b/Lib/test/test_deque.py
index a99de03..2afb179c 100644
--- a/Lib/test/test_deque.py
+++ b/Lib/test/test_deque.py
@@ -474,6 +474,57 @@ IndexError: pop from an empty deque
 >>> d
 deque(['c', 'b', 'a'])
 
+
+
+
+>>> def delete_nth(d, n):
+...     "del d[n]"
+...     d.rotate(-n)
+...     d.popleft()
+...     d.rotate(n)
+...
+>>> d = deque('abcdef')
+>>> delete_nth(d, 2)   # remove the entry at d[2]
+>>> d
+deque(['a', 'b', 'd', 'e', 'f'])
+
+
+
+>>> def roundrobin(*iterables):
+...     pending = deque(iter(i) for i in iterables)
+...     while pending:
+...         task = pending.popleft()
+...         try:
+...             yield task.next()
+...         except StopIteration:
+...             continue
+...         pending.append(task)
+...
+
+>>> for value in roundrobin('abc', 'd', 'efgh'):
+...     print value
+...
+a
+d
+e
+b
+f
+c
+g
+h
+
+
+>>> def maketree(iterable):
+...     d = deque(iterable)
+...     while len(d) > 1:
+...         pair = [d.popleft(), d.popleft()]
+...         d.append(pair)
+...     return list(d)
+...
+>>> print maketree('abcdefgh')
+[[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]]
+
+
 """