/* SibTree.java */

package tree;

/**
 *  The SibTree class implements general trees using linked nodes.  Each node
 *  has pointers to its parent, its first (leftmost) child, and its sibling to
 *  the immediate right.
 *  @author Jonathan Shewchuk
 */

public class SibTree extends Tree {

  /**
   *  (inherited)  size is the number of items in the tree.
   *  root is the tree's root node.
   **/

  SibTreeNode root;

  /**
   *  ADT implementation invariants:
   *
   *    Definition:  SibTreeNode y is a "sibling of" SibTreeNode x if
   *      1) x.nextSibling == y, or 
   *      2) y is a sibling of x.nextSibling
   *    Definition:  SibTreeNode y is a "descendant of" SibTreeNode x if
   *      1) x == y, or 
   *      2) y is a descendant of x.firstChild, or 
   *      3) y is a descendant of some SibTreeNode z and 
   *             z is a sibling of x.firstChild
   *    Definition:  a SibTreeNode x is said to be "in" SibTree "this" if
   *             x is a descendant of this.root
   *
   *  1) if root != null, then root.valid == true, and root.parent == null.
   *  2) for any SibTreeNode x in SibTree "this", x.valid == true.
   *  3) for any SibTreeNodes x and y in SibTree "this", if
   *             x.firstChild == y or y is a sibling of x.firstChild, then 
   *             y.parent == x.
   *  4) for any SibTreeNodes x and y in SibTree "this", if x.parent == y, then
   *             y.firstChild == x or x is a sibling of y.firstChild.
   *  5) for any SibTreeNode x in SibTree "this", if x.parent == null, then
   *             x == root.
   *  6) "size" is the number of nodes in SibTree "this".
   *  7) for any SibTreeNode x in SibTree "this", x satisfies all the
   *             invariants of SibTreeNode (listed in SibTreeNode.java).
   */

  /**
   * Construct an empty SibTree.
   */
  public SibTree() {
    root = null;
    size = 0;
  }

  /**
   * Construct a one-node SibTree.
   */
  public SibTree(Object item) {
    root = new SibTreeNode(this, item);
    size = 1;
  }

  /**
   *  root() returns the root node, if one exists.  Returns an invalid node if
   *  the tree is empty.
   */
  public TreeNode root() {
    if (root == null) {
      return new SibTreeNode();
    } else {
      return root;
    }
  }

  /**
   *  insertRoot() inserts a node containing "item" at the root of the tree.
   *  If a root already exists, it becomes a child of the new node.
   */
  public void insertRoot(Object item) {
    SibTreeNode newRoot = new SibTreeNode(this, item);
    newRoot.firstChild = root;
    if (root != null) {
      root.parent = newRoot;
    }
    root = newRoot;
    size++;
  }

  /**
   * toString() returns a string representation of the SibTree.
   */
  public String toString() {
    return preorderString(root, 0);
  }

  private String preorderString(SibTreeNode currentNode, int depth) {
    if (currentNode == null) {
      return "";
    }
    String s = "";
    for (int i = 0; i < depth; i++) {
      s = s + "  ";
    }
    return s + currentNode.item + "\n" +
           preorderString(currentNode.firstChild, depth + 1) +
           preorderString(currentNode.nextSibling, depth);
  }

