Main Page   Namespace List   Class Hierarchy   Compound List   File List   Namespace Members   Compound Members  

mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode > Class Template Reference

#include <general_tree.hh>

List of all members.

Public Types

typedef TNode::alloc_smart_pointer QTNode
 Alloc-smart-pointer to node type.

typedef memory::TAllocSmartPointer<
TGeneralTree, TAllocator > 		QTTree
 Smart-pointer to general tree type.

typedef TGeneralTreePreIterator<
const TItem, TAllocator > 		const_iterator
 Const iterator type.

typedef TGeneralTreeSideIterator<
const TItem, TAllocator > 		const_side_iterator
 Const side iterator type.

typedef TGeneralTreePreIterator<
TItem, TAllocator > 		iterator
 Iterator type.

typedef TGeneralTreeSideIterator<
TItem, TAllocator > 		side_iterator
 Iterator type.

typedef TNode::size_type size_type
 Size type.

typedef TItem value_type
 Value type.


Public Methods

 TGeneralTree (void)
 TGeneralTree (const TItem &rktITEM)
 TGeneralTree (const TGeneralTree &rktGENERAL_TREE)
virtual ~TGeneralTree (void)
 Destroys the instance. Complexity is like of clear().

void clear (void)
TGeneralTree & copy (const TGeneralTree &rktGENERAL_TREE)
template<typename TIterator> TIterator erase (TIterator tPOSITION)
template<typename TIterator> TIterator erase (TIterator tBEGIN, TIterator tEND)
void insert (QTTree &rqtGENERAL_TREE) throw (TConstraintException)
void insert (const TItem &rktITEM) throw (TConstraintException)
template<class TIterator> void insert (TIterator tPOSITION, QTTree &rqtGENERAL_TREE) throw (TConstraintException)
template<class TIterator> void insert (TIterator tPOSITION, const TItem &rktITEM) throw (TConstraintException)
TGeneralTree & operator= (const TGeneralTree &rktGENERAL_TREE)
void setRoot (const TItem &rktITEM)
iterator begin (void)
const_iterator begin (void) const
side_iterator beginChild (void) throw (TConstraintException)
const_side_iterator beginChild (void) const throw (TConstraintException)
bool empty (void) const
iterator end (void)
const_iterator end (void) const
side_iterator endChild (void)
const_side_iterator endChild (void) const
const TItem & getRoot (void) const throw (TConstraintException)
TItem & getRoot (void) throw (TConstraintException)
size_type height (void) const
TGeneralTree leftChild (void) const
size_type max_size (void) const
TGeneralTree rightSibling (void) const
size_type size (void) const
void swap (TGeneralTree &rtTREE)

Detailed Description

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
class mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >

General (unsorted) tree.
Invariant:
( size() >= 0 )

Definition at line 704 of file general_tree.hh.

Constructor & Destructor Documentation

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::TGeneralTree (  void    )  [inline]
 

Builds a new instance of empty tree.

Postcondition:
( this->empty() )

Definition at line 777 of file general_tree.hh.

Referenced by mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::leftChild(), and mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::rightSibling().

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::TGeneralTree (  const TItem &    rktITEM )  [inline]
 

Builds a new instance with a root node that is a copy of rktITEM.

Parameters:
rktITEM  Source root node.
Postcondition:
( this->getRoot() == rktITEM )

Definition at line 786 of file general_tree.hh.

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::TGeneralTree (  const TGeneralTree< TItem, TAllocator, TNode > &    rktGENERAL_TREE )  [inline]
 

Builds a new instance copying from tree rktGENERAL_TREE.

Parameters:
rktGENERAL_TREE  Source tree.
Postcondition:
( *this == rktGENERAL_TREE )

Definition at line 795 of file general_tree.hh.

References mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::size_type.

Member Function Documentation

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
const_iterator mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::begin (  void    )  const [inline]
 

Returns the iterator at first sub-tree. Complexity is constant.

Returns:
The iterator at first sub-tree.

Definition at line 1053 of file general_tree.hh.

References mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::const_iterator.

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
iterator mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::begin (  void    )  [inline]
 

Returns the iterator at first sub-tree. Complexity is constant.

Returns:
The iterator at first sub-tree.

Definition at line 1044 of file general_tree.hh.

References mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::iterator.

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
const_side_iterator mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::beginChild (  void    )  const throw (TConstraintException) [inline]
 

Returns the iterator at first sub-tree. Complexity is constant.

Returns:
The iterator at first sub-tree.
Precondition:
( !empty() )

