/**
 * @author Peter A. Friend
 * @version 1.0
 */

public abstract class MCBSTree
{
   /**
    * The initial capacity allocated for the tree.
    */
   protected int initial_capacity;
   /**
    * The amount the capacity of the tree is incremented when needed.
    */
   protected int capacity_increment;
   /**
    * The total size of the tree if all nodes on all levels are occupied.
    */
   protected int full_size;
   /**
    * The current level of the tree, numbered from 0.
    */
   protected int current_level;
   /**
    * An array is used (sequential representation) for the binary tree.
    */
   protected Object tree_array[];
   /**
    * The number of items currently in the tree.
    */
   protected int size;
   protected int current_capacity;

   /**
    * Constructor. 
    *
    * @param initialCapacity The storage allocated for the tree upon creation.
    * @param capacityIncrement The additional storage allocated for the tree when needed.
    */

   public MCBSTree(int initialCapacity, int capacityIncrement)
   {
      initial_capacity = initialCapacity;
      capacity_increment = capacityIncrement;
      current_capacity = initialCapacity;
      full_size = 1;
      size = 0;
      current_level = 0;
      tree_array = new Object[initial_capacity];
   }

   /**
    * Returns an inorder sorted array of Objects from the tree.
    *
    */

   public synchronized final Object[] inorder()
   {
      int stack[] = new int[current_level + 1];
      int stack_index = -1;
      int retarray_index = 0;
      int tree_index = 1;

      if (size == 0)
         return null;

      Object retarray[] = new Object[size];

      while (true)
      {
         if (tree_array[tree_index] == null)
         {
            if (stack_index == -1)
               return retarray;
            else
            {
               tree_index = stack[stack_index];
               stack_index--;
               retarray[retarray_index] = tree_array[tree_index];
               retarray_index++;
               tree_index = (tree_index << 1) + 1;
            }
         }
         else
         {
            stack_index++;
            stack[stack_index] = tree_index;
            tree_index <<= 1;
         }
      }
   }

   /**
    * Searches for an item in the tree.
    *
    * @param item The Object to search for.
    * @return The Object if it is found in the tree, null otherwise.
    */
   public final Object search(Object item)
   {
      int compare_result;
      int tree_index = 1;
  
      while (tree_array[tree_index] != null)
      {
         compare_result = compare(item, tree_array[tree_index]);
         switch (compare_result)
         {
            case -1: /* less than */
               tree_index = tree_index << 1;
               break;
            case 0: /* equal */
               return tree_array[tree_index];
            case 1: /* greater than */
               tree_index = (tree_index << 1) + 1;
               break;
         }
      }
      
      return null;
   }

   /**
    * Inserts an item into the tree.
    *
    * @param newItem The item to insert.
    * @return The object inserted if not already in the tree, null otherwise.
    */

