aGrUM  0.13.2
gum::IndexedTree< Key, Data > Class Template Reference

The class for storing the nodes of the Arborescence. More...

#include <agrum/core/indexedTree.h>

+ Collaboration diagram for gum::IndexedTree< Key, Data >:

Public Member Functions

Constructors / Destructors
 IndexedTree (Data *data=nullptr)
 Creates a tree with one node with or without data. More...
 
 IndexedTree (const Key &theKey, Data *data=nullptr)
 Creates a tree with one node (with or without data). More...
 
 IndexedTree (const Key &theKey, const Data &data)
 Creates a tree with one node with data. More...
 
 IndexedTree (const IndexedTree< Key, Data > &from)
 Copy constructor. More...
 
IndexedTree< Key, Data > & operator= (const IndexedTree< Key, Data > &from)
 Copy operator. More...
 
 ~IndexedTree ()
 Class destructor. More...
 
Accessors / Modifiers
void insertNode (const std::vector< Key > &index, const Data *data)
 Adds a new node into the tree. More...
 
void insertNode (const std::vector< Key > &index, const Data &data)
 Adds a new node into the tree. More...
 
void setNode (const std::vector< Key > &index, Data *data)
 Updates the value of a node (or adds it if it does not already exist). More...
 
void setNode (const std::vector< Key > &index, const Data &data)
 Updates the value of a node (or adds it if it does not already exist). More...
 
Data & getData (const std::vector< Key > &index) const
 Returns the value of a given node of the tree. More...
 
IndexedTree< Key, Data > & getNode (const std::vector< Key > &index) const
 Returns a given node of the tree. More...
 

Detailed Description

template<typename Key, typename Data>
class gum::IndexedTree< Key, Data >

The class for storing the nodes of the Arborescence.

Template Parameters
KeyThe tree's keys type.
DataThe tree's values type.

Definition at line 50 of file indexedTree.h.

Constructor & Destructor Documentation

template<typename Key , typename Data >
gum::IndexedTree< Key, Data >::IndexedTree ( Data *  data = nullptr)

Creates a tree with one node with or without data.

If data equals the nullptr, then tree is created with one node without data.

Parameters
dataAdds data as the root of the tree.

Definition at line 49 of file indexedTree_tpl.h.

49  : data(theData), parent(0) {
50  // for debugging purposes
51  GUM_CONSTRUCTOR(IndexedTree);
52  }
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.
Data * data
The data stored into the node.
Definition: indexedTree.h:183
template<typename Key , typename Data >
gum::IndexedTree< Key, Data >::IndexedTree ( const Key &  theKey,
Data *  data = nullptr 
)

Creates a tree with one node (with or without data).

The parameters are inserted directly into the tree, i.e., no copy is performed. For copies of key and data to occur, use the constructor with const& parameters.

If data equals the nullptr, then tree is created with one node without data.

Parameters
theKeyThe data's key.
dataThe data added to the tree.

Definition at line 40 of file indexedTree_tpl.h.

40  :
41  key(theKey), data(theData), parent(0) {
42  // for debugging purposes
43  GUM_CONSTRUCTOR(IndexedTree);
44  }
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.
Data * data
The data stored into the node.
Definition: indexedTree.h:183
Key key
The key of the current node.
Definition: indexedTree.h:180
template<typename Key , typename Data >
gum::IndexedTree< Key, Data >::IndexedTree ( const Key &  theKey,
const Data &  data 
)

Creates a tree with one node with data.

The key and data are copied into the tree. If you do not want any copy, use the constructor with the pointers parameters.

Parameters
theKeyThe data's key.
dataThe data added to the tree.

Definition at line 57 of file indexedTree_tpl.h.

57  :
58  key(theKey), data(new Data(theData)), parent(0) {
59  // for debugging purposes
60  GUM_CONSTRUCTOR(IndexedTree);
61  }
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.
Data * data
The data stored into the node.
Definition: indexedTree.h:183
Key key
The key of the current node.
Definition: indexedTree.h:180
template<typename Key , typename Data >
gum::IndexedTree< Key, Data >::IndexedTree ( const IndexedTree< Key, Data > &  from)

Copy constructor.

Parameters
fromThe gum::IndexedTree to copy.

Definition at line 66 of file indexedTree_tpl.h.

References gum::IndexedTree< Key, Data >::children, gum::IndexedTree< Key, Data >::data, and gum::IndexedTree< Key, Data >::operator=().

66  :
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 
78  for (HashTableIteratorSafe< Key, IndexedTree< Key, Data > > iter =
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  }
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
Data * data
The data stored into the node.
Definition: indexedTree.h:183
Key key
The key of the current node.
Definition: indexedTree.h:180

+ Here is the call graph for this function:

template<typename Key , typename Data >
gum::IndexedTree< Key, Data >::~IndexedTree ( )

Class destructor.

Definition at line 134 of file indexedTree_tpl.h.

References gum::IndexedTree< Key, Data >::data.

134  {
135  // for debugging purposes
136  GUM_DESTRUCTOR(IndexedTree);
137 
138  if (data) delete data;
139  }
IndexedTree(Data *data=nullptr)
Creates a tree with one node with or without data.
Data * data
The data stored into the node.
Definition: indexedTree.h:183

Member Function Documentation

template<typename Key , typename Data >
INLINE Data & gum::IndexedTree< Key, Data >::getData ( const std::vector< Key > &  index) const

Returns the value of a given node of the tree.

