/**
 * 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;
  }
}