///// STUDENT TO FILL OUT ALL THE STUB METHODS IN THIS CLASS.

package tree234;

/**
* Represents nodes with 4 subtrees of a 2-3-4 tree.
* It contains a left Tree234, a left data object, a left center Tree234, a center
* data object, a right center tree, a right data object, and a right Tree234.
* @author  Dung X. Nguyen - Copyright 2000 - All Rights Reserved.
*/
class Node4 extends ANode234
{
	private Tree234 _leftTree      = new Tree234 ();  // Data invariant:  _leftTree     != null
   private Integer _leftDat;	                       // Data invariant:  _leftDat      != null
	private Tree234 _leftMidTree   = new Tree234 ();  // Data invariant:  _leftMidTree  != null
   private Integer _midDat;	                       // Data invariant:  _midDat       != null
	private Tree234 _rightMidTree  = new Tree234 ();  // Data invariant:  _rightMidTree != null
   private Integer _rightDat;	                       // Data invariant:  _rightDat     != null
	private Tree234 _rightTree     = new Tree234 ();  // Data invariant:  _rightTree    != null
                                                     // Data invariant:  _leftDat < _midDat < _rightDat.

   /**
   * Initializes this Node4 to contain 4 empty subtrees and the 3 input parameters in the correct order.
   * @param lo < hi
   * @param hi > lo
   * @param n an Integer to be stored in this Node4 in the correct order
   */
   Node4(Integer lo, Integer hi, Integer n)
  {
  	   int loVal = lo.intValue ();
  	   int hiVal = hi.intValue ();
  	   int nVal  = n.intValue ();
  	   if (hiVal < nVal)
  	   {
  	      _leftDat  = lo;
  	      _midDat   = hi;
  	      _rightDat = n;
  	   }
  	   else if (loVal < nVal)  // nVal < hiVal.
  	   {
  	      _leftDat  = lo;
  	      _midDat   = n;
  	      _rightDat = hi;
  	   }
  	   else
  	   {
  	      _leftDat  = n;
  	      _midDat   = lo;
  	      _rightDat = hi;
  	   }
   }

   /**
   * Initializes this Node4 to contain the 4 given subtrees and the 3 given Integers in the correct order.
   * @param lTree != null, the new leftmost subtree, all elements in lTree < lN.
   * @param lN < mN, to be stored as the leftmost data, < all elements in lmTree
   * @param lmTree != null, the new middle-left subtree, all elements in lmTree < mN
   * @param mN < rN, to be stored as the middle data, < all elements in rmTree
   * @param rmTree != null, the new middle-right subtree, all elements in rmTree < rN.
   * @param rN, to be stored as the rightmost data, < all elements in rTree.
   * @param rTree != null, the new rightmost subtree
   */
   Node4(Tree234 lTree, Integer lN, Tree234 lmTree, Integer mN, Tree234 rmTree, Integer rN, Tree234 rTree)
   {
      _leftTree     = lTree;
      _leftDat      = lN;
      _leftMidTree  = lmTree;
      _midDat       = mN;
      _rightMidTree = rmTree;
      _rightDat     = rN;
      _rightTree    = rTree;
   }

   /**
   * Splits this Node4 into a Node2 with appropriate left and right subtrees before inserting the data.
   * Called when owner has no parent tree, i.e. this is the top level root.
   * @param n != null.
   * @param owner the owner of this Node4.
   */
	final void insert (Integer n, Tree234 owner)
   {
//// STUDENT TO WRITE CODE.
   }

	/**
   * Helps the owner's parent tree insert data, using the other two owner's siblings if necessary.
   * This is a Node4.  Thus the owner's parent is not a leaf.
   * Asks the owner's parent to insert data not as a leaf.
   * @param ownerParent the parent of owner.
   * @param ownerSib1 one of the siblings of owner.
   * @param ownerSib2 the sibling of ownerSib1 and owner.
   * @param n an Integer to be properly inserted into ownerParent.
   * @param owner the owner of this Node4
   */
	final void helpParentInsert (Tree234 ownerParent, Tree234 ownerSib1, Tree234 ownerSib2, Integer n, Tree234 owner)
	{
//// STUDENT TO WRITE CODE.
	}

	/**
   * Helps the owner's parent insert data, using the one remaining owner's sibling if necessary.
   * This is a Node4.  Thus the owner's parent is not a leaf.
   * Asks the owner's parent to insert data not as a leaf. 
   * @param ownerParent the parent of owner.
   * @param ownerSib one of the two sibblings of owner.
   * @param n an Integer to be properly inserted into ownerParent.
   * @param owner the owner of this Node4
    */
	final void helpParentInsert (Tree234 ownerParent, Tree234 ownerSib, Integer n, Tree234 owner)
	{
//// STUDENT TO WRITE CODE.
	}

	/**
   * Helps the owner's parent insert data with the knowledge that all the owner's siblings are empty .
   * This is a Node4.  Thus the owner's parent is not a leaf.
   * Asks the owner's parent to insert data not as a leaf. 
   * @param ownerParent the parent of owner.
   * @param n an Integer to be properly inserted into ownerParent.
   * @param owner the owner of this Node4
   */
	void helpParentInsert (Tree234 ownerParent, Integer n, Tree234 owner)
	{
//// STUDENT TO WRITE CODE.
	}

   /**
   * Inserts data into owner when this Node4 is a leaf node.
   * Throws an IllegalStateException since a Node4 can never be asked by its subtrees
   * to insert as a leaf.  A Node4 is always split up whenever an insertion is to be done.
   * @param n an Integer to be properly inserted into owner.
   * @param owner the owner of this Node4
   */
	void insertAsLeaf(Integer n, Tree234 owner)
	{
      throw new IllegalStateException ("4-Node is never checked for being a leaf!");
	}

   /**
   * Inserts data into the owner when this Node4 is NOT a leaf node.
   * Throws an IllegalStateException since a Node4 can never be the parent of a non-empty
   * tree  A Node4 is always split up whenever an insertion is to be done.
   * @param n an Integer to be properly inserted into owner.
   * @param owner the owner of this Node4
   */
	void insertNotAsLeaf (Integer n, Tree234 owner)
	{
      throw new IllegalStateException ("4-Node cannot be a parent of a non-empty node!");
	}

  /**
   * Called when onwer has a parent tree.
   * This is a Node4.  Need to split and re-attach to the owner's parent before inserting data.
   * @param ownerParent the parent of this tree.
   * @param n an Integer to be properly inserted into owner.
   * @param owner the owner of this Node4
   */
   final void insertAsChild (Tree234 ownerParent, Integer n, Tree234 owner)
   {
//// STUDENT TO WRITE CODE.
   }

   /**
   * Attaches the 3 components a 2-node to the owner tree in the proper order.
   * Throws an IllegalStateException since it does not make sense to attach additional
   * data and subtrees to a Node4.
   * @param lTree a 2-3-4 tree whose elements are less than n.
   * @param n a data element.
   * @param rTree a 2-3-4 tree whose elements are greater than n.
   * @param owner the owner of this Node4, must be the parent of a Tree234.
   */
   final void attach (Tree234 lTree, Integer n, Tree234 rTree, Tree234 owner)
   {
      throw new IllegalStateException ("should never be called.");
   }
}