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;

const stats = {
  queries: 0,
  totalTime: 0,
  getAverage() {
    return `${this.totalTime / this.queries}ms`;
  },
  clear() {
    this.totalTime = this.queries = 0;
  }
};

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,
        curvature: (i % 3 === 0) ? 1 : 1,
        //curvature: 0,
        source: Math.floor(Math.sqrt(i)),
        target: i + 1
      };
    })
  };
}

var N = 1000;
var data, nodesMap, simulation;
const SZ = 5;
var flatStorage;
let foundNodes = [];
let foundEdges = [];
let selectedNode = null;
let showIndex = false;

function populate(n) {
  N = n;
  foundNodes = [];
  foundEdges = [];
  selectedNode = null;

  if (simulation) simulation.stop();
  data = generateDenseTree(N, w, h);
  nodesMap = data.nodes.reduce((a, n) => {
    a[n.id] = n;
    return a;
  }, {});
  flatStorage = new Float32Array(SZ * 2 * N);


  simulation = layout(data, onLayoutDone);
}

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

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

  if (showIndex) {
    ctx.lineWidth = 0.5;
    renderIndex();

    ctx.lineWidth = 1;
    ctx.beginPath();
    U._checkedNodes.forEach((n) => {
      const b = U.keyToBBox(n.key);
      ctx.rect(b[0], b[1], b[2] - b[0], b[3] - b[1]);
    });
    ctx.globalAlpha = 0.2;
    ctx.fillStyle = 'blue';
    ctx.fill();
    ctx.globalAlpha = 1;
  }


  const Nn = data.nodes.length;
  // const { nodes, edges } = U.size === 0 ? data : U.query([0, 0, w, h])
  //   .reduce((a, id) => {
  //     if (!a.ids[id]) {
  //       a.ids[id] = true;
  //       if (id >= Nn) a.edges.push(data.edges[id - Nn]);
  //       else          a.nodes.push(data.nodes[id]);
  //     }
  //     return a;
  //   }, { nodes: [], edges: [], ids: {} });

  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);
    if (e.curvature === 0) {
      ctx.lineTo(t.x, t.y);
    } else {
      const cp = getQuadraticControlPoint(s.x, s.y, t.x, t.y);
      ctx.quadraticCurveTo(cp.x, cp.y, t.x, t.y);
    }
  });
  ctx.stroke();
  ctx.closePath();

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

    if (e.curvature === 0) {
      ctx.lineTo(t.x, t.y);
    } else {
      const cp = getQuadraticControlPoint(s.x, s.y, t.x, t.y);
      ctx.quadraticCurveTo(cp.x, cp.y, t.x, t.y);
    }
  });
  ctx.stroke();

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

  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.closePath();
  ctx.stroke();
}


function renderIndex() {
  const map = {};
  const nodesToDraw = [];
  U.forEach((n) => {
    if (!map[n.key]) {
      map[n.key] = true;
      nodesToDraw.push(n);
    }
  });

  ctx.beginPath();
  nodesToDraw.forEach((n) => {
    const b = U.keyToBBox(n.key);
    ctx.rect(b[0], b[1], b[2] - b[0], b[3] - b[1]);
  });
  ctx.closePath();
  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;
}

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;

  const Nn = data.nodes.length;
  const before = Date.now();
  U.query(qBounds).forEach((id) => {
    if (id >= Nn) {
      foundEdges.push(data.edges[id - Nn]);
    } else {
      foundNodes.push(data.nodes[id]);
    }
  });
  stats.totalTime += (Date.now() - before);
  stats.queries++;

  requestAnimationFrame(render);
});

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

  requestAnimationFrame(render);
});

function onLayoutDone() {
  indexNodes();
  indexEdges();
}


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

    const pos = i * SZ;
    flatStorage[pos + 0] = bbox[0];
    flatStorage[pos + 1] = bbox[1];
    flatStorage[pos + 2] = bbox[2];
    flatStorage[pos + 3] = bbox[3];
    flatStorage[pos + 4] = POLYGON;

    U.insert(i);
  });
  console.timeEnd('insert nodes into UB');
}

