INNER CODE UNIT · JavaScript
it_overlap
lh3/minigraph · misc/mgutils.js:65
function it_overlap(a, st, en) {
if (a == null) return [];
var h, stack = [], b = [];
for (h = 0; 1<<h <= a.length; ++h);
--h;
stack.push([(1<<h) - 1, h, 0]);
while (stack.length) {
var t = stack.pop();
var x = t[0], h = t[1], w = t[2];
if (h <= 2) {
var i0 = x >> h << h, i1 = i0 + (1<<(h+1)) - 1;
if (i1 >= a.length) i1 = a.length;
for (var i = i0; i < i1; ++i)
if (a[i][0] < en && st < a[i][1])
b.push(a[i]);
} else if (w == 0) { // if left child not processed
stack.push([x, h, 1]);
var y = x - (1<<(h-1));