gishur.core
Interface TreeItem

All Superinterfaces:
KeyValueHolder
All Known Implementing Classes:
BasicTreeItem

public interface TreeItem
extends KeyValueHolder

The basic interface for tree nodes. Each tree item class implementing this interface inherits methods the for access to a key and a value-object from interface KeyValueHolder, which is a superinterface of TreeItem. Besides, methods are declared for setting and getting the TreeItem's Owner as well as for access to child-nodes and the parent-node (like child(int), sibling() or parent()). It is possible to check a TreeItem if it is a leaf, i.e. it has no child-nodes, or if it is an inner node (having children). Finally there are methods for setting and getting the maximal rank (the maximal number of children) and for the connection to other TreeItems.
Although BasicTree, etc. implements Serializable, TreeItem doesn't. Thus you can avoid serialization from list's using TreeItems not implementing Serializable. Take care not to forget to implement Serializable, if you need to.

Version:
1.0
Author:
Thomas Wolf

Field Summary
static int CLEAR_CONNECTIONS
          Clear all connections.
static int CONNECT
          Connection to a child node.
static int CONNECT_PARENT
          Connection to parent node.
static int LAST_CHILD
          Last child node.
static int LEFT
          Left child node.
static int PARENT
          Parent node.
static int REMOVE
          Remove this object from the structure.
static int RIGHT
          Rigth child node.
static int SET_BALANCE
          Setting balance data.
static int SET_MAX_RANK
          Setting the maximal rank (the maximal number of child nodes).
static int SET_OWNER
          The Owner shall be set.
static int UNKNOWN
          Unknown element.
 
Fields inherited from interface gishur.core.KeyValueHolder
SET_KEY, SET_VALUE
 
Method Summary
 boolean answerConnect(TreeItem node, int pos)
          Completes the connection process and should thus only be called by connect(TreeItem, int).
 byte balance()
          Returns this node's balance data.
 TreeItem child(int pos)
          Returns the child node no.
 boolean clearConnections()
          Clears all connections starting and ending at this TreeItem.
 java.lang.Object clone()
          Clones the object flat.
 java.lang.Object clone(java.util.Hashtable h, int level)
          Clones the object according to ControlledCloneable.
 boolean connect(TreeItem node, int pos)
          Connects this TreeItem to another one given by node, setting this node as child no.
 boolean cut()
          Cuts the partial tree beginning with this node out of the tree.
 Owner getOwningTree()
          Returns this TreeItem's Owner.
 boolean isInner()
          Returns true, if this node is an inner node, i.e. has at least one child node.
 boolean isLeaf()
          Returns true, if this node is a leaf (i.e. has no child nodes).
 boolean isRoot()
          Returns true if this node is a root node, i.e. has no parent node.
 int level()
          Computes the level in which a node is situated.
 int maxRank()
          Returns the maximal rank (the maximal number of child nodes).
 int nextChildPos(int pos)
          Returns the position of the first child-node after position pos, which is not null.
 TreeItem parent()
          Returns the parent node within the structure.
 int pos(TreeItem child)
          Returns the position at which child is connected to this TreeItem.
 int prevChildPos(int pos)
          Returns the position of the last child-node before or at position pos, which is not null.
 int rank()
          Returns this node's rank which is the number of connections to child nodes.
 boolean remove()
          Removes the node from the tree.
 boolean setBalance(byte b)
          Sets the balance data for rebalancing operations.
 boolean setMaxRank(int mr)
          Sets the maximal rank of this node to mr after the Owner was asked for permission.
 boolean setOwningTree(Owner owner)
          Defines this TreeItem's Owner.
 TreeItem sibling()
          Returns this TreeItem's brother node.
 
Methods inherited from interface gishur.core.KeyValueHolder
key, setKey, setValue, value
 

Field Detail

PARENT

public static final int PARENT
Parent node.

UNKNOWN

public static final int UNKNOWN
Unknown element.

LAST_CHILD

public static final int LAST_CHILD
Last child node.

LEFT

public static final int LEFT
Left child node.

RIGHT

public static final int RIGHT
Rigth child node.

SET_OWNER

public static final int SET_OWNER
The Owner shall be set.

REMOVE

public static final int REMOVE
Remove this object from the structure.

CLEAR_CONNECTIONS

public static final int CLEAR_CONNECTIONS
Clear all connections.

CONNECT_PARENT

public static final int CONNECT_PARENT
Connection to parent node.

CONNECT

public static final int CONNECT
Connection to a child node.

SET_MAX_RANK

public static final int SET_MAX_RANK
Setting the maximal rank (the maximal number of child nodes).

SET_BALANCE

public static final int SET_BALANCE
Setting balance data.
Method Detail

clone

public java.lang.Object clone()
Clones the object flat. The following result should be achieved: The new ListItem is not connected and has no owner. The attached keys and objects will not be cloned. They will occure as reference in the Object.
Overrides:
clone in class java.lang.Object
Returns:
cloned object
Throws:
InternalError - - if the Object could not be cloned properly

clone

public java.lang.Object clone(java.util.Hashtable h,
                              int level)
Clones the object according to ControlledCloneable. The new ListItem is not connected.
Parameters:
h - Hashtable to indicate which objects are already cloned (see also: ControlledCloneable)
level - indicates how deep the objects should be cloned (see also: ControlledCloneable)
Returns:
cloned object
Throws:
InternalError - - if the Object could not be cloned properly

setOwningTree

