modules/buffers.js

/*
 * Copyright (c) 2017-2018 Thomas Otterson
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"), to deal in
 * the Software without restriction, including without limitation the rights to
 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
 * the Software, and to permit persons to whom the Software is furnished to do so,
 * subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

/**
 * Provides several types of buffers usable in buffered channels. These are all built on a small, efficient queue (also
 * provided) which is in turn backed by a JavaScript array.
 *
 * @module cispy/buffers
 */

/**
 * **The value returned from a buffer when it has no values in it.**
 *
 * This is used instead of `null` because `null` is a value that can actually be put onto a channel (and therefore
 * into a buffer backing that channel). That means that, despite the assertion that only
 * `{@link module:cispy~Cispy.CLOSED|CLOSED}` cannot be put onto a channel, it's probably not a great idea to put
 * `EMPTY` onto an *unbuffered* channel. While it won't cause an error to be thrown, and while it will be removed from
 * the buffer to allow the next value to be removed, it's likely to cause some odd behavior.
 *
 * @type {Symbol}
 * @memberOf module:cispy~Cispy
 */
const EMPTY = Symbol('EMPTY');

/**
 * A general purpose, highly efficient JavaScript queue. It is backed by a JavaScript array, but it does not
 * use `unshift` to take elements off the array because unshift causes elements to be copied every time it's used.
 * Instead, a pointer is maintained that keeps track of the location of the next element to be dequeued, and when that
 * dequeue happens, the pointer simply moves. When the empty space at the head of the array gets large enough, it's
 * removed by a single slice operation.
 *
 * Putting elements into the queue is just done with a basic `push`, which *is* highly efficient.
 *
 * This type of queue is possible in JavaScript because JS arrays are resizable. In languages with fixed-size arrays,
 * a resizing operation would have to be run each time the queue fills.
 *
 * @namespace Queue
 */

/**
 * Creates a new queue. This queue is created empty, with a backing array of length 0.
 *
 * @returns {module:cispy/buffers~Queue} a new, empty queue
 * @private
 */
function queue() {
  const obj = {
    store: [],
    pointer: 0,

    /**
     * Returns the number of elements stored in the queue. This may or may not equal the length of the backing store.
     *
     * @name count
     * @memberOf module:cispy/buffers~Queue
     * @instance
     * @type {number}
     * @readonly
     */
    get count() {
      return this.store.length - this.pointer;
    },

    /**
     * Returns `true` if the queue is empty.
     *
     * @name empty
     * @memberOf module:cispy/buffers~Queue
     * @instance
     * @type {boolean}
     * @readonly
     */
    get empty() {
      return this.store.length === 0;
    },

    /**
     * Adds an item to the queue.
     *
     * @function enqueue
     * @memberOf module:cispy/buffers~Queue
     * @instance
     * @param {*} item The value being added to the queue.
     */
    enqueue(item) {
      this.store.push(item);
    },

    /**
     * Removes an item from the queue and returns that item. If the removal causes the amount of empty space at the
     * head of the backing store to exceed a threshold, that empty space is removed.
     *
     * @function dequeue
     * @memberOf module:cispy/buffers~Queue
     * @instance
     * @return {*} The oldest stored item in the queue.
     */
    dequeue() {
      if (this.empty) {
        return EMPTY;
      }

      const item = this.store[this.pointer];
      // Removes the items in the backing array before the current pointer, if there is enough empty space before the
      // pointer to justify it.
      if (++this.pointer * 2 >= this.store.length) {
        this.store = this.store.slice(this.pointer);
        this.pointer = 0;
      }
      return item;
    },

    /**
     * Returns the next item in the queue without removing it.
     *
     * @function peek
     * @memberOf module:cispy/buffers~Queue
     * @instance
     * @return {*} The oldest item stored in the queue.
     */
    peek() {
      return this.empty ? EMPTY : this.store[this.pointer];
    },

    /**
     * Filters out any item in the queue that does not cause the supplied predicate function to return `true` when
     * passed that item. This is not exactly a general purpose queue operation, but we need it with channels that will
     * occasionally want to get rid of inactive handlers.
     *
     * @function filter
     * @memberOf module:cispy/buffers~Queue
     * @instance
     * @param {Function} fn The predicate function that determines whether an element remains in the queue.
     */
    filter(fn) {
      for (let i = 0, { count } = this; i < count; ++i) {
        const item = this.dequeue();
        if (fn(item)) {
          this.enqueue(item);
        }
      }
    }
  };

  return obj;
}

// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Buffer implementations
//
// Each of the three buffers has the same three properties and two operations. The difference between them is the
// behavior of the `full` property and of the `add` operation.
//
// size: the largest number of items that can be in the buffer at once.
// count: the actual number of items in the buffer.
// full: whether or not the buffer is full.
// add: adds an item to the buffer.
// remove: removes an item from the buffer (and returns it).
// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

/**
 * The base for buffer classes, containing the common functionality between all of them. The only properties that
 * actually vary between buffer types are `full` (whether or not the buffer is full) and `add` (because different
 * buffers have different behavior when something is added to a full buffer).
 *
 * These buffers are each backed by a {@link Queue}.
 *
 * @namespace Buffer
 */

/**
 * Creates a base buffer of the given size.
 *
 * @param  {number} size the maximum number of items that the new buffer can hold.
 * @return {module:cispy/buffers~Buffer} the new buffer.
 * @private
 */
function base(size) {
  const q = queue();

  return {
    /**
     * The queue that backs this buffer.
     *
     * @name queue
     * @memberOf module:cispy/buffers~Buffer
     * @instance
     * @type {module:cispy/buffers~Queue}
     * @readonly
     */
    get queue() {
      return q;
    },

    /**
     * The size of the buffer.
     *
     * This is *not* the number of elements in the buffer; it is the number of items that can be stored without the
     * buffer overflowing. It is static and is set at creation time.
     *
     * @name size
     * @memberOf module:cispy/buffers~Buffer
     * @instance
     * @type {number}
     * @readonly
     */
    get size() {
      return size;
    },

    /**
     * The number of items currently being stored by the buffer.
     *
     * @name count
     * @memberOf module:cispy/buffers~Buffer
     * @instance
     * @type {number}
     * @readonly
     */
    get count() {
      return this.queue.count;
    },

    /**
     * Removes and returns the oldest item in the buffer.
     *
     * @function remove
     * @memberOf module:cispy/buffers~Buffer
     * @instance
     * @return {*} The oldest item in the buffer.
     */
    remove() {
      return this.queue.dequeue();
    }
  };
}

/**
 * **Creates a fixed buffer of the specified capacity.**
 *
 * A fixed buffer is a 'normal' buffer, one that stores and returns items on demand. While it is capable of being
 * over-filled, that ability is not used in Cispy. A buffer that is full will cause the next put to its channel to
 * block until at least one item is removed from the buffer.
 *
 * This buffer is able to be passed to `{@link module:cispy~Cispy.chan|chan}` to create a buffered channel.
 *
 * @function fixedBuffer
 * @memberOf module:cispy~Cispy
 * @param {number} size The number of items that the new buffer can hold before it's full.
 * @return {module:cispy/buffers~FixedBuffer} A new fixed buffer of the specified capacity.
 */
function fixed(size) {
  /**
   * A buffer implementation that never discards buffered items when a new item is added.
   *
   * This buffer has a concept of *full*, but it's a soft limit. If the size of the buffer is exceeded, added items are
   * still stored. {@link module:cispy/buffers~FixedBuffer#full|full} returns `true` any time that the size is
   * reached or exceeded, so it's entirely possible to call {@link module:cispy/buffers~Buffer#remove|remove} on a
   * full buffer and have it still be full.
   *
   * @namespace FixedBuffer
   * @augments {module:cispy/buffers~Buffer}
   */
  return Object.assign(
    Object.create(base(size), {
      // Object.assign doesn't handle getters and setters properly, so we add this getter as a property descriptor
      // in the second argument of Object.create instead.
      full: {
        /**
         * Whether or not the buffer has as many or more items stored as its
         * {@link module:cispy/buffers~Buffer#size|size}.
         *
         * @name full
         * @memberOf module:cispy/buffers~FixedBuffer
         * @instance
         * @type {number}
         * @readonly
         */
        get() {
          return this.queue.count >= this.size;
        }
      }
    }),
    {
      /**
       * Adds one or more items to the buffer. These items will be added even if the buffer is full.
       *
       * @function add
       * @memberOf module:cispy/buffers~FixedBuffer
       * @instance
       * @param {...*} items The items to be added to the buffer.
       */
      add(...items) {
        for (const item of items) {
          this.queue.enqueue(item);
        }
      }
    }
  );
}

