gishur.core
Class BasicTree

java.lang.Object
  |
  +--gishur.core.BasicTree
All Implemented Interfaces:
Owner, java.io.Serializable
Direct Known Subclasses:
BinarySearchTree

public class BasicTree
extends java.lang.Object
implements Owner, java.io.Serializable

Fundamental methods for trees. This class should be used as a basis for further tree-classes. A BasicTree only contains a reference to the root-node and the number of stored elements. Although BasicTree implements Serializable, Treeitem doesn't. If you want to derive a list which works correct with serialization, pay attention to use treeitems which implement the Serializable interface.

Version:
1.0
Author:
Thomas Wolf
See Also:
Serialized Form

Field Summary
protected  byte _access
          A variable which makes it possible to allow acces to nodes temporarily.
protected static byte ANY_ACCESS
          Allow any access.
static byte CHILDS_ROOT_ORDER
          All children at first, then the root.
protected static byte KEY
          Access to the key.
static byte LEFT_RIGHT_ROOT_ORDER
          Left-right-root (only works correctly with binary trees).
static byte LEFT_ROOT_RIGHT_ORDER
          Left-root-right (only works correctly with binary trees).
protected static byte NO_ACCESS
          Does not allow any access (by default), where 'access' means access to the enchainment.
static byte ROOT_CHILDS_ORDER
          The root at first, then the children.
static byte ROOT_LEFT_RIGHT_ORDER
          Root-left-right (only works correctly with binary trees).
protected static byte TREEITEM
          Access to the TreeItem-object.
protected static byte VALUE
          Access to the value.
 
Constructor Summary
protected BasicTree()
          A protected constructor.
 
Method Summary
protected  TreeItem add(TreeItem n, Comparitor comparitor, boolean left_is_smaller, boolean allow_duplicates)
          The add-method for binary search trees.
protected  TreeItem add(TreeItem n, TreeItem base, int pos)
          Inserts TreeItem n as child no.
protected  void allowAccess(byte accesskonst)
          Allows the temporary acces to ListItems
protected  java.lang.Object clone(java.util.Hashtable h, int level)
          Clones the entire tree according to ControlledCloneable.
protected  int connect(TreeItem n, TreeItem base, int pos)
          Connects a partial tree with root root as child no.
protected  boolean contains(TreeItem node)
          Returns true if the TreeItem node is part of the tree.
protected  TreeItem copy(TreeItem start, java.util.Hashtable h, int level)
          Returns a copy of the tree/subtree beginning with TreeItem start as root.
protected  int countItems(TreeItem root)
          Counts the TreeItems in the partial tree with root root.
protected  int cutTree(TreeItem root)
          Cuts the the partial tree which starts with root from the tree and returns the total number of removed elements.
 TreeItem double_rotation(TreeItem u, int pos1, int pos2)
          A double rotation.
protected  boolean empty()
          Returns true if the tree is empty.
protected  java.util.Enumeration emptyEnumeration()
          Returns an empty Enumeration.
protected  java.util.Enumeration enumerate(TreeItem root, byte order, boolean forward, byte objecttype)
          Enumerates all objects in the partial tree with root root constructing an Enumeration-object.
protected  java.util.Enumeration enumerate(TreeItem start, TreeItem end, byte order, byte objecttype)
          Enumerates all objects in the interval from start to end constructing an Enumeration-object.
protected  TreeItem find(java.lang.Object key, TreeItem start)
          Searches for a TreeItem whose equals(Object)-method returns true with argument key.
protected  TreeItem find(java.lang.Object key, TreeItem start, Comparitor comparitor, boolean left_is_smaller)
          Searches in the partial tree with root root for a TreeItem whose key is most similar to key, using the Comparitor comparitor.
protected  TreeItem findLast(TreeItem root, int pos)
          Returns the last element in the sequence root-root.child(pos)-root.child(pos).child(pos)... and so on.
protected  TreeItem first(TreeItem root, byte order)
          Returns the first TreeItem in the partial tree with root root referring to the traversal-order defined by order.
