node.java

ALGAE是一个快速创建算法演示的框架。目前支持的算法实现语言包括java和c

    nodeSize.height = gi.getTextOffset().height;

    if (text != null && text.length() > 0)
      {
	FontMetrics fm = gi.getFontMetrics();
	stringWidth = fm.stringWidth(text);
	nodeSize.width += stringWidth + gi.getTextOffset().width;
	nodeSize.height += fm.getAscent() + gi.getTextOffset().height;
      }

    if (vertical)
      {
	for (Enumeration e = children(); e.hasMoreElements(); )
	  {
	    Node child = (Node)(e.nextElement());
	    child.computeSize(gi);
	    if (child.oldPosition == null)
	      child.oldPosition = new Point();

	    child.oldPosition.x = gi.getTextOffset().width;
	    child.oldPosition.y = nodeSize.height;
	    nodeSize.height += child.nodeSize.height + gi.getTextOffset().height;
	    nodeSize.width = Math.max
	      (nodeSize.width,
	       child.nodeSize.width+2*gi.getTextOffset().width);
	  }
      }
    else
      {
	int componentWidth = gi.getTextOffset().width;
	int componentHeight = 0;
	for (Enumeration e = children(); e.hasMoreElements(); )
	  {
	    Node child = (Node)(e.nextElement());
	    child.computeSize(gi);
	    if (child.oldPosition == null)
	      child.oldPosition = new Point();

	    child.oldPosition.x = componentWidth;
	    child.oldPosition.y = nodeSize.height;
	    componentWidth += child.nodeSize.width + gi.getTextOffset().width;
	    componentHeight = Math.max
	      (componentHeight, child.nodeSize.height);
	  }
	if (componentHeight > 0)
	  {
	    nodeSize.height += componentHeight + gi.getTextOffset().height;
	    nodeSize.width = Math.max(nodeSize.width,
				      componentWidth/*+2*gi.getTextOffset().width*/);
	  }
      }
  }


  /**
   * Used in repositioning nodes, this function computes a penalty score
   * based on how far the edges into and out of the node are bent away
   * from their "ideal" angle and on how much their length differs from
   * a given target length.
   *   @param targetLength  The desired length for all edges
   *   @return The penalty value
   */
  private double edgeScore(double targetLength)
  {
    Debug.show (Debug.edgeScore, "edgeScore ", ID());
    double score = 0.0;
    for (Enumeration ei = outEdges.edges(); ei.hasMoreElements();)
      {
	Edge e = (Edge)(ei.nextElement());
	score += e.positionScore(targetLength);
	if (e.destination != null)
	  {
	  Debug.show (Debug.edgeScore, "  dest: ", e.destination.ID());
	  Debug.show (Debug.edgeScore, "  score: ", score);
	  }
	else
	  Debug.show (Debug.edgeScore, "  score: ", score);
      }
    for (Enumeration ei = inEdges.edges(); ei.hasMoreElements();)
      {
	Edge e = (Edge)(ei.nextElement());
	score += e.positionScore(targetLength);
	if (e.destination != null)
	  Debug.show (Debug.edgeScore, "  dest: ", e.destination.ID());
	Debug.show (Debug.edgeScore, "  score: ", score);
      }
    return score;
  }


  /**
   *  Checks to see if this node overlaps another.
   *
   *  @param n any node
   *  @return true if this node overlaps n
   */
  private boolean overlaps (Node n)
  {
    if ((n.currentPosition.y + n.nodeSize.height < currentPosition.y)
	|| (n.currentPosition.y > currentPosition.y + n.nodeSize.height)
	|| (n.currentPosition.x + n.nodeSize.width < currentPosition.x)
	|| (n.currentPosition.x > currentPosition.x + n.nodeSize.width))
      return false;
    else
      return true;
  }
  

  
  /**
   * Used in repositioning nodes, this function computes a penalty score
   * based on the edge score and the number of nodes overlapping this one.
   *
   *   @see edgeScore
   *
   *   @param targetLength  The desired length for all edges
   *   @return The penalty value
   */
  private double positionScore(double targetLength)
  {
    // Nodes that are less than this number of "body lengths" away
    // from each other are subject to a "repulsion penalty" to push them
    // apart.
    final int repulsionSensitivity = 3;
    final double repulsionStrength = 15.0;

    Debug.show (Debug.positionScore, "positionScore ", ID());
    double repulsionPenalty = 1.0;
    int s1 = (nodeSize.width + nodeSize.height) / 2;

    if (targetLength < (double)s1)
      targetLength = (double)s1;

    Point currentPos = position();
    
    for (Enumeration e = parent().children(); e.hasMoreElements(); )
      {
	Node n = (Node)(e.nextElement());
	if (n != this) {
	  Point nCurrentPos = n.position();
	  int dx = Math.abs(currentPos.x + nodeSize.width/2 -
			    nCurrentPos.x - n.nodeSize.width/2);
	  int dy = Math.abs(currentPos.y + nodeSize.height/2 -
			    nCurrentPos.y - n.nodeSize.height/2);
	  int s2 = (n.nodeSize.width + n.nodeSize.height) / 2;
	  int limit = repulsionSensitivity * (s1 + s2);
	  
	  if (dx + dy < limit)
	    {
	      double p = 1.0 - ((double)(dx + dy)) / ((double)limit);
	      repulsionPenalty += /* repulsionStrength * */ p * p;
	    }
	}
      }
    
    Debug.show (Debug.positionScore,
		"  repulsion penalty: ", repulsionPenalty);
    double score = (1.0 + edgeScore(targetLength)) * repulsionPenalty;

    for (Enumeration e = children(); e.hasMoreElements(); )
      {
	Node child = (Node)(e.nextElement());
	score += child.positionScore (targetLength);
      }
    return score;
  }


  /**
   * Used in repositioning nodes, this function computes a penalty score
   * based on the edge score and the number of nodes overlapping this one.
   * 
   *   @see edgeScore
   *
   *   @param targetLength  The desired length for all edges
   *   @param pos           The node's currentPosition is set to this before
   *                        evaluating the score.
   *   @return The penalty value
   */
  private double positionScore(double targetLength, Point pos)
  {
    currentPosition = pos;
    return positionScore (targetLength);
  }

  
  /**
   * Aids in computing the average length of all edges in the graph.
   *  @return The sum of the lengths of all edges emanating from this node
   *   and the number of non-zero-length outgoing edges.
   */
  PartialSum tallyEdgeLengths()
  {
    PartialSum p = new PartialSum();
    p.nEdges = 0;
    p.sumOfLengths = 0.0;
    for (Enumeration ei = outEdges.edges(); ei.hasMoreElements();)
      {
	Edge e = (Edge)(ei.nextElement());
	if ((this != e.destination) && (e.destination != null))
	  {
	    p.sumOfLengths += e.length();
	    ++p.nEdges;
	  }
      }

    for (Enumeration e = children(); e.hasMoreElements(); )
      {
	Node child = (Node)(e.nextElement());
	PartialSum pInner = child.tallyEdgeLengths();
	p.sumOfLengths += pInner.sumOfLengths;
	p.nEdges += p.nEdges;
      }

    return p;
  }


  /**
   *  Find the best position to place this node along a specified
   *  line segment.
   *
   *  @param targetLength  Desired average length for all edges.
   *  @param endpoint1  One endpoint of the line segment.
   *  @param endpoint2  The other endpoint.
   *  @return The point along the line segment from <code>endpoint1</code>
   *    to <code>endpoint2</code> that minimizes the node's position score.
   *
   *  @see positionScore
   */
  private Point optimalPosition (double targetLength,
				 Point endpoint1,
				 Point endpoint2)
  {
    Point savedCurrentPosition = currentPosition;

    Point p1 = new Point(endpoint1);
    Point p3 = new Point(endpoint2);
    Point p2 = new Point((p1.x + p3.x)/2, (p1.y + p3.y)/2);
    double s1 = positionScore (targetLength, p1);
    double s2 = positionScore (targetLength, p2);
    double s3 = positionScore (targetLength, p3);
    

    Point ptmp;
    double stmp;

    // Stage 1: binary search until the middle point has a smaller score
    //  than either endpoint.
    while ((s2 >= s1 || s2 >= s3)
	   && (p2.x != p3.x || p2.y != p3.y)
	   && (p2.x != p1.x || p2.y != p1.y))
      {
	Debug.show (Debug.reposition, "binary search: p1 ", p1);
	Debug.show (Debug.reposition, "             : p2 ", p2);
	Debug.show (Debug.reposition, "             : p3 ", p3);
	Debug.show (Debug.reposition, "             : s1 ", s1);
	Debug.show (Debug.reposition, "             : s2 ", s2);
	Debug.show (Debug.reposition, "             : s3 ", s3);
	
	if (s1 > s3)
	  {
	    ptmp = p1;
	    p1 = p2;
	    s1 = s2;
	    p2 = ptmp;
	  }
	else
	  {
	    ptmp = p3;
	    p3 = p2;
	    s3 = s2;
	    p2 = ptmp;
	  }
	p2.x = (p1.x + p3.x) / 2;
	p2.y = (p1.y + p3.y) / 2;
	s2 = positionScore (targetLength, p2);
      }

    // Stage 2: valley search
    Point p4 = p3;
    p3 = new Point ((p2.x + p4.x)/2, (p2.y + p4.y)/2);
    double s4 = s3;
    s3 = positionScore (targetLength, p3);

    int d12 = 5;
    int d24 = 0;

    while (d12 + d24 > 4)
      {
	Debug.show (Debug.reposition, "valley search: p1 ", p1);
	Debug.show (Debug.reposition, "             : p2 ", p2);
	Debug.show (Debug.reposition, "             : p3 ", p3);
	Debug.show (Debug.reposition, "             : p4 ", p4);
	Debug.show (Debug.reposition, "             : s1 ", s1);
	Debug.show (Debug.reposition, "             : s2 ", s2);
	Debug.show (Debug.reposition, "             : s3 ", s3);
	Debug.show (Debug.reposition, "             : s4 ", s4);
	if (s2 < s3)
	  {
	    // Keep points p1, p2, p3
	    ptmp = p4;
	    p4 = p3;
	    s4 = s3;
	  }
	else
	  {
	    // Keep points p2, p3, p4
	    ptmp = p1;
	    p1 = p2;
	    p2 = p3;

	    s1 = s2;
	    s2 = s3;
	  }

	// Points p1, p2, p4 are in order, (p3 is garbage)
	// Choose a point midway in the larger of the p1..p2 and p2..p4
	//  ranges.
	d12 = Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y);
	d24 = Math.abs(p2.x - p4.x) + Math.abs(p2.y - p4.y);
	if (d12 < d24)
	  {
	    // new point is between p2 and p4
	    p3 = ptmp;
	    p3.x = (p2.x + p4.x) / 2;
	    p3.y = (p2.y + p4.y) / 2;
	    s3 = positionScore (targetLength, p3);
	  }
	else
	  {
	    // new point is between p1 and p2
	    p3 = p2;
	    s3 = s2;
	    p2 = ptmp;
	    p2.x = (p1.x + p3.x) / 2;
	    p2.y = (p1.y + p3.y) / 2;
	    s2 = positionScore (targetLength, p2);
	  }
      }

    currentPosition = savedCurrentPosition;
    return p2;
  }
  


  /**
   * Add a nested component of this node.
   *  @param vn Node to add
   */
  public void addComponent (Node vn)
  {
    Node addThis = vn;
    
    if ((vn.parent() != null) && (vn.parent().parent() != null))
      {
	addThis = new Stub (vn, vn.color, vn.vertical);
      }
    
    addThis.oldPosition = addThis.currentPosition = addThis.newPosition = null;
    super.add (addThis);

    changed();
  }

  /**
   * Remove a nested component of this node.
   *  @param vn Node to remove
   *  @return True if vn was a component of this node (in which case it has
   *    been removed). False if it was not (in which case nothing was done).
   */
  boolean removeComponent (Node vn)
  {
    if (vn.parent() == this)
      {
	vn.isolate();
	vn.oldPosition = vn.currentPosition = vn.newPosition = null;
	changed();
	return true;
      }
    else
      return false;
  }

  /**
   *  What is the current color of this node? (May include highlighting).
   *    @return the color
   */
  public Color getColor() 
  {
    return color;
  }


  /**
   *  Change the normal ("permanent") color of this node.
   *    @param v   the color
   */
  public void setColor(Color v) 
  {
    if (color != v)
      {
	color = v;
	changed();
      }
  }


  /**
   *  If this node has no position yet, choose one.
   *  The same chosen position will be assigned as the old, new, and current
   *  position.
   *
   *   @param gi Graphics context information
   *   @param graph  The data graph within which this node occurs.
   */
  void chooseInitialPosition (GraphicsInfo gi, IDTree graph)
  {
    computeSize(gi);
    int offset = (nodeSize.width + nodeSize.height) / 2;

    for (Enumeration i = inEdges.edges();
	 i.hasMoreElements() && oldPosition == null;)
      {
	Edge e = (Edge)(i.nextElement());
	Point exit = null;
	if (e.source != this &&
	    e.dir != Direction.ANYDIR &&
	    ((Node)(e.source)).oldPosition != null &&
	     (exit = e.exitPoint()) != null)
	  {
	    oldPosition = new Point(exit);
	    oldPosition.x += offset*Edge.xNorm[e.dir];
	    oldPosition.y += offset*Edge.yNorm[e.dir];
	  }
      }
    for (Enumeration i = inEdges.edges();
	 i.hasMoreElements() && oldPosition == null;)
      {
	Edge e = (Edge)(i.nextElement());
	Point exit = null;
	int dir = (e.dir + 8) % 16;
	if (e.destination != null &&
	    e.destination != this &&
	    e.dir != Direction.ANYDIR &&
	    ((Node)(e.destination)).oldPosition != null &&