lti::tree< T >::node Class Reference

The elements of the tree are instances of the "node" class. More...

#include <ltiTree.h>

Inheritance diagram for lti::tree< T >::node:

[legend]

Collaboration diagram for lti::tree< T >::node:

[legend]

List of all members.

Public Member Functions
	node (const node &other)
virtual	~node ()
bool	isChildValid (const int &n) const
const node &	child (const int &n) const
node &	child (const int &n)
void	setDegree (const int &n, bool clear=false)
node &	appendChild (const T &newChildData)
node &	insertChild (const T &newChildData)
node &	insertChild (const int &n, const T &newChildData)
node &	moveChild (const int &m, const int &n)
node &	insertSibling (const T &newSiblingData)
node &	deleteChild (const int &n)
bool	isRoot () const
node &	parent ()
const node &	parent () const
int	degree () const
int	numberOfChildren () const
T &	getData ()
const T &	getData () const
void	setData (const T &newData)
node &	copy (const node &other)
int	height () const
int	subtreeSize () const
const int &	level () const
int	position () const
bool	equals (const node &other)
bool	isSameNode (const node &other) const
bool	isParentOf (const node &other) const
bool	isSiblingOf (const node &other) const
bool	equalsTopology (const node &other)
Storable interface

virtual bool	write (ioHandler &handler, const bool complete=true) const
virtual bool	read (ioHandler &handler, const bool complete=true)
Protected Member Functions
const int &	index () const
	node (const int &n, node &theNewParent, nodeManager &owner, const T &newData, const int &index)
	node (const int &n, node *theNewParent, nodeManager &owner, const T &newData, const int &index)
void	setParent (node &newParent)
void	setChild (const int &n, node &newChild)
void	updateLevels ()
Protected Attributes
std::vector< node * >	children
node *	theParent
nodeManager *	theOwner
T	theData
int	myIndex
int	theLevel

Detailed Description

template<class T>
class lti::tree< T >::node

The elements of the tree are instances of the "node" class.

Constructor & Destructor Documentation

template<class T>

lti::tree< T >::node::node ( const node & other ) [inline]

Copy constructor.

References lti::tree< T >::node::copy().

template<class T>

virtual lti::tree< T >::node::~node ( ) [inline, virtual]

Destructor.

template<class T>

lti::tree< T >::node::node	(	const int &	n,
		node &	theNewParent,
		nodeManager &	owner,
		const T &	newData,
		const int &	index
	)			`[inline, protected]`

Protected constructor: only the nodeManager is allowed to generate new nodes!

Parameters:

	n	initial number of children (degree) for this node
	theNewParent	the parent node of this node
	owner	the tree which owns this node
	newData	the data to be hold on this node
	index	of this node on the tree

References lti::tree< T >::node::children, lti::tree< T >::node::level(), lti::tree< T >::node::theLevel, and lti::tree< T >::node::theParent.

template<class T>

lti::tree< T >::node::node	(	const int &	n,
		node *	theNewParent,
		nodeManager &	owner,
		const T &	newData,
		const int &	index
	)			`[inline, protected]`

Protected constructor: only the nodeManager is allowed to generate new nodes!

Parameters:

	n	initial number of children (degree) for this node
	theNewParent	the parent node of this node
	owner	the tree which owns this node
	newData	the data to be hold on this node
	index	of this node on the tree

References lti::tree< T >::node::children, lti::tree< T >::node::level(), lti::tree< T >::node::theLevel, and lti::tree< T >::node::theParent.

Member Function Documentation

template<class T>

node& lti::tree< T >::node::appendChild ( const T & newChildData ) [inline]

Append a new child node with the given data.

The new node will be inserted "at the end" of the node as a new child, increasing the actual node degree. The degree of the new child will be the specified degree for the tree

Returns:: a reference to the new child

References lti::tree< T >::node::children, lti::tree< T >::nodeManager::createNode(), and lti::tree< T >::node::theOwner.

template<class T>

node& lti::tree< T >::node::child ( const int & n ) [inline]

Access a child.

If n is greater or equal than the degree, an assertion will be thrown If the n-th child has not been initialized yet, an invalid reference will be returned!. To check if a child is valid use isChildValid().

References lti::tree< T >::node::children, and lti::tree< T >::node::degree().

template<class T>

const node& lti::tree< T >::node::child ( const int & n ) const [inline]

Access the n-th child of the node.

If n is greater or equal than the degree, an assertion will be thrown If the n-th child has not been initialized yet, an invalid reference will be returned!. To check if a child is valid use isChildValid().

