/**********************************************************************/
// van Emde Boas trees:  supports priority queue operations on elements
// in a fixed range [i, i+n-1] in O(log log n) time.  
/**********************************************************************/

public class VEBTree
{
   private int storedItemsVal = 0;  // number of items stored
   private int minVal = -1;         // current minimum
   private int leftEndVal;          // smallest integer in range 
                                    //   that can be stored
   private int lengthVal;           // length of range of ints 
                                    //    that can be
   private int subtreeLengthVal;    // length of subtrees (except last subtree,
                                    //   which can have an oddball size)
   private int rootDegreeVal;       // number of children of root
   private NaiveHeap BaseCaseHeap;  // trivial structure used in base case
   private VEBTree[] Subtrees;      // subtrees of root
   private VEBTree SideHeap;        // side heap for managing indices
   
   public int length()    // length of tree (number of items in range)
   {
       return lengthVal;
   }

   public int storedItems()    // number of items currently stored
   {
       return storedItemsVal;
   }

   public int findMin()      // current minimum (-1 if nothing stored)
   {
       return minVal;
   }

   public int leftEnd()  // first integer in the tree's range
   {
       return leftEndVal;
   }

   public boolean isEmpty()   // true if nothing currently stored
   {
       return storedItems() == 0;
   }

   // length of each subtree (except last, which may be an oddball)
   public int subtreeLength()  
   {
       return subtreeLengthVal;
   }

   // number of children of the root
   public int rootDegree()
   {
       return rootDegreeVal;
   }

   // true if length puts the tree in the trivial base case
   public boolean isBaseCase()
   {
       return length() <= 3;
   }

   // true if i is in the tree's range of integers it can store
   public boolean inRange(int i)
   {
       return (i >= leftEnd() && i < leftEnd() + length());
   }

   public int subtreeBucket(int i)  // which subtree does i hash to?
   {
       return ((i - leftEnd()) / subtreeLength());
   }

   /******************************************************************/
   // The ranges of the O(sqrt(n)) (big-O of square root of n) recursive 
   // subtrees are a partition of the range of the root into ranges of 
   // length O(sqrt(n)).  In addition, we keep a recursive "side heap" 
   // that keeps the indices of the nonempty subtrees.

   // The recurrence we must achieve for the time bound is 
   // T(n) = T(sqrt(n))+O(1) = O(log log n), where n is the length of the 
   // range.  The recurrence of T(n) = 2T(sqrt(n)) + O(1) = O(log n), which
   // we could get by making a recursive call on a subtree and the side heap,
   // would blow the time bound.
   //
   // To avoid this, we store the minimum element in a separate variable, 
   // minVal, and store the remaining elements recursively in the subtrees.  
   // This ensures that one of the two calls on the subtree and the side heap 
   // is O(1), by ensuring that inserting the first element or extracting
   // the last is O(1).
   //
   //  The procedure returns false if the item cannot be stored, either
   //  because it is out of range or because the integer is already stored.
   /******************************************************************/
   public boolean insert(int i) // insert a new element i
   {
      if (! inRange(i)) // if out of range 
          return false;
      else if (isBaseCase())  // if the length puts us in trivial base case
      { 
          if (! BaseCaseHeap.insert(i))
              return false;
          else
          {
              storedItemsVal++;
              minVal = BaseCaseHeap.findMin();
              return true;
          }
      }
      else
      {
          if (storedItems () == 0)  // if we're storing the first element
          {
              minVal = i;
              storedItemsVal++;
              return true;
          }
          else 
          {
              if (i == findMin()) // if new item already stored 
                   return false;
              // if i is the new minimum element, swap its role with the old
              //  minimum element
              if (i < findMin())  
              {
                 int temp = minVal; minVal = i; i = temp;
              }
              int index = subtreeBucket(i);   // find the subtree it belongs in
              if (! Subtrees[index].insert(i))  // store it recursively
                   return false;
              else
              {
                  storedItemsVal++;
                  SideHeap.insert(index); // store the index in side heap if
                                          //  not already there
                  return true;
              }
          }
      }
   }


   /******************************************************************/
   // extract the minimum element ...
   // See 'insert' for comments about the invariants that must be maintained.
   /******************************************************************/
   public int extractMin()
   {
      if (isEmpty()) 
             return -1;

      int oldMin = findMin();   
      if (isBaseCase())        // range is small, use a trivial structure
      {
          storedItemsVal--;
          BaseCaseHeap.extractMin();
          minVal = BaseCaseHeap.findMin();
      }
      else
      {
          storedItemsVal--;
          int index = SideHeap.findMin(); // index of second-to-smallest
          if (index == -1) 
              minVal = -1;
          else
          {
              minVal = Subtrees[index].extractMin();      
              if (Subtrees[index].isEmpty())  // if subtree is now empty rmv
                   SideHeap.extractMin();       // index from list of nonempty indices
          }
      }
      return oldMin;
   }

   // print out current contents of side heap ..
   public void printSideHeap()
   {
       SideHeap.printContents();
   }

   // print out current set of items stored in the tree ...
   public void printContents()
   {
       printContentsRecursive();
       System.out.println();
   }

   private void printContentsRecursive()
   {
       if (isEmpty())
           return;
       if (isBaseCase())
           BaseCaseHeap.printContents();
       // if only one item stored, we find it in findMin() ...
       else 
       {
           System.out.print (findMin() + " ");
           // recursively print everything stored in subtrees ...
           for (int i = 0; i < rootDegree(); i++)
               Subtrees[i].printContentsRecursive();

       }
   }

   /*****************************************************************/
   // The ranges of the (sqrt(n)) recursive subtrees are a partition of the 
   // range of the root into ranges of length (sqrt(n)).  In addition, we
   // keep a recursive "side heap" that keeps the indices of the nonempty
   // subtrees.
   /*****************************************************************/
   public VEBTree(int leftRange, int len)
   {
       leftEndVal = leftRange;
       lengthVal = len;  
       storedItemsVal = 0;
       minVal = -1;
       if (isBaseCase())
       {
           subtreeLengthVal = -1;
           rootDegreeVal = -1;
           BaseCaseHeap = new NaiveHeap(leftRange,len);
       }
       else
       {
           subtreeLengthVal = (int) Math.floor(Math.sqrt((double) length()));


           double temp = (double) length() / (double)subtreeLength();
           rootDegreeVal = (int) Math.ceil(temp);
           SideHeap = new VEBTree(0, rootDegree());
           Subtrees = new VEBTree[rootDegree()];

           // Create all but last subtree ...
           for (int i = 0; i < rootDegree() - 1; i++)
               Subtrees[i] = new VEBTree(leftEnd() + i * subtreeLength(), 
                                         subtreeLength());

           // create last subtree (may have oddball size) ...
           int lastTreeLeft = leftEnd() + (rootDegree() - 1) * subtreeLength();
           Subtrees[rootDegree() - 1] 
              = new VEBTree(lastTreeLeft,
                            leftEnd()+length() - lastTreeLeft);
       }
   }
}