   public final Object insert(Object newItem)
   {
      int i;
      int j;
      int desired_size;
      int position_level;
      int compare_result;
      int new_position;
      int new_position_parent;
      int current_level_begin_index;
      int current_level_end_index;
      int desired_position = 0;
      int current_position;
      int next_inorder_position = 0;
      Object temp[];
      Object current_object;

      /*
       * First we need to make sure that there are enough free nodes in tree
       * for the current level plus one. 
       */

      verifyCapacity();

      /*
       * If we have been given a null object we return null to indicate the
       * error. 
       */

      if (newItem == null)
         return null;

      /*
       * First we traverse the tree to find the new position for the new
       * object. 
       */

      i = 1;
      new_position = 1;

      while (i <= full_size)
      {
         if (tree_array[i] == null)
            break;
 
         current_object = tree_array[i];
         compare_result = compare(newItem, current_object);
         switch (compare_result)
         {
            case -1: /* less than */
               i = i << 1;
               break;
            case 0: /* equal */
               return tree_array[i];
            case 1: /* greater than */
               i = (i << 1) + 1;
               break;
         }
      }

      new_position = i;

      /*
       * Now we need to check if the new position increases the height of the
       * tree. We do this by determining the level of the new position, and
       * comparing it to the current level. If they are equal, we can insert
       * the new item.
       */

      position_level = levelForIndex(new_position);

      if (position_level == current_level)
      {
         tree_array[new_position] = newItem;
         size++;
         return newItem;
      }
      
      /*
       * If we get here then the new position increases the height of the tree. 
       * We first check to see if the tree is full. If so, we can just 
       * move to the next level, otherwise, we have to make adjustments. 
       */

      if (full_size == size)
      {
         current_level++;
         full_size = 1 + (full_size << 1);
         tree_array[new_position] = newItem;
         size++;

	 /*
	  * Since the level of the tree is being increased, we must check to
	  * make sure that we have enough nodes allocated for the current level 
	  * plus one. 
	  */

         verifyCapacity();

         return newItem;
      }

      /*
       * Now we are forced to adjust the tree. We first calculate
       * desired_position by looking for the empty slot closest to the parent
       * of new_position. To aid in this, we have to calculate
       * current_level_begin_index, current_level_end_index and
       * new_position_parent.
       */

      current_level_begin_index = beginIndexForLevel(current_level);
      current_level_end_index = endIndexForLevel(current_level);
      new_position_parent = new_position >>> 1;

      i = new_position_parent - 1;
      j = new_position_parent + 1;

      while (true)
      {
         if (j <= current_level_end_index)
         {
            if (tree_array[j] == null)
            {
               desired_position = j;
               break;
            }
            else
            {
               j++;
               continue;
            }
         }

         if (i >= current_level_begin_index)
         {
            if (tree_array[i] == null)
            {
               desired_position = i;
               break;
            }
            else
            {
               i--;
               continue;
            }
         }
      }

      tree_array[new_position] = newItem;
      inorderShift(new_position, desired_position);

      size++;
      return newItem;
   }

   public synchronized Object delete(Object item)
   {
      int compare_result;
      int tree_index = 1;
      Object object_to_delete;

      /* First, find the node that we want to delete. */

      while (tree_array[tree_index] != null)
      {
         compare_result = compare(item, tree_array[tree_index]);
         switch (compare_result)
         { 
            case -1: /* less than */
               tree_index = tree_index << 1; 
               break;
            case 0: /* equal */
               object_to_delete = tree_array[tree_index];
               /* Now we call another internal function to remove the node. */
               if (this.delete(tree_index) == false)
                  return null;
               else
                  return object_to_delete;
            case 1: /* greater than */
               tree_index = (tree_index << 1) + 1;
               break;
         }
      }
  
      return null;
   }

