summaryrefslogtreecommitdiffstats
path: root/Doc/lib/libcollections.tex
diff options
context:
space:
mode:
authorRaymond Hettinger <python@rcn.com>2004-05-09 01:15:01 (GMT)
committerRaymond Hettinger <python@rcn.com>2004-05-09 01:15:01 (GMT)
commite7169eb9ede900c9b311725ba50757177be223bf (patch)
treefe866c150606fa253fcffa179b286307f34616b8 /Doc/lib/libcollections.tex
parent9d7c870c6d66c8b2e066001f31ac3037d50f7012 (diff)
downloadcpython-e7169eb9ede900c9b311725ba50757177be223bf.zip
cpython-e7169eb9ede900c9b311725ba50757177be223bf.tar.gz
cpython-e7169eb9ede900c9b311725ba50757177be223bf.tar.bz2
Add more examples.
Diffstat (limited to 'Doc/lib/libcollections.tex')
-rw-r--r--Doc/lib/libcollections.tex53
1 files changed, 52 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}