/*****************************************************************************/
/*                                                                           */
/*                  Sets Test program: Graphical Version                     */
/*                                                                           */
/*                     February 1998, Toshimi Minoura                        */
/*                     November 1999, Jacob Lundberg                         */
/*                                                                           */
/*****************************************************************************/

import java.awt.*;

// Nodes are stored in nodes[] in class SetG.
// A Node belongs to the same class with its parent Node.
// A Node with its parentIdx = -1 is the root Node of a set.
 
class SetsG extends StepTestCanvas {

  class Node {
    int parentIdx;               // array index of parent Node
    int height;                  // height of node in tree
    public Object value;         // value of this node
    boolean focus;
    int xLoc;
    int yLoc;
  
    Node(Object val) {           // constructor
      parentIdx = -1;            // initially a singleton set
      height = 1;
      value = val;               // copy argument
      focus = false;             // initially highlighted
    }
  
    public String toString() {   // create String representation for node
      return "node with parent = " + parentIdx + ", value = " + value;
    } 
  }

  static final int TableSize = 100;   // size of nodes[]
  private Node nodes[];              // storage for Node data
  int currentIdx = -1;               // index for node currently being visited

  public SetsG() {                   // constructor
    nodes = new Node[TableSize];
  }

  public void setNode(int nodeIdx, Object value) {
    nodes[nodeIdx] = new Node(value);
    repaintStep("New node created for nodeIdx = " + nodeIdx + ": "
                 + nodes[nodeIdx]);
  }

  // recalculate heights of all nodes
  // after a find any number of nodes in a set may have incorrect heights
  private void calcHeights() {
    int counter;
    int token;
    for( counter = 0 ; counter < TableSize ; counter++ )
      if( nodes[counter] != null )
        nodes[counter].height = 0;
    for( --counter ; counter >= 0 ; counter-- )
      if( nodes[counter] != null && nodes[counter].height == 0 ) {
        // leaf node so we calculate on up the tree
        token = counter;
        nodes[token].height = 1;
        while( nodes[token].parentIdx >= 0 ) {
          if( nodes[token].height >= nodes[nodes[token].parentIdx].height )
            nodes[nodes[token].parentIdx].height = nodes[token].height + 1;
          token = nodes[token].parentIdx;
        }
      }
//    repaintStep( "Heights of all nodes have been recalculated." );
    System.out.println( "Heights of all nodes recalculated." );
  }

  // perform a set union on sets with index setIdx1 and setIdx2
  // make the shallower set a child of the deeper set
  public void union(int setIdx1, int setIdx2) {

    // always place the shallow tree into the deep tree
    if( nodes[setIdx1].height < nodes[setIdx2].height ) {
      union( setIdx2, setIdx1 );
      return;
    } else if( nodes[setIdx1].height == nodes[setIdx2].height ) {
      // special case where heights are equal so set1 will get higher
      ++nodes[setIdx1].height;
    }
    currentIdx = setIdx1;                // highlight new set root node
    nodes[setIdx2].focus = true;         // highlight set member node
    repaintStep("Set " + setIdx2 + " will be added to set " + setIdx1);
    nodes[setIdx2].parentIdx = setIdx1;  // add set setIdx2 to set setIdx1

    repaintStep("Set " + setIdx2 + " was added to set " + setIdx1);
    currentIdx = -1;                     // unhighlight new set root node
    nodes[setIdx2].focus = false;        // unhighlight set member node
  }

  // merge set including node nodeIdx1 and set including node nodeIdx2
  public void join(int nodeIdx1, int nodeIdx2) {
    nodes[nodeIdx1].focus = true;        // highlight member node
    nodes[nodeIdx2].focus = true;        // highlight member node
    repaintStep("Set including node " + nodeIdx1 + 
           " and set including node " + nodeIdx2 + " will be merged.");
    int setIdx1 = findSet(nodeIdx1, false); // find set including node nodeIdx1
    int setIdx2 = findSet(nodeIdx2, false); // find set including node nodeIdx2
    nodes[nodeIdx1].focus = false;       // unhighlight
    nodes[nodeIdx2].focus = false;       // unhighlight 
    union( setIdx1, setIdx2 );
  }

