projects / OpenSPARC-T2-DV / blame
? search:
summary | tags | clone url | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Initial commit of OpenSPARC T2 design and verification files.
[OpenSPARC-T2-DV] / tools / src / nas,5.n2.os.2 / lib / python / html / python / lib / deque-recipes.html
CommitLineData
86530b38
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>
565.12.1 Recipes
57</H2>
58
59<P>
60This section shows various approaches to working with deques.
61
62<P>
63The <tt class="method">rotate()</tt> method provides a way to implement <tt class="class">deque</tt>
64slicing 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
66elements to be popped:
67
68<P>
69<div class="verbatim"><pre>
70def delete_nth(d, n):
71 d.rotate(-n)
72 d.popleft()
73 d.rotate(n)
74</pre></div>
75
76<P>
77To 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.
79Remove 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>
83With minor variations on that approach, it is easy to implement Forth style
84stack 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>
88A 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>
90to add it back to the tasklist if the input stream is not exhausted:
91
92<P>
93<div class="verbatim"><pre>
94def 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&gt;&gt;&gt; for value in roundrobin('abc', 'd', 'efgh'):
105... print value
106
107a
108d
109e
110b
111f
112c
113g
114h
115</pre></div>
116
117<P>
118Multi-pass data reduction algorithms can be succinctly expressed and
119efficiently 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>
124For example, building a balanced binary tree of nested lists entails
125reducing two adjacent nodes into one by grouping them in a list:
126
127<P>
128<div class="verbatim"><pre>
129def maketree(iterable):
130 d = deque(iterable)
131 while len(d) &gt; 1:
132 pair = [d.popleft(), d.popleft()]
133 d.append(pair)
134 return list(d)
135
136&gt;&gt;&gt; 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>
178See <i><a href="about.html">About this document...</a></i> for information on suggesting changes.
179</ADDRESS>
180</BODY>
181</HTML>
Full OpenSPARC design & verification tarball including full HDL.