/*
   FullTree.java

   A simple general tree implementation
   A Vector is used to hold the children of each node.
   MAH 10/19/01

   */

import java.util.*; // contains the Vector class
import java.io.*;  // allows us to read in files

public class FullTree {

    // instance variables
    private String name;        // data to store in the node
    private  int        value;       // data to store in the node
    private  Vector children; // the children of the node

    // constructor
    FullTree () {
        name = "default";
        value  = 0;
        children = new Vector();
    }

    // constructor
    FullTree (String n, int v) {
        name = n;
        value = v;
        children = new Vector();
    }

   // Use the Vector addElement method to add a child
    public void addChild(FullTree tree) {
        children.addElement(tree);
    }



// Use this method as a helper for building up a string of indentations
// of the appropriate length.
private static StringBuffer getIndents (int level) {
    StringBuffer indent=new StringBuffer();
          for(int i=0;i<level;i++)
           indent.append("  ");
     return indent;
}


// Breadth First Traversal of the FullTree
public void BFTraversal () {

              Queue queue = new Queue();
              queue.enQueue(this);
              BFTraversalHelper(queue);
}

    // Note this is not recursive; we use the queue instead.
    // Note also that this code assumes the "value" stored in
    // each node represents the node's depth in the tree.   Indenting
    // will not work correctly if this is not the case.
    private void BFTraversalHelper(Queue queue) {

         FullTree t;
         FullTree child;
         // this is for debugging only
         //  System.out.println("Contents of the queue");
         //  queue.printQueue();

          while ((t = (FullTree) queue.deQueue()) != null) {

                System.out.println(getIndents(t.value) + t.name);
                // The enumeration lets us get to all the elements in the children Vector
                // The main methods used by Enumeration are
                // elements(), hasMoreElements() and nextElement()
                Enumeration e = t.children.elements();
                while (e.hasMoreElements()) {
                    child = (FullTree) e.nextElement();
                    queue.enQueue(child);
                 }
             }
       }


// This works with buildFullTreeFromFile to build up a tree
// from a list of (parent,child) pairs
// If it can't find the parent in the current tree, then the child
// is not added and the method returns false.
// If it does find the parent, it adds the child and returns true.

   public boolean addChildToParent(FullTree child, String parent) {

          if (this.name.equals( parent) ) {
              if (!this.children.contains(child)) {
                  this.addChild(child);
              }
              return true;
          } else {
              Enumeration e = this.children.elements();
              while (e.hasMoreElements()) {
                  FullTree t = (FullTree) e.nextElement();
                    if (t.addChildToParent(child, parent)) {
                          return true;
                     }
              }
       }
       return false;
    }

    /* This method reads in a file and produces a FullTree based on the contents of the file.
       The format of the file is a list of lines of the format:
               parentName | childName | childValue
        A parent name has to appear before any of its children; otherwise that parent will
        not get entered, neither will any of its children.  Note that by default the root is called "root".

       In the example file "treefile" the children's value represents their level number
      This makes printing out with indentations easier.
       One way to change this code is to add a String data value to the FullTree type
     This would allow you to store a string such as a URL along with each node.
     */

     public static FullTree buildFullTreeFromFile(String FileName) {

      FullTree root = new FullTree("root",0);
      String str;
      try {
                  BufferedReader fin = new BufferedReader(new FileReader (FileName));

                  while ((str=fin.readLine())!=null) {
                          String parentName = "";
                          String childName = "";
                          int childValue = 0;
                            StringTokenizer st = new StringTokenizer(str, "|");
                             if (st.hasMoreTokens())
                                    parentName = st.nextToken();
                              if (st.hasMoreTokens())
                                      childName = st.nextToken();
                              if (st.hasMoreTokens())
                                      childValue = Integer.parseInt(st.nextToken());

                               FullTree child = new FullTree(childName, childValue);

                             if (!root.addChildToParent(child,parentName)) {
                                System.out.println("Failed to enter " + childName + " as child of " + parentName);
                             }
                    }
                    fin.close();
         }
         catch (Exception ioe) {
            System.err.println("FullTree: " + ioe.toString());
            System.exit(1);
        }
        return root;

  }

  private static void makeExampleTree () {

          // These lines show how to build up a tree "manually"
          // The value is being used to indicate the level number

              FullTree root = new FullTree("root", 0);
              FullTree a      = new FullTree("a", 1);
              FullTree b        = new FullTree("b", 1);
              a.addChild(new FullTree("aa", 2));
              a.addChild(new FullTree("ab",2));
              b.addChild(new FullTree("ba",2));
              b.addChild(new FullTree("bb",2));
              root.addChild(a);
              root.addChild(b);
              root.addChildToParent(new FullTree("bbb",3),"bb");

               System.out.println("Printing BFS");
               root.BFTraversal();

               /*Need to add code to support this!
                  System.out.println("Printing DFTraversal");
                   root.DFTraversal();
               */
  }

    public static void main (String args[]) {

         makeExampleTree();

        // These lines show how to build up a tree from a file
        // and then use the resulting tree.
        FullTree ft = buildFullTreeFromFile("treefile.txt");

        System.out.println("Printing BFS");
        ft.BFTraversal();

        /* need to add code to support this!
         System.out.println("Printing DFTraversal");
         ft.DFTraversal();
         */

    }

}