  // find set index for node with nodeIdx
  public int findSet(int nodeIdx) {
    int setIdx;
    nodes[nodeIdx].focus = true;           // highlight member node
    repaintStep("Set will be found for node " + nodeIdx);
    if (nodes[nodeIdx].parentIdx == -1) {  // no parent node, root node
      nodes[nodeIdx].focus = false;        // unhighlight member node
      setIdx = nodeIdx;                    // set index found
      calcHeights();
    } else {
      setIdx = findSet(nodes[nodeIdx].parentIdx, true);
      nodes[nodeIdx].parentIdx = setIdx;   // put current node under set root
    }
    currentIdx = setIdx;             // highlight set root node
    repaintStep("Node " + nodeIdx + " is in set " + setIdx);
    nodes[nodeIdx].focus = false;    // unhighlight member node
    currentIdx = -1;                 // unhighlight set root node
    return setIdx;
  }

  public int findSet(int nodeIdx, boolean pause) {
    int setIdx;                         // node index of set root node
    System.out.println("SetsG.findSet() called for nodeIdx = " + nodeIdx);
    if (nodes[nodeIdx] == null) {
      System.out.println("Node with nodeIdx = " + nodeIdx +
                         " does not exist.");
      return -1;
    }
    if (pause) {
      currentIdx = nodeIdx;             // highlight parent node
      repaintStep("Parent node visited: nodeIdx = " + nodeIdx);
    }
    if (nodes[nodeIdx].parentIdx == -1) {
      setIdx = nodeIdx;                 // set root node found
      calcHeights();
    } else {
      setIdx = findSet(nodes[nodeIdx].parentIdx, pause);   // recursive call
      nodes[nodeIdx].parentIdx = setIdx;  // put current node under set root
    }
    return setIdx;                        // return set index for given node
  }

  static final int TableXLoc = 20;   // left margin on Canvas
  static final int TableYLoc = 20;   // right margin on Canvas

  static final int NodeWidth  = 50;  // width of node drawn
  static final int NodeHeight = 30;  // height of node drawn
  static final int YGap = 50;        // vertical gap between nodes

  // Calcuclate xLoc and yLoc for each node in subtree under node with
  // nodeIdx. The left-top corner of the subtree is at (x, y).

  public int calcXY(int nodeIdx, int x, int y) {
    int subtreeWidth = 0;
    for (int childIdx = 0; childIdx < TableSize; childIdx++) {
      if (nodes[childIdx] != null && nodes[childIdx].parentIdx == nodeIdx) {
        subtreeWidth += calcXY(childIdx, x + subtreeWidth, y + YGap);
      }  // adjust x for each subtree by the widths of preceding subtrees
    }
    if (subtreeWidth == 0) {
      subtreeWidth = NodeWidth * 3 / 2;    // width of area for one node
    }
    nodes[nodeIdx].xLoc = x + subtreeWidth / 2;  // put this node in center
    nodes[nodeIdx].yLoc = y;
    return subtreeWidth;
  }

  Font f = new Font("TimesRoman", Font.BOLD, 18);

  public void paint(Graphics g) {
//  System.out.println("SetsG.paint() entered");
    g.setFont(f);                   // set font for letters

    int x = TableXLoc + NodeWidth / 2;   // x of center of leftmost node
    int y = TableYLoc + NodeHeight / 2;  // y of center of top-most node

    for (int childIdx = 0; childIdx < TableSize; childIdx++) {
      if (nodes[childIdx] != null && nodes[childIdx].parentIdx == -1) { // root
        x += calcXY(childIdx, x, y);     // add width of each subtree
      }
    }

    for (int nodeIdx = 0; nodeIdx < TableSize; nodeIdx++) {
      if (nodes[nodeIdx] != null && nodes[nodeIdx].parentIdx == -1) {
        draw(nodeIdx, g);                // draw each subtree
      }
    }
  }

