package t234;

/**
* 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.
* @since 11/13/01
* @author Dung X. Nguyen, Copyright 2001 - All Rights Reserved.
*/
class Node3 extends ANode234 {
    private Tree234 _leftTree  = new Tree234 (); // Invariant:  _leftTree  != null
    private Integer _leftDat;	                 // Invariant:  _leftDat   != null
    private Tree234 _midTree  = new Tree234 ();  // Invariant:  _midTree   != null
    private Integer _rightDat;	                 // Invariant:  _rightDat  != null
    private Tree234 _rightTree  = new Tree234 ();// Invariant:  _rightTree != null
                                                 // 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 whose elements are less than lN.
    * @param lN != null  less than all elements in mTree.
    * @param mTree != null the middle subtree whose elements 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;
    }

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

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

    final void insertHelper (Tree234 ownerPo, Tree234 owner, Integer n) {
        owner.insert(n); // can call insert (owner, n) instead.
    }

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

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