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

package tree234;

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

   /**
   * Initializes this Node2 to contain n and two empty subtrees.
   * @param n != null
   */
   Node2 (Integer n)
   {
  	   _data      = n;
   }

   /**
   * Initializes this Node2 to contain the given data and the given left and right subtrees.
   * @param lTree != null  the left subtree, all elements in lTree are less than n.
   * @param n != null less than all elements in rTree.
   * @param rTree != null  the right subtree
   */
   Node2(Tree234 lTree, Integer n, Tree234 rTree)
   {
  	   _data      = n;
  	   _leftTree  = lTree;
  	   _rightTree = rTree;
   }

   /**
   * Instead of checking the subtrees for emptiness, hands the right subtree to the
   * left subtree and asks it to help the owner insert the data.
   * @param n != null.
   * @param owner the owner of this Node2.
   */
   final void insert (Integer n, Tree234 owner)
	{
      if ( n.intValue () == _data.intValue ())
         return;
      _leftTree.helpParentInsert (owner, _rightTree, n);
	}

	/**
   * Helps the owner's parent tree insert data, using the other two owner's siblings if necessary.
   * This is a Node2.  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 two 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 Node2
   */
   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 Node2.  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 Node2
    */
	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 Node2.  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 Node2
   */
	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 Node3.
   * @param n an Integer to be properly inserted into owner.
   * @param owner the owner of this Node2
   */
	final void insertAsLeaf (Integer n, Tree234 owner)
	{
//// STUDENT TO WRITE CODE.
	}

   /**
   * Inserts data into the owner when this Node2 is NOT a leaf node.
   * If the input Integer is less than the root data,
   * ask the left subtree to insert data as a child of the owner
   * else ask the right subtree to insert as a child of the owner.
   * @param n != root data
   * @param owner the owner of this Node2
   */
	void insertNotAsLeaf (Integer n, Tree234 owner)
	{
      if (n.intValue () < _data.intValue ())
        _leftTree.insertAsChild (owner, n);
	    else // n.intValue () > _data.intValue ()
        _rightTree.insertAsChild (owner, n);
	}

  /**
   * Inserts n into the owner tree.
   * The owner of this Node2 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 Node2
   */
   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 Node2, must be the parent of a Tree234.
   */
  final void attach (Tree234 lTree, Integer n, Tree234 rTree, Tree234 owner)
  {
    Node3 topNode;
    if (n.intValue () < _data.intValue ())
      topNode = new Node3 (lTree, n, rTree, _data, _rightTree);
    else
      topNode = new Node3 (_leftTree, _data, lTree, n, rTree);
    owner.changeRoot (topNode);
  }
}