protected  TreeItem fitInPlace(TreeItem v, TreeItem u)
          TreeItem v takes the place of u (and his balance data).
protected  ListItem getListItemChain(TreeItem root, byte order)
          Turns the partial tree with root root into a chain of ListItems.
protected  TreeItem getRemovableTreeItem(TreeItem i)
          Returns a removable TreeItem in the binary search tree belonging to TreeItem i.
protected  java.lang.String getTreeString(boolean item2string, java.lang.String preline, java.lang.String sepl, java.lang.String sepsp, java.lang.String cmul, java.lang.String csing)
           
protected  int height(TreeItem root)
          Calculates the height of the partial tree with root root.
protected  TreeItem last(TreeItem root, byte order)
          Returns the last TreeItem in the partial tree with root root referring to the traversal-order defined by order.
protected  int length()
          Returns the number of stored elements in the tree.
protected  TreeItem next(TreeItem root, TreeItem i, byte order)
          Returns the next TreeItem in the partial tree with root root referring to the traversal-order defined by order.
protected  TreeItem ownTree(TreeItem root, Owner owner)
          The owner of the partial tree with root root is set to owner.
protected  TreeItem ownTree(TreeItem root, Owner owner, java.util.Hashtable h, int level)
          The owner of the partial tree with root root is set to owner.
protected  TreeItem prev(TreeItem root, TreeItem i, byte order)
          Returns the previous TreeItem in the partial tree with root root referring to the traversal-order defined by order.
protected  TreeItem removeSym(TreeItem i)
          Removes the TreeItem i symmetrically from the tree.
protected  int removeTree(TreeItem root)
          Removes the partial tree with root root from the tree and returns the total number of removed TreeItems.
 boolean requestAccess(int accesstype, java.lang.Object who, java.lang.Object argument)
          The owned object asks the Owner for permission to perform an action of the type specified by accesstype with argument argument.
protected  TreeItem root()
          Returns a reference to the root of this tree.
protected  TreeItem rotation(TreeItem u, int pos1, int pos2)
          A simple rotation.
protected  int storeInArray(java.lang.Object[] array, int startindex, int length, TreeItem root, byte order, byte objecttype)
          Saves the partial tree with root root into array, starting at position startindex and maximally writing into length elements of the array.
 java.lang.String toString()
          Overrides Object.toString().
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

NO_ACCESS

protected static final byte NO_ACCESS
Does not allow any access (by default), where 'access' means access to the enchainment.

ANY_ACCESS

protected static final byte ANY_ACCESS
Allow any access.

TREEITEM

protected static final byte TREEITEM
Access to the TreeItem-object.

KEY

protected static final byte KEY
Access to the key.

VALUE

protected static final byte VALUE
Access to the value.

CHILDS_ROOT_ORDER

public static final byte CHILDS_ROOT_ORDER
All children at first, then the root.

ROOT_CHILDS_ORDER

public static final byte ROOT_CHILDS_ORDER
The root at first, then the children.

LEFT_ROOT_RIGHT_ORDER

public static final byte LEFT_ROOT_RIGHT_ORDER
Left-root-right (only works correctly with binary trees).

LEFT_RIGHT_ROOT_ORDER

public static final byte LEFT_RIGHT_ROOT_ORDER
Left-right-root (only works correctly with binary trees).

ROOT_LEFT_RIGHT_ORDER

public static final byte ROOT_LEFT_RIGHT_ORDER
Root-left-right (only works correctly with binary trees).

_access

protected byte _access
A variable which makes it possible to allow acces to nodes temporarily.
Constructor Detail

BasicTree

protected BasicTree()
A protected constructor.
Method Detail

getTreeString

protected java.lang.String getTreeString(boolean item2string,
                                         java.lang.String preline,
                                         java.lang.String sepl,
                                         java.lang.String sepsp,
                                         java.lang.String cmul,
                                         java.lang.String csing)
Parameters:
item2string - if true, the TreeItems will be converted into strings, otherwise only the keys or key-value-pairs will be converted
preline - the beginning of any line
sepl - string for an upright line (to the next child)
sepsp - string for a gap (no next child)
cmul - string for a branch to a child (but not to the last)
csing - string for a branch to the last child

