var QT_ROOT_LEVEL = 0;

function createNode(bbox, parent, level) {
  return {
    bbox,
    leaf: true,
    level, parent,
    objects:  [],
    final:    false
  };
}


function inside (box, container) {
  var cx = (box[0] + box[2]) / 2;
  var cy = (box[1] + box[3]) / 2;

  return cx >= container[0] && cx < container[2] &&
         cy >= container[1] && cy < container[3];
}


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


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


const LEFT_BOTTOM  = 0;
const LEFT_TOP     = 1;
const RIGHT_TOP    = 2;
const RIGHT_BOTTOM = 3;


function findQuad (bbox, nbbox) {
  var ncx = (nbbox[0] + nbbox[2]) / 2, ncy = (nbbox[1] + nbbox[3]) / 2;
  var cx  = (bbox[0]  + bbox[2])  / 2, cy  = (bbox[1]  + bbox[3])  / 2;

  if (cx < ncx) return cy < ncy ? LEFT_BOTTOM  : LEFT_TOP;
  else          return cy < ncy ? RIGHT_BOTTOM : RIGHT_TOP;
}


const INF_BBOX = [-Number.MAX_VALUE, -Number.MAX_VALUE,
                   Number.MAX_VALUE,  Number.MAX_VALUE];


function scale (bbox, k) {
  var cx = (bbox[0] + bbox[2]) / 2,
      cy = (bbox[1] + bbox[3]) / 2;
  var w = Math.abs(bbox[2] - bbox[0]),
      h = Math.abs(bbox[3] - bbox[1]);

  k /= 2;

  return [cx - w * k, cy - h * k, cx + w * k, cy + h * k];
}


function grow (bbox, other) {
  var w = Math.abs(bbox[2] - bbox[0]),
      h = Math.abs(bbox[3] - bbox[1]);
  return [bbox[0] + w * 2, bbox[1] + h * 2]
}


const DEF_GET_BBOX = (o) => o;


class Quadtree {

  constructor (getBBox = DEF_GET_BBOX, nodeCapacity = 10, initialBbox, getId) {
    this._nodeCapacity = nodeCapacity;
    this._root     = null;
    this._getBBox  = getBBox;
    this._upScale  = 4;

    this._objects  = {};
    this._size     = 0;
    this._idToCell = {};

    if (initialBbox) this._root = createNode(initialBbox, null, QT_ROOT_LEVEL);
  }


  insert (id, bbox, root = this._root) {
    bbox = bbox || this._getBBox(id);

    if (this._objects[id]) return;

    this._objects[id] = true;

    if (!this._root) {
      var size = Math.max(
        Math.abs(bbox[2] - bbox[0]),
        Math.abs(bbox[3] - bbox[1])
      );
      this._root = createNode([bbox[0], bbox[1], bbox[0] + size, bbox[1] + size], QT_ROOT_LEVEL);
      this._root.objects.push(id);
      return id;
    }

    var Q = [root], node, nbbox, inserted = false;
    var nodeCapacity = this._nodeCapacity, idToCell = this._idToCell;

    while (node = Q.pop()) {
      nbbox = node.bbox;
      if (overlaps(bbox, nbbox)) {
        if (node.leaf) {
          if (node.final || (node.objects.length < nodeCapacity)) {
            node.objects.push(id);
            if (idToCell[id]) idToCell[id].push(node);
            else idToCell[id] = [node];
            if (Math.abs(nbbox[2] - nbbox[0]) <= Math.abs(bbox[2] - bbox[0]) ||
                Math.abs(nbbox[3] - nbbox[1]) <= Math.abs(bbox[3] - bbox[1])) {
              node.final = true;
            }
            inserted = true;
            //return node;
          } else {
            this.splitNode(node);
            Q.push.apply(Q, node.children);
            // this would work if we would only insert objects into 1 leaf
            // Q.push(node.children[findQuad(bbox, nbbox)]);
          }
        } else Q.push.apply(Q, node.children);
        //} else Q.push(node.children[findQuad(bbox, nbbox)]);
      }
    }

    if (inserted) return id;

    if (!inside(bbox, this._root.bbox)) {
      var level = QT_ROOT_LEVEL;
      // if we are here, we need to grow the root
      while (!inside(bbox, this._root.bbox)) {
        root = this._root;
        nbbox = root.bbox;
        var cx = (bbox[0] + bbox[2]) / 2,
            cy = (bbox[1] + bbox[3]) / 2;

        var newbbox = nbbox.slice(), newRoot;
        var nw = Math.abs(nbbox[2] - nbbox[0]),
            nh = Math.abs(nbbox[3] - nbbox[1]);

        if (cx <= nbbox[0]) newbbox[0] -= nw;
        if (cy <= nbbox[1]) newbbox[1] -= nh;
        if (cx >  nbbox[0]) newbbox[2] += nw;
        if (cy >  nbbox[1]) newbbox[3] += nh;

        newRoot = createNode(newbbox, null, level);
        this.splitNode(newRoot);
        newRoot.children[findQuad(nbbox, newbbox)] = root;
        this._root = root.parent = newRoot;
      }


      Q = [this._root];
      this._root.level = QT_ROOT_LEVEL;
      while (node = Q.shift()) {
        if (!node.leaf) {
          for (var i = 0; i < 4; i++) {
            var child = node.children[i];
            child.level = node.level + 1;
            Q.push(child);
          }
        }
      }
    }

    node = this._root.children[findQuad(bbox, this._root.bbox)];
    if (node.leaf) {
      node.objects.push(id);
      if (idToCell[id]) idToCell[id].push(node);
      else idToCell[id] = [node];
    }
    return id;
  }


