function overlaps (a, b) {
  return (a[3] >= b[1] && a[1] <= b[3]) &&
         (a[2] >= b[0] && a[0] <= b[2]);
}

const _000_ = 0,
      _001_ = 1,
      _010_ = 2,
      _011_ = 3,
      _100_ = 4,
      _101_ = 5;

const MASK = 0xaaaaaaaa; // hex(int('10'*10, 2))

const FULL = 0xffffffff

const BITMAX = 31;

const zEncode = morton;

function setbits(p, v) {
  var mask = (MASK >>> (BITMAX-p)) & (~(FULL << p) & FULL);
  return (v | mask) & ~(1 << p) & FULL;
}

function unsetbits(p, v) {
  var mask = ~(MASK >>> (BITMAX-p)) & FULL;
  return (v & mask) | (1 << p);
}

function litMax(minz, maxz, zcode) {
  var litmax = minz;
  for (var p = BITMAX; p > 0; p--) {
    var mask = 1 << p;
    var v = (zcode & mask) && _100_ || _000_;
    if (minz & mask) v |= _010_
    if (maxz & mask) v |= _001_

    // console.log(["cl",p,v,minz,maxz,litmax])

    if (v === _001_)      maxz = setbits(p, maxz);
    else if (v === _011_) return litmax;
    else if (v === _100_) return maxz;
    else if (v === _101_) {
      litmax = setbits(p, maxz);
      minz   = unsetbits(p, minz);
    }
  }

  return litmax;
}

function bigMin(minz, maxz, zcode) {
  var bigmin = maxz;
  for (var p = BITMAX; p > 0; p--) {
    var mask = 1 << p;
    var v = (zcode & mask) && _100_ || _000_;
    if (minz & mask) v |= _010_;
    if (maxz & mask) v |= _001_;

    // console.log(["cb",p,v,minz,maxz,bigmin])

    if (v === _001_) {
      bigmin = unsetbits(p, minz);
      maxz   = setbits(p, maxz);
    } else if (v === _011_) return minz;
      else if (v === _100_) return bigmin;
      else if (v === _101_) minz = unsetbits(p, minz);
  }
  return bigmin;
}


class UBTree {

  constructor () {
    this._tree = new avl((a, b) => a.zcode - b.zcode);
  }

  // Node must have x and y integers
  insert (entity) {
    entity.zcode = entity.bbox ?
      zEncode(
        (entity.bbox[2] + entity.bbox[0]) / 2,
        (entity.bbox[3] + entity.bbox[1]) / 2
      ) :
      zEncode(entity.x|0, entity.y|0);
    this._tree.insert(entity);
  }

  remove(entity) {
    this._tree.remove(entity);
  }

  forEach(callback) {
    this._tree.forEach(callback);
  }

  all() {
    var all = [];
    this._tree.forEach((entity) => all.push(entity));
    return all;
  }

  load(arr) {
    arr.forEach((entity) => this.insert(entity));
  }

  searchNode(node, minz, maxz, x1, y1, x2, y2, z1, z2, res) {
    if (!node) return;
    var z = node.key.zcode;
    if (z < minz) return this.searchNode(node.right, minz, maxz, x1, y1, x2, y2, z1, z2, res);
    if (z > maxz) return this.searchNode(node.left, minz, maxz, x1, y1, x2, y2, z1, z2, res);

    // This can be simplified with fail-first
    var inside = false;
    if (node.key.bbox) {
      inside = overlaps(node.key.bbox, [x1, y1, x2, y2]);
    } else {
      var { x, y } = node.key;
      inside = (x1 <= x && x <= x2 && y1 <= y && y <= y2);
    }

    if (inside) {
      //this.searchNode(node.left, minz, z, x1, y1, x2, y2, z1, z2, res);
      res.push(node.key);
      Q.push(node.left, node.right);
      //this.searchNode(node.right, z, maxz, x1, y1, x2, y2, z1, z2, res);
    } else {
      minz = bigMin(z1, z2, z);
      maxz = litMax(z1, z2, z);
      Q.push(node.left, node.right);
      this.searchNode(node.left, minz, litMax(z1, z2, z), x1, y1, x2, y2, z1, z2, res);
      this.searchNode(node.right, bigMin(z1, z2, z), maxz, x1, y1, x2, y2, z1, z2, res);
    }
  }

  searchSemiRecursive(node, minz, maxz, x1, y1, x2, y2, z1, z2, res) {
    var Q = [node];
    while (node = Q.pop()) {
      var z = node.key.zcode;
      if (z < minz) {
        Q.push(node.right);
        continue;
      } else if (z > maxz) {
        Q.push(node.left);
        continue;
      } else {
        var inside = false;
        if (node.key.bbox) {
          inside = overlaps(node.key.bbox, [x1, y1, x2, y2]);
        } else {
          var { x, y } = node.key;
          inside = (x1 <= x && x <= x2 && y1 <= y && y <= y2);
        }

        if (inside) {
          res.push(node.key);
          this.searchSemiRecursive(node.left, minz, z, x1, y1, x2, y2, z1, z2, res);
          this.searchSemiRecursive(node.right, z, maxz, x1, y1, x2, y2, z1, z2, res);
        } else {
          this.searchSemiRecursive(node.left, minz, litMax(z1, z2, z), x1, y1, x2, y2, z1, z2, res);
          this.searchSemiRecursive(node.right, bigMin(z1, z2, z), maxz, x1, y1, x2, y2, z1, z2, res);
        }
      }
    }
  }

  search(x1, y1, x2, y2) {
    x1 |= 0;
    y1 |= 0;
    x2 |= 0;
    y2 |= 0;

    var z1 = zEncode(x1, y1);
    var z2 = zEncode(x2, y2);

    var res = [];

    //this.searchNode(this._tree._root, z1, z2, x1, y1, x2, y2, z1, z2, res);
    this.searchSemiRecursive(this._tree._root, z1, z2, x1, y1, x2, y2, z1, z2, res);

    return res;
  }
}

function testUB() {
  var tree = new UBTree();
  for (var x = 0; x < 9; x++) {
    for (var y = 0; y < 17; y++) {
      tree.insert ({ x, y });
    }
  }

  tree.insert({ bbox: [2, 6, 4, 7] });
  tree.insert({ bbox: [0, 2, 3, 4] });

  tree.forEach (d => console.log(d.key, d));

  var zmin = zEncode(3, 5);
  var zmax = zEncode(5, 10);
  var z = 58;

  console.log('search', tree.search(3, 5, 5, 10, console.log))
  console.log('litmax', litMax(zmin, zmax, z))
  console.log('bigmin', bigMin(zmin, zmax, z))
}