Ring Buffer in TypeScript

What's a Ring Buffer?

A ring buffer, or circular buffer, is a buffer data structure that behaves as if it has a circular structure (where the last element is connected to the first element.) Ring buffers are typically allocated a fixed size, but not always.

Ring buffers excel in situations where we need FIFO (first in, first out) behavior and fast random access. Imagine the case where we have 500 elements in a standard, linear buffer and we'd like to remove the first element; all 499 remaining elements now need shifted left by one. That's not a cheap operation! We could avoid the shifting by using a linked list with queue-like operations, however the fast random access is lost due to needing to linearly traverse the list.

Ring buffers with their circular structure and sequential use of a contiguous block of memory alleviate this. When the first item is consumed, the head position is moved forward by one. The position at which the old head pointed is now considered empty, and it is overwritten when the slot is needed again. As the head position exceeds the length of the buffer, it flips back to the starting position of the underlying buffer.

Operations

Ring buffers have the typical operations you would find on a queue.

• Enqueue
  • Adds an item to the buffer
• Dequeue
  • Removes and returns the oldest item in the buffer
• Peek
  • Returns the oldest item in the buffer
• Clear
  • Clears all items from the queue

Diagram of the Structure

TypeScript Implementation

Let's implement a fixed-size ring buffer in TypeScript. Under the hood, the implementation will actually utilize a dynamic array. For me, it is also helpful to conceptualize this as a circular queue where the headPos is being treated as the back of the queue.

We could keep a pointer to the tail position, but this introduces more complexity to our state which we must be mindful to properly bookkeep. Instead, we can derive the tail position using our length property along with the offset of our headPos.

class RingBuffer<T> {
    private length: number;
    private readonly capacity: number;

    private buffer: T[];
    private headPos: number;

    constructor(capacity: number) {
        this.capacity = capacity;
        this.buffer = new Array(this.capacity);
        this.length = 0;
        this.headPos = 0;
    }

    // * places item at the rear of the queue
    enqueue(item: T): void {
        if (this.isFull()) {
            throw new Error("Buffer is full");
        }

        const newheadPos = mod(this.headPos - 1, this.capacity);
        this.buffer[newheadPos] = item;
        this.length++;
        this.headPos = newheadPos;
    }

    // * pulls item from the front of the queue
    dequeue(): T | undefined {
        if (this.isEmpty()) {
            return undefined;
        }

        const tailIdx = this.getTailPos();
        const lastEl = this.buffer[tailIdx];
        this.buffer[tailIdx] = undefined as T;
        this.length--;

        return lastEl;
    }

    // * removes all items from the buffer
    clear(): void {
        this.length = 0;
        this.buffer = new Array(this.capacity);
    }

    peek(): T | undefined {
        if (this.isEmpty()) {
            return undefined;
        }

        return this.buffer[this.getTailPos()];
    }

    isFull(): boolean {
        return this.length === this.capacity;
    }

    isEmpty(): boolean {
        return this.length === 0;
    }

    getLength(): number {
        return this.length;
    }

    getCapacity(): number {
        return this.capacity;
    }

    // * returns a list of all items (oldest to newest)
    getItems(): T[] {
        const items = [];

        const max = this.headPos + this.length - 1;
        for (let i = max; i >= this.headPos; i--) {
            const tmpIdx = i % this.capacity;
            items.push(this.buffer[tmpIdx]);
        }

        return items;
    }

    // * for debugging
    toString(): string {
        const items = [];

        const max = this.headPos + this.length - 1;
        for (let i = this.headPos; i <= max; i++) {
            const tmpIdx= i % this.capacity;
            items.push(this.buffer[tmpIdx]);
        }

        const queueVals= items.join("->");
        return `[${queueVals}]`;
    }

    private getTailPos(): number {
        return mod(this.headPos + this.length - 1, this.capacity);
    }
}

// helper util fn
function mod(n: number, m: number) {
    return ((n % m) + m) % m;
}