Queue.js

/**
 * A queue that can enqueue items at the end, and dequeue items from the front.
 *
 * @alias Queue
 * @constructor
 */
function Queue() {
  this._array = [];
  this._offset = 0;
  this._length = 0;
}

Object.defineProperties(Queue.prototype, {
  /**
   * The length of the queue.
   *
   * @memberof Queue.prototype
   *
   * @type {Number}
   * @readonly
   */
  length: {
    get: function () {
      return this._length;
    },
  },
});

/**
 * Enqueues the specified item.
 *
 * @param {*} item The item to enqueue.
 */
Queue.prototype.enqueue = function (item) {
  this._array.push(item);
  this._length++;
};

/**
 * Dequeues an item.  Returns undefined if the queue is empty.
 *
 * @returns {*} The the dequeued item.
 */
Queue.prototype.dequeue = function () {
  if (this._length === 0) {
    return undefined;
  }

  var array = this._array;
  var offset = this._offset;
  var item = array[offset];
  array[offset] = undefined;

  offset++;
  if (offset > 10 && offset * 2 > array.length) {
    //compact array
    this._array = array.slice(offset);
    offset = 0;
  }

  this._offset = offset;
  this._length--;

  return item;
};

/**
 * Returns the item at the front of the queue.  Returns undefined if the queue is empty.
 *
 * @returns {*} The item at the front of the queue.
 */
Queue.prototype.peek = function () {
  if (this._length === 0) {
    return undefined;
  }

  return this._array[this._offset];
};

/**
 * Check whether this queue contains the specified item.
 *
 * @param {*} item The item to search for.
 */
Queue.prototype.contains = function (item) {
  return this._array.indexOf(item) !== -1;
};

/**
 * Remove all items from the queue.
 */
Queue.prototype.clear = function () {
  this._array.length = this._offset = this._length = 0;
};

/**
 * Sort the items in the queue in-place.
 *
 * @param {Queue.Comparator} compareFunction A function that defines the sort order.
 */
Queue.prototype.sort = function (compareFunction) {
  if (this._offset > 0) {
    //compact array
    this._array = this._array.slice(this._offset);
    this._offset = 0;
  }

  this._array.sort(compareFunction);
};

/**
 * A function used to compare two items while sorting a queue.
 * @callback Queue.Comparator
 *
 * @param {*} a An item in the array.
 * @param {*} b An item in the array.
 * @returns {Number} Returns a negative value if <code>a</code> is less than <code>b</code>,
 *          a positive value if <code>a</code> is greater than <code>b</code>, or
 *          0 if <code>a</code> is equal to <code>b</code>.
 *
 * @example
 * function compareNumbers(a, b) {
 *     return a - b;
 * }
 */
export default Queue;