References lti::tree< T >::node::children, and lti::tree< T >::node::degree().

Referenced by lti::tree< T >::node::copy(), lti::tree< T >::node::equals(), lti::tree< T >::node::equalsTopology(), lti::tree< T >::nodeManager::freeNode(), lti::tree< T >::node::height(), lti::tree< T >::const_iterator::operator++(), lti::tree< T >::iterator::operator++(), lti::tree< T >::node::position(), lti::tree< T >::node::read(), lti::tree< T >::node::subtreeSize(), lti::tree< T >::node::updateLevels(), and lti::tree< T >::node::write().

template<class T>

node& lti::tree< T >::node::copy ( const node & other ) [inline]

Copy the contents of the other node and of all its children.

The parent will be kept. All the children will be also copied.

Parameters:

other

the "root" node of the branch to be copied

Returns:: a reference to this node If you need to copy only the data of the node, you can use for example setData(other.getData());

Reimplemented from lti::ioObject.

References lti::tree< T >::node::child(), lti::tree< T >::node::children, lti::tree< T >::nodeManager::createNode(), lti::tree< T >::node::degree(), lti::tree< T >::node::getData(), lti::tree< T >::node::isChildValid(), lti::tree< T >::node::setData(), lti::tree< T >::node::setDegree(), lti::tree< T >::node::theLevel, and lti::tree< T >::node::theOwner.

Referenced by lti::tree< T >::node::node().

template<class T>

int lti::tree< T >::node::degree ( ) const [inline]

template<class T>

node& lti::tree< T >::node::deleteChild ( const int & n ) [inline]

Delete the given child.

Returns:: a reference to this node

References lti::tree< T >::node::children, lti::tree< T >::node::degree(), lti::tree< T >::nodeManager::freeNode(), and lti::tree< T >::node::theOwner.

template<class T>

bool lti::tree< T >::node::equals ( const node & other ) [inline]

Return true if both nodes contains equal data AND if all its children are equal.

If you need to compare only the data of this node, you can do it explicitly with getData()==other.getData().

References lti::tree< T >::node::child(), lti::tree< T >::node::degree(), lti::tree< T >::node::equals(), lti::tree< T >::node::getData(), lti::tree< T >::node::height(), lti::tree< T >::node::isChildValid(), and lti::tree< T >::size().

Referenced by lti::tree< T >::node::equals().

template<class T>

bool lti::tree< T >::node::equalsTopology ( const node & other ) [inline]

