avl.prototype.put = avl.prototype.insert;
avl.prototype.del = avl.prototype.remove;
avl.prototype.get = avl.prototype.find;

avl.prototype.lessThanOrEqual = function(key) {
  var compare = this._comparator;
  var subtree = this._root, cmp;

  while (subtree) {
    cmp = compare(subtree.key, key);

    // leaf node reached and is greater than key
    if (subtree.left === null && subtree.right === null && cmp > 0) return null;

    if ((cmp <= 0 && subtree.right === null) ||
        (cmp <= 0 && compare(subtree.right.key, key) > 0)) { // that's the one
      return subtree;
    }

    // if node value is greater than 'key' search in the left subtree
    if (cmp >= 0) subtree = subtree.left;
    // if node value is less than 'key' search in the right subtree
    else          subtree = subtree.right;
  }

  return subtree;
};

avl.prototype.walkRange = function(low, high, fn, ctx) {
  var Q = [];
  var node = this._root, cmp;

  while (Q.length !== 0 || node) {
    if (node) {
      Q.push(node);
      node = node.left;
    } else {
      node = Q.pop();
      cmp = compare(node.key, high);
      if (cmp > 0) {
        break;
      } else if (compare(node.key, low) >= 0) {
        if (fn.call(ctx, node)) return this; // stop if smth is returned
      }
      node = node.right;
    }
  }
  return this;
};

avl.prototype.binaryAscend = function(key, zmax) {
  var subtree = this._root, cmp, prev;
  var compare = this._comparator;

  // descend from root to find the closest node
  while (subtree) {
    prev = subtree;
    cmp = compare(key, subtree.key);
    if    (cmp === 0) { return subtree; }
    else if (cmp < 0) { subtree = subtree.left; }
    else              { subtree = subtree.right; }
  }

  // traverse left to find the enclosing key
  var node = prev, predecessor;
  // remove encoded zoom level to avoid false positives
  key = pcode(key, zmax);
  while (node) {
    if (node.key === 0) return node; // always

    cmp = compare(key, node.key);
    if (cmp === 0) return node;
    if (cmp > 0) {
      key = pcode(key, zmax);
    } else { // prev
      predecessor = node;
      if (predecessor.left) {
        predecessor = predecessor.left;
        while (predecessor && predecessor.right) {
          predecessor = predecessor.right;
        }
      } else {
        predecessor = node.parent;
        while (predecessor && predecessor.left === node) {
          node = predecessor;
          predecessor = predecessor.parent;
        }
      }
      node = predecessor;
    }
  }

  return null;
}



const equals = (a, b) => a[0] === b[0] && a[1] === b[1] && a[2] === b[2] && a[3] === b[3];
const width  = (a) => a[2] - a[0];
const height = (a) => a[3] - a[1];
const center = (a) => [(a[0] + a[2]) / 2, (a[1] + a[3] / 2)];
const corner = (a, i) => {
  switch (i) {
    case 0: return [a[2], a[3]];
    case 1: return [a[2], a[1]];
    case 2: return [a[0], a[1]];
    case 3: return [a[0], a[3]];
  }
};

const bboxContains = (a, x, y) => a[0] <= x && a[2] >= x && a[1] <= y && a[3] >= y;
const bboxIntersection = (a, b) => {
  if (b[2] < a[0] || b[0] > a[2] || b[3] < a[1] || b[1] > a[3]) return b;

  const r = b.slice();

  if (b[2] > a[2]) r[2] = a[2];
  if (b[0] < a[0]) r[0] = a[0];
  if (b[3] > a[3]) r[3] = a[3];
  if (b[1] < a[1]) r[1] = a[1];

  return r;
}

function _contains(xmin1, ymin1, xmax1, ymax1, xmin2, ymin2, xmax2, ymax2) {
  return xmin1 <= xmin2 &&
         ymin1 <= ymin2 &&
         xmax2 <= xmax1 &&
         ymax2 <= ymax1;
}

const contains = (a, b) => a[0] <= b[0] && a[1] <= b[1] && b[2] <= a[2] && b[3] <= a[3];

const intersects = (a, b) => b[0] < a[2] && b[1] < a[3] && b[2] > a[0] && b[3] > a[1];

