interval-tree-1d with preval

interval-tree-1d.js

//@noflow
/* eslint-disable */

'use strict';
//prettier-ignore
(function () {
  var $$0 = {
    enumerable: false,
    configurable: false
  };

  var _$0 = this;

  var _$1 = _$0.Object;
  var _$2 = _$1.defineProperty;

  var _B = function (t, i, r, h, n) {
    this.mid = t, this.left = i, this.right = r, this.leftPoints = h, this.rightPoints = n, this.count = (i ? i.count : 0) + (r ? r.count : 0) + h.length;
  };

  var _C = _B.prototype;

  var _1 = function (t) {
    this.root = t;
  };

  var _2 = _1.prototype;

  var _E = function (t) {
    return t.push.apply(t, this.leftPoints), this.left && this.left.intervals(t), this.right && this.right.intervals(t), t;
  };

  var _F = function (i) {
    var s,
        e,
        l = this.count - this.leftPoints.length;
    this.count += 1, i[1] < this.mid ? this.left ? 4 * (this.left.count + 1) > 3 * (l + 1) ? _M(this, i) : this.left.insert(i) : this.left = _A([i]) : i[0] > this.mid ? this.right ? 4 * (this.right.count + 1) > 3 * (l + 1) ? _M(this, i) : this.right.insert(i) : this.right = _A([i]) : (s = _L.ge(this.leftPoints, i, _J), e = _L.ge(this.rightPoints, i, _K), this.leftPoints.splice(s, 0, i), this.rightPoints.splice(e, 0, i));
  };

  var _G = function (t) {
    var i,
        n,
        s,
        e,
        u = this.count - this.leftPoints;
    if (t[1] < this.mid) return this.left ? 4 * (this.right ? this.right.count : 0) > 3 * (u - 1) ? _S(this, t) : 2 === (i = this.left.remove(t)) ? (this.left = null, this.count -= 1, 1) : (1 === i && (this.count -= 1), i) : 0;
    if (t[0] > this.mid) return this.right ? 4 * (this.left ? this.left.count : 0) > 3 * (u - 1) ? _S(this, t) : 2 === (i = this.right.remove(t)) ? (this.right = null, this.count -= 1, 1) : (1 === i && (this.count -= 1), i) : 0;
    if (1 === this.count) return this.leftPoints[0] === t ? 2 : 0;

    if (1 === this.leftPoints.length && this.leftPoints[0] === t) {
      if (this.left && this.right) {
        for (n = this, s = this.left; s.right;) n = s, s = s.right;

        n === this ? s.right = this.right : (e = this.left, i = this.right, n.count -= s.count, n.right = s.left, s.left = e, s.right = i), _T(this, s), this.count = (this.left ? this.left.count : 0) + (this.right ? this.right.count : 0) + this.leftPoints.length;
      } else this.left ? _T(this, this.left) : _T(this, this.right);

      return 1;
    }

    for (e = _L.ge(this.leftPoints, t, _J); e < this.leftPoints.length && this.leftPoints[e][0] === t[0]; ++e) if (this.leftPoints[e] === t) for (this.count -= 1, this.leftPoints.splice(e, 1), i = _L.ge(this.rightPoints, t, _K); i < this.rightPoints.length && this.rightPoints[i][1] === t[1]; ++i) if (this.rightPoints[i] === t) return this.rightPoints.splice(i, 1), 1;

    return 0;
  };

  var _H = function (t, i) {
    var r;
    return t < this.mid ? this.left && (r = this.left.queryPoint(t, i)) ? r : _U(this.leftPoints, t, i) : t > this.mid ? this.right && (r = this.right.queryPoint(t, i)) ? r : _V(this.rightPoints, t, i) : _W(this.leftPoints, i);
  };

  var _I = function (t, i, r) {
    var h;
    return t < this.mid && this.left && (h = this.left.queryInterval(t, i, r)) ? h : i > this.mid && this.right && (h = this.right.queryInterval(t, i, r)) ? h : i < this.mid ? _U(this.leftPoints, i, r) : t > this.mid ? _V(this.rightPoints, t, r) : _W(this.leftPoints, r);
  };

  var _4 = function (t) {
    this.root ? this.root.insert(t) : this.root = new _B(t[0], null, null, [t], [t]);
  };

  var _5 = function (t) {
    if (this.root) {
      var i = this.root.remove(t);
      return 2 === i && (this.root = null), 0 !== i;
    }

    return !1;
  };

  var _6 = function (t, i) {
    if (this.root) return this.root.queryPoint(t, i);
  };

  var _7 = function (t, i, r) {
    if (i >= t && this.root) return this.root.queryInterval(t, i, r);
  };

  var _8 = function () {
    return this.root ? this.root.count : 0;
  };

  var _9 = function () {
    return this.root ? this.root.intervals([]) : [];
  };

  _C.intervals = _E;

  var _A = n => {
    var s, e, o, l, f, u, g, v, c;
    if (0 === n.length) return null;

    for (s = [], e = 0; e < n.length; ++e) s.push(n[e][0], n[e][1]);

    for (s.sort(_D), o = s[s.length >> 1], l = [], f = [], u = [], e = 0; e < n.length; ++e) (g = n[e])[1] < o ? l.push(g) : o < g[0] ? f.push(g) : u.push(g);

    return v = u, c = u.slice(), v.sort(_J), c.sort(_K), new _B(o, _A(l), _A(f), v, c);
  };

  var _D = (t, i) => {
    return t - i;
  };

  var _J = (t, i) => {
    return t[0] - i[0] || t[1] - i[1];
  };

  var _K = (t, i) => {
    return t[1] - i[1] || t[0] - i[0];
  };

  var _M = (t, i) => {
    var r = t.intervals([]);
    r.push(i), _X(t, r);
  };

  var _N = (t, i, r, h, n) => {
    return "function" == typeof r ? ((t, i, r, h, n) => {
      for (var s, e = r + 1; r >= i;) 0 > n(t[s = i + r >>> 1], h) ? i = s + 1 : (e = s, r = s - 1);

      return e;
    })(t, void 0 === h ? 0 : 0 | h, void 0 === n ? t.length - 1 : 0 | n, i, r) : ((t, i, r, h) => {
      for (var n, s = r + 1; r >= i;) h > t[n = i + r >>> 1] ? i = n + 1 : (s = n, r = n - 1);

      return s;
    })(t, void 0 === r ? 0 : 0 | r, void 0 === h ? t.length - 1 : 0 | h, i);
  };

  var _O = (t, i, r, h, n) => {
    return "function" == typeof r ? ((t, i, r, h, n) => {
      for (var s, e = r + 1; r >= i;) n(t[s = i + r >>> 1], h) > 0 ? (e = s, r = s - 1) : i = s + 1;

      return e;
    })(t, void 0 === h ? 0 : 0 | h, void 0 === n ? t.length - 1 : 0 | n, i, r) : ((t, i, r, h) => {
      for (var n, s = r + 1; r >= i;) t[n = i + r >>> 1] > h ? (s = n, r = n - 1) : i = n + 1;

      return s;
    })(t, void 0 === r ? 0 : 0 | r, void 0 === h ? t.length - 1 : 0 | h, i);
  };

  var _P = (t, i, r, h, n) => {
    return "function" == typeof r ? ((t, i, r, h, n) => {
      for (var s, e = i - 1; r >= i;) 0 > n(t[s = i + r >>> 1], h) ? (e = s, i = s + 1) : r = s - 1;

      return e;
    })(t, void 0 === h ? 0 : 0 | h, void 0 === n ? t.length - 1 : 0 | n, i, r) : ((t, i, r, h) => {
      for (var n, s = i - 1; r >= i;) h > t[n = i + r >>> 1] ? (s = n, i = n + 1) : r = n - 1;

      return s;
    })(t, void 0 === r ? 0 : 0 | r, void 0 === h ? t.length - 1 : 0 | h, i);
  };

  var _Q = (t, i, r, h, n) => {
    return "function" == typeof r ? ((t, i, r, h, n) => {
      for (var s, e = i - 1; r >= i;) n(t[s = i + r >>> 1], h) > 0 ? r = s - 1 : (e = s, i = s + 1);

      return e;
    })(t, void 0 === h ? 0 : 0 | h, void 0 === n ? t.length - 1 : 0 | n, i, r) : ((t, i, r, h) => {
      for (var n, s = i - 1; r >= i;) t[n = i + r >>> 1] > h ? r = n - 1 : (s = n, i = n + 1);

      return s;
    })(t, void 0 === r ? 0 : 0 | r, void 0 === h ? t.length - 1 : 0 | h, i);
  };

  var _R = (t, i, r, h, n) => {
    return "function" == typeof r ? ((t, i, r, h, n) => {
      for (var s, e; r >= i;) {
        if (0 === (e = n(t[s = i + r >>> 1], h))) return s;
        e > 0 ? r = s - 1 : i = s + 1;
      }

      return -1;
    })(t, void 0 === h ? 0 : 0 | h, void 0 === n ? t.length - 1 : 0 | n, i, r) : ((t, i, r, h) => {
      for (; r >= i;) {
        var n = i + r >>> 1,
            s = t[n];
        if (s === h) return n;
        s > h ? r = n - 1 : i = n + 1;
      }

      return -1;
    })(t, void 0 === r ? 0 : 0 | r, void 0 === h ? t.length - 1 : 0 | h, i);
  };

  var _X = (i, r) => {
    var h = _A(r);

    i.mid = h.mid, i.left = h.left, i.right = h.right, i.leftPoints = h.leftPoints, i.rightPoints = h.rightPoints, i.count = h.count;
  };

  var _0 = i => {
    return i && 0 !== i.length ? new _1(_A(i)) : new _1(null);
  };

  var _L = {
    ge: _N,
    gt: _O,
    lt: _P,
    le: _Q,
    eq: _R
  };

  var _S = (t, i) => {
    var r = t.intervals([]),
        h = r.indexOf(i);
    return 0 > h ? 0 : (r.splice(h, 1), _X(t, r), 1);
  };

  var _T = (t, i) => {
    t.mid = i.mid, t.left = i.left, t.right = i.right, t.leftPoints = i.leftPoints, t.rightPoints = i.rightPoints, t.count = i.count;
  };

  _C.insert = _F;

  var _U = (t, i, r) => {
    var h, n;

    for (h = 0; h < t.length && t[h][0] <= i; ++h) if (n = r(t[h])) return n;
  };

  var _V = (t, i, r) => {
    var h, n;

    for (h = t.length - 1; h >= 0 && t[h][1] >= i; --h) if (n = r(t[h])) return n;
  };

  var _W = (t, i) => {
    var r, h;

    for (r = 0; r < t.length; ++r) if (h = i(t[r])) return h;
  };

  _C.remove = _G;
  _C.queryPoint = _H;
  _C.queryInterval = _I;
  _2.insert = _4;
  _2.remove = _5;
  _2.queryPoint = _6;
  _2.queryInterval = _7;
  $$0.get = _8, _$2(_2, "count", $$0);
  $$0.get = _9, _$2(_2, "intervals", $$0);
  _$0.interval = _0;
}).call(global);