  static Color LineColor = new Color(0, 0, 0);
  static final Color OutlineColor = new Color(100, 0, 0);   // for node outline
  static Color NodeColor = new Color(0, 100, 0);
  static Color VisitedNodeColor = new Color(150, 255, 0);
  static Color NewNodeColor = new Color(255, 225, 0);

  // draw the subtree rooted at nodes[nodeIdx] in rectangle area
  // coordinates of whose left-top corner are (xLoc, yLoc).
  // The return value is the width of the subtree drawn.

  public void draw(int nodeIdx, Graphics g) {

    for (int childIdx = 0; childIdx < TableSize; childIdx++) {
      if (nodes[childIdx] != null && nodes[childIdx].parentIdx == nodeIdx) {
        draw(childIdx, g);
      }
    }

    if (nodes[nodeIdx].parentIdx != -1) {
      g.setColor(LineColor);           // draw line to parent node
      g.drawLine(nodes[nodeIdx].xLoc, nodes[nodeIdx].yLoc,
                 nodes[nodes[nodeIdx].parentIdx].xLoc,
                 nodes[nodes[nodeIdx].parentIdx].yLoc);
    }

    if (nodes[nodeIdx].focus) {
      g.setColor(NewNodeColor);        // set color for new Node
    } else if (currentIdx == nodeIdx) {
      g.setColor(VisitedNodeColor);    // set color for Node visited
    } else {
      g.setColor(NodeColor);           // color for other Nodes
    }
    g.fillOval(nodes[nodeIdx].xLoc - NodeWidth / 2, 
       nodes[nodeIdx].yLoc - NodeHeight / 2, NodeWidth, NodeHeight);
    g.setColor(OutlineColor);
    g.drawOval(nodes[nodeIdx].xLoc - NodeWidth / 2, 
       nodes[nodeIdx].yLoc - NodeHeight / 2, NodeWidth, NodeHeight);
    if (currentIdx == nodeIdx || nodes[nodeIdx].focus) {
      g.setColor(Color.blue);          // set color for node label
    } else {
      g.setColor(Color.white);         // for other node
    }
    g.drawString("" + nodeIdx, nodes[nodeIdx].xLoc - 4,
                               nodes[nodeIdx].yLoc + 6); 
  }

  public static void main(String argv[]) {
    new StepTestFrame("Sets Manipulation", new SetsG(),
                       900, 350).show();
  }
 
  public void reset() {
    for (int i = 0; i < TableSize; i++) {
      nodes[i] = null;               // initially no Node
    }
  }

  public void runMain() {             // called from run() of StepTestCanvas
    System.out.println("SetsG.runMain() entered");
    reset();
    repaintStep();

    int i = 0;                        // counter
    char charX = 'A';    

    setNode(i++, "" + charX++);
    setNode(i++, "" + charX++);
    setNode(i++, "" + charX++);
    setNode(i++, "" + charX++);
    setNode(i++, "" + charX++);
    setNode(i++, "" + charX++);
    setNode(i++, "" + charX++);
    setNode(i++, "" + charX++);
    setNode(i++, "" + charX++);
    setNode(i++, "" + charX++);

    join(0, 1);
    join(2, 3);
    join(4, 5);
    join(2, 4);
    join(5, 6);
    repaintStep( "state1" );

    join(8, 7);
    repaintStep( "findSet(4) == " + findSet(4) + "." );
    join(7, 5);
    repaintStep( "state2" );

    join(2, 9);
    repaintStep( "findSet(6) == " + findSet(6) + "." );
    repaintStep( "state3" );

    repaintStep( "Execution of runMain() completed successfully." );
    System.out.println("runMain() completed");
  }  
}