const POLYGON         = 0; // box
const LINESTRING      = 1; // segment
const MULTILINESTRING = 2; // for curved edges
const CURVE           = 3;

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

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

const intersect = (function() {
  const _a   = [0, 0], _b = [0, 0];
  const _ca  = [0, 0], _cb = [0, 0];
  const _box = [0,0,0,0];

  return function intersect(type, coords, b) {
    if (type === LINESTRING) {
      const [x1, y1, x2, y2] = coords;
      _a[0] = x1; _a[1] = y1;
      _b[0] = x2; _b[1] = y2;
      return lbclip(_a, _b, b);
    } else if (type === CURVE) {
      return bezierIntersect.quadBezierAABB(
        coords[0], coords[1],
        coords[2], coords[3],
        coords[4], coords[5],
        b[0], b[1], b[2], b[3]
      );
    } else if (type === MULTILINESTRING) {
      for (let i = 1; i < coords.length / 2; i += 2) {
        const x1 = coords[i - 2],
              y1 = coords[i - 1],
              x2 = coords[i + 0],
              y2 = coords[i + 1];

        _a[0] = x1; _a[1] = y1;
        _b[0] = x2; _b[1] = y2;
        if (lbclip(_a, _b, b)) return true;
      }
      return false;
    } else {
      const [x1, y1, x2, y2] = coords;
      _box[0] = x1; _box[1] = y1;
      _box[2] = x2; _box[3] = y2;
      return intersects(_box, b);
    }
  }
})();


const cover = (function() {
  const _coords = [[0, 0], [0, 0]];

  return function cover(type, coords, zoom) {
    const tileHash = {};
    const tiles    = [];

    switch (type) {
      case LINESTRING:
        _coords[0][0] = coords[0];
        _coords[0][1] = coords[1];
        _coords[1][0] = coords[2];
        _coords[1][1] = coords[3];
        coverSegment(tileHash, _coords, zoom, undefined, tiles);
        break;
      case POLYGON:
        coverAABB(tileHash,
          coords[0], coords[1],
          coords[2], coords[3],
          zoom, tiles);
        break;
      case CURVE:
        let tile;
        coverQuadBezier(tileHash, coords, zoom, tiles);
      default:
        break;
    }
    return tiles;
  };
})();


// "world" size
const toID = morton;
const wsz = 1 << 12; // MAX morton-encodable level
function pointToQuad(x, y, z) {
  var z2 = 1 << z,
      x = ~~(z2 * (x / wsz)),
      y = ~~(z2 * (y / wsz));
  return [x, y, z];
}

function pointToQuadFraction(x, y, z) {
  var z2 = 1 << z,
      x = z2 * (x / wsz),
      y = z2 * (y / wsz);
  return [x, y, z];
}

function coverAABB(tileHash, x1, y1, x2, y2, zoom, t) {
  const lb = pointToQuad(x1, y1, zoom);
  const rt = pointToQuad(x2, y2, zoom);
  for (let x = lb[0]; x <= rt[0]; x++) {
    for (let y = lb[1]; y <= rt[1]; y++) {
      //tileHash[toID(x, y, zoom)] = true;
      t.push(toID(x, y, zoom));
    }
  }
}

