// A small program to help you prepare for the midterm!
// Make sure you understand it, make changes -- try to predict
// what the output will be given some changes, explore the questions I've posed...
// This is the program presented in class today to implement some of the functionality
// required for a Treemap.

import java.util.Vector;
import java.util.Enumeration;

public class TreeMap {
	
	 TreeNode root; // root node in our treemap


     
     // constructor
     public TreeMap() {
            // create the root node
            root = new TreeNode();
            int level1 = 2; // num of children at level 1
            int level2 = 3; // num of children at level 2
            System.out.println("Printing the branching factor for each level "
            	+ level1 + " " + level2);   // try adding a third level to the tree!
     		
     		// How would we create a tree recursively given
     		// the number of levels and the branching factor?
      		for (int i=0; i<level1; i++) {
                  // note TreeNode is a nested private class, see below
                  TreeNode t2 = new TreeNode();  
                  t2.data = level1;                     
                  root.addChild(t2);              

                  for (int j=0; j<level2; j++) {
                        TreeNode t3 = new TreeNode(); 
                        t3.data = level2;                
                        t2.addChild(t3);
                  }
            }     
      }     

      private int calculateDescendents(TreeNode root) {             
            int descendents = 0;
            // store the children using a Vector  -- why use a Vector? why not an array?
            Vector children = root.getChildren();                            
            for (int i=0; i<children.size(); i++) {                           
                  TreeNode child = (TreeNode) children.elementAt(i);
                  // recursive call, what is the stopping condition?
                  descendents += calculateDescendents(child);
            }

            root.setNumDescendents(descendents); 
            // debug print statement here to check if it is working!         
            System.out.println("The number of descendents for this node is: "
                  		+ descendents);
           return descendents + 1; //we add one for this element, 
            						// if we don't add one what happens?
      } 
      
     
      // try adding a postorder traversal
      private class PreOrderIterator implements Enumeration {
   			private int curNode;
   			private Vector pre;
   			private int curSize;

   			public PreOrderIterator() {
      			pre = new Vector();
      			curNode = 0;
      			curSize = 0;
      			preorder(root); // populate our vector with the order we want
      			curNode = 0;
   			}
   		
   			// if we added a postorder traversal we wouldn't have to change
   			// this method very much....
   			// for a levelorder it would be very different..... see the class notes
   			// that gives pseudocode for the different traversals
   			// and finally what about printing an euler tour?
   	   		private void preorder(TreeNode t) {
   				if (t != null) {
      				pre.add(t);
      				curNode++; curSize++;
      				Vector children = t.getChildren();
      				for (int i=0; i<children.size(); i++) {                           
                  		TreeNode child = (TreeNode)children.elementAt(i);
                  		preorder(child);
            		}
   				}
   	   		}
   	   		
			public boolean hasMoreElements() {
   				return curNode < curSize;
			}
			public Object nextElement() {
   				return pre.elementAt(curNode++);
			}

	   } // end of private class
	
	   // return a preorder traversal iterator, just like assignment #2
       public Enumeration preIterator() {
        	return new PreOrderIterator();
       }
    		 
      // what is the advantage of having this class private?   
      // why not put in a separate file and class?
      private class TreeNode{
            private Vector children;
            private int numDescendents;
            private TreeNode parent;
            private int data;
            public TreeNode () {
                  children = new Vector();
                  numDescendents = 0;
            }
            public void addChild(TreeNode child) {
            	try { 
            		child.setParent(this);
    			} catch(NullParentException e) {
        			e.printStackTrace(System.err);
    			}
                children.add(child);              
            }

            public Vector getChildren() {
                  return children;
            }

            public TreeNode getParent() {
                  return this.parent;
            }
            // I added an exception in case someone misuses the addChild method 
            // Try writing some code in the addChild method that will cause this exception
            // to be thrown...   How would you add an exception to stop someone
            // from adding a null child
            public void setParent(TreeNode parent) throws NullParentException {
            	  if ( parent == null ) {
            	  		throw new NullParentException("can't have a null parent");
            	  }
                  this.parent = parent;
            }
            public void setNumDescendents(int numDescendents) {
                  this.numDescendents = numDescendents;
            }
            public int getNumDescendents() {
                  return this.numDescendents;
            }           
         
      }
           

      public static void main(String args[]) {
            TreeMap test = new TreeMap();
            
            //test if the preorder traversal works properly!
            Enumeration testPreIt = test.preIterator();   
            while (testPreIt.hasMoreElements()) {
  		          System.out.println("Data for this node is: " +
  		         		((TreeNode)testPreIt.nextElement()).data );
  			}  
  			
  			 //do preorder and see the number of descendants to see if calculatedescendants
  			 // works correctly
  			 // what would you need to do if we wanted to count the "data" fields 
  			 // for all descendants?
  			test.calculateDescendents(test.root);
            Enumeration testPreIt2 = test.preIterator();   
            while (testPreIt2.hasMoreElements()) {
  		          System.out.println("Number of descendants for this node is: " +
  		          		((TreeNode)testPreIt2.nextElement()).getNumDescendents() );
  			}         
      }
}