const squarify = (b) => {
  const r = Math.max(width(b), height(b)) /2;
  const [cx, cy] = center(b);
  return [cx - r, cy - r, cx + r, cy + r];
}


const bboxSplit = ([xmin, ymin, xmax, ymax]) => {
  const nw = (xmax - xmin) / 2;
  const nh = (ymax - ymin) / 2;

  return [
    [xmin,           ymin, xmin + nw, ymin + nh],
    [xmin + nw,      ymin,      xmax, ymin + nh],
    [xmin,      ymin + nh, xmin + nw,      ymax],
    [xmin + nw, ymin + nh,      xmax,      ymax]
  ];
}

const treeGetNext = (tree, val) => {
  let node;
  tree.walkAsc(val, (a, b) => (node = b));
  return node;
};

const treeGetPrev = (tree, val) => {
  let node;
  tree.walkDesc(0, val, (a, b) => (node = b));
  return node;
};

const BITS_FOR_ZOOM = 4;
// 12 levels, 2 bits per zoom + 4 bit to store the zoom
const MAX_ZOOM      = 11;
const MIN_ZOOM      = 0;
const ZOOM_MASK     = (1 << BITS_FOR_ZOOM) - 1;

// | morton xy  | ln2(zoom) |
// | --- 28 --- | --- 4 --- |
const code = (z, x, y) => (z | (morton(x, y) << 4));
const decode = (xy, dest = []) => {
  morton.reverse(xy >> 4, dest);
  dest[2] = xy & ZOOM_MASK;
  return dest;
};

const pcode = (c, zmax) => {
  const z = (c & ZOOM_MASK) - 1;
  const shift = 2 * (zmax - z) + 4;
  return z && (z | (c >>> shift << shift));
};

const compare = (a, b) => a - b;

const _ca = [0, 0], _cb = [0, 0];
const intersect = (o, b) => {
  return o.segment ? lbclip(o[0], o[1], b, _ca, _cb) : intersects(o, b);
}

// this is super-important, it encodes the level and the position
//const code = (z, x, y) => ({ z, code: morton(x, y) });

const codeToBBox = (code, size, res) => {
  const side = size / (1 << (code & ZOOM_MASK));
  const [x, y] = morton.reverse(code >> 4);
  const tx = x * res,
        ty = y * res;
  return [tx, ty, tx + side, ty + side];
};

const MAX = Math.pow(2, 12) - 1;

/**
 * TODO: use intersection test for nodes,
 * and liang-barsky for segments
 */
class MQuadtree {

  constructor(leafCapacity = 20, levels = MAX_ZOOM, bbox = [0, 0, MAX, MAX]) {
    bbox   = squarify(bbox);
    levels = Math.min(levels, MAX_ZOOM);

    this._bbox      = bbox;
    this._zmax      = levels;
    this._leafCapacity = leafCapacity;

    this._tree = new avl(compare);

    // root leaf node
    this._tree.put(0, { code: code(0, 0, 0), bbox, objects: [], leaf: true });

    this._size = Math.max(width(bbox), height(bbox));
    this._resolution = this._size / (1 << levels);
  }


  get bbox() {
    return this._bbox;
  }


  get maxZoom() {
    return this._zmax;
  }


  get resolution() {
    return this._resolution;
  }


  insert(o) {
    const block     = this.getContainingBlock(o);
    const node      = this._tree.binaryAscend(block, this._zmax);

    if (node) { // it's a leaf
      this.insertIntoLeaf(node.data, o);
    } else { // non-leaf, descend
      this.insertIntoBlock(block, o);
    }
  }

  isLeaf(block) {
    return this._tree.get(block);
  }


  insertIntoBlock(block, o) {
    const tree       = this._tree;
    const size       = this._size;
    const zmax       = this._zmax;
    const res        = this._resolution;
    let [tx, ty, tz] = decode(block);
    let side         = size / (1 << tz);
    let quadCode     = block;
    let node, childBBox;

    const Q = bboxSplit([tx * res, ty * res, tx * res + side, ty * res + side]);

    while (childBBox = Q.pop()) {
      if (intersect(o, childBBox)) {
        side     = childBBox[2] - childBBox[0];
        tz       = Math.log2(size / side);
        quadCode = code(tz, childBBox[0] / res, childBBox[1] / res);
        node = tree.get(quadCode);
        if (node) { // leaf
          this.insertIntoLeaf(node.data, o);
        } else if (tz < zmax) { // non-leaf, split
          Q.push.apply(Q, bboxSplit(childBBox)); // DFS
        }
      }
    }
  }


