info.monitorenter.cpdetector.util.collections
Class ITreeNode.DefaultTreeNode

java.lang.Object
  info.monitorenter.cpdetector.util.collections.ITreeNode.DefaultTreeNode

All Implemented Interfaces:

ITreeNode, Comparable

Direct Known Subclasses:

TreeNodeUniqueChildren

Enclosing interface:

ITreeNode

public static class ITreeNode.DefaultTreeNode
extends Object
implements ITreeNode, Comparable

Plain-forward implementation of the ITreeNodeinterface.

This implementation covers many of the algorithms that may be somewhat tricky to implement in an elegant way for beginners. Subclasses may add other policies and constraints to achieve a special invariant with a certain behaviour.

Author:

Nested Class Summary

Nested classes/interfaces inherited from interface info.monitorenter.cpdetector.util.collections.ITreeNode

ITreeNode.DefaultTreeNode

Field Summary

protected SortedSet	m_children A Listof child ITreeNode instances.
protected Object	m_userObject Member for saving the user Object.
protected boolean	marked Flag for saving the marking-state.

Fields inherited from interface info.monitorenter.cpdetector.util.collections.ITreeNode

ROOT

Constructor Summary

ITreeNode.DefaultTreeNode()
Create a ITreeNode without a parent, user Object and m_children.

ITreeNode.DefaultTreeNode(Object userObject)
Create a ITreeNode without a parent that carries the given user Object.

ITreeNode.DefaultTreeNode(Object userObject, ITreeNode child)
Create a ITreeNode without a parent that carries the given user Object and has the given ITreeNode as child.

ITreeNode.DefaultTreeNode(Object userObject, ITreeNode[] children)
Create a ITreeNode without a parent that carries the given user Object and has the given ITreeNode instances as m_children.

Method Summary

