/*
6/26/97   DXN

This file contains the code for class Node4 which 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.

Copyright 1997,  Dung X. Nguyen - All Rights Reserved.

*/

class Node4 extends ANode234
{
  /** @SBGen Variable (,,,64)   */
	private Tree234 _leftTree;      //Data invariant:  _leftTree     != null
  private Integer _leftDat;	      /**
	 * Data invariant:  _leftDat      != null
	 * @SBGen Variable (,,,64)
	 */
	private Tree234 _leftMidTree;   //Data invariant:  _leftMidTree  != null
  private Integer _midDat;	      /**
	 * Data invariant:  _midDat       != null
	 * @SBGen Variable (,,,64)
	 */
	private Tree234 _rightMidTree;  //Data invariant:  _rightMidTree != null
  private Integer _rightDat;	    /**
	 * Data invariant:  _rightDat     != null
	 * @SBGen Variable (,,,64)
	 */
	private Tree234 _rightTree;     //Data invariant:  _rightTree    != null
                         //Data invariant:  _leftDat < _midDat < _rightDat.

  Node4(Integer lo, Integer hi, Integer n)
  //Pre: lo, hi, n are not null and distinct.
  //     lo < hi.
  //Post:
  //
  //Called by: Node3.insert (Tree234, Integer).
  {
  	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;
  	}
  	_leftTree     = new Tree234 ();
  	_leftMidTree  = new Tree234 ();
  	_rightMidTree = new Tree234 ();
  	_rightTree    = new Tree234 ();
  	//Data invariants are maintained.
  }

  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;
  }

  final boolean isEmpty ()
  {
	  return false;
  }

  final void drawRootAndSubtrees (int level)
  {
  	System.out.println (_leftDat + "  " + _midDat + "  " + _rightDat);
  	_leftTree.drawAtLevel (level + 1);
  	System.out.println ();
  	_leftMidTree.drawAtLevel (level + 1);
  	System.out.println ();
  	_rightMidTree.drawAtLevel (level + 1);
  	System.out.println ();
  	_rightTree.drawAtLevel (level + 1);
  }

  final void insert (Tree234 parent, Integer n)
  //called when there is no grandparent tree, i.e. this is the top level root. 
  {
  	int key = n.intValue ();
      if (key == _leftDat.intValue () ||
          key == _midDat.intValue ()  || key == _rightDat.intValue ())
        return;
  	Tree234 leftTree  = new Tree234 (_leftTree, _leftDat, _leftMidTree);
  	Tree234 rightTree = new Tree234 (_rightMidTree, _rightDat, _rightTree);
  	parent.changeRoot (new Node2 (leftTree, _midDat, rightTree));
  	parent.insert (n);
  }

  final void insertHelper (Tree234 grandPo, Tree234 parent, Integer n)
  // called when there is a grandparent tree.
  {
  	   int key = n.intValue ();
  	   int midVal = _midDat.intValue ();
      if (key == _leftDat.intValue () || key == midVal || key == _rightDat.intValue ())
         return;
  	   Tree234 leftTree  = new Tree234 (_leftTree, _leftDat, _leftMidTree);
  	   Tree234 rightTree = new Tree234 (_rightMidTree, _rightDat, _rightTree);
      grandPo.attach (leftTree, _midDat, rightTree);
      if (key < midVal)
        leftTree.insert (n);
      else
        rightTree.insert (n);
  }

  final void attach (Tree234 parent, Tree234 lTree, Integer n, Tree234 rTree)
  {
    throw new IllegalStateException ("should never be called.");
  }

  private final boolean isLeafNode ()
  {
    return (_leftTree.isEmpty ()     && _leftMidTree.isEmpty () &&
            _rightMidTree.isEmpty () && _rightTree.isEmpty ());
  }
}