Skip to content

Commit fe35792

Browse files
mgechevmgechev
committed
Linting of the interval tree
1 parent ede1819 commit fe35792

File tree

1 file changed

+97
-89
lines changed

1 file changed

+97
-89
lines changed

‎src/data-structures/interval-tree.js

Lines changed: 97 additions & 89 deletions
Original file line numberDiff line numberDiff line change
@@ -1,112 +1,120 @@
1-
function Node(start, end, left, right) {
2-
this.interval = [start, end];
3-
this.max = -Infinity;
4-
this.parentNode = null;
5-
this.left = left;
6-
this.right = right;
7-
}
1+
(function (exports) {
2+
'use strict';
83

9-
function IntervalTree() {
10-
this.root = null;
11-
}
4+
function Node(start, end, left, right) {
5+
this.interval = [start, end];
6+
this.max = -Infinity;
7+
this.parentNode = null;
8+
this.left = left;
9+
this.right = right;
10+
}
11+
12+
function IntervalTree() {
13+
this.root = null;
14+
}
1215

13-
function addNode(node, side, interval) {
14-
var child = new Node(interval[0], interval[1]);
15-
child.parentNode = node;
16-
node[side] = child;
17-
if (side === 'right' && node.max < interval[1]) {
18-
while (child) {
19-
if (child.max < interval[1]) {
20-
child.max = interval[1];
16+
function addNode(node, side, interval) {
17+
var child = new Node(interval[0], interval[1]);
18+
child.parentNode = node;
19+
node[side] = child;
20+
if (side === 'right' && node.max < interval[1]) {
21+
while (child) {
22+
if (child.max < interval[1]) {
23+
child.max = interval[1];
24+
}
25+
child = child.parentNode;
2126
}
22-
child = child.parentNode;
2327
}
2428
}
25-
}
2629

27-
function addHelper(node, interval) {
28-
if (node.interval[0] > interval[0]) {
29-
if (node.left) {
30-
addHelper(node.left, interval);
31-
} else {
32-
addNode(node, 'left', interval);
33-
}
34-
} else {
35-
if (node.right) {
36-
addHelper(node.right, interval);
30+
function addHelper(node, interval) {
31+
if (node.interval[0] > interval[0]) {
32+
if (node.left) {
33+
addHelper(node.left, interval);
34+
} else {
35+
addNode(node, 'left', interval);
36+
}
3737
} else {
38-
addNode(node, 'right', interval);
38+
if (node.right) {
39+
addHelper(node.right, interval);
40+
} else {
41+
addNode(node, 'right', interval);
42+
}
3943
}
4044
}
41-
}
4245

43-
IntervalTree.prototype.add = function (interval) {
44-
if (!this.root) {
45-
this.root = new Node(interval[0], interval[1]);
46-
return;
47-
}
48-
addHelper(this.root, interval);
49-
};
46+
IntervalTree.prototype.add = function (interval) {
47+
if (!this.root) {
48+
this.root = new Node(interval[0], interval[1]);
49+
return;
50+
}
51+
addHelper(this.root, interval);
52+
};
5053

51-
function contains(point, node) {
52-
if (!node) {
53-
return false;
54-
}
55-
if (node.interval[0] <= point && node.interval[1] >= point) {
56-
return true;
57-
}
58-
var result = false, temp;
59-
['left', 'right'].forEach(function (key) {
60-
temp = node[key];
61-
if (temp) {
62-
if (temp.max > point) {
63-
result = result || contains(point, temp);
64-
}
54+
function contains(point, node) {
55+
if (!node) {
56+
return false;
6557
}
66-
});
67-
return result;
68-
}
58+
if (node.interval[0] <= point && node.interval[1] >= point) {
59+
return true;
60+
}
61+
var result = false, temp;
62+
['left', 'right'].forEach(function (key) {
63+
temp = node[key];
64+
if (temp) {
65+
if (temp.max > point) {
66+
result = result || contains(point, temp);
67+
}
68+
}
69+
});
70+
return result;
71+
}
6972

70-
IntervalTree.prototype.contains = function (point) {
71-
return contains(point, this.root);
72-
};
73+
IntervalTree.prototype.contains = function (point) {
74+
return contains(point, this.root);
75+
};
7376

74-
function intersectsHelper(interval, node) {
75-
if (!node) {
76-
return false;
77-
}
78-
if (intersects(node.interval, interval)) {
79-
return true;
80-
}
81-
var result = false, temp;
82-
['left', 'right'].forEach(function (side) {
83-
temp = node[side];
84-
if (temp && temp.max >= interval[0]) {
85-
result = result || intersectsHelper(interval, temp);
77+
function intersectsHelper(interval, node) {
78+
if (!node) {
79+
return false;
80+
}
81+
if (intersects(node.interval, interval)) {
82+
return true;
8683
}
87-
});
88-
return result;
89-
}
84+
var result = false, temp;
85+
['left', 'right'].forEach(function (side) {
86+
temp = node[side];
87+
if (temp && temp.max >= interval[0]) {
88+
result = result || intersectsHelper(interval, temp);
89+
}
90+
});
91+
return result;
92+
}
9093

91-
function intersects(a, b) {
92-
return (a[0] <= b[0] && a[1] >= b[0]) || (a[0] <= b[1] && a[1] >= b[1]) ||
93-
(b[0] <= a[0] && b[1] >= a[0]) || (b[0] <= a[1] && b[1] >= a[1]);
94-
}
94+
function intersects(a, b) {
95+
return (a[0] <= b[0] && a[1] >= b[0]) || (a[0] <= b[1] && a[1] >= b[1]) ||
96+
(b[0] <= a[0] && b[1] >= a[0]) || (b[0] <= a[1] && b[1] >= a[1]);
97+
}
9598

96-
IntervalTree.prototype.intersects = function (interval) {
97-
return intersectsHelper(interval, this.root);
98-
};
99+
IntervalTree.prototype.intersects = function (interval) {
100+
return intersectsHelper(interval, this.root);
101+
};
99102

100-
function heightHelper(node) {
101-
if (!node) {
102-
return 0;
103+
function heightHelper(node) {
104+
if (!node) {
105+
return 0;
106+
}
107+
return 1 + Math.max(heightHelper(node.left), heightHelper(node.right));
103108
}
104-
return 1 + Math.max(heightHelper(node.left), heightHelper(node.right));
105-
}
106109

107-
IntervalTree.prototype.height = function () {
108-
return heightHelper(this.root);
109-
};
110+
IntervalTree.prototype.height = function () {
111+
return heightHelper(this.root);
112+
};
113+
114+
exports.Node = Node;
115+
exports.IntervalTree = IntervalTree;
116+
117+
}(typeof exports === 'undefined' ? window : exports));
110118

111119
//
112120
// var t = new IntervalTree();

0 commit comments

Comments
 (0)