Message258893
The behavior of deque.insert() in a bounded deque is a bit odd:
>>> from collections import deque
>>> d = deque(range(20), maxlen=10)
>>> d
deque([10, 11, 12, 13, 14, 15, 16, 17, 18, 19], maxlen=10)
>>> d.insert(3, 'New')
>>> d
deque([19, 10, 11, 'New', 13, 14, 15, 16, 17, 18], maxlen=10)
# ^ ^ ^--- The 12 got replaced
# | \--- The elements before the insertion point got rotated
# \--- The final element got rotated to first position
With append/appendleft/extend/extendleft, the intended and useful behavior for maxlen is to pop from the opposite end. But for deque.insert(), the best and most useful behavior invariants are less obvious.
Ideally, the effect of d.insert(0, item) would be the same as d.appendleft(item), and the effect of d.insert(len(d), item) would be the same as d.append(item).
Also, d.insert(i, newitem) should have the post-condition:
assert d[i] == newitem if i < len(d) else d[-1] == newitem
Having decided where to put the newitem, the question turns to deciding which element should be popped-off to maintain the size invariant.
I'm thinking that it should always be the rightmost element that gets popped, so that items before the inserted element never get moved. This matches what insert() does for unbounded deques, making it the least surprising choice. |
|
Date |
User |
Action |
Args |
2016-01-24 17:47:04 | rhettinger | set | recipients:
+ rhettinger |
2016-01-24 17:47:04 | rhettinger | set | messageid: <1453657624.63.0.880277863791.issue26194@psf.upfronthosting.co.za> |
2016-01-24 17:47:04 | rhettinger | link | issue26194 messages |
2016-01-24 17:47:02 | rhettinger | create | |
|