Innovenergy_trunk/frontend/node_modules/graphlib/lib/data/priority-queue.js

153 lines
4.1 KiB
JavaScript

var _ = require("../lodash");
module.exports = PriorityQueue;
/**
* A min-priority queue data structure. This algorithm is derived from Cormen,
* et al., "Introduction to Algorithms". The basic idea of a min-priority
* queue is that you can efficiently (in O(1) time) get the smallest key in
* the queue. Adding and removing elements takes O(log n) time. A key can
* have its priority decreased in O(log n) time.
*/
function PriorityQueue() {
this._arr = [];
this._keyIndices = {};
}
/**
* Returns the number of elements in the queue. Takes `O(1)` time.
*/
PriorityQueue.prototype.size = function() {
return this._arr.length;
};
/**
* Returns the keys that are in the queue. Takes `O(n)` time.
*/
PriorityQueue.prototype.keys = function() {
return this._arr.map(function(x) { return x.key; });
};
/**
* Returns `true` if **key** is in the queue and `false` if not.
*/
PriorityQueue.prototype.has = function(key) {
return _.has(this._keyIndices, key);
};
/**
* Returns the priority for **key**. If **key** is not present in the queue
* then this function returns `undefined`. Takes `O(1)` time.
*
* @param {Object} key
*/
PriorityQueue.prototype.priority = function(key) {
var index = this._keyIndices[key];
if (index !== undefined) {
return this._arr[index].priority;
}
};
/**
* Returns the key for the minimum element in this queue. If the queue is
* empty this function throws an Error. Takes `O(1)` time.
*/
PriorityQueue.prototype.min = function() {
if (this.size() === 0) {
throw new Error("Queue underflow");
}
return this._arr[0].key;
};
/**
* Inserts a new key into the priority queue. If the key already exists in
* the queue this function returns `false`; otherwise it will return `true`.
* Takes `O(n)` time.
*
* @param {Object} key the key to add
* @param {Number} priority the initial priority for the key
*/
PriorityQueue.prototype.add = function(key, priority) {
var keyIndices = this._keyIndices;
key = String(key);
if (!_.has(keyIndices, key)) {
var arr = this._arr;
var index = arr.length;
keyIndices[key] = index;
arr.push({key: key, priority: priority});
this._decrease(index);
return true;
}
return false;
};
/**
* Removes and returns the smallest key in the queue. Takes `O(log n)` time.
*/
PriorityQueue.prototype.removeMin = function() {
this._swap(0, this._arr.length - 1);
var min = this._arr.pop();
delete this._keyIndices[min.key];
this._heapify(0);
return min.key;
};
/**
* Decreases the priority for **key** to **priority**. If the new priority is
* greater than the previous priority, this function will throw an Error.
*
* @param {Object} key the key for which to raise priority
* @param {Number} priority the new priority for the key
*/
PriorityQueue.prototype.decrease = function(key, priority) {
var index = this._keyIndices[key];
if (priority > this._arr[index].priority) {
throw new Error("New priority is greater than current priority. " +
"Key: " + key + " Old: " + this._arr[index].priority + " New: " + priority);
}
this._arr[index].priority = priority;
this._decrease(index);
};
PriorityQueue.prototype._heapify = function(i) {
var arr = this._arr;
var l = 2 * i;
var r = l + 1;
var largest = i;
if (l < arr.length) {
largest = arr[l].priority < arr[largest].priority ? l : largest;
if (r < arr.length) {
largest = arr[r].priority < arr[largest].priority ? r : largest;
}
if (largest !== i) {
this._swap(i, largest);
this._heapify(largest);
}
}
};
PriorityQueue.prototype._decrease = function(index) {
var arr = this._arr;
var priority = arr[index].priority;
var parent;
while (index !== 0) {
parent = index >> 1;
if (arr[parent].priority < priority) {
break;
}
this._swap(index, parent);
index = parent;
}
};
PriorityQueue.prototype._swap = function(i, j) {
var arr = this._arr;
var keyIndices = this._keyIndices;
var origArrI = arr[i];
var origArrJ = arr[j];
arr[i] = origArrJ;
arr[j] = origArrI;
keyIndices[origArrJ.key] = i;
keyIndices[origArrI.key] = j;
};