/*
 * 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.
 */

class BSTNode {
    protected BSTNode     parent;
    protected BSTNode     left;
    protected BSTNode     right;
    protected Object    key;
    protected Object    payload;

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

    protected BSTNode() {
        super();
    }

    /** Return successor node to this one. */
    public BSTNode successor() {
        BSTNode n = this;
        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;
    }

    /** Return the predecessor node to this one */
    public BSTNode predecessor() {
        BSTNode n = this;
        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;
    }

    /** Return the minimum key in the tree relative to this one. */
    public BSTNode min() {
        BSTNode n = this;
        while (n.left != null) {
            n = n.left;
        }
        return n;
    }

    /** Return the maximum key in the tree relative to this one */
    public BSTNode max() {
        BSTNode n = this;
        while (n.right != null) {
            n = n.right;
        }
        return n;
    }

    /** Do an in-order walk from this node */
    public void print(PrintStream p) {
        BSTNode n = this;
        if (n.left != null)
            n.left.print(p);

        p.println(n.payload);

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

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