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

#include <tree.hpp>

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_type &	add_child (const T &v)
	Add a child to this node.
self_type &	add_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
T	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 ( )

Default constructor.

Definition at line 36 of file tree.tpp.

  : value()
{

} // tree::tree()

template<typename T>

claw::tree< T >::tree ( const T & v ) [explicit]

Constructor with initialization.

Parameters:

v	The value of the root node.

Definition at line 48 of file tree.tpp.

  : value(v)
{

} // tree::tree()

Member Function Documentation

template<typename T>

claw::tree< T >::self_type & claw::tree< T >::add_child ( const T & v )

Add a child to this node.

Parameters:

v	The value of the child to add.

Definition at line 97 of file tree.tpp.

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

template<typename T>

claw::tree< T >::self_type & claw::tree< T >::add_child ( const self_type & v )

Add a child subtree to this node.

Parameters:

v	The tree to add.

Definition at line 110 of file tree.tpp.

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

template<typename T >

claw::tree< T >::const_iterator claw::tree< T >::begin ( ) const

Get a constant iterator on the begining of the children.

Definition at line 180 of file tree.tpp.

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

template<typename T >

claw::tree< T >::iterator claw::tree< T >::begin ( )

Get an iterator on the begining of the children.

Definition at line 160 of file tree.tpp.

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

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

template<typename T >

claw::tree< T >::iterator claw::tree< T >::end ( )

Get an iterator just past the end of the children.

Definition at line 170 of file tree.tpp.

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

template<typename T >

claw::tree< T >::const_iterator claw::tree< T >::end ( ) const

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

Definition at line 190 of file tree.tpp.

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

template<typename T>

claw::tree< T >::iterator claw::tree< T >::find ( const T & v )

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.

{
  typename child_list::iterator it;
  bool found = false;

  for ( it=m_child.begin(); !found && (it!=end()) ; )
    if ( it->value == v )
      found = true;
    else
      ++it;

  return iterator( it );
} // tree::find()

template<typename T>

claw::tree< T >::const_iterator claw::tree< T >::find ( const T & v ) const

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.

{
  typename child_list::const_iterator it;
  bool found = false;

  for ( it=m_child.begin(); !found && (it!=end()) ; )
    if ( it->value == v )
      found = true;
    else
      ++it;

  return const_iterator( it );
} // tree::find()

template<typename T >

bool claw::tree< T >::is_leaf ( ) const

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

Definition at line 86 of file tree.tpp.

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

template<typename T >

bool claw::tree< T >::operator== ( const self_type & that ) const

Equality operator.

Parameters:

that	The tree to compare to.

Definition at line 60 of file tree.tpp.

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

{
  bool result = ( value == that.value );

  if (result)
    {
      typename child_list::const_iterator it_me = m_child.begin();
      typename child_list::const_iterator it_him = that.m_child.begin();
      typename child_list::const_iterator eit_me = m_child.end();
      typename child_list::const_iterator eit_him = that.m_child.end();
  
      while ( result && (it_me!=eit_me) && (it_him!=eit_him) )
        result = (*it_me == *it_him);

      if ( (it_me!=eit_me) || (it_him!=eit_him) )
        result = false;
    }

  return result;
} // tree::operator==()