Equals topology returns true if this and the other tree have exactly the same topology (the same valid children and all children have the same topology.

References lti::tree< T >::node::child(), lti::tree< T >::node::degree(), lti::tree< T >::node::equalsTopology(), and lti::tree< T >::node::isChildValid().

Referenced by lti::tree< T >::node::equalsTopology().

template<class T>

const T& lti::tree< T >::node::getData ( ) const [inline]

Return a read-only reference to the node's data.

References lti::tree< T >::node::theData.

template<class T>

T& lti::tree< T >::node::getData ( ) [inline]

Return a reference to the node's data.

References lti::tree< T >::node::theData.

Referenced by lti::tree< T >::node::copy(), and lti::tree< T >::node::equals().

template<class T>

int lti::tree< T >::node::height ( ) const [inline]

Calculate the height of this node, defined as the length of the longest path from this node to some leaf node.

If this node is a leaf, the returned value is 0. Please note that this function is highly recursive and could take a while...

References lti::tree< T >::node::child(), lti::tree< T >::node::degree(), lti::tree< T >::node::isChildValid(), and lti::max().

Referenced by lti::tree< T >::node::equals().

template<class T>

const int& lti::tree< T >::node::index ( ) const [inline, protected]

Return a const reference to the index of this node in the nodeManager.

Referenced by lti::tree< T >::nodeManager::freeNode(), and lti::tree< T >::nodeManager::getIndexOfNode().

template<class T>

node& lti::tree< T >::node::insertChild	(	const int &	n,
		const T &	newChildData
	)			`[inline]`

Insert a new child node with the given data at the given child index.

If the node has already a child at the given position, the whole branch will be inserted at the first child of the new node

The degree of the new child will be the degree of this node

References lti::tree< T >::node::children, lti::tree< T >::nodeManager::createNode(), lti::tree< T >::node::degree(), lti::tree< T >::node::setChild(), lti::tree< T >::node::setDegree(), and lti::tree< T >::node::theOwner.

template<class T>

node& lti::tree< T >::node::insertChild ( const T & newChildData ) [inline]

Insert a new child node with the given data.

The new node will be inserted at the first uninitialized child. If all children are already initialized, the degree of this node will be incremented and the new child will contain the given data. The degree of the new child will be the specified degree for the tree

Returns:: a reference to the new child

References lti::tree< T >::node::children, lti::tree< T >::nodeManager::createNode(), lti::tree< T >::node::degree(), lti::tree< T >::node::setDegree(), and lti::tree< T >::node::theOwner.

Referenced by lti::tree< T >::node::insertSibling(), and lti::tree< T >::node::read().

template<class T>

node& lti::tree< T >::node::insertSibling ( const T & newSiblingData ) [inline]

Insert a new sibling node with the given data.

The new node will be created at the first uninitialized sibling. If all siblings are already initialized, the degree of the parent will be incremented and the new child will contain the given data. The degree of the new child will be the new degree of the parent An assertion will be thrown if this member is called for a root node

Returns:: a reference to the new sibling

References lti::tree< T >::node::insertChild(), lti::tree< T >::node::isRoot(), and lti::tree< T >::node::parent().

template<class T>

bool lti::tree< T >::node::isChildValid ( const int & n ) const [inline]

Return true if the n-th child of this node has valid data or false otherwise.

References lti::tree< T >::node::children, and lti::tree< T >::node::degree().

Referenced by lti::tree< T >::node::copy(), lti::tree< T >::node::equals(), lti::tree< T >::node::equalsTopology(), lti::tree< T >::nodeManager::freeNode(), lti::tree< T >::node::height(), lti::tree< T >::node::numberOfChildren(), lti::tree< T >::const_iterator::operator++(), lti::tree< T >::iterator::operator++(), lti::tree< T >::node::subtreeSize(), lti::tree< T >::node::updateLevels(), and lti::tree< T >::node::write().

template<class T>

bool lti::tree< T >::node::isParentOf ( const node & other ) const [inline]

Return true if the this node is the parent of the other node.

References lti::tree< T >::node::isRoot(), lti::tree< T >::node::isSameNode(), and lti::tree< T >::node::parent().

template<class T>

bool lti::tree< T >::node::isRoot ( ) const [inline]

Check if this node is a root node (i.e.

has no parent!)

References lti::tree< T >::node::theParent.

Referenced by lti::tree< T >::node::insertSibling(), lti::tree< T >::node::isParentOf(), lti::tree< T >::node::isSiblingOf(), and lti::tree< T >::node::position().

template<class T>

bool lti::tree< T >::node::isSameNode ( const node & other ) const [inline]

Return true if both nodes are exactly the same node.

Referenced by lti::tree< T >::node::isParentOf(), lti::tree< T >::node::isSiblingOf(), and lti::tree< T >::node::position().

template<class T>

bool lti::tree< T >::node::isSiblingOf ( const node & other ) const [inline]

Return true if the other node is a sibling of this node.

A node is NOT a sibling of itself.

References lti::tree< T >::node::isRoot(), lti::tree< T >::node::isSameNode(), and lti::tree< T >::node::parent().

template<class T>

const int& lti::tree< T >::node::level ( ) const [inline]

Returns the level of this node, defined as the lenght of the path from this node to the root.

i.e. if this node is root, its level is 0

References lti::tree< T >::node::theLevel.

Referenced by lti::tree< T >::node::node(), and lti::tree< T >::node::updateLevels().

template<class T>

node& lti::tree< T >::node::moveChild	(	const int &	m,
		const int &	n
	)			`[inline]`

Move a child branch to another position at this node.

If the node has already a child at the given position, the whole branch will be deleted.

Parameters:

	m	the old position
	n	the new position

References lti::tree< T >::node::children, lti::tree< T >::node::degree(), lti::tree< T >::nodeManager::freeNode(), and lti::tree< T >::node::theOwner.

template<class T>

int lti::tree< T >::node::numberOfChildren ( ) const [inline]

Calculate the number of valid children.

This number is always less or equal degree(). The number of valid children will be calculated and for that reason is faster to ask for the degree() of the node.

References lti::tree< T >::node::degree(), and lti::tree< T >::node::isChildValid().

template<class T>

const node& lti::tree< T >::node::parent ( ) const [inline]

Access parent node.

References lti::tree< T >::node::theParent.

template<class T>

node& lti::tree< T >::node::parent ( ) [inline]

Access parent node.

Please note that the returned reference can be invalid if this is the root node. To check this condition use isRoot()

References lti::tree< T >::node::theParent.

Referenced by lti::tree< T >::node::insertSibling(), lti::tree< T >::node::isParentOf(), lti::tree< T >::node::isSiblingOf(), and lti::tree< T >::node::position().

template<class T>

int lti::tree< T >::node::position ( ) const [inline]

Calulates the position of this node for the parent.

If this node is root, the returned value will be negative.

For example, let aNode be a non-root node, the following expression will return always true: aNode.isSameNode(aNode.parent().child(aNode.position()))

References lti::tree< T >::node::child(), lti::tree< T >::node::degree(), lti::tree< T >::node::isRoot(), lti::tree< T >::node::isSameNode(), and lti::tree< T >::node::parent().

template<class T>

virtual bool lti::tree< T >::node::read	(	ioHandler &	handler,
		const bool	complete = `true`
	)			`[inline, virtual]`

Read the parameters from the given ioHandler.

Parameters:

	handler	the ioHandler to be used
	complete	if true (the default) the enclosing begin/end will be also written, otherwise only the data block will be written.

Returns:: true if write was successful

Reimplemented from lti::ioObject.

References lti::tree< T >::node::child(), lti::tree< T >::node::insertChild(), lti::tree< T >::node::read(), lti::ioHandler::read(), lti::ioHandler::readBegin(), lti::ioHandler::readDataSeparator(), lti::ioHandler::readEnd(), lti::tree< T >::node::setDegree(), lti::tree< T >::node::theData, and lti::ioHandler::tryEnd().

Referenced by lti::tree< T >::node::read().

template<class T>

void lti::tree< T >::node::setChild	(	const int &	n,
		node &	newChild
	)			`[inline, protected]`

Change the reference of a child node.

Be careful with the use of this member function: after the use of the function there is no way to get a reference to the old child, and this can produce huge memory leaks!!! the parent of the child will be changed to this node!

References lti::tree< T >::node::children, lti::tree< T >::node::degree(), lti::tree< T >::node::theParent, and lti::tree< T >::node::updateLevels().

Referenced by lti::tree< T >::node::insertChild().

template<class T>

void lti::tree< T >::node::setData ( const T & newData ) [inline]

Set the data of the node.

References lti::tree< T >::node::theData.

Referenced by lti::tree< T >::node::copy().

template<class T>

void lti::tree< T >::node::setDegree	(	const int &	n,
		bool	clear = `false`
	)			`[inline]`

Change the degree of this node.

Parameters:

	n	new degree
	clear	(default false) if true, this node will be (re)initialized as a leaf (i.e. all children NULL!)

References lti::tree< T >::node::children, lti::tree< T >::clear(), lti::tree< T >::node::degree(), lti::tree< T >::nodeManager::freeNode(), and lti::tree< T >::node::theOwner.

Referenced by lti::tree< T >::node::copy(), lti::tree< T >::node::insertChild(), and lti::tree< T >::node::read().

template<class T>

void lti::tree< T >::node::setParent ( node & newParent ) [inline, protected]

Change the reference to the parent node.

Note that you should make sure that the old parent forgets about this node!

References lti::tree< T >::node::theParent, and lti::tree< T >::node::updateLevels().

template<class T>

int lti::tree< T >::node::subtreeSize ( ) const [inline]

Calculates the size (total number of valid nodes) of the subtree beginning with this node.

If this node is a leaf, the returned value is 1 Please note that this function is highly recursive and could take a while...

References lti::tree< T >::node::child(), lti::tree< T >::node::degree(), lti::tree< T >::node::isChildValid(), and lti::tree< T >::node::subtreeSize().

Referenced by lti::tree< T >::node::subtreeSize().

template<class T>

void lti::tree< T >::node::updateLevels ( ) [inline, protected]

Update parent size and height.

References lti::tree< T >::node::child(), lti::tree< T >::node::degree(), lti::tree< T >::node::isChildValid(), lti::tree< T >::node::level(), lti::tree< T >::node::theLevel, lti::tree< T >::node::theParent, and lti::tree< T >::node::updateLevels().

Referenced by lti::tree< T >::node::setChild(), lti::tree< T >::node::setParent(), and lti::tree< T >::node::updateLevels().

template<class T>

virtual bool lti::tree< T >::node::write	(	ioHandler &	handler,
		const bool	complete = `true`
	)			const `[inline, virtual]`

Write the parameters in the given ioHandler.

Parameters:

	handler	the ioHandler to be used
	complete	if true (the default) the enclosing begin/end will be also written, otherwise only the data block will be written.