BST.java revision 7c478bd95313f5f23a4c958a745db2134aa03244
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License, Version 1.0 only
* (the "License"). You may not use this file except in compliance
* with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* or http://www.opensolaris.org/os/licensing.
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
*
* ident "%Z%%M% %I% %E% 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");
}
}
}