/*
 * BST implementation in which insertion and deletion are accomplished by
 * recursive algorithms (insertion after Carrano, deletion after Weiss).

 * Data Structure (class) BST --- binary search tree
 * public member functions:
 *    constructor --- for the tree itself
 *    empty       --- empty out the tree
 *    walk        --- traverse the data structure, showing the values
 *                    in increasing order.
 *    pretty      --- Display the tree structure (level-order traversal)
 *    tstNR(opt)  --- Exercise Carrano (opt=2) and Weiss (opt=1 or 3)
 *                    non-recursive traversal algorithms.
 *    insert      --- insert one cell into the data structure
 *    find        --- find, based on data value; returns pointer to cell
 *    delete      --- remove one cell from the data structure
 *    avgDepth    --- average depth of all tree nodes
 *    height      --- height of the entire tree
 *    size        --- number of nodes in the tree

 * Additional classes used:
 *   BSTnode: single binary search tree node.
 *   Wrapper: for Weiss' traversal, hold a BSTnode AND which visit.
 *            in the pretty-printing, the int field is the tree level
 *
 * Author  Timothy J. Rolfe
 * Version 2009 April 29
 */
import java.util.*;     // Stack, Queue

public class BST
{
// Instance fields:

   protected BSTnode root = null,
                     current = null;   // Spare reference for processing
   private int nItems;                 // Used in the protected tree walk
   private BSTnode free = null;        // nodes for re-use

// Class fields:

// ¿ ¿ Show nodes on recycling ? ?
   protected static final boolean DEBUG  = false;
// ¿ ¿ Enforce unique keys ? ?
   protected static final boolean UNIQUE = false;

// no constructor needed:  root and free initialized to null already

//  ************** Over-all tree characteristics **************  //
/*
 * Tree size --- available as root.size, if there is a root
 */
   public int size()
   {  return root == null ? 0 : root.size;  }
/*
 * Tree height == number of levels in the tree = root height
 */
   public int height()       // root = null means empty = 0
   {  return root == null ? 0 : root.height;  }
/*
 * Average node depth
 */
   public double avgDepth()
   {  if ( root == null )
         return 0;
      else
         return sumDepths(root, 1) / root.size;
   } // end avgDepth()
   // Total all depths of nodes within the tree:
   double sumDepths(BSTnode node, int deep)
   {  if (node == null)
         return 0;
      else
         return deep
              + sumDepths (node.left, deep+1)
              + sumDepths (node.right, deep+1);
   } // end sumDepths()

//  ******************* Simple Find *******************  //
/*
 * Find the cell with the data field corresponding to value
 */
   BSTnode find(int value)
   {  current = root;
      while ( current != null && current.data != value )
      {  if (value < current.data)
            current = current.left;
         else
            current = current.right;
      }

      return current;
   } // end find()

//  ************** Tree modifier methods **************  //
/*
 * Empty out the tree.  The "autumn" method recycles the nodes
 * to save on garbage collection expense.
 */
   public void empty()
   {  autumn(root);  root = null;  }

   // All the leaf (nodes) fall . . . recursively
   void autumn (BSTnode node)
   {  if ( node != null )
      {  autumn(node.left);  // post-order traversal
         autumn(node.right);
         recycle(node);      // This is now a leaf.  Goodbye!
      }
   } // end autumn()

/*
 * Insertion in the BST
 */
// Insert the value into its proper place in the binary search tree
   public void insert(int value)
   {  root = insert(root, value);  }

// Recursive insertion, returning reference to subtree generated.
   BSTnode insert(BSTnode node, int value)
   {  if ( node == null )
         node = build (value);
      else if ( value < node.data )
         node.left  = insert (node.left, value);
      // ***** If equal keys allowed, place them right *****
      else if ( ! UNIQUE )
         node.right = insert (node.right, value);
      // ***** Equal keys must be FORBIDDEN *****
      else if ( value > node.data )
         node.right = insert (node.right, value);
      // ***** If equal keys are NOT allowed, ERROR  *****
      else
      {  System.err.println (value + " is already in.");
      } // end if/else if/else if/else if/else
   // Correct this node's height and size after the insertion:
      node.height = newHt(node);
      node.size = newSize(node);
      return node;
   } // end insert(BSTnode, int)

//  ******************* Deletion *******************  ///

// Fields required as stable in delete(BSTnode, int)
   BSTnode deleteNode, lastNode;

/*
 * Delete the node with the value passed.
 */
   public void delete(int value)
   {  deleteNode = null;  lastNode = null;
      root = delete(root, value);
   }

// Interchange the .data fields on two BSTnodes passed
   static void swapData (BSTnode d, BSTnode s)
   {  int temp = d.data;  d.data = s.data;  s.data = temp; }

