node.java

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

package edu.odu.cs.zeil.AlgAE.Client.DataViewer.DataGraph;

import java.awt.Color;
import java.awt.Dimension;
import java.awt.FontMetrics;
import java.awt.Graphics;
import java.awt.Point;
import java.util.Enumeration;
import java.util.Random;

import edu.odu.cs.zeil.AlgAE.Debug;
import edu.odu.cs.zeil.AlgAE.Direction;
import edu.odu.cs.zeil.AlgAE.Client.GraphicsInfo;
import edu.odu.cs.zeil.AlgAE.Client.DataViewer.DataGraph.Edge;
import edu.odu.cs.zeil.AlgAE.Client.DataViewer.DataGraph.Edgeable;
import edu.odu.cs.zeil.AlgAE.Client.DataViewer.DataGraph.EdgeList;
import edu.odu.cs.zeil.AlgAE.Client.DataViewer.DataGraph.IDTree;
import edu.odu.cs.zeil.AlgAE.Client.DataViewer.DataGraph.PartialSum;
import edu.odu.cs.zeil.AlgAE.Client.DataViewer.DataGraph.Stub;




/**
 * Labelled nodes, which can be connected to other nodes by directional edges.
 * <P>
 * Each node is drawn as a colored box containing a single line of text.
 * Nodes may also contain other, nested nodes arranged either vertically
 * or horizontally below the text.
 * <P>
 * Each node has 16 possible points from which edges may emanate. These points
 * are named for the points of a compass: <pre>
 *        NNW  N  NNE
 *   NW   ----------  NE
 *        |        |
 *    WNW |        | ENE
 *        |        |
 *      W |        | E
 *        |        |
 *    WSW |        | ESE
 *        |        |
 *   SW   ----------  SE
 *        SSW  S  SSE
 * </pre>
 * Edges are drawn as arrows emanating from one of these points.
 * Edges may be assigned a specific direction from which to emanate. If so,
 * a small black dot is drawn at the point of emanation. "Null" edges can
 * be created that have a direction of emanation (and hence a dot) but no
 * destination node (hence no arrow).  These are useful in portraying null 
 * pointers.
 */
public class Node extends IDTree implements Edgeable
{
  private static Random rnd = new Random();

  /**
   * The label for this node.
   */
  protected String text;

  /**
   * List of incoming edges.
   */
  protected EdgeList inEdges;

  /**
   * List of outgoing edges.
   */
  protected EdgeList outEdges;

  /**
   * Size of this node in pixels.
   */
  private Dimension nodeSize;

  /**
   * Width of this node's text string, in pixels.
   */
  private int stringWidth;

  /**
   * Each node has 3 positions.  <P>
   * The current position is where we would draw it if <code>draw()</code>
   * were called at this moment.  This position will be somewhere on the
   * line segment between its old and its new positions. During an
   * incremental movement sequence, this position is moved progressively
   * closer to the new position, redrawing the graph after each movement.
   *  @see edu.odu.cs.zeil.AlgAE.Client.DataViewer.DataGraph.Graph.initiateMovement
   */
  private Point currentPosition;

  /**
   * Position of the node at the start of an incremental movement.
   */
  private Point oldPosition;

  /**
   * Position of the node at the end of an incremental movement, ususally
   * assigned by the last <code>reposition()</code> call.
   */
  private Point newPosition;

  /**
   * Temporary used for position calculations and debugging
   */
  private Point savedPosition;
  
  /**
   * True if inner components (if any) should be stacked vertically.
   * Otherwise, they are arranged horizontally.
   */
  protected boolean vertical;

  /**
   * The color of this node
   */
  protected Color color;

  /**
   * Mark flag used to track nodes from one frame to another.
   */
  protected boolean marked;
  
  
  /**
   * Timestamp used to determine if stubs must be updated.
   */
  protected int timeStamp;
  