toString

public java.lang.String toString()
Overrides Object.toString().
Overrides:
toString in class java.lang.Object
See Also:
Object.toString()

clone

protected java.lang.Object clone(java.util.Hashtable h,
                                 int level)
Clones the entire tree according to ControlledCloneable. That means, all TreeItems are cloned and connected proper.
For further details about level see also
Parameters:
h - Hashtable to indicate which objects are already cloned
level - indicates how deep the objects should be cloned
Returns:
cloned object
Throws:
InternalError - - if the Object could not be cloned properly
See Also:
ControlledCloneable

length

protected int length()
Returns the number of stored elements in the tree.
Returns:
number of elements

empty

protected boolean empty()
Returns true if the tree is empty.
Returns:
true, if tree is empty

contains

protected boolean contains(TreeItem node)
Returns true if the TreeItem node is part of the tree. The test is completed in constant time.
Parameters:
node - the TreeItem-object to be tested
Returns:
true, if node is part of this tree

root

protected TreeItem root()
Returns a reference to the root of this tree.
Returns:
the root

height

protected int height(TreeItem root)
Calculates the height of the partial tree with root root. The computation needs linear time!
Parameters:
root - the root of the partial tree to be examined
Returns:
the height of the partial tree

findLast

protected TreeItem findLast(TreeItem root,
                            int pos)
Returns the last element in the sequence root-root.child(pos)-root.child(pos).child(pos)... and so on. If root==null, root is set to the root of the tree. It is possible that this function returns correct results, even if root is part of another tree, although this case should be avoided.
Parameters:
root - the root of the partial tree to be examined
Returns:
the TreeItem which has the farest left position in the partial tree with root root

countItems

protected int countItems(TreeItem root)
Counts the TreeItems in the partial tree with root root.
Parameters:
root - the root of the partial tree to be examined
Returns:
number of elements in this partial tree

find

protected TreeItem find(java.lang.Object key,
                        TreeItem start)
Searches for a TreeItem whose equals(Object)-method returns true with argument key. start is the root for the partial tree to search in. The computation takes O(n) time! If start==null, start=root() is performed. If start is not part of the tree or no TreeItem matching key has been found, null is returned.
Parameters:
key - key to be searched for
start - the root of the partial tree to search in
Returns:
TreeItem with matching key or null, if no such TreeItem has been found

find

protected TreeItem find(java.lang.Object key,
                        TreeItem start,
                        Comparitor comparitor,
                        boolean left_is_smaller)
Searches in the partial tree with root root for a TreeItem whose key is most similar to key, using the Comparitor comparitor. This method only returns senseful results if the tree is a binary search tree. If start==null, start=root() will be performed. If start is not part of the tree, null will be returned. If left_is_smaller is set to true, the search will be continued in the left partial tree while key is smaller than the actual node.
Parameters:
key - key to search for
start - root node for the partial tree to search in
comparitor - Object of type Comparitor which performs the comparisons between to nodes
left_is_smaller - defines the behaviour of the method for the case that key is smaller than the actual node
Returns:
TreeItem, for which EQUAL was returned in a comparison or whose key is most similar to key

first

protected TreeItem first(TreeItem root,
                         byte order)
Returns the first TreeItem in the partial tree with root root referring to the traversal-order defined by order. This method also works for partial trees which are not part of the actual tree.
Parameters:
root - root of the partial tree to move through
order - a constant for tree-traversals (ROOT_CHILDS_ORDER, CHILDS_ROOT_ORDER, LEFT_ROOT_RIGHT_ORDER, LEFT_RIGHT_ROOT_ORDER or ROOT_LEFT_RIGHT_ORDER)

last

protected TreeItem last(TreeItem root,
                        byte order)
Returns the last TreeItem in the partial tree with root root referring to the traversal-order defined by order. This method also works with partial trees which are not part of the actual tree.
Parameters:
root - root of the partial tree to move through
order - a constant for tree-traversals (ROOT_CHILDS_ORDER, CHILDS_ROOT_ORDER, LEFT_ROOT_RIGHT_ORDER, LEFT_RIGHT_ROOT_ORDER or ROOT_LEFT_RIGHT_ORDER)

