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