Parameters
indexThe node's index.
Returns
Returns the data at index.
Exceptions
NotFoundexception is thrown if the so-called value cannot be found in the tree.

Definition at line 361 of file indexedTree_tpl.h.

References gum::IndexedTree< Key, Data >::children, gum::IndexedTree< Key, Data >::data, and GUM_ERROR.

361  {
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  }
Data * data
The data stored into the node.
Definition: indexedTree.h:183
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66
template<typename Key , typename Data >
INLINE IndexedTree< Key, Data > & gum::IndexedTree< Key, Data >::getNode ( const std::vector< Key > &  index) const

Returns a given node of the tree.

Parameters
indexThe node's index.
Returns
Returns a given node of the tree.
Exceptions
NotFoundexception is thrown if the node we look for cannot be found in the tree.

Definition at line 377 of file indexedTree_tpl.h.

References gum::IndexedTree< Key, Data >::children.

377  {
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  }
template<typename Key , typename Data >
void gum::IndexedTree< Key, Data >::insertNode ( const std::vector< Key > &  index,
const Data *  data 
)

Adds a new node into the tree.

Parameters
indexThe node's index.
dataThe node's data.
Exceptions
DuplicateElementexception is thrown if a node with an identical index has already been entered into the tree. If, in this case, you would like the value of the to be updated, use function setNode instead.

Definition at line 144 of file indexedTree_tpl.h.

References gum::IndexedTree< Key, Data >::children, GUM_ERROR, and gum::IndexedTree< Key, Data >::parent.

145  {
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  }
HashTable< Key, IndexedTree< Key, Data > * > children
The list of children nodes of the current node.
Definition: indexedTree.h:189
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66
template<typename Key , typename Data >
void gum::IndexedTree< Key, Data >::insertNode ( const std::vector< Key > &  index,
const Data &  data 
)

Adds a new node into the tree.

Parameters
indexThe node's index.
dataThe node's data.
Exceptions
DuplicateElementexception is thrown if a node with an identical index has already been entered into the tree. If, in this case, you would like the value of the to be updated, use function setNode instead.

Definition at line 196 of file indexedTree_tpl.h.

References gum::IndexedTree< Key, Data >::children, GUM_ERROR, and gum::IndexedTree< Key, Data >::parent.

197  {
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  }
HashTable< Key, IndexedTree< Key, Data > * > children
The list of children nodes of the current node.
Definition: indexedTree.h:189
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66
template<typename Key , typename Data >
IndexedTree< Key, Data > & gum::IndexedTree< Key, Data >::operator= ( const IndexedTree< Key, Data > &  from)

Copy operator.

Parameters
fromThe gum::IndexedTree to copy.
Returns
Returns this gum::IndexedTree.

Definition at line 96 of file indexedTree_tpl.h.

References gum::IndexedTree< Key, Data >::children, gum::IndexedTree< Key, Data >::data, and gum::IndexedTree< Key, Data >::key.

Referenced by gum::IndexedTree< Key, Data >::IndexedTree().

96  {
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 
114  for (HashTableIteratorSafe< Key, IndexedTree< Key, Data > > iter =
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  }
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
Data * data
The data stored into the node.
Definition: indexedTree.h:183
Key key
The key of the current node.
Definition: indexedTree.h:180

+ Here is the caller graph for this function:

template<typename Key , typename Data >
void gum::IndexedTree< Key, Data >::setNode ( const std::vector< Key > &  index,
Data *  data 
)

Updates the value of a node (or adds it if it does not already exist).

Parameters
indexThe node's index.
dataThe node's data.

Definition at line 248 of file indexedTree_tpl.h.

References gum::IndexedTree< Key, Data >::children, gum::IndexedTree< Key, Data >::data, and gum::IndexedTree< Key, Data >::parent.

249  {
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  }
HashTable< Key, IndexedTree< Key, Data > * > children
The list of children nodes of the current node.
Definition: indexedTree.h:189
Data * data
The data stored into the node.
Definition: indexedTree.h:183
template<typename Key , typename Data >
void gum::IndexedTree< Key, Data >::setNode ( const std::vector< Key > &  index,
const Data &  data 
)

Updates the value of a node (or adds it if it does not already exist).

Parameters
indexThe node's index.
dataThe node's data.

Definition at line 304 of file indexedTree_tpl.h.

References gum::IndexedTree< Key, Data >::children, gum::IndexedTree< Key, Data >::data, and gum::IndexedTree< Key, Data >::parent.

305  {
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  }
HashTable< Key, IndexedTree< Key, Data > * > children
The list of children nodes of the current node.
Definition: indexedTree.h:189
Data * data
The data stored into the node.
Definition: indexedTree.h:183

Member Data Documentation

template<typename Key, typename Data>
HashTable< Key, IndexedTree< Key, Data >* > gum::IndexedTree< Key, Data >::children
private
template<typename Key, typename Data>
Data* gum::IndexedTree< Key, Data >::data
private
template<typename Key, typename Data>
Key gum::IndexedTree< Key, Data >::key
private

The key of the current node.

Definition at line 180 of file indexedTree.h.

Referenced by gum::IndexedTree< Key, Data >::operator=().

template<typename Key, typename Data>
IndexedTree< Key, Data >* gum::IndexedTree< Key, Data >::parent
private

The parent of the node.

Definition at line 186 of file indexedTree.h.

Referenced by gum::IndexedTree< Key, Data >::insertNode(), and gum::IndexedTree< Key, Data >::setNode().


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