next

protected TreeItem next(TreeItem root,
                        TreeItem i,
                        byte order)
Returns the next TreeItem in the partial tree with root root referring to the traversal-order defined by order. This method also works with partial trees which are not part of the actual tree.
Parameters:
root - root of the tree to move through
i - TreeItem whose following item shall be returned
order - a constant for tree-traversals (ROOT_CHILDS_ORDER, CHILDS_ROOT_ORDER, LEFT_ROOT_RIGHT_ORDER, LEFT_RIGHT_ROOT_ORDER or ROOT_LEFT_RIGHT_ORDER)

prev

protected TreeItem prev(TreeItem root,
                        TreeItem i,
                        byte order)
Returns the previous TreeItem in the partial tree with root root referring to the traversal-order defined by order. This method also works with partial trees whitch are not part of the actual tree.
Parameters:
root - root of the partial tree to move through
i - TreeItem for which the previous item shall be returned
order - a constant for tree-traversals (ROOT_CHILDS_ORDER, CHILDS_ROOT_ORDER, LEFT_ROOT_RIGHT_ORDER, LEFT_RIGHT_ROOT_ORDER or ROOT_LEFT_RIGHT_ORDER)

storeInArray

protected int storeInArray(java.lang.Object[] array,
                           int startindex,
                           int length,
                           TreeItem root,
                           byte order,
                           byte objecttype)
Saves the partial tree with root root into array, starting at position startindex and maximally writing into length elements of the array. The number of written elements is the return-value. The variable objecttype defines whether TreeItems or keys or values shall be saved. If root==null, root==root() is performed.
Parameters:
array - array to save into
startindex - index, from which the partial tree shall be saved into array
length - maximal length of the interval into which the tree shall be saved
root - root-node of the partial tree to be saved
order - a tree-traversal constant which defines the order in which the tree is saved into array
objecttype - type of object to be saved (TREEITEM, KEY or VALUE)
Returns:
the number of saved objects

getListItemChain

protected ListItem getListItemChain(TreeItem root,
                                    byte order)
Turns the partial tree with root root into a chain of ListItems. The traversal-order to be used in this operation is defined by order. If the method encounters a TreeItem which is also a ListItem (that means that it implements the interface ListItem), it is tried to set the owning list to null and to connect this ListItem into the chain. If the owning list denies access, the ListItem is (flat)cloned and it is tried to set its owning list to null. If even this fails, a new StdListItem is created containing the key and the value of the old one.
Parameters:
root - the root-node of the partial tree to be converted into a chain of ListItems
order - a tree-traversal constant (ROOT_CHILDS_ORDER, CHILDS_ROOT_ORDER, LEFT_ROOT_RIGHT_ORDER, LEFT_RIGHT_ROOT_ORDER or ROOT_LEFT_RIGHT_ORDER)
Returns:
the heading ListItem (which is the conversion of the result of first(root,order)) of the created chain

copy

protected TreeItem copy(TreeItem start,
                        java.util.Hashtable h,
                        int level)
Returns a copy of the tree/subtree beginning with TreeItem start as root. If start==null, the entire tree will be copied. The new tree/subtree has no owner. The dataobjects of the tree are cloned according to ControlledCloneable. That means, that all TreeItems are cloned and connected proper.
Parameters:
start - root of the subtree to be copied
h - Hashtable to indicate which objects are already cloned
level - indicates how deep the objects should be cloned
Returns:
root of the new tree/subtree
See Also:
ControlledCloneable

enumerate

protected java.util.Enumeration enumerate(TreeItem root,
                                          byte order,
                                          boolean forward,
                                          byte objecttype)