Definition at line 1078 of file general_tree.hh.

References mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::const_side_iterator.

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
side_iterator mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::beginChild (  void    )  throw (TConstraintException) [inline]
 

Returns the iterator at first sub-tree. Complexity is constant.

Returns:
The iterator at first sub-tree.
Precondition:
( !empty() )

Definition at line 1063 of file general_tree.hh.

References mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::side_iterator.

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
void mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::clear (  void    )  [inline]
 

Clears all the sub-trees. Complexity is constant.

Postcondition:
( empty() )

Definition at line 819 of file general_tree.hh.

Referenced by mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::~TGeneralTree().

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
TGeneralTree& mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::copy (  const TGeneralTree< TItem, TAllocator, TNode > &    rktGENERAL_TREE )  [inline]
 

Copies another tree onto this instance. Complexity is linear.

Parameters:
rktGENERAL_TREE  Source tree.
Returns:
This instance.

Definition at line 829 of file general_tree.hh.

References mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::qtRootNode, mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::size(), and mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::size_type.

Referenced by mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::operator=().

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
bool mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::empty (  void    )  const [inline]
 

Returns true if tree is empty. Complexity is constant.

Returns:
True if tree is empty (has no root node).

Definition at line 1092 of file general_tree.hh.

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
const_iterator mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::end (  void    )  const [inline]
 

Returns the iterator at position past the last sub-tree. Complexity is constant.

Returns:
The iterator at position past the last sub-tree.

Definition at line 1112 of file general_tree.hh.

References mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::const_iterator.

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
iterator mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::end (  void    )  [inline]
 

Returns the iterator at position past the last sub-tree. Complexity is constant.

Returns:
The iterator at position past the last sub-tree.

Definition at line 1102 of file general_tree.hh.

References mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::iterator.

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
const_side_iterator mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::endChild (  void    )  const [inline]
 

Returns the iterator at position past the last sub-tree. Complexity is constant.

Returns:
The iterator at position past the last sub-tree.

Definition at line 1132 of file general_tree.hh.

References mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::const_side_iterator.

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
side_iterator mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::endChild (  void    )  [inline]
 

Returns the iterator at position past the last sub-tree. Complexity is constant.

Returns:
The iterator at position past the last sub-tree.

Definition at line 1122 of file general_tree.hh.

References mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::side_iterator.

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
template<typename TIterator>
TIterator mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::erase (  TIterator    tBEGIN,
TIterator    tEND
)  [inline]
 

Erases sub-trees from position tBEGIN to tEND. Complexity is linear.

Parameters:
tBEGIN  Iterator pointing to the first element to be erased.
tEND  Iterator pointing past the last element to be erased.
Returns:
An iterator that points to the element immediately following tEND prior to the element being erased. If no such element exists, end() is returned.

Definition at line 888 of file general_tree.hh.

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
template<typename TIterator>
TIterator mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::erase (  TIterator    tPOSITION )  [inline]
 

Erases sub-tree pointed by tPOSITION. Complexity is constant.

Parameters:
tPOSITION  Iterator pointing to the element to be erased.
Returns:
An iterator that points to the element immediately following tPOSITION prior to the element being erased. If no such element exists, end() is returned.
Postcondition:
( old (size()) > size() )

Definition at line 869 of file general_tree.hh.

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
TItem& mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::getRoot (  void    )  throw (TConstraintException) [inline]
 

Returns the root node item. Complexity is constant.

Returns:
The root node item.
Precondition:
( !empty() )

Definition at line 1157 of file general_tree.hh.

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
const TItem& mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::getRoot (  void    )  const throw (TConstraintException) [inline]
 

Returns the root node item. Complexity is constant.

Returns:
The root node item.
Precondition:
( !empty() )

Definition at line 1142 of file general_tree.hh.

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
size_type mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::height (  void    )  const [inline]
 

Returns the height of the tree. Complexity is like TNode::height().

Returns:
The height of the tree.

Definition at line 1171 of file general_tree.hh.

References mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::size_type.

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
template<class TIterator>
void mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::insert (  TIterator    tPOSITION,
const TItem &    rktITEM
)  throw (TConstraintException) [inline]
 

Inserts as the last child node, the item rktITEM. Complexity is like of TNode::insert().

Parameters:
tPOSITION  Iterator pointing at the position where the tree rqtGENERAL_TREE must be inserted.
rqtGENERAL_TREE  Smart-pointer to the tree to be inserted.
Precondition:
( !empty() )
Postcondition:
( size() > old (size()) )
Exceptions:
TConstraintException  ( rqtGENERAL_TREEE.empty() )
TConstraintException  ( tPOSITION == end() )