   private boolean delete(int item_index)
   {
      int previous_level_full_size;
      int left_index;
      int right_index;
      int min_index;
      int min_index_right_child;
      int shifted_index;
      int level_begin_index;

      /* If the node at the position is null, we just return. */

      if (item_index > full_size)
         return false;

      if (tree_array[item_index] == null)
         return false;

      /*
       * Calculate the left and right child indices for the item. 
       */

      left_index = item_index << 1;
      right_index = (item_index << 1) + 1;

      /*
       * Deletion is much the same as for a standard binary tree, except that
       * we have to fill any holes left when we delete nodes that are NOT on
       * the current level.
       */

      if ( (tree_array[left_index] == null) && (tree_array[right_index] == null) )
      {
         /* Case where node is on the current level. */

         if (levelForIndex(item_index) == current_level)
         {
            tree_array[item_index] = null;
            shifted_index = 0;
         }
         else
         {
            /* Case where node is not on the current level. */

            tree_array[item_index] = null;
            
            level_begin_index = beginIndexForLevel(current_level);

            while (tree_array[level_begin_index] == null)
               level_begin_index++;

            /* Now shift the nodes. */

            inorderShift(level_begin_index, item_index);
            shifted_index = 0;
         }
      }
      else
      {
         if ( (tree_array[left_index] == null) && (tree_array[right_index] != null) )
         {
            shifted_index = 0;
            tree_array[item_index] = tree_array[right_index];
            tree_array[right_index] = null;
         }
         else if ( (tree_array[left_index] != null) && (tree_array[right_index] == null) )
         {
            shifted_index = 0;
            tree_array[item_index] = tree_array[left_index];
            tree_array[left_index] = null;
         }
         else
         {
	    /*
	     * Find the smallest value in the right subtree. Replace the
	     * deleted item with that item, then replace the minimum item with
	     * the right child of the of the minimum item. 
	     */

            min_index = right_index;

            while (tree_array[min_index << 1] != null)
            {
               min_index <<= 1;
            }

            tree_array[item_index] = tree_array[min_index];
            min_index_right_child = (min_index << 1) + 1;

	    /*
	     * If the minimum item had a right child, then replace the minimum
	     * item with its right child. 
	     */
            
            if (tree_array[min_index_right_child] != null)
            {
               tree_array[min_index] = tree_array[min_index_right_child];
               tree_array[min_index_right_child] = null;
               shifted_index = 0;
            }
            else
            {
               tree_array[min_index] = null;

               if (levelForIndex(min_index) == current_level)
                  shifted_index = 0;
               else
                  shifted_index = min_index;
            }
         }

         /*
          * If the shifted index is 0 then we don't have a hole to fill,
          * otherwise, we have to find an active node on the current level,
          * and shift to fill the hole. 
          */
           
         if (shifted_index != 0)
            inorderShift(nearestActiveIndexForIndex(shifted_index), shifted_index);
      }

      size--;

      /*
       * Finally, we have to check if the deletion has decreased the level of
       * the tree. If so, we decrease the current level and reset the full
       * size.
       */

      previous_level_full_size = (2 << (current_level - 1)) - 1;

      if (size <= previous_level_full_size)
      {
         current_level--;
         full_size = previous_level_full_size;
      }

      return true;
   }

   public synchronized void deleteAll()
   {
      int i;

      for (i = 0; i < tree_array.length; i++)
         tree_array[i] = null;

      full_size = 1;
      size = 0;
      current_level = 0;
   }

   private final int levelForIndex(int index)
   {
      int level_count = -1;

      /*
       * The level for an index can be calculated by repeatedly dividing the
       * index by two, and each time the result is not zero, we increment a
       * level count. 
       */

      do
      {
         index >>>= 1;
         level_count++;
      } while (index != 0);
      
      return level_count;
   }

   private final int beginIndexForLevel(int level)
   {
      /*
       * The beginning index for a level is calculated by multiplying 1 by 2
       * level number of times. 
       */

      return 1 << level;
   }

   private final int endIndexForLevel(int level)
   {
      /*
       * The end index for a level is calculated by multiplying 2 by 2
       * level number of times, then subtracting 1.
       */

      return (2 << level) - 1;
   }

   private final void inorderShift(int start_position, int end_position)
   {
      int start_position_parent = start_position >>> 1;
      int end_position_parent = end_position >>> 1;
      int current_position;
      int next_inorder_position;
      Object current_object;
      Object shifting_object;

      /*
       * If the end position is less than the parent of the start position we
       * shift from end_position to start_position backwards starting at
       * end_position. 
       */

      if (end_position < start_position_parent)
      {
         current_position = end_position;
         next_inorder_position = end_position;
         shifting_object = tree_array[start_position];
         tree_array[start_position] = null;

         /* Calculate next inorder position (for leaf). */

         while ( (next_inorder_position & 0x00000001) == 1)
            next_inorder_position >>>=1;

         next_inorder_position >>>= 1;

         /* Enter the shift loop. */

         while (next_inorder_position != start_position_parent)
         {
            /* Shift node. */

            tree_array[current_position] = tree_array[next_inorder_position];
            current_position = next_inorder_position;

            /* Calculate next inorder position. */

            next_inorder_position = nextInorderForIndex(next_inorder_position, end_position);
         }

         /* Now move the final nodes. */

         if ( (start_position & 0x00000001) == 1)
         {
            tree_array[current_position] = tree_array[start_position_parent];
            tree_array[start_position_parent] = shifting_object;
         }
         else
            tree_array[current_position] = shifting_object;
      }

      /*
       * If the end position is greater then the parent of the start position
       * then we shift from start_position to end_position starting at
       * start_position. 
       */

      else
      {
         current_position = start_position;
         next_inorder_position= start_position;

         /* Calculate next inorder position (for leaf). */

         while ( (next_inorder_position & 0x00000001) == 1)
            next_inorder_position >>>=1;

         next_inorder_position >>>= 1;

         shifting_object = tree_array[start_position];
         tree_array[start_position] = null;

         /* Enter shift loop. */

         while (next_inorder_position != end_position_parent)
         {
            current_object = tree_array[next_inorder_position];
            tree_array[next_inorder_position] = shifting_object;
            shifting_object = current_object;
            current_position = next_inorder_position;
            next_inorder_position = nextInorderForIndex(next_inorder_position, end_position);
         }

         /* Now move the final nodes. */

         if ( (end_position & 0x00000001) == 1)
         {
            tree_array[end_position] = tree_array[end_position_parent];
            tree_array[end_position_parent] = shifting_object;
         }
         else
            tree_array[end_position] = shifting_object;
      }
   }