Enumerates all objects in the partial tree with root root constructing an Enumeration-object.
Parameters:
root - the root of the partial tree to be enumerated or null if the whole tree shall be enumerated
order - a traversal-order constant (ROOT_CHILDS_ORDER, CHILDS_ROOT_ORDER, LEFT_ROOT_RIGHT_ORDER, LEFT_RIGHT_ROOT_ORDER or ROOT_LEFT_RIGHT_ORDER)
forward - the direction to process enumeration: forward, if true, backward otherwise
objecttype - type of object to be returned (TREEITEM, KEY oder VALUE)
Returns:
an Enumeration-object enabeling the traversal

enumerate

protected java.util.Enumeration enumerate(TreeItem start,
                                          TreeItem end,
                                          byte order,
                                          byte objecttype)
Enumerates all objects in the interval from start to end constructing an Enumeration-object.
Parameters:
start - TreeItem at the beginning of the interval
end - TreeItem at the end of the interval
order - a traversal-order constant (ROOT_CHILDS_ORDER, CHILDS_ROOT_ORDER, LEFT_ROOT_RIGHT_ORDER, LEFT_RIGHT_ROOT_ORDER or ROOT_LEFT_RIGHT_ORDER)
objecttype - type of object to be returned (TREEITEM, KEY oder VALUE)
Returns:
Enumeration-object which enables the requested traversal

emptyEnumeration

protected java.util.Enumeration emptyEnumeration()
Returns an empty Enumeration.
Returns:
Enumeration-object

ownTree

protected TreeItem ownTree(TreeItem root,
                           Owner owner,
                           java.util.Hashtable h,
                           int level)
