/**

 * The SpringLayout package represents a visualization of a set of nodes. The

 * SpringLayout, which is initialized with a Graph, assigns X/Y locations to

 * each node. When called <code>relax()</code>, the SpringLayout moves the

 * visualization forward one step.

 *

 * @author Danyel Fisher

 * @author Joshua O'Madadhain

 */

sclass CALSpringLayout {

  double repulsion_range_sq = sqr(0.4/*0.5*//*100*/);

  double repulsionFactor = 0.02/*0.01*/;

  double desiredLength = defaultDesiredLength;

  static double defaultDesiredLength = 0.3;

  bool center;

  AutoMap<Circle, SpringVertexData> springVertexData = new(SpringVertexData.class);

  CirclesAndLines cal;

  *() {}

  *(CirclesAndLines *cal) {}

  /**

   * <p>Sets the stretch parameter for this instance.  This value

   * specifies how much the degrees of an edge's incident vertices

   * should influence how easily the endpoints of that edge

   * can move (that is, that edge's tendency to change its length).</p>

   *

   * <p>The default value is 0.70.  Positive values less than 1 cause

   * high-degree vertices to move less than low-degree vertices, and

   * values > 1 cause high-degree vertices to move more than

   * low-degree vertices.  Negative values will have unpredictable

   * and inconsistent results.</p>

   * @param stretch

   */

  double stretch = 0.70;

  /**

   * Returns the current value for the node repulsion range.

   * @see #setRepulsionRange(int)

   */

  public int getRepulsionRange() {

      return (int)(Math.sqrt(repulsion_range_sq));

  }

  /**

   * Sets the node repulsion range (in drawing area units) for this instance.

   * Outside this range, nodes do not repel each other.  The default value

   * is 100.  Negative values are treated as their positive equivalents.

   * @param range

   */

  public void setRepulsionRange(int range) {

      this.repulsion_range_sq = range * range;

  }

  /**

   * Sets the force multiplier for this instance.  This value is used to

   * specify how strongly an edge "wants" to be its default length

   * (higher values indicate a greater attraction for the default length),

   * which affects how much its endpoints move at each timestep.

   * The default value is 1/3.  A value of 0 turns off any attempt by the

   * layout to cause edges to conform to the default length.  Negative

   * values cause long edges to get longer and short edges to get shorter; use

   * at your own risk.

   */

  double force_multiplier = 1.0 / 3.0;

  /**

   * Relaxation step. Moves all nodes a smidge.

   */

  bool step() {

    deleteKeysNotIn(springVertexData, new HashSet(cal.circles));

		for (Circle v : cal.circles) {

			SpringVertexData svd = springVertexData.get(v);

			if (svd == null) continue;

			svd.dx /= 4;

			svd.dy /= 4;

			svd.edgedx = svd.edgedy = 0;

			svd.repulsiondx = svd.repulsiondy = 0;

		}

  	relaxEdges();

  	calculateRepulsion();

  	ret moveNodes();

  }

  protected void relaxEdges() {

  	try {

  		for (Line e : cal.lines) {

  		  Circle v1 = e.a, v2 = e.b;

  			Point2D p1 = transform(v1);

  			Point2D p2 = transform(v2);

  			if(p1 == null || p2 == null) continue;

  			double vx = p1.getX() - p2.getX();

  			double vy = p1.getY() - p2.getY();

  			double len = Math.sqrt(vx * vx + vy * vy);

  			// round from zero, if needed [zero would be Bad.].

  			len = (len == 0) ? .0001 : len;

  			double f = force_multiplier * (desiredLength - len) / len;

  			// XXX? f = f * Math.pow(stretch, (getGraph().degree(v1) + getGraph().degree(v2) - 2));

  			// the actual movement distance 'dx' is the force multiplied by the

  			// distance to go.

  			double dx = f * vx;

  			double dy = f * vy;

  			ifdef CALSpringLayout_debug

    			print("desiredLen=" + desiredLen + ", len=" + len + ", f=" + f + ", dx=" + dx + ", dy=" + dy);

  			endifdef

  			SpringVertexData v1D, v2D;

  			v1D = springVertexData.get(v1);

  			v2D = springVertexData.get(v2);

  			v1D.edgedx += dx;

  			v1D.edgedy += dy;

  			v2D.edgedx += -dx;

  			v2D.edgedy += -dy;

  		}

  	} catch(ConcurrentModificationException cme) {

  		relaxEdges();

  	}

  }

  void calculateRepulsion() {

    for (Circle v : cal.circles) {

      SpringVertexData svd = springVertexData.get(v);

      if(svd == null) continue;

      double dx = 0, dy = 0;

      for (Circle v2 : cal.circles) {

        if (v == v2) continue;

        Point2D p = transform(v);

        Point2D p2 = transform(v2);

        if(p == null || p2 == null) continue;

        double vx = p.getX() - p2.getX();

        double vy = p.getY() - p2.getY();

        double distanceSq = p.distanceSq(p2);

        if (distanceSq == 0) {

            dx += Math.random()*0.01;

            dy += Math.random()*0.01;

        } else if (distanceSq < repulsion_range_sq) {

            double factor = 1;

            dx += factor * vx / distanceSq;

            dy += factor * vy / distanceSq;

        }

  			ifdef CALSpringLayout_debug

          print("repulsion: distanceSq=" + distanceSq + ", dx=" + dx + ", dy=" + dy);

        endifdef

      }

      double dlen = dx * dx + dy * dy;

      if (dlen > 0) {

        //dlen = Math.sqrt(dlen) / 2 / repulsionFactor;

        // XXX

        dlen = 1000;

        svd.repulsiondx += dx / dlen;

        svd.repulsiondy += dy / dlen;

  			ifdef CALSpringLayout_debug

          print("total repulsion: " + dx/dlen + ", " + dy/dlen);

        endifdef

      }

    }

  }

  // returns true if anything was moved

  bool moveNodes() {

    for (Circle v : cal.circles) {

      SpringVertexData vd = springVertexData.get(v);

      if (vd == null) continue;

      Point2D xyd = transform(v);

      vd.dx += vd.repulsiondx + vd.edgedx;

      vd.dy += vd.repulsiondy + vd.edgedy;

      // keeps nodes from moving any faster than 5 per time unit

      v.x += Math.max(-5, Math.min(5, vd.dx));

      v.y += Math.max(-5, Math.min(5, vd.dy));

      pcallF(cal.onLayoutChange, v);

    }

    if (center)

      calCenterStepwise(cal, 0.1);

    true; // for now

  }

  Point2D transform(Circle v) {

    ret new Point2D.Double(v.x, v.y);

  }

  void clear() {

    springVertexData.clear();

  }

  static class SpringVertexData {

    double edgedx;

    double edgedy;

    double repulsiondx;

    double repulsiondy;

    /** movement speed, x */

    protected double dx;

    /** movement speed, y */

    protected double dy;

  }

}