ITreeNode	addChild(Object userObject) The given Object will be stored in a newly created ITreeNode which will get assigned this node to be it's father, while this instance will store the new node in it's list (unconditionally: e.g.
boolean	addChildNode(ITreeNode node) The given ITreeNode will become this node to be it's father, while this instance will store the given node in it's list if not null (unconditionally: e.g.
boolean	addChildNodes(ITreeNode[] nodes) Adds all given ITreeNode instances to the set of this instances childs.
ITreeNode[]	addChildren(Object[] userObjects) Adds all given Objects to newly instanciated ITreeNode instances that are added to the set of this instances childs.
int	compareTo(Object o)
boolean	contains(Object userObject) Find out, wether a certain "user" Object is carried by any of this ITreeNodes subtree.
boolean	containsNode(ITreeNode node) Find out, wether the given ITreeNode is a member of this node's subtree.
boolean	equals(Object obj) Two instances are equal, if they both are of this type and user objects are equal.
List	getAllChildren() Get all child nodes of the ITreeNode.
int	getChildCount() Returns the amount of child ITreeNodes of this ITreeNode.
Iterator	getChilds() The Iteratorreturned will not traverse the whole subtree but only the direct child nodes of this ITreeNode.
ITreeNode	getParent() Get the parent node of this ITreeNode.
void	getPathFromRoot(List l)
int	getSubtreeCount() Get the amount of direct and indirect childs of this ITreeNode.
Object	getUserObject() Returns the "user" Object that may be carried by the ITreeNode, or null, if no one was assigned.
void	getUserObjectPathFromRoot(List l)
boolean	isLeaf() Find out, wether this ITreeNode is a childless leaf.
boolean	isMarked() Check, wether this ITreeNode is marked.
boolean	isRoot() Find out, wether there is no path to a higher parental node from this ITreeNode.
void	mark() Marks this ITreeNode instance (e.g.
ITreeNode	newInstance() Generic operations in default implementations may need to allocate new instances but have to choose the right type to support the provided invariants.
ITreeNode	remove(Object userObject) The search is a "prefix-search":
List	removeAllChildren() Remove all child nodes of the ITreeNode.
boolean	removeChild(ITreeNode node) Remove the given ITreeNode from this node.
void	setParent(ITreeNode parent) This method should not be called from outside.
Object	setUserObject(Object store) Assigns the "user" Object that may be carried by the ITreeNode.
String	toString()
protected void	toStringInternal(StringBuffer buf, int depth)
void	unmark() Unmarks this ITreeNode instance (e.g.

Methods inherited from class java.lang.Object

clone, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

marked

protected boolean marked

Flag for saving the marking-state. False by default.

m_userObject

protected Object m_userObject

Member for saving the user Object.

See Also:

getUserObject()

m_children

protected SortedSet m_children

A Listof child ITreeNode instances.

Constructor Detail

ITreeNode.DefaultTreeNode

public ITreeNode.DefaultTreeNode()

Create a ITreeNode without a parent, user Object and m_children. After this call, this instance will be the root node (no parent).

ITreeNode.DefaultTreeNode

public ITreeNode.DefaultTreeNode(Object userObject)

Create a ITreeNode without a parent that carries the given user Object.

Parameters:

userObject - An Object that is desired to be stored in the node.

ITreeNode.DefaultTreeNode

public ITreeNode.DefaultTreeNode(Object userObject,
                                 ITreeNode child)

Create a ITreeNode without a parent that carries the given user Object and has the given ITreeNode as child.

Parameters:

userObject - An Object that is desired to be stored in the node.

child - The first child of this node.

ITreeNode.DefaultTreeNode

public ITreeNode.DefaultTreeNode(Object userObject,
                                 ITreeNode[] children)

Create a ITreeNode without a parent that carries the given user Object and has the given ITreeNode instances as m_children.

Perhaps the most useful constructor. It allows to construct trees in a short overviewable way:

        new DefaultTreeNode(
          new Integer(1),
          new ITreeNode[]{
            new DefaultTreeNode(
              new Integer(2)
            ),
            new DefaultTreeNode(
              new Integer(3),
              new DefaultTreeNode(
                new Integer
              )
            )
        );
 

Parameters:

userObject - An Object that is desired to be stored in the node.

children - An array of ITreeNode instances that will become childs of this node.

Method Detail

equals

public boolean equals(Object obj)

Two instances are equal, if they both are of this type and user objects are equal.

Specified by:

equals in interface ITreeNode

Overrides:

equals in class Object

Parameters:

obj - Possibly a ITreeNode that has to be checked for equality.

Returns:

True, if your implementation judges both instances equal.

See Also:

setUserObject(Object), Object.equals(java.lang.Object)

addChild

public final ITreeNode addChild(Object userObject)

The given Object will be stored in a newly created ITreeNode which will get assigned this node to be it's father, while this instance will store the new node in it's list (unconditionally: e.g. no test, if already contained).

Specified by:

addChild in interface ITreeNode

Parameters:

userObject - The Object that should be carried by the new ITreeNode or null, if no one is desired.

Returns:

See the ITreeNode{interface}: Null may be returned in case of failure!!!

See Also:

ITreeNode.addChild(Object)

addChildNode

public boolean addChildNode(ITreeNode node)

The given ITreeNode will become this node to be it's father, while this instance will store the given node in it's list if not null (unconditionally: e.g. no test, if already contained).

Specified by:

addChildNode in interface ITreeNode

Parameters:

node - the node to add as child.

Returns:

True, if the operation was succesful: For example some implementations (e.g. with support for unique user Objects in childs on the same level with the same parent node) may dissallow duplicate child nodes.

See Also:

ITreeNode.addChildNode(ITreeNode)

contains

public final boolean contains(Object userObject)

Description copied from interface: ITreeNode

Find out, wether a certain "user" Object is carried by any of this ITreeNodes subtree.

Specified by:

contains in interface ITreeNode

Parameters:

userObject - Any Object, that might be contained in this tree - Identification is done by the means of the Objects Object.equals(Object)- method.

Returns:

True, if any node of this subtree (including this ITreeNode contained a user Object that was equal to the given argument.

containsNode

public final boolean containsNode(ITreeNode node)

Description copied from interface: ITreeNode

Find out, wether the given ITreeNode is a member of this node's subtree.

Specified by:

containsNode in interface ITreeNode

Parameters:

node - A ITreeNode that migth possibly linked to (or be) this instance by the means of the equals operation.

Returns:

True, if an ITreeNode equal to the argument was found in the subtree started by this node.

See Also:

ITreeNode.equals(Object)

getChildCount

public final int getChildCount()

Description copied from interface: ITreeNode

Returns the amount of child ITreeNodes of this ITreeNode.

Specified by:

getChildCount in interface ITreeNode

getChilds

public final Iterator getChilds()

Description copied from interface: ITreeNode

The Iteratorreturned will not traverse the whole subtree but only the direct child nodes of this ITreeNode.

Specified by:

getChilds in interface ITreeNode

Returns:

An Iteratorover the direct childs of this ITreeNode.

getParent

public final ITreeNode getParent()

Description copied from interface: ITreeNode

Get the parent node of this ITreeNode. If the TreeNode has no parent node (e.g. a member of an implementation for the parent node is null), ITreeNode.ROOThas to be returned.

Specified by:

getParent in interface ITreeNode

Returns:

The parent ITreeNode of this node or ITreeNode.ROOT, if this node is the root.

getSubtreeCount

public final int getSubtreeCount()

Description copied from interface: ITreeNode

Get the amount of direct and indirect childs of this ITreeNode.

Specified by:

getSubtreeCount in interface ITreeNode

Returns:

The total amount of all ITreeNode instances of this subtree (including this node).

getUserObject

public final Object getUserObject()

Description copied from interface: ITreeNode

Returns the "user" Object that may be carried by the ITreeNode, or null, if no one was assigned.

Specified by:

getUserObject in interface ITreeNode

Returns:

The user Object carried by this treenode or null, if no one was assigned.

mark

public final void mark()

Description copied from interface: ITreeNode

Marks this ITreeNode instance (e.g. for being visited or invisible). Marking may be used to traverse the tree in an asynchronous manner from outside (TreeIterator) or for other desireable tasks.

Subsequent calls to this method should not change the state to "unmarked".

Specified by:

mark in interface ITreeNode

isMarked

public final boolean isMarked()

Description copied from interface: ITreeNode

Check, wether this ITreeNode is marked.

Specified by:

isMarked in interface ITreeNode

Returns:

True, if this ITreeNode is marked, false else.

remove

public final ITreeNode remove(Object userObject)

The search is a "prefix-search":

      
       
       
            A
           / \
          B   C
         / \
        D   E
       
        
       
 

The search will be done in the order: A,B,D,E,C. If this ITreeNode contains the user Object equal to the argument, itself will be returned. This ITreeNode may be the root!

Specified by:

remove in interface ITreeNode

Parameters:

userObject - The user Object identifying the treenode to remove.

Returns:

The TreeNode (being the new root of it's subtree) that was removed from this node's subtree or null, if no ITreeNode contained an equal user Object.

See Also:

ITreeNode.remove(Object)

removeAllChildren

public final List removeAllChildren()

Description copied from interface: ITreeNode

Remove all child nodes of the ITreeNode.

Specified by:

removeAllChildren in interface ITreeNode

Returns:

A Listcontaining all removed child nodes. An empty List should be provided instead of null!

removeChild

public boolean removeChild(ITreeNode node)

Description copied from interface: ITreeNode

Remove the given ITreeNode from this node. If the operation is successful the given node will not have any parent node (e.g. null for parent member) but be the root node of it's subtree.

The operation may fail, if the given ITreeNode is no child of this node, or the implementation permits the removal.

Specified by:

removeChild in interface ITreeNode

Parameters:

node - A child of this ITreeNode (by the means of the ITreeNode.equals(Object)operation) .

Returns:

True, if the removal was successful, false if not.

setUserObject

public final Object setUserObject(Object store)

Description copied from interface: ITreeNode

Assigns the "user" Object that may be carried by the ITreeNode.

Specified by:

setUserObject in interface ITreeNode

Returns:

The previous user Object that was carried or null, if no one was assigned.

unmark

public final void unmark()

Description copied from interface: ITreeNode

Unmarks this ITreeNode instance (e.g. for being visited or invisible). Marking may be used to traverse the tree in an asynchronous manner from outside (TreeIterator) or for other desireable tasks.

Subsequent calls to this method should not change the state to "marked".

Specified by:

unmark in interface ITreeNode

setParent

public final void setParent(ITreeNode parent)

Description copied from interface: ITreeNode

This method should not be called from outside. It is a callback for the method ITreeNode.addChildNode(ITreeNode)and should be used by implementations of that method but not any further. Else inconsistencies could occur: A node thinks it is the father of another node which itself does not know about that relation any more (remove itself from the old parent member's list could avoid it).

Specified by:

setParent in interface ITreeNode

Parameters:

parent - The new parental node.

isLeaf

public final boolean isLeaf()

Description copied from interface: ITreeNode

Find out, wether this ITreeNode is a childless leaf.

Specified by:

isLeaf in interface ITreeNode

Returns:

True, if this ITreeNode has no child nodes.

isRoot

public final boolean isRoot()

Description copied from interface: ITreeNode

Find out, wether there is no path to a higher parental node from this ITreeNode.

Specified by:

isRoot in interface ITreeNode

Returns:

True if this poor node is an orphan.

toString

public String toString()

Overrides:

toString in class Object

toStringInternal

protected void toStringInternal(StringBuffer buf,
                                int depth)

addChildNodes

public final boolean addChildNodes(ITreeNode[] nodes)

Description copied from interface: ITreeNode

Adds all given ITreeNode instances to the set of this instances childs. This operation should delegate to ITreeNode.addChildNode(ITreeNode).

Specified by:

addChildNodes in interface ITreeNode

Parameters:

nodes - An arry of ITreeNode instances.

Returns:

True, if all childs could be added (null instances are skipped), false else.

addChildren

public final ITreeNode[] addChildren(Object[] userObjects)

Description copied from interface: ITreeNode

Adds all given Objects to newly instanciated ITreeNode instances that are added to the set of this instances childs. This operation should delegate to ITreeNode.addChild(Object).

Specified by:

addChildren in interface ITreeNode

Parameters:

userObjects - An arry of Objects instances which will become the m_userObject members of the newly created ITreeNode instances.

Returns:

An array containing all new ITreeNode instances created (they contain the user objects).

getAllChildren

public final List getAllChildren()

Description copied from interface: ITreeNode

Get all child nodes of the ITreeNode.

Specified by:

getAllChildren in interface ITreeNode

Returns:

A Listcontaining all child nodes. An empty List should be provided instead of null!

newInstance

public ITreeNode newInstance()

Description copied from interface: ITreeNode

Generic operations in default implementations may need to allocate new instances but have to choose the right type to support the provided invariants.

If you provide a subclass that has invariants you should overload this.

Specified by:

newInstance in interface ITreeNode

Returns:

A new allocated instance of the concrete impelementation.

getPathFromRoot

public void getPathFromRoot(List l)

Specified by:

getPathFromRoot in interface ITreeNode

Parameters:

l - An empty List: After this call it will be filled with ITreeNodeinstances starting from the root node to the current node that is invoked.

getUserObjectPathFromRoot

public void getUserObjectPathFromRoot(List l)

Specified by:

getUserObjectPathFromRoot in interface ITreeNode

Parameters:

l - An empty List: After this call it will be filled with the ITreeNode.getUserObject()instances starting from the root node to the current node that was invoked.

compareTo

public int compareTo(Object o)
              throws ClassCastException

Specified by:

compareTo in interface Comparable

Throws:

ClassCastException