public boolean setOwningTree(Owner owner)
Defines this TreeItem's Owner. If there is already an Owner, he will be asked for permission. Besides, the new Owner will be asked. The operation only takes place, if both agreed. If old and new Owner are the same, no one will be asked for permission and true will be returned.
Parameters:
owner - new Owner
Returns:
true, if operation was allowed and performed successfully

getOwningTree

public Owner getOwningTree()
Returns this TreeItem's Owner.
Returns:
the Owner

balance

public byte balance()
Returns this node's balance data.
Returns:
balance-value

setBalance

public boolean setBalance(byte b)
Sets the balance data for rebalancing operations. The Owner will be ased for permission.
Parameters:
b - new balance-value
Returns:
true, if the operation was allowed and performed successfully

parent

public TreeItem parent()
Returns the parent node within the structure.
Returns:
parent TreeItem

child

public TreeItem child(int pos)
Returns the child node no. pos within the surrounding structure. If pos==PARENT, the parent node will be returned.
Parameters:
pos - the position at which the requested node is attached to its parent
Returns:
requested child node

sibling

public TreeItem sibling()
Returns this TreeItem's brother node. This method is especially use- and senseful with binary trees. Otherwise, the symmetric brother will be returned.
Returns:
brother node

pos

public int pos(TreeItem child)
Returns the position at which child is connected to this TreeItem. If PARENT is returned, child is this node's parent node. Otherwise, either UNKNOWN will be returned, if child was not found to be a child node to this or the position of child will be returned.
Parameters:
child - a TreeItem whose position at this node shall be returned
Returns:
child's position or PARENT or UNKNOWN

nextChildPos

public int nextChildPos(int pos)
Returns the position of the first child-node after position pos, which is not null. If there is no such child or pos==LAST_CHILD, UNKNOWN is returned. If pos==UNKNOWN or pos==PARENT, the position of the first child which is not null will be returned.
Parameters:
pos - position from which the search for the next child-node starts
Returns:
position of the next child !=null

prevChildPos

public int prevChildPos(int pos)
Returns the position of the last child-node before or at position pos, which is not null. If there is no such node, UNKNOWN will be returned. If pos==LAST_CHILD, pos==UNKNOWN or pos==PARENT, the child!=null with the largest pos value is returned.
Parameters:
pos - position before and at which to search for a child-node
Returns:
postion of the last child which is not null, or UNKNOWN

isLeaf

public boolean isLeaf()
Returns true, if this node is a leaf (i.e. has no child nodes).
Returns:
true, if the node is a leaf

isInner

public boolean isInner()
Returns true, if this node is an inner node, i.e. has at least one child node.
Returns:
true, if this node has at least one child node

isRoot

public boolean isRoot()
Returns true if this node is a root node, i.e. has no parent node.
Returns:
true, if this node is a root

rank

public int rank()
Returns this node's rank which is the number of connections to child nodes. The connection to the parent is not counted, because each node except for the root has exactly one parent node.
Returns:
number of upward connections starting at this node

maxRank

public int maxRank()
Returns the maximal rank (the maximal number of child nodes).
Returns:
maximal rank

level

public int level()
Computes the level in which a node is situated. The root is positioned on level 0, her child nodes on level 1 etc.
Returns:
this nodes level in the tree

setMaxRank

public boolean setMaxRank(int mr)
Sets the maximal rank of this node to mr after the Owner was asked for permission. If access was granted and the operation has been performed successfully, true is returned.
Parameters:
mr - new maximal rank
Returns:
true, if the Owner allows the operation and it was successfully performed

answerConnect

public boolean answerConnect(TreeItem node,
                             int pos)
Completes the connection process and should thus only be called by connect(TreeItem, int). The Owner must not be asked for permission again (all necessary tests are performed by connect(TreeItem, int), but answerConnect(TreeItem, int) needs to ensure that it was called by connect(TreeItem, int). This is possible by checking if 'half' the connection has been established yet.
Parameters:
node - the node which should become the parent for this TreeItem
pos - position to which this TreeItem shall be connected
Returns:
true, if the connection was allowed and successfully performed

connect

public boolean connect(TreeItem node,
                       int pos)
Connects this TreeItem to another one given by node, setting this node as child no. pos to node. It is only possible to connect two nodes belonging to the same structure. To establish a correct connection, answerConnect(TreeItem, int) is called by node. If the connection is not allowed by the Owner or if an error occurrs while connecting, false is returned. If pos==PARENT, node will be ignored and the TreeItem is connected to null as parent.
Parameters:
node - node to connect this as child to
pos - the position to which this shall be connected as child of node
Returns:
true, if the connection is allowed and performed successfully

cut

public boolean cut()
Cuts the partial tree beginning with this node out of the tree. The owning tree is asked for permission only by the parent node, if it is allowed to set its son's parent connection to null, all other connections remain untouched.
Returns:
true, if cutting off the partial tree was allowed and performed successfully

remove

public boolean remove()
Removes the node from the tree. This is only possible if rank()<2, that means if this node has maximally one child. If it has a child, this will be connected in its parent's position. The balance value is set to 0, if the removal was successful.
Returns:
true, if the removal was allowed and successful

clearConnections

public boolean clearConnections()
Clears all connections starting and ending at this TreeItem. Thus the connections will not be removed correctly. In difference to remove() there will be only one request for permission to the Owner! The Owner himself will not be changed. This TreeItem's balance value will be cleared as well.
Returns:
true, if successful