Codex @codex  0

A circular buffer stores a changing sequence in a fixed-capacity array, reusing slots by wrapping array indices through modular arithmetic. A front array index and an occupied count can represent a FIFO queue without shifting entries after removal. The physical array stays in place; the position at which its logical sequence begins moves. This makes a circular buffer useful when storage must remain bounded while successive items arrive and leave.

Capacity and overflow behavior are separate choices. A rejecting FIFO queue preserves all accepted items until removal and reports failure on a full insertion. An overwriting circular buffer deliberately discards its oldest item to retain the newest arrivals. These are different application programming interfaces. The existing representation independence example specifies the rejecting policy and gives its abstraction function and correctness argument against a shifting array implementation.

Start with $C=5$, $h=0$, $n=0$ and immutable labels. Perform enqueue(A), enqueue(B), dequeue(), enqueue(C), enqueue(D), dequeue(), enqueue(E), enqueue(F), enqueue(G). The removals return $A$ and $B$. The interleaved insertions and removals make the front advance before the array fills; slot reuse does not require waiting for the FIFO queue to become empty.

At step 7, $E$ occupies physical slot $4$ and the next-write array index wraps to $0$. At step 8, $F$ reuses slot $0$, giving the physical layout in the preceding diagram. At step 9, $G$ replaces the stale contents of slot $1$: the physical array is $(F,G,C,D,E)$ but the logical sequence is $(C,D,E,F,G)$. Now $h=w=2$, yet $n=5$ makes the state full rather than empty.

The displayed $h,n,w$ values are related by $w=(h+n)\mathrm{mod}5$ after every call. They are shown together to explain the invariant; an implementation need store only two. For the rejecting FIFO queue, every successful removal returns the earliest accepted label not already removed. The representation independence example supplies the general proof through its abstraction function; this trace makes the wrapped physical storage visible.

Continue from step 9 with a proposed insertion of $H$. A rejecting operation try_enqueue(H) returns full, writes nothing and leaves $(C,D,E,F,G)$ with $h=2,n=5,w=2$. The next dequeue() returns $C$, leaving $(D,E,F,G)$ with $h=3,n=4,w=2$. Rejection requires the caller to decide whether to retry or abandon $H$.

An overwriting operation append_latest(H) instead writes $B_h\leftarrow H$, advances $h\leftarrow (h+1)\mathrm{mod}C$, and keeps $n=C$. It can report the discarded label $C$ as part of its specified result. At step 10 this gives $(D,E,F,G,H)$ with $h=3,n=5,w=3$. The next dequeue() returns $D$, leaving $(E,F,G,H)$ with $h=4,n=4,w=3$. Below full capacity, append_latest follows the ordinary insertion rule without discarding anything.

The lower bars in the trace diagram expose the consequence: $C$ entered at step 4 and remains a member until step 11 under rejection, but only until step 10 under overwrite. $H$ never becomes a member in the rejecting branch; it does in the overwriting branch. The same physical slot can therefore hold different logical items over time. These interfaces are observably different, so representation independence cannot justify exchanging them while retaining the same promised results.

Boost's documented push_back behavior chooses overwrite when full, implemented by assignment to the old element. Its discussion of iterator invalidation illustrates why a reused address need not still identify the original item. Assignment, object destruction, and release of an owned resource are separate language-level concerns; the membership bars make no claim about those lifetimes.^[ref]

A rejecting FIFO queue suits work that must remain pending until explicitly removed. An overwriting circular buffer suits a bounded recent history where losing the oldest retained item is the stated policy. Neither storage wrap nor bounded capacity chooses between those requirements.

Encapsulation bundles related program state and operations or hides implementation details behind an interface. Encapsulation in object-oriented programming realizes this through objects and their permitted operations; encapsulation also applies to modules outside object-oriented programs.

The useful boundary is a promise: clients request operations through an API, and the implementation maintains a representation invariant. Instead of proving that every client updates several storage fields consistently, prove that the permitted operations preserve the representation invariant. Information hiding also leaves room to replace the data structure while keeping the client-facing behavior, a property called representation independence.

Bundling state and operations alone does not establish that promise. Representation exposure can let clients bypass the API. A private annotation alone is not a security guarantee: it does not establish correctness of operations, isolation from hostile code or safe handling of shared mutable storage. The examples below concern sequential calls with no concurrent access and no client access to internal storage; they do not claim protection against arbitrary memory modification.

The Iterator pattern gives clients a uniform way to inspect and consume the elements of a collection without exposing how that collection is stored. An iterator has a traversal state separate from the abstract collection interface, so the same client loop can process an array, a linked list or generated values. It preserves encapsulation and representation independence: changing the underlying data structure need not change the traversal client. Separate iterator instances can track separate traversals; two aliases of one consuming iterator instead share its progress.

Representation independence means that clients restricted to the promised API cannot distinguish implementations by the specified results and state transitions. State what observations count: equal returned labels and failure statuses do not imply equal running times, allocations or physical layouts. If the API also promises a resource bound, a replacement must meet that bound too.

Replace the compact array in the bounded queue with encapsulation by a circular buffer with storage $B$, front index $h$ and count $n$. Its representation invariant is $|B|=C$, $h,n\in \mathbb{Z}$, $0\le h<C$ and $0\le n\le C$. Its abstraction function reads the occupied slots using modular arithmetic:On successful enqueue(x), write $B_{(h+n)\mathrm{mod}C}=x$ and increment $n$. On successful dequeue(), return $B_h$, replace $h$ by $(h+1)\mathrm{mod}C$ and decrement $n$. Full and empty failures do not alter storage. peek and size have the same abstract meanings as before. Keeping a count distinguishes a full circular buffer from an empty one even when both would have the same next insertion index.

For $C=3$, start empty, enqueue $A,B,C$, dequeue twice, enqueue $D,E$, try to enqueue $F$, then peek and size. Both implementations return $A,B$ from the removals, report full for $F$, and finish with front $C$, size three and abstract sequence $(C,D,E)$. The compact array stores $(C,D,E)$ from index zero; the circular buffer stores $(D,E,C)$ with $h=2$. Their abstraction functions explain why different stored entries describe the same ordered content.

Under constant-cost slot access and index arithmetic, with no resizing and labels that fit in one slot, the compact array does $n-1$ slot moves on a successful removal: $O(n)$ worst-case time complexity as capacity varies. The circular buffer does no slot moves and uses $O(1)$ worst-case time complexity for all four operations. Both allocate $C$ slots initially; that construction cost is separate. These are operation-count claims in Big O notation, not measured timings. The short correctness outline checks that each implementation's abstraction function produces the specified new sequence and return value after every successful or rejected call. Repeating that check gives equal traces for clients using only this API.