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

package tree234;

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

   /**
   * Initializes this Node3 to contain 2 Integers sorted in ascendig order and three empty subtrees.
   * @param n0 != null
   * @param n1 != null
   */
   Node3(Integer n0, Integer n1)
   {
	   if (n0.intValue () < n1.intValue ())
	   {
	      _leftDat   = n0;
	      _rightDat  = n1;
	   }
	   else
	   {
	      _leftDat   = n1;
	      _rightDat  = n0;
	   }
   }

   /**
   * Initializes this Node3 to contain two given Integers and the given left, middle, and right subtrees.
   * @param lTree != null  the left subtree, all elements in lTree are less than lN.
   * @param lN != null  less than all elements in mTree.
   * @param mTree != null the middle subtree, all elements in mTree are less than rN.
   * @param rN != null less than all elements in rTree.
   * @param rTree != null  the right subtree
   */
   Node3(Tree234 lTree, Integer lN, Tree234 mTree, Integer rN, Tree234 rTree)
   {
      _leftTree  = lTree;
      _leftDat  = lN;
      _midTree   = mTree;
      _rightDat = rN;
      _rightTree = rTree;
   }

   /**
   * Instead of checking the subtrees for emptiness, hands the mid and right subtrees
   * to the left subtree and asks it to help owner insert the data.
   * @param n != null.
   * @param owner the owner of this Node2.
   */
	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 Node3.  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 Node3
   */
	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 Node3.  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 siblings of owner.
   * @param n an Integer to be properly inserted into ownerParent.
   * @param owner the owner of this Node3
    */
	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 Node3.  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 Node3
   */
	final void helpParentInsert (Tree234 ownerParent, Integer n, Tree234 owner)
	{
//// STUDENT TO WRITE CODE.
	}

   /**
   * Inserts data into owner when this Node2 is a leaf node.
   * Change the owner's root to an appropriate Node4.
   * @param n an Integer to be properly inserted into owner.
   * @param owner the owner of this Node3
   */
   final void insertAsLeaf (Integer n, Tree234 owner)
	{
  	   owner.changeRoot (new Node4 (_leftDat, _rightDat, n));
	}

   /**
   * Inserts data into the owner when this Node2 is NOT a leaf node.
   * By comparing the value of the input Integer with the root data, asks the appropriate
   * subtree to insert data as a child of the owner.
   * @param n != root data
   * @param owner the owner of this Node3
   */
	final void insertNotAsLeaf(Integer n, Tree234 owner)
	{
//// STUDENT TO WRITE CODE.
	}

  /**
   * Inserts n into the owner tree.
   * The owner of this Node3 is is a subtree of a given parent tree.  There is no need to split.
   * @param ownerParent the parent of this tree.
   * @param n an Integer to be properly inserted into owner.
   * @param owner the owner of this Node3
   */
   final void insertAsChild (Tree234 ownerParent, Integer n, Tree234 owner)
   {
      insert (n, owner); // short cut for owner.insert (n);
   }

   /**
   * Attaches the 3 components a 2-node to the owner tree in the proper order.
   * Changes the state of the owner to an appropriate Node3.
   * @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 Node3, must be the parent of a Node3.
   */
   final void attach (Tree234 lTree, Integer n, Tree234 rTree, Tree234 owner)
   {
//// STUDENT TO WRITE CODE.
   }
}