Collections Data Structure Java

//package termproject;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
 * (2,4) Search Tree
 *
 * Description: An ADT for a (2,4) Search Tree as described on page 451 of
 * the Data Structures and Algorithms in Java textbook.
 *
 * Date Created: December, 2008
 * @author Alex Laird, Wes Perrien
 * @version 1.0
 */
public class TwoFourTree implements Dictionary
{
  private Comparator treeComp;
  private int size = 0;
  private TFNode treeRoot = null;
  /**
   * Default constructor which assigns the comparator for the tree.
   * 
   * @param comp Comparator the comparator to be assigned
   */
  public TwoFourTree(Comparator comp)
  {
    treeComp = comp;
  }
  /**
   * Returns the current size of the tree.
   * 
   * @return int the current size of the tree.
   */
  public int size()
  {
    return size;
  }
  /**
   * Returns true if the tree is empty, otherwise false.
   * 
   * @return boolean whether the tree is empty or not
   */
  public boolean isEmpty()
  {
    return (size == 0);
  }
  /**
   * Returns a pointer to the root node of the tree.
   * 
   * @return TFNode the root node
   */
  public TFNode root()
  {
      return treeRoot;
  }
  /**
   * Finds an the first element in the tree with the specified key.
   * 
   * @param key Object the key that is to be found in the tree
   * @return Object the Item that contains the specified key
   * @throws ElementNotFoundException if the key is not found in the tree
   */
  public Object findElement (Object key) throws ElementNotFoundException
  {
      TFNode node = firstGreaterOrEqualNode(key, root());
      int itemIndex = firstGreaterOrEqualItem(key, node);
      
      if(itemIndex == -1)
          throw new ElementNotFoundException();
      if(treeComp.isEqual(key, ((Item) node.getItem(itemIndex)).key()))
          return node.getItem(itemIndex);
      else
          throw new ElementNotFoundException();
  }
  /**
   * Inserts an Item with the specified key and element into the tree at it's
   * proper location. This function determines the in order successor based on
   * the specified key to find the proper location.
   * 
   * @param key Object the key to be used for the inserted Item
   * @param element Object the element to be used for the inserted Item
   */
  public void insertElement (Object key, Object element)
  {
      Item newItem = new Item(key, element);
      // if this is the first element, make a root node
      if(size() == 0)
      {
          treeRoot = new TFNode();
          treeRoot.addItem(0, newItem);
          size++;
          return;
      }
      // find the node that contains the first greater or equal item
      TFNode greatest = findInsertionPointer(newItem.key(), root());
      if(greatest != null)
      {
          // find greatest or equal item within node
          int index = firstGreaterOrEqualItem(newItem.key(), greatest);
          // if a greater or equal item was not found in node, add at end
          if(index == -1)
              index = greatest.numItems();
          // insert item at proper location
          greatest.insertItem(index, newItem);
      }
      // if a greater or equal node was not found, insert at root
      else
      {
          greatest = treeRoot;
          // walks to the far right child
          while(greatest.getChild(greatest.numItems()) != null)
              greatest = greatest.getChild(greatest.numItems());
          greatest.addItem(greatest.numItems(), newItem);
      }
      // incremet tree size
      size++;
      // if the insert caused a node to be greater than the max allowed size
      // a node split is required
      if(greatest.numItems() == greatest.maxItems() + 1)
      {
          nodePop(greatest);
      }
  }
  /**
   * Removes the first element from the tree that matches the specified key.
   * 
   * @param key Object the key to be removed by the first found element
   * @return Object the Item that contains the specified key
   * @throws ElementNotFoundException if the key is not found in the tree
   */
  public Object removeElement (Object key) throws ElementNotFoundException
  {
      // ensure that the element is in the tree and find it
      findElement(key);
      TFNode node = firstGreaterOrEqualNode(key, root());
      TFNode inOrderSuccessor = null;
      Object element;
      // find the index of the element within the node
      int location = firstGreaterOrEqualItem(key, node);
      // if the node is internal
      if(node.getChild(location + 1) != null)
      {
          inOrderSuccessor = node.getChild(location + 1);
          
          // find the in order successor
          while(inOrderSuccessor.getChild(0) != null)
              inOrderSuccessor = inOrderSuccessor.getChild(0);
          node.insertItem(location, inOrderSuccessor.removeItem(0));
          
          location++;
      }
      // remove the item from the tree
      element = node.removeItem(location);
      // rebalance the tree if the node has become empty
      if(node.numItems() == 0
         && node != root())
          rebalance(node);
      
      // rebalance tree if in order successor has become empty
      if(inOrderSuccessor != null
         && inOrderSuccessor.numItems() == 0)
          rebalance(inOrderSuccessor);
      return element;
  }
  /**
   * Determines whether the specified node has a left sibling or not. If it does
   * have a left sibling, this method returns the index to the left sibling.
   * 
   * @param node TFNode the node to be checked for a left sibling
   * @return int -1 if there is no left sibling, otherwise the index of the left sibling
   */
  protected int hasLeftSibling(TFNode node)
  {
      int childIndex;
      // find the index in the parent of the current node
      for(childIndex = 0; childIndex < 4; childIndex++)
      {
          if (node.getParent().getChild(childIndex) == node)
              break;
      }
      if(childIndex != 0
         && node.getParent().getChild(childIndex - 1) != null)
         // return the index of the left sibling
         return childIndex - 1;
      else
        // no left sibling exists
        return -1;
  }
  /**
   * Determines whether the specified node has a right sibling or not. If it does
   * have a right sibling, this method returns the index to the right sibling.
   * 
   * @param node TFNode the node to be checked for a right sibling
   * @return int -1 if there is no right sibling, otherwise the index of the right sibling
   */
  protected int hasRightSibling(TFNode node)
  {
      int childIndex;
      // find the index in the parent of the current node
      for(childIndex = 0; childIndex < 4; childIndex++)
      {
          if (node.getParent().getChild(childIndex) == node)
              break;
      }
      if(childIndex != 3
         && node.getParent().getChild(childIndex + 1) != null)
        // return the index of the right sibling
        return childIndex + 1;
      else
        // no right sibling exists
        return -1;
  }
  /**
   * This method will rebalance if needed, usually directly following a remove.
   * 
   * @param node TFNode the node to be the starting point for rebalance
   */
  protected void rebalance(TFNode node)
  {
      // check siblings
      int leftSibIndex = hasLeftSibling(node);
      int rightSibIndex = hasRightSibling(node);
      TFNode leftSib = null;
      TFNode rightSib = null;
      TFNode parent = node.getParent();
      TFNode newNode = null;
      
      if(leftSibIndex != -1)
      {
          // get the left sibling
        leftSib = parent.getChild(leftSibIndex);  
      }
      if(rightSibIndex != -1)
      {
          // get the right sibling
        rightSib = parent.getChild(rightSibIndex);
      }
      
      // transfer from left sibling
      if(leftSibIndex != -1
         && leftSib.numItems() > 1)
      {
        // insert parent into index 0
        node.insertItem(0, parent.getItem(leftSibIndex));
        
        // make left sibling's most right child the first child here
        node.setChild(0, leftSib.getChild(leftSib.numItems()));
          
        if(node.getChild(0) != null)
          node.getChild(0).setParent(node);
        
          // store the last pointer reference
          TFNode pointer = leftSib.getChild(leftSib.numItems() - 1);
          
        // make left sibling's greatest item the new parent
        parent.replaceItem(leftSibIndex, leftSib.removeItem(leftSib.numItems() - 1));
          
          // reset the last pointer
          leftSib.setChild(leftSib.numItems(), pointer);
      }
      // transfer from right sibling
      else if(rightSibIndex != -1
            && rightSib.numItems() > 1)
      {
        // insert parent into index 0
        node.insertItem(0, parent.getItem(rightSibIndex - 1));
        
        // make right sibling's first child the last child here
        node.setChild(0, rightSib.getChild(0));
        if(node.getChild(0) != null)
                node.getChild(0).setParent(node);
        
          // store the third last pointer reference
          TFNode pointer = rightSib.getChild(0);
          
        // make right sibling's first item the new parent
        parent.replaceItem(rightSibIndex - 1, rightSib.removeItem(0));
          
          // reset the last pointer
          rightSib.setChild(rightSib.numItems(), pointer);
      }
      // neither sibling has enough elements
      else
      {
        // left fusion
          if(leftSib != null
             && leftSib.numItems() == 1)
          {
              // store nodes pointer
              TFNode pointer = node.getChild(0);
              
              if(treeComp.isLessThan(((Item) leftSib.getItem(0)).key(), ((Item) parent.getItem(leftSibIndex)).key()))
            leftSib.addItem(1, parent.removeItem(leftSibIndex));
              else
            leftSib.insertItem(0, parent.removeItem(leftSibIndex));
            
              // reset the last pointer
              leftSib.setChild(leftSib.numItems(), pointer);
              
              if(pointer != null)
                pointer.setParent(leftSib);
              
              parent.setChild(leftSibIndex, leftSib);
              newNode = leftSib;
          }
          // right fusion
          else
          {
              // store the nodes pointer
              TFNode pointer = node.getChild(rightSib.numItems());
              
              if(treeComp.isLessThan(((Item) rightSib.getItem(0)).key(), ((Item) parent.getItem(rightSibIndex - 1)).key()))
                   rightSib.addItem(1, node.getParent().removeItem(rightSibIndex - 1));
              else
                   rightSib.insertItem(0, node.getParent().removeItem(rightSibIndex - 1));
            
              // reset the first pointer
              rightSib.setChild(0, pointer);
              
              if(pointer != null)
                  pointer.setParent(rightSib);
              
              parent.setChild(rightSibIndex - 1, rightSib);
              newNode = rightSib;
          }
      }
      
      // rebalance parent recursively if it has zero items and is not he parent
      if(parent.numItems() == 0)
      {
          if(parent != root())
             rebalance(parent);
          else
          {
             treeRoot = newNode;
             newNode.setParent(null);
             
             size--;
          }
      }
      
      node = null;
  }
  /**
   * Searches the tree until it finds a node with an item that is greater than
   * or equal to the specified key.
   * 
   * @param key Object the key to be compared against
   * @param node TFNode the node to be the starting point, usually the root
   * @return TFNode the node that holds the first greater or equal item
   */
  protected TFNode firstGreaterOrEqualNode(Object key, TFNode start)
  {
      // recursive exit condition
      if(start == null)
          return null;
      
      int index = firstGreaterOrEqualItem(key, start);
      
      if(index == -1)
      {
          index = start.numItems();
          return firstGreaterOrEqualNode(key, start.getChild(index));
      }
      
      if(treeComp.isLessThan(key, ((Item) start.getItem(index)).key()))
         return firstGreaterOrEqualNode(key, start.getChild(index));
      else if(treeComp.isGreaterThan(key, ((Item) start.getItem(index)).key()))
              return firstGreaterOrEqualNode(key, start.getChild(index + 1));
      else
          return start;
  }
  
