A Three is a mini-deque containing exactly three items. In an immutable deque, Threes serve as the standard chunks stored in the recursive middle, keeping individual pushes and pops at the edges while allowing the structure to grow in layers. section 3.3.2
When an edge mini overflows, the deque removes three items, packages them as a Three, and pushes that chunk into the middle. Repeating this operation produces a finger-tree shape: Threes become elements of higher-level mini-deques, and a Three of Threes can move to the next level. section 3.3.2 section 3.4
Overflowing the left edge
After building a character deque and pushing Q onto the left, the full left Four cannot grow. The deque keeps Q with the nearest edge items and pushes a Three containing S, T, and U into the middle. Further pushes repeat the pattern, eventually promoting three Threes into a higher-level chunk. section 3.4
Figure 3.3 A nine-item deque after we push Q onto the left. The left mini containing R, S, T, U couldn’t grow to hold Q, so we pushed a Three containing S, T, U onto the middle, which is a deque of minis, not a deque of chars. Second, when we push Z onto the right, the mini containing V, W, X, Y couldn’t grow, so we pushed a Three containing V, W, X onto the middle. When we’re done, the middle deque has two Threes in it: a One containing a Three on the left, an empty middle, and a One containing a Three on the right.
Inspect the figure showing how an overflowing Four becomes a Three in the middle and how the middle stores Threes rather than individual characters. section 3.4
Concatenation relaxes the invariant: middle chunks may be Threes or Twos. Boundary minis are reshaped into a sequence of Twos and Threes, avoiding singleton chunks in the middle while preserving recursive structure. section 3.7