  /**
   * Create a new node.
   *
   * @param theID Unique identifier for this node. It is the caller's
   *              responsibility to provide these IDs and guarantee their
   *              uniqueness.
   * @param theColor  Color in which to draw this node
   * @param isVertical True if any nested nodes contained within this one
   *              should be arranged vertically. False if they should be
   *              arranged horizontally. If there are no nested nodes, this
   *              has no effect.
   */
  public Node(String theID, Color theColor, boolean isVertical)
  {
    super(theID);
    color = theColor;
    currentPosition = oldPosition = newPosition = null;
    nodeSize = new Dimension(1,1);
    savedPosition = new Point();
    text = "";
    inEdges = new EdgeList();
    outEdges = new EdgeList();
    vertical = isVertical;
    marked = true;
    timeStamp = 0;
  }


  /**
   *  Update timestamp to indicate that node has been changed.
   */
  void changed()
  {
    ++timeStamp;
    if (timeStamp > 16000)
      timeStamp = 0;
  }
  

  /**
   * Changes the label associated with this node.
   * @param txt  Text to be printed within the node. Should consist only
   *    of simple printable characters (ASCII 32-126).
   */
  public void setText (String txt)
  {
    text = txt;
    changed();
  }

  /**
   * Changes the vertical/horizontal layout rule for this node
   * @param isVertical  true if components should be stacked vertically
   */
  public void setVertical (boolean isVertical)
  {
    vertical = isVertical;
  }

  /**
     * Get the value of marked.
     * @return Value of marked.
     */
  public boolean getMarked() {return marked;}
  
  /**
     * Set the value of marked in this node and its components.
     * @param v  Value to assign to marked.
     */
  public void setMarked(boolean  v)
  {
    marked = v;
    for (Enumeration e = children(); e.hasMoreElements(); )
      {
	Node n = (Node)e.nextElement();
	n.setMarked (v);
      }
  }
  
  /**
   * Adds an edge from this node to another.
   *  @param destination  Node that the edge points to. May be null.
   *  @param dir    Direction from which the edge leaves this node.
   *                May be ANYDIR if you have no preference.
   *  @param color  Color in which to draw this edge
   *  @param edgeLabel  Text to print along edge (may be null)
   */
  public Edge addEdge (Node destination, int dir,
		       Color color, String edgeLabel)
  {
    Edge e;
    if (destination == null)
	e = new NullEdge (this, dir, color, edgeLabel);
    else if (destination == this)
      {
	e = new SelfEdge (this, dir, color, edgeLabel);
	inEdges.add (e);
      }
    else
      {
	e = new LinearEdge (this, destination, dir, color, edgeLabel);
	destination.inEdges.add (e);
      }
    outEdges.add (e);
    changed();
    return e;
  }


  /**
   * Finds an existing edge from this node.
   *  @param destination  Node that the edge points to. May be null.
   *  @param dir    Direction from which the edge leaves this node.
   *                May be ANYDIR if you have no preference.
   *  @return An existing edge matching the above parameters, or null if no
   *           such edge exists.
   */
  public Edge getEdge (Node destination, int dir)
  {
    return outEdges.find (this, destination, dir);
  }


  /**
   * Finds an existing edge from this node.
   *  @param destination  Node that the edge points to. May be null.
   *  @return An existing edge matching the above parameters, or null if no
   *           such edge exists.
   */
  public Edge getEdge (Node destination)
  {
    return outEdges.find (this, destination);
  }


  /**
   * Finds an existing edge from this node.
   *  @param dir    Direction from which the edge leaves this node.
   *                May be ANYDIR if you have no preference.
   *  @return An existing edge matching the above parameters, or null if no
   *           such edge exists.
   */
  public Edge getEdge (int dir)
  {
    return outEdges.find (dir);
  }
  
  
  