var createIntervalTree = global.interval

//Create some random list of intervals
var intervals = [[1, 2], [-1, 0], [0.5, 1], [-10, 10]]

//Build tree
var tree = createIntervalTree(intervals)

//Find all intervals containing query point 0.7
console.log('querying point:', 0.7)
tree.queryPoint(0.7, function(interval) {
  console.log(interval)
})

without prepack.js

"use strict"
var bounds = (function() {
function compileSearch(funcName, predicate, reversed, extraArgs, earlyOut) {
  var code = [
    "function ", funcName, "(a,l,h,", extraArgs.join(","),  "){",
    earlyOut ? "" : "var i=", (reversed ? "l-1" : "h+1"),
    ";while(l<=h){var m=(l+h)>>>1,x=a[m]"]
  if(earlyOut) {
    if(predicate.indexOf("c") < 0) {
      code.push(";if(x===y){return m}else if(x<=y){")
    } else {
      code.push(";var p=c(x,y);if(p===0){return m}else if(p<=0){")
    }
  } else {
    code.push(";if(", predicate, "){i=m;")
  }
  if(reversed) {
    code.push("l=m+1}else{h=m-1}")
  } else {
    code.push("h=m-1}else{l=m+1}")
  }
  code.push("}")
  if(earlyOut) {
    code.push("return -1};")
  } else {
    code.push("return i};")
  }
  return code.join("")
}

function compileBoundsSearch(predicate, reversed, suffix, earlyOut) {
  var result = new Function([
  compileSearch("A", "x" + predicate + "y", reversed, ["y"], earlyOut),
  compileSearch("P", "c(x,y)" + predicate + "0", reversed, ["y", "c"], earlyOut),
"function dispatchBsearch", suffix, "(a,y,c,l,h){\
if(typeof(c)==='function'){\
return P(a,(l===void 0)?0:l|0,(h===void 0)?a.length-1:h|0,y,c)\
}else{\
return A(a,(c===void 0)?0:c|0,(l===void 0)?a.length-1:l|0,y)\
}}\
return dispatchBsearch", suffix].join(""))
  return result()
}

return {
  ge: compileBoundsSearch(">=", false,  "GE"),
  gt: compileBoundsSearch(">",  false,  "GT"),
  lt: compileBoundsSearch("<",  true,   "LT"),
  le: compileBoundsSearch("<=", true,   "LE"),
  eq: compileBoundsSearch("-",  true,   "EQ", true)
}
})();

