// A rudimentary force layout using Gauss-Seidel.

d3.layout.force = function() {

  var force = {},

      event = d3.dispatch("tick"),

      size = [1, 1],

      drag,

      alpha,

      friction = .9,

      linkDistance = d3_layout_forceLinkDistance,

      linkStrength = d3_layout_forceLinkStrength,

      charge = -30,

      gravity = .1,

      theta = .8,

      interval,

      nodes = [],

      links = [],

      distances,

      strengths,

      charges;

  function repulse(node) {

    return function(quad, x1, y1, x2, y2) {

      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;

    };

  }

  function tick() {

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

    // simulated annealing, basically

    return (alpha *= .99) < .005;

  }

  force.on = function(type, listener) {

    event.on(type, listener);

    return force;

  };

  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 = d3.functor(x);

    return force;

  };

  // For backwards-compatibility.

  force.distance = force.linkDistance;

  force.linkStrength = function(x) {

    if (!arguments.length) return linkStrength;

    linkStrength = d3.functor(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.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;

    }

    distances = [];

    strengths = [];

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

      distances[i] = linkDistance.call(this, o, i);

      strengths[i] = linkStrength.call(this, o, i);

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

    }

    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() {

    alpha = .1;

    d3.timer(tick);

    return force;

  };

  force.stop = function() {

    alpha = 0;

    return force;

  };

  // use `node.call(force.drag)` to make nodes draggable

  force.drag = function() {

    if (!drag) drag = d3.behavior.drag()

        .on("dragstart", dragstart)

        .on("drag", d3_layout_forceDrag)

        .on("dragend", d3_layout_forceDragEnd);

    this.on("mouseover.force", d3_layout_forceDragOver)

        .on("mouseout.force", d3_layout_forceDragOut)

        .call(drag);

  };

  function dragstart(d) {

    d3_layout_forceDragOver(d3_layout_forceDragNode = d);

    d3_layout_forceDragForce = force;

  }

  return force;

};

var d3_layout_forceDragForce,

    d3_layout_forceDragNode;

function d3_layout_forceDragOver(d) {

  d.fixed |= 2;

}

function d3_layout_forceDragOut(d) {

  if (d !== d3_layout_forceDragNode) d.fixed &= 1;

}

function d3_layout_forceDragEnd() {

  d3_layout_forceDrag();

  d3_layout_forceDragNode.fixed &= 1;

  d3_layout_forceDragForce = d3_layout_forceDragNode = null;

}

function d3_layout_forceDrag() {

  d3_layout_forceDragNode.px += d3.event.dx;

  d3_layout_forceDragNode.py += d3.event.dy;

  d3_layout_forceDragForce.resume(); // restart annealing

}

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;