/**
* Interval tree is an ordered tree data structure to hold intervals.
*
* @example
*
* var IT = require('path-to-algorithms/src/data-structures/interval-tree');
* var intervalTree = new IT.IntervalTree();
*
* intervalTree.add([0, 100]);
* intervalTree.add([101, 200]);
* intervalTree.add([10, 50]);
* intervalTree.add([120, 220]);
*
* console.log(intervalTree.contains(150)); // true
* console.log(intervalTree.contains(250)); // false
* console.log(intervalTree.intersects([210, 310])); // true
* console.log(intervalTree.intersects([310, 320])); // false
*
* @module data-structures/interval-tree
*/
(function (exports) {
'use strict';
/**
* Node which describes an interval.
*
* @public
* @constructor
* @param {Number} start Start of the interval.
* @param {Number} end End of the interval.
* @param {Node} left Left child node.
* @param {Node} right Right child node.
*/
exports.Node = function (start, end, left, right) {
/**
* Node interval.
* @member {Array}
*/
this.interval = [start, end];
/**
* Max endpoint in subtree which starts from this node.
* @member {Number}
*/
this.max = -Infinity;
/**
* Parent node.
* @member {Node}
*/
this.parentNode = null;
/**
* Left child node.
* @member {Node}
*/
this.left = left;
/**
* Right child node.
* @member {Node}
*/
this.right = right;
};
/**
* Interval tree.
*
* @public
* @constructor
*/
exports.IntervalTree = function () {
/**
* Root node of the tree.
* @member {Node}
*/
this.root = null;
};
function addNode(node, side, interval) {
var child = new exports.Node(interval[0], interval[1]);
child.max = interval[1];
child.parentNode = node;
node[side] = child;
if (node.max < interval[1]) {
while (child) {
if (child.max < interval[1]) {
child.max = interval[1];
}
child = child.parentNode;
}
}
}
function addHelper(node, interval) {
if (node.interval[0] > interval[0]) {
if (node.left) {
addHelper(node.left, interval);
} else {
addNode(node, 'left', interval);
}
} else {
if (node.right) {
addHelper(node.right, interval);
} else {
addNode(node, 'right', interval);
}
}
}
/**
* Add new interval to the tree.
*
* @public
* @param {Array} intreval Array with start and end points of the interval.
*/
exports.IntervalTree.prototype.add = function (interval) {
if (!this.root) {
this.root = new exports.Node(interval[0], interval[1]);
this.root.max = interval[1];
return;
}
addHelper(this.root, interval);
};
function contains(point, node) {
if (!node) {
return false;
}
if (node.interval[0] <= point && node.interval[1] >= point) {
return true;
}
var result = false;
var temp;
['left', 'right'].forEach(function (key) {
temp = node[key];
if (temp) {
if (temp.max > point) {
result = result || contains(point, temp);
}
}
});
return result;
}
/**
* Checks or point belongs to at least one intarval from the tree.<br><br>
* Complexity: O(log N).
*
* @public
* @method
* @param {Number} point Point which should be checked.
* @return {Boolean} True if point belongs to one of the intervals.
*/
exports.IntervalTree.prototype.contains = function (point) {
return contains(point, this.root);
};
function intersects(a, b) {
return (a[0] <= b[0] && a[1] >= b[0]) || (a[0] <= b[1] && a[1] >= b[1]) ||
(b[0] <= a[0] && b[1] >= a[0]) || (b[0] <= a[1] && b[1] >= a[1]);
}
function intersectsHelper(interval, node) {
if (!node) {
return false;
}
if (intersects(node.interval, interval)) {
return true;
}
var result = false;
var temp;
['left', 'right'].forEach(function (side) {
temp = node[side];
if (temp && temp.max >= interval[0]) {
result = result || intersectsHelper(interval, temp);
}
});
return result;
}
/**
* Checks or interval belongs to at least one intarval from the tree.<br><br>
* Complexity: O(log N).
*
* @public
* @method
* @param {Array} interval Interval which should be checked.
* @return {Boolean} True if interval intersects with one of the intervals.
*/
exports.IntervalTree.prototype.intersects = function (interval) {
return intersectsHelper(interval, this.root);
};
function heightHelper(node) {
if (!node) {
return 0;
}
return 1 + Math.max(heightHelper(node.left), heightHelper(node.right));
}
/**
* Returns height of the tree.
*
* @public
* @method
* @return {Number} Height of the tree.
*/
exports.IntervalTree.prototype.height = function () {
return heightHelper(this.root);
};
/**
* Returns node with the max endpoint in subtree.
*
* @public
* @method
* @param {Node} node Root node of subtree.
* @return {Node} Node with the largest endpoint.
*/
exports.IntervalTree.prototype.findMax = function (node) {
var stack = [node];
var current;
var max = -Infinity;
var maxNode;
while (stack.length) {
current = stack.pop();
if (current.left) {
stack.push(current.left);
}
if (current.right) {
stack.push(current.right);
}
if (current.interval[1] > max) {
max = current.interval[1];
maxNode = current;
}
}
return maxNode;
};
// adjust the max value
exports.IntervalTree.prototype._removeHelper = function (interval, node) {
if (!node) {
return;
}
if (node.interval[0] === interval[0] &&
node.interval[1] === interval[1]) {
// When left and right children exists
if (node.left && node.right) {
var replacement = node.left;
while (replacement.left) {
replacement = replacement.left;
}
var temp = replacement.interval;
replacement.interval = node.interval;
node.interval = temp;
this._removeHelper(replacement.interval, node);
} else {
// When only left or right child exists
var side = 'left';
if (node.right) {
side = 'right';
}
var parentNode = node.parentNode;
if (parentNode) {
if (parentNode.left === node) {
parentNode.left = node[side];
} else {
parentNode.right = node[side];
}
if (node[side]) {
node[side].parentNode = parentNode;
}
} else {
this.root = node[side];
// last node removed
if (this.root) {
this.root.parentNode = null;
}
}
}
// Adjust the max value
var p = node.parentNode;
if (p) {
var maxNode = this.findMax(p);
var max = maxNode.interval[1];
while (maxNode) {
if (maxNode.max === node.interval[1]) {
maxNode.max = max;
maxNode = maxNode.parentNode;
} else {
maxNode = false;
}
}
}
} else {
// could be optimized
this._removeHelper(interval, node.left);
this._removeHelper(interval, node.right);
}
};
/**
* Remove interval from the tree.
*
* @public
* @method
* @param {Array} intreval Array with start and end of the interval.
*/
exports.IntervalTree.prototype.remove = function (interval) {
return this._removeHelper(interval, this.root);
};
})(typeof window === 'undefined' ? module.exports : window);