/* SibTree.java */

package tree;

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

public class SibTree implements Tree {

  /**
   * ADT implementation invariants:
   *
   *   Definition: SibTreeNode y is said to be a 'sibling of' 
   *                  SibTreeNode x if:
   *      1) x.nextSibling == y, or 
   *      2) y is a sibling of x.nextSibling
   *   Definition: SibTreeNode y is said to be a 'descendent of' 
   *                  SibTreeNode x if:
   *      1) x == y, or 
   *      2) y is a descendent of x.firstChild, or 
   *      3) y is a descendent 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 descendent of this.root
   *
   * 1) if root != null, then root.live == true; and root.parent == null.
   * 2) for any SibTreeNode x in SibTree 'this' x.live == 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, if x.live == true, then x is in some SibTree.
   */

  SibTreeNode root;
  int size;

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

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

  /**
   * isEmpty() returns true if the Tree has no nodes; false otherwise.
   */
  public boolean isEmpty() {
    return size == 0;
  }

  /**
   * size() returns the number of nodes in the Tree.
   */
  public int size() {
    return size;
  }

  /**
   * root() constructs a TreePosition that refers to the root node.  Returns
   * an invalid position if the tree is empty.
   */
  public TreePosition root() {
    return new SibTreePosition(this);
  }

  /**
   * insertRoot() inserts a node containing "value" at the root of the tree.
   * If a root already exists, it becomes a child of the node containing
   * "value".
   */
  public void insertRoot(Object value) {
    SibTreeNode newRoot = new SibTreeNode(value);
    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) {
    TreePosition r, r1, r2, r3, r31, r32;

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

    // Set positions at the nodes.
    r = t.root();
    r1 = null;
    try {
      r1 = r.child(1);
    } catch (Exception e) {
    }


    // Does parent() work?
    System.out.println("Testing parent().");
    try {
      if (!r.equals(r1.parent())) {
        System.out.println("  Error:  parent of leaf node's child is" +
                           " incorrect.");
      }
    } catch (NoSuchTreePosition e) {
      System.out.println("  Error:  parent() threw interrupt on valid node.");
    }
    try {
      TreePosition stp = r.child(2).parent();
      System.out.println("  Error:  parent() failed to throw interrupt on" +
                         " invalid node.");
    } catch (NoSuchTreePosition e) {
    }


    // Add more nodes to tree.
    System.out.println("Adding four 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.elementAt()).intValue() != 12) {
        System.out.println("  Error:  Second child of root does not contain" +
                           " the correct key, 12.");
      }
      if (((Integer) r3.elementAt()).intValue() != 13) {
        System.out.println("  Error:  Third child of root does not contain" +
                           " the correct key, 13.");
      }
      if (!r2.parent().equals(r)) {
        System.out.println("  Error:  Second child of root does not think" +
                           " the root is its parent.");
      }
      if (!r3.parent().equals(r)) {
        System.out.println("  Error:  Third child of root does not think" +
                           " the root is its parent.");
      }
      r3.insertChild(new Integer(132), 1);
      r3.insertChild(new Integer(131), 1);
      r31 = r3.child(1);
      r32 = r3.child(2);
      if (((Integer) r31.elementAt()).intValue() != 131) {
        System.out.println("  Error:  Node r31 does not contain" +
                           " the correct key, 131.");
      }
      if (((Integer) r32.elementAt()).intValue() != 132) {
        System.out.println("  Error:  Node r32 does not contain" +
                           " the correct key, 132.");
      }
      if (!r31.parent().equals(r3)) {
        System.out.println("  Error:  Node r31 does not think" +
                           " Node r3 is its parent.");
      }
      if (!r32.parent().equals(r3)) {
        System.out.println("  Error:  Node r32 does not think" +
                           " Node r3 is its parent.");
      }
    } catch (NoSuchTreePosition e) {
      System.out.println("  Error:  unexpected exception while adding and" +
                         " testing nodes.");
      System.exit(1);
    }
    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.]");


    System.out.println("Removing one node from 6-node tree.");
    try {
      r1.removeLeaf();
    } catch (Exception e) {
      System.out.println("  Error:  unexpected exception while removing.");
    }
    if (r1.isValidPosition()) {
      System.out.println("  Error:  the deleted position 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.equals(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.isValidPosition()) {
      System.out.println("  Error:  Node r3 still has a second child.");
    }


    System.out.println("Attempting to remove non-leaf node from 4-node tree.");
    try {
      r3.removeLeaf();
      System.out.println("  Error:  removeLeaf() failed to throw exception.");
    } catch (NoSuchTreePosition e) {
      System.out.println("  Error:  removeLeaf() threw wrong exception.");
    } catch (BadOperation e) {
      System.out.println("  Failed...good.");
    }

    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 (BadOperation e) {
      System.out.println("  Error:  removeLeaf() threw wrong exception.");
    } catch (NoSuchTreePosition e) {
      System.out.println("  Failed...good.");
    }


    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.isValidPosition()) {
      System.out.println("  Error:  the root should be invalid.");
    }
  }

}