  /**
   * main() contains mounds and mounds of icky test code.
   */
  public static void main(String[] args) {
    TreeNode r, r1, r2, r3, r31, r32;

    // Create two-node tree.
    Tree t = new SibTree(new Integer(11));
    t.insertRoot(new Integer(1));
    System.out.println("Creating 2-node tree.");

    // Reference the nodes.
    r = t.root();
    r1 = null;
    try {
      r1 = r.child(1);
    } catch (InvalidNodeException e) {
    }

    // Does parent() work?
    System.out.println("Testing parent().");
    try {
      if (r != r1.parent()) {
        System.out.println("  ERROR:  parent of root node's child is" +
                           " not the root, but should be.");
      }
      if (r.parent() == null) {
        System.out.println("  ERROR:  parent() returned null.");
      } else if (r.parent().isValidNode()) {
        System.out.println("  ERROR:  parent() of root is valid," +
                           " but shouldn't be.");
      }
    } catch (Exception e) {
      System.out.println("  ERROR:  parent() threw interrupt on valid node.");
    }
    try {
      TreeNode stp = r.child(2).parent();
      System.out.println("  ERROR:  parent() failed to throw exception on" +
                         " invalid node.");
    } catch (InvalidNodeException e) {
    }

    // Add more nodes to tree.
    System.out.println("\nTesting insertChild()." +
                       "  Adding two more nodes to the 2-node tree.");
    r2 = null;
    r3 = null;
    r31 = null;
    r32 = null;
    try {
      r.insertChild(new Integer(13), 1000);
      r.insertChild(new Integer(12), 2);
      r2 = r.child(2);
      r3 = r.child(3);
      if (((Integer) r2.item()).intValue() != 12) {
        System.out.println("  ERROR:  Second child of root does not contain" +
                           " the correct key, 12.");
      }
      if (((Integer) r3.item()).intValue() != 13) {
        System.out.println("  ERROR:  Third child of root does not contain" +
                           " the correct key, 13.");
      }
      if (r2.parent() != r) {
        System.out.println("  ERROR:  Second child of root does not think" +
                           " the root is its parent.");
      }
      if (r3.parent() != r) {
        System.out.println("  ERROR:  Third child of root does not think" +
                           " the root is its parent.");
      }
      if (r2.nextSibling() != r3) {
        System.out.println("  ERROR:  Second child of root does not think" +
                           " the root's third child is its next sibling.");
      }
      if (r3.nextSibling().isValidNode()) {
        System.out.println("  ERROR:  Third child of root thinks it has" +
                           " a next sibling.");
      }

      System.out.println("Adding two more nodes to the 4-node tree.");
      r3.insertChild(new Integer(132), 1);
      r3.insertChild(new Integer(131), 1);
      r31 = r3.child(1);
      r32 = r3.child(2);
      if (((Integer) r31.item()).intValue() != 131) {
        System.out.println("  ERROR:  Node r31 does not contain" +
                           " the correct key, 131.");
      }
      if (((Integer) r32.item()).intValue() != 132) {
        System.out.println("  ERROR:  Node r32 does not contain" +
                           " the correct key, 132.");
      }
      if (r31.parent() != r3) {
        System.out.println("  ERROR:  Node r31 does not think" +
                           " Node r3 is its parent.");
      }
      if (r32.parent() != r3) {
        System.out.println("  ERROR:  Node r32 does not think" +
                           " Node r3 is its parent.");
      }
      if (r31.nextSibling() != r32) {
        System.out.println("  ERROR:  Node r31 does not think" +
                           " Node r32 is its next sibling.");
      }
      if (r32.nextSibling().isValidNode()) {
        System.out.println("  ERROR:  Node r32 thinks it has a next sibling.");
      }
    } catch (Exception e) {
      System.out.println("  ERROR:  unexpected exception while adding and" +
                         " testing nodes.");
      //      System.exit(1);
    }
    try {
      if (r.parent() == null) {
        System.out.println("  ERROR:  parent() returned null.");
      } else {
        r.parent().insertChild(new Integer(0), 1);
        System.out.println("  ERROR:  insertChild() failed to throw" +
                           " exception on invalid node.");
      }
    } catch (InvalidNodeException e) {
    }
    if (t.size() != 6) {
      System.out.println("  ERROR:  tree size is " + t.size() +
                         " but should be 6.");
    }


    System.out.println("The tree looks like this:");
    System.out.print(t.toString());
    System.out.println("[The above sequence should be" +
                       " 1, 11, 12, 13, 131, 132.]");


    // Remove nodes from tree.
    System.out.println("\nTesting removeLeaf()." +
                       "  Removing one node from 6-node tree.");
    try {
      r1.removeLeaf();
    } catch (Exception e) {
      System.out.println("  ERROR:  unexpected exception while removing.");
    }
    if (r1.isValidNode()) {
      System.out.println("  ERROR:  the removed node should be invalid.");
    }
    if (t.size() != 5) {
      System.out.println("  ERROR:  tree size is " + t.size() +
                         " but should be 5.");
    }
    try {
      r1 = r.child(1);
    } catch (Exception e) {
    }
    if (r1 != r2) {
      System.out.println("  ERROR:  after deleting Node r1, Node r2 has" +
                         " not become the first child of the root.");
    }


    System.out.println("Removing another node from 5-node tree.");
    try {
      r32.removeLeaf();
    } catch (Exception e) {
      System.out.println("  ERROR:  unexpected exception while removing.");
    }
    if (t.size() != 4) {
      System.out.println("  ERROR:  tree size is " + t.size() +
                         " but should be 4.");
    }
    try {
      r32 = r3.child(2);
    } catch (Exception e) {
    }
    if (r32.isValidNode()) {
      System.out.println("  ERROR:  Node r3 still has a second child.");
    }
    try {
      r32 = r31.nextSibling();
    } catch (Exception e) {
    }
    if (r32.isValidNode()) {
      System.out.println("  ERROR:  Node r31 still has a next sibling.");
    }


    System.out.println("Attempting to remove non-leaf node from 4-node tree.");
    System.out.println("  Operation should have no effect.");
    try {
      r3.removeLeaf();
      if (!r3.isValidNode()) {
        System.out.println("  ERROR:  removed non-leaf is invalid.");
      }
      if (r.child(2) != r3) {
        System.out.println("  ERROR:  removed non-leaf is no longer" +
                           " the root's second child.");
      }
    } catch (Exception e) {
      System.out.println("  ERROR:  removeLeaf() threw exception.");
    }

    System.out.println("Attempting to remove invalid node from 4-node tree.");
    try {
      r32.removeLeaf();
      System.out.println("  ERROR:  removeLeaf() failed to throw exception.");
    } catch (InvalidNodeException e) {
    }


    System.out.println("The tree looks like this:");
    System.out.print(t.toString());
    System.out.println("[The above sequence should be" +
                       " 1, 12, 13, 131.]");


    System.out.println("Removing remaining nodes from 4-node tree.");
    try {
      r31.removeLeaf();
      r2.removeLeaf();
      r3.removeLeaf();
      r.removeLeaf();
    } catch (Exception e) {
      System.out.println("  ERROR:  unexpected exception while removing.");
    }
    if (t.size() != 0) {
      System.out.println("  ERROR:  tree size is " + t.size() +
                         " but should be zero.");
    }
    r = t.root();
    if (r.isValidNode()) {
      System.out.println("  ERROR:  the root should be invalid.");
    }
  }

}