import java.io.*;  // Needed for BufferedReader etc.

/**
 * Wrapper class for a main() to demonstrate AVL tree behaviors.
 *
 *@author  Timothy Rolfe
 *@version 2002 October 23
 */

public class AVLdemo
{//class fields (for in-class drill use)
   static int   top = -1,    // Disable "new round" on first pass.
                nPlayers = 0;
   static int[] current = null;

// Accept the default initialization of Random
   static java.util.Random generator = new java.util.Random();

/**
 * Program to demonstrate AVL tree behaviors.
 *
 * Initial dialog:
 *    AVL tree size
 *    Number of "players" for in-class drill (0 or 1 for solo use)
 *
 * Insert phase:
 *    insert individual values up to the specified size
 *
 * Delete/Insert phase:
 *    randomly delete one of the values in use
 *    randomly insert another value (might happen to be the same)
 */
   public static void main ( String[] args )
   {//Uses the verbose TRACE extension of the AVL tree class.
      AVLverbose tree = new AVLverbose();
      final int nTotal = 90; // Size of the "deck" used
      int       value[];     // The "deck" itself
      int       nInit,       // Initial tree size
                nUnused,     // Size of the unused part
                tail,        // Last subscript used
                idx;         // misc. loop/subscript
      int       request,     // User request for next
                check;       // Location of "request"
      String lineIn = "",    // string that may hold a hidden number
             ans = "";       // response to ¿continue? query

   // Code for reading console from "Java in a Nutshell", p. 166
      BufferedReader console = new BufferedReader
                               (new InputStreamReader(System.in));

   // *********** Set up the shuffled array of 90 values *********** //

      value = new int[nTotal];
      for (idx = 0; idx < nTotal; idx++)       // Fill with 10 through 99
         value[idx] = idx + 10;
      shuffle (value, nTotal); shuffle (value, nTotal); // twice for luck

   // *********** Specify tree size for the drill *********** //

      System.out.print ("Tree size:  ");
      lineIn = getLine(console);
      nInit = atoi(lineIn);  // local version for zero on invalid string
      nUnused = nTotal - nInit;
      tail = nInit-1;        // last entry of value in use.

   // *********** In-class use:  number of players *********** //

      System.out.print ("Number of players (0 or 1 for solo):  ");
      lineIn = getLine(console);
      nPlayers = atoi(lineIn);

      if ( nPlayers > 1 )
      {  current = new int [nPlayers];
         for ( idx = 0; idx < nPlayers; idx++ )
            current[idx] = idx+1;
      } // end if

   // *********** Insertion portion of the drill *********** //

      System.out.print ("Press <Enter> to begin: ");
      lineIn = getLine(console);

      for (idx = 0; idx < nInit; idx++)
      {  System.out.println();  // spacing line
         request = atoi(lineIn);
         if ( request > 0 )
         {  check = find ( value, nTotal, request );
            if ( check < nTotal && check > idx )
               swap ( value, check, idx );
         } // end if
         if ( current != null )
            promptNext(console);
         System.out.print ("Insert " + value[idx]
                         + "  Press ENTER to continue: ");
         lineIn = getLine(console);
         tree.insert(value[idx]);
         System.out.println ("Current state:");
         tree.pretty();
      } // end for

   // *********** Delete/Insert portion of the drill *********** //

      System.out.println (
           "\nNOTE:  Deletion replaces with in-order successor."
         + "\n       Equal keys on insertion go to the RIGHT");

   // NOTE:  lineIn will possibly hold value for next delete/insert
   //        Hence ans will be used for ¿continue? query at loop end
      System.out.print ("\nPress <Enter> to begin: ");
      lineIn = getLine(console);

      do
      {  System.out.println();  // spacing line
         idx = generator.nextInt(nInit );
         request = atoi(lineIn);
         if ( request > 0 )
         {  check = find (value, nInit, request);
            if ( check < nInit )
               idx = check;
         } // end if
         swap ( value, tail, idx );
         if ( current != null )
            promptNext(console);
         System.out.print ("Deleting " + value[tail]
                         + "  Press ENTER to see result: ");
         lineIn = getLine(console);
         tree.delete(value[tail]);
         tree.pretty();
         System.out.println();  // spacing line
         idx = nTotal - ( 1 + generator.nextInt(nUnused) );
         request = atoi(lineIn);
         if ( request > 0 )
         {  check = find (value, nTotal, request);
            if ( check < nTotal && check >= tail )
               idx = check;
         } // end if
         swap ( value, tail, idx );
         if ( current != null )
            promptNext(console);
         System.out.print ("Inserting " + value[tail]
                         + "  Press ENTER to see result: ");
         lineIn = getLine(console);
         tree.insert(value[tail]);
         tree.pretty();

         System.out.print (
            "\nAnother?  <CR> for YES, anything else for NO: ");
         ans = getLine(console);
      } while ( ans.length() == 0 );
   } // end main()

// UTILITY FUNCTIONS:
// Pull a line of text from a file.
   static String getLine (BufferedReader inp)
   {  String text = "";
      try
      {  text = inp.readLine();  }
      catch (IOException e)
      {  System.out.println ("Error on read: " + e);
         System.exit(-1);
      }
      return text;
   } // end getLine()

// replacement for parseInt that acts like the C function atoi
   static int atoi(String number)
   {  int rtnVal = 0;   // on invalid string, return a zero

      try
      {  rtnVal = Integer.parseInt(number);  }
      catch (NumberFormatException e)
      { /* Let it pass! */  }

      return rtnVal;
   } // end atoi

   static void swap ( int[] x, int lt, int rt )
   {  int tmp = x[lt];  x[lt] = x[rt];  x[rt] = tmp;  }

// The method name say it all!
   static void shuffle ( int[] x, int n )
   {  while ( n > 1 )
      {  int k = generator.nextInt(n);    // interval [0..n)
         swap(x, --n, k);
      } // end while
   } // end shuffle()

// NOTE:  error return is "n", not -1
   static int find( int[] x, int n, int val )
   {  int k;
      for ( k = 0; k < n; k++ )
         if ( val == x[k] )
            break;
      return k;
   } // end find()

// Prompt for the next player, reshuffling list when empty.
   static void promptNext(BufferedReader inp)
   {  if ( top < 1 )
      {  if ( top == 0 )     // I.e., have exhausted the deck
            System.out.println ("New round of play.");
         shuffle(current, nPlayers);
         top = nPlayers;     // reset the top-of-deck
      } // if
   // Note the predecrement [--top]
      System.out.print ("Player " + current[--top] + ":  ");
   } // end promptNext
} // end class AVLdemo