| java.lang.Object
 util.BinaryTree
| BinaryTree | | public class BinaryTree implements Cloneable,Enumeration(Code) | | A binary tree enumerator.
Several methods directly manipulate the private current
attribute which points at the enumerator's current position
in the tree.
Unlike many Enumerator implementations, this class doesn't
permanently consume it's target,
it can easily reset to the beginning or to arbitrary nodes
in the tree.
The enumerator understands that it's root may be within
a binary tree rather than being the actual root of a binary tree.
Created in less restrictive times, this functionality
may be deprecated in favor of subtree clones.
This class implements Enumeration, but adds features
not in standard JDK enumeration classes.
Open Issues
- Need toString() that will walk the tree according to
the current enumeration type.
- create methods that manipulate current do not take "stitching"
into account, i.e. createNext() destroys the current.next
if it is not null rather than inserting a new next between
current and current.next. Issue for queryNode.
- Should the methods that manipulate current be final?
- Making BTreeNode non-public may eliminate the need for
many of it's methods.
If the enumerationType is DEPTHFIRSTSORTED, key must be
a String.
Note: "peers" are always understood to be the next list.
SGP: Currently, no attempt is made by the peer functions to chain back
to ensure that they are beginning at the root of a next list,
probably should.
|
| Field Summary | |
| final public static int | BREADTHFIRST
Breadth (left) first enumeration. | | final public static int | CHILD
Child (right). | | final public static int | DEPTHFIRST
Depth (right) first enumeration. | | final public static int | DEPTHFIRSTSORTED
Depth (right) sorted first enumeration. | | final public static int | LEFT
Left (next). | | final public static int | LEFTFIRST
Left (breadth) first enumeration. | | final public static int | NEXT
Next (left). | | final public static int | PARENT
Parent. | | final public static int | RIGHT
Right (child). | | final public static int | RIGHTFIRST
Right (depth) first enumeration. | | public boolean | debugging
|
| Constructor Summary | |
| public | BinaryTree(int enumerationType)
|
| Method Summary | |
| public Object | clone()
| | public Object | cloneSubTree()
Clone enumerator w/ a root that points at a copy of a binary
tree that starts w/ current. | | public int | count()
Number of visible nodes in the binary tree enumeration. | | public int | count(boolean all)
Number of nodes in the binary tree enumeration. | | public int | countPeersByKey(String k, boolean all)
Count the number of peers with the passed key. | | public BTreeNode | createChild(Object key, Object value)
Creates a new child and sets current to the new child. | | public BTreeNode | createChild(BTreeNode btn)
Creates a new child and sets current to the new child. | | public BTreeNode | createLeft(Object key, Object value)
Creates a new left and sets current to the new left. | | public BTreeNode | createLeft(BTreeNode btn)
Creates a new left and sets current to the new left. | | public BTreeNode | createNext(Object key, Object value)
Creates a new next and sets current to the new next. | | public BTreeNode | createNext(BTreeNode btn)
Creates a new next and sets current to the new next. | | public BTreeNode | createRight(Object key, Object value)
Creates a new right and sets current to the new right. | | public BTreeNode | createRight(BTreeNode btn)
Creates a new right and sets current to the new right. | | public void | currentBackup()
Bookmark current position in the tree so
that it can be returned to later. | | public void | currentRestore()
Restore from bookmark a saved "current" position. | | public BTreeNode | cutCurrent(int carry)
Cuts current out of tree. | | public void | dumpTree()
Debugging aid. | | public int | getBinaryDepth()
Get the 'current' node's binary depth. | | public BTreeNode | getChild()
Get the child (right). | | public BTreeNode | getChild(boolean all)
Get the child (right). | | public int | getChildPeerCount(boolean all)
| | public Vector | getChildPeers(boolean all)
| | public BTreeNode | getCurrent()
| | public BTreeNode | getFirstPeer()
| | public BTreeNode | getFirstPeerByKey(String k, boolean all)
| | public Object | getKey()
| | public BTreeNode | getLeft()
Get the left (next). | | public BTreeNode | getLeft(boolean all)
Get the left (next). | | public BTreeNode | getNext()
Get the next (left). | | public BTreeNode | getNext(boolean all)
Get the next (left). | | public BTreeNode | getParent()
Get the parent. | | public int | getPeerCount(boolean all)
| | public Vector | getPeers(boolean all)
| | public BTreeNode | getRight()
Get the right (child). | | public BTreeNode | getRight(boolean all)
Get the right (child). | | public BTreeNode | getRoot()
Get the root. | | public Object | getSubtreeKeyByValue(Object o)
Search subtree by value, return key. | | public Object | getSubtreeValueByKey(Object o)
Search subtree by key, return value. | | public int | getTerminalPolicy()
Get the 'current' node's terminal policy. | | public Object | getTreeKeyByValue(Object o)
Search full tree by value, return key. | | public Object | getTreeValueByKey(Object o)
Search full tree by key, return value. | | public int | getUnaryDepth()
Get the 'current' node's unary depth. | | public BTreeNode | getUnaryParent()
Get the unary parent, the parent of a peer set. | | public Object | getValue()
| | public int | getVisibility()
Get the 'current' node's visibility. | | public boolean | hasMoreElements()
Whether the tree has more elements. | | public boolean | hasMoreElements(boolean all)
Whether the tree has more elements. | | public BTreeNode | insertChild(Object key, Object value, int reposition)
Creates a new child and sets current to the new child. | | public BTreeNode | insertChild(BTreeNode pbtn, int reposition)
Creates a new child and sets current to the new child. | | public BTreeNode | insertLeft(Object key, Object value, int reposition)
Creates a new left and sets current to the new left. | | public BTreeNode | insertLeft(BTreeNode pbtn, int reposition)
Creates a new left and sets current to the new left. | | public BTreeNode | insertNext(Object key, Object value, int reposition)
Creates a new next and sets current to the new next. | | public BTreeNode | insertNext(BTreeNode pbtn, int reposition)
Creates a new next and sets current to the new next. | | public BTreeNode | insertRight(Object key, Object value, int reposition)
Creates a new right and sets current to the new right. | | public BTreeNode | insertRight(BTreeNode pbtn, int reposition)
Creates a new right and sets current to the new right. | | public boolean | isEmpty()
Whether or not the tree contains any data. | | public boolean | keyIsDepthFirstSorted()
Verify that the keys in the tree conform to
the rules governing DEPTHFIRSTSORTED. | | public Object | nextElement()
Return the next element in the tree. | | public Object | nextElement(boolean all)
Return the next element in the tree. | | public void | nullifyCurrent()
Effectively dereferences the current node, causing
current to point at the doomed node's parent. | | public void | resetEnumeration()
Enumeration doesn't have to be a one way street. | | public void | setEnumeration(BTreeNode node)
Enumeration doesn't even have to be a street. | | public void | setEnumerationType(int enumerationType)
Set enumeration type. | | public boolean | setKey(Object key)
Sets the key. | | public boolean | setSafeEnumerationType(int enumerationType, boolean resetRoot)
Safely set enumeration type. | | public boolean | setSubtreeNodeByKey(Object o)
Search subtree by key, set current to result
and return true if found. | | public boolean | setSubtreeNodeByValue(Object o)
Search subtree by value, set current to result
and return true if found. | | public boolean | setToChild()
Set current position in tree to the child (right) of the current position. | | public boolean | setToLeft()
Set current position in tree to the left (next) of the current position. | | public boolean | setToNext()
Set current position in tree to the next (left) of the current position. | | public boolean | setToParent()
Set current position in tree to the parent of the current position. | | public boolean | setToRight()
Set current position in tree to the right (child) of the current position. | | public void | setToRoot()
Set current position in tree to the root of the tree. | | public boolean | setToUnaryParent()
Set to the unary parent, to the parent of a peer set. | | public boolean | setTreeNodeByKey(Object o)
Search full tree by key, set current to result
and return true if found. | | public boolean | setTreeNodeByValue(Object o)
Search full tree by value, set current to result
and return true if found. | | public void | setValue(Object value)
Set the value. | | public void | setVisibility(int visibility)
Set the visibility. | | public String | toString()
| | public String | toStringTree()
Debugging aid. |
| BREADTHFIRST | | final public static int BREADTHFIRST(Code) | | Breadth (left) first enumeration.
|
| CHILD | | final public static int CHILD(Code) | | Child (right).
|
| DEPTHFIRST | | final public static int DEPTHFIRST(Code) | | Depth (right) first enumeration.
|
| DEPTHFIRSTSORTED | | final public static int DEPTHFIRSTSORTED(Code) | | Depth (right) sorted first enumeration.
|
| LEFT | | final public static int LEFT(Code) | | Left (next).
|
| LEFTFIRST | | final public static int LEFTFIRST(Code) | | Left (breadth) first enumeration.
|
| NEXT | | final public static int NEXT(Code) | | Next (left).
|
| PARENT | | final public static int PARENT(Code) | | Parent.
|
| RIGHT | | final public static int RIGHT(Code) | | Right (child).
|
| RIGHTFIRST | | final public static int RIGHTFIRST(Code) | | Right (depth) first enumeration.
|
| debugging | | public boolean debugging(Code) | | |
| BinaryTree | | public BinaryTree(int enumerationType)(Code) | | |
| cloneSubTree | | public Object cloneSubTree()(Code) | | Clone enumerator w/ a root that points at a copy of a binary
tree that starts w/ current.
|
| count | | public int count()(Code) | | Number of visible nodes in the binary tree enumeration.
|
| count | | public int count(boolean all)(Code) | | Number of nodes in the binary tree enumeration.
Parameters:
all - all or visible |
| countPeersByKey | | public int countPeersByKey(String k, boolean all)(Code) | | Count the number of peers with the passed key.
Good for duplicate peer detection.
Parameters:
k - key
Parameters:
all - all or respect visibility |
| createChild | | public BTreeNode createChild(Object key, Object value)(Code) | | Creates a new child and sets current to the new child.
If a child already exists, it is dereferenced.
If no root exists, it is automatically created.
|
| createChild | | public BTreeNode createChild(BTreeNode btn)(Code) | | Creates a new child and sets current to the new child.
If a child already exists, it is dereferenced.
If no root exists, it is automatically created.
SGP: Potential recursion alert!
|
| createLeft | | public BTreeNode createLeft(Object key, Object value)(Code) | | Creates a new left and sets current to the new left.
If a left already exists, it is dereferenced.
If no root exists, it is automatically created.
|
| createLeft | | public BTreeNode createLeft(BTreeNode btn)(Code) | | Creates a new left and sets current to the new left.
If a left already exists, it is dereferenced.
If no root exists, it is automatically created.
SGP: Potential recursion alert!
|
| createNext | | public BTreeNode createNext(Object key, Object value)(Code) | | Creates a new next and sets current to the new next.
If a next already exists, it is dereferenced.
If no root exists, it is automatically created.
|
| createNext | | public BTreeNode createNext(BTreeNode btn)(Code) | | Creates a new next and sets current to the new next.
If a next already exists, it is dereferenced.
If no root exists, it is automatically created.
SGP: Potential recursion alert!
|
| createRight | | public BTreeNode createRight(Object key, Object value)(Code) | | Creates a new right and sets current to the new right.
If a right already exists, it is dereferenced.
If no root exists, it is automatically created.
|
| createRight | | public BTreeNode createRight(BTreeNode btn)(Code) | | Creates a new right and sets current to the new right.
If a right already exists, it is dereferenced.
If no root exists, it is automatically created.
SGP: Potential recursion alert!
|
| currentBackup | | public void currentBackup()(Code) | | Bookmark current position in the tree so
that it can be returned to later.
Note that some BinaryTree and TreeView methods use this
bookmark as well, so it is advisable to
use only when doing an independantly managed
tree traversal.
|
| currentRestore | | public void currentRestore()(Code) | | Restore from bookmark a saved "current" position.
Note that some BinaryTree and TreeView methods use this
bookmark as well, so it is advisable to
use only when doing an independantly managed
tree traversal.
|
| cutCurrent | | public BTreeNode cutCurrent(int carry)(Code) | | Cuts current out of tree.
Currently, the cut can only take with it LEFT
or RIGHT - not both.
If carry is LEFT, RIGHT is plugged into the
parent and vica versa.
|
| dumpTree | | public void dumpTree()(Code) | | Debugging aid.
|
| getBinaryDepth | | public int getBinaryDepth()(Code) | | Get the 'current' node's binary depth.
|
| getChild | | public BTreeNode getChild(boolean all)(Code) | | Get the child (right).
Parameters:
all - all or respect visibility |
| getChildPeerCount | | public int getChildPeerCount(boolean all)(Code) | | |
| getLeft | | public BTreeNode getLeft(boolean all)(Code) | | Get the left (next).
Parameters:
all - all or respect visibility |
| getNext | | public BTreeNode getNext(boolean all)(Code) | | Get the next (left).
Parameters:
all - all or respect visibility |
| getPeerCount | | public int getPeerCount(boolean all)(Code) | | |
| getRight | | public BTreeNode getRight(boolean all)(Code) | | Get the right (child).
Parameters:
all - all or respect visibility |
| getSubtreeKeyByValue | | public Object getSubtreeKeyByValue(Object o)(Code) | | Search subtree by value, return key.
Parameters:
o - target |
| getSubtreeValueByKey | | public Object getSubtreeValueByKey(Object o)(Code) | | Search subtree by key, return value.
Parameters:
o - target |
| getTerminalPolicy | | public int getTerminalPolicy()(Code) | | Get the 'current' node's terminal policy.
|
| getTreeKeyByValue | | public Object getTreeKeyByValue(Object o)(Code) | | Search full tree by value, return key.
Parameters:
o - target |
| getTreeValueByKey | | public Object getTreeValueByKey(Object o)(Code) | | Search full tree by key, return value.
Parameters:
o - target |
| getUnaryDepth | | public int getUnaryDepth()(Code) | | Get the 'current' node's unary depth.
|
| getUnaryParent | | public BTreeNode getUnaryParent()(Code) | | Get the unary parent, the parent of a peer set.
If successful, the parent is returned, if it fails,
null is returned and it can be assumed that the
peer set is headed by root and using setToRoot()
might be the next step - this is not done automatically
because it is semantically significantly different.
|
| getVisibility | | public int getVisibility()(Code) | | Get the 'current' node's visibility.
|
| hasMoreElements | | public boolean hasMoreElements()(Code) | | Whether the tree has more elements.
Respect visibility.
|
| hasMoreElements | | public boolean hasMoreElements(boolean all)(Code) | | Whether the tree has more elements.
Parameters:
all - all or respect visibility |
| insertChild | | public BTreeNode insertChild(Object key, Object value, int reposition)(Code) | | Creates a new child and sets current to the new child.
If a child already exists, it is moved to the reposition target
of the new node.
If no root exists, it is automatically created.
If enumeration type is DEPTHFIRSTSORTED, the new node
is inserted in the correct place on this branch at
the next unaryDepth.
Parameters:
key - key
Parameters:
value - value
Parameters:
reposition - where the current child goes on the new node |
| insertChild | | public BTreeNode insertChild(BTreeNode pbtn, int reposition)(Code) | | Creates a new child and sets current to the new child.
If a child already exists, it is moved to the reposition target
of the new node.
If no root exists, it is automatically created.
If enumeration type is DEPTHFIRSTSORTED, the new node
is inserted in the correct place on this branch at
the next unaryDepth.
If the passed node has a parent, it is reset.
SGP: recursion alert - need to check that the node
is not being placed in a subtree of itself.
Parameters:
btn - node
Parameters:
reposition - where the current child goes on the new node |
| insertLeft | | public BTreeNode insertLeft(Object key, Object value, int reposition)(Code) | | Creates a new left and sets current to the new left.
If a left already exists, it is moved to the reposition target
of the new node.
If no root exists, it is automatically created.
If enumeration type is DEPTHFIRSTSORTED, the new node
is inserted in the correct place on this branch at
this unaryDepth.
Parameters:
key - key
Parameters:
value - value
Parameters:
reposition - where the current child goes on the new node |
| insertLeft | | public BTreeNode insertLeft(BTreeNode pbtn, int reposition)(Code) | | Creates a new left and sets current to the new left.
If a left already exists, it is moved to the reposition target
of the new node.
If no root exists, it is automatically created.
If enumeration type is DEPTHFIRSTSORTED, the new node
is inserted in the correct place on this branch at
this unaryDepth.
If the passed node has a parent, it is reset.
SGP: recursion alert - need to check that the node
is not being placed in a subtree of itself.
Parameters:
pbtn - node
Parameters:
reposition - where the current child goes on the new node |
| insertNext | | public BTreeNode insertNext(Object key, Object value, int reposition)(Code) | | Creates a new next and sets current to the new next.
If a next already exists, it is moved to the reposition target
of the new node.
If no root exists, it is automatically created.
If enumeration type is DEPTHFIRSTSORTED, the new node
is inserted in the correct place on this branch at
this unaryDepth.
Parameters:
key - key
Parameters:
value - value
Parameters:
reposition - where the current child goes on the new node |
| insertNext | | public BTreeNode insertNext(BTreeNode pbtn, int reposition)(Code) | | Creates a new next and sets current to the new next.
If a next already exists, it is moved to the reposition target
of the new node.
If no root exists, it is automatically created.
If enumeration type is DEPTHFIRSTSORTED, the new node
is inserted in the correct place on this branch at
this unaryDepth.
If the passed node has a parent, it is reset.
SGP: recursion alert - need to check that the node
is not being placed in a subtree of itself.
Parameters:
pbtn - node
Parameters:
reposition - where the current child goes on the new node |
| insertRight | | public BTreeNode insertRight(Object key, Object value, int reposition)(Code) | | Creates a new right and sets current to the new right.
If a right already exists, it is moved to the reposition target
of the new node.
If no root exists, it is automatically created.
If enumeration type is DEPTHFIRSTSORTED, the new node
is inserted in the correct place on this branch at
the next unaryDepth and a reposition value of RIGHT
is rejected as an error.
Parameters:
key - key
Parameters:
value - value
Parameters:
reposition - where the current child goes on the new node
exception:
IllegalArgumentException - if not passed a legal type |
| insertRight | | public BTreeNode insertRight(BTreeNode pbtn, int reposition)(Code) | | Creates a new right and sets current to the new right.
If a right already exists, it is moved to the reposition target
of the new node.
If no root exists, it is automatically created.
If enumeration type is DEPTHFIRSTSORTED, the new node
is inserted in the correct place on this branch at
the next unaryDepth and a reposition value of RIGHT
is rejected as an error.
If the passed node has a parent, it is reset.
SGP: recursion alert - need to check that the node
is not being placed in a subtree of itself.
Parameters:
btn - node
Parameters:
reposition - where the current child goes on the new node |
| isEmpty | | public boolean isEmpty()(Code) | | Whether or not the tree contains any data.
|
| keyIsDepthFirstSorted | | public boolean keyIsDepthFirstSorted()(Code) | | Verify that the keys in the tree conform to
the rules governing DEPTHFIRSTSORTED.
Keys must be Strings and must be in String.compareTo() valid
sort order.
Called automatically by setEnumerationType().
SGP: not done!
|
| nextElement | | public Object nextElement()(Code) | | Return the next element in the tree.
Respect visibility.
|
| nextElement | | public Object nextElement(boolean all)(Code) | | Return the next element in the tree.
Parameters:
all - all or respect visibility |
| nullifyCurrent | | public void nullifyCurrent()(Code) | | Effectively dereferences the current node, causing
current to point at the doomed node's parent.
May be redundant to cutCurrent().
|
| resetEnumeration | | public void resetEnumeration()(Code) | | Enumeration doesn't have to be a one way street.
Set the current pointer to root.
|
| setEnumeration | | public void setEnumeration(BTreeNode node) throws IllegalArgumentException(Code) | | Enumeration doesn't even have to be a street.
Set the current pointer to passed node after verifying
that it's in this tree.
Parameters:
node - new current node
exception:
IllegalArgumentException - if not passed a legal type |
| setEnumerationType | | public void setEnumerationType(int enumerationType) throws IllegalArgumentException(Code) | | Set enumeration type.
If the new type is DEPTHFIRSTSORTED,
it is the responsibility of the caller to
call keyIsDepthFirstSorted() to verify that
the enumeration is in that form.
The reason for this is so that the
sorting capability can be turned on and off
for performance reasons, since verification
is potentially costly.
Parameters:
enumerationType - enumeration type
exception:
IllegalArgumentException - if not passed a legal type |
| setKey | | public boolean setKey(Object key)(Code) | | Sets the key.
If the enumeration is DEPTHFIRSTSORTED, it also sorts the peer group.
|
| setSafeEnumerationType | | public boolean setSafeEnumerationType(int enumerationType, boolean resetRoot) throws IllegalArgumentException(Code) | | Safely set enumeration type. If resetRoot is true, then
the current pointer is reset to root. If resetRoot is false,
then the operation fails if current is not equal to root.
in either case, if the operation fails false is returned
otherwise true is returned.
Parameters:
enumerationType - enumeration type
Parameters:
resetRoot - force reset to root or fail
exception:
IllegalArgumentException - if not passed a legal type |
| setSubtreeNodeByKey | | public boolean setSubtreeNodeByKey(Object o)(Code) | | Search subtree by key, set current to result
and return true if found.
|
| setSubtreeNodeByValue | | public boolean setSubtreeNodeByValue(Object o)(Code) | | Search subtree by value, set current to result
and return true if found.
|
| setToChild | | public boolean setToChild()(Code) | | Set current position in tree to the child (right) of the current position.
|
| setToLeft | | public boolean setToLeft()(Code) | | Set current position in tree to the left (next) of the current position.
|
| setToNext | | public boolean setToNext()(Code) | | Set current position in tree to the next (left) of the current position.
|
| setToParent | | public boolean setToParent()(Code) | | Set current position in tree to the parent of the current position.
|
| setToRight | | public boolean setToRight()(Code) | | Set current position in tree to the right (child) of the current position.
|
| setToRoot | | public void setToRoot()(Code) | | Set current position in tree to the root of the tree.
|
| setToUnaryParent | | public boolean setToUnaryParent()(Code) | | Set to the unary parent, to the parent of a peer set.
If successful, true is returned, if it fails, the
peer set is headed by root and using setToRoot()
might be the next step - this is not done automatically
because it is semantically significantly different.
|
| setTreeNodeByKey | | public boolean setTreeNodeByKey(Object o)(Code) | | Search full tree by key, set current to result
and return true if found.
|
| setTreeNodeByValue | | public boolean setTreeNodeByValue(Object o)(Code) | | Search full tree by value, set current to result
and return true if found.
|
| setValue | | public void setValue(Object value)(Code) | | Set the value.
Parameters:
value - the value in question |
| setVisibility | | public void setVisibility(int visibility)(Code) | | Set the visibility.
|
| toStringTree | | public String toStringTree()(Code) | | Debugging aid.
|
|
|