const screenWidth  = document.documentElement.clientWidth;
const screenHeight = document.documentElement.clientHeight;

const pxRatio = window.devicePixelRatio;

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');

const w = canvas.width = screenWidth * devicePixelRatio;
const h = canvas.height = screenHeight * devicePixelRatio;

canvas.style.width  = screenWidth + 'px';
canvas.style.height = screenHeight + 'px';


function scaleGraphToFitBounds(G, bounds) {
  var min = Math.min, max = Math.max;
  var bbox = getBounds(G);
  var cx = (bounds[0] + bounds[2]) / 2,
      cy = (bounds[1] + bounds[3]) / 2,
      gcx = (bbox[0] + bbox[2]) / 2,
      gcy = (bbox[1] + bbox[3]) / 2;

  var tx = cx - gcx,
      ty = cy - gcy;

  var scale = min(
    (bounds[2] - bounds[0]) / (bbox[2] - bbox[0]),
    (bounds[3] - bounds[1]) / (bbox[3] - bbox[1])
  );


  G.nodes.forEach(function (n) {
    n.x = cx + ((n.x + tx) - cx) * scale;
    n.y = cy + ((n.y + ty) - cy) * scale;
  });
}

function getBounds(g) {
  return g.nodes.reduce((b, n) => {
    b[0] = Math.min(b[0], n.x);
    b[1] = Math.min(b[1], n.y);
    b[2] = Math.max(b[2], n.x);
    b[3] = Math.max(b[3], n.y);
    return b;
  }, [Infinity, Infinity, -Infinity, -Infinity]);
}


function generateDenseTree(N = 550, width = 1000, height = 1000) {
  let counter = 0;
  return {
    nodes: new Array(N).fill(0).map(function(_, i) {
      counter++;
      return {
        id: i,
        text: 'Node #' + i,
        x: Math.random() * width,
        y: Math.random() * height,
        r: 3 + Math.random() * 8
      };
    }),
    edges: new Array(N - 1).fill(0).map(function(_, i) {
      counter++;
      return {
        id: i,
        source: Math.floor(Math.sqrt(i)),
        target: i + 1
      };
    })
  };
}

const data = generateDenseTree(2000, w, h);
const nodesMap = data.nodes.reduce((a, n) => {
  a[n.id] = n;
  return a;
}, {});
const visualQuads = [];
let selectedNode = null;
let selectedQuad = null;
let foundNodes = [];
let foundEdges = [];


const segmentBounds = (e) => {
  const s = nodesMap[e.source],
        t = nodesMap[e.target];

  let xmin, xmax, ymin, ymax;

  if (s.x < t.x) {
    xmin = s.x; xmax = t.x;
  } else {
    xmax = s.x; xmin = t.x;
  }

  if (s.y < t.y) {
    ymin = s.y; ymax = t.y;
  } else {
    ymax = s.y; ymin = t.y;
  }

  return [xmin, ymin, xmax, ymax];
};

const index = () => {
  const { nodes, edges } = data;
  const hashes = [];

  nodes.forEach(n => {
    const { x, y, r } = n;
    hashes.push(
      jointPrefix(
        hash(x - r, y - r),
        hash(x + r, y + r)
      ).value);
  });

  // edges.forEach((e) => {
  //   const s = nodesMap[e.source],
  //         t = nodesMap[e.target];
  //   hashes.push(
  //     jointPrefix(
  //       hash(s.x, s.y),
  //       hash(t.x, t.y)
  //     ).value
  //   );
  //   const b = segmentBounds(e);
  //   console.log(b, hashes[hashes.length - 1], boxHash(b))
  // });

  const map = {};
  return hashes.reduce((a, h) => {
    if (!map[h]) {
      a.push(h);
      map[h] = 1;
    }
    return a;
  }, []);
}

const qBounds = [0, 0, 0, 0];

const H = 24;

const hash   = (x, y) => hilbert.encode(H, [x, y]);
const unhash = (h) => hilbert.decode(H, h);

