A mini-deque is a small, immutable, double-ended sequence used as a buffer at the edges of a deque. It holds exactly one, two, three, or four items. Unlike a general deque, it has no empty state: popping its sole item or pushing onto a four-item mini is an error. section 3.3.1
The bounded size makes the implementation straightforward. A private `IMini` interface exposes `Size`, left and right access, and pushes and pops at either end. Records `One`, `Two`, `Three`, and `Four` represent the possible sizes; an operation returns a new record rather than changing the old one. Keeping this interface distinct from the general deque interface makes its stricter contract visible in the code. section 3.3.1
Listing 3.4 A mini-deque
public sealed class Deque<T> : IDeque<T>
{
private interface IMini : IEnumerable<T>
{
public int Size { get; }
public IMini PushLeft(T item);
public IMini PushRight(T item);
public IMini PopLeft();
public IMini PopRight();
public T Left();
public T Right();
}
private record One(T item1) : IMini
{
public int Size => 1;
public IMini PushLeft(T item) => new Two(item, item1);
public IMini PushRight(T item) => new Two(item1, item);
public IMini PopLeft() => throw new InvalidOperationException();
public IMini PopRight() => throw new InvalidOperationException();
public T Left() => item1;
public T Right() => item1;
public IEnumerator<T> GetEnumerator()
{
yield return item1;
}
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
private record Two(T item1, T item2) : IMini
{
public int Size => 2;
public IMini PushLeft(T item) => new Three(item, item1, item2);
public IMini PushRight(T item) => new Three(item1, item2, item);
public IMini PopLeft() => new One(item2);
public IMini PopRight() => new One(item1);
public T Left() => item1;
public T Right() => item2;
public IEnumerator<T> GetEnumerator()
{
yield return item1;
yield return item2;
}
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
private record Three(T item1, T item2, T item3) : IMini
{
public int Size => 3;
public IMini PushLeft(T item) =>
new Four(item, item1, item2, item3);
public IMini PushRight(T item) =>
new Four(item1, item2, item3, item);
public IMini PopLeft() => new Two(item2, item3);
public IMini PopRight() => new Two(item1, item2);
public T Left() => item1;
public T Right() => item3;
public IEnumerator<T> GetEnumerator()
{
yield return item1;
yield return item2;
yield return item3;
}
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
private record Four(T item1, T item2, T item3, T item4) : IMini
{
public int Size => 4;
public IMini PushLeft(T item) =>
throw new InvalidOperationException();
public IMini PushRight(T item) =>
throw new InvalidOperationException();
public IMini PopLeft() => new Three(item2, item3, item4);
public IMini PopRight() => new Three(item1, item2, item3);
public T Left() => item1;
public T Right() => item4;
public IEnumerator<T> GetEnumerator()
{
yield return item1;
yield return item2;
yield return item3;
yield return item4;
}
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
The listing shows the bounded `IMini` contract and how a `One` becomes a `Two` when an item is pushed on either side. section 3.3.1
Why stop at four? A recursive deque can consist of a left mini, a middle deque of minis, and a right mini. Pushing at an edge usually changes only its mini; popping there does the same unless that mini has just one item. Each new mini takes constant time to make, and the unchanged structure is reused. The size limit gives these cheap cases a clear boundary without requiring a larger edge buffer. section 3.3.2
Pushing onto a full left edge
If the left mini already holds four items, pushing another cannot produce a five-item mini. Instead, make a new `Two` from the incoming item and the old leftmost item. Remove that leftmost item from the old mini, leaving a `Three`, and push the `Three` onto the middle deque. The right edge remains unchanged. The middle receives a chunk, not three separate pushes. section 3.3.2
Chunks in the middle must contain more than one item. The initial recursive design uses `Three` chunks there; supporting concatenation relaxes that rule to `Two` or `Three`. Minis at the join between two deques are redistributed into a sequence of those sizes, which can be pushed into the middle before concatenation continues recursively. The outer edge minis still hold between one and four items. section 3.3.2 section 3.7
Listing 3.6 Concatenating minis into Twos and Threes
public sealed class Deque<T> : IDeque<T>
{
private interface IMini : IEnumerable<T>
{
[…]
public IEnumerable<IMini> TwosAndThrees(IMini mini);
}
private record One(T item1) : IMini
{
[…]
public IEnumerable<IMini> TwosAndThrees(IMini mini) => mini switch
{
One or Two => [mini.PushLeft(Left())], #1
_ => [PushRight(mini.Left()), mini.PopLeft()] #2
};
}
private record Two(T item1, T item2) : IMini
{
[…]
public IEnumerable<IMini> TwosAndThrees(IMini mini) => mini switch
{
One => [PushRight(mini.Left())], #3
Two or Three => [this, mini], #4
_ => [PushRight(mini.Left()), mini.PopLeft()] #5
};
}
private record Three(T item1, T item2, T item3) : IMini
{
[…]
public IEnumerable<IMini> TwosAndThrees(IMini mini) => mini switch
{
One => [PopRight(),mini.PushLeft(Right())], #6
Two or Three => [this, mini], #7
_ => [this,
mini.PopRight().PopRight(),
mini.PopLeft().PopLeft()] #8
};
}
private record Four(T item1, T item2, T item3, T item4) : IMini
{
[…]
public IEnumerable<IMini> TwosAndThrees(IMini mini) => mini switch
{
One or Two => [PopRight(), mini.PushLeft(Right())], #9
Three => [PopRight().PopRight(), PopLeft().PopLeft(), mini], #10
_ => [PopRight().PopRight(),
PopLeft().PopLeft().PushRight(mini.Left()),
mini.PopLeft()] #11
};
}
`TwosAndThrees` handles combinations of mini sizes at a concatenation boundary, returning chunks suitable for the middle deque. section 3.7
