From e7169eb9ede900c9b311725ba50757177be223bf Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Sun, 9 May 2004 01:15:01 +0000 Subject: Add more examples. --- Doc/lib/libcollections.tex | 53 +++++++++++++++++++++++++++++++++++++++++++++- Lib/test/test_deque.py | 51 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 103 insertions(+), 1 deletion(-) 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']]]] + + """ -- cgit v0.12