Definition at line 984 of file general_tree.hh.

References mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::QTNode.

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
template<class TIterator>
void mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::insert (  TIterator    tPOSITION,
QTTree &    rqtGENERAL_TREE
)  throw (TConstraintException) [inline]
 

Inserts the sub-tree rqtGENERAL_TREE at position tPOSITION. Complexity is like of TNode::insert().

Parameters:
tPOSITION  Iterator pointing at the position where the tree rqtGENERAL_TREE must be inserted.
rqtGENERAL_TREE  Smart-pointer to the tree to be inserted.
Precondition:
( !empty() )
( !rqtGENERAL_TREE.empty() )
Postcondition:
( size() > old (size()) )
Exceptions:
TConstraintException  ( rqtGENERAL_TREEE.empty() )
TConstraintException  ( tPOSITION == end() )

Definition at line 957 of file general_tree.hh.

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
void mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::insert (  const TItem &    rktITEM )  throw (TConstraintException) [inline]
 

Inserts, as the last position, the item rktITEM. Complexity is like of TNode::insert().

Parameters:
rktITEM  Item to be inserted.
Exceptions:
TConstraintException  ( empty() )
Precondition:
( !empty() )
Postcondition:
( size() > old (size()) )

Definition at line 929 of file general_tree.hh.

References mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::QTNode.

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
void mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::insert (  QTTree &    rqtGENERAL_TREE )  throw (TConstraintException) [inline]
 

Inserts, as the last sub-tree, the tree rqtGENERAL_TREE. Complexity is like of TNode::insert().

Parameters:
rqtGENERAL_TREE  Smart-pointer to the tree to insert.
Exceptions:
TConstraintException  ( empty() )
Precondition:
( !empty() )
( !rqtGENERAL_TREE.empty() )
Postcondition:
( size() > old (size()) )

Definition at line 911 of file general_tree.hh.

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
TGeneralTree mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::leftChild (  void    )  const [inline]
 

Returns a tree pointing to the left child sub-tree. Complexity is constant.

Returns:
A tree pointing to the left child sub-tree.
Precondition:
( !empty() )

Definition at line 1182 of file general_tree.hh.

References mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::TGeneralTree().

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
size_type mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::max_size (  void    )  const [inline]
 

Returns maximum size of the tree.

Returns:
Maximum size of the tree.

Definition at line 1195 of file general_tree.hh.

References mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::size_type.

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
TGeneralTree& mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::operator= (  const TGeneralTree< TItem, TAllocator, TNode > &    rktGENERAL_TREE )  [inline]
 

Copies another tree onto this instance. Complexity is linear.

Parameters:
rktGENERAL_TREE  Source tree.
Returns:
This instance.
Postcondition:
( parent() == old (parent()) )

Definition at line 1011 of file general_tree.hh.

References mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::copy().

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
TGeneralTree mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::rightSibling (  void    )  const [inline]
 

Returns a tree pointing to the right sibling sub-tree. Complexity is constant.

Returns:
A tree pointing to the right sibling sub-tree.
Precondition:
( !empty() )

Definition at line 1206 of file general_tree.hh.

References mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::TGeneralTree().

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
void mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::setRoot (  const TItem &    rktITEM )  [inline]
 

Sets the root node item to rktITEM. Complexity is constant.

Parameters:
rktITEM  Source item.
Postcondition:
( size() >= old (size()) )

Definition at line 1021 of file general_tree.hh.

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
size_type mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::size (  void    )  const [inline]
 

Returns the number of nodes. Complexity is like TNode::size().

Returns:
The number of nodes.

Definition at line 1219 of file general_tree.hh.

References mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::size_type.

Referenced by mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::copy().

template<typename TItem, template< typename TItemA > class TAllocator, typename TNode>
void mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::swap (  TGeneralTree< TItem, TAllocator, TNode > &    rtTREE )  [inline]
 

Swaps tree with rtTREE.

Parameters:
rtTREE  Tree to swap to.
Postcondition:
( old (*this) == rtTREE )
( old (*rtTREE) == *this )

Definition at line 1236 of file general_tree.hh.

References mpcl::util::collection::TGeneralTree< TItem, TAllocator, TNode >::qtRootNode.

The documentation for this class was generated from the following file:
Generated on Mon Oct 13 02:35:27 2003 for MPCL by doxygen1.2.18