INNER CODE UNIT · JavaScript
it_index
lh3/minigraph · misc/mgutils.js:45
function it_index(a) {
if (a.length == 0) return -1;
a.sort(function(x, y) { return x[0] - y[0] });
var last, last_i;
for (var i = 0; i < a.length; i += 2) last = a[i][2] = a[i][1], last_i = i;
for (var k = 1; 1<<k <= a.length; ++k) {
var i0 = (1<<k) - 1, step = 1<<(k+1);
for (var i = i0; i < a.length; i += step) {
var x = 1<<(k-1);
a[i][2] = a[i][1];
if (a[i][2] < a[i-x][2]) a[i][2] = a[i-x][2];
var e = i + x < a.length? a[i+x][2] : last;
if (a[i][2] < e) a[i][2] = e;
}
last_i = last_i>>k&1? last_i - (1<<(k-1)) : last_i + (1<<(k-1));
if (last_i < a.length) last = last > a[last_i][2]? last : a[last_i][2];
}
return k - 1;