Commit | Line | Data |
---|---|---|
920dae64 AT |
1 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> |
2 | <html> | |
3 | <head> | |
4 | <link rel="STYLESHEET" href="lib.css" type='text/css' /> | |
5 | <link rel="SHORTCUT ICON" href="../icons/pyfav.png" type="image/png" /> | |
6 | <link rel='start' href='../index.html' title='Python Documentation Index' /> | |
7 | <link rel="first" href="lib.html" title='Python Library Reference' /> | |
8 | <link rel='contents' href='contents.html' title="Contents" /> | |
9 | <link rel='index' href='genindex.html' title='Index' /> | |
10 | <link rel='last' href='about.html' title='About this document...' /> | |
11 | <link rel='help' href='about.html' title='About this document...' /> | |
12 | <link rel="prev" href="module-collections.html" /> | |
13 | <link rel="parent" href="module-collections.html" /> | |
14 | <link rel="next" href="module-heapq.html" /> | |
15 | <meta name='aesop' content='information' /> | |
16 | <title>5.12.1 Recipes </title> | |
17 | </head> | |
18 | <body> | |
19 | <DIV CLASS="navigation"> | |
20 | <div id='top-navigation-panel' xml:id='top-navigation-panel'> | |
21 | <table align="center" width="100%" cellpadding="0" cellspacing="2"> | |
22 | <tr> | |
23 | <td class='online-navigation'><a rel="prev" title="5.12 collections " | |
24 | href="module-collections.html"><img src='../icons/previous.png' | |
25 | border='0' height='32' alt='Previous Page' width='32' /></A></td> | |
26 | <td class='online-navigation'><a rel="parent" title="5.12 collections " | |
27 | href="module-collections.html"><img src='../icons/up.png' | |
28 | border='0' height='32' alt='Up One Level' width='32' /></A></td> | |
29 | <td class='online-navigation'><a rel="next" title="5.13 heapq " | |
30 | href="module-heapq.html"><img src='../icons/next.png' | |
31 | border='0' height='32' alt='Next Page' width='32' /></A></td> | |
32 | <td align="center" width="100%">Python Library Reference</td> | |
33 | <td class='online-navigation'><a rel="contents" title="Table of Contents" | |
34 | href="contents.html"><img src='../icons/contents.png' | |
35 | border='0' height='32' alt='Contents' width='32' /></A></td> | |
36 | <td class='online-navigation'><a href="modindex.html" title="Module Index"><img src='../icons/modules.png' | |
37 | border='0' height='32' alt='Module Index' width='32' /></a></td> | |
38 | <td class='online-navigation'><a rel="index" title="Index" | |
39 | href="genindex.html"><img src='../icons/index.png' | |
40 | border='0' height='32' alt='Index' width='32' /></A></td> | |
41 | </tr></table> | |
42 | <div class='online-navigation'> | |
43 | <b class="navlabel">Previous:</b> | |
44 | <a class="sectref" rel="prev" href="module-collections.html">5.12 collections </A> | |
45 | <b class="navlabel">Up:</b> | |
46 | <a class="sectref" rel="parent" href="module-collections.html">5.12 collections </A> | |
47 | <b class="navlabel">Next:</b> | |
48 | <a class="sectref" rel="next" href="module-heapq.html">5.13 heapq </A> | |
49 | </div> | |
50 | <hr /></div> | |
51 | </DIV> | |
52 | <!--End of Navigation Panel--> | |
53 | ||
54 | <H2><A NAME="SECTION0071210000000000000000"></A><A NAME="deque-recipes"></A> | |
55 | <BR> | |
56 | 5.12.1 Recipes | |
57 | </H2> | |
58 | ||
59 | <P> | |
60 | This section shows various approaches to working with deques. | |
61 | ||
62 | <P> | |
63 | The <tt class="method">rotate()</tt> method provides a way to implement <tt class="class">deque</tt> | |
64 | slicing and deletion. For example, a pure python implementation of | |
65 | <code>del d[n]</code> relies on the <tt class="method">rotate()</tt> method to position | |
66 | elements to be popped: | |
67 | ||
68 | <P> | |
69 | <div class="verbatim"><pre> | |
70 | def delete_nth(d, n): | |
71 | d.rotate(-n) | |
72 | d.popleft() | |
73 | d.rotate(n) | |
74 | </pre></div> | |
75 | ||
76 | <P> | |
77 | To implement <tt class="class">deque</tt> slicing, use a similar approach applying | |
78 | <tt class="method">rotate()</tt> to bring a target element to the left side of the deque. | |
79 | Remove old entries with <tt class="method">popleft()</tt>, add new entries with | |
80 | <tt class="method">extend()</tt>, and then reverse the rotation. | |
81 | ||
82 | <P> | |
83 | With minor variations on that approach, it is easy to implement Forth style | |
84 | stack manipulations such as <code>dup</code>, <code>drop</code>, <code>swap</code>, <code>over</code>, | |
85 | <code>pick</code>, <code>rot</code>, and <code>roll</code>. | |
86 | ||
87 | <P> | |
88 | A roundrobin task server can be built from a <tt class="class">deque</tt> using | |
89 | <tt class="method">popleft()</tt> to select the current task and <tt class="method">append()</tt> | |
90 | to add it back to the tasklist if the input stream is not exhausted: | |
91 | ||
92 | <P> | |
93 | <div class="verbatim"><pre> | |
94 | def roundrobin(*iterables): | |
95 | pending = deque(iter(i) for i in iterables) | |
96 | while pending: | |
97 | task = pending.popleft() | |
98 | try: | |
99 | yield task.next() | |
100 | except StopIteration: | |
101 | continue | |
102 | pending.append(task) | |
103 | ||
104 | >>> for value in roundrobin('abc', 'd', 'efgh'): | |
105 | ... print value | |
106 | ||
107 | a | |
108 | d | |
109 | e | |
110 | b | |
111 | f | |
112 | c | |
113 | g | |
114 | h | |
115 | </pre></div> | |
116 | ||
117 | <P> | |
118 | Multi-pass data reduction algorithms can be succinctly expressed and | |
119 | efficiently coded by extracting elements with multiple calls to | |
120 | <tt class="method">popleft()</tt>, applying the reduction function, and calling | |
121 | <tt class="method">append()</tt> to add the result back to the queue. | |
122 | ||
123 | <P> | |
124 | For example, building a balanced binary tree of nested lists entails | |
125 | reducing two adjacent nodes into one by grouping them in a list: | |
126 | ||
127 | <P> | |
128 | <div class="verbatim"><pre> | |
129 | def maketree(iterable): | |
130 | d = deque(iterable) | |
131 | while len(d) > 1: | |
132 | pair = [d.popleft(), d.popleft()] | |
133 | d.append(pair) | |
134 | return list(d) | |
135 | ||
136 | >>> print maketree('abcdefgh') | |
137 | [[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]] | |
138 | </pre></div> | |
139 | ||
140 | <DIV CLASS="navigation"> | |
141 | <div class='online-navigation'> | |
142 | <p></p><hr /> | |
143 | <table align="center" width="100%" cellpadding="0" cellspacing="2"> | |
144 | <tr> | |
145 | <td class='online-navigation'><a rel="prev" title="5.12 collections " | |
146 | href="module-collections.html"><img src='../icons/previous.png' | |
147 | border='0' height='32' alt='Previous Page' width='32' /></A></td> | |
148 | <td class='online-navigation'><a rel="parent" title="5.12 collections " | |
149 | href="module-collections.html"><img src='../icons/up.png' | |
150 | border='0' height='32' alt='Up One Level' width='32' /></A></td> | |
151 | <td class='online-navigation'><a rel="next" title="5.13 heapq " | |
152 | href="module-heapq.html"><img src='../icons/next.png' | |
153 | border='0' height='32' alt='Next Page' width='32' /></A></td> | |
154 | <td align="center" width="100%">Python Library Reference</td> | |
155 | <td class='online-navigation'><a rel="contents" title="Table of Contents" | |
156 | href="contents.html"><img src='../icons/contents.png' | |
157 | border='0' height='32' alt='Contents' width='32' /></A></td> | |
158 | <td class='online-navigation'><a href="modindex.html" title="Module Index"><img src='../icons/modules.png' | |
159 | border='0' height='32' alt='Module Index' width='32' /></a></td> | |
160 | <td class='online-navigation'><a rel="index" title="Index" | |
161 | href="genindex.html"><img src='../icons/index.png' | |
162 | border='0' height='32' alt='Index' width='32' /></A></td> | |
163 | </tr></table> | |
164 | <div class='online-navigation'> | |
165 | <b class="navlabel">Previous:</b> | |
166 | <a class="sectref" rel="prev" href="module-collections.html">5.12 collections </A> | |
167 | <b class="navlabel">Up:</b> | |
168 | <a class="sectref" rel="parent" href="module-collections.html">5.12 collections </A> | |
169 | <b class="navlabel">Next:</b> | |
170 | <a class="sectref" rel="next" href="module-heapq.html">5.13 heapq </A> | |
171 | </div> | |
172 | </div> | |
173 | <hr /> | |
174 | <span class="release-info">Release 2.4.2, documentation updated on 28 September 2005.</span> | |
175 | </DIV> | |
176 | <!--End of Navigation Panel--> | |
177 | <ADDRESS> | |
178 | See <i><a href="about.html">About this document...</a></i> for information on suggesting changes. | |
179 | </ADDRESS> | |
180 | </BODY> | |
181 | </HTML> |