package t234;

/**
* 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.
* @since 11/13/01
* @author Dung X. Nguyen, Copyright 2001 - All Rights Reserved.
*/
class Node4 extends ANode234 {
    private Tree234 _leftTree  = new Tree234 ();      // Invariant:  _leftTree     != null
    private Integer _leftDat;	                      // Invariant:  _leftDat      != null
    private Tree234 _leftMidTree  = new Tree234 ();   // Invariant:  _leftMidTree  != null
    private Integer _midDat;	                      // Invariant:  _midDat       != null
    private Tree234 _rightMidTree  = new Tree234 ();  // Invariant:  _rightMidTree != null
    private Integer _rightDat;	                      // Invariant:  _rightDat     != null
    private Tree234 _rightTree  = new Tree234 ();     // Invariant:  _rightTree    != null
                                                 // 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 whose elements < lN.
    * @param lN < mN, to be stored as the leftmost data, < all elements in lmTree
    * @param lmTree != null, the new middle-left subtree whose elements lmTree < mN
    * @param mN < rN, to be stored as the middle data, < all elements in rmTree
    * @param rmTree != null, the new middle-right subtree whose elements < 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;
    }

    final boolean isEmpty(Tree234 owner) {
        return false;
    }

    /**
    * Called when there is no parent tree, i.e. this is the top level root:
    * Splits the node then inserts the data.
    */
    final void insert(Tree234 owner, Integer n) {
        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);
        owner.changeRoot (new Node2(leftTree, _midDat, rightTree));
        owner.insert (n);
    }

    /**
     * Called when there is a parent tree.
     */
    final void insertHelper(Tree234 ownerPo, Tree234 owner, Integer n) {
        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);
        ownerPo.attach (leftTree, _midDat, rightTree);
        if (key < midVal) {
            leftTree.insert(n);
        } else {
            rightTree.insert(n);
        }
    }

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

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