import Check from "./Check.js"; import defaultValue from "./defaultValue.js"; import defined from "./defined.js"; /** * Array implementation of a heap. * * @alias Heap * @constructor * @private * * @param {Object} options Object with the following properties: * @param {Heap.ComparatorCallback} options.comparator The comparator to use for the heap. If comparator(a, b) is less than 0, sort a to a lower index than b, otherwise sort to a higher index. */ function Heap(options) { //>>includeStart('debug', pragmas.debug); Check.typeOf.object("options", options); Check.defined("options.comparator", options.comparator); //>>includeEnd('debug'); this._comparator = options.comparator; this._array = []; this._length = 0; this._maximumLength = undefined; } Object.defineProperties(Heap.prototype, { /** * Gets the length of the heap. * * @memberof Heap.prototype * * @type {Number} * @readonly */ length: { get: function () { return this._length; }, }, /** * Gets the internal array. * * @memberof Heap.prototype * * @type {Array} * @readonly */ internalArray: { get: function () { return this._array; }, }, /** * Gets and sets the maximum length of the heap. * * @memberof Heap.prototype * * @type {Number} */ maximumLength: { get: function () { return this._maximumLength; }, set: function (value) { //>>includeStart('debug', pragmas.debug); Check.typeOf.number.greaterThanOrEquals("maximumLength", value, 0); //>>includeEnd('debug'); var originalLength = this._length; if (value < originalLength) { var array = this._array; // Remove trailing references for (var i = value; i < originalLength; ++i) { array[i] = undefined; } this._length = value; array.length = value; } this._maximumLength = value; }, }, /** * The comparator to use for the heap. If comparator(a, b) is less than 0, sort a to a lower index than b, otherwise sort to a higher index. * * @memberof Heap.prototype * * @type {Heap.ComparatorCallback} */ comparator: { get: function () { return this._comparator; }, }, }); function swap(array, a, b) { var temp = array[a]; array[a] = array[b]; array[b] = temp; } /** * Resizes the internal array of the heap. * * @param {Number} [length] The length to resize internal array to. Defaults to the current length of the heap. */ Heap.prototype.reserve = function (length) { length = defaultValue(length, this._length); this._array.length = length; }; /** * Update the heap so that index and all descendants satisfy the heap property. * * @param {Number} [index=0] The starting index to heapify from. */ Heap.prototype.heapify = function (index) { index = defaultValue(index, 0); var length = this._length; var comparator = this._comparator; var array = this._array; var candidate = -1; var inserting = true; while (inserting) { var right = 2 * (index + 1); var left = right - 1; if (left < length && comparator(array[left], array[index]) < 0) { candidate = left; } else { candidate = index; } if (right < length && comparator(array[right], array[candidate]) < 0) { candidate = right; } if (candidate !== index) { swap(array, candidate, index); index = candidate; } else { inserting = false; } } }; /** * Resort the heap. */ Heap.prototype.resort = function () { var length = this._length; for (var i = Math.ceil(length / 2); i >= 0; --i) { this.heapify(i); } }; /** * Insert an element into the heap. If the length would grow greater than maximumLength * of the heap, extra elements are removed. * * @param {*} element The element to insert * * @return {*} The element that was removed from the heap if the heap is at full capacity. */ Heap.prototype.insert = function (element) { //>>includeStart('debug', pragmas.debug); Check.defined("element", element); //>>includeEnd('debug'); var array = this._array; var comparator = this._comparator; var maximumLength = this._maximumLength; var index = this._length++; if (index < array.length) { array[index] = element; } else { array.push(element); } while (index !== 0) { var parent = Math.floor((index - 1) / 2); if (comparator(array[index], array[parent]) < 0) { swap(array, index, parent); index = parent; } else { break; } } var removedElement; if (defined(maximumLength) && this._length > maximumLength) { removedElement = array[maximumLength]; this._length = maximumLength; } return removedElement; }; /** * Remove the element specified by index from the heap and return it. * * @param {Number} [index=0] The index to remove. * @returns {*} The specified element of the heap. */ Heap.prototype.pop = function (index) { index = defaultValue(index, 0); if (this._length === 0) { return undefined; } //>>includeStart('debug', pragmas.debug); Check.typeOf.number.lessThan("index", index, this._length); //>>includeEnd('debug'); var array = this._array; var root = array[index]; swap(array, index, --this._length); this.heapify(index); array[this._length] = undefined; // Remove trailing reference return root; }; /** * The comparator to use for the heap. * @callback Heap.ComparatorCallback * @param {*} a An element in the heap. * @param {*} b An element in the heap. * @returns {Number} If the result of the comparison is less than 0, sort a to a lower index than b, otherwise sort to a higher index. */ export default Heap;