  /**
   * Removes an existing edge from this node.
   *  @param destination  Node that the edge points to. May be null.
   *  @param dir    Direction from which the edge leaves this node.
   *                May be ANYDIR if you have no preference.
   */
  public void removeEdge (Node destination, int dir)
  {
    boolean found = outEdges.remove(this, destination, dir);
    Debug.show(Debug.debug && !found,
	       "Attempt to remove nonexistent edge to node " +
	       destination.ID() + " at dir " + dir);

    if (destination != null) {
      destination.inEdges.remove (this, destination, dir);
    }
    changed();
  }

  /**
   * Removes an existing edge from this node.
   *  @param dir    Direction from which the edge leaves this node.
   */
  public void removeEdge (int dir)
  {
    Edge e = outEdges.find(dir);
    if (e != null)
      {
	outEdges.remove (e);
	if (e.destination != null)
	  {
	    Node dest = (Node)e.destination;
	    dest.inEdges.remove (e);
	  }
	changed();
      }
    else
      Debug.show(Debug.debug,
		 "Attempt to remove nonexistent edge at dir " + dir);
  }

  
  /**
   * Removes all outgoing edges from this node.
   */
  public void clearOutEdges ()
  {
    Edge e;
    for (Enumeration i = outEdges.edges(); i.hasMoreElements(); )
      {
	e = (Edge)(i.nextElement());
	if (e.destination != null)
	  {
	    Node dest = (Node)e.destination;
	    dest.inEdges.remove (e);
	  }
      }
    outEdges.clear();
    changed();
  }

  /**
   * Removes all incoming edges from this node.
   */
  public void clearInEdges ()
  {
    Edge e;
    for (Enumeration i = inEdges.edges(); i.hasMoreElements(); )
      {
	e = (Edge)(i.nextElement());
	Node src = (Node)e.source;
	src.outEdges.remove (e);
      }
    inEdges.clear();
    changed();
  }



  /**
   * Removes all nested components from this node.
   */
  public void clearComponents ()
  {
    IDTree graph = this;
    while (graph.parent() != null)
      graph = graph.parent();
    
    while (children().hasMoreElements())
      {
	Enumeration e = children();
	Node child = (Node)e.nextElement();
	child.isolate();
	graph.add (child);
      }
    changed();
  }



  /**
   * Draw the node (but not its edges).
   *  @param gi Graphics context information
   */
  void draw (GraphicsInfo gi)
  {
      Point currentPos = position();
	
      Graphics g = gi.g;
      g.setColor (color);
      g.fillRect (currentPos.x, currentPos.y,
		  nodeSize.width, nodeSize.height);
      int brightness = color.getRed() +
	  3 * color.getGreen() / 2 + color.getBlue();
      if (brightness >= 256+128) {
	  g.setColor (Color.black);
      }
      else {
	  g.setColor (Color.white);
      }
      if (text.length() > 0)
	  g.drawString (text,
		        currentPos.x + (nodeSize.width - stringWidth)/2,
		        currentPos.y + 3*gi.getTextOffset().height);
      
      // Draw the inner components, if any
      for (Enumeration e = children(); e.hasMoreElements(); )
	  {
	      Node child = (Node)(e.nextElement());
	      child.draw(gi);
	  }
      
  }
  
  

  /**
   * Draw the edges emanating from this node.
   *  @param gi Graphics context information
   */
  void drawEdges(GraphicsInfo gi)
  {
      Graphics g = gi.g;
      for (Enumeration ei = outEdges.edges(); ei.hasMoreElements();)
	  {
	      Edge e = (Edge)(ei.nextElement());
	      e.draw (gi);
	  }

      // Draw edges from the inner components, if any
      for (Enumeration e = children(); e.hasMoreElements(); )
	  {
	      Node child = (Node)(e.nextElement());
	      child.drawEdges(gi);
	  }
  }
  

  /**
   * Compute the size of this node, given its current label and nested
   * components.  The result is stored in the node's <code>nodeSize</code> data
   * member.
   *  @param gi Graphics context information
   */
  void computeSize(GraphicsInfo gi)
  {
    nodeSize.width = gi.getTextOffset().width;