function coverSegment(tileHash, coords, maxZoom, ring, t) {
  var prevX, prevY;

  for (var i = 0; i < coords.length - 1; i++) {
    var start = pointToQuadFraction(coords[i][0], coords[i][1], maxZoom),
        stop = pointToQuadFraction(coords[i + 1][0], coords[i + 1][1], maxZoom),
        x0 = start[0],
        y0 = start[1],
        x1 = stop[0],
        y1 = stop[1],
        dx = x1 - x0,
        dy = y1 - y0;

    if (dy === 0 && dx === 0) continue;

    var sx = dx > 0 ? 1 : -1,
        sy = dy > 0 ? 1 : -1,
        x = Math.floor(x0),
        y = Math.floor(y0),
        tMaxX = dx === 0 ? Infinity : Math.abs(((dx > 0 ? 1 : 0) + x - x0) / dx),
        tMaxY = dy === 0 ? Infinity : Math.abs(((dy > 0 ? 1 : 0) + y - y0) / dy),
        tdx = Math.abs(sx / dx),
        tdy = Math.abs(sy / dy);

    if (x !== prevX || y !== prevY) {
      //tileHash[toID(x, y, maxZoom)] = true;
      t.push(toID(x, y, maxZoom));
      if (ring && y !== prevY) ring.push([x, y]);
      prevX = x;
      prevY = y;
    }

    while (tMaxX < 1 || tMaxY < 1) {
      if (tMaxX < tMaxY) {
        tMaxX += tdx;
        x += sx;
      } else {
        tMaxY += tdy;
        y += sy;
      }
      //tileHash[toID(x, y, maxZoom)] = true;
      t.push(toID(x, y, maxZoom));
      if (ring && y !== prevY) ring.push([x, y]);
      prevX = x;
      prevY = y;
    }
  }

  if (ring && y === ring[0][1]) ring.pop();
}

function coverQuadBezier(tileHash, coords, zoom, tiles) {
  const [x0, y0] = pointToQuad(coords[0], coords[1], zoom);
  const [x1, y1] = pointToQuad(coords[2], coords[3], zoom);
  const [x2, y2] = pointToQuad(coords[4], coords[5], zoom);
  bresenham.quadBezierAA(x0, y0, x1, y1, x2, y2, (x, y) => {
    tiles.push(toID(x, y, zoom));
  });
}


const zEncode = morton;

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;

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_

    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_;

    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;
}


const getQuadraticControlPoint = (x1, y1, x2, y2, cx = 2, cy = 1.5, dest = { x: 0, y: 0}) => {
  dest.x = (x1 + x2) / cx + (y2 - y1) / cy;
  dest.y = (y1 + y2) / cx + (x1 - x2) / cy;

  return dest;
}


const getGeometry = (function() {
  const geom = [];
  const _cp = { x: 0, y: 0 };
  const output = {
    type:        0,
    coordinates: geom
  };

  return (id) => {
    const pos   = id * SZ;
    const type  = flatStorage[pos + SZ - 1];;
    output.type = type;

    if (type === CURVE) {
      const s = SZ * flatStorage[pos + 0];
      const t = SZ * flatStorage[pos + 1];
      const curvature = flatStorage[pos + 2];

      const sx = (flatStorage[s + 0] + flatStorage[s + 2]) / 2;
      const sy = (flatStorage[s + 1] + flatStorage[s + 3]) / 2;
      const tx = (flatStorage[t + 0] + flatStorage[t + 2]) / 2;
      const ty = (flatStorage[t + 1] + flatStorage[t + 3]) / 2;

      getQuadraticControlPoint(sx, sy, tx, ty, 2, 1.5, _cp);

      geom[0] = sx;
      geom[1] = sy;
      geom[2] = _cp.x;
      geom[3] = _cp.y;
      geom[4] = tx;
      geom[5] = ty;

      // get control point
    } else if (type === LINESTRING) {
      const s = SZ * flatStorage[pos + 0];
      const t = SZ * flatStorage[pos + 1];

      geom[0] = (flatStorage[s + 0] + flatStorage[s + 2]) / 2;
      geom[1] = (flatStorage[s + 1] + flatStorage[s + 3]) / 2;
      geom[2] = (flatStorage[t + 0] + flatStorage[t + 2]) / 2;
      geom[3] = (flatStorage[t + 1] + flatStorage[t + 3]) / 2;
    } else {
      geom[0] = flatStorage[pos + 0];
      geom[1] = flatStorage[pos + 1];
      geom[2] = flatStorage[pos + 2];
      geom[3] = flatStorage[pos + 3];
    }
    return output;
  };
})();