/**
 * **Creates a dropping buffer of the specified capacity.**
 *
 * A dropping buffer silently drops the item being added if the buffer is already at capacity. Since adding a new
 * item will always 'succeed' (even if it succeeds by just ignoring the add), it is never considered full and
 * therefore a put to a channel buffered by a dropping buffer never blocks.
 *
 * This buffer is able to be passed to `{@link module:cispy~Cispy.chan|chan}` to create a buffered channel.
 *
 * @function droppingBuffer
 * @memberOf module:cispy~Cispy
 * @param {number} size The number of items that the new buffer can hold before newest items are dropped on add.
 * @return {module:cispy/buffers~DroppingBuffer} A new dropping buffer of the specified capacity.
 */
function dropping(size) {
  /**
   * A buffer implementation that drops newly added items when the buffer is full.
   *
   * This dropping behavior is silent: the new item is simply not added to the queue. Note that this buffer is never
   * `full` because it can always be added to wiehtout exceeding the size, even if that 'adding' doesn't result in a new
   * item actually appearing in the buffer.
   *
   * @namespace DroppingBuffer
   * @extends {module:cispy/buffers~Buffer}
   */
  return Object.assign(
    Object.create(base(size), {
      full: {
        /**
         * Whether or not the buffer is full. As a {@link module:cispy/buffers~DroppingBuffer|DroppingBuffer} is
         * never considered full, this will always return `false`.
         *
         * @name full
         * @memberOf module:cispy/buffers~DroppingBuffer
         * @instance
         * @type {number}
         * @readonly
         */
        get() {
          return false;
        }
      }
    }),
    {
      /**
       * Adds one or more items to the buffer. If the buffer has already reached its capacity, then the item is silently
       * dropped instead.
       *
       * @function add
       * @memberOf module:cispy/buffers~DroppingBuffer
       * @instance
       * @param {...*} items the items added to the buffer.
       */
      add(...items) {
        for (const item of items) {
          if (this.queue.count < this.size) {
            this.queue.enqueue(item);
          }
        }
      }
    }
  );
}

/**
 * **Creates a sliding buffer of the specified capacity.**
 *
 * A sliding buffer drops the first-added (oldest) item already in the buffer if a new item is added when the buffer
 * is already at capacity. Since it's always capable of having items added to it, it's never considered full, and
 * therefore a put to a channel buffered by a sliding buffer never blocks.
 *
 * This buffer is able to be passed to `{@link module:cispy~Cispy.chan|chan}` to create a buffered channel.
 *
 * @function slidingBuffer
 * @memberOf module:cispy~Cispy
 * @param {number} size The number of items that the new buffer can hold before oldest items are dropped on add.
 * @return {module:cispy/buffers~SlidingBuffer} A new sliding buffer of the specified capacity.
 */
function sliding(size) {
  /**
   * A buffer implementation that drops the oldest item when an item is added to a full buffer.
   *
   * This is very similar to {@link module:cispy/buffers~DroppingBuffer|DroppingBuffer}; the only difference is in
   * what happens when an item is added. In this buffer, the new item is indeed added to the buffer, but in order to
   * keep the count of the buffer at or below its size, the oldest item in the buffer is silently dropped.
   *
   * @namespace SlidingBuffer
   * @extends {module:cispy/buffers~Buffer}
   */
  return Object.assign(
    Object.create(base(size), {
      /**
       * Whether or not the buffer is full. As a {@link module:cispy/buffers~SlidingBuffer|SlidingBuffer} is
       * never considered full, this will always return `false`.
       *
       * @name full
       * @memberOf module:cispy/buffers~SlidingBuffer
       * @instance
       * @type {number}
       * @readonly
       */
      full: {
        get() {
          return false;
        }
      }
    }),
    {
      /**
       * Adds one or more items to the buffer. If the buffer has already reached its capacity, then the oldest items in
       * the buffer are dropped to make way for the new items.
       *
       * @function add
       * @memberOf module:cispy/buffers~SlidingBuffer
       * @instance
       * @param {...*} items The items to be added to the buffer.
       */
      add(...items) {
        for (const item of items) {
          if (this.queue.count === this.size) {
            this.queue.dequeue();
          }
          this.queue.enqueue(item);
        }
      }
    }
  );
}

module.exports = {
  EMPTY,
  queue,
  fixed,
  dropping,
  sliding
};