/*
6/26/97   DXN

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

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

*/

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

  Node3(Integer n0, Integer n1)
  //Pre: n0 and n1 are not null and are distinct.
  //A more sophiticated approach is to throw an exception when Pre is violated.
  //Post:
  //
  {
	if (n0.intValue () < n1.intValue ())
	{
	  _leftDat   = n0;
	  _rightDat  = n1;
	}
	else
	{
	  _leftDat   = n1;
	  _rightDat  = n0;
	}
	_leftTree  = new Tree234 ();
	_midTree   = new Tree234 ();
	_rightTree = new Tree234 ();
	//Data invariants are maintained.
  }

  Node3(Tree234 lTree, Integer lN, Tree234 mTree, Integer rN, Tree234 rTree)
  {
    _leftTree  = lTree;
    _leftDat  = lN;
    _midTree   = mTree;
    _rightDat = rN;
    _rightTree = rTree;
  }

  final boolean isEmpty ()
  {
	  return false;
  }

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

  final void insert (Tree234 parent, Integer n)
  {
  	int leftVal  = _leftDat.intValue ();
  	int rightVal = _rightDat.intValue ();
  	int key = n.intValue ();
  	if ((key == leftVal) || (key == rightVal))
  	  return;
    if (isLeafNode())
    {
  	   parent.changeRoot (new Node4 (_leftDat, _rightDat, n));
    }
    else
    {//parent is parent of left, center, and right subtrees.
      if (key < leftVal)
        _leftTree.insertHelper (parent, n);
      else if (rightVal < key)
        _rightTree.insertHelper (parent, n);
      else
        _midTree.insertHelper (parent, n);
    }
  }

  final void insertHelper (Tree234 grandPo, Tree234 parent, Integer n)
  {
    insert (parent, n);
  }

  final void attach (Tree234 parent, Tree234 lTree, Integer n, Tree234 rTree)
  {
    int key = n.intValue ();
    Node4 topNode;
    if (key < _leftDat.intValue ())
      topNode = new Node4 (lTree, n, rTree, _leftDat, _midTree, _rightDat, _rightTree);
    else if (_rightDat.intValue () < key)
      topNode = new Node4 (_leftTree, _leftDat, _midTree, _rightDat, lTree, n, rTree);
    else  //  _leftDat < n < _rightDat
      topNode = new Node4 (_leftTree, _leftDat, lTree, n, rTree, _rightDat, _rightTree);
    parent.changeRoot (topNode);
  }

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