/*
 *
 * ident	"@(#)BST.java	1.4	99/03/29 SMI"
 *
 * Copyright (c) 1999 by Sun Microsystems, Inc.
 * All rights reserved.
 * 
 * BST.java
 * Simple binary search tree implementation for help articles
 *
 */

package com.sun.admin.pm.client;

import java.lang.*;
import java.util.*;
import com.sun.admin.pm.server.*;


public class BST extends Object {
    
    // these should be protected...
    public BST left = null;
    public BST right = null;
    public BST parent = null;
    public BSTItem data;

    static public int comparisons;

    public BST(BSTItem theItem) {
        // Debug.info("HELP: New BST(" + theItem + ")");

        left = right = null;
        data = theItem;
    }
    

    public BST() {
        this(new BSTItem("", null));
    }

    public BST insert(String key, Object data) {
        return insert(new BSTItem(key,  data));
    }


    // normal bst insertion
    public BST insert(BSTItem theItem) {

        int comp = data.compare(theItem);
        BST node = null;

        if (comp == 0) {
            Debug.info("HELP: Duplicate insert: " + 
                        theItem.toString());
        } else if (comp > 0) {
            if (left != null)
                left.insert(theItem);
            else
                left = node = new BST(theItem);
        } else if (comp < 0) {
            if (right != null)
                right.insert(theItem);
            else
                right = node = new BST(theItem);
        } 

        return node;
    }

    
    public BST find_tree(String newKey) {
        return find_tree(newKey, true);
    }

    public BSTItem find(String newKey) {
        return find(newKey, true);
    }


    public BST find_tree(String newKey, boolean exactMatch) {
        /*
          Debug.info("HELP: Finding " +(exactMatch ? "exact " : "partial ") +
          newKey);
        */

        BST rv = null;
        int comp = data.compare(newKey, exactMatch);
      
        ++comparisons;

        if (comp > 0) {
            if (left != null)
                rv = left.find_tree(newKey, exactMatch);
        } else if (comp < 0) {
            if (right != null)
                rv = right.find_tree(newKey, exactMatch);
        } else {
            rv = this;
            // Debug.info("HELP: Found " + newKey + " in " + data);
        } 

        return rv;
    }

    public BSTItem find(String newKey, boolean exactMatch) {
        Debug.info("HELP: Finding " +(exactMatch ? "exact " : "partial ") +
                    newKey);

        BSTItem rv = null;
        int comp = data.compare(newKey, exactMatch);
      
        ++comparisons;

        if (comp > 0) {
            if (left != null)
                rv = left.find(newKey, exactMatch);
        } else if (comp < 0) {
            if (right != null)
                rv = right.find(newKey, exactMatch);
        } else {
            Debug.info("HELP: Found " + newKey + " in " + data);
            rv = this.data;
        } 

        return rv;
    }

    

    public void traverse() {
        if (left != null)
            left.traverse();
        Debug.info("HELP: Traverse: " + data);
        if (right != null)
            right.traverse();
    }

    public void traverse_right() {
        Debug.info("HELP: Traverse: " + data);
        if (right != null)
            right.traverse();
    }

 
    public void traverse_find(String key) {
        if (left != null)
            left.traverse_find(key);
        if (data.compare(key, false) < 0)
            return;
        Debug.info("HELP: Traverse_find: " + data.key);
        if (right != null)
            right.traverse_find(key);
    }

