claw::tree< T > Class Template Reference

A tree structure with any number of children. More...

#include <tree.hpp>

List of all members.

Public Types

typedef T value_type
 The type of the value stored in the nodes.
typedef tree< T > self_type
 The type of the current class.
typedef child_list::iterator iterator
typedef child_list::const_iterator const_iterator

Public Member Functions

 tree ()
 Default constructor.
 tree (const T &that)
 Constructor with initialization.
bool operator== (const self_type &that) const
 Equality operator.
bool is_leaf () const
 Tell if this node is a leaf (ie. it has no child).
self_typeadd_child (const T &v)
 Add a child to this node.
self_typeadd_child (const self_type &v)
 Add a child subtree to this node.
iterator find (const T &v)
 Search the first child having a given value.
const_iterator find (const T &v) const
 Search the first child having a given value.
iterator begin ()
 Get an iterator on the begining of the children.
iterator end ()
 Get an iterator just past the end of the children.
const_iterator begin () const
 Get a constant iterator on the begining of the children.
const_iterator end () const
 Get a constant iterator just past the end of the children.

Public Attributes

value
 The value in this node.

Private Types

typedef std::list< tree< T > > child_list
 The type of the list in which are stored the children.

Private Attributes

child_list m_child
 The children of this node.

Detailed Description

template<typename T>
class claw::tree< T >

A tree structure with any number of children.

Author:
Julien Jorge

Definition at line 42 of file tree.hpp.


Member Typedef Documentation

template<typename T>
typedef std::list< tree<T> > claw::tree< T >::child_list [private]

The type of the list in which are stored the children.

Definition at line 53 of file tree.hpp.

template<typename T>
typedef child_list::const_iterator claw::tree< T >::const_iterator

Definition at line 57 of file tree.hpp.

template<typename T>
typedef child_list::iterator claw::tree< T >::iterator

Definition at line 56 of file tree.hpp.

template<typename T>
typedef tree<T> claw::tree< T >::self_type

The type of the current class.

Definition at line 49 of file tree.hpp.

template<typename T>
typedef T claw::tree< T >::value_type

The type of the value stored in the nodes.

Definition at line 46 of file tree.hpp.


Constructor & Destructor Documentation

template<typename T >
claw::tree< T >::tree (  )  [inline]

Default constructor.

Definition at line 36 of file tree.tpp.

00037   : value()
00038 {
00039 
00040 } // tree::tree()

template<typename T>
claw::tree< T >::tree ( const T &  v  )  [inline, explicit]

Constructor with initialization.

Parameters:
v The value of the root node.

Definition at line 48 of file tree.tpp.

00049   : value(v)
00050 {
00051 
00052 } // tree::tree()


Member Function Documentation

template<typename T>
claw::tree< T >::self_type & claw::tree< T >::add_child ( const self_type v  )  [inline]

Add a child subtree to this node.

Parameters:
v The tree to add.

Definition at line 110 of file tree.tpp.

References claw::tree< T >::m_child.

00111 {
00112   m_child.push_back( v );
00113 } // tree::add_child()

template<typename T>
claw::tree< T >::self_type & claw::tree< T >::add_child ( const T &  v  )  [inline]

Add a child to this node.

Parameters:
v The value of the child to add.

Definition at line 97 of file tree.tpp.

References claw::tree< T >::m_child.

00098 {
00099   m_child.push_back( self_type(v) );
00100   return m_child.back();
00101 } // tree::add_child()

template<typename T >
claw::tree< T >::const_iterator claw::tree< T >::begin (  )  const [inline]

Get a constant iterator on the begining of the children.

Definition at line 180 of file tree.tpp.

References claw::tree< T >::m_child.

00181 {
00182   return const_iterator( m_child.begin() );
00183 } // tree::begin()

template<typename T >
claw::tree< T >::iterator claw::tree< T >::begin (  )  [inline]

Get an iterator on the begining of the children.

Definition at line 160 of file tree.tpp.

References claw::tree< T >::m_child.

00161 {
00162   return iterator( m_child.begin() );
00163 } // tree::begin()()

template<typename T >
claw::tree< T >::const_iterator claw::tree< T >::end (  )  const [inline]

Get a constant iterator just past the end of the children.

Definition at line 190 of file tree.tpp.

References claw::tree< T >::m_child.

00191 {
00192   return const_iterator( m_child.end() );
00193 } // tree::end()

template<typename T >
claw::tree< T >::iterator claw::tree< T >::end (  )  [inline]

Get an iterator just past the end of the children.

Definition at line 170 of file tree.tpp.

References claw::tree< T >::m_child.

Referenced by claw::tree< T >::find().

00171 {
00172   return iterator( m_child.end() );
00173 } // tree::end()

template<typename T>
claw::tree< T >::const_iterator claw::tree< T >::find ( const T &  v  )  const [inline]

Search the first child having a given value.

Parameters:
v The value of the child to find.

Definition at line 141 of file tree.tpp.

References claw::tree< T >::end(), and claw::tree< T >::m_child.

00142 {
00143   typename child_list::const_iterator it;
00144   bool found = false;
00145 
00146   for ( it=m_child.begin(); !found && (it!=end()) ; )
00147     if ( it->value == v )
00148       found = true;
00149     else
00150       ++it;
00151 
00152   return const_iterator( it );
00153 } // tree::find()

template<typename T>
claw::tree< T >::iterator claw::tree< T >::find ( const T &  v  )  [inline]

Search the first child having a given value.

Parameters:
v The value of the child to find.

Definition at line 121 of file tree.tpp.

References claw::tree< T >::end(), and claw::tree< T >::m_child.

00122 {
00123   typename child_list::iterator it;
00124   bool found = false;
00125 
00126   for ( it=m_child.begin(); !found && (it!=end()) ; )
00127     if ( it->value == v )
00128       found = true;
00129     else
00130       ++it;
00131 
00132   return iterator( it );
00133 } // tree::find()

template<typename T >
bool claw::tree< T >::is_leaf (  )  const [inline]

Tell if this node is a leaf (ie. it has no child).

Definition at line 86 of file tree.tpp.

References claw::tree< T >::m_child.

00087 {
00088   return m_child.empty();
00089 } // tree::is_leaf()

template<typename T >
bool claw::tree< T >::operator== ( const self_type that  )  const [inline]

Equality operator.

Parameters:
that The tree to compare to.

Definition at line 60 of file tree.tpp.

References claw::tree< T >::m_child, and claw::tree< T >::value.

00061 {
00062   bool result = ( value == that.value );
00063 
00064   if (result)
00065     {
00066       typename child_list::const_iterator it_me = m_child.begin();
00067       typename child_list::const_iterator it_him = that.m_child.begin();
00068       typename child_list::const_iterator eit_me = m_child.end();
00069       typename child_list::const_iterator eit_him = that.m_child.end();
00070   
00071       while ( result && (it_me!=eit_me) && (it_him!=eit_him) )
00072         result = (*it_me == *it_him);
00073 
00074       if ( (it_me!=eit_me) || (it_him!=eit_him) )
00075         result = false;
00076     }
00077 
00078   return result;
00079 } // tree::operator==()


Member Data Documentation

template<typename T>
child_list claw::tree< T >::m_child [private]
template<typename T>
T claw::tree< T >::value

The value in this node.

Definition at line 81 of file tree.hpp.

Referenced by claw::tree< T >::operator==().


The documentation for this class was generated from the following files:

Generated on 9 Nov 2009 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.6.1