function AVLTree() {
this.root = null;
}n/a
function BST(compareFn) {
this.root = null;
this._size = 0;
/**
* @var Comparator
*/
this._comparator = new Comparator(compareFn);
/**
* Read-only property for the size of the tree
*/
Object.defineProperty(this, 'size', {
get: function () { return this._size; }.bind(this)
});
}n/a
function DisjointSetForest() {
this._parents = {};
this._ranks = {};
this._sizes = {};
}n/a
function FenwickTree(length) {
this._elements = new Array(length + 1);
for (var i = 0; i < this._elements.length ; i++)
this._elements[i] = 0;
}n/a
function Graph(directed) {
this.directed = (directed === undefined ? true : !!directed);
this.adjList = Object.create(null);
this.vertices = new HashSet();
}n/a
function HashTable(initialCapacity) {
this._table = new Array(initialCapacity || 64);
this._items = 0;
Object.defineProperty(this, 'capacity', {
get: function () {
return this._table.length;
}
});
Object.defineProperty(this, 'size', {
get: function () {
return this._items;
}
});
}n/a
function LinkedList() {
this._length = 0;
this.head = null;
this.tail = null;
// Read-only length property
Object.defineProperty(this, 'length', {
get: function () {
return this._length;
}.bind(this)
});
}n/a
function PriorityQueue(initialItems) {
var self = this;
MinHeap.call(this, function (a, b) {
return self.priority(a) < self.priority(b) ? -1 : 1;
});
this._priority = {};
initialItems = initialItems || {};
Object.keys(initialItems).forEach(function (item) {
self.insert(item, initialItems[item]);
});
}n/a
function Queue() {
this._elements = new LinkedList();
Object.defineProperty(this, 'length', {
get: function () {
return this._elements.length;
}.bind(this)
});
}n/a
DataStructures.Set = function () {
this._elements = new HashTable(arguments.length);
this.add.apply(this, arguments);
Object.defineProperty(this, 'size', {
get: function () {
return this._elements.size;
}
});
}n/a
function Stack() {
Queue.call(this);
}n/a
function Treap() {
this.root = null;
}n/a
Geometry.BezierCurve = function (points) {
this.n = points.length;
this.p = [];
// The binomial coefficient
var c = [1];
var i, j;
for (i = 1; i < this.n; ++i) {
c.push(0);
for (j = i; j >= 1; --j) {
c[j] += c[j - 1];
}
}
// the i-th control point times the coefficient
for (i = 0; i < this.n; ++i) {
this.p.push({x: c[i] * points[i].x, y: c[i] * points[i].y});
}
}n/a
Math.fibonacci = function (n) {
var fibNMinus2 = 0,
fibNMinus1 = 1,
fib = n;
for (var i = 1; i < n; i++) {
fib = fibNMinus1 + fibNMinus2;
fibNMinus2 = fibNMinus1;
fibNMinus1 = fib;
}
return fib;
}n/a
Math.gcd = function (a, b) {
var tmp = a;
a = Math.max(a, b);
b = Math.min(tmp, b);
while (b !== 0) {
tmp = b;
b = a % b;
a = tmp;
}
return a;
}n/a
Math.lcm = function () { [native code] }n/a
Math.powerSet = function (array) {
if (array.length === 0) {
return [];
}
var powerSet = [];
var cache = [];
var i;
for (i = 0; i < array.length; i++) {
cache[i] = true;
}
for (i = 0; i < Math.pow(2, array.length); i++) {
powerSet.push([]);
for (var j = 0; j < array.length; j++) {
if (i % Math.pow(2, j) === 0) {
cache[j] = !cache[j];
}
if (cache[j]) {
powerSet[i].push(array[j]);
}
}
}
return powerSet;
}n/a
Search.dfs = function (node, callback) {
if (node) {
inOrder(node.left, callback);
callback(node.value);
inOrder(node.right, callback);
}
}n/a
function Comparator(compareFn) {
if (compareFn) {
this.compare = compareFn;
}
}n/a
function AVLTree() {
this.root = null;
}n/a
function BST(compareFn) {
this.root = null;
this._size = 0;
/**
* @var Comparator
*/
this._comparator = new Comparator(compareFn);
/**
* Read-only property for the size of the tree
*/
Object.defineProperty(this, 'size', {
get: function () { return this._size; }.bind(this)
});
}n/a
function DisjointSetForest() {
this._parents = {};
this._ranks = {};
this._sizes = {};
}n/a
function FenwickTree(length) {
this._elements = new Array(length + 1);
for (var i = 0; i < this._elements.length ; i++)
this._elements[i] = 0;
}n/a
function Graph(directed) {
this.directed = (directed === undefined ? true : !!directed);
this.adjList = Object.create(null);
this.vertices = new HashSet();
}n/a
function HashTable(initialCapacity) {
this._table = new Array(initialCapacity || 64);
this._items = 0;
Object.defineProperty(this, 'capacity', {
get: function () {
return this._table.length;
}
});
Object.defineProperty(this, 'size', {
get: function () {
return this._items;
}
});
}n/a
function LinkedList() {
this._length = 0;
this.head = null;
this.tail = null;
// Read-only length property
Object.defineProperty(this, 'length', {
get: function () {
return this._length;
}.bind(this)
});
}n/a
function PriorityQueue(initialItems) {
var self = this;
MinHeap.call(this, function (a, b) {
return self.priority(a) < self.priority(b) ? -1 : 1;
});
this._priority = {};
initialItems = initialItems || {};
Object.keys(initialItems).forEach(function (item) {
self.insert(item, initialItems[item]);
});
}n/a
function Queue() {
this._elements = new LinkedList();
Object.defineProperty(this, 'length', {
get: function () {
return this._elements.length;
}.bind(this)
});
}n/a
Set = function () {
this._elements = new HashTable(arguments.length);
this.add.apply(this, arguments);
Object.defineProperty(this, 'size', {
get: function () {
return this._elements.size;
}
});
}n/a
function Stack() {
Queue.call(this);
}n/a
function Treap() {
this.root = null;
}n/a
function AVLTree() {
this.root = null;
}n/a
_find = function (value, current) {
if (!current) {
return null;
}
var node;
if (current.value === value) {
node = current;
} else if (current.value > value) {
node = this._find(value, current.left);
} else if (current.value < value) {
node = this._find(value, current.right);
}
return node;
}...
this.preOrder(current.right, callback);
};
/**
* Finds a node by its value.
*/
AVLTree.prototype.find = function (value) {
return this._find(value, this.root);
};
/**
* Finds a node by its value in the given sub-tree.
*/
AVLTree.prototype._find = function (value, current) {
if (!current) {
..._findMax = function (node, current) {
current = current || {
value: -Infinity
};
if (!node) {
return current;
}
if (current.value < node.value) {
current = node;
}
return this._findMax(node.right, current);
}...
};
if (!node) {
return current;
}
if (current.value < node.value) {
current = node;
}
return this._findMax(node.right, current);
};
/**
* Finds the node with minimum value in the whole tree.
*/
AVLTree.prototype.findMin = function () {
return this._findMin(this.root);
..._findMin = function (node, current) {
current = current || {
value: Infinity
};
if (!node) {
return current;
}
if (current.value > node.value) {
current = node;
}
return this._findMin(node.left, current);
}...
};
if (!node) {
return current;
}
if (current.value > node.value) {
current = node;
}
return this._findMin(node.left, current);
};
/**
* Finds the node with maximum value in the given
* sub-tree.
*/
AVLTree.prototype._findMax = function (node, current) {
...find = function (value) {
return this._find(value, this.root);
}...
}
};
/**
* Removes a node by its value.
*/
AVLTree.prototype.remove = function (value) {
var node = this.find(value);
if (!node) {
return false;
}
if (node.left && node.right) {
var min = this.findMin(node.right);
var temp = node.value;
...findMax = function () {
return this._findMax(this.root);
}n/a
findMin = function () {
return this._findMin(this.root);
}...
AVLTree.prototype.remove = function (value) {
var node = this.find(value);
if (!node) {
return false;
}
if (node.left && node.right) {
var min = this.findMin(node.right);
var temp = node.value;
node.value = min.value;
min.value = temp;
return this.remove(min);
} else if (node.left) {
this.replaceChild(node.parent, node, node.left);
this.keepHeightBalance(node.left, true);
...getNodeHeight = function (node) {
var height = 1;
if (node.left !== null && node.right !== null) {
height = Math.max(node.left.height, node.right.height) + 1;
} else if (node.left !== null) {
height = node.left.height + 1;
} else if (node.right !== null) {
height = node.right.height + 1;
}
return height;
}...
* root and checking for invalid heights.
*/
AVLTree.prototype.keepHeightBalance = function (node, afterRemove) {
var current = node;
var traveledNodes = [];
while (current !== null) {
traveledNodes.push(current);
current.height = this.getNodeHeight(current);
if (!this.isNodeBalanced(current)) {
var nodesToBeRestructured = (afterRemove) ?
this.getNodesToRestructureAfterRemove(traveledNodes) :
this.getNodesToRestructureAfterInsert(traveledNodes);
this.restructure(nodesToBeRestructured);
}
current = current.parent;
...getNodesToRestructureAfterInsert = function (traveledNodes) {
// z is last traveled node - imbalance found at z
var zIndex = traveledNodes.length - 1;
var z = traveledNodes[zIndex];
// y should be child of z with larger height
// (must be ancestor of inserted node)
// therefore, last traveled node is correct.
var yIndex = traveledNodes.length - 2;
var y = traveledNodes[yIndex];
// x should be tallest child of y
// If children same height, x should be ancestor
// of inserted node (in traveled path)
var x;
if (y.left !== null && y.right !== null) {
if (y.left.height > y.right.height) {
x = y.left;
} else if (y.left.height < y.right.height) {
x = y.right;
} else if (y.left.height === y.right.height) {
var xIndex = traveledNodes.length - 3;
x = traveledNodes[xIndex];
}
} else if (y.left !== null && y.right === null) {
x = y.left;
} else if (y.right !== null && y.left === null) {
x = y.right;
}
return [x, y, z];
}...
var traveledNodes = [];
while (current !== null) {
traveledNodes.push(current);
current.height = this.getNodeHeight(current);
if (!this.isNodeBalanced(current)) {
var nodesToBeRestructured = (afterRemove) ?
this.getNodesToRestructureAfterRemove(traveledNodes) :
this.getNodesToRestructureAfterInsert(traveledNodes);
this.restructure(nodesToBeRestructured);
}
current = current.parent;
}
};
/**
...getNodesToRestructureAfterRemove = function (traveledNodes) {
// z is last traveled node - imbalance found at z
var zIndex = traveledNodes.length - 1;
var z = traveledNodes[zIndex];
// y should be child of z with larger height
// (cannot be ancestor of removed node)
var y;
if (z.left !== null && z.right !== null) {
y = (z.left === y) ? z.right : z.left;
} else if (z.left !== null && z.right === null) {
y = z.left;
} else if (z.right !== null && z.left === null) {
y = z.right;
}
// x should be tallest child of y
// If children same height, x should be child of y
// that has same orientation as z to y
var x;
if (y.left !== null && y.right !== null) {
if (y.left.height > y.right.height) {
x = y.left;
} else if (y.left.height < y.right.height) {
x = y.right;
} else if (y.left.height === y.right.height) {
x = (z.left === y) ? y.left : y.right;
}
} else if (y.left !== null && y.right === null) {
x = y.left;
} else if (y.right !== null && y.left === null) {
x = y.right;
}
return [x, y, z];
}...
var current = node;
var traveledNodes = [];
while (current !== null) {
traveledNodes.push(current);
current.height = this.getNodeHeight(current);
if (!this.isNodeBalanced(current)) {
var nodesToBeRestructured = (afterRemove) ?
this.getNodesToRestructureAfterRemove(traveledNodes) :
this.getNodesToRestructureAfterInsert(traveledNodes);
this.restructure(nodesToBeRestructured);
}
current = current.parent;
}
};
...getTreeHeight = function () {
var current = this.root;
if (!current) {
return 0;
}
return 1 + Math.max(this.getNodeHeight(current._left),
this._getNodeHeight(current._right));
}n/a
inOrder = function (current, callback) {
if (!current) {
return;
}
this.inOrder(current.left, callback);
if (typeof callback === 'function') {
callback(current);
}
this.inOrder(current.right, callback);
}...
/**
* In-order traversal from the given node.
*/
AVLTree.prototype.inOrder = function (current, callback) {
if (!current) {
return;
}
this.inOrder(current.left, callback);
if (typeof callback === 'function') {
callback(current);
}
this.inOrder(current.right, callback);
};
/**
...insert = function (value, current) {
if (this.root === null) {
this.root = new Node(value, null, null, null, 1);
this.keepHeightBalance(this.root);
return;
}
var insertKey;
current = current || this.root;
if (current.value > value) {
insertKey = 'left';
} else {
insertKey = 'right';
}
if (!current[insertKey]) {
current[insertKey] = new Node(value, null, null, current);
this.keepHeightBalance(current[insertKey], false);
} else {
this.insert(value, current[insertKey]);
}
}...
insertKey = 'right';
}
if (!current[insertKey]) {
current[insertKey] = new Node(value, null, null, current);
this.keepHeightBalance(current[insertKey], false);
} else {
this.insert(value, current[insertKey]);
}
};
/**
* In-order traversal from the given node.
*/
AVLTree.prototype.inOrder = function (current, callback) {
...isNodeBalanced = function (node) {
var isBalanced = true;
if (node.left !== null && node.right !== null) {
isBalanced = (Math.abs(node.left.height - node.right.height) <= 1);
} else if (node.right !== null && node.left === null) {
isBalanced = node.right.height < 2;
} else if (node.left !== null && node.right === null) {
isBalanced = node.left.height < 2;
}
return isBalanced;
}...
*/
AVLTree.prototype.keepHeightBalance = function (node, afterRemove) {
var current = node;
var traveledNodes = [];
while (current !== null) {
traveledNodes.push(current);
current.height = this.getNodeHeight(current);
if (!this.isNodeBalanced(current)) {
var nodesToBeRestructured = (afterRemove) ?
this.getNodesToRestructureAfterRemove(traveledNodes) :
this.getNodesToRestructureAfterInsert(traveledNodes);
this.restructure(nodesToBeRestructured);
}
current = current.parent;
}
...isTreeBalanced = function () {
var current = this.root;
if (!current) {
return true;
}
return this._isBalanced(current._left) &&
this._isBalanced(current._right) &&
Math.abs(this._getNodeHeight(current._left) -
this._getNodeHeight(current._right)) <= 1;
}n/a
keepHeightBalance = function (node, afterRemove) {
var current = node;
var traveledNodes = [];
while (current !== null) {
traveledNodes.push(current);
current.height = this.getNodeHeight(current);
if (!this.isNodeBalanced(current)) {
var nodesToBeRestructured = (afterRemove) ?
this.getNodesToRestructureAfterRemove(traveledNodes) :
this.getNodesToRestructureAfterInsert(traveledNodes);
this.restructure(nodesToBeRestructured);
}
current = current.parent;
}
}...
/**
* Inserts a value as a Node of an AVL Tree.
*/
AVLTree.prototype.insert = function (value, current) {
if (this.root === null) {
this.root = new Node(value, null, null, null, 1);
this.keepHeightBalance(this.root);
return;
}
var insertKey;
current = current || this.root;
if (current.value > value) {
insertKey = 'left';
...leftLeft = function (x, y, z) {
//pass z parent to y and move y's right to z's left
if (z.parent !== null) {
var orientation = (z.parent.left === z) ? 'left' : 'right';
z.parent[orientation] = y;
y.parent = z.parent;
} else {
this.root = y;
y.parent = null;
}
z.left = y.right;
if (z.left !== null) {
z.left.parent = z;
}
//fix y right child
y.right = z;
z.parent = y;
// Correct each nodes height - order matters, children first
x.height = this.getNodeHeight(x);
z.height = this.getNodeHeight(z);
y.height = this.getNodeHeight(y);
}...
var y = nodesToRestructure[1];
var z = nodesToRestructure[2];
// Determine Rotation Pattern
if (z.right === y && y.right === x) {
this.rightRight(x, y, z);
} else if (z.left === y && y.left === x) {
this.leftLeft(x, y, z);
} else if (z.right === y && y.left === x) {
this.rightLeft(x, y, z);
} else if (z.left === y && y.right === x) {
this.leftRight(x, y, z);
}
};
...leftRight = function (x, y, z) {
//pass z parent to x
if (z.parent !== null) {
var orientation = (z.parent.left === z) ? 'left' : 'right';
z.parent[orientation] = x;
x.parent = z.parent;
} else {
this.root = x;
x.parent = null;
}
// Adoptions
z.left = x.right;
if (z.left !== null) {
z.left.parent = z;
}
y.right = x.left;
if (y.right !== null) {
y.right.parent = y;
}
// Point to new children (x new parent)
x.right = z;
x.left = y;
x.left.parent = x;
x.right.parent = x;
// Correct each nodes height - order matters, children first
y.height = this.getNodeHeight(y);
z.height = this.getNodeHeight(z);
x.height = this.getNodeHeight(x);
}...
if (z.right === y && y.right === x) {
this.rightRight(x, y, z);
} else if (z.left === y && y.left === x) {
this.leftLeft(x, y, z);
} else if (z.right === y && y.left === x) {
this.rightLeft(x, y, z);
} else if (z.left === y && y.right === x) {
this.leftRight(x, y, z);
}
};
/**
* Right-right rotation pattern.
*/
AVLTree.prototype.rightRight = function (x, y, z) {
...postOrder = function (current, callback) {
if (!current) {
return;
}
this.postOrder(current.left, callback);
this.postOrder(current.right, callback);
if (typeof callback === 'function') {
callback(current);
}
}...
* Post-order traversal from the given node.
*/
AVLTree.prototype.postOrder = function (current, callback) {
if (!current) {
return;
}
this.postOrder(current.left, callback);
this.postOrder(current.right, callback);
if (typeof callback === 'function') {
callback(current);
}
};
/**
...preOrder = function (current, callback) {
if (!current) {
return;
}
if (typeof callback === 'function') {
callback(current);
}
this.preOrder(current.left, callback);
this.preOrder(current.right, callback);
}...
AVLTree.prototype.preOrder = function (current, callback) {
if (!current) {
return;
}
if (typeof callback === 'function') {
callback(current);
}
this.preOrder(current.left, callback);
this.preOrder(current.right, callback);
};
/**
* Finds a node by its value.
*/
AVLTree.prototype.find = function (value) {
...remove = function (value) {
var node = this.find(value);
if (!node) {
return false;
}
if (node.left && node.right) {
var min = this.findMin(node.right);
var temp = node.value;
node.value = min.value;
min.value = temp;
return this.remove(min);
} else if (node.left) {
this.replaceChild(node.parent, node, node.left);
this.keepHeightBalance(node.left, true);
} else if (node.right) {
this.replaceChild(node.parent, node, node.right);
this.keepHeightBalance(node.right, true);
} else {
this.replaceChild(node.parent, node, null);
this.keepHeightBalance(node.parent, true);
}
return true;
}...
}
if (node.left && node.right) {
var min = this.findMin(node.right);
var temp = node.value;
node.value = min.value;
min.value = temp;
return this.remove(min);
} else if (node.left) {
this.replaceChild(node.parent, node, node.left);
this.keepHeightBalance(node.left, true);
} else if (node.right) {
this.replaceChild(node.parent, node, node.right);
this.keepHeightBalance(node.right, true);
} else {
...replaceChild = function (parent, oldChild, newChild) {
if (parent === null) {
this.root = newChild;
if (this.root !== null) {
this.root.parent = null;
}
} else {
if (parent.left === oldChild) {
parent.left = newChild;
} else {
parent.right = newChild;
}
if (newChild) {
newChild.parent = parent;
}
}
}...
if (node.left && node.right) {
var min = this.findMin(node.right);
var temp = node.value;
node.value = min.value;
min.value = temp;
return this.remove(min);
} else if (node.left) {
this.replaceChild(node.parent, node, node.left);
this.keepHeightBalance(node.left, true);
} else if (node.right) {
this.replaceChild(node.parent, node, node.right);
this.keepHeightBalance(node.right, true);
} else {
this.replaceChild(node.parent, node, null);
this.keepHeightBalance(node.parent, true);
...restructure = function (nodesToRestructure) {
var x = nodesToRestructure[0];
var y = nodesToRestructure[1];
var z = nodesToRestructure[2];
// Determine Rotation Pattern
if (z.right === y && y.right === x) {
this.rightRight(x, y, z);
} else if (z.left === y && y.left === x) {
this.leftLeft(x, y, z);
} else if (z.right === y && y.left === x) {
this.rightLeft(x, y, z);
} else if (z.left === y && y.right === x) {
this.leftRight(x, y, z);
}
}...
while (current !== null) {
traveledNodes.push(current);
current.height = this.getNodeHeight(current);
if (!this.isNodeBalanced(current)) {
var nodesToBeRestructured = (afterRemove) ?
this.getNodesToRestructureAfterRemove(traveledNodes) :
this.getNodesToRestructureAfterInsert(traveledNodes);
this.restructure(nodesToBeRestructured);
}
current = current.parent;
}
};
/**
* Identifies and calls the appropriate pattern
...rightLeft = function (x, y, z) {
//pass z parent to x
if (z.parent !== null) {
var orientation = (z.parent.left === z) ? 'left' : 'right';
z.parent[orientation] = x;
x.parent = z.parent;
} else {
this.root = x;
x.parent = null;
}
// Adoptions
z.right = x.left;
if (z.right !== null) {
z.right.parent = z;
}
y.left = x.right;
if (y.left !== null) {
y.left.parent = y;
}
// Point to new children (x new parent)
x.left = z;
x.right = y;
x.left.parent = x;
x.right.parent = x;
// Correct each nodes height - order matters, children first
y.height = this.getNodeHeight(y);
z.height = this.getNodeHeight(z);
x.height = this.getNodeHeight(x);
}...
// Determine Rotation Pattern
if (z.right === y && y.right === x) {
this.rightRight(x, y, z);
} else if (z.left === y && y.left === x) {
this.leftLeft(x, y, z);
} else if (z.right === y && y.left === x) {
this.rightLeft(x, y, z);
} else if (z.left === y && y.right === x) {
this.leftRight(x, y, z);
}
};
/**
* Right-right rotation pattern.
...rightRight = function (x, y, z) {
// pass z parent to y and move y's left to z's right
if (z.parent !== null) {
var orientation = (z.parent.left === z) ? 'left' : 'right';
z.parent[orientation] = y;
y.parent = z.parent;
} else {
this.root = y;
y.parent = null;
}
// z adopts y's left.
z.right = y.left;
if (z.right !== null) {
z.right.parent = z;
}
// y adopts z
y.left = z;
z.parent = y;
// Correct each nodes height - order matters, children first
x.height = this.getNodeHeight(x);
z.height = this.getNodeHeight(z);
y.height = this.getNodeHeight(y);
}...
AVLTree.prototype.restructure = function (nodesToRestructure) {
var x = nodesToRestructure[0];
var y = nodesToRestructure[1];
var z = nodesToRestructure[2];
// Determine Rotation Pattern
if (z.right === y && y.right === x) {
this.rightRight(x, y, z);
} else if (z.left === y && y.left === x) {
this.leftLeft(x, y, z);
} else if (z.right === y && y.left === x) {
this.rightLeft(x, y, z);
} else if (z.left === y && y.right === x) {
this.leftRight(x, y, z);
}
...function BST(compareFn) {
this.root = null;
this._size = 0;
/**
* @var Comparator
*/
this._comparator = new Comparator(compareFn);
/**
* Read-only property for the size of the tree
*/
Object.defineProperty(this, 'size', {
get: function () { return this._size; }.bind(this)
});
}n/a
_find = function (e, root) {
if (!root) {
if (this.root) root = this.root;
else return false;
}
if (root.value === e)
return root;
if (this._comparator.lessThan(e, root.value))
return root.left && this._find(e, root.left);
if (this._comparator.greaterThan(e, root.value))
return root.right && this._find(e, root.right);
}...
this.preOrder(current.right, callback);
};
/**
* Finds a node by its value.
*/
AVLTree.prototype.find = function (value) {
return this._find(value, this.root);
};
/**
* Finds a node by its value in the given sub-tree.
*/
AVLTree.prototype._find = function (value, current) {
if (!current) {
..._findMin = function (root) {
var minNode = root;
while (minNode.left) {
minNode = minNode.left;
}
return minNode;
}...
};
if (!node) {
return current;
}
if (current.value > node.value) {
current = node;
}
return this._findMin(node.left, current);
};
/**
* Finds the node with maximum value in the given
* sub-tree.
*/
AVLTree.prototype._findMax = function (node, current) {
..._replaceNodeInParent = function (currNode, newNode) {
var parent = currNode.parent;
if (parent) {
parent[currNode === parent.left ? 'left' : 'right'] = newNode;
if (newNode)
newNode.parent = parent;
} else {
this.root = newNode;
}
}...
node.value = successor.value;
} else {
/**
* If the node is a leaf, just make the parent point to null,
* and if it has one child, make the parent point to this child
* instead
*/
this._replaceNodeInParent(node, node.left || node.right);
this._size--;
}
};
module.exports = BST;
...contains = function (e) {
return !!this._find(e);
}...
// Normalize vertex labels as strings
var _ = function (v) {
return '' + v;
};
Graph.prototype.addVertex = function (v) {
v = _(v);
if (this.vertices.contains(v)) {
throw new Error('Vertex "' + v + '" has already been added');
}
this.vertices.add(v);
this.adjList[v] = Object.create(null);
};
Graph.prototype.addEdge = function (a, b, w) {
...insert = function (value, parent) {
// Set the root as the initial insertion point
// if it has not been passed
if (!parent) {
if (!this.root) {
this.root = new Node(value);
this._size++;
return;
}
parent = this.root;
}
var child = this._comparator.lessThan(value, parent.value) ? 'left' : 'right';
if (parent[child]) {
this.insert(value, parent[child]);
} else {
parent[child] = new Node(value, parent);
this._size++;
}
}...
insertKey = 'right';
}
if (!current[insertKey]) {
current[insertKey] = new Node(value, null, null, current);
this.keepHeightBalance(current[insertKey], false);
} else {
this.insert(value, current[insertKey]);
}
};
/**
* In-order traversal from the given node.
*/
AVLTree.prototype.inOrder = function (current, callback) {
...remove = function (e) {
var node = this._find(e);
if (!node) {
throw new Error('Item not found in the tree');
}
if (node.left && node.right) {
/**
* If the node to be removed has both left and right children,
* replace the node's value by the minimum value of the right
* sub-tree, and remove the leave containing the value
*/
var successor = this._findMin(node.right);
this.remove(successor.value);
node.value = successor.value;
} else {
/**
* If the node is a leaf, just make the parent point to null,
* and if it has one child, make the parent point to this child
* instead
*/
this._replaceNodeInParent(node, node.left || node.right);
this._size--;
}
}...
}
if (node.left && node.right) {
var min = this.findMin(node.right);
var temp = node.value;
node.value = min.value;
min.value = temp;
return this.remove(min);
} else if (node.left) {
this.replaceChild(node.parent, node, node.left);
this.keepHeightBalance(node.left, true);
} else if (node.right) {
this.replaceChild(node.parent, node, node.right);
this.keepHeightBalance(node.right, true);
} else {
...function DisjointSetForest() {
this._parents = {};
this._ranks = {};
this._sizes = {};
}n/a
_introduce = function (element) {
if (!(element in this._parents)) {
this._parents[element] = element;
this._ranks[element] = 0;
this._sizes[element] = 1;
}
}...
* Check if the elements belong to the same subset.
* Complexity: O(A^-1) (inverse Ackermann function) amortized.
*
* @param {...*} element
* @return {boolean}
*/
DisjointSetForest.prototype.sameSubset = function (element) {
this._introduce(element);
var root = this.root(element);
return [].slice.call(arguments, 1).every(function (element) {
this._introduce(element);
return this.root(element) === root;
}.bind(this));
};
...function merge(element1, element2) {
if (arguments.length > 2) {
merge.apply(this, [].slice.call(arguments, 1));
}
this._introduce(element1);
this._introduce(element2);
var root1 = this.root(element1);
var root2 = this.root(element2);
if (this._ranks[root1] < this._ranks[root2]) {
this._parents[root1] = root2;
this._sizes[root2] += this._sizes[root1];
}
else if (root1 !== root2) {
this._parents[root2] = root1;
this._sizes[root1] += this._sizes[root2];
if (this._ranks[root1] === this._ranks[root2]) {
this._ranks[root1] += 1;
}
}
return this;
}...
});
edges.sort(function (a, b) {
return a.weight - b.weight;
}).forEach(function (edge) {
if (!connectedComponents.sameSubset(edge.ends[0], edge.ends[1])) {
mst.addEdge(edge.ends[0], edge.ends[1], edge.weight);
connectedComponents.merge(edge.ends[0], edge.ends[1]);
}
});
return mst;
};
...root = function (element) {
this._introduce(element);
if (this._parents[element] !== element) {
this._parents[element] = this.root(this._parents[element]);
}
return this._parents[element];
}...
* Complexity: O(A^-1) (inverse Ackermann function) amortized.
*
* @param {...*} element
* @return {boolean}
*/
DisjointSetForest.prototype.sameSubset = function (element) {
this._introduce(element);
var root = this.root(element);
return [].slice.call(arguments, 1).every(function (element) {
this._introduce(element);
return this.root(element) === root;
}.bind(this));
};
...sameSubset = function (element) {
this._introduce(element);
var root = this.root(element);
return [].slice.call(arguments, 1).every(function (element) {
this._introduce(element);
return this.root(element) === root;
}.bind(this));
}...
}
});
});
edges.sort(function (a, b) {
return a.weight - b.weight;
}).forEach(function (edge) {
if (!connectedComponents.sameSubset(edge.ends[0], edge.ends[1])) {
mst.addEdge(edge.ends[0], edge.ends[1], edge.weight);
connectedComponents.merge(edge.ends[0], edge.ends[1]);
}
});
return mst;
};
...size = function (element) {
this._introduce(element);
return this._sizes[this.root(element)];
}...
assert(!forest.sameSubset(1, 5));
});
it('should maintain subset sizes', function () {
var forest = new DisjointSetForest();
var assertSizesCorrect = function (elements, size) {
elements.forEach(function (element) {
assert.equal(forest.size(element), size);
});
};
assertSizesCorrect([0, 1, 2, 3, 4], 1);
forest.merge(0, 1);
assertSizesCorrect([0, 1], 2);
forest.merge(0, 2);
assertSizesCorrect([0, 1, 2], 3);
...function FenwickTree(length) {
this._elements = new Array(length + 1);
for (var i = 0; i < this._elements.length ; i++)
this._elements[i] = 0;
}n/a
adjust = function (index, value) {
/*
This function goes up the tree adding the value to all parent nodes.
In the array, to know where a index is in the tree, just look at where is
the rightmost bit. 1 is a leaf, because the rightmost bit is at position 0.
2 (10) is 1 level above the leafs. 4 (100) is 2 levels above the leafs.
Going up the tree means pushing the rightmost bit far to the left. We do
this by adding only the bit itself to the index. Eventually we skip
some levels that aren't represented in the array. E.g. starting at 3 (11),
it's imediate parent is 11b + 1b = 100b. We started at a leaf and skipped
the level-1 node, because it wasn't represented in the array
(a right child).
Note: (index&-index) finds the rightmost bit in index.
*/
for (; index < this._elements.length ; index += (index&-index))
this._elements[index] += value;
}...
var FenwickTree = require('../..').DataStructures.FenwickTree,
assert = require('assert');
describe('FenwickTree', function () {
it('should allow prefix queries', function () {
var tree = new FenwickTree(10);
tree.adjust(5, 42);
tree.adjust(7, 43);
tree.adjust(9, 44);
assert.equal(tree.prefixSum(0), 0);
assert.equal(tree.prefixSum(1), 0);
assert.equal(tree.prefixSum(2), 0);
...prefixSum = function (index) {
/*
This function goes up the tree adding the required nodes to sum the prefix.
The key here is to sum every node that isn't in the same subtree as an
already seen node. In practice we proceed always getting a node's uncle
(the sibling of the node's parent). So, if we start at the index 7, we must
go to 6 (7's uncle), then to 4 (6's uncle), then we stop, because 4 has
no uncle.
Binary-wise, this is the same as erasing the rightmost bit of the index.
E.g. 7 (111) -> 6 (110) -> 4 (100).
Note: (index&-index) finds the rightmost bit in index.
*/
var sum = 0;
for (; index > 0 ; index -= (index&-index))
sum += this._elements[index];
return sum;
}...
return sum;
};
/**
* Returns the sum of all values between two indexes in O(log n)
*/
FenwickTree.prototype.rangeSum = function (fromIndex, toIndex) {
return this.prefixSum(toIndex) - this.prefixSum(fromIndex - 1);
};
module.exports = FenwickTree;
...rangeSum = function (fromIndex, toIndex) {
return this.prefixSum(toIndex) - this.prefixSum(fromIndex - 1);
}...
it('should allow range queries', function () {
var tree = new FenwickTree(10);
tree.adjust(5, 42);
tree.adjust(7, 43);
tree.adjust(9, 44);
assert.equal(tree.rangeSum(6, 10), 43 + 44);
assert.equal(tree.rangeSum(5, 7), 42 + 43);
});
});
...function Graph(directed) {
this.directed = (directed === undefined ? true : !!directed);
this.adjList = Object.create(null);
this.vertices = new HashSet();
}n/a
addEdge = function (a, b, w) {
a = _(a);
b = _(b);
// If no weight is assigned to the edge, 1 is the default
w = (w === undefined ? 1 : w);
if (!this.adjList[a]) this.addVertex(a);
if (!this.adjList[b]) this.addVertex(b);
// If there's already another edge with the same origin and destination
// sum with the current one
this.adjList[a][b] = (this.adjList[a][b] || 0) + w;
// If the graph is not directed add the edge in both directions
if (!this.directed) {
this.adjList[b][a] = (this.adjList[b][a] || 0) + w;
}
}...
graph.vertices.forEach(seen.addVertex.bind(seen));
depthFirstSearch(graph, endpoints.start, {
allowTraversal: function (vertex, neighbor) {
return !seen.edge(vertex, neighbor);
},
beforeTraversal: function (vertex, neighbor) {
seen.addEdge(vertex, neighbor);
},
afterTraversal: function (vertex) {
route.push(vertex);
}
});
graph.vertices.forEach(function (vertex) {
...addVertex = function (v) {
v = _(v);
if (this.vertices.contains(v)) {
throw new Error('Vertex "' + v + '" has already been added');
}
this.vertices.add(v);
this.adjList[v] = Object.create(null);
}...
Graph.prototype.addEdge = function (a, b, w) {
a = _(a);
b = _(b);
// If no weight is assigned to the edge, 1 is the default
w = (w === undefined ? 1 : w);
if (!this.adjList[a]) this.addVertex(a);
if (!this.adjList[b]) this.addVertex(b);
// If there's already another edge with the same origin and destination
// sum with the current one
this.adjList[a][b] = (this.adjList[a][b] || 0) + w;
// If the graph is not directed add the edge in both directions
...edge = function (a, b) {
return this.adjList[_(a)][_(b)];
}...
// Add all the edges from the graph to the 'edges' array
graph.vertices.forEach(function (s) {
graph.neighbors(s).forEach(function (t) {
edges.push({
source: s,
target: t,
weight: graph.edge(s, t)
});
});
minDistance[s] = Infinity;
++adjacencyListSize;
});
...neighbors = function (v) {
return Object.keys(this.adjList[_(v)]);
}...
var minDistance = {};
var previousVertex = {};
var edges = [];
var adjacencyListSize = 0;
// Add all the edges from the graph to the 'edges' array
graph.vertices.forEach(function (s) {
graph.neighbors(s).forEach(function (t) {
edges.push({
source: s,
target: t,
weight: graph.edge(s, t)
});
});
...function HashTable(initialCapacity) {
this._table = new Array(initialCapacity || 64);
this._items = 0;
Object.defineProperty(this, 'capacity', {
get: function () {
return this._table.length;
}
});
Object.defineProperty(this, 'size', {
get: function () {
return this._items;
}
});
}n/a
_findInList = function (list, key) {
var node = list && list.head;
while (node) {
if (node.value.k === key) return node;
node = node.next;
}
}...
}
return hash;
};
HashTable.prototype.get = function (key) {
var i = this._position(key);
var node;
if ((node = this._findInList(this._table[i], key))) {
return node.value.v;
}
};
HashTable.prototype.put = function (key, value) {
var i = this._position(key);
if (!this._table[i]) {
..._increaseCapacity = function () {
var oldTable = this._table;
this._table = new Array(2 * this.capacity);
this._items = 0;
for (var i = 0; i < oldTable.length; i++) {
var node = oldTable[i] && oldTable[i].head;
while (node) {
this.put(node.value.k, node.value.v);
node = node.next;
}
}
}...
// if the key already exists in the list, replace
// by the current item
node.value = item;
} else {
this._table[i].add(item);
this._items++;
if (this._items === this.capacity) this._increaseCapacity();
}
};
HashTable.prototype.del = function (key) {
var i = this._position(key);
var node;
..._position = function (key) {
return Math.abs(this.hash(key)) % this.capacity;
}...
hash = ((hash << 5) - hash) + s.charCodeAt(i);
hash &= hash; // Keep it a 32bit int
}
return hash;
};
HashTable.prototype.get = function (key) {
var i = this._position(key);
var node;
if ((node = this._findInList(this._table[i], key))) {
return node.value.v;
}
};
HashTable.prototype.put = function (key, value) {
...del = function (key) {
var i = this._position(key);
var node;
if ((node = this._findInList(this._table[i], key))) {
this._table[i].delNode(node);
this._items--;
}
}...
* Pops the element in the beginning of the queue
*/
Queue.prototype.pop = function () {
if (this.isEmpty()) {
throw new Error('Empty queue');
}
var e = this._elements.get(0);
this._elements.del(0);
return e;
};
Queue.prototype.peek = function () {
if (this.isEmpty()) {
throw new Error('Empty queue');
}
...forEach = function (fn) {
var applyFunction = function (linkedList) {
linkedList.forEach(function (elem) {
fn(elem.k, elem.v);
});
};
for (var i = 0; i < this._table.length; i++) {
if (this._table[i]) {
applyFunction(this._table[i]);
}
}
}...
node = node.next;
}
}
};
HashTable.prototype.forEach = function (fn) {
var applyFunction = function (linkedList) {
linkedList.forEach(function (elem) {
fn(elem.k, elem.v);
});
};
for (var i = 0; i < this._table.length; i++) {
if (this._table[i]) {
applyFunction(this._table[i]);
...get = function (key) {
var i = this._position(key);
var node;
if ((node = this._findInList(this._table[i], key))) {
return node.value.v;
}
}...
/**
* Pops the element in the beginning of the queue
*/
Queue.prototype.pop = function () {
if (this.isEmpty()) {
throw new Error('Empty queue');
}
var e = this._elements.get(0);
this._elements.del(0);
return e;
};
Queue.prototype.peek = function () {
if (this.isEmpty()) {
throw new Error('Empty queue');
...hash = function (s) {
if (typeof s !== 'string') s = JSON.stringify(s);
var hash = 0;
for (var i = 0; i < s.length; i++) {
hash = ((hash << 5) - hash) + s.charCodeAt(i);
hash &= hash; // Keep it a 32bit int
}
return hash;
}...
if ((node = this._findInList(this._table[i], key))) {
this._table[i].delNode(node);
this._items--;
}
};
HashTable.prototype._position = function (key) {
return Math.abs(this.hash(key)) % this.capacity;
};
HashTable.prototype._findInList = function (list, key) {
var node = list && list.head;
while (node) {
if (node.value.k === key) return node;
node = node.next;
...put = function (key, value) {
var i = this._position(key);
if (!this._table[i]) {
// Hashing with chaining
this._table[i] = new LinkedList();
}
var item = {k: key, v: value};
var node = this._findInList(this._table[i], key);
if (node) {
// if the key already exists in the list, replace
// by the current item
node.value = item;
} else {
this._table[i].add(item);
this._items++;
if (this._items === this.capacity) this._increaseCapacity();
}
}...
var oldTable = this._table;
this._table = new Array(2 * this.capacity);
this._items = 0;
for (var i = 0; i < oldTable.length; i++) {
var node = oldTable[i] && oldTable[i].head;
while (node) {
this.put(node.value.k, node.value.v);
node = node.next;
}
}
};
HashTable.prototype.forEach = function (fn) {
var applyFunction = function (linkedList) {
...function MaxHeap(compareFn) {
MinHeap.call(this, compareFn);
this._comparator.reverse();
}...
// Make sure nothing was really removed
assert.equal(h.n, 6);
});
});
describe('Max Heap', function () {
it('should always return the greatest element', function () {
var h = new heap.MaxHeap();
assert(h.isEmpty());
h.insert(10);
h.insert(2091);
h.insert(4);
h.insert(1);
h.insert(5);
h.insert(500);
...function MinHeap(compareFn) {
this._elements = [null];
this._comparator = new Comparator(compareFn);
Object.defineProperty(this, 'n', {
get: function () {
return this._elements.length - 1;
}.bind(this)
});
}...
'use strict';
var heap = require('../..').DataStructures.Heap,
assert = require('assert');
describe('Min Heap', function () {
it('should always return the lowest element', function () {
var h = new heap.MinHeap();
assert(h.isEmpty());
h.insert(10);
h.insert(2091);
h.insert(4);
h.insert(1);
h.insert(5);
h.insert(500);
..._siftDown = function (i) {
var c;
for (i = i || 1; (c = i << 1) <= this.n; i = c) {
// checks which is the smaller child to compare with
if (c + 1 <= this.n && this._comparator.lessThan(
this._elements[c + 1], this._elements[c]))
// use the right child if it's lower than the left one
c++;
if (this._comparator.lessThan(this._elements[i],
this._elements[c]))
break;
this._swap(i, c);
}
}...
var element = this._elements[1];
// Get the one from the bottom in insert it on top
// If this isn't already the last element
var last = this._elements.pop();
if (this.n) {
this._elements[1] = last;
this._siftDown();
}
return element;
};
/**
* Sift up the last element
..._siftUp = function () {
var i, parent;
for (i = this.n;
i > 1 && (parent = i >> 1) && this._comparator.greaterThan(
this._elements[parent], this._elements[i]);
i = parent) {
this._swap(parent, i);
}
}...
MinHeap.prototype.isEmpty = function () {
return this.n === 0;
};
MinHeap.prototype.insert = function (e) {
this._elements.push(e);
this._siftUp();
};
MinHeap.prototype.extract = function () {
var element = this._elements[1];
// Get the one from the bottom in insert it on top
// If this isn't already the last element
..._swap = function (a, b) {
var tmp = this._elements[a];
this._elements[a] = this._elements[b];
this._elements[b] = tmp;
}...
MinHeap.prototype._siftUp = function () {
var i, parent;
for (i = this.n;
i > 1 && (parent = i >> 1) && this._comparator.greaterThan(
this._elements[parent], this._elements[i]);
i = parent) {
this._swap(parent, i);
}
};
/**
* Sifts down the first element
* O(lg n)
*/
...extract = function () {
var element = this._elements[1];
// Get the one from the bottom in insert it on top
// If this isn't already the last element
var last = this._elements.pop();
if (this.n) {
this._elements[1] = last;
this._siftDown();
}
return element;
}...
var i;
for (i = 0; i < this._elements.length; i++) {
elementsCopy.push(this._elements[i]);
}
for (i = this.n; i > 0; i--) {
fn(this.extract());
}
this._elements = elementsCopy;
};
/**
* Max Heap, keeps the highest element always on top
...forEach = function (fn) {
// A copy is necessary in order to perform extract(),
// get the items in sorted order and then restore the original
// this._elements array
var elementsCopy = [];
var i;
for (i = 0; i < this._elements.length; i++) {
elementsCopy.push(this._elements[i]);
}
for (i = this.n; i > 0; i--) {
fn(this.extract());
}
this._elements = elementsCopy;
}...
node = node.next;
}
}
};
HashTable.prototype.forEach = function (fn) {
var applyFunction = function (linkedList) {
linkedList.forEach(function (elem) {
fn(elem.k, elem.v);
});
};
for (var i = 0; i < this._table.length; i++) {
if (this._table[i]) {
applyFunction(this._table[i]);
...heapify = function (a) {
if (a) {
this._elements = a;
this._elements.unshift(null);
}
for (var i = this.n >> 1; i > 0; i--) {
this._siftDown(i);
}
}...
PriorityQueue.prototype.priority = function (item) {
return this._priority[item];
};
PriorityQueue.prototype.changePriority = function (item, priority) {
this._priority[item] = priority;
this.heapify();
};
module.exports = PriorityQueue;
...insert = function (e) {
this._elements.push(e);
this._siftUp();
}...
insertKey = 'right';
}
if (!current[insertKey]) {
current[insertKey] = new Node(value, null, null, current);
this.keepHeightBalance(current[insertKey], false);
} else {
this.insert(value, current[insertKey]);
}
};
/**
* In-order traversal from the given node.
*/
AVLTree.prototype.inOrder = function (current, callback) {
...isEmpty = function () {
return this.n === 0;
}...
get: function () {
return this._elements.length;
}.bind(this)
});
}
Queue.prototype.isEmpty = function () {
return this._elements.isEmpty();
};
/**
* Adds element to the end of the queue
*/
Queue.prototype.push = function (e) {
this._elements.add(e);
...function LinkedList() {
this._length = 0;
this.head = null;
this.tail = null;
// Read-only length property
Object.defineProperty(this, 'length', {
get: function () {
return this._length;
}.bind(this)
});
}n/a
add = function (n, index) {
if (index > this.length || index < 0) {
throw new Error('Index out of bounds');
}
var node = new Node(n);
if (index !== undefined && index < this.length) {
var prevNode,
nextNode;
if (index === 0) {
// Insert in the beginning
nextNode = this.head;
this.head = node;
} else {
nextNode = this.getNode(index);
prevNode = nextNode.prev;
prevNode.next = node;
node.prev = prevNode;
}
nextNode.prev = node;
node.next = nextNode;
} else {
// Insert at the end
if (!this.head) this.head = node;
if (this.tail) {
this.tail.next = node;
node.prev = this.tail;
}
this.tail = node;
}
this._length++;
}...
};
Graph.prototype.addVertex = function (v) {
v = _(v);
if (this.vertices.contains(v)) {
throw new Error('Vertex "' + v + '" has already been added');
}
this.vertices.add(v);
this.adjList[v] = Object.create(null);
};
Graph.prototype.addEdge = function (a, b, w) {
a = _(a);
b = _(b);
// If no weight is assigned to the edge, 1 is the default
...del = function (index) {
if (index >= this.length || index < 0) {
throw new Error('Index out of bounds');
}
this.delNode(this.getNode(index));
}...
* Pops the element in the beginning of the queue
*/
Queue.prototype.pop = function () {
if (this.isEmpty()) {
throw new Error('Empty queue');
}
var e = this._elements.get(0);
this._elements.del(0);
return e;
};
Queue.prototype.peek = function () {
if (this.isEmpty()) {
throw new Error('Empty queue');
}
...delNode = function (node) {
if (node === this.tail) {
// node is the last element
this.tail = node.prev;
} else {
node.next.prev = node.prev;
}
if (node === this.head) {
// node is the first element
this.head = node.next;
} else {
node.prev.next = node.next;
}
this._length--;
}...
};
HashTable.prototype.del = function (key) {
var i = this._position(key);
var node;
if ((node = this._findInList(this._table[i], key))) {
this._table[i].delNode(node);
this._items--;
}
};
HashTable.prototype._position = function (key) {
return Math.abs(this.hash(key)) % this.capacity;
};
...forEach = function (fn) {
var node = this.head;
while (node) {
fn(node.value);
node = node.next;
}
}...
node = node.next;
}
}
};
HashTable.prototype.forEach = function (fn) {
var applyFunction = function (linkedList) {
linkedList.forEach(function (elem) {
fn(elem.k, elem.v);
});
};
for (var i = 0; i < this._table.length; i++) {
if (this._table[i]) {
applyFunction(this._table[i]);
...get = function (index) {
return this.getNode(index).value;
}...
/**
* Pops the element in the beginning of the queue
*/
Queue.prototype.pop = function () {
if (this.isEmpty()) {
throw new Error('Empty queue');
}
var e = this._elements.get(0);
this._elements.del(0);
return e;
};
Queue.prototype.peek = function () {
if (this.isEmpty()) {
throw new Error('Empty queue');
...getNode = function (index) {
if (index >= this.length || index < 0) {
throw new Error('Index out of bounds');
}
var node = this.head;
for (var i = 1; i <= index; i++) {
node = node.next;
}
return node;
}...
nextNode;
if (index === 0) {
// Insert in the beginning
nextNode = this.head;
this.head = node;
} else {
nextNode = this.getNode(index);
prevNode = nextNode.prev;
prevNode.next = node;
node.prev = prevNode;
}
nextNode.prev = node;
node.next = nextNode;
} else {
...isEmpty = function () {
return this.length === 0;
}...
get: function () {
return this._elements.length;
}.bind(this)
});
}
Queue.prototype.isEmpty = function () {
return this._elements.isEmpty();
};
/**
* Adds element to the end of the queue
*/
Queue.prototype.push = function (e) {
this._elements.add(e);
...function PriorityQueue(initialItems) {
var self = this;
MinHeap.call(this, function (a, b) {
return self.priority(a) < self.priority(b) ? -1 : 1;
});
this._priority = {};
initialItems = initialItems || {};
Object.keys(initialItems).forEach(function (item) {
self.insert(item, initialItems[item]);
});
}n/a
changePriority = function (item, priority) {
this._priority[item] = priority;
this.heapify();
}...
});
}
PriorityQueue.prototype = new MinHeap();
PriorityQueue.prototype.insert = function (item, priority) {
if (this._priority[item] !== undefined) {
return this.changePriority(item, priority);
}
this._priority[item] = priority;
MinHeap.prototype.insert.call(this, item);
};
PriorityQueue.prototype.extract = function (withPriority) {
var min = MinHeap.prototype.extract.call(this);
...extract = function (withPriority) {
var min = MinHeap.prototype.extract.call(this);
return withPriority ?
min && {item: min, priority: this._priority[min]} :
min;
}...
var i;
for (i = 0; i < this._elements.length; i++) {
elementsCopy.push(this._elements[i]);
}
for (i = this.n; i > 0; i--) {
fn(this.extract());
}
this._elements = elementsCopy;
};
/**
* Max Heap, keeps the highest element always on top
...insert = function (item, priority) {
if (this._priority[item] !== undefined) {
return this.changePriority(item, priority);
}
this._priority[item] = priority;
MinHeap.prototype.insert.call(this, item);
}...
insertKey = 'right';
}
if (!current[insertKey]) {
current[insertKey] = new Node(value, null, null, current);
this.keepHeightBalance(current[insertKey], false);
} else {
this.insert(value, current[insertKey]);
}
};
/**
* In-order traversal from the given node.
*/
AVLTree.prototype.inOrder = function (current, callback) {
...priority = function (item) {
return this._priority[item];
}...
* the heap operations are performed based on the priority of the element
* and not on the element itself
*/
function PriorityQueue(initialItems) {
var self = this;
MinHeap.call(this, function (a, b) {
return self.priority(a) < self.priority(b) ? -1 : 1;
});
this._priority = {};
initialItems = initialItems || {};
Object.keys(initialItems).forEach(function (item) {
self.insert(item, initialItems[item]);
...function Queue() {
this._elements = new LinkedList();
Object.defineProperty(this, 'length', {
get: function () {
return this._elements.length;
}.bind(this)
});
}n/a
forEach = function (fn) {
this._elements.forEach(fn);
}...
node = node.next;
}
}
};
HashTable.prototype.forEach = function (fn) {
var applyFunction = function (linkedList) {
linkedList.forEach(function (elem) {
fn(elem.k, elem.v);
});
};
for (var i = 0; i < this._table.length; i++) {
if (this._table[i]) {
applyFunction(this._table[i]);
...isEmpty = function () {
return this._elements.isEmpty();
}...
get: function () {
return this._elements.length;
}.bind(this)
});
}
Queue.prototype.isEmpty = function () {
return this._elements.isEmpty();
};
/**
* Adds element to the end of the queue
*/
Queue.prototype.push = function (e) {
this._elements.add(e);
...peek = function () {
if (this.isEmpty()) {
throw new Error('Empty queue');
}
return this._elements.get(0);
}...
assert(q.isEmpty());
assert.throws(function () { q.pop(); }, Error);
});
it('should allow me to peek at the first element in' +
' line without popping it', function () {
var q = new Queue();
assert.throws(function () { q.peek(); }, Error); //Empty list
q.push(1);
q.push(2);
q.push(3);
assert.equal(q.peek(), 1);
assert.equal(q.peek(), 1);
q.pop();
assert.equal(q.peek(), 2);
...pop = function () {
if (this.isEmpty()) {
throw new Error('Empty queue');
}
var e = this._elements.get(0);
this._elements.del(0);
return e;
}...
};
MinHeap.prototype.extract = function () {
var element = this._elements[1];
// Get the one from the bottom in insert it on top
// If this isn't already the last element
var last = this._elements.pop();
if (this.n) {
this._elements[1] = last;
this._siftDown();
}
return element;
};
...push = function (e) {
this._elements.add(e);
}...
* Keep the height balance property by walking to
* root and checking for invalid heights.
*/
AVLTree.prototype.keepHeightBalance = function (node, afterRemove) {
var current = node;
var traveledNodes = [];
while (current !== null) {
traveledNodes.push(current);
current.height = this.getNodeHeight(current);
if (!this.isNodeBalanced(current)) {
var nodesToBeRestructured = (afterRemove) ?
this.getNodesToRestructureAfterRemove(traveledNodes) :
this.getNodesToRestructureAfterInsert(traveledNodes);
this.restructure(nodesToBeRestructured);
}
...Set = function () {
this._elements = new HashTable(arguments.length);
this.add.apply(this, arguments);
Object.defineProperty(this, 'size', {
get: function () {
return this._elements.size;
}
});
}n/a
add = function () {
for (var i = 0; i < arguments.length; i++) {
this._elements.put(arguments[i], true);
}
return this;
}...
};
Graph.prototype.addVertex = function (v) {
v = _(v);
if (this.vertices.contains(v)) {
throw new Error('Vertex "' + v + '" has already been added');
}
this.vertices.add(v);
this.adjList[v] = Object.create(null);
};
Graph.prototype.addEdge = function (a, b, w) {
a = _(a);
b = _(b);
// If no weight is assigned to the edge, 1 is the default
...contains = function (e) {
return this._elements.get(e) !== undefined;
}...
// Normalize vertex labels as strings
var _ = function (v) {
return '' + v;
};
Graph.prototype.addVertex = function (v) {
v = _(v);
if (this.vertices.contains(v)) {
throw new Error('Vertex "' + v + '" has already been added');
}
this.vertices.add(v);
this.adjList[v] = Object.create(null);
};
Graph.prototype.addEdge = function (a, b, w) {
...forEach = function (fn) {
this._elements.forEach(fn);
}...
node = node.next;
}
}
};
HashTable.prototype.forEach = function (fn) {
var applyFunction = function (linkedList) {
linkedList.forEach(function (elem) {
fn(elem.k, elem.v);
});
};
for (var i = 0; i < this._table.length; i++) {
if (this._table[i]) {
applyFunction(this._table[i]);
...remove = function () {
for (var i = 0; i < arguments.length; i++) {
this._elements.del(arguments[i]);
}
return this;
}...
}
if (node.left && node.right) {
var min = this.findMin(node.right);
var temp = node.value;
node.value = min.value;
min.value = temp;
return this.remove(min);
} else if (node.left) {
this.replaceChild(node.parent, node, node.left);
this.keepHeightBalance(node.left, true);
} else if (node.right) {
this.replaceChild(node.parent, node, node.right);
this.keepHeightBalance(node.right, true);
} else {
...function Stack() {
Queue.call(this);
}n/a
push = function (e) {
this._elements.add(e, 0);
}...
* Keep the height balance property by walking to
* root and checking for invalid heights.
*/
AVLTree.prototype.keepHeightBalance = function (node, afterRemove) {
var current = node;
var traveledNodes = [];
while (current !== null) {
traveledNodes.push(current);
current.height = this.getNodeHeight(current);
if (!this.isNodeBalanced(current)) {
var nodesToBeRestructured = (afterRemove) ?
this.getNodesToRestructureAfterRemove(traveledNodes) :
this.getNodesToRestructureAfterInsert(traveledNodes);
this.restructure(nodesToBeRestructured);
}
...function Treap() {
this.root = null;
}n/a
_find = function (node, value) {
if (node === null) {
// Empty tree
return false;
}
if (node.value === value) {
// Found!
return true;
}
// Search within childnodes
var side = ~~(value > node.value);
return this._find(node.children[side], value);
}...
this.preOrder(current.right, callback);
};
/**
* Finds a node by its value.
*/
AVLTree.prototype.find = function (value) {
return this._find(value, this.root);
};
/**
* Finds a node by its value in the given sub-tree.
*/
AVLTree.prototype._find = function (value, current) {
if (!current) {
..._insert = function (node, value) {
if (node === null) {
return new Node(value, null, null);
}
// Passing to childnodes and update
var side = ~~(value > node.value);
node.children[side] = this._insert(node.children[side], value);
// Keep it balance
if (node.children[side].key < node.key) {
return node.rotate(side);
} else {
return node.resize();
}
}...
Treap.prototype._insert = function (node, value) {
if (node === null) {
return new Node(value, null, null);
}
// Passing to childnodes and update
var side = ~~(value > node.value);
node.children[side] = this._insert(node.children[side], value);
// Keep it balance
if (node.children[side].key < node.key) {
return node.rotate(side);
} else {
return node.resize();
}
..._maximum = function (node) {
if (node === null) {
// Empty tree, returns -Infinity
return -Infinity;
}
return Math.max(node.value, this._maximum(node.children[1]));
}...
Treap.prototype._maximum = function (node) {
if (node === null) {
// Empty tree, returns -Infinity
return -Infinity;
}
return Math.max(node.value, this._maximum(node.children[1]));
};
Treap.prototype._remove = function (node, value) {
if (node === null) {
// Empty node, value not found
return null;
}
..._minimum = function (node) {
if (node === null) {
// Empty tree, returns Infinity
return Infinity;
}
return Math.min(node.value, this._minimum(node.children[0]));
}...
Treap.prototype._minimum = function (node) {
if (node === null) {
// Empty tree, returns Infinity
return Infinity;
}
return Math.min(node.value, this._minimum(node.children[0]));
};
Treap.prototype._maximum = function (node) {
if (node === null) {
// Empty tree, returns -Infinity
return -Infinity;
}
..._remove = function (node, value) {
if (node === null) {
// Empty node, value not found
return null;
}
var side;
if (node.value === value) {
if (node.children[0] === null && node.children[1] === null) {
// It's a leaf, set to null
return null;
}
// Rotate to a subtree and remove it
side = (node.children[0] === null ? 1 : 0);
node = node.rotate(side);
node.children[1 - side] = this._remove(node.children[1 - side], value);
return node.resize();
} else {
side = ~~(value > node.value);
node.children[side] = this._remove(node.children[side], value);
return node.resize();
}
}...
// It's a leaf, set to null
return null;
}
// Rotate to a subtree and remove it
side = (node.children[0] === null ? 1 : 0);
node = node.rotate(side);
node.children[1 - side] = this._remove(node.children[1 - side], value);
return node.resize();
} else {
side = ~~(value > node.value);
node.children[side] = this._remove(node.children[side], value);
return node.resize();
}
};
...find = function (value) {
return this._find(this.root, value);
}...
}
};
/**
* Removes a node by its value.
*/
AVLTree.prototype.remove = function (value) {
var node = this.find(value);
if (!node) {
return false;
}
if (node.left && node.right) {
var min = this.findMin(node.right);
var temp = node.value;
...height = function () {
return this.root ? this.root.height : 0;
}...
it('should keep balance', function () {
// Insert 1023 elements randomly
for (var i = 0; i < 1023; ++i) {
treap.insert(Math.random());
}
assert.equal(treap.size(), 1023);
// The averange height should be 23 (with an error of 5)
assert(Math.abs(treap.height() - 23) < 5);
});
it('should rotate correctly', function () {
// Force clear the tree
treap.root = null;
treap.insert(1);
// 1
...insert = function (value) {
this.root = this._insert(this.root, value);
}...
insertKey = 'right';
}
if (!current[insertKey]) {
current[insertKey] = new Node(value, null, null, current);
this.keepHeightBalance(current[insertKey], false);
} else {
this.insert(value, current[insertKey]);
}
};
/**
* In-order traversal from the given node.
*/
AVLTree.prototype.inOrder = function (current, callback) {
...maximum = function () {
return this._maximum(this.root);
}...
treap.remove(-100);
// [2, 3, 10, 100]
assert.equal(treap.minimum(), 2);
});
it('should get maximum element', function () {
// [2, 3, 10, 100]
assert.equal(treap.maximum(), 100);
treap.remove(100);
// [2, 3, 10]
assert.equal(treap.maximum(), 10);
treap.remove(10);
// [2, 3]
assert.equal(treap.maximum(), 3);
treap.remove(3);
...minimum = function () {
return this._minimum(this.root);
}...
assert.equal(treap.find(-100), false);
assert.equal(treap.find(-1), false);
assert.equal(treap.find(101), false);
});
it('should get minimum element', function () {
// [1, 2, 3, 10, 100]
assert.equal(treap.minimum(), 1);
treap.remove(1);
// [2, 3, 10, 100]
assert.equal(treap.minimum(), 2);
treap.insert(-100);
// [-100, 2, 3, 10, 100]
assert.equal(treap.minimum(), -100);
treap.remove(-100);
...remove = function (value) {
this.root = this._remove(this.root, value);
}...
}
if (node.left && node.right) {
var min = this.findMin(node.right);
var temp = node.value;
node.value = min.value;
min.value = temp;
return this.remove(min);
} else if (node.left) {
this.replaceChild(node.parent, node, node.left);
this.keepHeightBalance(node.left, true);
} else if (node.right) {
this.replaceChild(node.parent, node, node.right);
this.keepHeightBalance(node.right, true);
} else {
...size = function () {
return this.root ? this.root.size : 0;
}...
assert(!forest.sameSubset(1, 5));
});
it('should maintain subset sizes', function () {
var forest = new DisjointSetForest();
var assertSizesCorrect = function (elements, size) {
elements.forEach(function (element) {
assert.equal(forest.size(element), size);
});
};
assertSizesCorrect([0, 1, 2, 3, 4], 1);
forest.merge(0, 1);
assertSizesCorrect([0, 1], 2);
forest.merge(0, 2);
assertSizesCorrect([0, 1, 2], 3);
...BezierCurve = function (points) {
this.n = points.length;
this.p = [];
// The binomial coefficient
var c = [1];
var i, j;
for (i = 1; i < this.n; ++i) {
c.push(0);
for (j = i; j >= 1; --j) {
c[j] += c[j - 1];
}
}
// the i-th control point times the coefficient
for (i = 0; i < this.n; ++i) {
this.p.push({x: c[i] * points[i].x, y: c[i] * points[i].y});
}
}n/a
BezierCurve = function (points) {
this.n = points.length;
this.p = [];
// The binomial coefficient
var c = [1];
var i, j;
for (i = 1; i < this.n; ++i) {
c.push(0);
for (j = i; j >= 1; --j) {
c[j] += c[j - 1];
}
}
// the i-th control point times the coefficient
for (i = 0; i < this.n; ++i) {
this.p.push({x: c[i] * points[i].x, y: c[i] * points[i].y});
}
}n/a
get = function (t) {
var res = {x: 0, y: 0};
var i;
var a = 1, b = 1;
// The coefficient
var c = [];
for (i = 0; i < this.n; ++i) {
c.push(a);
a *= t;
}
for (i = this.n - 1; i >= 0; --i) {
res.x += this.p[i].x * c[i] * b;
res.y += this.p[i].y * c[i] * b;
b *= 1 - t;
}
return res;
}...
/**
* Pops the element in the beginning of the queue
*/
Queue.prototype.pop = function () {
if (this.isEmpty()) {
throw new Error('Empty queue');
}
var e = this._elements.get(0);
this._elements.del(0);
return e;
};
Queue.prototype.peek = function () {
if (this.isEmpty()) {
throw new Error('Empty queue');
...function spfa(graph, s) {
var distance = {};
var previous = {};
var queue = {};
var isInQue = {};
var cnt = {};
var head = 0;
var tail = 1;
// initialize
distance[s] = 0;
queue[0] = s;
isInQue[s] = true;
cnt[s] = 1;
graph.vertices.forEach(function (v) {
if (v !== s) {
distance[v] = Infinity;
isInQue[v] = false;
cnt[v] = 0;
}
});
var currNode;
while (head !== tail) {
currNode = queue[head++];
isInQue[currNode] = false;
var neighbors = graph.neighbors(currNode);
for (var i = 0; i < neighbors.length; i++) {
var v = neighbors[i];
// relaxation
var newDistance = distance[currNode] + graph.edge(currNode, v);
if (newDistance < distance[v]) {
distance[v] = newDistance;
previous[v] = currNode;
if (!isInQue[v]) {
queue[tail++] = v;
isInQue[v] = true;
cnt[v]++;
if (cnt[v] > graph.vertices.size)
// indicates negative-weighted cycle
return {
distance: {}
};
}
}
}
}
return {
distance: distance,
previous: previous
};
}n/a
bellmanFord = function (graph, startNode) {
var minDistance = {};
var previousVertex = {};
var edges = [];
var adjacencyListSize = 0;
// Add all the edges from the graph to the 'edges' array
graph.vertices.forEach(function (s) {
graph.neighbors(s).forEach(function (t) {
edges.push({
source: s,
target: t,
weight: graph.edge(s, t)
});
});
minDistance[s] = Infinity;
++adjacencyListSize;
});
minDistance[startNode] = 0;
var edgesSize = edges.length;
var sourceDistance;
var targetDistance;
var iteration;
for (iteration = 0; iteration < adjacencyListSize; ++iteration) {
var somethingChanged = false;
for (var j = 0; j < edgesSize; j++) {
sourceDistance = minDistance[edges[j].source] + edges[j].weight;
targetDistance = minDistance[edges[j].target];
if (sourceDistance < targetDistance) {
somethingChanged = true;
minDistance[edges[j].target] = sourceDistance;
previousVertex[edges[j].target] = edges[j].source;
}
}
if (!somethingChanged) {
// Early stop.
break;
}
}
// If the loop did not break early, then there is a negative-weighted cycle.
if (iteration === adjacencyListSize) {
// Empty 'distance' object indicates Negative-Weighted Cycle
return {
distance: {}
};
}
return {
distance: minDistance,
previous: previousVertex
};
}n/a
bfsShortestPath = function (graph, source) {
var distance = {}, previous = {};
distance[source] = 0;
breadthFirstSearch(graph, source, {
onTraversal: function (vertex, neighbor) {
distance[neighbor] = distance[vertex] + 1;
previous[neighbor] = vertex;
}
});
return {
distance: distance,
previous: previous
};
}n/a
breadthFirstSearch = function (graph, startVertex, callbacks) {
var vertexQueue = new Queue();
vertexQueue.push(startVertex);
callbacks = normalizeCallbacks(callbacks, [startVertex]);
var vertex;
var enqueue = function (neighbor) {
if (callbacks.allowTraversal(vertex, neighbor)) {
callbacks.onTraversal(vertex, neighbor);
vertexQueue.push(neighbor);
}
};
while (!vertexQueue.isEmpty()) {
vertex = vertexQueue.pop();
callbacks.enterVertex(vertex);
graph.neighbors(vertex).forEach(enqueue);
callbacks.leaveVertex(vertex);
}
}n/a
depthFirstSearch = function (graph, startVertex, callbacks) {
dfsLoop(graph, startVertex, normalizeCallbacks(callbacks, [startVertex]));
}n/a
function dijkstra(graph, s) {
var distance = {};
var previous = {};
var q = new PriorityQueue();
// Initialize
distance[s] = 0;
graph.vertices.forEach(function (v) {
if (v !== s) {
distance[v] = Infinity;
}
q.insert(v, distance[v]);
});
var currNode;
var relax = function (v) {
var newDistance = distance[currNode] + graph.edge(currNode, v);
if (newDistance < distance[v]) {
distance[v] = newDistance;
previous[v] = currNode;
q.changePriority(v, distance[v]);
}
};
while (!q.isEmpty()) {
currNode = q.extract();
graph.neighbors(currNode).forEach(relax);
}
return {
distance: distance,
previous: previous
};
}n/a
eulerPath = function (graph) {
if (!graph.vertices.size) {
return [];
}
var endpoints = eulerEndpoints(graph);
var route = [endpoints.finish];
var seen = new Graph(graph.directed);
graph.vertices.forEach(seen.addVertex.bind(seen));
depthFirstSearch(graph, endpoints.start, {
allowTraversal: function (vertex, neighbor) {
return !seen.edge(vertex, neighbor);
},
beforeTraversal: function (vertex, neighbor) {
seen.addEdge(vertex, neighbor);
},
afterTraversal: function (vertex) {
route.push(vertex);
}
});
graph.vertices.forEach(function (vertex) {
if (seen.neighbors(vertex).length < graph.neighbors(vertex).length) {
throw new Error('There is no euler path for a disconnected graph.');
}
});
return route.reverse();
}n/a
floydWarshall = function (graph) {
// Fill in the distances with initial values:
// - 0 if source == destination;
// - edge(source, destination) if there is a direct edge;
// - +inf otherwise.
var distance = Object.create(null);
graph.vertices.forEach(function (src) {
distance[src] = Object.create(null);
graph.vertices.forEach(function (dest) {
if (src === dest) {
distance[src][dest] = 0;
} else if (graph.edge(src, dest) !== undefined) {
distance[src][dest] = graph.edge(src, dest);
} else {
distance[src][dest] = Infinity;
}
});
});
// Internal vertex with the largest index along the shortest path.
// Needed for path reconstruction.
var middleVertex = Object.create(null);
graph.vertices.forEach(function (vertex) {
middleVertex[vertex] = Object.create(null);
});
graph.vertices.forEach(function (middle) {
graph.vertices.forEach(function (src) {
graph.vertices.forEach(function (dest) {
var dist = distance[src][middle] + distance[middle][dest];
if (dist < distance[src][dest]) {
distance[src][dest] = dist;
middleVertex[src][dest] = middle;
}
});
});
});
// Check for a negative-weighted cycle.
graph.vertices.forEach(function (vertex) {
if (distance[vertex][vertex] < 0) {
// Negative-weighted cycle found.
throw new Error('The graph contains a negative-weighted cycle!');
}
});
/**
* Reconstruct the shortest path for a given pair of end vertices.
* Complexity: O(L), L - length of the path (number of edges).
*
* @param {string} srce
* @param {string} dest
* @return {?string[]} Null if destination is unreachable.
*/
var path = function (src, dest) {
if (!Number.isFinite(distance[src][dest])) {
// dest unreachable.
return null;
}
var path = [src];
if (src !== dest) {
(function pushInOrder(src, dest) {
if (middleVertex[src][dest] === undefined) {
path.push(dest);
} else {
var middle = middleVertex[src][dest];
pushInOrder(src, middle);
pushInOrder(middle, dest);
}
})(src, dest);
}
return path;
};
return {
distance: distance,
path: path
};
}n/a
kruskal = function (graph) {
if (graph.directed) {
throw new Error('Can\'t build MST of a directed graph.');
}
var connectedComponents = new DisjointSetForest();
var mst = new Graph(false);
graph.vertices.forEach(mst.addVertex.bind(mst));
var edges = [];
graph.vertices.forEach(function (vertex) {
graph.neighbors(vertex).forEach(function (neighbor) {
// Compared as strings, loops intentionally omitted.
if (vertex < neighbor) {
edges.push({
ends: [vertex, neighbor],
weight: graph.edge(vertex, neighbor)
});
}
});
});
edges.sort(function (a, b) {
return a.weight - b.weight;
}).forEach(function (edge) {
if (!connectedComponents.sameSubset(edge.ends[0], edge.ends[1])) {
mst.addEdge(edge.ends[0], edge.ends[1], edge.weight);
connectedComponents.merge(edge.ends[0], edge.ends[1]);
}
});
return mst;
}n/a
prim = function (graph) {
if (graph.directed) {
throw new Error('Can\'t build MST of a directed graph.');
}
var mst = new Graph(false);
var parent = Object.create(null);
var q = new PriorityQueue();
graph.vertices.forEach(function (vertex) {
q.insert(vertex, Infinity);
});
var relax = function (vertex, neighbor) {
var weight = graph.edge(vertex, neighbor);
if (weight < q.priority(neighbor)) {
q.changePriority(neighbor, weight);
parent[neighbor] = vertex;
}
};
while (!q.isEmpty()) {
var top = q.extract(true);
var vertex = top.item,
weight = top.priority;
if (parent[vertex]) {
mst.addEdge(parent[vertex], vertex, weight);
}
else {
mst.addVertex(vertex);
}
graph.neighbors(vertex).forEach(relax.bind(null, vertex));
}
return mst;
}n/a
topologicalSort = function (graph) {
var stack = new Stack();
var firstHit = {};
var time = 0;
graph.vertices.forEach(function (node) {
if (!firstHit[node]) {
depthFirstSearch(graph, node, {
allowTraversal: function (node, neighbor) {
return !firstHit[neighbor];
},
enterVertex: function (node) {
firstHit[node] = ++time;
},
leaveVertex: function (node) {
stack.push(node);
}
});
}
});
return stack;
}n/a
extendedEuclidean = function (a, b) {
var s = 0, oldS = 1;
var t = 1, oldT = 0;
var r = b, oldR = a;
var quotient, temp;
while (r !== 0) {
quotient = Math.floor(oldR / r);
temp = r;
r = oldR - quotient * r;
oldR = temp;
temp = s;
s = oldS - quotient * s;
oldS = temp;
temp = t;
t = oldT - quotient * t;
oldT = temp;
}
return {
x: oldS,
y: oldT
};
}n/a
fastPower = function (base, power, mul, identity) {
if (mul === undefined) {
mul = multiplicationOperator;
identity = 1;
}
if (power < 0 || Math.floor(power) !== power) {
throw new Error('Power must be a positive integer or zero.');
}
// If the power is zero, identity value must be given (or set by default).
if (!power) {
if (identity === undefined) {
throw new Error('The power is zero, but identity value not set.');
}
else {
return identity;
}
}
// Iterative form of the algorithm avoids checking the same thing twice.
var result;
var multiplyBy = function (value) {
result = (result === undefined) ? value : mul(result, value);
};
for (var factor = base; power; power >>>= 1, factor = mul(factor, factor)) {
if (power & 1) {
multiplyBy(factor);
}
}
return result;
}n/a
fibonacci = function (n) {
var fibNMinus2 = 0,
fibNMinus1 = 1,
fib = n;
for (var i = 1; i < n; i++) {
fib = fibNMinus1 + fibNMinus2;
fibNMinus2 = fibNMinus1;
fibNMinus1 = fib;
}
return fib;
}n/a
fisherYates = function (a) {
for (var i = a.length - 1; i > 0; i--) {
var j = Math.floor(Math.random() * (i + 1));
var tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}n/a
gcd = function (a, b) {
var tmp = a;
a = Math.max(a, b);
b = Math.min(tmp, b);
while (b !== 0) {
tmp = b;
b = a % b;
a = tmp;
}
return a;
}n/a
greatestDifference = function (numbers) {
var index = 0;
var largest = numbers[0];
var length = numbers.length;
var number;
var smallest = numbers[0];
for (index; index < length; index++) {
number = numbers[index];
if (number > largest) largest = number;
if (number < smallest) smallest = number;
}
return largest - smallest;
}n/a
lcm = function () { [native code] }n/a
newtonSqrt = function (n, tolerance, maxIterations) {
tolerance = tolerance || 1e-7;
maxIterations = maxIterations || 1e7;
var upperBound = n;
var lowerBound = 0;
var i = 0;
var square, x;
do {
i++;
x = (upperBound - lowerBound) / 2 + lowerBound;
square = x * x;
if (square < n) lowerBound = x;
else upperBound = x;
} while (Math.abs(square - n) > tolerance && i < maxIterations);
// Checks if the number is a perfect square to return the exact root
var roundX = Math.round(x);
if (roundX * roundX === n) x = roundX;
return x;
}n/a
nextPermutation = function (array, compareFn) {
if (!array.length) {
return false;
}
var cmp = new Comparator(compareFn);
// Find pivot and successor indices.
var pivot = array.length - 1;
while (pivot && cmp.greaterThanOrEqual(array[pivot - 1], array[pivot])) {
pivot -= 1;
}
if (!pivot) {
// Permutation is sorted in descending order.
return false;
}
var pivotValue = array[--pivot];
var successor = array.length - 1;
while (cmp.lessThanOrEqual(array[successor], pivotValue)) {
successor -= 1;
}
// Swap values.
array[pivot] = array[successor];
array[successor] = pivotValue;
// Reverse the descending part.
for (var left = pivot, right = array.length; ++left < --right;) {
var temp = array[left];
array[left] = array[right];
array[right] = temp;
}
return true;
}n/a
powerSet = function (array) {
if (array.length === 0) {
return [];
}
var powerSet = [];
var cache = [];
var i;
for (i = 0; i < array.length; i++) {
cache[i] = true;
}
for (i = 0; i < Math.pow(2, array.length); i++) {
powerSet.push([]);
for (var j = 0; j < array.length; j++) {
if (i % Math.pow(2, j) === 0) {
cache[j] = !cache[j];
}
if (cache[j]) {
powerSet[i].push(array[j]);
}
}
}
return powerSet;
}n/a
reservoirSampling = function (array, sampleSize) {
if (sampleSize > array.length) {
throw new Error('Sample size exceeds the total number of elements.');
}
var reservoir = array.slice(0, sampleSize);
for (var i = sampleSize; i < array.length; ++i) {
var j = Math.floor(Math.random() * (i + 1));
if (j < sampleSize) {
reservoir[j] = array[i];
}
}
return reservoir;
}n/a
shannonEntropy = function (arr) {
// find the frequency of each value
var freqs = arr.reduce(function (acc, item) {
acc[item] = acc[item] + 1 || 1;
return acc;
}, {});
// find the probability of each value
var probs = Object.keys(freqs).map(function (key) {
return freqs[key] / arr.length;
});
// calulate the shannon entropy of the array
return probs.reduce(function (e, p) {
return e - p * Math.log(p);
}, 0) * Math.LOG2E;
}n/a
function calculateCollatzConjecture(number) {
if (number in cache) return cache[number];
if (number % 2 === 0) return cache[number] = number >> 1;
return cache[number] = number * 3 + 1;
}...
var math = require('../../..').Math,
collatzConjecture = math.collatzConjecture,
assert = require('assert');
describe('Collatz Conjecture', function () {
it('should return odd numbers divided by two', function () {
assert.equal(collatzConjecture.calculate(200), 100);
assert.equal(collatzConjecture.calculate(222), 111);
assert.equal(collatzConjecture.calculate(444), 222);
});
it('should return even numbers multiplied by 3 + 1', function () {
assert.equal(collatzConjecture.calculate(111), 334);
assert.equal(collatzConjecture.calculate(333), 1000);
...function generateCollatzConjecture(number) {
var collatzConjecture = [];
do {
number = calculateCollatzConjecture(number);
collatzConjecture.push(number);
} while (number !== 1);
return collatzConjecture;
}...
it('should return even numbers multiplied by 3 + 1', function () {
assert.equal(collatzConjecture.calculate(111), 334);
assert.equal(collatzConjecture.calculate(333), 1000);
assert.equal(collatzConjecture.calculate(555), 1666);
});
it('should return Collatz Conjecture sequence ', function () {
assert.deepEqual(collatzConjecture.generate(10), [5, 16, 8, 4, 2, 1]);
});
});
...fibonacci = function (n) {
var fibNMinus2 = 0,
fibNMinus1 = 1,
fib = n;
for (var i = 1; i < n; i++) {
fib = fibNMinus1 + fibNMinus2;
fibNMinus2 = fibNMinus1;
fibNMinus1 = fib;
}
return fib;
}n/a
direct = function (number) {
var phi = (1 + Math.sqrt(5)) / 2;
return Math.floor(Math.pow(phi, number) / Math.sqrt(5) + 0.5);
}n/a
exponential = function (n) {
return n < 2 ? n : fibExponential(n - 1) + fibExponential(n - 2);
}n/a
logarithmic = function (number) {
// Transforms [f_1, f_0] to [f_2, f_1] and so on.
var nextFib = [[1, 1], [1, 0]];
var matrixMultiply = function (a, b) {
return [[a[0][0] * b[0][0] + a[0][1] * b[1][0],
a[0][0] * b[0][1] + a[0][1] * b[1][1]],
[a[1][0] * b[0][0] + a[1][1] * b[1][0],
a[1][0] * b[0][1] + a[1][1] * b[1][1]]];
};
var transform = power(nextFib, number, matrixMultiply, [[1, 0], [0, 1]]);
// [f_n, f_{n-1}] = Transform * [f_0, f_{-1}] = Transform * [0, 1]
// Hence the result is the first row of Transform multiplied by [0, 1],
// which is the same as transform[0][1].
return transform[0][1];
}n/a
withMemoization = function (n) {
if (cache[n] === undefined) {
cache[n] = fib(n - 1) + fib(n - 2);
}
return cache[n];
}n/a
gcd = function (a, b) {
var tmp = a;
a = Math.max(a, b);
b = Math.min(tmp, b);
while (b !== 0) {
tmp = b;
b = a % b;
a = tmp;
}
return a;
}n/a
binary = function (a, b) {
// GCD(0,b) == b; GCD(a,0) == a, GCD(0,0) == 0
if (a === 0) {
return b;
}
if (b === 0) {
return a;
}
var shift;
// Let shift = log(K), where K is the greatest power of 2
// dividing both a and b
for (shift = 0; ((a | b) & 1) === 0; ++shift) {
a >>= 1;
b >>= 1;
}
// Remove all factors of 2 in a -- they are not common
// Note: a is not zero, so while will terminate
while ((a & 1) === 0) {
a >>= 1;
}
var tmp;
// From here on, a is always odd
do {
// Remove all factors of 2 in b -- they are not common
// Note: b is not zero, so while will terminate
while ((b & 1) === 0) {
b >>= 1;
}
// Now a and b are both odd. Swap if necessary so a <= b,
// then set b = b - a (which is even).
if (a > b) {
tmp = b;
b = a;
a = tmp;
}
b -= a; // Here b >= a
} while (b !== 0);
// restore common factors of 2
return a << shift;
}n/a
lcm = function () { [native code] }n/a
binary = function () { [native code] }n/a
powerSet = function (array) {
if (array.length === 0) {
return [];
}
var powerSet = [];
var cache = [];
var i;
for (i = 0; i < array.length; i++) {
cache[i] = true;
}
for (i = 0; i < Math.pow(2, array.length); i++) {
powerSet.push([]);
for (var j = 0; j < array.length; j++) {
if (i % Math.pow(2, j) === 0) {
cache[j] = !cache[j];
}
if (cache[j]) {
powerSet[i].push(array[j]);
}
}
}
return powerSet;
}n/a
recursive = function (array) {
if (array.length === 0) {
return [];
} else if (array.length === 1) {
return [ [], [ array[0] ] ];
} else {
var powerSet = [];
var firstElem = array[0];
array.splice(0, 1);
powerSetRecursive(array).forEach(function (elem) {
powerSet.push(elem);
var withFirstElem = [ firstElem ];
withFirstElem.push.apply(withFirstElem, elem);
powerSet.push(withFirstElem);
});
return powerSet;
}
}...
assert(fourElementTest.length === 16);
});
});
describe('#recursive()', function () {
it('should return the right elements of power set', function () {
var zeroElementTest = powerSet.recursive([]);
assert(zeroElementTest.length === 0);
var oneElementTest = powerSet.recursive([0]);
assert(testArrayInArray([], oneElementTest));
assert(testArrayInArray([0], oneElementTest));
assert(oneElementTest.length === 2);
...naiveTest = function () { [native code] }n/a
trialDivisionTest = function () { [native code] }n/a
bfs = function (root, callback) {
var q = new Queue();
q.push(root);
var node;
while (!q.isEmpty()) {
node = q.pop();
callback(node.value);
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
}n/a
binarySearch = function (sortedArray, element) {
var init = 0,
end = sortedArray.length - 1;
while (end >= init) {
var m = ((end - init) >> 1) + init;
if (sortedArray[m] === element) return m;
if (sortedArray[m] < element) init = m + 1;
else end = m - 1;
}
return -1;
}n/a
dfs = function (node, callback) {
if (node) {
inOrder(node.left, callback);
callback(node.value);
inOrder(node.right, callback);
}
}n/a
ternarySearch = function (fn, left, right, precision) {
while (Math.abs(right - left) > precision) {
var leftThird = left + (right - left) / 3,
rightThird = right - (right - left) / 3;
if (fn(leftThird) < fn(rightThird))
left = leftThird; else
right = rightThird;
}
return (left + right) / 2;
}n/a
dfs = function (node, callback) {
if (node) {
inOrder(node.left, callback);
callback(node.value);
inOrder(node.right, callback);
}
}n/a
postOrder = function (node, callback) {
if (node) {
postOrder(node.left, callback);
postOrder(node.right, callback);
callback(node.value);
}
}...
* Post-order traversal from the given node.
*/
AVLTree.prototype.postOrder = function (current, callback) {
if (!current) {
return;
}
this.postOrder(current.left, callback);
this.postOrder(current.right, callback);
if (typeof callback === 'function') {
callback(current);
}
};
/**
...preOrder = function (node, callback) {
if (node) {
callback(node.value);
preOrder(node.left, callback);
preOrder(node.right, callback);
}
}...
AVLTree.prototype.preOrder = function (current, callback) {
if (!current) {
return;
}
if (typeof callback === 'function') {
callback(current);
}
this.preOrder(current.left, callback);
this.preOrder(current.right, callback);
};
/**
* Finds a node by its value.
*/
AVLTree.prototype.find = function (value) {
...bubbleSort = function (a, comparatorFn) {
var comparator = new Comparator(comparatorFn);
var n = a.length;
var bound = n - 1;
var check = false;
for (var i = 0; i < n - 1; i++) {
var newbound = 0;
for (var j = 0; j < bound; j++) {
if (comparator.greaterThan(a[j], a[j + 1])) {
var tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
newbound = j;
check = true;
}
}
if (!check)
return a;
bound = newbound;
}
return a;
}n/a
countingSort = function (array) {
var max = maximumKey(array);
var auxiliaryArray = [];
var length = array.length;
var i;
for (i = 0; i < length; i++) {
var position = array[i].key;
if (auxiliaryArray[position] === undefined) {
auxiliaryArray[position] = [];
}
auxiliaryArray[position].push(array[i]);
}
array = [];
var pointer = 0;
for (i = 0; i <= max; i++) {
if (auxiliaryArray[i] !== undefined) {
var localLength = auxiliaryArray[i].length;
for (var j = 0; j < localLength; j++) {
array[pointer++] = auxiliaryArray[i][j];
}
}
}
return array;
}n/a
heapSort = function (array, comparatorFn) {
var minHeap = new MinHeap(comparatorFn);
minHeap.heapify(array);
var result = [];
while (!minHeap.isEmpty())
result.push(minHeap.extract());
return result;
}n/a
insertionSort = function (vector, comparatorFn) {
var comparator = new Comparator(comparatorFn);
for (var i = 1, len = vector.length; i < len; i++) {
var aux = vector[i],
j = i;
while (j > 0 && comparator.lessThan(aux, vector[j - 1])) {
vector[j] = vector[j - 1];
j--;
}
vector[j] = aux;
}
return vector;
}n/a
mergeSort = function (a, compareFn) {
var comparator = new Comparator(compareFn);
return (function mergeSort(a) {
if (a.length > 1) {
var middle = a.length >> 1;
var left = mergeSort(a.slice(0, middle));
var right = mergeSort(a.slice(middle));
a = merge(left, right, comparator);
}
return a;
})(a);
}n/a
quicksort = function (array, comparatorFn) {
var comparator = new Comparator(comparatorFn);
return (function quicksort(array, lo, hi) {
while (lo < hi) {
var p = partition(array, comparator, lo, hi);
//Chooses only the smallest partition to use recursion on and
//tail-optimize the other. This guarantees O(log n) space in worst case.
if (p - lo < hi - p) {
quicksort(array, lo, p - 1);
lo = p + 1;
} else {
quicksort(array, p + 1, hi);
hi = p - 1;
}
}
return array;
})(array, 0, array.length - 1);
}n/a
radixSort = function (array) {
var max = maximumKey(array);
var digitsMax = (max === 0 ? 1 :
1 + Math.floor(Math.log(max) / Math.log(10))); // log base 10
for (var i = 0; i < digitsMax; i++) {
array = auxiliaryCountingSort(array, i);
}
return array;
}n/a
selectionSort = function (a, comparatorFn) {
var comparator = new Comparator(comparatorFn);
var n = a.length;
for (var i = 0; i < n - 1; i++) {
var min = i;
for (var j = i + 1; j < n; j++) {
if (comparator.greaterThan(a[min], a[j])) {
min = j;
}
}
if (min !== i) {
var tmp = a[i];
a[i] = a[min];
a[min] = tmp;
}
}
return a;
}n/a
shellSort = function (array, comparatorFn) {
var comparator = new Comparator(comparatorFn),
begin = 0,
end = array.length - 1,
gap = parseInt((end - begin + 1) / 2),
i = 0, j = 0, temp = 0;
while (gap >= 1) {
for (i = begin + gap;i <= end;i += 1) {
temp = array[i];
j = i - gap;
while (j >= begin && comparator.greaterThan(array[j], temp)) {
array[j + gap] = array[j];
j = j - gap;
}
array[j + gap] = temp;
}
gap = parseInt(gap / 2);
}
return array;
}n/a
function shortBubbleSort(array, comparatorFn) {
var comparator = new Comparator(comparatorFn);
var length = array.length - 1;
var i = 0;
for (i; i < length; i++) {
var current = array[i];
var next = array[i+1];
/**
* If the current value if greater than the next:
* - set current value to next value;
* - and set next value to current value;
* - then reset iterator counter to rescan for values to be sorted.
*/
if (comparator.greaterThan(current, next)) {
array[i+1] = current;
array[i] = next;
i = -1;
}
}
return array;
}n/a
hamming = function (a, b) {
if (a.length !== b.length) {
throw new Error('Strings must be equal in length');
}
var dist = 0;
for (var i = 0; i < a.length; i++) {
if (a[i] !== b[i]) {
dist++;
}
}
return dist;
}n/a
knuthMorrisPratt = function (text, pattern) {
var textLength = text.length;
var patternLength = pattern.length;
var m = 0;
var i = 0;
var table = buildTable(pattern);
while (m + i < textLength) {
if (pattern[i] === text[m + i]) {
if (i === patternLength - 1) {
return m;
}
++i;
}
else {
if (table[i] >= 0) {
i = table[i];
m = m + i - table[i];
}
else {
i = 0;
++m;
}
}
}
return textLength;
}n/a
levenshtein = function (a, b) {
var editDistance = [];
var i, j;
// Initialize the edit distance matrix. The first collumn contains
// the values comparing the string a to an empty string b
for (i = 0; i <= a.length; i++) {
editDistance[i] = [];
editDistance[i][0] = i;
}
// And the first line the values comparint the string b to an empty string a
for (j = 0; j <= b.length; j++) {
editDistance[0][j] = j;
}
for (i = 1; i <= a.length; i++) {
for (j = 1; j <= b.length; j++) {
// Finds the minimum cost for keeping the two strings equal
editDistance[i][j] =
Math.min(
editDistance[i - 1][j - 1], // if we replace a[i] by b[j]
editDistance[i - 1][j], // if we delete the char from a
editDistance[i][j - 1] // if we add the char from b
) +
(a[i - 1] !== b[j - 1] ? 1 : 0);
}
}
return editDistance[a.length][b.length];
}n/a
longestCommonSubsequence = function (s1, s2) {
// Multidimensional array for dynamic programming algorithm
var cache = new Array(s1.length + 1);
var i, j;
for (i = 0; i <= s1.length; i++) {
cache[i] = new Int32Array(s2.length + 1);
}
// Fill in the cache
for (i = 1; i <= s1.length; i++) {
for (j = 1; j <= s2.length; j++) {
if (s1[i - 1] === s2[j - 1]) {
cache[i][j] = cache[i - 1][j - 1] + 1;
} else {
cache[i][j] = Math.max(cache[i][j - 1], cache[i - 1][j]);
}
}
}
// Build LCS from cache
i = s1.length;
j = s2.length;
var lcs = '';
while (cache[i][j] !== 0) {
if (s1[i - 1] === s2[j - 1]) {
lcs = s1[i - 1] + lcs;
i--;
j--;
} else if (cache[i - 1][j] > cache[i][j - 1]) {
i--;
} else {
j--;
}
}
return lcs;
}n/a
longestCommonSubstring = function (s1, s2) {
// Multidimensional array for dynamic programming algorithm
var cache = new Array(s1.length + 1);
var i, j;
for (i = 0; i <= s1.length + 1; i++) {
cache[i] = new Int32Array(s2.length + 1);
}
var lcsPosition = {};
var lcsLength = 0;
// Fill in the cache
for (i = 1; i <= s1.length; i++) {
for (j = 1; j <= s2.length; j++) {
if (s1[i - 1] === s2[j - 1]) {
cache[i][j] = cache[i - 1][j - 1] + 1;
if (cache[i][j] > lcsLength) {
lcsPosition.i = i;
lcsPosition.j = j;
lcsLength = cache[i][j];
}
} else {
cache[i][j] = 0;
}
}
}
var lcs = '';
if (lcsLength) {
lcs = s1.substring(lcsPosition.i - lcsLength, lcsPosition.i);
}
return lcs;
}n/a
rabinKarp = function (s, pattern) {
if (pattern.length === 0) return 0;
var hashPattern = hash(pattern);
var currentSubstring = s.substring(0, pattern.length);
var hashCurrentSubstring;
for (var i = pattern.length; i <= s.length; i++) {
if (hashCurrentSubstring === undefined) {
hashCurrentSubstring = hash(currentSubstring);
} else {
/*
* Re-hash
* Recalculates the hash representation of a word so that it isn't
* necessary to traverse the whole word again
*/
hashCurrentSubstring -= currentSubstring.charCodeAt(0) *
Math.pow(base, pattern.length - 1);
hashCurrentSubstring *= base;
hashCurrentSubstring += s.charCodeAt(i);
currentSubstring = currentSubstring.substring(1) + s[i];
}
if (hashPattern === hashCurrentSubstring &&
pattern === currentSubstring) {
// Hack for the off-by-one when matching in the beginning of the string
return i === pattern.length ? 0 : i - pattern.length + 1;
}
}
return -1;
}n/a
decode = function (encoding, encodedString) {
if (Array.isArray(encodedString)) {
encodedString = decompress(encodedString);
}
// We can make use of the fact that encoding mapping is always one-to-one
// and rely on the power of JS hashes instead of building hand-made FSMs.
var letterByCode = Object.keys(encoding).reduce(function (acc, letter) {
acc[encoding[letter]] = letter;
return acc;
}, {});
var decodedLetters = [];
var unresolved = encodedString.split('').reduce(function (code, char) {
code += char;
var letter = letterByCode[code];
if (letter) {
decodedLetters.push(letter);
code = '';
}
return code;
}, '');
if (unresolved) {
throw new Error('Invalid string to decode.');
}
return decodedLetters.join('');
}...
}
messages.push(characters.join(''));
}
it('should decode previously encoded messages correctly', function () {
messages.forEach(function (message) {
var encoded = huffman.encode(message);
var decoded = huffman.decode(encoded.encoding, encoded.value);
assert.equal(message, decoded);
var encodedCompressed = huffman.encode(message, true);
var decodedCompressed = huffman.decode(encodedCompressed.encoding,
encodedCompressed.value);
assert.equal(message, decodedCompressed);
});
});
...encode = function (string, compressed) {
if (!string.length) {
return {
encoding: {},
value: (compressed ? [] : '')
};
}
var counter = {};
string.split('').forEach(function (char) {
counter[char] = (counter[char] || 0) + 1;
});
var letters = Object.keys(counter).map(function (char) {
return {
char: char,
count: counter[char]
};
});
var compare = function (a, b) {
return a.count - b.count;
};
var less = function (a, b) {
return a && (b && (a.count < b.count) || !b);
};
letters.sort(compare);
// Each time two least letters are merged into one, the result is pushing into
// this buffer. Since the letters are pushing in ascending order of frequency,
// no more sorting is ever required.
var buffer = [];
var lettersIndex = 0, bufferIndex = 0;
var extractMinimum = function () {
return less(letters[lettersIndex], buffer[bufferIndex]) ?
letters[lettersIndex++] : buffer[bufferIndex++];
};
for (var numLetters = letters.length; numLetters > 1; --numLetters) {
var a = extractMinimum(), b = extractMinimum();
a.code = '0';
b.code = '1';
var union = {
count: a.count + b.count,
parts: [a, b]
};
buffer.push(union);
}
// At this point there is a single letter left.
var root = extractMinimum();
root.code = (letters.length > 1) ? '' : '0';
// Unroll the code recursively in reverse.
(function unroll(parent) {
if (parent.parts) {
var a = parent.parts[0], b = parent.parts[1];
a.code += parent.code;
b.code += parent.code;
unroll(a);
unroll(b);
}
})(root);
var encoding = letters.reduce(function (acc, letter) {
acc[letter.char] = letter.code.split('').reverse().join('');
return acc;
}, {});
// Finally, apply the encoding to the given string.
var result = string.split('').map(function (char) {
return encoding[char];
}).join('');
return {
encoding: encoding,
value: (compressed ? compress(result) : result)
};
}...
characters.push(String.fromCharCode(charCode));
}
messages.push(characters.join(''));
}
it('should decode previously encoded messages correctly', function () {
messages.forEach(function (message) {
var encoded = huffman.encode(message);
var decoded = huffman.decode(encoded.encoding, encoded.value);
assert.equal(message, decoded);
var encodedCompressed = huffman.encode(message, true);
var decodedCompressed = huffman.decode(encodedCompressed.encoding,
encodedCompressed.value);
assert.equal(message, decodedCompressed);
});
...function Comparator(compareFn) {
if (compareFn) {
this.compare = compareFn;
}
}n/a
compare = function (a, b) {
if (a === b) return 0;
return a < b ? -1 : 1;
}...
*/
Comparator.prototype.compare = function (a, b) {
if (a === b) return 0;
return a < b ? -1 : 1;
};
Comparator.prototype.lessThan = function (a, b) {
return this.compare(a, b) < 0;
};
Comparator.prototype.lessThanOrEqual = function (a, b) {
return this.lessThan(a, b) || this.equal(a, b);
};
Comparator.prototype.greaterThan = function (a, b) {
...equal = function (a, b) {
return this.compare(a, b) === 0;
}...
};
Comparator.prototype.lessThan = function (a, b) {
return this.compare(a, b) < 0;
};
Comparator.prototype.lessThanOrEqual = function (a, b) {
return this.lessThan(a, b) || this.equal(a, b);
};
Comparator.prototype.greaterThan = function (a, b) {
return this.compare(a, b) > 0;
};
Comparator.prototype.greaterThanOrEqual = function (a, b) {
...greaterThan = function (a, b) {
return this.compare(a, b) > 0;
}...
if (root.value === e)
return root;
if (this._comparator.lessThan(e, root.value))
return root.left && this._find(e, root.left);
if (this._comparator.greaterThan(e, root.value))
return root.right && this._find(e, root.right);
};
/**
* Substitute two nodes
*/
BST.prototype._replaceNodeInParent = function (currNode, newNode) {
...greaterThanOrEqual = function (a, b) {
return this.greaterThan(a, b) || this.equal(a, b);
}...
if (!array.length) {
return false;
}
var cmp = new Comparator(compareFn);
// Find pivot and successor indices.
var pivot = array.length - 1;
while (pivot && cmp.greaterThanOrEqual(array[pivot - 1], array[pivot])) {
pivot -= 1;
}
if (!pivot) {
// Permutation is sorted in descending order.
return false;
}
var pivotValue = array[--pivot];
...lessThan = function (a, b) {
return this.compare(a, b) < 0;
}...
this.root = new Node(value);
this._size++;
return;
}
parent = this.root;
}
var child = this._comparator.lessThan(value, parent.value) ? 'left' : '
;right';
if (parent[child]) {
this.insert(value, parent[child]);
} else {
parent[child] = new Node(value, parent);
this._size++;
}
};
...lessThanOrEqual = function (a, b) {
return this.lessThan(a, b) || this.equal(a, b);
}...
}
if (!pivot) {
// Permutation is sorted in descending order.
return false;
}
var pivotValue = array[--pivot];
var successor = array.length - 1;
while (cmp.lessThanOrEqual(array[successor], pivotValue)) {
successor -= 1;
}
// Swap values.
array[pivot] = array[successor];
array[successor] = pivotValue;
...reverse = function () {
var originalCompareFn = this.compare;
this.compare = function (a, b) {
return originalCompareFn(b, a);
};
}...
*
* To avoid code repetition, the Min Heap is used just with
* a reverse comparator;
*/
function MaxHeap(compareFn) {
MinHeap.call(this, compareFn);
this._comparator.reverse();
}
MaxHeap.prototype = new MinHeap();
module.exports = {
MinHeap: MinHeap,
MaxHeap: MaxHeap
...