[Python-checkins] python/dist/src/Doc/lib libcollections.tex, 1.7, 1.8

[rhettinger at users.sourceforge.net]

Update of /cvsroot/python/python/dist/src/Doc/lib
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv24983/Doc/lib

Modified Files:
	libcollections.tex 
Log Message:
Add more examples.

Index: libcollections.tex
===================================================================
RCS file: /cvsroot/python/python/dist/src/Doc/lib/libcollections.tex,v
retrieving revision 1.7
retrieving revision 1.8
diff -C2 -d -r1.7 -r1.8
*** libcollections.tex	30 Apr 2004 22:52:50 -0000	1.7
--- libcollections.tex	9 May 2004 01:15:00 -0000	1.8
***************
*** 131,134 ****
--- 131,163 ----
  \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
***************
*** 148,152 ****
  
  >>> for value in roundrobin('abc', 'd', 'efgh'):
!         print value
  
  a
--- 177,181 ----
  
  >>> for value in roundrobin('abc', 'd', 'efgh'):
! ...     print value
  
  a
***************
*** 160,161 ****
--- 189,212 ----
  
  \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}