Dynamic Circular Buffer & Amortized O(1) Vector

Overview

A cache-contiguous circular ring buffer and dynamic vector using power-of-two bitmask wrap-around, geometric doubling/halving with hysteresis, and potential-function telemetry.

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Power-of-2 Bitmask Physical Index Mapping

• Core Mechanical Concept: Two’s-Complement Modular Arithmetic via (head + i) & (capacity - 1)
• Target Module: index.js (CircularDeque._physIndex)
• Engineering Specification: Implement _physIndex(logicalIdx) to map any logical offset 0 <= i < size to its physical slot in this._buf without integer division. Because this._capacity is strictly a power of two ($2^k$), this._mask = this._capacity - 1 has its lowest $k$ bits set to 1. Therefore (this._head + logicalIdx) & this._mask computes (head + i) mod capacity in 1 CPU cycle, even when this._head - 1 is negative during pushFront.
• Verification Invariant: maps logical indices across wrap-around boundaries via bitmask

Step 2: Order-Preserving Ring Linearization on Resize

• Core Mechanical Concept: Unwrapping Split Ring Segments During Geometric Doubling
• Target Module: index.js (CircularDeque._resize)
• Engineering Specification: Implement _resize(newCap) to allocate a new backing array of length newCap, copy all this._size live elements in logical order 0 .. size - 1 to indices 0 .. size - 1 of the new buffer, and reset _head = 0. Never copy raw physical indices 0 .. cap - 1 directly when _head !== 0, or the newly opened empty space will be spliced into the middle of the logical sequence.
• Verification Invariant: linearizes wrapped elements into contiguous order on geometric doubling

Step 3: Amortized O(1) pushBack and pushFront

• Core Mechanical Concept: Circular Head/Tail Advancement & Potential Function Φ = 2n - m
• Target Module: index.js (CircularDeque.pushBack / CircularDeque.pushFront)
• Engineering Specification: Implement pushBack(value) and pushFront(value). 1. If this._size === this._capacity, call this._resize(this._capacity * 2). 2. For pushBack: write value at (this._head + this._size) & this._mask and increment _size. 3. For pushFront: update this._head = (this._head - 1) & this._mask, write value at this._head, and increment _size.
• Verification Invariant: supports alternating pushFront and pushBack in amortized O(1) time

Step 4: popFront, popBack & Quarter-Load Hysteresis Shrinking

• Core Mechanical Concept: Preventing Thrashing at Capacity Boundaries via 1/4 Shrink Threshold
• Target Module: index.js (CircularDeque.popFront / CircularDeque.popBack)
• Engineering Specification: Implement popFront() and popBack() with GC-friendly slot clearing (undefined) and quarter-capacity shrinking. Halving capacity at 50% fullness causes $O(N)$ thrashing on alternating push/pop sequences at the boundary. Only halve this._capacity when this._capacity > 8 && this._size <= (this._capacity >> 2).
• Verification Invariant: pops from both ends and shrinks only at quarter load without thrashing

Asymptotic & Memory Layout Guarantees

• Category: Linear Structures & Memory
• Difficulty: Intermediate (~30 minutes)
• Key Architectural Highlights:
  • Power-of-2 capacity invariant enabling single-cycle (head + i) & mask wrap-around
  • Order-preserving geometric doubling (2x) and quarter-load shrinking (0.25x)
  • Potential-function Φ = 2n - m instrumentation verifying O(1) amortized bounds
• Tags & Primitives: Circular Buffer, Amortized O(1), Bitmask Indexing, Dynamic Array, Cache Locality

Production Systems Context & Verification

This from-scratch implementation is engineered with zero external dependencies and deterministic verification harnesses. Every internal invariant—from pointer restoration and bitmask addressing to amortized potential bounds and tree height balance—is asserted directly in test.js. Use the interactive browser workbench above to complete the guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.