The owner of the partial tree with root root is set to owner. If this is not possible, the TreeItems will be cloned according to h, level in method {link TreeItem#clone(Hashtable, int)} in TreeItem and the clones' owner will be set to owner. It is allowed that owner==this !
Parameters:
root - the root of the partial tree whose owner shall be changed
h - Hashtable to indicate which objects are already cloned
level - indicates how deep the objects should be cloned
Returns:
the possibly cloned root-node of the acquired partial tree
See Also:
ControlledCloneable

ownTree

protected TreeItem ownTree(TreeItem root,
                           Owner owner)
The owner of the partial tree with root root is set to owner. If this is not possible, the TreeItems will be cloned (flat) and the clones' owner will be set to owner. It is allowed that owner==this !
Parameters:
root - the root of the partial tree whose owner shall be changed
Returns:
the possibly cloned root-node of the acquired partial tree

add

protected TreeItem add(TreeItem n,
                       TreeItem base,
                       int pos)
Inserts TreeItem n as child no. pos of base. If this tree does not own n, it will be tried to change the owner or otherwise the TreeItem will be cloned. base should be a member of the tree or base==null should be true, in this case n is inserted as the root and the tree becomes child no. pos of the new root.
Parameters:
n - new TreeItem to insert
base - position in the tree where the insertion shall take place
pos - n will be child no. pos for base
Returns:
n, if n is inserted or null, if n==null

connect

protected int connect(TreeItem n,
                      TreeItem base,
                      int pos)
Connects a partial tree with root root as child no. pos to node base and returns the number of elements inserted into the tree by this operation. The TreeItems attached to n as well as base should be members of the tree, otherwise a LinkException is thrown. If base==null, n will be inserted before the root (as the new root, of course). If base has already a child at position pos, the partial tree attached to position pos will be attached to the first node in the inserted tree whose child no. pos is null. When n is inserted as new root, the old tree is inserted into the partial tree of n in the same way.
Parameters:
n - root-node of the partial tree to insert
base - position in the tree where the insertion shall take place
pos - n will be inserted as child no. pos for base
Returns:
number of TreeItems inserted into the tree

add

protected TreeItem add(TreeItem n,
                       Comparitor comparitor,
                       boolean left_is_smaller,
                       boolean allow_duplicates)
The add-method for binary search trees. n is inserted at the right position using the Comparitor comparitor. left_is_smaller==true means that smaller values are stored in the left partial trees. If allow_duplicates is true, it is allowed to insert a node whose key already exists in the tree. This will be inserted into the partial tree with smaller values. If, on the other hand, allow_duplicates is false, the old TreeItem will be overwritten by the new one if both have equal keys. (In this case, they both should have the same maximal rank).
Parameters:
n - TreeItem to insert
comparitor - the Comparitor used to compare the TreeItems
left_is_smaller - defines, whether smaller (<=) values can be found in the left (true) or in the right (false) partial tree.
allow_duplicates - allows (true) or disallows (false) the insertion of TreeItems with equal keys
Returns:
the inserted TreeItem

cutTree

protected int cutTree(TreeItem root)
Cuts the the partial tree which starts with root from the tree and returns the total number of removed elements. If root==null, the whole tree is cut.
Parameters:
root - the root-node of the partial tree to be cut off
Returns:
number of elements removed from the tree be this cut operation

removeTree

protected int removeTree(TreeItem root)
Removes the partial tree with root root from the tree and returns the total number of removed TreeItems. The removed TreeItems are not connected with each other after the removal.
Parameters:
root - the root-node of the partial tree to be removed
Returns:
number of removed TreeItems

getRemovableTreeItem

protected TreeItem getRemovableTreeItem(TreeItem i)
Returns a removable TreeItem in the binary search tree belonging to TreeItem i. A TreeItem can only be removed correctly, if it has maximally one child-node. If this condition is fulfilled, i will be returned, otherwise a symmetric neighbour, which could be removed (in better words: which could take i's place).
Parameters:
i - TreeItem to be removed
Returns:
removable TreeItem

fitInPlace

protected TreeItem fitInPlace(TreeItem v,
                              TreeItem u)
TreeItem v takes the place of u (and his balance data). v and u must be part of the tree and v must be removable (that means v.rank()<2) If v has a child-node, this will be connected to his father (thus v is removed correctly).
Parameters:
v - node which should take the place of u
u - node to be removed
Returns:
reference to u

removeSym

protected TreeItem removeSym(TreeItem i)
Removes the TreeItem i symmetrically from the tree. This method may only be used on binary trees ! If i has two sons, it is replaced by the symmetrically following TreeItem (LEFT_ROOT_RIGHT_ORDER). Thus the order in a binary search tree won't be disturbed by the operation.
Parameters:
i - TreeItem to be removed
Returns:
removed TreeItem

rotation

protected TreeItem rotation(TreeItem u,
                            int pos1,
                            int pos2)
A simple rotation. Child no. pos1 of u (=:v) takes the position of u in the tree by connecting u to child-position pos2 of v and connecting the partial tree former attached to pos2 of v to pos1 of u. Rotations are normally used to balance binary trees:
 
     u               v
   v   T3    =>    T1   u
 T1 T2                T2 T3
 (in this special case, pos1==TreeItem.LEFT and 
 pos2==TreeItem.RIGHT
Parameters:
u - node to be rotated with child at pos1
pos1 - position of the node to be rotated to u's position
pos2 - position, to which u shall be attached as child of v
Returns:
the TreeItem which has taken u's position

double_rotation

public TreeItem double_rotation(TreeItem u,
                                int pos1,
                                int pos2)
A double rotation. The three nodes u, v:=u.child(pos1) and x:=v.child(pos2) are rotated in a way that x takes the position of u and u will be attached to pos2 and v to pos1 of x. Normally, the double rotation is used to balance binary trees:
     u                  x
   v    T3    =>     v     u
 T1   x            T1 T2 T4 T3
    T2 T4
 (in this case, pos1==TreeItem.LEFT and pos2==TreeItem.RIGHT
Parameters:
u - node, at which the rotation shall take place
pos1 - position, at which v is attached to u and after the rotation to x
pos2 - position, at which x is attached to v and at which after the rotation u is connected to x
Returns:
the TreeItem which has taken the place of u (that means x)

allowAccess

protected void allowAccess(byte accesskonst)
Allows the temporary acces to ListItems

requestAccess

public boolean requestAccess(int accesstype,
                             java.lang.Object who,
                             java.lang.Object argument)
The owned object asks the Owner for permission to perform an action of the type specified by accesstype with argument argument.
Specified by:
requestAccess in interface Owner
Parameters:
accesstype - type of action (type of access)
who - object which asks for permission
argument - argument of the action who wants to perform
Returns:
true if the owner gives the asked permission, false otherwise