/*
 * BinarySearchTree.java - Binary Search Tree
 *
 * Written 9/20/96 by Chuck McManis
 * Implemented from the description in "Introduction to Algorithms"
 * by Cormen, Leiserson, and Rivest. MIT Press, ISBN 0-07-013143-0
 */

import java.io.PrintStream;
import java.util.Enumeration;
import java.util.Dictionary;

/**
 * This is Variation 3 of the Binary Search Tree class.
 *
 * In this final variation, the put and get methods from Dictionary
 * take objects, however those objects are manipulated by a mixin of
 * type "ContainerOrganizer" this mixin assures us that the container
 * is properly used during its lifetime.
 */
public class BinarySearchTree extends Dictionary {
    BSTNode rootNode;
    private int elementCount;
    private ContainerOrganizer co;

    public BinarySearchTree(ContainerOrganizer c) {
        super();
        co = c;
        co.setDict(this);
    }

    /**
     * Print from the root node.
     */
    public void print(PrintStream p) {
        if (rootNode != null)
            rootNode.print(p);
    }


    public Enumeration elements() {
        return new BSTEnumerator(rootNode, false);
    }

    public Enumeration keys() {
        return new BSTEnumerator(rootNode, true);
    }


    public boolean isEmpty() {
        return (elementCount == 0);
    }

    public int size() {
        return elementCount;
    }

    public Object get(Object skey) {
        Object s = co.keyForObject(skey);
        BSTNode n = search(rootNode, s);

        return (n == null) ? null : n.payload;
    }

    public Object put(Object key, Object value) {
        BSTNode n;
        Object s;

        co.verifyType(value);
        s = co.keyForObject(key);
        n = search(s);
        Object r = null;

        if (n != null) {
            r = n.payload;
            remove(s);
        }
        n = new BSTNode(s, value);
        insert(n);
        return r;
    }

    public Object remove(Object skey) {
        BSTNode n;

        Object s = co.keyForObject(skey);
        n = search(s);
        if (n == null)
            return null;
        Object r = n.payload;
        delete(n);
        return r;
    }

    /* **** PRIVATE METHODS IN BinarySearchTree ***** */

    /**
     * This method searches the tree for the first node
     * with a key equal to key.
     * 0: It uses Object.equals() to identify matching keys.
     */
    private BSTNode search(BSTNode n, Object searchKey) {
        if ((n == null) || co.equalKeys(searchKey, n.key)) {
            return n;
        }
        if (co.compareKeys(searchKey, n.key) < 0) {
            return search(n.left, searchKey);
        } else {
            return search(n.right, searchKey);
        }
    }

    /**
     * This is a short cut for starting at the root node.
     */
    private BSTNode search(Object skey) {
        return search(rootNode, skey);
    }

    /**
     * Insert a new node into the tree.
     */
    private void insert(BSTNode n) {
        BSTNode y = null;
        BSTNode x = rootNode;

        while (x != null) {
            y = x;
            if (co.compareKeys(n.key, x.key) < 0) {
                x = y.left;
            } else {
                x = y.right;
            }
        }
        n.parent = y;
        if (y == null) {
            rootNode = n;
        } else if (co.compareKeys(n.key, y.key) < 0) {
            y.left = n;
        } else {
            y.right = n;
        }
        elementCount++;
    }

    /**
     * Delete a node from the tree.
     */
    private BSTNode delete(BSTNode z) {
        BSTNode x, y;

        if ((z.left == null) || (z.right == null)) {
            y = z;
        } else {
            y = z.successor();
        }

        if (y.left != null) {
            x = y.left;
        } else {
            x = y.right;
        }
        if (x != null) {
            x.parent = y.parent;
        }
        if (y.parent == null) {
            rootNode = x;
        } else {
            if (y == y.parent.left) {
                y.parent.left = x;
            } else {
                y.parent.right = x;
            }
        }
        if (y != z) {
            z.key = y.key;
            z.payload = y.payload;
        }
        elementCount--;
        return y;
    }
}