aGrUM  0.13.2
indexedTree_tpl.h
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005 by Christophe GONZALES and Pierre-Henri WUILLEMIN *
3  * {prenom.nom}_at_lip6.fr *
4  * *
5  * This program is free software; you can redistribute it and/or modify *
6  * it under the terms of the GNU General Public License as published by *
7  * the Free Software Foundation; either version 2 of the License, or *
8  * (at your option) any later version. *
9  * *
10  * This program is distributed in the hope that it will be useful, *
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13  * GNU General Public License for more details. *
14  * *
15  * You should have received a copy of the GNU General Public License *
16  * along with this program; if not, write to the *
17  * Free Software Foundation, Inc., *
18  * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
19  ***************************************************************************/
27 // to ease IDE parser
28 #include <agrum/core/indexedTree.h>
29 
30 namespace gum {
31  /* =========================================================================*/
32  /* =========================================================================*/
33  /* === IMPLEMENTATION OF NODES FOR GENERIC TREE (DATA) STRUCTURE === */
34  /* =========================================================================*/
35  /* =========================================================================*/
36 
37  // creates a tree with one node (with or without data)
38 
39  template < typename Key, typename Data >
40  IndexedTree< Key, Data >::IndexedTree(const Key& theKey, Data* theData) :
41  key(theKey), data(theData), parent(0) {
42  // for debugging purposes
43  GUM_CONSTRUCTOR(IndexedTree);
44  }
45 
46  // creates a tree with one node (with or without data)
47 
48  template < typename Key, typename Data >
49  IndexedTree< Key, Data >::IndexedTree(Data* theData) : data(theData), parent(0) {
50  // for debugging purposes
51  GUM_CONSTRUCTOR(IndexedTree);
52  }
53 
54  // creates a tree with one node with data
55 
56  template < typename Key, typename Data >
57  IndexedTree< Key, Data >::IndexedTree(const Key& theKey, const Data& theData) :
58  key(theKey), data(new Data(theData)), parent(0) {
59  // for debugging purposes
60  GUM_CONSTRUCTOR(IndexedTree);
61  }
62 
63  // copy constructor
64 
65  template < typename Key, typename Data >
67  key(from.key), data(0), parent(0) {
68  // for debugging purposes
69  GUM_CONS_CPY(IndexedTree);
70 
71  try {
72  // create the data of the node
73  if (from.data) data = new Data(*from.data);
74 
75  // create and link properly the children
76  children = from.children;
77 
79  children.begin();
80  iter != children.end();
81  ++iter)
82  iter->parent = this;
83  } catch (...) {
84  if (data) delete data;
85 
86  children.clear();
87 
88  throw;
89  }
90  }
91 
92  // copy operator
93 
94  template < typename Key, typename Data >
97  // avoid self assignment
98  if (this != &from) {
99  // for debugging purposes
100  GUM_OP_CPY(IndexedTree);
101 
102  try {
103  key = from.key;
104 
105  if (data) delete data;
106 
107  if (from.data)
108  data = new Data(*from.data);
109  else
110  data = 0;
111 
112  children = from.children;
113 
115  children.begin();
116  iter != children.end();
117  ++iter)
118  iter->parent = this;
119  } catch (...) {
120  if (data) delete data;
121 
122  children.clear();
123 
124  throw;
125  }
126  }
127 
128  return *this;
129  }
130 
131  // destructor
132 
133  template < typename Key, typename Data >
135  // for debugging purposes
136  GUM_DESTRUCTOR(IndexedTree);
137 
138  if (data) delete data;
139  }
140 
141  // adds a new node into the tree
142 
143  template < typename Key, typename Data >
144  void IndexedTree< Key, Data >::insertNode(const std::vector< Key >& index,
145  const Data* theData) {
146  // parse the tree until we are on the proper index. Then, insert the new
147  // node.
148  // current_node is a pointer on the node of the tree corresponding to
149  // position
150  // i in vector index. When i+2 < index.size(), we need go down into the tree
151  // structure before we can insert the new node
152  IndexedTree< Key, Data >* current_node = this;
153  unsigned int i;
154 
155  for (i = 0; i + 1 < index.size(); ++i) {
156  // if the node that should be on the path between the root of the tree and
157  // the node that we wish to insert does not exist, create it
158  if (!children.exists(index[i])) {
159  IndexedTree< Key, Data >* new_node =
160  new IndexedTree< Key, Data >(index[i], (Data*)0);
161  current_node->children.insert(index[i], new_node);
162  new_node->parent = this;
163  current_node = new_node;
164  } else
165  current_node = current_node->children[index[i]];
166  }
167 
168  // here, we can insert the new node. if ind + 1 == index.size(), this means
169  // that
170  // the index vector was not empty, else the vector was empty and we are at
171  // the
172  // root of the tree
173  if (i + 1 == index.size()) {
174  // if the node to be inserted already exist, throw an exception
175  if (current_node->children.exists(index[i])) {
176  GUM_ERROR(DuplicateElement, "the indexed tree already contains the node");
177  }
178 
179  // here, the node to be inserted does not exist, so we must create it
180  IndexedTree< Key, Data >* new_node =
181  new IndexedTree< Key, Data >(index[i], const_cast< Data* >(theData));
182 
183  current_node->children.insert(index[i], new_node);
184 
185  new_node->parent = current_node;
186  } else {
187  // here, the node to be inserted is the root of the tree (so it already
188  // exists)
189  GUM_ERROR(DuplicateElement, "the indexed tree already contains the node");
190  }
191  }
192 
193  // adds a new node into the tree
194 
195  template < typename Key, typename Data >
196  void IndexedTree< Key, Data >::insertNode(const std::vector< Key >& index,
197  const Data& theData) {
198  // parse the tree until we are on the proper index. Then, insert the new
199  // node.
200  // current_node is a pointer on the node of the tree corresponding to
201  // position
202  // i in vector index. When i+2 < index.size(), we need go down into the tree
203  // structure before we can insert the new node
204  IndexedTree< Key, Data >* current_node = this;
205  unsigned int i;
206 
207  for (i = 0; i + 1 < index.size(); ++i) {
208  // if the node that should be on the path between the root of the tree and
209  // the node that we wish to insert does not exist, create it
210  if (!children.exists(index[i])) {
211  IndexedTree< Key, Data >* new_node =
212  new IndexedTree< Key, Data >(index[i], (Data*)0);
213  current_node->children.insert(index[i], new_node);
214  new_node->parent = this;
215  current_node = new_node;
216  } else
217  current_node = current_node->children[index[i]];
218  }
219 
220  // here, we can insert the new node. if ind + 1 == index.size(), this means
221  // that
222  // the index vector was not empty, else the vector was empty and we are at
223  // the
224  // root of the tree
225  if (i + 1 == index.size()) {
226  // if the node to be inserted already exist, throw an exception
227  if (current_node->children.exists(index[i])) {
228  GUM_ERROR(DuplicateElement, "the indexed tree already contains the node");
229  }
230 
231  // here, the node to be inserted does not exist, so we must create it
232  IndexedTree< Key, Data >* new_node =
233  new IndexedTree< Key, Data >(index[i], theData);
234 
235  current_node->children.insert(index[i], new_node);
236 
237  new_node->parent = current_node;
238  } else {
239  // here, the node to be inserted is the root of the tree (so it already
240  // exists)
241  GUM_ERROR(DuplicateElement, "the indexed tree already contains the node");
242  }
243  }
244 
245  // updates the value of a node (or adds it if it does not already exist)
246 
247  template < typename Key, typename Data >
248  void IndexedTree< Key, Data >::setNode(const std::vector< Key >& index,
249  Data* theData) {
250  // parse the tree until we are on the proper index. Then, insert the new
251  // node.
252  // current_node is a pointer on the node of the tree corresponding to
253  // position
254  // i in vector index. When i+2 < index.size(), we need go down into the tree
255  // structure before we can insert the new node
256  IndexedTree< Key, Data >* current_node = this;
257  unsigned int i;
258 
259  for (i = 0; i + 1 < index.size(); ++i) {
260  // if the node that should be on the path between the root of the tree and
261  // the node that we wish to insert does not exist, create it
262  if (!children.exists(index[i])) {
263  IndexedTree< Key, Data >* new_node =
264  new IndexedTree< Key, Data >(index[i], (Data*)0);
265  current_node->children.insert(index[i], new_node);
266  new_node->parent = this;
267  current_node = new_node;
268  } else
269  current_node = current_node->children[index[i]];
270  }
271 
272  // here, we can set the new node. if ind + 1 == index.size(), this means
273  // that
274  // the index vector was not empty, else the vector was empty and we are at
275  // the
276  // root of the tree
277  if (i + 1 == index.size()) {
278  // if the node to be set does not exist, create it, else modify it
279  if (current_node->children.exists(index[i])) {
280  IndexedTree< Key, Data >* node = current_node->children[index[i]];
281 
282  if (node->data) delete node->data;
283 
284  node->data = theData;
285  } else {
286  // here, the node tobe set does not exist, so we must create it
287  IndexedTree< Key, Data >* new_node =
288  new IndexedTree< Key, Data >(index[i], theData);
289  current_node->children.insert(index[i], new_node);
290  new_node->parent = current_node;
291  }
292  } else {
293  // here, the node to be set is the root of the tree (so it does already
294  // exist
295  if (data) delete data;
296 
297  data = theData;
298  }
299  }
300 
301  // updates the value of a node (or adds it if it does not already exist)
302 
303  template < typename Key, typename Data >
304  void IndexedTree< Key, Data >::setNode(const std::vector< Key >& index,
305  const Data& theData) {
306  // parse the tree until we are on the proper index. Then, insert the new
307  // node.
308  // current_node is a pointer on the node of the tree corresponding to
309  // position
310  // i in vector index. When i+2 < index.size(), we need go down into the tree
311  // structure before we can insert the new node
312  IndexedTree< Key, Data >* current_node = this;
313  unsigned int i;
314 
315  for (i = 0; i + 1 < index.size(); ++i) {
316  // if the node that should be on the path between the root of the tree and
317  // the node that we wish to insert does not exist, create it
318  if (!children.exists(index[i])) {
319  IndexedTree< Key, Data >* new_node =
320  new IndexedTree< Key, Data >(index[i], (Data*)0);
321  current_node->children.insert(index[i], new_node);
322  new_node->parent = this;
323  current_node = new_node;
324  } else
325  current_node = current_node->children[index[i]];
326  }
327 
328  // here, we can set the new node. if ind + 1 == index.size(), this means
329  // that
330  // the index vector was not empty, else the vector was empty and we are at
331  // the
332  // root of the tree
333  if (i + 1 == index.size()) {
334  // if the node to be set does not exist, create it, else modify it
335  if (current_node->children.exists(index[i])) {
336  IndexedTree< Key, Data >* node = current_node->children[index[i]];
337 
338  if (node->data) delete node->data;
339 
340  node->data = new Data(theData);
341  } else {
342  // here, the node tobe set does not exist, so we must create it
343  IndexedTree< Key, Data >* new_node =
344  new IndexedTree< Key, Data >(index[i], theData);
345  current_node->children.insert(index[i], new_node);
346  new_node->parent = current_node;
347  }
348  } else {
349  // here, the node to be set is the root of the tree (so it does already
350  // exist
351  if (data) delete data;
352 
353  data = new Data(theData);
354  }
355  }
356 
357  // returns the value of a given test from the cache
358 
359  template < typename Key, typename Data >
360  INLINE Data&
361  IndexedTree< Key, Data >::getData(const std::vector< Key >& index) const {
362  IndexedTree< Key, Data >* current_node =
363  const_cast< IndexedTree< Key, Data >* >(this);
364 
365  for (unsigned int i = 0; i < index.size(); ++i)
366  current_node = current_node->children[index[i]];
367 
368  if (data == 0) { GUM_ERROR(NotFound, "the datum could not be found"); }
369 
370  return *(current_node->data);
371  }
372 
373  // returns a given node of the tree
374 
375  template < typename Key, typename Data >
377  IndexedTree< Key, Data >::getNode(const std::vector< Key >& index) const {
378  IndexedTree< Key, Data >* current_node =
379  const_cast< IndexedTree< Key, Data >* >(this);
380 
381  for (unsigned int i = 0; i < index.size(); ++i)
382  current_node = current_node->children[index[i]];
383 
384  return *current_node;
385  }
386 
387 } /* namespace gum */
Data & getData(const std::vector< Key > &index) const
Returns the value of a given node of the tree.
The class for storing the nodes of the Arborescence.
Definition: indexedTree.h:50
IndexedTree< Key, Data > * parent
The parent of the node.
Definition: indexedTree.h:186
IndexedTree(Data *data=nullptr)
Creates a tree with one node with or without data.
HashTable< Key, IndexedTree< Key, Data > * > children
The list of children nodes of the current node.
Definition: indexedTree.h:189
void insertNode(const std::vector< Key > &index, const Data *data)
Adds a new node into the tree.
Data * data
The data stored into the node.
Definition: indexedTree.h:183
Safe Iterators for hashtables.
Definition: hashTable.h:2217
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
IndexedTree< Key, Data > & operator=(const IndexedTree< Key, Data > &from)
Copy operator.
void setNode(const std::vector< Key > &index, Data *data)
Updates the value of a node (or adds it if it does not already exist).
Key key
The key of the current node.
Definition: indexedTree.h:180
Class for storing trees (as data structures, not graphs).
IndexedTree< Key, Data > & getNode(const std::vector< Key > &index) const
Returns a given node of the tree.
~IndexedTree()
Class destructor.
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66