    // empty search string is a wildcard...
    public void traverse_find_vector(Vector v, String key) {
        /*
         * Debug.info("HELP: traverse_find_vector: node " + 
         * data.key + "[" +(left!=null?left.data.key:"null") + "]" +
         * "[" +(right!=null ?right.data.key:"null") + "]" +
         * " seeking " + key);
         */
        int c = 0;

        if (key.length() > 0)
            c = data.compare(key, false);
      
        /*
         * Debug.info("HELP: traverse_find_vector: compare " + 
         * data.key + " to "+ key + " = " + c);
         */
			
        if (c >= 0 && left != null)
            left.traverse_find_vector(v, key);

        if (c == 0) {
            // Debug.info("HELP: traverse_find_vector: adding " + data.key);
            v.addElement(data.data);
        }
      
        if (c <= 0) {
            if (right != null)
                right.traverse_find_vector(v, key);
        }
    }

    
    public void dump() {
        Debug.info("HELP: \nDump: this = " + data.key);

        if (left != null)
            Debug.info("HELP: Dump: left = " + left.data.key);
        else
            Debug.info("HELP: Dump: left = null");


        if (right != null)
            Debug.info("HELP: Dump: right = " + right.data.key);
        else
            Debug.info("HELP: Dump: right = null");

        if (left != null)
            left.dump();
        if (right != null)
            right.dump();

    }

    public static void main(String args[]) {
        BSTItem root = new BSTItem("Root");
        BSTItem a = new BSTItem("Alpha");
        BSTItem b = new BSTItem("Bravo");
        BSTItem c = new BSTItem("Charlie");
        BSTItem d = new BSTItem("Delta");
        BSTItem e = new BSTItem("Echo");
        BSTItem x = new BSTItem("Xray");
        BSTItem aa = new BSTItem("aspect");
        BSTItem ab = new BSTItem("assess");
        BSTItem ad = new BSTItem("assist");
        BSTItem ae = new BSTItem("asphalt");
        BSTItem af = new BSTItem("asap");
        BSTItem ag = new BSTItem("adroit");
        BSTItem ah = new BSTItem("adept");
        BSTItem ai = new BSTItem("asdf");

        BST bst = new BST(root);

        BST.comparisons = 0;
        bst.insert(a);
        System.out.println(BST.comparisons + 
                            " comparisons\n");
        BST.comparisons = 0;
        bst.insert(x);
        System.out.println(BST.comparisons + 
                            " comparisons\n");
        BST.comparisons = 0;
        bst.insert(e);
        System.out.println(BST.comparisons + 
                            " comparisons\n");
        BST.comparisons = 0;
        bst.insert(c);
        System.out.println(BST.comparisons + 
                            " comparisons\n");
        BST.comparisons = 0;
        bst.insert(b);
        System.out.println(BST.comparisons + 
                            " comparisons\n");
        BST.comparisons = 0;
        bst.insert(d);
        System.out.println(BST.comparisons + 
                            " comparisons\n");

        bst.insert(aa);
        bst.insert(ab);
        bst.insert(ad);
        bst.insert(ae);
        bst.insert(af);
        bst.insert(ag);
        bst.insert(ah);
        bst.insert(ai);

        bst.traverse();

        BST.comparisons = 0;
        bst.find("Echo");
        System.out.println(BST.comparisons + 
                            " comparisons\n");
        BST.comparisons = 0;
        bst.find("Xray");
        System.out.println(BST.comparisons + 
                            " comparisons\n");
        BST.comparisons = 0;
        bst.find("Delta");
        System.out.println(BST.comparisons + 
                            " comparisons\n");
        BST.comparisons = 0;
        bst.find("Root");
        System.out.println(BST.comparisons + 
                            " comparisons\n");
        bst.find("Alpha");

        bst.dump();
        if (bst.left != null)
            bst.left.dump();
        if (bst.right != null)
            bst.right.dump();

        {
            Debug.info("HELP: Looking for a");
            BST result = bst.find_tree("a", false);
            result.traverse_find("a");

            Debug.info("HELP: Looking for as");
            result = result.find_tree("as", false);
            result.traverse_find("as");

            Debug.info("HELP: Looking for ass");
            result = result.find_tree("ass", false);
            result.traverse_find("ass");

            Debug.info("HELP: Looking for ad");
            result = bst.find_tree("ad", false);
            result.traverse_find("ad");
        }
    }
}


    




