Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit fe35792

Browse filesBrowse files
mgechevmgechev
committed
Linting of the interval tree
1 parent ede1819 commit fe35792
Copy full SHA for fe35792

1 file changed

+97-89Lines changed: 97 additions & 89 deletions

File tree

Expand file treeCollapse file tree
Open diff view settings
Filter options
Expand file treeCollapse file tree
Open diff view settings
Collapse file

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

Copy file name to clipboardExpand all lines: src/data-structures/interval-tree.js
+97-89Lines 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 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.