function indexEdges() {
  console.time('insert edges into UB');
  const offset = data.nodes.length;
  data.edges.forEach(({ source, target, curvature }, i) => {
    const s = nodesMap[source],
          t = nodesMap[target];
    const pos = SZ * (offset + i);

    // console.log(source, target);

    flatStorage[pos + 0] = /*s.x; */ source;
    flatStorage[pos + 1] = /*s.y; */ target;
    flatStorage[pos + 2] = curvature; // t.x;
    flatStorage[pos + 3] = t.y;
    flatStorage[pos + 4] = curvature === 0 ? LINESTRING : CURVE;

    U.insert(offset + i);
  });
  console.timeEnd('insert edges into UB');
}


function updateNodes() {
  data.nodes.map((n, i) => {
    const { x, y, r } = n;
    const pos = i * SZ;
    flatStorage[pos + 0] = x - r;
    flatStorage[pos + 1] = y - r;
    flatStorage[pos + 2] = x + r;
    flatStorage[pos + 3] = y + r;
    flatStorage[pos + 4] = POLYGON;

    U.update(i);
  });
}

function updateEdges() {
  const offset = data.nodes.length;
  data.edges.forEach(({ source, target }, i) => {
    const s = nodesMap[source],
          t = nodesMap[target];
    const pos = SZ * (offset + i);

    flatStorage[pos + 0] = source; //s.x;
    flatStorage[pos + 1] = target; //s.y;
    flatStorage[pos + 2] = t.x;
    flatStorage[pos + 3] = t.y;
    flatStorage[pos + 4] = LINESTRING;

    U.update(offset + i);
  });
}


function clearNodesIndex() {
  console.time('clear nodes');
  data.nodes.forEach((e, i) => U.remove(i))
  console.timeEnd('clear nodes');
}

function clearEdgesIndex() {
  console.time('clear edges');
  const offset = data.nodes.length;
  data.edges.forEach((e, i) => U.remove(offset + i));
  console.timeEnd('clear edges');
}

function layout(data, callback = () => {}) {
  const m = data.nodes.length < 1000 ? 1.2 : 1;
  return d3.forceSimulation(data.nodes)
    .force('charge', d3.forceManyBody())
    .force('link', d3.forceLink(data.edges.map((e) => ({
        id: e.id,
        target: e.target,
        source: e.source
      }))
    )
      .id((d) => d.id)
      .distance(25 * m))
    .force('collision', d3.forceCollide(15 * m))
    .force('center', d3.forceCenter(w / 2, h / 2))
    .force("y", d3.forceY(0))
    .force("x", d3.forceX(0))
    .alphaDecay(0.1)
    .on('tick', render)
    .on('end', callback);
}

const U = new UBTree(6);

const form = document.querySelector('#control');
form.addEventListener('change', function() {
  setTimeout(function() {
    var nodesIndex = form['nodes'].checked;
    var edgesIndex = form['edges'].checked;
    var level      = form['level'].value;

    U.clear();
    U.setLevel(level);

    if (nodesIndex) indexNodes();
    if (edgesIndex) indexEdges();

    showIndex = form['grid'].checked;
    render();
  }, 50);
});

const indicator  = document.querySelector('#indicator');
const rangeInput = document.querySelector('#range');
var populateTimer = 0;
function onGraphChanged() {
  clearTimeout(populateTimer);
  populateTimer = requestAnimationFrame(() => {
    N = parseInt(rangeInput.value);
    indicator.innerHTML = `G = (${N}<sub>V</sub> &times; ${N}<sub>E</sub>)`;
    populate(N);
  });
}
rangeInput.addEventListener('change', onGraphChanged);

onGraphChanged();