Node

////////////////////////////////////////////////////////////////
class Node
   {
   private static final int ORDER = 4;
   private int numItems; // number of items currently in a node
   private Node parent; // the node's parent
   private Node childArray[] = new Node[ORDER]; // four cells long, holds references to children the node might have
   private DataItem itemArray[] = new DataItem[ORDER-1]; // three cells long, holds references to DataItem contained in the node
   // data items in itemArray may need to be shifted to make room to insert/remove in ORDER.
   // itemArray is considered to be an ordered array
// -------------------------------------------------------------
   // connect child to this node
   public void connectChild(int childNum, Node child)
      {
      childArray[childNum] = child;
      if(child != null)
         child.parent = this;
      }
// -------------------------------------------------------------
   // disconnect child from this node, return it
   public Node disconnectChild(int childNum)
      {
      Node tempNode = childArray[childNum];
      childArray[childNum] = null;
      return tempNode;
      }
// -------------------------------------------------------------
   public Node getChild(int childNum)
      { return childArray[childNum]; }
// -------------------------------------------------------------
   public Node getParent()
      { return parent; }
// -------------------------------------------------------------
   public boolean isLeaf()
       // returns true if childArray[0] == null, and false if not
       // basically, if the childArray at the first location is null, then the
       // parent array is actually a leaf and there is no childArray
      { return (childArray[0]==null) ? true : false; }
// -------------------------------------------------------------
   public int getNumItems() // get number of items currently in node
     { return numItems; }
// -------------------------------------------------------------
   public DataItem getItem(int index)   // get DataItem at index
      { return itemArray[index]; }
// -------------------------------------------------------------
   public boolean isFull() // if # of items = 3, array is full, returns true, false if not full
      { return (numItems==ORDER-1) ? true : false; }
// -------------------------------------------------------------
   // searches through a node for a data item with a particular key, returns index of item
   public int findItem(long key)       // return index of item (within node)
      {
      for(int j=0; j<ORDER-1; j++)         // go through array of data items
         {
         if(itemArray[j] == null)   // if we go through each item and end at null
            break; // break out of loop, not found, return -1
         else if(itemArray[j].dData == key) // if the items data matches the key
            return j; // return the index that it belongs to
         }
      return -1; // return -1
      }  // end findItem
// -------------------------------------------------------------
   // find the minimum value from a set of data
   public long getMin() {
       return itemArray[0].dData; // item at [0] should be smallest data item
   } // end findMin()
// -------------------------------------------------------------
   // inserts a new data item into a node, moving existing items if necessary
   public int insertItem(DataItem newItem)
      {
      // assumes node is not full
      numItems++;                          // will add new item
      long newKey = newItem.dData;         // key of new item

      for(int j=ORDER-2; j>=0; j--)        // start on right (for j = 2 until it goes down to 0, decrement)
         {                                 //    examine items
         if(itemArray[j] == null)          // if item null,
            continue;                      // skips current iteration of the loop, go left one cell
         else                              // if item array is not null
            {
            long itsKey = itemArray[j].dData; // get its key
            if(newKey < itsKey)            // if the new data item is smaller than the key we are comparing
               itemArray[j+1] = itemArray[j]; // shift the old data item to the right (rules of 2-3-4 tree, sorts it)
            else // else the new key is bigger
               {
               itemArray[j+1] = newItem;   // insert new item right of old item
               return j+1;                 // return index to
               }                           //    new item
            }  // end else (not null)
         }  // end for                     // shifted all items,
      itemArray[0] = newItem;              // if there is no contents in the item array, insert into first position
      return 0; // return the index
      }  // end insertItem()
// -------------------------------------------------------------
   public DataItem removeItem()        // remove largest item
      {
      // assumes node not empty
      DataItem temp = itemArray[numItems-1];  // save item
      itemArray[numItems-1] = null;           // disconnect it
      numItems--;                             // one less item
      return temp;                            // return item
      }
// -------------------------------------------------------------
   public void displayNode()           // format "/24/56/74/"
      {
      for(int j=0; j<numItems; j++)
         itemArray[j].displayItem();   // "/56"
      System.out.println("/");         // final "/"
      }
// -------------------------------------------------------------
   }  // end class Node