const MAX_ZOOM = 12;


class UBTree {

  constructor (zoom = 10) {
    this.setLevel(zoom);
    this._tree  = new SplayTree((a, b) => a - b);
    this._reverseIndex = [];

    this._checkedNodes = [];
  }

  // Node must have x and y integers
  insert (id) {
    const object = getGeometry(id);
    //const pos = id * SZ;
    const tiles = cover(object.type, object.coordinates, this._level);
    const nodes = this._reverseIndex[id] = [];
    for (let i = 0; i < tiles.length; i++) {
      //const t    = tiles[i];
      const code = tiles[i];
      let node = this._tree.find(code);
      if (node) {
        node.data.push(id);
      } else {
        node = this._tree.insert(code, [id]);
      }
      //const code = morton(t[0], t[1]);
      nodes.push(node);
    }
  }

  remove(id) {
    var quads = this._reverseIndex[id];
    if (quads) {
      for (let i = 0; i < quads.length; i++) {
        var quad = quads[i];
        var ids = quad.data;
        ids.splice(ids.indexOf(id), 1);
        if (ids.length === 0) {
          this._tree.removeNode(quad);
        }
      }
      delete this._reverseIndex[id];
    }
  }

  update(id) {
    this.remove(id);
    this.insert(id);
  }

  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));
  }

  clear() {
    this._tree._root = null;
    this._tree._size = 0;
    this._reverseIndex = [];
  }

  setLevel(level) {
    this._level = level;
  }

  searchNode(node, minz, maxz, range, z1, z2, res) {
    var Q = [node];
    while (node = Q.pop()) {
      var z = node.key;
      if (z < minz) {
        Q.push(node.right);
        continue;
      } else if (z > maxz) {
        Q.push(node.left);
        continue;
      } else {
        var ids = node.data;
        var inside = false;

        if (this._checkedNodesHash[node.key]) continue;

        this._checkedNodesHash[node.key] = true;
        this._checkedNodes.push(node);
        for (let i = 0; i < ids.length; i++) {
          var id = ids[i];
          var object = getGeometry(id);
          var oinside = intersect(object.type, object.coordinates, range);
          this._intersectionChecks++;
          if (oinside) {
            res.push(id);
            inside = true;
          }
        }

        if (inside) { // range is good
          this.searchNode(node.left, minz, z, range, z1, z2, res);
          this.searchNode(node.right, z, maxz, range, z1, z2, res);
        } else {      // split range
          this.searchNode(node.left, minz, litMax(z1, z2, z), range, z1, z2, res);
          this.searchNode(node.right, bigMin(z1, z2, z), maxz, range, z1, z2, res);
        }
      }
    }
  }

  query(range) {
    range[0] |= 0;
    range[1] |= 0;
    range[2] |= 0;
    range[3] |= 0;

    const tile1 = pointToQuadFraction(range[0], range[1], this._level);
    const tile2 = pointToQuadFraction(range[2], range[3], this._level);

    const z1 = morton(tile1[0], tile1[1]);
    const z2 = morton(tile2[0], tile2[1]);

    const res = [];

    this._intersectionChecks = 0;
    this._checkedNodes = [];
    this._checkedNodesHash = {};
    this.searchNode(this._tree._root, z1, z2, range, z1, z2, res);

    return res;
  }

  get intersectionChecks() {
    return this._intersectionChecks;
  }

  get cellCount() {
    return this._tree.size;
  }

  get level () {
    return this._level;
  }

  get size () {
    return this._tree.size;
  }

  keyToBBox(key) {
    const [tx, ty] = morton.reverse(key);
    const side = 1 << (MAX_ZOOM - this._level);
    return [tx * side, ty * side, (tx + 1) * side, (ty + 1) * side];
  }
}

UBTree.MAX_ZOOM = MAX_ZOOM;