   BSTnode delete(BSTnode node, int value)
   {  if ( node == null ) return null;

      lastNode = node;                      // Reference to LAST node seen
      if ( value < node.data )
         node.left = delete (node.left, value);
      else
      {//When we FIND the node and take one step right, all subsequent
       //steps will be left --- down to the in-order successor
         deleteNode = node;                 // Potentially the node to go
         node.right = delete (node.right, value);
      }

   // In the returns, the call where we are dealing with the replacement
      if ( node == lastNode )
      {//Check to see if we indeed DID find the value
         if ( deleteNode != null && value == deleteNode.data )
         {//Final check:  if node is RIGHTMOST in its subtree
            if ( deleteNode == lastNode )   // Half-nodes are easy!
            {  node = node.left;            // Return left subtree
            }
          //node is NOT rightmost in its subtree.  Copy replacement up.
            else
            {  swapData (deleteNode, lastNode);
               node = node.right;           // Return right subtree
            }
            recycle (lastNode);             // Return the node for re-use
         }
      }
      else  // Adjust heights on the way back up the recursive stack
      {  node.height = newHt(node);
         node.size = newSize(node);
      }
      return node;
   }

//  ******************* Recursive traversal *******************  //
/*
 * Walk through the tree; display is to be ascending order
 */
   public void walk()
   {  if (root != null)
      {  nItems = 0;
         inOrder(root);
         // Check whether final '\n' is required.
         if (nItems % 10 != 0)
            System.out.println();
      }
   } // end walk()

   // To get ascending order, do an in-order traversal of the tree
   void inOrder(BSTnode item)
   {  StringBuffer front = new StringBuffer("    ");
      String       back;

      if ( item == null) return;            // I.e., empty tree

      inOrder(item.left);                   // Process left sub-tree

      back = "" + item.data;                // Process this node
//    back = Integer.toString(item.data) if you want the hard way.
      front.setLength(front.length()-back.length());
      System.out.print (front+back + "(" + item.height + ")");
      if ( ++nItems % 10 == 0 )
         System.out.println();
      inOrder(item.right);                  // Process right sub-tree
   } // end inOrder()

//  ******************* NON-Recursive traversals *******************  //
/*
 *  Test non-recursive algorithms, based on parameter opt.
 *
 *     opt = 1:  Weiss-style  pre-order
 *     opt = 2:  Carrano's     in-order
 *     opt = 3:  Weiss-style post-order
 */
   public void tstNR(int opt)
   {  if   (opt==2)  Carrano(root);
      else           Weiss(root, opt);
      System.out.println();
   } // end tstNR()

// Simplest possible visit:  just print the node
   void visit ( BSTnode node )
   {  System.out.print (node.data + "  ");  }

// Carrano's non-recursive in-order traversal
// alterations by Timothy Rolfe
   void Carrano(BSTnode current)
   {  Stack<BSTnode> stack = new Stack<BSTnode>();

   // Revision:  instead of a boolean loop variable, just use a break:
      while ( true )                 // Infinite loop exited via break
      {//Revision:  Carrano code is equivalent in behavior to a "while"
         while ( current != null )
         {  stack.push ( current );
            current = current.left;
         } // end while (current...
      // What follows would be under Carrano's "else"
         if ( stack.empty() )
            break;                   // Exit the processing loop
         else
         {  current = stack.pop ( );
            visit (current);
            current = current.right;
         } // end if/else
      } // end while (forever)
   } // end Carrano()

   static class Wrapper
   {  int visit;
      BSTnode node;

