How can an immutable deque grow at either end without copying its contents? Give it small buffers at the edges. A deque is empty, holds one item, or consists of a left mini-deque, a middle deque of minis, and a right mini-deque. Each mini holds one to four items. Crucially, the middle holds minis, not individual items. section 3.3.2
The edge minis determine what an update must touch:
- Push into an edge mini with room, or pop from one holding multiple items: make a new mini and reuse the middle and opposite edge. section 3.3.2
- Push against a full Four: leave a Two at the edge and push the displaced Three into the middle. That middle can repeat the same operation at the next level. section 3.3.2
- Pop the sole item from an edge mini: if the middle is nonempty, take its end mini to refill the edge. Initially, middle elements are always Threes, so chunks never shrink to single items there. section 3.3.2
left.Size < 4 ?
new Deque<T>(left.PushLeft(value), middle, right) :
new Deque<T>(
new Two(value, left.Left()),
middle.PushLeft(left.PopLeft()),
right);
The two branches of PushLeft show the central choice: update only the left mini when possible, or transfer a Three to the recursive middle. section 3.3.2
When the middle grows
Start with four characters in each edge mini and an empty middle. Pushing Q on the left and Z on the right transfers a Three from each full edge into the middle. Continue pushing left: eventually the middle’s own left mini fills, and its overflow becomes a Three of Threes at a third level. The edges remain shallow even as the center grows deeper. section 3.4
Figure 3.5 A 22-item deque. The left mini on the second level has overflowed, so we’ve made a single-item deque of minis of minis to hold three Threes. Notice that the number of arrows traversed from the root to any given leaf is shallowest at the left and right edges and deepest in the middle.
The 22-item diagram makes the second-level overflow and the resulting third level visible. section 3.4
Concatenation slightly relaxes the invariant: middle elements may be Twos or Threes, but still never Ones. Repackage the two facing edge minis into those chunks, push them onto one middle, then concatenate the two middles recursively. This avoids the straightforward linear approach of pushing every item across. section 3.7
The recursion also changes the generic type at each level: a deque of items contains a deque of minis, which contains minis of minis. Its depth is O(log3 n). C# and Java generics can accommodate this nesting; template expansion in languages such as C++ raises a different compiler concern. section 3.6
