Ring buffer implementation

circularQueue.spec.js

class CircularQueue {
  constructor(size) {
    this.size = size;
    this.storage = Array.from(new Array(size));
    Object.seal(this.storage);
    this.head = -1;
    this.tail = -1;
  }

  queue(value) {
    if (this.isFull()) {
      throw new Error("Queue is full");
    }
    if (this.head === -1 && this.tail === -1) {
      this.head = 0;
      this.tail = 0;
    } else {
      this.head = (this.head + 1) % this.size;
    }
    this.storage[this.head] = value;
  }

  dequeue() {
    if (this.isEmpty()) {
      throw new Error("Queue is empty");
    }
    const value = this.storage[this.tail];
    this.storage[this.tail] = undefined;
    this.tail = (this.tail + 1) % this.size;
    if (this.tail - 1 == this.head) {
      this.tail = -1;
      this.head = -1;
    }
    return value;
  }

  isFull() {
    return (this.head + 1) % this.size == this.tail;
  }

  isEmpty() {
    return this.head === -1 && this.tail === -1;
  }
}

describe("CircularQueue", () => {
  let q;

  beforeEach(() => {
    q = new CircularQueue(4);
  });

  test("first in first out", () => {
    q.queue(1);
    q.queue(2);
    expect(q.dequeue()).toEqual(1);
  });

  test("throws when queueing to full", () => {
    q.queue(1);
    q.queue(2);
    q.queue(3);
    q.queue(4);
    expect(() => q.queue(5)).toThrowError("Queue is full");
  });

  test("throws when dequeueing from empty", () => {
    expect(() => q.dequeue()).toThrowError("Queue is empty");
  });

  test("dequeue frees capacity", () => {
    q.queue(1);
    q.queue(2);
    q.queue(3);
    q.queue(4);
    expect(q.dequeue()).toEqual(1);
    q.queue(5);
    expect(q.dequeue()).toEqual(2);
  });

  test("throws when dequeueing below capacity starting from non-empty queue", () => {
    q.queue(1);
    q.dequeue();
    expect(() => q.dequeue()).toThrowError("Queue is empty");
  });

  test("just a random-ass test", () => {
    q.queue(1);
    q.queue(2);
    q.queue(3);
    q.queue(4);
    expect(q.dequeue()).toEqual(1);
    expect(q.dequeue()).toEqual(2);
    expect(q.dequeue()).toEqual(3);
    q.queue(5);
    q.queue(6);
    q.queue(7);
    expect(() => q.queue(8)).toThrowError("Queue is full");
    expect(q.dequeue()).toEqual(4);
    expect(q.dequeue()).toEqual(5);
    expect(q.dequeue()).toEqual(6);
    expect(q.dequeue()).toEqual(7);
    expect(() => q.dequeue()).toThrowError("Queue is empty");
  });
});