      Wrapper(BSTnode node, int visit)
      {  this.visit = visit; this.node = node;  }
   }
// Implementation of Weiss' logic for post-order traversal,
// generalized by Timothy Rolfe for pre-order and post-order.
   void Weiss  (BSTnode node, int opt)
   //       opt = 1:  pre-order
   //       opt = 3:  post-order
   // NOTE: opt = 2:  this in fact does a POST-order traversal
   {  Stack<Wrapper> stack = new Stack<Wrapper>();
      int nVisit = 1;

      stack.push(new Wrapper(node, nVisit));

      while ( ! stack.empty() )
      {  Wrapper item = stack.pop();
         node   = item.node;
         nVisit = item.visit;
         if ( nVisit == opt )
            visit(node);
         else
            stack.push ( new Wrapper(node, nVisit+1) );
         if ( nVisit == 1 )
         {//push right-to-left to simulate recursive behavior
            if ( node.right != null )
               stack.push (new Wrapper(node.right, 1) );
            if ( node.left != null )
               stack.push (new Wrapper(node.left, 1) );
         } // end if
      } // end while
   } // end Weiss()
/*
 *  Display the BST horizontally --- based on a level-order traversal
 */
   // Keep track of position on the line across calls to setPos
   static int skip;
   public void pretty()
   {  skip = 0;

      if ( root == null )  // Nothing to display!
      {  System.out.println ("Empty tree!"); return;  }

      setPos (root);       // Find line position for each node
      pretty (root);       // level-order traversal displaying the nodes
   } // end pretty()       // one line for each level, in proper position

   // Find line position for each node --- based on in-order traversal
   void setPos (BSTnode node)
   {//If the nodes were all printed on one line, their order is based
   // in an in-order traversal.  skip shows number of positions to skip
   // to properly position the node.  Note that this MUST be a class
   // data member --- the root depends on skip to come back with the
   // size of the entire left subtree, for instance.
      if ( node != null )
      {  setPos (node.left);
         node.util = skip;        // Store skip value in util data member
         skip += 2;               // Update for printing THIS node
         setPos (node.right);
      } // end if
   } // end setPos()

// Pretty-print:  each tree level prints on one line, with the node
// horizontally positioned to be visually the parent of its children.
   void pretty (BSTnode node)
   {//work queue during traversal
      Queue<Wrapper> queue = new LinkedList<Wrapper>();

      int   position = 0,           // position in output line
            level = 1,              // level being processed
            current;                // value for node ABOUT to process

   // level-order traversal:  initialize the work queue with the root
      queue.offer(new Wrapper(node, level));// node initially IS the root

      while ( ! queue.isEmpty() )     // Go there's nothing left to do!
      {  Wrapper item = queue.remove();
         node    = item.node;
         current = item.visit;
         if (node.left != null)     // Enqueue child nodes
            queue.offer(new Wrapper(node.left, current+1));
         if (node.right != null)
            queue.offer(new Wrapper(node.right, current+1));
   //    Check for line-break:  change in tree level
         if ( current != level )
         {  System.out.println();
            position = 0;
            level = current;
         }
   //    skip over to proper position
         for ( ; position < node.util ; position++ )
            System.out.print (" ");
         System.out.print (( node.data < 10 ? "0" : "" ) + node.data);
         position += 2;    // Update position for the output just done
      } // end while
      System.out.println();      // Final line termination.
   } // end pretty(BSTnode)

//  ******************* Utility functions *******************  //

// Return the height based on the children; node must NOT be null.
   static int newHt ( BSTnode node )
   {  BSTnode lt = node.left,
              rt = node.right;

      if ( lt == null && rt == null )     // Leaf node is height 1
         return 1;
      else if ( lt == null )              // Half node cases
         return 1 + rt.height;
      else if (rt == null )
         return 1 + lt.height;
      else                                // Full node --- need java.lang.Math.max
         return 1 + Math.max(lt.height, rt.height);
   } // end newHt()

// Return the size based on the children; node must NOT be null.
   static int newSize( BSTnode node )
   {  BSTnode lt = node.left,
              rt = node.right;

      if ( lt == null && rt == null )     // Leaf node has size 1
         return 1;
      else if ( lt == null )              // Half node cases
         return 1 + rt.size;
      else if (rt == null )
         return 1 + lt.size;
      else                                // Full node --- do the sum
         return 1 + lt.size + rt.size;
   } // end newSize()

//  ************** free-space list mainenance ******************  //

// Generate a node, either re-using from the free list or constructed
   BSTnode build( int data )
   {  BSTnode rtn;

      if (free == null)
      {  rtn = new BSTnode (data);
         if ( rtn == null )
         {  System.err.println ("ALLOCATION ERROR.  Abort execution.");
            System.exit(7);
         }
      }
      else
      {  rtn = free;
         free = free.right;
         rtn.data = data;
         rtn.height = rtn.size = 1;    // Leaf node
         rtn.left = null; rtn.right = null;
      }
      return rtn;
   }

// push node onto free list.
   void recycle( BSTnode node )
   {  if ( DEBUG )
         System.out.println ("Recycling node \"" + node.data + '"');
      node.left   = null;
      node.right  = free;
      free = node;
   } // end recycle

} // end class BST