/**
 * @param {object} G
 * @param {Array<Object>} G.nodes
 * @param {Array<Object>} G.edges
 * @param {Array<Number>} [xmin,ymin,xmax,ymax]
 */
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;
  });
}

/**
 * G -> [xmin, ymin, xmax, ymax], radii are ignored
 */
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]);
}

/**
 * O(V+E) tree graph generator
 */
function generateTree(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
      };
    })
  };
}

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

let simulation = null;


function fmm ({ nodes }) {

  const getX = n => n.x;
  const getY = n => n.y;

  function force (alpha) {
    let i, n = nodes.length;
    const tree = d3.quadtree(nodes, getX, getY);
    const leafs = [];
    tree.visit((node) => {
      if (node.length) {
        for (let i = 0; i < 4; i++) {
          const child = node[i];
          if (child) child.parent = node;
        }
      } else leafs.push(node);
    });

    //d3.packEnclose([{x: 0, y: 0, r: 200}])
  }

  return force;
}

/**
 * Force layout to get the initial positions
 * @param {Graph} data
 * @param [function] onUpdate - to call on each layout pass
 */
function layout(data, onUpdate = () => {}) {
  return new Promise((resolve) => {
    const m = 2;
    const {
      forceSimulation,
      forceLink,
      forceX, forceY,
      forceCenter,
      forceCollide,
      forceManyBody
    } = d3;
    if (simulation) simulation.stop();
    simulation = forceSimulation(data.nodes)
      .force('charge', forceManyBody())
      .force('link', forceLink(data.edges.map((e) => ({
          id: e.id,
          target: e.target,
          source: e.source
        }))
      )
        .id((d) => d.id))
      .force('collision', forceCollide(10))
      .force('center', forceCenter(w / 2, h / 2))
      .force('y', forceY(0))
      .force('x', forceX(0))
      //.alphaDecay(0.1)  // increase for rougher results
      .on('tick', onUpdate)
      .on('end', resolve);
  });
}


function layout(data, onUpdate = () => {}) {
  return new Promise((resolve) => {
    const m = 2;
    const {
      forceSimulation,
      forceLink,
      forceX, forceY,
      forceCenter,
      forceCollide,
      forceManyBody
    } = d3;
    if (simulation) simulation.stop();
    simulation = forceSimulation(data.nodes)
      .force('fmm', fmm(data))
      .force('charge', forceManyBody())
      .force('link', forceLink(data.edges.map((e) => ({
          id: e.id,
          target: e.target,
          source: e.source
        }))
      )
        .id((d) => d.id))
      //.force('collision', forceCollide(10))
      .force('center', forceCenter(w / 2, h / 2))
      .force('y', forceY(0))
      .force('x', forceX(0))
      //.alphaDecay(0.1)  // increase for rougher results
      .on('tick', onUpdate)
      .on('end', resolve);
  });
}