import “../behavior/drag”; import “../core/identity”; import “../core/rebind”; import “../event/event”; import “../event/dispatch”; import “../event/timer”; import “../geom/quadtree”; import “layout”;

// A rudimentary force layout using Gauss-Seidel. d3.layout.force = function() {

var force = {},
    event = d3.dispatch("start", "tick", "end"),
    size = [1, 1],
    drag,
    alpha,
    friction = .9,
    linkDistance = d3_layout_forceLinkDistance,
    linkStrength = d3_layout_forceLinkStrength,
    charge = -30,
    gravity = .1,
    theta = .8,
    nodes = [],
    links = [],
    distances,
    strengths,
    charges;

function repulse(node) {
  return function(quad, x1, _, x2) {
    if (quad.point !== node) {
      var dx = quad.cx - node.x,
          dy = quad.cy - node.y,
          dn = 1 / Math.sqrt(dx * dx + dy * dy);

      /* Barnes-Hut criterion. */
      if ((x2 - x1) * dn < theta) {
        var k = quad.charge * dn * dn;
        node.px -= dx * k;
        node.py -= dy * k;
        return true;
      }

      if (quad.point && isFinite(dn)) {
        var k = quad.pointCharge * dn * dn;
        node.px -= dx * k;
        node.py -= dy * k;
      }
    }
    return !quad.charge;
  };
}

force.tick = function() {
  // simulated annealing, basically
  if ((alpha *= .99) < .005) {
    event.end({type: "end", alpha: alpha = 0});
    return true;
  }

  var n = nodes.length,
      m = links.length,
      q,
      i, // current index
      o, // current object
      s, // current source
      t, // current target
      l, // current distance
      k, // current force
      x, // x-distance
      y; // y-distance

  // gauss-seidel relaxation for links
  for (i = 0; i < m; ++i) {
    o = links[i];
    s = o.source;
    t = o.target;
    x = t.x - s.x;
    y = t.y - s.y;
    if (l = (x * x + y * y)) {
      l = alpha * strengths[i] * ((l = Math.sqrt(l)) - distances[i]) / l;
      x *= l;
      y *= l;
      t.x -= x * (k = s.weight / (t.weight + s.weight));
      t.y -= y * k;
      s.x += x * (k = 1 - k);
      s.y += y * k;
    }
  }

  // apply gravity forces
  if (k = alpha * gravity) {
    x = size[0] / 2;
    y = size[1] / 2;
    i = -1; if (k) while (++i < n) {
      o = nodes[i];
      o.x += (x - o.x) * k;
      o.y += (y - o.y) * k;
    }
  }

  // compute quadtree center of mass and apply charge forces
  if (charge) {
    d3_layout_forceAccumulate(q = d3.geom.quadtree(nodes), alpha, charges);
    i = -1; while (++i < n) {
      if (!(o = nodes[i]).fixed) {
        q.visit(repulse(o));
      }
    }
  }

  // position verlet integration
  i = -1; while (++i < n) {
    o = nodes[i];
    if (o.fixed) {
      o.x = o.px;
      o.y = o.py;
    } else {
      o.x -= (o.px - (o.px = o.x)) * friction;
      o.y -= (o.py - (o.py = o.y)) * friction;
    }
  }

  event.tick({type: "tick", alpha: alpha});
};

force.nodes = function(x) {
  if (!arguments.length) return nodes;
  nodes = x;
  return force;
};

force.links = function(x) {
  if (!arguments.length) return links;
  links = x;
  return force;
};

force.size = function(x) {
  if (!arguments.length) return size;
  size = x;
  return force;
};

force.linkDistance = function(x) {
  if (!arguments.length) return linkDistance;
  linkDistance = typeof x === "function" ? x : +x;
  return force;
};

// For backwards-compatibility.
force.distance = force.linkDistance;

force.linkStrength = function(x) {
  if (!arguments.length) return linkStrength;
  linkStrength = typeof x === "function" ? x : +x;
  return force;
};

force.friction = function(x) {
  if (!arguments.length) return friction;
  friction = +x;
  return force;
};

force.charge = function(x) {
  if (!arguments.length) return charge;
  charge = typeof x === "function" ? x : +x;
  return force;
};

force.gravity = function(x) {
  if (!arguments.length) return gravity;
  gravity = +x;
  return force;
};

force.theta = function(x) {
  if (!arguments.length) return theta;
  theta = +x;
  return force;
};

force.alpha = function(x) {
  if (!arguments.length) return alpha;

  x = +x;
  if (alpha) { // if we're already running
    if (x > 0) alpha = x; // we might keep it hot
    else alpha = 0; // or, next tick will dispatch "end"
  } else if (x > 0) { // otherwise, fire it up!
    event.start({type: "start", alpha: alpha = x});
    d3.timer(force.tick);
  }

  return force;
};