   private final int nextInorderForIndex(int index, int ep)
   {
      /* Leaf condition. */

      if ( (tree_array[index << 1] == null) && (tree_array[(index << 1) + 1] == null) )
      {
         while ( (index & 0x00000001) == 1)
            index >>>= 1;
 
         index >>>= 1;
      }
      else /* Interior node condition. */
      {
         index = (index << 1) + 1;
 
         if (tree_array[index] == null)
         {
            while ( (index & 0x00000001) == 1)
               index >>>= 1;

            index >>>= 1;

            return index;
         }

         while (tree_array[index << 1] != null)
            index <<= 1;
      }
 
      return index;
   }

   private final int nearestActiveIndexForIndex(int start_index)
   {
      int i;
      int j;
      int level_begin;
      int level_end;
      int left_index;
      int right_index;
      int start_index_level;

      left_index = start_index << 1;
      right_index = left_index + 1;
      start_index_level = levelForIndex(start_index);
      level_begin = beginIndexForLevel(current_level);
      level_end = endIndexForLevel(current_level);

      if (start_index_level == current_level)
      {
         for (i = level_begin; i <= level_end; i++)
         {
            if (tree_array[i] != null)
               return i;
         }
      }
      else
      {
         for (i = start_index_level + 1; i < current_level; i++)
         {
            left_index = (left_index << 1) + 1;
            right_index = (right_index << 1) + 1;
         }
            
         if (tree_array[left_index] != null)
            return left_index;

         if (tree_array[right_index] != null)
            return right_index;

         /* Search the indexes between the ideal indexes. */

         for (i = left_index + 1, j = right_index - 1; i < j; i++, j--)
         {
            if (tree_array[i] != null)
               return i;
 
            if (tree_array[j] != null)
               return j;
         }

         /* Search the indexes to the left and right sides. */

         i = left_index - 1;
         j = right_index + 1;

         while (true)
         {
            if (i >= level_begin)
            {
               if (tree_array[i] != null)
                  return i;
            }

            if (j <= level_end)
            {
               if (tree_array[j] != null)
                  return j;
            }

            i--;
            j++;
         }
      }

      return 0;
   }

   private final void verifyCapacity()
   {
      int i;
      int desired_size;
      Object temp[];

      desired_size = 2 << (current_level + 1);
 
      if (desired_size > current_capacity)
      {
         if ((desired_size - current_capacity) > capacity_increment)
            capacity_increment = desired_size - current_capacity;
    
         temp = new Object[current_capacity + capacity_increment];
         for (i = 1; i < current_capacity; i++)
            temp[i] = tree_array[i];
      
         tree_array = temp;
         current_capacity += capacity_increment;
      }
   }

   /**
    * Compares newItem to currentItem. 
    *
    * @param newItem Item that is being inserted into the tree.
    * @param currentItem Item from the tree that newItem is being compared with.
    * @return -1, 0 or 1 to indicate that newItem is less than, equal, or greater than currentItem.
    */
   abstract public int compare(Object newItem, Object currentItem);
}