  /**
   * Searches the node until it finds a node that is greater than or equal to
   * the specified key.
   * 
   * @param key Object the key to be compared against
   * @param node TFNode the node to be searched
   * @return int the index of the first greater than or equal item
   */
  protected int firstGreaterOrEqualItem(Object key, TFNode node) throws ElementNotFoundException
  {
      if(node == null)
          throw new ElementNotFoundException();
      
      // find first greater or equal item within the node
      for(int i = 0; i < node.numItems(); i++)
      {
          if (treeComp.isGreaterThanOrEqualTo(((Item) node.getItem(i)).key(), key))
              return i;
      }
      // no greater or equal item was found
      return -1;
  }
  /**
   * Searches the tree until it finds a node with an item that is greater than
   * or equal to the specified key.  This is the point at which it will insert
   * the a new node.
   * 
   * @param key Object the key to be compared against
   * @param start TFNode the node to be the starting point, usually the root
   * @return TFNode the node that holds the first greater or equal item
   */
  protected TFNode findInsertionPointer(Object key, TFNode start)
  {
      // exit condition for recursion
      if(start == null)
          return null;
      int index = firstGreaterOrEqualItem(key, start); 
      // if a greater or equal item was not found in node, add at end
      if(index == -1)
          index = start.numItems();
      // continue searching down tree
      TFNode node = findInsertionPointer(key, start.getChild(index));
      if(node == null)
          return start;
      return node;
  }
  /**
   * Pops the third item out of a node and sends it to the parent, thus creating
   * the children nodes off of that parent then. Essentially a node split. Usually
   * called directly after an insert if the insert causes a node to become too full.
   * 
   * @param left TFNode the node to be split
   */
  protected void nodePop(TFNode left)
  {
      TFNode parent;
      TFNode right = new TFNode();
      int index;
      // if no parent exists, we are the root
      if(left.getParent() == null)
      {
          parent = new TFNode();
          treeRoot = parent;
          index = 0;
      }
      else
      {
          parent = left.getParent();
          index = firstGreaterOrEqualItem(((Item) left.getItem(2)).key(), parent);
          // if a greater or equal item was not found in node, add at end
          if(index == -1)
              index = parent.numItems();
      }
      // insert items in new locations
      parent.insertItem(index, left.getItem(2));
      right.addItem(0, left.getItem(3));
      // set new child pointers
      parent.setChild(index, left);
      parent.setChild(index + 1, right);
      // set parent pointers
      left.setParent(parent);
      right.setParent(parent);
      // conditions if the node has more than three children
      if(left.getChild(3) != null)
      {
          right.setChild(0, left.getChild(3));
          right.getChild(0).setParent(right);
      }
      if(left.getChild(4) != null)
      {
          right.setChild(1, left.getChild(4));
          right.getChild(1).setParent(right);
      }
      // store the third pointer reference
      TFNode pointer = left.getChild(2);
      // remove the two items
      left.removeItem(2);
      left.removeItem(2);
      // reassign the child which was lost in the remove
      left.setChild(2, pointer);
      // check to see if the parent is too full now; call recursion
      if(parent.numItems() == parent.maxItems() + 1)
          nodePop(parent);
  }
  /**
   * The main method which the program executes from and which handles all
   * testing and input/output.
   * 
   * @param args String[]
   */
  public static void main(String[] args) throws IOException
  {
        Comparator myComp = new IntegerComparator();
        TwoFourTree myTree = new TwoFourTree(myComp);
        TwoFourTree firstTree = new TwoFourTree(myComp);
        TwoFourTree secondTree = new TwoFourTree(myComp);
        BufferedReader myReader = new BufferedReader(new InputStreamReader(System.in));
        String input;
        boolean go = true;
    
        while(go == true)
        {
            System.out.print("Format like this:  -a 37 to add a 37 to the tree. -r 37 to remove a 37 from the tree: ");
            input = myReader.readLine();
            
            if(input.substring(0, 2).equals("-a"))
            {
                Integer myInt = new Integer(input.substring(3, input.length()));
                myTree.insertElement(myInt, myInt);
                myTree.printAllElements();
            }
            else if(input.substring(0, 2).equals("-r"))
            {
                Integer myInt = new Integer(input.substring(3, input.length()));
                myTree.removeElement(myInt);
                myTree.printAllElements();
            }
            else
                System.out.print("\nYou're bad!");
            
            System.out.print("\n");
                
        }
        
        /*System.out.println("Loading firstTree with values ...");
        
        Integer firstInt1 = new Integer(20);
        firstTree.insertElement(firstInt1, firstInt1);
        Integer firstInt2 = new Integer(50);
        firstTree.insertElement(firstInt2, firstInt2);
        Integer firstInt3 = new Integer(30);
        firstTree.insertElement(firstInt3, firstInt3);
        Integer firstInt4 = new Integer(40);
        firstTree.insertElement(firstInt4, firstInt4);
        Integer firstInt5 = new Integer(15);
        firstTree.insertElement(firstInt5, firstInt5);
        Integer firstInt6 = new Integer(35);
        firstTree.insertElement(firstInt6, firstInt6);
        Integer firstInt7 = new Integer(55);
        firstTree.insertElement(firstInt7, firstInt7);
        Integer firstInt8 = new Integer(38);
        firstTree.insertElement(firstInt8, firstInt8);
        Integer firstInt9 = new Integer(17);
        firstTree.insertElement(firstInt9, firstInt9);
        Integer firstInt10 = new Integer(37);
        firstTree.insertElement(firstInt10, firstInt10);
        Integer firstInt11 = new Integer(16);
        firstTree.insertElement(firstInt11, firstInt11);
        Integer firstInt12 = new Integer(36);
        firstTree.insertElement(firstInt12, firstInt12);
        Integer firstInt13 = new Integer(15);
        firstTree.insertElement(firstInt13, firstInt13);
        Integer firstInt14 = new Integer(36);
        firstTree.insertElement(firstInt14, firstInt14);
        Integer firstInt15 = new Integer(30);
        firstTree.insertElement(firstInt15, firstInt15);
        Integer firstInt16 = new Integer(34);
        firstTree.insertElement(firstInt16, firstInt16);
        Integer firstInt17 = new Integer(34);
        firstTree.insertElement(firstInt17, firstInt17);
        Integer firstInt18 = new Integer(30);
        firstTree.insertElement(firstInt18, firstInt18);
        Integer firstInt19 = new Integer(30);
        firstTree.insertElement(firstInt18, firstInt18);
       
        System.out.println("firstTree is fully loaded as follows:");
        firstTree.printAllElements();
        System.out.println("Checking parent/child connections ...");
        firstTree.checkTree(firstTree.root());
        System.out.println("All parent/child connections valid.");
        
        System.out.println("\nRemove 30");
        firstTree.removeElement(30);
        System.out.println("Removed successfully. Print new tree:");
        firstTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 30");
        firstTree.removeElement(30);
        System.out.println("Removed successfully. Print new tree:");
        firstTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 30");
        firstTree.removeElement(30);
        System.out.println("Removed successfully. Print new tree:");
        firstTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 30");
        firstTree.removeElement(30);
        System.out.println("Removed successfully. Print new tree:");
        firstTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 15");
        firstTree.removeElement(15);
        System.out.println("Removed successfully. Print new tree:");
        firstTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 55");
        firstTree.removeElement(55);
        System.out.println("Removed successfully. Print new tree:");
        firstTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 35");
        firstTree.removeElement(35);
        System.out.println("Removed successfully. Print new tree:");
        firstTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 38");
        firstTree.removeElement(38);
        System.out.println("Removed successfully. Print new tree:");
        firstTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 40");
        firstTree.removeElement(40);
        System.out.println("Removed successfully. Print new tree:");
        firstTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 36");
        firstTree.removeElement(36);
        System.out.println("Removed successfully. Print new tree:");
        firstTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 17");
        firstTree.removeElement(17);
        System.out.println("Removed successfully. Print new tree:");
        firstTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 34");
        firstTree.removeElement(34);
        System.out.println("Removed successfully. Print new tree:");
        firstTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 34");
        firstTree.removeElement(34);
        System.out.println("Removed successfully. Print new tree:");
        firstTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 36");
        firstTree.removeElement(36);
        System.out.println("Removed successfully. Print new tree:");
        firstTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 20");
        firstTree.removeElement(20);
        System.out.println("Removed successfully. Print new tree:");
        firstTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 37");
        firstTree.removeElement(37);
        System.out.println("Removed successfully. Print new tree:");
        firstTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 16");
        firstTree.removeElement(16);
        System.out.println("Removed successfully. Print new tree:");
        firstTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 50");
        firstTree.removeElement(50);
        System.out.println("Removed successfully. Print new tree:");
        firstTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 15");
        firstTree.removeElement(15);
        System.out.println("Removed successfully. Print new tree:");
        firstTree.printAllElements();
        System.out.println("done");
        System.out.println("\n\nLoading secondTree with values ...");
        
        Integer secondInt1 = new Integer(47);
        secondTree.insertElement(secondInt1, secondInt1);
        Integer secondInt2 = new Integer(83);
        secondTree.insertElement(secondInt2, secondInt2);
        Integer secondInt3 = new Integer(22);
        secondTree.insertElement(secondInt3, secondInt3);
        Integer secondInt4 = new Integer(16);
        secondTree.insertElement(secondInt4, secondInt4);
        Integer secondInt5 = new Integer(49);
        secondTree.insertElement(secondInt5, secondInt5);
        Integer secondInt6 = new Integer(100);
        secondTree.insertElement(secondInt6, secondInt6);
        Integer secondInt7 = new Integer(38);
        secondTree.insertElement(secondInt7, secondInt7);
        Integer secondInt8 = new Integer(3);
        secondTree.insertElement(secondInt8, secondInt8);
        Integer secondInt9 = new Integer(53);
        secondTree.insertElement(secondInt9, secondInt9);
        Integer secondInt10 = new Integer(66);
        secondTree.insertElement(secondInt10, secondInt10);
        Integer secondInt11 = new Integer(19);
        secondTree.insertElement(secondInt11, secondInt11);
        Integer secondInt12 = new Integer(23);
        secondTree.insertElement(secondInt12, secondInt12);
        Integer secondInt13 = new Integer(24);
        secondTree.insertElement(secondInt13, secondInt13);
        Integer secondInt14 = new Integer(88);
        secondTree.insertElement(secondInt14, secondInt14);
        Integer secondInt15 = new Integer(1);
        secondTree.insertElement(secondInt15, secondInt15);
        Integer secondInt16 = new Integer(97);
        secondTree.insertElement(secondInt16, secondInt16);
        Integer secondInt17 = new Integer(94);
        secondTree.insertElement(secondInt17, secondInt17);
        Integer secondInt18 = new Integer(35);
        secondTree.insertElement(secondInt18, secondInt18);
        Integer secondInt19 = new Integer(51);
        secondTree.insertElement(secondInt19, secondInt19);
        
        System.out.println("firstTree is fully loaded as follows:");
        secondTree.printAllElements();
        System.out.println("Checking parent/child connections ...");
        secondTree.checkTree(secondTree.root());
        System.out.println("All parent/child connections valid.");
        
        System.out.println("\nRemove 19");
        secondTree.removeElement(19);
        System.out.println("Removed successfully. Print new tree:");
        secondTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 3");
        secondTree.removeElement(3);
        System.out.println("Removed successfully. Print new tree:");
        secondTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 66");
        secondTree.removeElement(66);
        System.out.println("Removed successfully. Print new tree:");
        secondTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 88");
        secondTree.removeElement(88);
        System.out.println("Removed successfully. Print new tree:");
        secondTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 94");
        secondTree.removeElement(94);
        System.out.println("Removed successfully. Print new tree:");
        secondTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 100");
        secondTree.removeElement(100);
        System.out.println("Removed successfully. Print new tree:");
        secondTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 97");
        secondTree.removeElement(97);
        System.out.println("Removed successfully. Print new tree:");
        secondTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 47");
        secondTree.removeElement(47);
        System.out.println("Removed successfully. Print new tree:");
        secondTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 53");
        secondTree.removeElement(53);
        System.out.println("Removed successfully. Print new tree:");
        secondTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 38");
        secondTree.removeElement(38);
        System.out.println("Removed successfully. Print new tree:");
        secondTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 24");
        secondTree.removeElement(24);
        System.out.println("Removed successfully. Print new tree:");
        secondTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 83");
        secondTree.removeElement(83);
        System.out.println("Removed successfully. Print new tree:");
        secondTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 49");
        secondTree.removeElement(49);
        System.out.println("Removed successfully. Print new tree:");
        secondTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 23");
        secondTree.removeElement(23);
        System.out.println("Removed successfully. Print new tree:");
        secondTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 51");
        secondTree.removeElement(51);
        System.out.println("Removed successfully. Print new tree:");
        secondTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 1");
        secondTree.removeElement(1);
        System.out.println("Removed successfully. Print new tree:");
        secondTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 22");
        secondTree.removeElement(22);
        System.out.println("Removed successfully. Print new tree:");
        secondTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 16");
        secondTree.removeElement(16);
        System.out.println("Removed successfully. Print new tree:");
        secondTree.printAllElements();
        System.out.println("");
        System.out.println("Remove 35");
        secondTree.removeElement(35);
        System.out.println("Removed successfully. Print new tree:");
        secondTree.printAllElements();
        System.out.println("done");*/
  }
  public void printAllElements() {
    int indent = 0;
    if (root() == null) {
      System.out.println("The tree is empty");
    }
    else {
      printTree(root(), indent);
    }
  }
  public void printTree(TFNode start, int indent) {
    if (start == null) {
      return;
    }
    for (int i = 0; i < indent; i++) {
      System.out.print(" ");
    }
    printTFNode(start);
    indent += 4;
    int numChildren = start.numItems() + 1;
    for (int i = 0; i < numChildren; i++) {
      printTree(start.getChild(i), indent);
    }
  }
  public void printTFNode(TFNode node) {
    int numItems = node.numItems();
    for (int i = 0; i < numItems; i++) {
      System.out.print( ( (Item) node.getItem(i)).element() + " ");
    }
    System.out.println();
  }
  // checks if tree is properly hooked up, i.e., children point to parents
  public void checkTree(TFNode start) {
    if (start == null) {
      return;
    }
    if (start.getParent() != null) {
      TFNode parent = start.getParent();
      int childIndex = 0;
      for (childIndex = 0; childIndex <= parent.numItems(); childIndex++) {
        if (parent.getChild(childIndex) == start) {
          break;
        }
      }
      // if child wasn't found, print problem
      if (childIndex > parent.numItems()) {
        System.out.println("Child to parent confusion");
        printTFNode(start);
      }
    }
    if (start.getChild(0) != null) {
      for (int childIndex = 0; childIndex <= start.numItems(); childIndex++) {
        if (start.getChild(childIndex).getParent() != start) {
          System.out.println("Parent to child confusion");
          printTFNode(start);
        }
      }
    }
    int numChildren = start.numItems() + 1;
    for (int childIndex = 0; childIndex < numChildren; childIndex++) {
      checkTree (start.getChild(childIndex));
    }
  }
}
/**
 * Basic storage element for the 2-4 Tree
 *
 * @author Dr. Gallagher
 * @version 1.0
 * Created 2 Mar 2001
 * Description: The basic node for a 2-4 tree.  Contains an array of Items,
 * an array of references to children TFNodes, a pointer to a parent TFNode,
 * and a count of how many Items are stored in the node.
 */
