0001: /*
0002: * CONFIDENTIAL AND PROPRIETARY SOURCE CODE OF
0003: * NETSCAPE COMMUNICATIONS CORPORATION
0004: *
0005: * Copyright (c) 1996 Netscape Communications Corporation.
0006: * All Rights Reserved.
0007: * Use of this Source Code is subject to the terms of the applicable
0008: * license agreement from Netscape Communications Corporation.
0009: */
0010:
0011: package util;
0012:
0013: import java.util.Enumeration;
0014: import java.util.NoSuchElementException;
0015: import java.util.Vector;
0016:
0017: /**
0018: A binary tree enumerator.
0019: <p>
0020: Several methods directly manipulate the private <i>current</i>
0021: attribute which points at the enumerator's current position
0022: in the tree.
0023: Unlike many Enumerator implementations, this class doesn't
0024: permanently consume it's target,
0025: it can easily reset to the beginning or to arbitrary nodes
0026: in the tree.
0027: <p>
0028: The enumerator understands that it's root may be within
0029: a binary tree rather than being the actual root of a binary tree.
0030: <i>Created in less restrictive times, this functionality
0031: may be deprecated in favor of subtree clones.</i>
0032: <p>
0033: This class implements Enumeration, but adds features
0034: not in standard JDK enumeration classes.
0035: <p>
0036: <b>Open Issues</b>
0037: <ul>
0038: <li>Need toString() that will walk the tree according to
0039: the current enumeration type.
0040: <li>create methods that manipulate current do not take "stitching"
0041: into account, i.e. createNext() destroys the current.next
0042: if it is not null rather than inserting a new next between
0043: current and current.next. Issue for queryNode.
0044: <li>Should the methods that manipulate current be final?
0045: <li>Making BTreeNode non-public may eliminate the need for
0046: many of it's methods.
0047: </ul>
0048: <p>
0049: If the enumerationType is DEPTHFIRSTSORTED, <i>key</i> must be
0050: a String.
0051: <p>
0052: Note: "peers" are always understood to be the next list.
0053: SGP: Currently, no attempt is made by the peer functions to chain back
0054: to ensure that they are beginning at the root of a next list,
0055: probably should.
0056: *
0057: */
0058:
0059: public class BinaryTree implements Cloneable, Enumeration {
0060: private static final int ENUMERATION = 100;
0061: /**
0062: * Left (breadth) first enumeration.
0063: */
0064: public static final int LEFTFIRST = ENUMERATION + 1;
0065: /**
0066: * Breadth (left) first enumeration.
0067: */
0068: public static final int BREADTHFIRST = LEFTFIRST;
0069: /**
0070: * Right (depth) first enumeration.
0071: */
0072: public static final int RIGHTFIRST = ENUMERATION + 2;
0073: /**
0074: * Depth (right) first enumeration.
0075: */
0076: public static final int DEPTHFIRST = RIGHTFIRST;
0077: /**
0078: * Depth (right) sorted first enumeration.
0079: */
0080: public static final int DEPTHFIRSTSORTED = ENUMERATION + 3;
0081:
0082: private static final int RELATIVE = 200;
0083: /**
0084: * Parent.
0085: */
0086: public static final int PARENT = RELATIVE + 1;
0087: /**
0088: * Left (next).
0089: */
0090: public static final int LEFT = RELATIVE + 2;
0091: /**
0092: * Next (left).
0093: */
0094: public static final int NEXT = LEFT;
0095: /**
0096: * Right (child).
0097: */
0098: public static final int RIGHT = RELATIVE + 3;
0099: /**
0100: * Child (right).
0101: */
0102: public static final int CHILD = RIGHT;
0103:
0104: private int enumerationType;
0105:
0106: private BTreeNode root;
0107: private BTreeNode current;
0108:
0109: private boolean hasMore;
0110:
0111: public boolean debugging;
0112:
0113: private BTreeNode backCurrent;
0114: private boolean backHasMore;
0115:
0116: public BinaryTree(int enumerationType) {
0117: setEnumerationType(enumerationType);
0118:
0119: root = null;
0120: current = null;
0121:
0122: hasMore = false;
0123:
0124: debugging = false;
0125: }
0126:
0127: public Object clone() {
0128: try {
0129: BinaryTree bt = (BinaryTree) super .clone();
0130:
0131: if (root != null) {
0132: bt.root = (BTreeNode) root.clone();
0133: } else {
0134: bt.root = null;
0135: }
0136:
0137: current = root;
0138:
0139: return bt;
0140: } catch (CloneNotSupportedException e) {
0141: throw new InternalError();
0142: }
0143: }
0144:
0145: /**
0146: * Clone enumerator w/ a root that points at a copy of a binary
0147: * tree that starts w/ current.
0148: */
0149: public Object cloneSubTree() {
0150: try {
0151: BinaryTree bt = (BinaryTree) super .clone();
0152:
0153: if (root != null) {
0154: bt.root = (BTreeNode) current.clone();
0155: } else {
0156: bt.root = null;
0157: }
0158:
0159: root.setDepths(0, 0);
0160:
0161: current = root;
0162:
0163: return bt;
0164: } catch (CloneNotSupportedException e) {
0165: throw new InternalError();
0166: }
0167: }
0168:
0169: /*------------------*/
0170: /* enumeration type */
0171: /*------------------*/
0172:
0173: /**
0174: * Set enumeration type.
0175: * <p>
0176: * If the new type is DEPTHFIRSTSORTED,
0177: * it is the responsibility of the caller to
0178: * call keyIsDepthFirstSorted() to verify that
0179: * the enumeration is in that form.
0180: * The reason for this is so that the
0181: * sorting capability can be turned on and off
0182: * for performance reasons, since verification
0183: * is potentially costly.
0184: * @param enumerationType enumeration type
0185: * @exception IllegalArgumentException if not passed a legal type
0186: */
0187: public void setEnumerationType(int enumerationType)
0188: throws IllegalArgumentException {
0189: if ((enumerationType == LEFTFIRST)
0190: || (enumerationType == RIGHTFIRST)
0191: || (enumerationType == DEPTHFIRST)
0192: || (enumerationType == BREADTHFIRST)
0193: || (enumerationType == DEPTHFIRSTSORTED)) {
0194: this .enumerationType = enumerationType;
0195: } else {
0196: throw new IllegalArgumentException(
0197: Messages.UNKNOWNENUMERATIONTYPE);
0198: }
0199: }
0200:
0201: /**
0202: * Safely set enumeration type. If resetRoot is true, then
0203: * the current pointer is reset to root. If resetRoot is false,
0204: * then the operation fails if current is not equal to root.
0205: * in either case, if the operation fails false is returned
0206: * otherwise true is returned.
0207: * @param enumerationType enumeration type
0208: * @param resetRoot force reset to root or fail
0209: * @exception IllegalArgumentException if not passed a legal type
0210: */
0211: public boolean setSafeEnumerationType(int enumerationType,
0212: boolean resetRoot) throws IllegalArgumentException {
0213: if ((resetRoot) && (current != root)) {
0214: return false;
0215: }
0216:
0217: resetEnumeration();
0218: setEnumerationType(enumerationType);
0219:
0220: return true;
0221: }
0222:
0223: /*---------------*/
0224: /* enumeration++ */
0225: /*---------------*/
0226:
0227: /**
0228: * Whether or not the tree contains any data.
0229: */
0230: public boolean isEmpty() {
0231: return (root == null);
0232: }
0233:
0234: /**
0235: * Whether the tree has more elements.
0236: * Respect visibility.
0237: */
0238: public boolean hasMoreElements() {
0239: return (nextElement(false, false) != null);
0240: }
0241:
0242: /**
0243: * Return the next element in the tree.
0244: * Respect visibility.
0245: */
0246: public Object nextElement() {
0247: return nextElement(true, false);
0248: }
0249:
0250: /**
0251: * Whether the tree has more elements.
0252: * @param all all or respect visibility
0253: */
0254: public boolean hasMoreElements(boolean all) {
0255: return (nextElement(false, all) != null);
0256: }
0257:
0258: /**
0259: * Return the next element in the tree.
0260: * @param all all or respect visibility
0261: */
0262: public Object nextElement(boolean all) {
0263: return nextElement(true, all);
0264: }
0265:
0266: private Object nextElement(boolean realThing, boolean all) {
0267: if (current == null) {
0268: if (hasMore) {
0269: if (realThing) {
0270: // Root visibility is not
0271: // checked: root is assumed
0272: // to be visible.
0273: current = root;
0274: }
0275:
0276: return root;
0277: }
0278:
0279: if (realThing) {
0280: throw new NoSuchElementException("BinaryTree");
0281: } else {
0282: return null;
0283: }
0284: }
0285:
0286: BTreeNode tmpCurrent = current;
0287: BTreeNode tmpLeft;
0288: BTreeNode tmpRight;
0289: BTreeNode tmpParent;
0290:
0291: if (enumerationType == LEFTFIRST) {
0292: tmpLeft = tmpCurrent.getLeft(all);
0293: if (tmpLeft != null) {
0294: if (realThing) {
0295: current = tmpLeft;
0296: }
0297: return tmpLeft;
0298: }
0299:
0300: tmpRight = tmpCurrent.getRight(all);
0301: if (tmpRight != null) {
0302: if (realThing) {
0303: current = tmpRight;
0304: }
0305: return tmpRight;
0306: }
0307:
0308: for (tmpParent = tmpCurrent.getParent(); tmpParent != null; tmpParent = tmpCurrent
0309: .getParent()) {
0310: tmpRight = tmpParent.getRight(all);
0311: if ((tmpRight != null) && (tmpRight != tmpCurrent)) {
0312: if (realThing) {
0313: current = tmpRight;
0314: }
0315: return tmpRight;
0316: }
0317: tmpCurrent = tmpParent;
0318: }
0319: } else if ((enumerationType == RIGHTFIRST)
0320: || (enumerationType == DEPTHFIRSTSORTED)) {
0321: tmpRight = tmpCurrent.getRight(all);
0322: if (tmpRight != null) {
0323: if (realThing) {
0324: current = tmpRight;
0325: }
0326: if ((debugging) && (realThing)) {
0327: System.out.println("\n"
0328: + tmpCurrent.toStringSummary());
0329: System.out.println("right");
0330: System.out.println(tmpRight.toStringSummary());
0331: }
0332: return tmpRight;
0333: }
0334:
0335: tmpLeft = tmpCurrent.getLeft(all);
0336: if (tmpLeft != null) {
0337: if (realThing) {
0338: current = tmpLeft;
0339: }
0340: if ((debugging) && (realThing)) {
0341: System.out.println("\n"
0342: + tmpCurrent.toStringSummary());
0343: System.out.println("left");
0344: System.out.println(tmpLeft.toStringSummary());
0345: }
0346: return tmpLeft;
0347: }
0348:
0349: if ((debugging) && (realThing)) {
0350: System.out.println("");
0351: }
0352: for (tmpParent = tmpCurrent.getParent(); tmpParent != null; tmpParent = tmpCurrent
0353: .getParent()) {
0354: if ((debugging) && (realThing)) {
0355: System.out.println(tmpCurrent.toStringSummary());
0356: }
0357: tmpLeft = tmpParent.getLeft(all);
0358: if ((tmpLeft != null) && (tmpLeft != tmpCurrent)) {
0359: if (realThing) {
0360: current = tmpLeft;
0361: }
0362: if ((debugging) && (realThing)) {
0363: System.out
0364: .println(tmpCurrent.toStringSummary());
0365: System.out.println("parent left");
0366: System.out.println(tmpLeft.toStringSummary());
0367: }
0368: return tmpLeft;
0369: }
0370: tmpCurrent = tmpParent;
0371: }
0372: }
0373:
0374: hasMore = false;
0375:
0376: if (realThing) {
0377: current = null;
0378: throw new NoSuchElementException("BinaryTree");
0379: } else {
0380: return null;
0381: }
0382: }
0383:
0384: /**
0385: * Enumeration doesn't have to be a one way street.
0386: * Set the current pointer to root.
0387: */
0388: public void resetEnumeration() {
0389: current = null;
0390: hasMore = true;
0391: }
0392:
0393: /**
0394: * Enumeration doesn't even have to be a street.
0395: * Set the current pointer to passed node after verifying
0396: * that it's in this tree.
0397: * @param node new current node
0398: * @exception IllegalArgumentException if not passed a legal type
0399: */
0400: public void setEnumeration(BTreeNode node)
0401: throws IllegalArgumentException {
0402: if (node == root) {
0403: resetEnumeration();
0404: nextElement();
0405: return;
0406: }
0407:
0408: BTreeNode tmpParent = node.getParent();
0409:
0410: for (BTreeNode tmpNode = node; tmpParent != null; tmpNode = tmpParent) {
0411: if (root == tmpNode) {
0412: current = node;
0413: return;
0414: }
0415:
0416: tmpParent = tmpNode.getParent();
0417: }
0418:
0419: throw new IllegalArgumentException("target not in tree");
0420: }
0421:
0422: /**
0423: * Number of visible nodes in the binary tree enumeration.
0424: */
0425: public int count() {
0426: return count(false);
0427: }
0428:
0429: /**
0430: * Number of nodes in the binary tree enumeration.
0431: * @param all all or visible
0432: */
0433: public int count(boolean all) {
0434: if (isEmpty()) {
0435: return 0;
0436: }
0437:
0438: int n = 0;
0439:
0440: currentBackup();
0441: resetEnumeration();
0442: while (hasMoreElements(all)) {
0443: nextElement(all);
0444: n++;
0445: }
0446: currentRestore();
0447:
0448: return n;
0449: }
0450:
0451: // SGP: it would be good if backupLevel was a little more lock
0452: // like and errors were more assertively reported.
0453: private int backupLevel = 0;
0454:
0455: /**
0456: * Bookmark current position in the tree so
0457: * that it can be returned to later.
0458: * Note that some BinaryTree and TreeView methods use this
0459: * bookmark as well, so it is advisable to
0460: * use only when doing an independantly managed
0461: * tree traversal.
0462: */
0463: public void currentBackup() {
0464: backupLevel++;
0465: if (backupLevel > 1) {
0466: // System.out.println( ">> currentBackup() " + backupLevel );
0467: }
0468: backCurrent = current;
0469: backHasMore = hasMore;
0470: }
0471:
0472: /**
0473: * Restore from bookmark a saved "current" position.
0474: * Note that some BinaryTree and TreeView methods use this
0475: * bookmark as well, so it is advisable to
0476: * use only when doing an independantly managed
0477: * tree traversal.
0478: */
0479: public void currentRestore() {
0480: if (backupLevel > 1) {
0481: // System.out.println( ">> currentRestore() " + backupLevel );
0482: }
0483: backupLevel--;
0484: current = backCurrent;
0485: hasMore = backHasMore;
0486: }
0487:
0488: /*-----------------------------------*/
0489: /* surface node handling for current */
0490: /*-----------------------------------*/
0491:
0492: /*-------------*/
0493: /* set current */
0494: /*-------------*/
0495:
0496: /**
0497: * Effectively dereferences the current node, causing
0498: * current to point at the doomed node's parent.
0499: * May be redundant to cutCurrent().
0500: */
0501: public void nullifyCurrent() {
0502: if (current == null) {
0503: return;
0504: }
0505:
0506: BTreeNode tmp = current.getParent();
0507:
0508: if (tmp == null) {
0509: root = new BTreeNode();
0510: current = root;
0511: } else {
0512: if (tmp.getChild() == current) {
0513: tmp.setChild(null);
0514: } else {
0515: tmp.setNext(null);
0516: }
0517: current = tmp;
0518: }
0519: }
0520:
0521: /**
0522: * Cuts current out of tree.
0523: * Currently, the cut can only take with it LEFT
0524: * or RIGHT - not both.
0525: * If carry is LEFT, RIGHT is plugged into the
0526: * parent and vica versa.
0527: */
0528: public BTreeNode cutCurrent(int carry) {
0529: if (current == null) {
0530: return null;
0531: }
0532:
0533: if (!checkDescendant(carry)) {
0534: throw new IllegalArgumentException(
0535: Messages.UNKNOWNDESCENDANTTYPE);
0536: }
0537:
0538: BTreeNode prnt = current.getParent();
0539: BTreeNode drop = null;
0540:
0541: if (carry == LEFT) {
0542: drop = current.getRight(true);
0543: current.setRight(null);
0544: } else if (carry == RIGHT) {
0545: drop = current.getLeft(true);
0546: current.setLeft(null);
0547: }
0548:
0549: if (prnt == null) {
0550: root = drop;
0551: } else {
0552: if (prnt.getChild() == current) {
0553: prnt.setChild(drop);
0554: } else {
0555: prnt.setNext(drop);
0556: }
0557: }
0558:
0559: return current;
0560: }
0561:
0562: /**
0563: * If this is made public, add a hasAncestor() check.
0564: */
0565: private void moveCurrent(int carry, BTreeNode target,
0566: int targetBranch) {
0567: if (current == null) {
0568: return;
0569: }
0570:
0571: if ((!checkDescendant(carry))
0572: || (!checkDescendant(targetBranch))) {
0573: throw new IllegalArgumentException(
0574: Messages.UNKNOWNDESCENDANTTYPE);
0575: }
0576:
0577: BTreeNode prnt = current.getParent();
0578: BTreeNode drop = null;
0579:
0580: if (carry == LEFT) {
0581: drop = current.getRight(true);
0582: current.setRight(null);
0583: } else if (carry == RIGHT) {
0584: drop = current.getLeft(true);
0585: current.setLeft(null);
0586: }
0587:
0588: if (prnt == null) {
0589: root = drop;
0590: } else {
0591: if (prnt.getChild() == current) {
0592: prnt.setChild(drop);
0593: } else {
0594: prnt.setNext(drop);
0595: }
0596: }
0597:
0598: if (targetBranch == LEFT) {
0599: current.setLeft(target.getLeft(true));
0600: target.setLeft(current);
0601: } else if (targetBranch == RIGHT) {
0602: current.setLeft(target.getRight(true));
0603: target.setRight(current);
0604: }
0605: }
0606:
0607: /**
0608: * Creates a new root and sets current to the new root.
0609: * If a tree already exists, it is dereferenced.
0610: */
0611: private BTreeNode createRoot(BTreeNode pbtn, Object key,
0612: Object value) {
0613: if (pbtn != null) {
0614: root = pbtn;
0615: } else {
0616: root = new BTreeNode(key, value);
0617: }
0618: current = root;
0619: hasMore = true;
0620:
0621: return root;
0622: }
0623:
0624: /**
0625: * Creates a new root and sets current to the new root.
0626: * If a tree already exists, it is dereferenced.
0627: */
0628: private BTreeNode createRoot(BTreeNode btn) {
0629: root = btn;
0630: current = root;
0631: hasMore = true;
0632:
0633: return root;
0634: }
0635:
0636: /**
0637: * Creates a new child and sets current to the new child.
0638: * If a child already exists, it is dereferenced.
0639: * If no root exists, it is automatically created.
0640: */
0641: public BTreeNode createChild(Object key, Object value) {
0642: return createRight(key, value);
0643: }
0644:
0645: /**
0646: * Creates a new right and sets current to the new right.
0647: * If a right already exists, it is dereferenced.
0648: * If no root exists, it is automatically created.
0649: */
0650: public BTreeNode createRight(Object key, Object value) {
0651: if (root == null) {
0652: return createRoot(null, key, value);
0653: }
0654: current.setRight(new BTreeNode(key, value));
0655: current = current.getRight();
0656: return current;
0657: }
0658:
0659: /**
0660: * Creates a new next and sets current to the new next.
0661: * If a next already exists, it is dereferenced.
0662: * If no root exists, it is automatically created.
0663: */
0664: public BTreeNode createNext(Object key, Object value) {
0665: return createLeft(key, value);
0666: }
0667:
0668: /**
0669: * Creates a new left and sets current to the new left.
0670: * If a left already exists, it is dereferenced.
0671: * If no root exists, it is automatically created.
0672: */
0673: public BTreeNode createLeft(Object key, Object value) {
0674: if (root == null) {
0675: return createRoot(null, key, value);
0676: }
0677: current.setLeft(new BTreeNode(key, value));
0678: current = current.getLeft();
0679: return current;
0680: }
0681:
0682: /**
0683: * Creates a new child and sets current to the new child.
0684: * If a child already exists, it is dereferenced.
0685: * If no root exists, it is automatically created.
0686: * <b><font color="#FF0050">SGP: Potential recursion alert!</font></b>
0687: */
0688: public BTreeNode createChild(BTreeNode btn) {
0689: return createRight(btn);
0690: }
0691:
0692: /**
0693: * Creates a new right and sets current to the new right.
0694: * If a right already exists, it is dereferenced.
0695: * If no root exists, it is automatically created.
0696: * <b><font color="#FF0050">SGP: Potential recursion alert!</font></b>
0697: */
0698: public BTreeNode createRight(BTreeNode btn) {
0699: if (root == null) {
0700: return createRoot(btn);
0701: }
0702: current.setRight(btn);
0703: current = current.getRight();
0704: return current;
0705: }
0706:
0707: /**
0708: * Creates a new next and sets current to the new next.
0709: * If a next already exists, it is dereferenced.
0710: * If no root exists, it is automatically created.
0711: * <b><font color="#FF0050">SGP: Potential recursion alert!</font></b>
0712: */
0713: public BTreeNode createNext(BTreeNode btn) {
0714: return createLeft(btn);
0715: }
0716:
0717: /**
0718: * Creates a new left and sets current to the new left.
0719: * If a left already exists, it is dereferenced.
0720: * If no root exists, it is automatically created.
0721: * <b><font color="#FF0050">SGP: Potential recursion alert!</font></b>
0722: */
0723: public BTreeNode createLeft(BTreeNode btn) {
0724: if (root == null) {
0725: return createRoot(btn);
0726: }
0727: current.setLeft(btn);
0728: current = current.getLeft();
0729: return current;
0730: }
0731:
0732: private boolean checkDescendant(int relative) {
0733: return ((relative == LEFT) || (relative == RIGHT));
0734: }
0735:
0736: private boolean checkRelative(int relative) {
0737: return ((relative == PARENT) || (relative == LEFT) || (relative == RIGHT));
0738: }
0739:
0740: /**
0741: * Creates a new child and sets current to the new child.
0742: * If a child already exists, it is moved to the reposition target
0743: * of the new node.
0744: * If no root exists, it is automatically created.
0745: * If enumeration type is DEPTHFIRSTSORTED, the new node
0746: * is inserted in the correct place on this branch at
0747: * the next unaryDepth.
0748: * @param key key
0749: * @param value value
0750: * @param reposition where the current child goes on the new node
0751: */
0752: public BTreeNode insertChild(Object key, Object value,
0753: int reposition) {
0754: return insertRight(null, key, value, reposition);
0755: }
0756:
0757: /**
0758: * Creates a new child and sets current to the new child.
0759: * If a child already exists, it is moved to the reposition target
0760: * of the new node.
0761: * If no root exists, it is automatically created.
0762: * If enumeration type is DEPTHFIRSTSORTED, the new node
0763: * is inserted in the correct place on this branch at
0764: * the next unaryDepth.
0765: * If the passed node has a parent, it is reset.
0766: * SGP: recursion alert - need to check that the node
0767: * is not being placed in a subtree of itself.
0768: * @param btn node
0769: * @param reposition where the current child goes on the new node
0770: */
0771: public BTreeNode insertChild(BTreeNode pbtn, int reposition) {
0772: // return insertRight( pbtn, null, null, reposition );
0773: return insertRight(pbtn, pbtn.getKey(), pbtn.getValue(),
0774: reposition);
0775: }
0776:
0777: /**
0778: * Creates a new right and sets current to the new right.
0779: * If a right already exists, it is moved to the reposition target
0780: * of the new node.
0781: * If no root exists, it is automatically created.
0782: * If enumeration type is DEPTHFIRSTSORTED, the new node
0783: * is inserted in the correct place on this branch at
0784: * the next unaryDepth and a reposition value of RIGHT
0785: * is rejected as an error.
0786: * @param key key
0787: * @param value value
0788: * @param reposition where the current child goes on the new node
0789: * @exception IllegalArgumentException if not passed a legal type
0790: */
0791: public BTreeNode insertRight(Object key, Object value,
0792: int reposition) {
0793: return insertRight(null, key, value, reposition);
0794: }
0795:
0796: /**
0797: * Creates a new right and sets current to the new right.
0798: * If a right already exists, it is moved to the reposition target
0799: * of the new node.
0800: * If no root exists, it is automatically created.
0801: * If enumeration type is DEPTHFIRSTSORTED, the new node
0802: * is inserted in the correct place on this branch at
0803: * the next unaryDepth and a reposition value of RIGHT
0804: * is rejected as an error.
0805: * If the passed node has a parent, it is reset.
0806: * SGP: recursion alert - need to check that the node
0807: * is not being placed in a subtree of itself.
0808: * @param btn node
0809: * @param reposition where the current child goes on the new node
0810: */
0811: public BTreeNode insertRight(BTreeNode pbtn, int reposition) {
0812: // return insertRight( pbtn, null, null, reposition );
0813: return insertRight(pbtn, pbtn.getKey(), pbtn.getValue(),
0814: reposition);
0815: }
0816:
0817: /**
0818: * Note that checks to determine whether we're on the pbtn
0819: * axis or the key/value axis should be made by checking
0820: * to see if pbtn is null. It is possible for key to
0821: * become set during processing.
0822: */
0823: private BTreeNode insertRight(BTreeNode pbtn, Object key,
0824: Object value, int reposition)
0825: throws IllegalArgumentException {
0826: // System.out.println( "insertRight() beg -----------------------" );
0827: if (debugging) {
0828: System.out.println("insertRight()");
0829: }
0830: if (!checkDescendant(reposition)) {
0831: throw new IllegalArgumentException(
0832: Messages.UNKNOWNDESCENDANTTYPE);
0833: }
0834: if (root == null) {
0835: return createRoot(pbtn, key, value);
0836: }
0837: BTreeNode btn;
0838: if (pbtn != null) {
0839: btn = pbtn;
0840: key = pbtn.getKey();
0841: } else {
0842: btn = new BTreeNode(key, value);
0843: }
0844: BTreeNode trans = current.getRight(true);
0845: if (trans == null) {
0846: /* SGP: see angst in insertLeft() */
0847: // btn.setVisibility( BTreeNode.CLOSED );
0848: /*
0849: if ( reposition == LEFT )
0850: {
0851: btn.setVisibility( BTreeNode.LEFTVISIBLE );
0852: }
0853: else
0854: {
0855: btn.setVisibility( BTreeNode.RIGHTVISIBLE );
0856: }
0857: */
0858: } else {
0859: if (reposition == LEFT) {
0860: if (enumerationType == DEPTHFIRSTSORTED) {
0861: if (!(key instanceof String)) {
0862: throw new IllegalArgumentException(
0863: Messages.DEPTHFIRSTSORTEDKEYNOTSTRING);
0864: }
0865:
0866: if (((String) key).toLowerCase().compareTo(
0867: ((String) trans.getKey()).toLowerCase()) > 0) {
0868: setToChild();
0869: // System.out.println( "insertRight() end 2 -----------------------" );
0870: return insertLeft(pbtn, key, value, reposition);
0871: }
0872: }
0873:
0874: // btn.setVisibility( BTreeNode.LEFTVISIBLE );
0875: btn.setLeft(trans);
0876: } else {
0877: if (enumerationType == DEPTHFIRSTSORTED) {
0878: throw new IllegalArgumentException();
0879: }
0880:
0881: // btn.setVisibility( BTreeNode.RIGHTVISIBLE );
0882: btn.setRight(trans);
0883: }
0884: }
0885: current.setRight(btn);
0886: /*
0887: if ( ( getVisibility() == BTreeNode.OPEN )
0888: || ( getVisibility() == BTreeNode.LEFTVISIBLE )
0889: )
0890: {
0891: setVisibility( BTreeNode.OPEN );
0892: }
0893: else
0894: {
0895: setVisibility( BTreeNode.RIGHTVISIBLE );
0896: }
0897: */
0898: current = current.getRight();
0899: // System.out.println( "insertRight() end 3 -----------------------" );
0900: return current;
0901: }
0902:
0903: /**
0904: * Creates a new next and sets current to the new next.
0905: * If a next already exists, it is moved to the reposition target
0906: * of the new node.
0907: * If no root exists, it is automatically created.
0908: * If enumeration type is DEPTHFIRSTSORTED, the new node
0909: * is inserted in the correct place on this branch at
0910: * this unaryDepth.
0911: * @param key key
0912: * @param value value
0913: * @param reposition where the current child goes on the new node
0914: */
0915: public BTreeNode insertNext(Object key, Object value, int reposition) {
0916: return insertLeft(null, key, value, reposition);
0917: }
0918:
0919: /**
0920: * Creates a new next and sets current to the new next.
0921: * If a next already exists, it is moved to the reposition target
0922: * of the new node.
0923: * If no root exists, it is automatically created.
0924: * If enumeration type is DEPTHFIRSTSORTED, the new node
0925: * is inserted in the correct place on this branch at
0926: * this unaryDepth.
0927: * If the passed node has a parent, it is reset.
0928: * SGP: recursion alert - need to check that the node
0929: * is not being placed in a subtree of itself.
0930: * @param pbtn node
0931: * @param reposition where the current child goes on the new node
0932: */
0933: public BTreeNode insertNext(BTreeNode pbtn, int reposition) {
0934: // return insertLeft( pbtn, null, null, reposition );
0935: return insertLeft(pbtn, pbtn.getKey(), pbtn.getValue(),
0936: reposition);
0937: }
0938:
0939: /**
0940: * Creates a new left and sets current to the new left.
0941: * If a left already exists, it is moved to the reposition target
0942: * of the new node.
0943: * If no root exists, it is automatically created.
0944: * If enumeration type is DEPTHFIRSTSORTED, the new node
0945: * is inserted in the correct place on this branch at
0946: * this unaryDepth.
0947: * @param key key
0948: * @param value value
0949: * @param reposition where the current child goes on the new node
0950: */
0951: public BTreeNode insertLeft(Object key, Object value, int reposition) {
0952: return insertLeft(null, key, value, reposition);
0953: }
0954:
0955: /**
0956: * Creates a new left and sets current to the new left.
0957: * If a left already exists, it is moved to the reposition target
0958: * of the new node.
0959: * If no root exists, it is automatically created.
0960: * If enumeration type is DEPTHFIRSTSORTED, the new node
0961: * is inserted in the correct place on this branch at
0962: * this unaryDepth.
0963: * If the passed node has a parent, it is reset.
0964: * SGP: recursion alert - need to check that the node
0965: * is not being placed in a subtree of itself.
0966: * @param pbtn node
0967: * @param reposition where the current child goes on the new node
0968: */
0969: public BTreeNode insertLeft(BTreeNode pbtn, int reposition) {
0970: // return insertLeft( pbtn, null, null, reposition );
0971: return insertLeft(pbtn, pbtn.getKey(), pbtn.getValue(),
0972: reposition);
0973: }
0974:
0975: /**
0976: * Note that checks to determine whether we're on the pbtn
0977: * axis or the key/value axis should be made by checking
0978: * to see if pbtn is null. It is possible for key to
0979: * become set during processing.
0980: */
0981: private BTreeNode insertLeft(BTreeNode pbtn, Object key,
0982: Object value, int reposition)
0983: throws IllegalArgumentException {
0984: // System.out.println( "insertLeft() beg -----------------------" );
0985: if (debugging) {
0986: System.out.println("insertLeft() begin");
0987: }
0988: if (!checkDescendant(reposition)) {
0989: throw new IllegalArgumentException(
0990: Messages.UNKNOWNDESCENDANTTYPE);
0991: }
0992: if (root == null) {
0993: return createRoot(pbtn, key, value);
0994: }
0995: BTreeNode btn;
0996: if (pbtn != null) {
0997: btn = pbtn;
0998: key = pbtn.getKey();
0999: } else {
1000: btn = new BTreeNode(key, value);
1001: }
1002:
1003: if (enumerationType == DEPTHFIRSTSORTED) {
1004: if (reposition == RIGHT) {
1005: throw new IllegalArgumentException();
1006: }
1007:
1008: if (!(key instanceof String)) {
1009: throw new IllegalArgumentException(
1010: Messages.DEPTHFIRSTSORTEDKEYNOTSTRING);
1011: }
1012:
1013: int ud = getUnaryDepth();
1014: setToUnarySortParent((String) key);
1015: /* SGP: see setToUnarySortParent()
1016: ** description for uncovered corner case.
1017: */
1018: if (ud != getUnaryDepth()) {
1019: // System.out.println( "insertLeft() end 2 -----------------------" );
1020: return insertRight(pbtn, key, value, reposition);
1021: }
1022: }
1023:
1024: BTreeNode trans = current.getLeft(true);
1025: if (trans == null) {
1026: /* SGP: used to be CLOSED here. now it's
1027: ** not, but i'm suspicious. should revisit
1028: ** the model and figure out what is really
1029: ** supposed to happen - i suspect that a
1030: ** terminus should be closed. code in
1031: ** TreeView would have to overrule? much
1032: ** troubles.
1033: */
1034: /* SGP: the above comment was written when i went
1035: ** nuts w/ the LEFT/RIGHTVISIBLE thing instead of
1036: ** CLOSED. but here i am, in the middle of the night
1037: ** faced with a problem that is most easily solved
1038: ** by setting everything to OPEN and hoping that
1039: ** it doesn't mess anything up to do that. currently
1040: ** the visibility stuff is respected but not used
1041: ** in the apps, so may as well go ahead. actually,
1042: ** solving my current problem only requires that i
1043: ** leave it alone (it's already OPEN) so i'll do
1044: ** that and leave the opportunity to marvel at
1045: ** the mystery of visibility in the dim distant future.
1046: ** This angst applies to all commented out setVisibility
1047: ** calls. note that the default visibility is OPEN.
1048: */
1049: // btn.setVisibility( BTreeNode.CLOSED );
1050: /*
1051: if ( reposition == LEFT )
1052: {
1053: btn.setVisibility( BTreeNode.LEFTVISIBLE );
1054: }
1055: else
1056: {
1057: btn.setVisibility( BTreeNode.RIGHTVISIBLE );
1058: }
1059: */
1060: } else {
1061: if (reposition == LEFT) {
1062: // btn.setVisibility( BTreeNode.LEFTVISIBLE );
1063: btn.setLeft(trans);
1064: } else {
1065: if (enumerationType == DEPTHFIRSTSORTED) {
1066: throw new IllegalArgumentException();
1067: }
1068:
1069: // btn.setVisibility( BTreeNode.RIGHTVISIBLE );
1070: btn.setRight(trans);
1071: }
1072: }
1073: current.setLeft(btn);
1074: /*
1075: if ( ( getVisibility() == BTreeNode.OPEN )
1076: || ( getVisibility() == BTreeNode.RIGHTVISIBLE )
1077: )
1078: {
1079: setVisibility( BTreeNode.OPEN );
1080: }
1081: else
1082: {
1083: setVisibility( BTreeNode.LEFTVISIBLE );
1084: }
1085: */
1086: current = current.getLeft();
1087: if (debugging) {
1088: System.out.println("insertLeft() end");
1089: }
1090: // System.out.println( "insertLeft() end 3 -----------------------" );
1091: return current;
1092: }
1093:
1094: /**
1095: * Find the correct sort parent at this unary depth.
1096: * The caller is expected to determine if the parent
1097: * turns out to be at the next depth up.
1098: * The enumerationType must be DEPTHFIRSTSORTED,
1099: * since the method is private, this is not verified.
1100: * SGP: The "true" in the enumeration raises questions.
1101: * SGP: Ignoring corner case where the check is done
1102: * at the top unary level of the tree and the result
1103: * turns out to be that the proposed key should be
1104: * the new root.
1105: */
1106: private void setToUnarySortParent(String s) {
1107: int d = getUnaryDepth();
1108: String lc = s.toLowerCase();
1109:
1110: /* go to end of list or one past desired parent */
1111: while ((lc.compareTo(((String) getKey()).toLowerCase()) > 0)
1112: && (getNext(true) != null)) {
1113: setToNext();
1114: }
1115:
1116: /* back up to desired parent, not going beyond udepth-1 */
1117: while ((lc.compareTo(((String) getKey()).toLowerCase()) <= 0)
1118: && (getParent() != null) && (getUnaryDepth() == d)) {
1119: setToParent();
1120: }
1121: }
1122:
1123: /**
1124: * Set the visibility.
1125: */
1126: public void setVisibility(int visibility) {
1127: current.setVisibility(visibility);
1128: }
1129:
1130: /**
1131: * Sets the key.
1132: * If the enumeration is DEPTHFIRSTSORTED, it also sorts the peer group.
1133: */
1134: public boolean setKey(Object key) {
1135: // System.out.println( "setKey() beg" );
1136: // dumpTree();
1137: current.key = key;
1138: if (enumerationType == DEPTHFIRSTSORTED) {
1139: // SGP: suspecting i18n/l10n issues, yes i am
1140:
1141: if ((!(key instanceof String)) || (key == null)) {
1142: ReportError
1143: .reportError(ReportError.USER, "BinaryTree",
1144: "setKey",
1145: Messages.DEPTHFIRSTSORTEDKEYNOTSTRING);
1146: return false;
1147: }
1148:
1149: String skey = ((String) key).toLowerCase();
1150:
1151: // go back, looking for a new predecessor
1152: // on this level...
1153: BTreeNode p;
1154: for (p = current.getParent(); p != null; p = p.getParent()) {
1155: // if we go up a level...
1156: if (current.getUnaryDepth() != p.getUnaryDepth()) {
1157: // and this isn't our parent...
1158: if (p != current.getParent()) {
1159: // System.out.println( "setKey() 1" );
1160: // cut out current
1161: // insert at p as child
1162: moveCurrent(CHILD, p, CHILD);
1163: // dumpTree();
1164: return true;
1165: } else {
1166: break;
1167: }
1168: }
1169:
1170: // if we're greater than this...
1171: if (skey.compareTo(((String) p.getKey()).toLowerCase()) > 0) {
1172: // and this isn't our parent...
1173: if (p != current.getParent()) {
1174: // System.out.println( "setKey() 2" );
1175: // cut out current
1176: // insert at p as next
1177: moveCurrent(CHILD, p, NEXT);
1178: // dumpTree();
1179: return true;
1180: } else {
1181: break;
1182: }
1183: }
1184: }
1185:
1186: // side note: in case it isn't obvious, unary
1187: // depth should never change in this maneuver.
1188:
1189: // if we hit the top of the tree on this level
1190: // looking for a new predecessor, we get to
1191: // be root...
1192: if ((p == null) && (current != root)) {
1193: // System.out.println( "setKey() 3" );
1194: // new root, w/ current root as next
1195: BTreeNode c = cutCurrent(RIGHT);
1196: c.setNext(root);
1197: root = c;
1198: // dumpTree();
1199: return true;
1200: }
1201:
1202: BTreeNode n = current.getNext(true);
1203:
1204: // if there's no place to go, do nothing...
1205: if (n == null) {
1206: // System.out.println( "setKey() 4" );
1207: // dumpTree();
1208: return true;
1209: }
1210:
1211: // if what follows is greater than or equal to, bail...
1212: if (skey.compareTo(((String) n.getKey()).toLowerCase()) <= 0) {
1213: // System.out.println( "setKey() 5" );
1214: // dumpTree();
1215: return true;
1216: }
1217:
1218: // if we're still around, we go down the list
1219: // looking for a new parent...
1220: for (; n != null; n = n.getNext(true)) {
1221: // if we're greater than and nothing follows...
1222: if ((skey
1223: .compareTo(((String) n.getKey()).toLowerCase()) > 0)
1224: && (n.getNext(true) == null)) {
1225: // System.out.println( "setKey() 6" );
1226: // cut out current
1227: // insert at n as next
1228: moveCurrent(CHILD, n, NEXT);
1229: // dumpTree();
1230: return true;
1231: }
1232:
1233: // if we're greater than and what follows
1234: // is greater than or equal to us, then...
1235: if ((skey
1236: .compareTo(((String) n.getKey()).toLowerCase()) > 0)
1237: && (skey.compareTo(((String) n.getNext(true)
1238: .getKey()).toLowerCase()) <= 0)) {
1239: // System.out.println( "setKey() 7" );
1240: // cut out current
1241: // insert at n as next
1242: moveCurrent(CHILD, n, NEXT);
1243: // dumpTree();
1244: return true;
1245: }
1246: }
1247:
1248: // SGP: wishing for tripartite status, OK w/ move,
1249: // OK w/out move, not OK. this here is the OK w/out
1250: // move.
1251: // System.out.println( "setKey() 8" );
1252: // dumpTree();
1253: return false;
1254: }
1255:
1256: // System.out.println( "setKey() end" );
1257: // dumpTree();
1258: return true;
1259: }
1260:
1261: /**
1262: * Set the value.
1263: * @param value the value in question
1264: */
1265: public void setValue(Object value) {
1266: current.value = value;
1267: }
1268:
1269: /*-------------*/
1270: /* get current */
1271: /*-------------*/
1272:
1273: /**
1274: * Search full tree by key, set current to result
1275: * and return true if found.
1276: */
1277: public boolean setTreeNodeByKey(Object o) {
1278: BTreeNode tmp = root.getNodeByKey(o);
1279:
1280: if (tmp == null) {
1281: return false;
1282: } else {
1283: current = tmp;
1284: return true;
1285: }
1286: }
1287:
1288: /**
1289: * Search full tree by value, set current to result
1290: * and return true if found.
1291: */
1292: public boolean setTreeNodeByValue(Object o) {
1293: BTreeNode tmp = root.getNodeByValue(o);
1294:
1295: if (tmp == null) {
1296: return false;
1297: } else {
1298: current = tmp;
1299: return true;
1300: }
1301: }
1302:
1303: /**
1304: * Search subtree by key, set current to result
1305: * and return true if found.
1306: */
1307: public boolean setSubtreeNodeByKey(Object o) {
1308: BTreeNode tmp = current.getNodeByKey(o);
1309:
1310: if (tmp == null) {
1311: return false;
1312: } else {
1313: current = tmp;
1314: return true;
1315: }
1316: }
1317:
1318: /**
1319: * Search subtree by value, set current to result
1320: * and return true if found.
1321: */
1322: public boolean setSubtreeNodeByValue(Object o) {
1323: BTreeNode tmp = current.getNodeByValue(o);
1324:
1325: if (tmp == null) {
1326: return false;
1327: } else {
1328: current = tmp;
1329: return true;
1330: }
1331: }
1332:
1333: /**
1334: * Search full tree by key, return value.
1335: * @param o target
1336: */
1337: public Object getTreeValueByKey(Object o) {
1338: BTreeNode tmp = root.getNodeByKey(o);
1339:
1340: return (tmp == null) ? null : tmp.getValue();
1341: }
1342:
1343: /**
1344: * Search full tree by value, return key.
1345: * @param o target
1346: */
1347: public Object getTreeKeyByValue(Object o) {
1348: BTreeNode tmp = root.getNodeByValue(o);
1349:
1350: return (tmp == null) ? null : tmp.getKey();
1351: }
1352:
1353: /**
1354: * Search subtree by key, return value.
1355: * @param o target
1356: */
1357: public Object getSubtreeValueByKey(Object o) {
1358: BTreeNode tmp = current.getNodeByKey(o);
1359:
1360: return (tmp == null) ? null : tmp.getValue();
1361: }
1362:
1363: /**
1364: * Search subtree by value, return key.
1365: * @param o target
1366: */
1367: public Object getSubtreeKeyByValue(Object o) {
1368: BTreeNode tmp = current.getNodeByValue(o);
1369:
1370: return (tmp == null) ? null : tmp.getKey();
1371: }
1372:
1373: public BTreeNode getCurrent() {
1374: return current;
1375: }
1376:
1377: public Object getValue() {
1378: return current.getValue();
1379: }
1380:
1381: public Object getKey() {
1382: return current.getKey();
1383: }
1384:
1385: /**
1386: * Get the 'current' node's visibility.
1387: */
1388: public int getVisibility() {
1389: return current.getVisibility();
1390: }
1391:
1392: /**
1393: * Get the 'current' node's terminal policy.
1394: */
1395: public int getTerminalPolicy() {
1396: return current.getTerminalPolicy();
1397: }
1398:
1399: /**
1400: * Get the 'current' node's binary depth.
1401: */
1402: public int getBinaryDepth() {
1403: return current.getBinaryDepth();
1404: }
1405:
1406: /**
1407: * Get the 'current' node's unary depth.
1408: */
1409: public int getUnaryDepth() {
1410: return current.getUnaryDepth();
1411: }
1412:
1413: public int getChildPeerCount(boolean all) {
1414: int n = 0;
1415:
1416: for (BTreeNode tmp = current.getChild(all); tmp != null; tmp = tmp
1417: .getNext(all)) {
1418: n++;
1419: }
1420:
1421: return n;
1422: }
1423:
1424: public Vector getChildPeers(boolean all) {
1425: Vector v = new Vector(getChildPeerCount(all));
1426:
1427: for (BTreeNode tmp = current.getChild(all); tmp != null; tmp = tmp
1428: .getNext(all)) {
1429: v.addElement(tmp);
1430: }
1431:
1432: return v;
1433: }
1434:
1435: public int getPeerCount(boolean all) {
1436: int n = 0;
1437:
1438: for (BTreeNode tmp = getFirstPeer(); tmp != null; tmp = tmp
1439: .getNext(all)) {
1440: n++;
1441: }
1442:
1443: return n;
1444: }
1445:
1446: public Vector getPeers(boolean all) {
1447: Vector v = new Vector(getPeerCount(all));
1448:
1449: for (BTreeNode tmp = getFirstPeer(); tmp != null; tmp = tmp
1450: .getNext(all)) {
1451: v.addElement(tmp);
1452: }
1453:
1454: return v;
1455: }
1456:
1457: public BTreeNode getFirstPeer() {
1458: if (current == null) {
1459: return null;
1460: }
1461: BTreeNode tmp1 = current;
1462: BTreeNode tmp2 = tmp1.getParent();
1463: while (tmp2 != null) {
1464: if (tmp2.getNext() != tmp1) {
1465: return tmp1;
1466: }
1467: tmp1 = tmp2;
1468: tmp2 = tmp1.getParent();
1469: }
1470:
1471: return tmp1;
1472: }
1473:
1474: public BTreeNode getFirstPeerByKey(String k, boolean all) {
1475: Enumeration e = getPeers(all).elements();
1476: while (e.hasMoreElements()) {
1477: BTreeNode btn = (BTreeNode) e.nextElement();
1478: String s = (String) btn.getKey();
1479: if (k.equals(s)) {
1480: return btn;
1481: }
1482: }
1483: return null;
1484: }
1485:
1486: /**
1487: * Count the number of peers with the passed key.
1488: * Good for duplicate peer detection.
1489: * @param k key
1490: * @param all all or respect visibility
1491: */
1492: public int countPeersByKey(String k, boolean all) {
1493: int count = 0;
1494: Enumeration e = getPeers(all).elements();
1495: while (e.hasMoreElements()) {
1496: BTreeNode btn = (BTreeNode) e.nextElement();
1497: String s = (String) btn.getKey();
1498: if (k.equals(s)) {
1499: count++;
1500: }
1501: }
1502: return count;
1503: }
1504:
1505: /**
1506: * Get the root.
1507: */
1508: public BTreeNode getRoot() {
1509: return root;
1510: }
1511:
1512: /**
1513: * Get the parent.
1514: */
1515: public BTreeNode getParent() {
1516: return current.getParent();
1517: }
1518:
1519: /**
1520: * Get the child (right).
1521: */
1522: public BTreeNode getChild() {
1523: return getRight(false);
1524: }
1525:
1526: /**
1527: * Get the child (right).
1528: * @param all all or respect visibility
1529: */
1530: public BTreeNode getChild(boolean all) {
1531: return getRight(all);
1532: }
1533:
1534: /**
1535: * Get the right (child).
1536: */
1537: public BTreeNode getRight() {
1538: return getRight(false);
1539: }
1540:
1541: /**
1542: * Get the right (child).
1543: * @param all all or respect visibility
1544: */
1545: public BTreeNode getRight(boolean all) {
1546: return current.getRight(all);
1547: }
1548:
1549: /**
1550: * Get the next (left).
1551: */
1552: public BTreeNode getNext() {
1553: return getLeft(false);
1554: }
1555:
1556: /**
1557: * Get the next (left).
1558: * @param all all or respect visibility
1559: */
1560: public BTreeNode getNext(boolean all) {
1561: return getLeft(all);
1562: }
1563:
1564: /**
1565: * Get the left (next).
1566: */
1567: public BTreeNode getLeft() {
1568: return getLeft(false);
1569: }
1570:
1571: /**
1572: * Get the left (next).
1573: * @param all all or respect visibility
1574: */
1575: public BTreeNode getLeft(boolean all) {
1576: return current.getLeft(all);
1577: }
1578:
1579: /**
1580: * Get the unary parent, the parent of a peer set.
1581: * If successful, the parent is returned, if it fails,
1582: * null is returned and it can be assumed that the
1583: * peer set is headed by root and using setToRoot()
1584: * might be the next step - this is not done automatically
1585: * because it is semantically significantly different.
1586: */
1587: public BTreeNode getUnaryParent() {
1588: int ud = getUnaryDepth();
1589:
1590: for (BTreeNode btn = current.getParent(); btn != null; btn = btn
1591: .getParent()) {
1592: if (ud != btn.getUnaryDepth()) {
1593: return btn;
1594: }
1595: }
1596:
1597: return null;
1598: }
1599:
1600: /**
1601: * Set to the unary parent, to the parent of a peer set.
1602: * If successful, true is returned, if it fails, the
1603: * peer set is headed by root and using setToRoot()
1604: * might be the next step - this is not done automatically
1605: * because it is semantically significantly different.
1606: */
1607: public boolean setToUnaryParent() {
1608: int ud = getUnaryDepth();
1609:
1610: for (BTreeNode btn = current.getParent(); btn != null; btn = btn
1611: .getParent()) {
1612: if (ud != btn.getUnaryDepth()) {
1613: current = btn;
1614: return true;
1615: }
1616: }
1617:
1618: return false;
1619: }
1620:
1621: /**
1622: * Set current position in tree to the parent of the current position.
1623: */
1624: public boolean setToParent() {
1625: if (current.getParent() == null) {
1626: return false;
1627: } else {
1628: current = current.getParent();
1629: return true;
1630: }
1631: }
1632:
1633: /**
1634: * Set current position in tree to the root of the tree.
1635: */
1636: public void setToRoot() {
1637: current = root;
1638: }
1639:
1640: /**
1641: * Set current position in tree to the child (right) of the current position.
1642: */
1643: public boolean setToChild() {
1644: return setToRight();
1645: }
1646:
1647: /**
1648: * Set current position in tree to the right (child) of the current position.
1649: */
1650: public boolean setToRight() {
1651: BTreeNode tmp = current.getRight();
1652:
1653: if (tmp == null) {
1654: return false;
1655: } else {
1656: current = tmp;
1657: return true;
1658: }
1659: }
1660:
1661: /**
1662: * Set current position in tree to the next (left) of the current position.
1663: */
1664: public boolean setToNext() {
1665: return setToLeft();
1666: }
1667:
1668: /**
1669: * Set current position in tree to the left (next) of the current position.
1670: */
1671: public boolean setToLeft() {
1672: BTreeNode tmp = current.getLeft();
1673:
1674: if (tmp == null) {
1675: return false;
1676: } else {
1677: current = tmp;
1678: return true;
1679: }
1680: }
1681:
1682: /**
1683: * Verify that the keys in the tree conform to
1684: * the rules governing DEPTHFIRSTSORTED.
1685: * Keys must be Strings and must be in String.compareTo() valid
1686: * sort order.
1687: * Called automatically by setEnumerationType().
1688: * <b><font color="#FF0050">SGP: not done!</font></b>
1689: */
1690: public boolean keyIsDepthFirstSorted() {
1691: return true;
1692: }
1693:
1694: /*------------*/
1695: /* toString() */
1696: /*------------*/
1697:
1698: public String toString() {
1699: return "BinaryTree: " + " (" + Header.VERSION + ")" + "\n"
1700: + "\t" + "enumerationType: " + enumerationType + "\n"
1701: + "\t" + "root: "
1702: + ((root == null) ? "null" : "not null") + "\n" + "\t"
1703: + "current: "
1704: + ((current == null) ? "null" : "not null") + "\n";
1705: }
1706:
1707: /**
1708: * Debugging aid.
1709: */
1710: public void dumpTree() {
1711: System.out.println("---< v dumpTree() >-----");
1712: currentBackup();
1713: resetEnumeration();
1714: int j = 0;
1715: while ((hasMoreElements(true)) && (j++ < 100)) {
1716: nextElement(true);
1717: StringBuffer indent = new StringBuffer();
1718: for (int i = 1; i <= getUnaryDepth(); i++) {
1719: indent.append(" ");
1720: }
1721: System.out.println(indent.toString()
1722: // + getVisibility()
1723: // + " "
1724: // + getTerminalPolicy()
1725: // + " "
1726: + getKey()
1727: // + " "
1728: // + ( String ) ( ( getValue() == null )
1729: // ? "<null>"
1730: // : "<not null>"
1731: // )
1732: );
1733: }
1734: currentRestore();
1735: System.out.println("= " + j + " entries - dump caps at 100");
1736: System.out.println("---< ^ dumpTree() >-----");
1737: }
1738:
1739: /**
1740: * Debugging aid.
1741: */
1742: public String toStringTree() {
1743: StringBuffer sb = new StringBuffer(toString());
1744:
1745: if (isEmpty()) {
1746: return sb.toString();
1747: }
1748:
1749: sb.append("---------------------\n");
1750:
1751: currentBackup();
1752: resetEnumeration();
1753:
1754: while (hasMoreElements(true)) {
1755: nextElement(true);
1756: BTreeNode btn = getCurrent();
1757: sb.append(btn.toString() + "\n");
1758: sb.append("---------------------\n");
1759: }
1760: currentRestore();
1761:
1762: return sb.toString();
1763: }
1764: }
|