  removeById(id) {
    if (!this._objects[id]) return id;
    var leafs    = this._idToCell[id];

    for (var j = 0; j < leafs.length; j++) {
      var leaf = leafs[j];
      var objects = leaf.objects;
      for (var i = 0, len = objects.length; i< len; i++) {
        if (objects[i] === id) {
          objects.splice(i, 1);
          break;
        }
      }
    }

    delete this._objects[id];
    delete this._idToCell[id];

    return id;
  }


  remove (id) {
    var bbox = this._getBBox(id);
    var Q = [this._root], node;
    var nbbox, leaf, emptyLeafs;

    while (node = Q.pop()) {
      nbbox = node.bbox;

      if (overlaps(bbox, nbbox)) {
        if (node.leaf) {
          var objects = node.objects;

          for (var i = 0, len = objects.length; i < len; i++) {
            if (objects[i] === id) {
              objects.splice(i, 1);

              if (len === 1) { // it was the last object
                emptyLeafs = emptyLeafs || [];
                emptyLeafs.push(node);
              }
              break;
            }
          }
        } else Q.push.apply(Q, node.children);
      }
    }

    delete this._idToCell[id];
    delete this._objects[id];

    // prune the tree - balancing
    if (emptyLeafs) {
      while (leaf = emptyLeafs.pop()) {
        let p = leaf.parent;
        var allEmpty = true;

        while (p && allEmpty) {
          if (!p.leaf) {
            for (let i = 0; i < 4; i++) {
              node = p.children[i];

              // found a branch or a non-empty leaf on that level, bail out
              if (!node.leaf || node.objects.length !== 0) {
                allEmpty = false;
                break;
              }
            }

            if (allEmpty) { // this node is completely empty
              p.leaf     = true;
              p.children = null;
              p.objects  = [];
            }
          }

          p = p.parent;
        }
      }
    }

    return id;
  }


