/**
 * Class to do all the operations related to the random three,
 * i.d.: Insert and  Reset  
 */

import java.io.PrintStream;

public class RandomTree 
{
	 /**
	    * A node of randomTree that inserts a value
	    * and knows its children: the left node and the right node.
	    * This class is also able to do several two operations, such
	    * as insertion and removal
	    */
	   public class Node
	   {
	      /**
	       * The value to be stored as a String
	       */
	      private String value = "";
	      
	      /**
	       * Reference to the left subtree, null if none
	       */
	      private Node left = null;
	      
	      /**
	       * Reference to the right subtree, null if none
	       */
	      private Node right = null;
	      
	      /**
	       * Constructs a Node with the given key and value
	       * No children are created
	       * 
	       * @param key The key to be stored
	       * @param value The value to be stored
	       */
	      public Node(String value)
	      {
	         this.value = value;
	      }
	      
	     /**
	       * Tries to insert the given key value as a child
	       * of this node, otherwise, it will be inserted as a child
	       * of a random subtree (randomly chooses between right and left)
	       * 
	       * @param value The value to be stored
	       */
	      public void insert(int value)
	      {
	         double randomValue = Math.random() * 10;
	         
	    	  	// It gets a 50/50 chance to insert it in the left node
	         if ( randomValue > 5 )
	         {
	            // Check if we have a left subtree
	            if ( this.left == null )
	            {
	               // We do not have a left subtree, create it
	               this.left = new Node("-" + value);
	            }
	            else
	            {
	               // We have a left subtree, insert the (key,value) there
	               this.left.insert(value);
	            }
	         }
	         else 
	         {
	            // The key to be inserted must go in the right subtree
	            // Check if we already have a right subtree
	            if ( this.right == null )
	            {
	               // We do not have a right subtree, create the node there
	               this.right = new Node("+" + value);
	            }
	            else
	            {
	               // We already have a right subtree, insert the node there
	               this.right.insert(value);
	            }
	         }
	      }
	 
	      /**
	       * Print this tree in in-order, which gives alphabetical order
	       * @param out
	       */
	      public void print(PrintStream out)
	      {

		     // First, print myself because I am the next 
		     out.printf("%s ", this.value);
		         
	         // Second, print the entire left subtree recursively
	         // because all its keys are less than mine
	         if ( this.left != null ) { this.left.print(out); }
	         
	         // Third, print the entire right subtree recursively
	         // because all its keys are greater than mine
	         if ( this.right != null ) { this.right.print(out); }
	      }
	      
	      /**
		    * Method to reset the tree (all the collection is emptied)
		    */
		   public void resetTree(Node node)
		   {
			  if ( node != null) 
			  {
				  if ( this.left != null)
					  resetTree( this.left );
				  if ( this.right != null)
					  resetTree( this.right);
				  node = null;
			  }
		   }
	      
	   } // class Node
	   
	   /**
	    * If this reference is null, the tree is empty
	    */
	   private Node root = null;
	   
	   /**
	    * The number of levels of the tree
	    */
	   private int levelCount = 0;
	   
	   /**
	    * Return true if this tree is empty
	    * @return true if the tree is empty, false otherwise
	    */
	   public boolean isEmpty()
	   {
	      return root == null;
	   } 
	 
	   /**
	    * Insert the given pair (key,value) in the tree
	    * @param key The key to be stored
	    * @param value The value to be stored
	    */
	   public void insert(String key, int value)
	   {
	      // The insertion depends on if the tree is empty
	      if ( this.isEmpty() )
	      {
	         // The tree is empty, make the new pair the root
	         this.root = new Node("" + value);
	      }
	      else
	      {
	         // The tree has elements, ask the root to insert
	         // the pair (key,value) in its place
	         this.root.insert(value);
	      }
	      
	      ++this.levelCount;
	   }
	   
	   /**
	    * Prints this tree to the given output in alphabetical order
	    * @param out The file were the tree will be printed
	    */
	   public void print(PrintStream out)
	   {
	      // We can only print a tree if it has values
	      if ( ! this.isEmpty() )
	      {
	         // Print the nodes recursively
	         this.root.print(out);
	      }
	   }
	   
	   /**
	    * Method to count how many levels the tree has
	    * @return the amount of levels of the tree
	    */
	   public long findFarthestLeaf()
	   {
		   return this.levelCount;
	   }
	   
	   /**
	    * Calls the method to reset the tree
	    */
	   public void resetTree()
	   {
		   // The method does not work, but it should call the following:
		   // this.root.resetTree(root); <--- but it gives StackOverFlowError
		   System.out.println("El metodo de reiniciar el arbol aun no esta implementado");
	   }

}