|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--gishur.core.BasicTree
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.
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 |
protected static final byte NO_ACCESS
protected static final byte ANY_ACCESS
protected static final byte TREEITEM
TreeItem
-object.protected static final byte KEY
protected static final byte VALUE
public static final byte CHILDS_ROOT_ORDER
public static final byte ROOT_CHILDS_ORDER
public static final byte LEFT_ROOT_RIGHT_ORDER
public static final byte LEFT_RIGHT_ROOT_ORDER
public static final byte ROOT_LEFT_RIGHT_ORDER
protected byte _access
Constructor Detail |
protected BasicTree()
Method Detail |
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)
item2string
- if true
, the TreeItems
will be converted into strings,
otherwise only the keys or key-value-pairs will be convertedpreline
- the beginning of any linesepl
- 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 childpublic java.lang.String toString()
Object.toString()
.toString
in class java.lang.Object
Object.toString()
protected java.lang.Object clone(java.util.Hashtable h, int level)
ControlledCloneable
. That means,
all TreeItems
are cloned and connected proper.level
see alsoh
- Hashtable to indicate which objects are already clonedlevel
- indicates how deep the objects should be clonedInternalError
- - if the Object could not be cloned properlyControlledCloneable
protected int length()
protected boolean empty()
true
if the tree is empty.true
, if tree is emptyprotected boolean contains(TreeItem node)
TreeItem
node
is part of the tree.
The test is completed in constant time.node
- the TreeItem
-object to be testedtrue
, if node
is part of this treeprotected TreeItem root()
protected int height(TreeItem root)
root
. The computation needs linear time!root
- the root of the partial tree to be examinedprotected TreeItem findLast(TreeItem root, int pos)
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.root
- the root of the partial tree to be examinedTreeItem
which has the farest left position
in the partial tree with root root
protected int countItems(TreeItem root)
TreeItems
in the partial tree with
root root
.root
- the root of the partial tree to be examinedprotected TreeItem find(java.lang.Object key, TreeItem start)
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.key
- key to be searched forstart
- the root of the partial tree to search inTreeItem
with matching key or null
, if no such
TreeItem
has been foundprotected TreeItem find(java.lang.Object key, TreeItem start, Comparitor comparitor, boolean left_is_smaller)
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.key
- key to search forstart
- root node for the partial tree to search incomparitor
- Object of type Comparitor
which performs the comparisons
between to nodesleft_is_smaller
- defines the behaviour of the method for the case that
key
is smaller than the actual nodeTreeItem
, for which EQUAL
was returned in a comparison
or whose key is most similar to key
protected TreeItem first(TreeItem root, byte order)
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.root
- root of the partial tree to move throughorder
- a constant for tree-traversals (ROOT_CHILDS_ORDER
,
CHILDS_ROOT_ORDER
, LEFT_ROOT_RIGHT_ORDER
, LEFT_RIGHT_ROOT_ORDER
or ROOT_LEFT_RIGHT_ORDER
)protected TreeItem last(TreeItem root, byte order)
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.root
- root of the partial tree to move throughorder
- a constant for tree-traversals (ROOT_CHILDS_ORDER
,
CHILDS_ROOT_ORDER
, LEFT_ROOT_RIGHT_ORDER
, LEFT_RIGHT_ROOT_ORDER
or ROOT_LEFT_RIGHT_ORDER
)protected TreeItem next(TreeItem root, TreeItem i, byte order)
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.root
- root of the tree to move throughi
- TreeItem
whose following item shall be returnedorder
- a constant for tree-traversals (ROOT_CHILDS_ORDER
,
CHILDS_ROOT_ORDER
, LEFT_ROOT_RIGHT_ORDER
, LEFT_RIGHT_ROOT_ORDER
or ROOT_LEFT_RIGHT_ORDER
)protected TreeItem prev(TreeItem root, TreeItem i, byte order)
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.root
- root of the partial tree to move throughi
- TreeItem
for which the previous item shall be returnedorder
- a constant for tree-traversals (ROOT_CHILDS_ORDER
,
CHILDS_ROOT_ORDER
, LEFT_ROOT_RIGHT_ORDER
, LEFT_RIGHT_ROOT_ORDER
or ROOT_LEFT_RIGHT_ORDER
)protected int storeInArray(java.lang.Object[] array, int startindex, int length, TreeItem root, byte order, byte objecttype)
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.array
- array to save intostartindex
- index, from which the partial tree shall be saved into array
length
- maximal length of the interval into which the tree shall be savedroot
- root-node of the partial tree to be savedorder
- 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
)protected ListItem getListItemChain(TreeItem root, byte order)
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.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
)ListItem
(which is the conversion of
the result of first(root,order)
) of the created chainprotected TreeItem copy(TreeItem start, java.util.Hashtable h, int level)
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.start
- root of the subtree to be copiedh
- Hashtable to indicate which objects are already clonedlevel
- indicates how deep the objects should be clonedControlledCloneable
protected java.util.Enumeration enumerate(TreeItem root, byte order, boolean forward, byte objecttype)
root
constructing an Enumeration-object.root
- the root of the partial tree to be enumerated or null
if the whole tree shall be enumeratedorder
- 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 otherwiseobjecttype
- type of object to be returned (TREEITEM
, KEY
oder VALUE
)Enumeration
-object enabeling the traversalprotected java.util.Enumeration enumerate(TreeItem start, TreeItem end, byte order, byte objecttype)
start
to end
constructing an Enumeration
-object.start
- TreeItem
at the beginning of the intervalend
- TreeItem
at the end of the intervalorder
- 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
)Enumeration
-object which enables the requested traversalprotected java.util.Enumeration emptyEnumeration()
Enumeration
.Enumeration
-objectprotected TreeItem ownTree(TreeItem root, Owner owner, java.util.Hashtable h, int level)
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
!root
- the root of the partial tree whose owner shall be changedh
- Hashtable to indicate which objects are already clonedlevel
- indicates how deep the objects should be clonedControlledCloneable
protected TreeItem ownTree(TreeItem root, Owner owner)
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
!root
- the root of the partial tree whose owner shall be changedprotected TreeItem add(TreeItem n, TreeItem base, int pos)
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.n
- new TreeItem
to insertbase
- position in the tree where the insertion shall take placepos
- n
will be child no. pos
for base
n
, if n is inserted or null
, if n==null
protected int connect(TreeItem n, TreeItem base, int pos)
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.n
- root-node of the partial tree to insertbase
- position in the tree where the insertion shall take placepos
- n
will be inserted as child no. pos
for base
TreeItems
inserted into the treeprotected TreeItem add(TreeItem n, Comparitor comparitor, boolean left_is_smaller, boolean allow_duplicates)
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).n
- TreeItem
to insertcomparitor
- 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 keysTreeItem
protected int cutTree(TreeItem root)
root
from
the tree and returns the total number of removed elements.
If root==null
, the whole tree is cut.root
- the root-node of the partial tree to be cut offprotected int removeTree(TreeItem 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.root
- the root-node of the partial tree to be removedTreeItems
protected TreeItem getRemovableTreeItem(TreeItem i)
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).i
- TreeItem
to be removedTreeItem
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).v
- node which should take the place of u
u
- node to be removedu
protected TreeItem removeSym(TreeItem i)
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.i
- TreeItem
to be removedTreeItem
protected TreeItem rotation(TreeItem u, int pos1, int pos2)
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
andpos2==TreeItem.RIGHT
u
- node to be rotated with child at pos1
pos1
- position of the node to be rotated to u
's positionpos2
- position, to which u
shall be attached as child of v
TreeItem
which has taken u
's positionpublic TreeItem double_rotation(TreeItem u, int pos1, int pos2)
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
andpos2==TreeItem.RIGHT
u
- node, at which the rotation shall take placepos1
- 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
TreeItem
which has taken the place of u
(that means x
)protected void allowAccess(byte accesskonst)
ListItems
public boolean requestAccess(int accesstype, java.lang.Object who, java.lang.Object argument)
Owner
for permission to perform an
action of the type specified by accesstype
with argument
argument
.requestAccess
in interface Owner
accesstype
- type of action (type of access)who
- object which asks for permissionargument
- argument of the action who
wants to performtrue
if the owner gives the asked permission, false
otherwise
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |