89 lines
2.0 KiB
JavaScript
89 lines
2.0 KiB
JavaScript
'use strict';
|
|
|
|
module.exports = TinyQueue;
|
|
module.exports.default = TinyQueue;
|
|
|
|
function TinyQueue(data, compare) {
|
|
if (!(this instanceof TinyQueue)) return new TinyQueue(data, compare);
|
|
|
|
this.data = data || [];
|
|
this.length = this.data.length;
|
|
this.compare = compare || defaultCompare;
|
|
|
|
if (this.length > 0) {
|
|
for (var i = (this.length >> 1) - 1; i >= 0; i--) this._down(i);
|
|
}
|
|
}
|
|
|
|
function defaultCompare(a, b) {
|
|
return a < b ? -1 : a > b ? 1 : 0;
|
|
}
|
|
|
|
TinyQueue.prototype = {
|
|
|
|
push: function (item) {
|
|
this.data.push(item);
|
|
this.length++;
|
|
this._up(this.length - 1);
|
|
},
|
|
|
|
pop: function () {
|
|
if (this.length === 0) return undefined;
|
|
|
|
var top = this.data[0];
|
|
this.length--;
|
|
|
|
if (this.length > 0) {
|
|
this.data[0] = this.data[this.length];
|
|
this._down(0);
|
|
}
|
|
this.data.pop();
|
|
|
|
return top;
|
|
},
|
|
|
|
peek: function () {
|
|
return this.data[0];
|
|
},
|
|
|
|
_up: function (pos) {
|
|
var data = this.data;
|
|
var compare = this.compare;
|
|
var item = data[pos];
|
|
|
|
while (pos > 0) {
|
|
var parent = (pos - 1) >> 1;
|
|
var current = data[parent];
|
|
if (compare(item, current) >= 0) break;
|
|
data[pos] = current;
|
|
pos = parent;
|
|
}
|
|
|
|
data[pos] = item;
|
|
},
|
|
|
|
_down: function (pos) {
|
|
var data = this.data;
|
|
var compare = this.compare;
|
|
var halfLength = this.length >> 1;
|
|
var item = data[pos];
|
|
|
|
while (pos < halfLength) {
|
|
var left = (pos << 1) + 1;
|
|
var right = left + 1;
|
|
var best = data[left];
|
|
|
|
if (right < this.length && compare(data[right], best) < 0) {
|
|
left = right;
|
|
best = data[right];
|
|
}
|
|
if (compare(best, item) >= 0) break;
|
|
|
|
data[pos] = best;
|
|
pos = left;
|
|
}
|
|
|
|
data[pos] = item;
|
|
}
|
|
};
|