class TFNode {
    private static final int MAX_ITEMS = 3;
    private int numItems = 0;
    private TFNode nodeParent;
    private TFNode[] nodeChildren;
    private Object[] nodeItems;
    public TFNode() {
            // make them one bigger than needed, so can handle oversize nodes
            // during inserts
        nodeChildren = new TFNode[MAX_ITEMS+2];
        nodeItems = new Object[MAX_ITEMS+1];
    }
    public int numItems () {
        return numItems;
    }
    public int maxItems() {
        return MAX_ITEMS;
    }
    public TFNode getParent() {
        return nodeParent;
    }
    public void setParent (TFNode parent) {
        nodeParent = parent;
    }
    public Object getItem(int index) {
        if ( (index < 0) || (index > (numItems-1) ) )
            throw new TFNodeException();
        return nodeItems[index];
    }
        // adds, but does not extend array; so it overwrites anything there
    public void addItem (int index, Object data) {
            // always add at end+1; check that you are within array
        if ( (index < 0) || (index > numItems) || (index > MAX_ITEMS) )
            throw new TFNodeException();
        nodeItems[index] = data;
        numItems++;
    }
        // this function inserts an item into the node, and adjusts into child
        // pointers to add the proper corresponding pointer
    public void insertItem (int index, Object data) {
        if ( (index < 0) || (index > numItems) || (index > MAX_ITEMS) )
            throw new TFNodeException();
            // adjust Items
        for (int ind=numItems; ind > index; ind--) {
            nodeItems[ind] = nodeItems[ind-1];
        }
            // insert new data into hole made
        nodeItems[index] = data;
            // adjust children pointers; if inserting into index=1, we make
            // pointers 1 and 2 to point to 1; this is because whoever called
            // this function will fix one of them later; index 0 doesn't change;
            // pointer 3 becomes pointer 2; pointer 4 becomes 3, etc.
        for (int ind=numItems+1; ind > index; ind--) {
            nodeChildren[ind] = nodeChildren[ind-1];
        }
        numItems++;
    }
        // this method removes item, and shrinks array
    public Object removeItem (int index) {
        if ( (index < 0) || (index > (numItems-1) ) )
            throw new TFNodeException();
        Object removedItem = nodeItems[index];
        for (int ind=index; ind < numItems-1; ind++) {
            nodeItems[ind] = nodeItems[ind+1];
        }
        nodeItems[numItems-1] = null;
            // fix children pointers also
            // typically, you wouldn't expect to do a removeItem unless
            // children are null, because removal of an item will mess up the
            // pointers; however, here we will simply delete the child to the
            // left of the removed item; i.e., the child with same index
        for (int ind=index; ind < numItems; ind++) {
            nodeChildren[ind] = nodeChildren[ind+1];
        }
        nodeChildren[numItems] = null;
        numItems--;
        return removedItem;
    }
        // this method removes item, but does not shrink array
    public Object deleteItem (int index) {
        if ( (index < 0) || (index > (numItems-1) ) )
            throw new TFNodeException();
        Object removedItem = nodeItems[index];
        nodeItems[index] = null;
        numItems--;
        return removedItem;
    }
        // replaces Item at index with newItem, returning the old Item
    public Object replaceItem (int index, Object newItem) {
        if ( (index < 0) || (index > (numItems-1) ) )
            throw new TFNodeException();
        Object returnItem = nodeItems[index];
        nodeItems[index] = newItem;
        return returnItem;
    }
    public TFNode getChild (int index) {
        if ( (index < 0) || (index > (MAX_ITEMS+1)) )
            throw new TFNodeException();
        return nodeChildren[index];
    }
    public void setChild (int index, TFNode child) {
        if ( (index < 0) || (index > (MAX_ITEMS+1)) )
            throw new TFNodeException();
        nodeChildren[index] = child;
    }
}
class TFNodeException extends RuntimeException {
    public TFNodeException() {
        super ("Problem with TFNode");
    }
    public TFNodeException(String errorMsg) {
        super (errorMsg);
    }
}
interface Dictionary {
    public int size();
    public boolean isEmpty();
    public Object findElement (Object key) throws ElementNotFoundException;
    public void insertElement (Object key, Object element);
    public Object removeElement (Object key) throws ElementNotFoundException;
}
class ElementNotFoundException  extends RuntimeException
{
    public ElementNotFoundException()
    {
    }
}
class Item {
    private Object itemKey;
    private Object itemElement;
    public Item() {
        this (null, null);
    }
    public Item(Object key, Object element) {
        itemKey = key;
        itemElement = element;
    }
    public Object key() {
        return itemKey;
    }
    public void setKey(Object key) {
        itemKey = key;
    }
    public Object element() {
        return itemElement;
    }
    public void setElement (Object element) {
        itemElement = element;
    }
}interface Comparator {
    public boolean isLessThan (Object obj1, Object obj2);
    public boolean isLessThanOrEqualTo (Object obj1, Object obj2);
    public boolean isGreaterThan (Object obj1, Object obj2);
    public boolean isGreaterThanOrEqualTo (Object obj1, Object obj2);
    public boolean isEqual (Object obj1, Object obj2);
    public boolean isComparable (Object obj);
}class IntegerComparator implements Comparator {
    public IntegerComparator() {
    }
    public boolean isLessThan (Object obj1, Object obj2) {
        Integer myInt1;
        Integer myInt2;
        try {
            myInt1 = (Integer) obj1;
            myInt2 = (Integer) obj2;
        }
        catch (ClassCastException exc) {
            throw new InvalidIntegerException ("Object not an integer");
        }
        return ( myInt1.intValue() < myInt2.intValue() );
    }
    public boolean isLessThanOrEqualTo (Object obj1, Object obj2) {
        return ( ! isLessThan (obj2, obj1) );
    }
    public boolean isGreaterThan (Object obj1, Object obj2) {
        return ( isLessThan (obj2, obj1) );
    }
    public boolean isGreaterThanOrEqualTo (Object obj1, Object obj2) {
        return ( ! isLessThan (obj1, obj2) );
    }
    public boolean isEqual (Object obj1, Object obj2) {
        return ( (! isLessThan (obj1, obj2)) && (! isLessThan (obj2, obj1)) );
    }
    public boolean isComparable (Object obj) {
        try {
            Integer myInt = (Integer) obj;
            return true;
        }
        catch (ClassCastException exc) {
            return false;
        }
    }
}
class InvalidIntegerException extends RuntimeException {
    public InvalidIntegerException(String errorMsg) {
        super (errorMsg);
    }
}