an expanding circular buffer implementation

circular-buffer.js

// @ts-check
// eslint-plugin-jsdoc doesn't support @template
/* eslint-disable jsdoc/no-undefined-types,jsdoc/check-tag-names */
/**
 * Copy an array, the lame way
 * @template T
 * @param {T[]} source Source array
 * @param {T[]} dest Destination array
 * @param {number} srcStart Start index of source array
 * @param {number} srcEnd End index of source array plus one
 * @param {number} destStart Start index of destination array
 */
function arrayCopy(source, dest, srcStart, srcEnd, destStart) {
  for (let i = srcStart; i < srcEnd; i++) dest[i - srcStart + destStart] = source[i];
}

/**
 * A circular buffer
 * @template T
 */
class CircularBuffer {
  /**
   * The constructor
   * @param {number} [initialCapacity=16] How large the buffer should be initially
   * @param {boolean} [expand=true] Whether the buffer should expand when full
   * @param {boolean} [overwrite=false] If expand is false, whether to overwrite existing items when full
   */
  constructor(initialCapacity = 16, expand = true, overwrite = false) {
    /**
     * Backing array
     * @type {(T | null)[]}
     */
    this.array = new Array(initialCapacity);
    /** Whether to expand buffer when full */
    this.expand = expand;
    /** Whether to overwrite old contents when full */
    this.overwrite = overwrite;
    this.empty();
  }

  /** Empty the buffer */
  empty() {
    this.array.fill(null);
    /** Number if items in the buffer */
    this.count = 0;
    /**
     * Current read position, or null if buffer is empty
     * @type {number | null}
     */
    this.read = null;
    /**
     * Current write position, or null if buffer is full
     * @type {number | null}
     */
    this.write = 0;
  }

  /**
   * Whether or not the buffer is full
   * @return {boolean}
   */
  isFull() {
    return this.write === null;
  }

  /**
   * Whether or not the buffer is empty
   * @return {boolean}
   */
  isEmpty() {
    return this.read === null;
  }

  /**
   * Resize the buffer
   * @param {number} size New size, should not be 0
   */
  resize(size) {
    let prev = this.array;
    if (size < this.count) throw new Error('New size of array is too small');
    this.array = new Array(size);
    if (this.read !== null) { // buffer contains items that need to be moved
      // ensure write pointer is valid in case buffer is full
      if (this.write === null) this.write = this.read;
      if (this.read >= this.write) { // buffer wrapped
        // copy from read pointer to end of array
        arrayCopy(prev, this.array, this.read, prev.length, 0);
        // copy from start of array to write pointer
        arrayCopy(prev, this.array, 0, this.write, prev.length - this.read);
      } else { // buffer is a continuous region
        // copy from read pointer to write pointer
        arrayCopy(prev, this.array, this.read, this.write, 0);
      }
      this.read = 0;
      if (size === this.count) this.write = null; // new buffer is already full
      else {
        // fill remaining with null
        this.array.fill(null, this.count);
        // set write position to end
        this.write = this.count;
      }
    } else { // nothing is in the buffer
      // reset write pointer to 0 in case buffer was shrinked
      this.write = 0;
    }
  }

  /**
   * Add an item to the buffer
   * @param {T} item
   * @return {boolean} True if space still available, false if full
   */
  push(item) {
    if (this.write === null) { // buffer is full
      if (this.overwrite) { // overwriting is enabled
        // set write target to current read position (tail)
        this.write = this.read;
        // advance read position
        this.read = (this.read + 1) % this.array.length;
      } else if (this.expand) {
        this.resize(this.array.length << 1);
        this.count++;
      } else throw new Error('Buffer is full');
    } else this.count++; // update item count
    // write item
    this.array[this.write] = item;
    // if read pointer is null, set to position of current item
    if (this.read === null) this.read = this.write;
    // advance write position
    this.write = (this.write + 1) % this.array.length;
    if (this.write === this.read) { // buffer is full
      if (this.expand) this.resize(this.array.length << 1); // double current length
      else {
        this.write = null;
        return false;
      }
    }
    return true;
  }

  /**
   * Remove the last item from the buffer
   * @return {T | null} The item, or null if the buffer is empty
   */
  pop() {
    if (this.read === null) return null; // buffer is empty
    // update item count
    this.count--;
    // read current value
    let ret = this.array[this.read];
    // allow item to be garbage collected
    this.array[this.read] = null;
    // if buffer was full, set write pointer to current position
    if (this.write === null) this.write = this.read;
    // advance read position
    this.read = (this.read + 1) % this.array.length;
    // buffer is now empty
    if (this.write === this.read) this.read = null;
    return ret;
  }

  /**
   * Get the item at the top of the buffer, but don't remove it
   * @return {T | null}
   */
  peek() {
    if (this.read === null) return null; // buffer is empty
    // read current value
    return this.array[this.read];
  }
}
/* eslint-enable jsdoc/no-undefined-types,jsdoc/check-tag-names */

module.exports = CircularBuffer;