/** * A queue that can enqueue items at the end, and dequeue items from the front. * */ class Queue { constructor() { this._array = []; this._offset = 0; this._length = 0; } /** * The length of the queue. * * * @type {number} * @readonly */ get length() { return this._length; } /** * Enqueues the specified item. * * @param {*} item The item to enqueue. */ enqueue(item) { this._array.push(item); this._length++; } /** * Dequeues an item. Returns undefined if the queue is empty. * * @returns {*} The the dequeued item. */ dequeue() { if (this._length === 0) { return undefined; } const array = this._array; let offset = this._offset; const 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. */ peek() { 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. */ contains(item) { return this._array.indexOf(item) !== -1; } /** * Remove all items from the queue. */ clear() { 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. */ sort(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 a is less than b, * a positive value if a is greater than b, or * 0 if a is equal to b. * * @example * function compareNumbers(a, b) { * return a - b; * } */ export default Queue;