 |
 |
 |
Python Library Reference |  |
 |
 |
This section shows various approaches to working with deques.
The rotate() method provides a way to implement deque
slicing and deletion. For example, a pure python implementation of
del d[n] relies on the rotate() method to position
elements to be popped:
def delete_nth(d, n):
d.rotate(-n)
d.popleft()
d.rotate(n)
To implement deque slicing, use a similar approach applying rotate() to bring a target element to the left side of the deque. Remove old entries with popleft(), add new entries with extend(), and then reverse the rotation.
With minor variations on that approach, it is easy to implement Forth style
stack manipulations such as dup, drop, swap, over,
pick, rot, and roll.
A roundrobin task server can be built from a deque using popleft() to select the current task and append() to add it back to the tasklist if the input stream is not exhausted:
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
Multi-pass data reduction algorithms can be succinctly expressed and efficiently coded by extracting elements with multiple calls to popleft(), applying the reduction function, and calling append() to add 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:
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']]]]
|
|
|
Python Library Reference | |
|
|