/*
 * BSTNode.java - Base Node class for Binary Search Trees
 *
 * Copyright (c) 1996 Chuck McManis, All Rights Reserved.
 *
 * Permission to use, copy, modify, and distribute this software
 * and its documentation for NON-COMMERCIAL purposes and without
 * fee is hereby granted provided that this copyright notice
 * appears in all copies.
 *
 * CHUCK MCMANIS MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE
 * SUITABILITY OF THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING
 * BUT NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, OR NON-INFRINGEMENT. CHUCK MCMANIS
 * SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT
 * OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
 */

import java.io.PrintStream;

/**
 * This class is the base node type for a Binary Search Tree. It holds
 * a key and a payload object (the containees) and has some housekeeping
 * pointers for maintaining a binary search tree.
 *
 * In this version the indexing object is held in key and it is a SearchKey
 * object.
 */
class BSTNode {
    protected BSTNode parent;
    protected BSTNode left;
    protected BSTNode right;
    protected SearchKey  key;
    protected Object  payload;

    public BSTNode(SearchKey k, Object p) {
        key = k;
        payload = p;
    }

    protected BSTNode() {
        super();
    }

    /** Return successor node to this one. */
    public BSTNode successor() { return successor(this); }

    /** Return the predecessor node to this one */
    public BSTNode predecessor() { return predecessor(this); }

    /** Return the minimum key in the tree relative to this one. */
    public BSTNode min() { return min(this); }

    /** Return the maximum key in the tree relative to this one */
    public BSTNode max() { return max(this); }

    /** Do an in-order walk from this node */
    public void print(PrintStream p) { print(this, p); }

    /*
     * Private implementation of the base node functions. These are all
     * static to keep the size of the node object to a minimum.
     */
    /**
     * This method does an inorder tree walk and prints
     * out the results to the passed in printstream.
     */
    private static  void print(BSTNode n, PrintStream p) {
        if (n.left != null)
            n.left.print(p);

        p.println(n.payload);

        if (n.right != null)
            n.right.print(p);
    }

    private static BSTNode successor(BSTNode n) {
        if (n.right != null) {
            return n.right.min();
        }
        BSTNode y = n.parent;
        while (( y != null) && (n == y.right)) {
            n = y;
            y = y.parent;
        }
        return y;
    }

    private static BSTNode predecessor(BSTNode n) {
        if (n.left != null) {
            return n.left.max();
        }
        BSTNode y = n.parent;
        while (( y != null) && (n == y.left)) {
            n = y;
            y = y.parent;
        }
        return y;
    }

    private static BSTNode min(BSTNode n) {
        while (n.left != null) {
            n = n.left;
        }
        return n;
    }

    private static BSTNode max(BSTNode n) {
        while (n.right != null) {
            n = n.right;
        }
        return n;
    }

}