force.start = function() {
  var i,
      j,
      n = nodes.length,
      m = links.length,
      w = size[0],
      h = size[1],
      neighbors,
      o;

  for (i = 0; i < n; ++i) {
    (o = nodes[i]).index = i;
    o.weight = 0;
  }

  for (i = 0; i < m; ++i) {
    o = links[i];
    if (typeof o.source == "number") o.source = nodes[o.source];
    if (typeof o.target == "number") o.target = nodes[o.target];
    ++o.source.weight;
    ++o.target.weight;
  }

  for (i = 0; i < n; ++i) {
    o = nodes[i];
    if (isNaN(o.x)) o.x = position("x", w);
    if (isNaN(o.y)) o.y = position("y", h);
    if (isNaN(o.px)) o.px = o.x;
    if (isNaN(o.py)) o.py = o.y;
  }

  distances = [];
  if (typeof linkDistance === "function") for (i = 0; i < m; ++i) distances[i] = +linkDistance.call(this, links[i], i);
  else for (i = 0; i < m; ++i) distances[i] = linkDistance;

  strengths = [];
  if (typeof linkStrength === "function") for (i = 0; i < m; ++i) strengths[i] = +linkStrength.call(this, links[i], i);
  else for (i = 0; i < m; ++i) strengths[i] = linkStrength;

  charges = [];
  if (typeof charge === "function") for (i = 0; i < n; ++i) charges[i] = +charge.call(this, nodes[i], i);
  else for (i = 0; i < n; ++i) charges[i] = charge;

  // initialize node position based on first neighbor
  function position(dimension, size) {
    var neighbors = neighbor(i),
        j = -1,
        m = neighbors.length,
        x;
    while (++j < m) if (!isNaN(x = neighbors[j][dimension])) return x;
    return Math.random() * size;
  }

  // initialize neighbors lazily
  function neighbor() {
    if (!neighbors) {
      neighbors = [];
      for (j = 0; j < n; ++j) {
        neighbors[j] = [];
      }
      for (j = 0; j < m; ++j) {
        var o = links[j];
        neighbors[o.source.index].push(o.target);
        neighbors[o.target.index].push(o.source);
      }
    }
    return neighbors[i];
  }

  return force.resume();
};

force.resume = function() {
  return force.alpha(.1);
};

force.stop = function() {
  return force.alpha(0);
};

// use `node.call(force.drag)` to make nodes draggable
force.drag = function() {
  if (!drag) drag = d3.behavior.drag()
      .origin(d3_identity)
      .on("dragstart.force", d3_layout_forceDragstart)
      .on("drag.force", dragmove)
      .on("dragend.force", d3_layout_forceDragend);

  if (!arguments.length) return drag;

  this.on("mouseover.force", d3_layout_forceMouseover)
      .on("mouseout.force", d3_layout_forceMouseout)
      .call(drag);
};

function dragmove(d) {
  d.px = d3.event.x, d.py = d3.event.y;
  force.resume(); // restart annealing
}

return d3.rebind(force, event, "on");

};

// The fixed property has three bits: // Bit 1 can be set externally (e.g., d.fixed = true) and show persist. // Bit 2 stores the dragging state, from mousedown to mouseup. // Bit 3 stores the hover state, from mouseover to mouseout. // Dragend is a special case: it also clears the hover state.

function d3_layout_forceDragstart(d) {

d.fixed |= 2; // set bit 2

}

function d3_layout_forceDragend(d) {

d.fixed &= ~6; // unset bits 2 and 3

}

function d3_layout_forceMouseover(d) {

d.fixed |= 4; // set bit 3
d.px = d.x, d.py = d.y; // set velocity to zero

}

function d3_layout_forceMouseout(d) {

d.fixed &= ~4; // unset bit 3

}

function d3_layout_forceAccumulate(quad, alpha, charges) {

var cx = 0,
    cy = 0;
quad.charge = 0;
if (!quad.leaf) {
  var nodes = quad.nodes,
      n = nodes.length,
      i = -1,
      c;
  while (++i < n) {
    c = nodes[i];
    if (c == null) continue;
    d3_layout_forceAccumulate(c, alpha, charges);
    quad.charge += c.charge;
    cx += c.charge * c.cx;
    cy += c.charge * c.cy;
  }
}
if (quad.point) {
  // jitter internal nodes that are coincident
  if (!quad.leaf) {
    quad.point.x += Math.random() - .5;
    quad.point.y += Math.random() - .5;
  }
  var k = alpha * charges[quad.point.index];
  quad.charge += quad.pointCharge = k;
  cx += k * quad.point.x;
  cy += k * quad.point.y;
}
quad.cx = cx / quad.charge;
quad.cy = cy / quad.charge;

}

var d3_layout_forceLinkDistance = 20,

d3_layout_forceLinkStrength = 1;