const boxHash = ([minx, miny, maxx, maxy]) => {
  const prime = 31;
  let rx = 1, ry = 1, r = 1;

  rx = rx * prime + (maxx ^ (maxx >>> 32));
  rx = rx * prime + (minx ^ (minx >>> 32));

  ry = ry * prime + (maxy ^ (maxy >>> 32));
  ry = ry * prime + (miny ^ (miny >>> 32));

  r = r * prime + rx;
  r = r * prime + ry;

  return r;
}

const jointPrefix = (h1, h2) => {
  if (!h1 || !h2) return 0;

  let or     = h1 ^ h2;
  let mask   = 1;

  let max = Math.max(h1, h2);
  let msb = 0;
  while (max) { mask <<= 1; max >>= 1; msb++; }
  let offset = msb - 1;
  while ((or & mask) === 0) {
    mask >>= 1;
    offset--;
  }

  return { offset, value: (h2 >> offset) << offset };

  // more naive
  // let value = 0;
  // let offset = H;

  // for (i = 0; i < H; i++) {
  //   let mask = 1 << (H - 1 - i);
  //   if ((h1 & mask) !== (h2 & mask)) break;
  //   value |= h1 & mask;
  //   offset--;
  // }

  // return { value, offset };
}

const getPrefixes = (bbox) => {

}

function render() {
  ctx.clearRect(0, 0, w, h);

  ctx.strokeStyle = 'brown';
  ctx.beginPath();
  visualQuads.forEach(q => {
    ctx.rect(q[0], q[1], q[2] - q[0], q[3] - q[1]);
  });
  ctx.stroke();

  const { nodes, edges } = data;

  // edges
  ctx.beginPath();
  ctx.strokeStyle = '#707070';
  edges.forEach((e) => {
    const s = nodesMap[e.source],
          t = nodesMap[e.target];
    ctx.moveTo(s.x, s.y);
    ctx.lineTo(t.x, t.y);
  });
  ctx.stroke();
  ctx.closePath();

  // highlighted edges
  ctx.beginPath();
  ctx.fillStyle   = 'red';
  ctx.strokeStyle = '#505050';
  ctx.lineWidth = 3;
  foundEdges.forEach((e) => {
    const s = nodesMap[e.source],
          t = nodesMap[e.target];
    ctx.moveTo(s.x, s.y);
    ctx.lineTo(t.x, t.y);
  });
  ctx.stroke();
  ctx.fill();

  // nodes;
  ctx.beginPath();
  ctx.fillStyle   = 'orange';
  ctx.strokeStyle = '#333333';
  ctx.lineWidth = 1;
  nodes.forEach((n) => {
    ctx.moveTo(n.x + n.r, n.y);
    ctx.arc(n.x, n.y, n.r, 0, 2 * Math.PI, false);
  });
  ctx.stroke();
  ctx.fill();

  if (selectedNode) {
    ctx.beginPath();
    ctx.fillStyle   = 'red';
    ctx.strokeStyle = '#333333';
    ctx.moveTo(selectedNode.x + selectedNode.r, selectedNode.y);
    ctx.arc(selectedNode.x, selectedNode.y, selectedNode.r, 0, 2 * Math.PI, false);
    ctx.stroke();
    ctx.fill();
  }

  if (selectedQuad) {
    ctx.beginPath();
    ctx.strokeStyle = 'green';
    ctx.lineWidth = 3;
    ctx.rect(selectedQuad[0], selectedQuad[1],
      selectedQuad[2] - selectedQuad[0],
      selectedQuad[3] - selectedQuad[1]);
    ctx.closePath();
    ctx.stroke();
  }

  ctx.beginPath();
  ctx.fillStyle   = 'red';
  ctx.strokeStyle = '#333333';
  ctx.lineWidth = 15;
  foundNodes.forEach((n) => {
    ctx.moveTo(n.x + n.r, n.y);
    ctx.arc(n.x, n.y, n.r, 0, 2 * Math.PI, false);
  });
  ctx.stroke();
  ctx.fill();

  ctx.lineWidth = 1;
  // query
  ctx.beginPath();
  ctx.strokeStyle = 'brown';
  ctx.rect(qBounds[0], qBounds[1], qBounds[2] - qBounds[0], qBounds[3] - qBounds[1]);
  ctx.stroke();
}

