1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 /*
22  *
23  * ident	"%Z%%M%	%I%	%E% SMI"
24  *
25  * Copyright (c) 1999 by Sun Microsystems, Inc.
26  * All rights reserved.
27  *
28  * BST.java
29  * Simple binary search tree implementation for help articles
30  *
31  */
32 
33 package com.sun.admin.pm.client;
34 
35 import java.lang.*;
36 import java.util.*;
37 import com.sun.admin.pm.server.*;
38 
39 
40 public class BST extends Object {
41 
42     // these should be protected...
43     public BST left = null;
44     public BST right = null;
45     public BST parent = null;
46     public BSTItem data;
47 
48     static public int comparisons;
49 
BST(BSTItem theItem)50     public BST(BSTItem theItem) {
51         // Debug.info("HELP: New BST(" + theItem + ")");
52 
53         left = right = null;
54         data = theItem;
55     }
56 
57 
BST()58     public BST() {
59         this(new BSTItem("", null));
60     }
61 
insert(String key, Object data)62     public BST insert(String key, Object data) {
63         return insert(new BSTItem(key,  data));
64     }
65 
66 
67     // normal bst insertion
insert(BSTItem theItem)68     public BST insert(BSTItem theItem) {
69 
70         int comp = data.compare(theItem);
71         BST node = null;
72 
73         if (comp == 0) {
74             Debug.info("HELP: Duplicate insert: " +
75                         theItem.toString());
76         } else if (comp > 0) {
77             if (left != null)
78                 left.insert(theItem);
79             else
80                 left = node = new BST(theItem);
81         } else if (comp < 0) {
82             if (right != null)
83                 right.insert(theItem);
84             else
85                 right = node = new BST(theItem);
86         }
87 
88         return node;
89     }
90 
91 
find_tree(String newKey)92     public BST find_tree(String newKey) {
93         return find_tree(newKey, true);
94     }
95 
find(String newKey)96     public BSTItem find(String newKey) {
97         return find(newKey, true);
98     }
99 
100 
find_tree(String newKey, boolean exactMatch)101     public BST find_tree(String newKey, boolean exactMatch) {
102         /*
103          * Debug.info("HELP: Finding " +(exactMatch ? "exact " : "partial ") +
104          * newKey);
105          */
106 
107         BST rv = null;
108         int comp = data.compare(newKey, exactMatch);
109 
110         ++comparisons;
111 
112         if (comp > 0) {
113             if (left != null)
114                 rv = left.find_tree(newKey, exactMatch);
115         } else if (comp < 0) {
116             if (right != null)
117                 rv = right.find_tree(newKey, exactMatch);
118         } else {
119             rv = this;
120             // Debug.info("HELP: Found " + newKey + " in " + data);
121         }
122 
123         return rv;
124     }
125 
find(String newKey, boolean exactMatch)126     public BSTItem find(String newKey, boolean exactMatch) {
127         Debug.info("HELP: Finding " +(exactMatch ? "exact " : "partial ") +
128                     newKey);
129 
130         BSTItem rv = null;
131         int comp = data.compare(newKey, exactMatch);
132 
133         ++comparisons;
134 
135         if (comp > 0) {
136             if (left != null)
137                 rv = left.find(newKey, exactMatch);
138         } else if (comp < 0) {
139             if (right != null)
140                 rv = right.find(newKey, exactMatch);
141         } else {
142             Debug.info("HELP: Found " + newKey + " in " + data);
143             rv = this.data;
144         }
145 
146         return rv;
147     }
148 
149 
150 
traverse()151     public void traverse() {
152         if (left != null)
153             left.traverse();
154         Debug.info("HELP: Traverse: " + data);
155         if (right != null)
156             right.traverse();
157     }
158 
traverse_right()159     public void traverse_right() {
160         Debug.info("HELP: Traverse: " + data);
161         if (right != null)
162             right.traverse();
163     }
164 
165 
traverse_find(String key)166     public void traverse_find(String key) {
167         if (left != null)
168             left.traverse_find(key);
169         if (data.compare(key, false) < 0)
170             return;
171         Debug.info("HELP: Traverse_find: " + data.key);
172         if (right != null)
173             right.traverse_find(key);
174     }
175 
176     // empty search string is a wildcard...
traverse_find_vector(Vector v, String key)177     public void traverse_find_vector(Vector v, String key) {
178         /*
179          * Debug.info("HELP: traverse_find_vector: node " +
180          * data.key + "[" +(left!=null?left.data.key:"null") + "]" +
181          * "[" +(right!=null ?right.data.key:"null") + "]" +
182          * " seeking " + key);
183          */
184         int c = 0;
185 
186         if (key.length() > 0)
187             c = data.compare(key, false);
188 
189         /*
190          * Debug.info("HELP: traverse_find_vector: compare " +
191          * data.key + " to "+ key + " = " + c);
192          */
193 
194         if (c >= 0 && left != null)
195             left.traverse_find_vector(v, key);
196 
197         if (c == 0) {
198             // Debug.info("HELP: traverse_find_vector: adding " + data.key);
199             v.addElement(data.data);
200         }
201 
202         if (c <= 0) {
203             if (right != null)
204                 right.traverse_find_vector(v, key);
205         }
206     }
207 
208 
dump()209     public void dump() {
210         Debug.info("HELP: \nDump: this = " + data.key);
211 
212         if (left != null)
213             Debug.info("HELP: Dump: left = " + left.data.key);
214         else
215             Debug.info("HELP: Dump: left = null");
216 
217 
218         if (right != null)
219             Debug.info("HELP: Dump: right = " + right.data.key);
220         else
221             Debug.info("HELP: Dump: right = null");
222 
223         if (left != null)
224             left.dump();
225         if (right != null)
226             right.dump();
227 
228     }
229 
main(String args[])230     public static void main(String args[]) {
231         BSTItem root = new BSTItem("Root");
232         BSTItem a = new BSTItem("Alpha");
233         BSTItem b = new BSTItem("Bravo");
234         BSTItem c = new BSTItem("Charlie");
235         BSTItem d = new BSTItem("Delta");
236         BSTItem e = new BSTItem("Echo");
237         BSTItem x = new BSTItem("Xray");
238         BSTItem aa = new BSTItem("aspect");
239         BSTItem ab = new BSTItem("assess");
240         BSTItem ad = new BSTItem("assist");
241         BSTItem ae = new BSTItem("asphalt");
242         BSTItem af = new BSTItem("asap");
243         BSTItem ag = new BSTItem("adroit");
244         BSTItem ah = new BSTItem("adept");
245         BSTItem ai = new BSTItem("asdf");
246 
247         BST bst = new BST(root);
248 
249         BST.comparisons = 0;
250         bst.insert(a);
251         System.out.println(BST.comparisons +
252                             " comparisons\n");
253         BST.comparisons = 0;
254         bst.insert(x);
255         System.out.println(BST.comparisons +
256                             " comparisons\n");
257         BST.comparisons = 0;
258         bst.insert(e);
259         System.out.println(BST.comparisons +
260                             " comparisons\n");
261         BST.comparisons = 0;
262         bst.insert(c);
263         System.out.println(BST.comparisons +
264                             " comparisons\n");
265         BST.comparisons = 0;
266         bst.insert(b);
267         System.out.println(BST.comparisons +
268                             " comparisons\n");
269         BST.comparisons = 0;
270         bst.insert(d);
271         System.out.println(BST.comparisons +
272                             " comparisons\n");
273 
274         bst.insert(aa);
275         bst.insert(ab);
276         bst.insert(ad);
277         bst.insert(ae);
278         bst.insert(af);
279         bst.insert(ag);
280         bst.insert(ah);
281         bst.insert(ai);
282 
283         bst.traverse();
284 
285         BST.comparisons = 0;
286         bst.find("Echo");
287         System.out.println(BST.comparisons +
288                             " comparisons\n");
289         BST.comparisons = 0;
290         bst.find("Xray");
291         System.out.println(BST.comparisons +
292                             " comparisons\n");
293         BST.comparisons = 0;
294         bst.find("Delta");
295         System.out.println(BST.comparisons +
296                             " comparisons\n");
297         BST.comparisons = 0;
298         bst.find("Root");
299         System.out.println(BST.comparisons +
300                             " comparisons\n");
301         bst.find("Alpha");
302 
303         bst.dump();
304         if (bst.left != null)
305             bst.left.dump();
306         if (bst.right != null)
307             bst.right.dump();
308 
309         {
310             Debug.info("HELP: Looking for a");
311             BST result = bst.find_tree("a", false);
312             result.traverse_find("a");
313 
314             Debug.info("HELP: Looking for as");
315             result = result.find_tree("as", false);
316             result.traverse_find("as");
317 
318             Debug.info("HELP: Looking for ass");
319             result = result.find_tree("ass", false);
320             result.traverse_find("ass");
321 
322             Debug.info("HELP: Looking for ad");
323             result = bst.find_tree("ad", false);
324             result.traverse_find("ad");
325         }
326     }
327 }
328