001: /*
002: * CONFIDENTIAL AND PROPRIETARY SOURCE CODE OF
003: * NETSCAPE COMMUNICATIONS CORPORATION
004: *
005: * Copyright (c) 1996 Netscape Communications Corporation.
006: * All Rights Reserved.
007: * Use of this Source Code is subject to the terms of the applicable
008: * license agreement from Netscape Communications Corporation.
009: */
010:
011: package util;
012:
013: /**
014: A binary tree node.
015: <p>
016: <i>Structure.</i>
017: BTreeNodes and the BinaryTree enumeration are designed to
018: allow for binary trees to be treated as though they
019: had left-right children or next-child children.
020: Relevant methods for each are visible;
021: internally,
022: left is treated as being equivalent to next and
023: right is treated as being equivalent to child.
024: <p>
025: <i>Visibility.</i>
026: A CLOSED node is visible to enumeration but it's
027: children aren't.
028: A node that is OPEN is fully visible to BinaryTree enumeration
029: and the node's children are accessible,
030: though they themselves may not be visible.
031: LEFT/NEXT/RIGHT/CHILD implies the node itself is OPEN.
032: BTreeNodes have a sense of their visibility in enumeration.
033: If the node is LEFTVISIBLE or NEXTVISIBLE,
034: enumeration will attempt to traverse only it's
035: left or next child if they are visible.
036: If the node is RIGHTVISIBLE or CHILDVISIBLE,
037: enumeration will attempt to traverse only it's
038: right or child child if they are visible.
039: The default visibility is OPEN.
040: Visibility restrictions can be circumvented with the getAll methods.
041: <p>
042: <i>Terminal Policy.</i>
043: Terminal policy affects whether a node accepts expansion
044: and in what way it accepts expansion.
045: In other words, what kind of terminal it is.
046: The policy values are the same as the visibility values
047: and are used similarly.
048: The default terminal policy is OPEN, meaning that either
049: a right or left branch can be created.
050: LEFTVISIBLE and NEXTVISIBLE allow only left (next) branches to
051: be created.
052: RIGHTVISIBLE and CHILDVISIBLE allow only right (child) branches to
053: be created.
054: CLOSED means no branches can be created.
055: Currently, rejection based on terminal policy is silent.
056: <p>
057: <i>Depth.</i>
058: BTreeNodes maintain a sense of their "depth".
059: Both binary and unary depth are kept.
060: Binary depth is the depth a node is in a left-right tree,
061: unary depth is the depth a node is in a next-child tree,
062: the difference being that the next reference doesn't cause
063: depth to increment.
064: Depth 0 nodes are root nodes.
065: <p>
066: <i>Management.</i>
067: All alterations to the structure of a binary tree are expected
068: to take place through the Enumeration class.
069: While this class is public (compare with HashtableNode
070: in the JDK util.Hashtable class) enough to be viewed and referenced,
071: methods that alter the parent, left and right are restricted to the
072: BinaryTree enumeration class to ensure the integrity of the
073: enumeration.
074: <p>
075: <b>Open Issues</b>
076: <ul>
077: <li>Certain advanced operations (e.g., the deleting and inserting
078: operations required by QueryNode) will require methods
079: that are less or differently deterred by visibility.
080: <li>Need to support clone() (done) plus Enumeration/Dictionary
081: operations like: contains(), containsKey(), get() (done),
082: keys(). Some maybe in the Enumeration class.
083: <li>Need toString() and toStringList().
084: <li>Adding children should verify that the tree doesn't loop
085: back on itself, i.e. no inclusive descendant of a node being
086: added should point to an inclusive ancestor of the node it is
087: being added to. If access is restricted to the enumerator,
088: we can assume this is not necessary, assuming the creator
089: of the enumerator is not a pinhead.
090: <li>There are times when it would be useful for the BTreeNode
091: to point at it's BinaryTree. Dicey though; then
092: it'd need to be maintained and everything would
093: become just slightly more complicated. It would
094: all be managed w/in the util package though, so
095: consistency/correctness would be doable.
096: <li>getNodeByKey() and getNodeByValue() ignore the enumeration
097: order, are used by BinaryTree and return only the first
098: possible value.
099: Very, very bad.
100: </ul>
101: *
102: */
103:
104: public class BTreeNode implements Cloneable {
105: private BTreeNode parent;
106: private BTreeNode left; /* next */
107: private BTreeNode right; /* child */
108:
109: /**
110: * Key for the node
111: */
112: protected Object key;
113: /**
114: * Value for the node
115: */
116: protected Object value;
117:
118: public boolean display;
119:
120: private static final int VISIBILITY = 100;
121: /**
122: * See <i>Visibility</i> and <i>Terminal Policy</i> discussions above
123: */
124: public static final int CLOSED = VISIBILITY + 1;
125: /**
126: * See <i>Visibility</i> and <i>Terminal Policy</i> discussions above
127: */
128: public static final int LEFTVISIBLE = VISIBILITY + 2;
129: /**
130: * See <i>Visibility</i> and <i>Terminal Policy</i> discussions above
131: */
132: public static final int NEXTVISIBLE = LEFTVISIBLE;
133: /**
134: * See <i>Visibility</i> and <i>Terminal Policy</i> discussions above
135: */
136: public static final int RIGHTVISIBLE = VISIBILITY + 3;
137: /**
138: * See <i>Visibility</i> and <i>Terminal Policy</i> discussions above
139: */
140: public static final int CHILDVISIBLE = RIGHTVISIBLE;
141: /**
142: * See <i>Visibility</i> and <i>Terminal Policy</i> discussions above
143: */
144: public static final int OPEN = VISIBILITY + 4;
145:
146: private int visibility;
147: private int terminalPolicy;
148:
149: private int binaryDepth;
150: private int unaryDepth;
151:
152: /**
153: * Constructor.
154: */
155: public BTreeNode() {
156: this (null, null, OPEN);
157: }
158:
159: /**
160: * Constructor.
161: * @param key key
162: * @param value value
163: */
164: public BTreeNode(Object key, Object value) {
165: this (key, value, OPEN);
166: }
167:
168: /**
169: * Constructor.
170: * @param key key
171: * @param value value
172: * @param visibility visibility
173: */
174: public BTreeNode(Object key, Object value, int visibility) {
175: this .key = key;
176: this .value = value;
177:
178: setVisibility(visibility);
179: setTerminalPolicy(OPEN);
180:
181: display = true;
182:
183: binaryDepth = 0;
184: unaryDepth = 0;
185:
186: parent = null;
187: left = null;
188: right = null;
189: }
190:
191: protected Object clone() {
192: try {
193: BTreeNode btn = (BTreeNode) super .clone();
194:
195: if (left != null) {
196: btn.left = (BTreeNode) left.clone();
197: } else {
198: btn.left = null;
199: }
200:
201: if (right != null) {
202: btn.right = (BTreeNode) right.clone();
203: } else {
204: btn.right = null;
205: }
206:
207: return btn;
208: } catch (CloneNotSupportedException e) {
209: throw new InternalError();
210: }
211: }
212:
213: /**
214: * Set visibility.
215: * @param visibility visibility
216: * @exception IllegalArgumentException if not passed a legal visibility
217: */
218: public void setVisibility(int visibility)
219: throws IllegalArgumentException {
220: if ((visibility == LEFTVISIBLE) || (visibility == NEXTVISIBLE)
221: || (visibility == RIGHTVISIBLE)
222: || (visibility == CHILDVISIBLE) || (visibility == OPEN)
223: || (visibility == CLOSED)) {
224: this .visibility = visibility;
225: } else {
226: throw new IllegalArgumentException(
227: Messages.UNKNOWNVISIBILITY);
228: }
229: }
230:
231: /**
232: * Set terminal policy.
233: * @param terminalPolicy terminal policy
234: * @exception IllegalArgumentException if not passed a legal visibility
235: */
236: public void setTerminalPolicy(int terminalPolicy)
237: throws IllegalArgumentException {
238: if ((terminalPolicy == LEFTVISIBLE)
239: || (terminalPolicy == NEXTVISIBLE)
240: || (terminalPolicy == RIGHTVISIBLE)
241: || (terminalPolicy == CHILDVISIBLE)
242: || (terminalPolicy == OPEN)
243: || (terminalPolicy == CLOSED)) {
244: this .terminalPolicy = terminalPolicy;
245: } else {
246: throw new IllegalArgumentException(
247: Messages.UNKNOWNVISIBILITY);
248: }
249: }
250:
251: /**
252: * Get the current terminal policy.
253: */
254: public int getTerminalPolicy() {
255: return terminalPolicy;
256: }
257:
258: /*-----*/
259: /* set */
260: /*-----*/
261:
262: protected void setDepths() {
263: if (left != null) {
264: left.setDepths(unaryDepth, binaryDepth + 1);
265: }
266:
267: if (right != null) {
268: right.setDepths(unaryDepth + 1, binaryDepth + 1);
269: }
270: }
271:
272: protected void setDepths(int u, int b) {
273: /*
274: StringBuffer indent = new StringBuffer();
275: for ( int i = 0; i <= u; i++ ) { indent.append( "\t" ); }
276: System.out.println( "sd:" + indent.toString() + key );
277: */
278:
279: unaryDepth = u;
280: binaryDepth = b;
281:
282: if (left != null) {
283: left.setDepths(u, b + 1);
284: }
285: if (right != null) {
286: right.setDepths(u + 1, b + 1);
287: }
288: }
289:
290: /**
291: * Set the child (right) of this node to the passed node.
292: * @param node the new child
293: */
294: protected void setChild(BTreeNode node) {
295: setRight(node);
296: }
297:
298: /**
299: * Set the right (child) of this node to the passed node.
300: * @param node the new right
301: */
302: protected void setRight(BTreeNode node) {
303: if ((terminalPolicy != OPEN)
304: && (terminalPolicy != RIGHTVISIBLE)) {
305: return;
306: }
307:
308: right = node;
309: if (node != null) {
310: node.parent = this ;
311: right.setDepths(unaryDepth + 1, binaryDepth + 1);
312: }
313: }
314:
315: /**
316: * Set the next (left) of this node to the passed node.
317: * @param node the new next
318: */
319: protected void setNext(BTreeNode node) {
320: setLeft(node);
321: }
322:
323: /**
324: * Set the left (next) of this node to the passed node.
325: * @param node the new left
326: */
327: protected void setLeft(BTreeNode node) {
328: if ((terminalPolicy != OPEN) && (terminalPolicy != LEFTVISIBLE)) {
329: return;
330: }
331:
332: left = node;
333: if (node != null) {
334: node.parent = this ;
335: left.setDepths(unaryDepth, binaryDepth + 1);
336: }
337: }
338:
339: /**
340: * Detach the current node from it's parent and
341: * return it.
342: * leaveBehind indicates what is left
343: * behind for the parent.
344: * If leaveBehind is BinaryTree.LEFT, the left branch of
345: * current is attached to the parent.
346: * If leaveBehind is BinaryTree.RIGHT, the right branch of
347: * current is attached to the parent.
348: * If leaveBehind is BinaryTree.PARENT, the parent is
349: * left with a smouldering stub.
350: * @param leaveBehind LEFT, RIGHT or PARENT
351: */
352: public BTreeNode detachFromParent(int leaveBehind)
353: throws IllegalArgumentException {
354: if ((leaveBehind != BinaryTree.LEFT)
355: && (leaveBehind != BinaryTree.RIGHT)
356: && (leaveBehind != BinaryTree.PARENT)) {
357: throw new IllegalArgumentException();
358: }
359:
360: BTreeNode trans = null;
361:
362: if ((leaveBehind == BinaryTree.LEFT) && (left != null)) {
363: trans = left;
364: left = null;
365: } else if ((leaveBehind == BinaryTree.RIGHT) && (right != null)) {
366: trans = right;
367: right = null;
368: } else if (leaveBehind == BinaryTree.PARENT) {
369: trans = null;
370: }
371:
372: if (parent != null) {
373: if (parent.getLeft() == this ) {
374: parent.setLeft(trans);
375: } else if (parent.getRight() == this ) {
376: parent.setRight(trans);
377: }
378: }
379: parent = null;
380:
381: binaryDepth = 0;
382: unaryDepth = 0;
383:
384: setDepths();
385: return this ;
386: }
387:
388: /*-----*/
389: /* get */
390: /*-----*/
391:
392: /**
393: * Locate a node by checking values.
394: * Note that this method doesn't currently respect the
395: * tree's enumeration type or visibility, future releases will.
396: * Does a left (next) first search.
397: * Note that several BinaryTree methods use this method
398: * to conduct their searches, also violating the enumeration
399: * and visibility rules.
400: * @param o the target value
401: */
402: protected BTreeNode getNodeByValue(Object o) {
403: if (o == this .value) {
404: return this ;
405: }
406:
407: BTreeNode tmp;
408:
409: if (left != null) {
410: tmp = left.getNodeByValue(o);
411: if (tmp != null) {
412: return tmp;
413: }
414: }
415:
416: if (right != null) {
417: tmp = right.getNodeByValue(o);
418: if (tmp != null) {
419: return tmp;
420: }
421: }
422:
423: return null;
424: }
425:
426: /**
427: * Locate a node by checking keys.
428: * Note that this method doesn't currently respect the
429: * tree's enumeration type or visibility, future releases will.
430: * Does a left (next) first search.
431: * Note that several BinaryTree methods use this method
432: * to conduct their searches, also violating the enumeration
433: * and visibility rules.
434: * @param o the target key
435: */
436: protected BTreeNode getNodeByKey(Object o) {
437: if (o == this .key) {
438: return this ;
439: }
440:
441: BTreeNode tmp;
442:
443: if (left != null) {
444: tmp = left.getNodeByKey(o);
445: if (tmp != null) {
446: return tmp;
447: }
448: }
449:
450: if (right != null) {
451: tmp = right.getNodeByKey(o);
452: if (tmp != null) {
453: return tmp;
454: }
455: }
456:
457: return null;
458: }
459:
460: /**
461: * Return the value.
462: */
463: public Object getValue() {
464: return value;
465: }
466:
467: /**
468: * Return the key.
469: */
470: public Object getKey() {
471: return key;
472: }
473:
474: /**
475: * Return the visiblility.
476: */
477: public int getVisibility() {
478: return visibility;
479: }
480:
481: /**
482: * Return the node's binary (left/right) depth within the tree.
483: */
484: public int getBinaryDepth() {
485: return binaryDepth;
486: }
487:
488: /**
489: * Return the node's binary (next/child) depth within the tree.
490: */
491: public int getUnaryDepth() {
492: return unaryDepth;
493: }
494:
495: /**
496: * Get the parent. CAERFUL, parent is previous node, which may be
497: * a sibbling, this is not really a get parent method IMHO.
498: */
499: public BTreeNode getParent() {
500: return parent;
501: }
502:
503: /**
504: * Get the parent. This returns the REAL parent.
505: */
506: public BTreeNode getUnaryParent() {
507: BTreeNode p = null;
508:
509: for (p = parent; p != null; p = p.parent) {
510: if (p.unaryDepth < unaryDepth) {
511: break;
512: }
513: }
514:
515: return p;
516: }
517:
518: /**
519: * Get the child (right).
520: */
521: public BTreeNode getChild() {
522: return getRight(false);
523: }
524:
525: /**
526: * Get the child (right).
527: * @param all respect visibility or not
528: */
529: public BTreeNode getChild(boolean all) {
530: return getRight(all);
531: }
532:
533: /**
534: * Get the right (child).
535: */
536: public BTreeNode getRight() {
537: return getRight(false);
538: }
539:
540: /**
541: * Get the right (child).
542: * @param all respect visibility or not
543: */
544: public BTreeNode getRight(boolean all) {
545: if (all) {
546: return right;
547: }
548:
549: if ((right != null)
550: && ((visibility == RIGHTVISIBLE)
551: || (visibility == CHILDVISIBLE) || (visibility == OPEN))) {
552: return right;
553: }
554:
555: return null;
556: }
557:
558: /**
559: * Get the next (left).
560: */
561: public BTreeNode getNext() {
562: return getLeft(false);
563: }
564:
565: /**
566: * Get the next (left).
567: * @param all respect visibility or not
568: */
569: public BTreeNode getNext(boolean all) {
570: return getLeft(all);
571: }
572:
573: /**
574: * Get the left (next).
575: */
576: public BTreeNode getLeft() {
577: return getLeft(false);
578: }
579:
580: /**
581: * Get the left (next).
582: * @param all respect visibility or not
583: */
584: public BTreeNode getLeft(boolean all) {
585: if (all) {
586: return left;
587: }
588:
589: if ((left != null)
590: && ((visibility == LEFTVISIBLE)
591: || (visibility == NEXTVISIBLE) || (visibility == OPEN))) {
592: return left;
593: }
594:
595: return null;
596: }
597:
598: /**
599: * Return true if the caller has as an ancestor
600: * the passed node.
601: * If this node and the passed node match,
602: * the passed node is not considered an ancestor,
603: * so let's be careful out there.
604: * @param btn the proposed ancestor
605: */
606: public boolean hasAncestor(BTreeNode btn) {
607: for (BTreeNode i = this .getUnaryParent(); i != null; i = i
608: .getUnaryParent()) {
609: if (btn == i) {
610: return true;
611: }
612: }
613:
614: return false;
615: }
616:
617: /**
618: * Debugging aid.
619: */
620: public String toStringSummary() {
621: String p = (parent == null) ? "null" : (String) parent.key;
622: if (p == null) {
623: p = "null";
624: }
625:
626: String k = (key == null) ? "null" : (String) key;
627:
628: String r = (right == null) ? "null" : (String) right.key;
629: if (r == null) {
630: r = "null";
631: }
632:
633: String l = (left == null) ? "null" : (String) left.key;
634: if (l == null) {
635: l = "null";
636: }
637:
638: return "parent: " + p + ", key: " + k + ", right: " + r
639: + ", left: " + l;
640: }
641:
642: /**
643: * Debugging aid.
644: */
645: public void recursiveDump() {
646: recursiveDump(0);
647: }
648:
649: /**
650: * Debugging aid.
651: */
652: public void recursiveDump(int dumper) {
653: if (dumper > 30) {
654: return;
655: }
656: StringBuffer indent = new StringBuffer("" + dumper);
657: for (int i = 0; i <= binaryDepth; i++) {
658: indent.append("\t");
659: }
660: System.out.println("sd:" + indent.toString() + key);
661:
662: if (left != null) {
663: left.recursiveDump(dumper + 1);
664: }
665:
666: if (right != null) {
667: right.recursiveDump(dumper + 1);
668: }
669: }
670:
671: public String toString() {
672: return "BTreeNode: " + " (" + Header.VERSION + ")" + "\n"
673: + "\t" + "parent: "
674: + ((parent == null) ? "null" : "not null") + ", "
675: + "left: " + ((left == null) ? "null" : "not null")
676: + ", " + "right: "
677: + ((right == null) ? "null" : "not null") + "\n" + "\t"
678: + "visibility: " + visibility + ", " + "binaryDepth: "
679: + binaryDepth + ", " + "unaryDepth: " + unaryDepth
680: + "\n" + "\t" + "key: "
681: + ((key == null) ? "null" : "\n" + key.toString())
682: + "\n" + "\t" + "value: "
683: + ((value == null) ? "null" : "\n" + value.toString())
684: + "\n";
685: }
686: }
|