function getRandomColor() {
  const letters = '0123456789ABCDEF';
  let color = '#';
  for (var i = 0; i < 6; i++) {
    color += letters[Math.floor(Math.random() * 16)];
  }
  return color;
}

function drawTree() {
  Q._tree.values().forEach(({ bbox }) => {
    ctx.beginPath();
    ctx.strokeStyle = 'green';
    ctx.lineWidth = 1;
    ctx.fillStyle = getRandomColor();
    ctx.globalAlpha = 0.5;
    ctx.rect(bbox[0], bbox[1],
      bbox[2] - bbox[0],
      bbox[3] - bbox[1]);
    ctx.closePath();
    ctx.fill();
    ctx.stroke();
  });
  ctx.globalAlpha = 1;
}

function storeFound(rec) {
  (rec.segment ? foundEdges : foundNodes).push(rec.n);
}

canvas.addEventListener('mousemove', ({ clientX, clientY }) => {
  const x = clientX * pxRatio;
  const y = clientY * pxRatio;

  const offset = 10 * pxRatio;

  foundNodes.length = 0;
  foundEdges.length = 0;

  qBounds[0] = x - offset;
  qBounds[1] = y - offset;
  qBounds[2] = x + offset;
  qBounds[3] = y + offset;

  // foundNodes = U.search(qBounds[0], qBounds[1], qBounds[2], qBounds[3]).forEach(storeFound);
  Q.query(qBounds).forEach(storeFound);


  //const mhash = hash(x, y)
  requestAnimationFrame(render);
});

canvas.addEventListener('click', ({ clientX, clientY }) => {
  const mx = clientX * pxRatio;
  const my = clientY * pxRatio;

  selectedNode = null;
  selectedQuad = null;
  visualQuads.length = 0;
  for (let i = 0; i < data.nodes.length; i++) {
    const node = data.nodes[i];
    const { x, y, r } = node;
    const dx = x - mx,
          dy = y - my;
    const dist = Math.sqrt(dx * dx + dy * dy);
    if (dist < r) {
      selectedNode = node;
      break;
    }
  }

  const range = [mx - 50, my - 50, mx + 50, my + 50];
  const block = Q.getContainingBlock(range);
  const node  = Q.getEnclosingNode(block);

  if (node) {
    visualQuads.push(node.data.bbox);
    node.data.objects.forEach(storeFound);
  } else {
    Q.eachChild(block, (n) => {
      if (intersects(range, n.data.bbox)) {
        visualQuads.push(n.data.bbox);
        n.data.objects.forEach(storeFound);
      }
    });
  }

  requestAnimationFrame(render);
});


const Q = new MQuadtree(100);
const U = new UBTree();

console.time('insert into Q');
data.nodes.forEach((n) => {
  const bbox = [n.x - n.r, n.y - n.r, n.x + n.r, n.y + n.r];
  bbox.n = n;
  Q.insert(bbox);
});
console.timeEnd('insert into Q');

console.time('insert segments into Q');
data.edges.forEach((e) => {
  const s = nodesMap[e.source],
        t = nodesMap[e.target];
  const seg = [[s.x, s.y], [t.x, t.y]];
  seg.n = e;
  seg.segment = true;
  Q.insert(seg);
});
console.timeEnd('insert segments into Q');

console.time('insert into UB');
data.nodes.forEach((n) => {
  const bbox = [n.x - n.r, n.y - n.r, n.x + n.r, n.y + n.r];
  U.insert({ bbox, n });
});
console.timeEnd('insert into UB');

console.time('insert into d3-quadtree');
var d3t = d3.quadtree(data.nodes, (d) => d.x, (d) => d.y);
console.timeEnd('insert into d3-quadtree');

render();