  insertIntoLeaf(leaf, o) {
    leaf.objects.push(o);

    // node overflow
    if (leaf.objects.length > this._leafCapacity) {
      this.split(leaf);
    }
  }


  split(node) {
    const objects = node.objects;

    const [qx, qy, z] = decode(node.code);
    const nz = z + 1;
    const cells = (1 << (this._zmax - nz));

    if (z === this._zmax) return; // don't split

    this._tree.del(node.code); // make non-leaf by removing it

    delete node.objects;
    delete node.leaf;

    const quads = bboxSplit(node.bbox);
    for (let q = 0; q < 4; q++) {
      const childBBox = quads[q];
      // cells coding
      //   0 1 2 3
      // x 0 1 0 1
      // y 0 0 1 1
      const cellX = qx + (~~(q & 1)) * cells,
            cellY = qy + (~~(q > 1)) * cells;
      const childCode = code(nz, cellX, cellY);
      const quad = {
        code:    childCode,
        objects: [],
        bbox:    childBBox,
        leaf:    true
      };
      this._tree.put(childCode, quad); // make non-leaf

      for (let i = 0; i < objects.length; i++) {
        const o = objects[i];
        // select intersector by node type
        if (intersect(o, childBBox)) {
          this.insertIntoLeaf(quad, o);
        }
      }
    }
  }


  getContainingBlock(o) {
    const [xmin, ymin, xmax, ymax] = o;
    const size = Math.max(xmax - xmin, ymax - ymin);
    const zmax = this._zmax;
    // here here here

    let z = Math.min(zmax, ~~(Math.log2(this._size / size)));
    let side = this._size / (1 << z);
    let tx = ~~(xmin / side),
        ty = ~~(ymin / side);

    // get the tile that contains the object fully
    while (z > 0 &&  // don't break through
       (tx * side > xmin      || ty * side > ymin ||
       (tx + 1) * side < xmax || (ty + 1) * side < ymax)) {
      z -= 1;
      side  *= 2;
      tx = ~~(xmin / side);
      ty = ~~(ymin / side);
    }

    // upscale to the highest level
    const l = tx * (1 << (zmax - z));
    const b = ty * (1 << (zmax - z));

    return code(z, l, b);
  }

  query(range) {
    const result = [];
    const tree   = this._tree;
    const zmax   = this._zmax;
    const block  = this.getContainingBlock(range);
    const node   = tree.binaryAscend(block, zmax);

    if (node) { // leaf
      const objects = node.data.objects;
      for (let i = 0; i < objects.length; i++) {
        if (intersect(objects[i], range)) result.push(objects[i]);
      }
    } else { // descend
      // get all children quads using tree index
      const z     = ZOOM_MASK & block;
      const shift = (zmax - z) * 2 + 4; // 2 bits per zoom, 4 last bits for level
      const max   = block | ((1 << (shift + 4)) - 1); // fill with 1-s
      tree.walkRange(block, max, (node) => {
        if (intersects(node.data.bbox, range)) {
          const objects = node.data.objects;
          for (let i = 0; i < objects.length; i++) {
            if (intersect(objects[i], range)) result.push(objects[i]);
          }
        }
      });
    }
    return result;
  }


  eachChild(block, fn) {
    const zmax  = this._zmax;
    const z     = ZOOM_MASK & block;
    const shift = (zmax - z) * 2 + 4; // 2 bits per zoom, 4 last bits for level
    const max   = block | ((1 << (shift + 4)) - 1); // fill with 1-s

    this._tree.walkRange(block, max, fn);
    return this;
  }


  getEnclosingNode(block) {
    return this._tree.binaryAscend(block, this._zmax);
  }

  codeToBBox(c) {
    return codeToBBox(c, this._size, this._resolution);
  }
}