module.exports = (function(){

var NOT_FOUND = 0
var SUCCESS = 1
var EMPTY = 2

function IntervalTreeNode(mid, left, right, leftPoints, rightPoints) {
  this.mid = mid
  this.left = left
  this.right = right
  this.leftPoints = leftPoints
  this.rightPoints = rightPoints
  this.count = (left ? left.count : 0) + (right ? right.count : 0) + leftPoints.length
}

var proto = IntervalTreeNode.prototype

function copy(a, b) {
  a.mid = b.mid
  a.left = b.left
  a.right = b.right
  a.leftPoints = b.leftPoints
  a.rightPoints = b.rightPoints
  a.count = b.count
}

function rebuild(node, intervals) {
  var ntree = createIntervalTree(intervals)
  node.mid = ntree.mid
  node.left = ntree.left
  node.right = ntree.right
  node.leftPoints = ntree.leftPoints
  node.rightPoints = ntree.rightPoints
  node.count = ntree.count
}

function rebuildWithInterval(node, interval) {
  var intervals = node.intervals([])
  intervals.push(interval)
  rebuild(node, intervals)    
}

function rebuildWithoutInterval(node, interval) {
  var intervals = node.intervals([])
  var idx = intervals.indexOf(interval)
  if(idx < 0) {
    return NOT_FOUND
  }
  intervals.splice(idx, 1)
  rebuild(node, intervals)
  return SUCCESS
}

proto.intervals = function(result) {
  result.push.apply(result, this.leftPoints)
  if(this.left) {
    this.left.intervals(result)
  }
  if(this.right) {
    this.right.intervals(result)
  }
  return result
}

proto.insert = function(interval) {
  var weight = this.count - this.leftPoints.length
  this.count += 1
  if(interval[1] < this.mid) {
    if(this.left) {
      if(4*(this.left.count+1) > 3*(weight+1)) {
        rebuildWithInterval(this, interval)
      } else {
        this.left.insert(interval)
      }
    } else {
      this.left = createIntervalTree([interval])
    }
  } else if(interval[0] > this.mid) {
    if(this.right) {
      if(4*(this.right.count+1) > 3*(weight+1)) {
        rebuildWithInterval(this, interval)
      } else {
        this.right.insert(interval)
      }
    } else {
      this.right = createIntervalTree([interval])
    }
  } else {
    var l = bounds.ge(this.leftPoints, interval, compareBegin)
    var r = bounds.ge(this.rightPoints, interval, compareEnd)
    this.leftPoints.splice(l, 0, interval)
    this.rightPoints.splice(r, 0, interval)
  }
}

proto.remove = function(interval) {
  var weight = this.count - this.leftPoints
  if(interval[1] < this.mid) {
    if(!this.left) {
      return NOT_FOUND
    }
    var rw = this.right ? this.right.count : 0
    if(4 * rw > 3 * (weight-1)) {
      return rebuildWithoutInterval(this, interval)
    }
    var r = this.left.remove(interval)
    if(r === EMPTY) {
      this.left = null
      this.count -= 1
      return SUCCESS
    } else if(r === SUCCESS) {
      this.count -= 1
    }
    return r
  } else if(interval[0] > this.mid) {
    if(!this.right) {
      return NOT_FOUND
    }
    var lw = this.left ? this.left.count : 0
    if(4 * lw > 3 * (weight-1)) {
      return rebuildWithoutInterval(this, interval)
    }
    var r = this.right.remove(interval)
    if(r === EMPTY) {
      this.right = null
      this.count -= 1
      return SUCCESS
    } else if(r === SUCCESS) {
      this.count -= 1
    }
    return r
  } else {
    if(this.count === 1) {
      if(this.leftPoints[0] === interval) {
        return EMPTY
      } else {
        return NOT_FOUND
      }
    }
    if(this.leftPoints.length === 1 && this.leftPoints[0] === interval) {
      if(this.left && this.right) {
        var p = this
        var n = this.left
        while(n.right) {
          p = n
          n = n.right
        }
        if(p === this) {
          n.right = this.right
        } else {
          var l = this.left
          var r = this.right
          p.count -= n.count
          p.right = n.left
          n.left = l
          n.right = r
        }
        copy(this, n)
        this.count = (this.left?this.left.count:0) + (this.right?this.right.count:0) + this.leftPoints.length
      } else if(this.left) {
        copy(this, this.left)
      } else {
        copy(this, this.right)
      }
      return SUCCESS
    }
    for(var l = bounds.ge(this.leftPoints, interval, compareBegin); l<this.leftPoints.length; ++l) {
      if(this.leftPoints[l][0] !== interval[0]) {
        break
      }
      if(this.leftPoints[l] === interval) {
        this.count -= 1
        this.leftPoints.splice(l, 1)
        for(var r = bounds.ge(this.rightPoints, interval, compareEnd); r<this.rightPoints.length; ++r) {
          if(this.rightPoints[r][1] !== interval[1]) {
            break
          } else if(this.rightPoints[r] === interval) {
            this.rightPoints.splice(r, 1)
            return SUCCESS
          }
        }
      }
    }
    return NOT_FOUND
  }
}

function reportLeftRange(arr, hi, cb) {
  for(var i=0; i<arr.length && arr[i][0] <= hi; ++i) {
    var r = cb(arr[i])
    if(r) { return r }
  }
}

function reportRightRange(arr, lo, cb) {
  for(var i=arr.length-1; i>=0 && arr[i][1] >= lo; --i) {
    var r = cb(arr[i])
    if(r) { return r }
  }
}

function reportRange(arr, cb) {
  for(var i=0; i<arr.length; ++i) {
    var r = cb(arr[i])
    if(r) { return r }
  }
}

proto.queryPoint = function(x, cb) {
  if(x < this.mid) {
    if(this.left) {
      var r = this.left.queryPoint(x, cb)
      if(r) { return r }
    }
    return reportLeftRange(this.leftPoints, x, cb)
  } else if(x > this.mid) {
    if(this.right) {
      var r = this.right.queryPoint(x, cb)
      if(r) { return r }
    }
    return reportRightRange(this.rightPoints, x, cb)
  } else {
    return reportRange(this.leftPoints, cb)
  }
}

proto.queryInterval = function(lo, hi, cb) {
  if(lo < this.mid && this.left) {
    var r = this.left.queryInterval(lo, hi, cb)
    if(r) { return r }
  }
  if(hi > this.mid && this.right) {
    var r = this.right.queryInterval(lo, hi, cb)
    if(r) { return r }
  }
  if(hi < this.mid) {
    return reportLeftRange(this.leftPoints, hi, cb)
  } else if(lo > this.mid) {
    return reportRightRange(this.rightPoints, lo, cb)
  } else {
    return reportRange(this.leftPoints, cb)
  }
}

function compareNumbers(a, b) {
  return a - b
}

function compareBegin(a, b) {
  var d = a[0] - b[0]
  if(d) { return d }
  return a[1] - b[1]
}

function compareEnd(a, b) {
  var d = a[1] - b[1]
  if(d) { return d }
  return a[0] - b[0]
}

function createIntervalTree(intervals) {
  if(intervals.length === 0) {
    return null
  }
  var pts = []
  for(var i=0; i<intervals.length; ++i) {
    pts.push(intervals[i][0], intervals[i][1])
  }
  pts.sort(compareNumbers)

  var mid = pts[pts.length>>1]

  var leftIntervals = []
  var rightIntervals = []
  var centerIntervals = []
  for(var i=0; i<intervals.length; ++i) {
    var s = intervals[i]
    if(s[1] < mid) {
      leftIntervals.push(s)
    } else if(mid < s[0]) {
      rightIntervals.push(s)
    } else {
      centerIntervals.push(s)
    }
  }

  //Split center intervals
  var leftPoints = centerIntervals
  var rightPoints = centerIntervals.slice()
  leftPoints.sort(compareBegin)
  rightPoints.sort(compareEnd)

  return new IntervalTreeNode(mid, 
    createIntervalTree(leftIntervals),
    createIntervalTree(rightIntervals),
    leftPoints,
    rightPoints)
}

//User friendly wrapper that makes it possible to support empty trees
function IntervalTree(root) {
  this.root = root
}

var tproto = IntervalTree.prototype

tproto.insert = function(interval) {
  if(this.root) {
    this.root.insert(interval)
  } else {
    this.root = new IntervalTreeNode(interval[0], null, null, [interval], [interval])
  }
}

tproto.remove = function(interval) {
  if(this.root) {
    var r = this.root.remove(interval)
    if(r === EMPTY) {
      this.root = null
    }
    return r !== NOT_FOUND
  }
  return false
}

tproto.queryPoint = function(p, cb) {
  if(this.root) {
    return this.root.queryPoint(p, cb)
  }
}

tproto.queryInterval = function(lo, hi, cb) {
  if(lo <= hi && this.root) {
    return this.root.queryInterval(lo, hi, cb)
  }
}

Object.defineProperty(tproto, "count", {
  get: function() {
    if(this.root) {
      return this.root.count
    }
    return 0
  }
})

Object.defineProperty(tproto, "intervals", {
  get: function() {
    if(this.root) {
      return this.root.intervals([])
    }
    return []
  }
})

function createWrapper(intervals) {
  if(!intervals || intervals.length === 0) {
    return new IntervalTree(null)
  }
  return new IntervalTree(createIntervalTree(intervals))
}
  return createWrapper
})()