  splitNode(node) {
    var [l, b, r, t] = node.bbox;
    var cx = (l + r) / 2, cy = (b + t) / 2;
    var level = node.level + 1, child;
    var idToCell = this._idToCell;

    //  ---------
    //  | 1 | 2 |
    //  --------
    //  | 0 | 3 |
    //  ---------
    //  bitwise
    //  -----------
    //  | 01 | 10 |
    //  -----------
    //  | 00 | 11 |
    //  -----------
    var children = [
      createNode([l,   b, cx, cy], node, level),
      createNode([l,  cy, cx,  t], node, level),
      createNode([cx, cy,  r,  t], node, level),
      createNode([cx,  b,  r, cy], node, level)
    ];

    // re-insert objects
    if (node.objects) {
      var objects = node.objects;
      var getBBox = this._getBBox;
      for (var i = 0, len = objects.length; i < len; i++) {
        var id   = objects[i];
        var bbox = getBBox(id);
        var row  = idToCell[id];

        for (var j = 0; j < 4; j++) {
          child = children[j];
          if (overlaps(bbox, child.bbox)) {
            child.objects.push(id);
            if (row) row.push(child);
            else     row = [child]
          }
        }
        // var index = findQuad(getBBox(objects[i]), node.bbox);
        // var child = children[index];
        // var id = objects[i];
        // child.objects.push(id);

        row.splice(row.indexOf(node), 1);

        // var row = idToCell[id];
        // if (row) {
        //   row.push(child);
        //   row.splice(row.indexOf(node), 1);
        // } else idToCell[id] = [child];
      }
    }

    node.children = children;
    node.objects  = null;
    node.leaf     = false;
  }


  point (p, returnCandidates) {
    return this.query([p[0], p[1], p[0], p[1]]);
    var result = [];
    var Q = [this._root], node, bbox, obj;
    var [x, y] = p;
    var getBBox = this._getBBox;

    while (node = Q.pop()) {
      bbox = node.bbox;
      if (x >= bbox[0] && x <= bbox[2] && y >= bbox[1] && y <= bbox[3]) {
        if (node.leaf) {

          if (returnCandidates) result = node.objects;

          var objects = node.objects;
          for (var i = 0, len = objects.length; i < len; i++) {
            obj = objects[i];
            bbox = getBBox(obj);
            if (x >= bbox[0] && x <= bbox[2] &&
                y >= bbox[1] && y <= bbox[3]) result.push(obj);
          }
          break;
        }
        else Q.push.apply(Q, node.children);
      }
    }
    return result;
  }


  neigbours (p) {
    var result = [];
    var Q = [this._root], node, bbox;
    var [x, y] = p;
    var getBBox = this._getBBox;

    while (node = Q.pop()) {
      bbox = node.bbox;
      if (x >= bbox[0] && x <= bbox[2] && y >= bbox[1] && y <= bbox[3]) {
        if (node.leaf) {
          result = node.objects;
          break;
        }
        else Q.push.apply(Q, node.children);
      }
    }
    return result;
  }


  query (range) {
    var result = [];
    var Q = [this._root], node, obj, box, id;
    var getBBox = this._getBBox;
    var map = {};

    while (node = Q.pop()) {
      if (overlaps(range, node.bbox)) {
        if (node.leaf) {
          var objects = node.objects;
          for (var i = 0, len = objects.length; i < len; i++) {
            id = objects[i];
            if (!map[id]) {
              box = getBBox(id);
              if (overlaps(range, box)) result.push(id);
              map[id] = true;
            }
          }
        } else Q.push.apply(Q, node.children);
      }
    }
    return result;
  }


  getOverlaps () {
    var Q = [this._root], node, u, v;
    var overlapping = [];
    var getBBox = this._getBBox;

    var map = {}, storage = this._objects;

    while (node = Q.pop()) {
      if (node.leaf) {
        var objects = node.objects, len = objects.length;
        for (var i = 0; i < len; i++) {
          for (var j = 0; j < len; j++) {
            u = objects[i]; v = objects[j];

            if (i !== j && !map[u + ':' + v] && !map[v + ':' + u]) {
              var a = storage[u], b = storage[v];
              map[u + ':' + v] = true;

              if (overlaps(getBBox(a), getBBox(b))) overlapping.push(a, b);
            }
          }
        }
      } else Q.push.apply(Q, node.children);
    }
    return overlapping;
  }


  getAll () {
    return Object.keys(this._objects);
  }


  forEach (fn, ctx) {
    var Q = [], node;

    while (node = Q.pop()) {
      if (node.leaf) {
        for (var i = 0, len = node.objects.length; i < len; i++) {
          fn.call(ctx, node.objects[i]);
        }
      } else Q.push.apply(Q, node.children);
    }

    return this;
  }

  getLeafs() {
    var Q = [this._root], node, leafs = [];

    while (node = Q.pop()) {
      if (node.leaf) leafs.push(node);
      else Q.push.apply(Q, node.children);
    }
    return leafs;
  }
}