Claw  1.7.3
tree.tpp
1 /*
2  CLAW - a C++ Library Absolutely Wonderful
3 
4  CLAW is a free library without any particular aim but being useful to
5  anyone.
6 
7  Copyright (C) 2005-2011 Julien Jorge
8 
9  This library is free software; you can redistribute it and/or
10  modify it under the terms of the GNU Lesser General Public
11  License as published by the Free Software Foundation; either
12  version 2.1 of the License, or (at your option) any later version.
13 
14  This library is distributed in the hope that it will be useful,
15  but WITHOUT ANY WARRANTY; without even the implied warranty of
16  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17  Lesser General Public License for more details.
18 
19  You should have received a copy of the GNU Lesser General Public
20  License along with this library; if not, write to the Free Software
21  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 
23  contact: julien.jorge@gamned.org
24 */
25 /**
26  * \file tree.tpp
27  * \brief Implementation of the claw::tree class.
28  * \author Julien Jorge
29  */
30 
31 /*----------------------------------------------------------------------------*/
32 /**
33  * \brief Default constructor.
34  */
35 template<typename T>
36 claw::tree<T>::tree()
37  : value()
38 {
39 
40 } // tree::tree()
41 
42 /*----------------------------------------------------------------------------*/
43 /**
44  * \brief Constructor with initialization.
45  * \param v The value of the root node.
46  */
47 template<typename T>
48 claw::tree<T>::tree( const T& v )
49  : value(v)
50 {
51 
52 } // tree::tree()
53 
54 /*----------------------------------------------------------------------------*/
55 /**
56  * \brief Equality operator.
57  * \param that The tree to compare to.
58  */
59 template<typename T>
60 bool claw::tree<T>::operator==( const self_type& that ) const
61 {
62  bool result = ( value == that.value );
63 
64  if (result)
65  {
66  typename child_list::const_iterator it_me = m_child.begin();
67  typename child_list::const_iterator it_him = that.m_child.begin();
68  typename child_list::const_iterator eit_me = m_child.end();
69  typename child_list::const_iterator eit_him = that.m_child.end();
70 
71  while ( result && (it_me!=eit_me) && (it_him!=eit_him) )
72  result = (*it_me == *it_him);
73 
74  if ( (it_me!=eit_me) || (it_him!=eit_him) )
75  result = false;
76  }
77 
78  return result;
79 } // tree::operator==()
80 
81 /*----------------------------------------------------------------------------*/
82 /**
83  * \brief Tell if this node is a leaf (ie. it has no child).
84  */
85 template<typename T>
86 bool claw::tree<T>::is_leaf() const
87 {
88  return m_child.empty();
89 } // tree::is_leaf()
90 
91 /*----------------------------------------------------------------------------*/
92 /**
93  * \brief Add a child to this node.
94  * \param v The value of the child to add.
95  */
96 template<typename T>
97 typename claw::tree<T>::self_type& claw::tree<T>::add_child( const T& v )
98 {
99  m_child.push_back( self_type(v) );
100  return m_child.back();
101 } // tree::add_child()
102 
103 /*----------------------------------------------------------------------------*/
104 /**
105  * \brief Add a child subtree to this node.
106  * \param v The tree to add.
107  */
108 template<typename T>
109 typename claw::tree<T>::self_type&
110 claw::tree<T>::add_child( const self_type& v )
111 {
112  m_child.push_back( v );
113 } // tree::add_child()
114 
115 /*----------------------------------------------------------------------------*/
116 /**
117  * \brief Search the first child having a given value.
118  * \param v The value of the child to find.
119  */
120 template<typename T>
121 typename claw::tree<T>::iterator claw::tree<T>::find( const T& v )
122 {
123  typename child_list::iterator it;
124  bool found = false;
125 
126  for ( it=m_child.begin(); !found && (it!=end()) ; )
127  if ( it->value == v )
128  found = true;
129  else
130  ++it;
131 
132  return iterator( it );
133 } // tree::find()
134 
135 /*----------------------------------------------------------------------------*/
136 /**
137  * \brief Search the first child having a given value.
138  * \param v The value of the child to find.
139  */
140 template<typename T>
141 typename claw::tree<T>::const_iterator claw::tree<T>::find( const T& v ) const
142 {
143  typename child_list::const_iterator it;
144  bool found = false;
145 
146  for ( it=m_child.begin(); !found && (it!=end()) ; )
147  if ( it->value == v )
148  found = true;
149  else
150  ++it;
151 
152  return const_iterator( it );
153 } // tree::find()
154 
155 /*----------------------------------------------------------------------------*/
156 /**
157  * \brief Get an iterator on the begining of the children.
158  */
159 template<typename T>
160 typename claw::tree<T>::iterator claw::tree<T>::begin()
161 {
162  return iterator( m_child.begin() );
163 } // tree::begin()()
164 
165 /*----------------------------------------------------------------------------*/
166 /**
167  * \brief Get an iterator just past the end of the children.
168  */
169 template<typename T>
170 typename claw::tree<T>::iterator claw::tree<T>::end()
171 {
172  return iterator( m_child.end() );
173 } // tree::end()
174 
175 /*----------------------------------------------------------------------------*/
176 /**
177  * \brief Get a constant iterator on the begining of the children.
178  */
179 template<typename T>
180 typename claw::tree<T>::const_iterator claw::tree<T>::begin() const
181 {
182  return const_iterator( m_child.begin() );
183 } // tree::begin()
184 
185 /*----------------------------------------------------------------------------*/
186 /**
187  * \brief Get a constant iterator just past the end of the children.
188  */
189 template<typename T>
190 typename claw::tree<T>::const_iterator claw::tree<T>::end() const
191 {
192  return const_iterator( m_child.end() );
193 } // tree::end()