aGrUM  0.15.0
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 53 of file indexedTree.h.

Constructor & Destructor Documentation

◆ IndexedTree() [1/4]

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 52 of file indexedTree_tpl.h.

52  : data(theData), parent(0) {
53  // for debugging purposes
54  GUM_CONSTRUCTOR(IndexedTree);
55  }
IndexedTree< Key, Data > * parent
The parent of the node.
Definition: indexedTree.h:189
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:186

◆ IndexedTree() [2/4]

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 43 of file indexedTree_tpl.h.

43  :
44  key(theKey), data(theData), parent(0) {
45  // for debugging purposes
46  GUM_CONSTRUCTOR(IndexedTree);
47  }
IndexedTree< Key, Data > * parent
The parent of the node.
Definition: indexedTree.h:189
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:186
Key key
The key of the current node.
Definition: indexedTree.h:183

◆ IndexedTree() [3/4]

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 60 of file indexedTree_tpl.h.

60  :
61  key(theKey), data(new Data(theData)), parent(0) {
62  // for debugging purposes
63  GUM_CONSTRUCTOR(IndexedTree);
64  }
IndexedTree< Key, Data > * parent
The parent of the node.
Definition: indexedTree.h:189
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:186
Key key
The key of the current node.
Definition: indexedTree.h:183

◆ IndexedTree() [4/4]

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 69 of file indexedTree_tpl.h.

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

69  :
70  key(from.key), data(0), parent(0) {
71  // for debugging purposes
72  GUM_CONS_CPY(IndexedTree);
73 
74  try {
75  // create the data of the node
76  if (from.data) data = new Data(*from.data);
77 
78  // create and link properly the children
79  children = from.children;
80 
81  for (HashTableIteratorSafe< Key, IndexedTree< Key, Data > > iter =
82  children.begin();
83  iter != children.end();
84  ++iter)
85  iter->parent = this;
86  } catch (...) {
87  if (data) delete data;
88 
89  children.clear();
90 
91  throw;
92  }
93  }
IndexedTree< Key, Data > * parent
The parent of the node.
Definition: indexedTree.h:189
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:192
Data * data
The data stored into the node.
Definition: indexedTree.h:186
Key key
The key of the current node.
Definition: indexedTree.h:183
+ Here is the call graph for this function:

◆ ~IndexedTree()

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

Class destructor.

Definition at line 137 of file indexedTree_tpl.h.

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

137  {
138  // for debugging purposes
139  GUM_DESTRUCTOR(IndexedTree);
140 
141  if (data) delete data;
142  }
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:186

Member Function Documentation

◆ getData()

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 364 of file indexedTree_tpl.h.

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

364  {
365  IndexedTree< Key, Data >* current_node =
366  const_cast< IndexedTree< Key, Data >* >(this);
367 
368  for (unsigned int i = 0; i < index.size(); ++i)
369  current_node = current_node->children[index[i]];
370 
371  if (data == 0) { GUM_ERROR(NotFound, "the datum could not be found"); }
372 
373  return *(current_node->data);
374  }
Data * data
The data stored into the node.
Definition: indexedTree.h:186
#define GUM_ERROR(type, msg)
Definition: exceptions.h:55

◆ getNode()

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 380 of file indexedTree_tpl.h.

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

380  {
381  IndexedTree< Key, Data >* current_node =
382  const_cast< IndexedTree< Key, Data >* >(this);
383 
384  for (unsigned int i = 0; i < index.size(); ++i)
385  current_node = current_node->children[index[i]];
386 
387  return *current_node;
388  }

◆ insertNode() [1/2]

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 147 of file indexedTree_tpl.h.

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

148  {
149  // parse the tree until we are on the proper index. Then, insert the new
150  // node.
151  // current_node is a pointer on the node of the tree corresponding to
152  // position
153  // i in vector index. When i+2 < index.size(), we need go down into the tree
154  // structure before we can insert the new node
155  IndexedTree< Key, Data >* current_node = this;
156  unsigned int i;
157 
158  for (i = 0; i + 1 < index.size(); ++i) {
159  // if the node that should be on the path between the root of the tree and
160  // the node that we wish to insert does not exist, create it
161  if (!children.exists(index[i])) {
162  IndexedTree< Key, Data >* new_node =
163  new IndexedTree< Key, Data >(index[i], (Data*)0);
164  current_node->children.insert(index[i], new_node);
165  new_node->parent = this;
166  current_node = new_node;
167  } else
168  current_node = current_node->children[index[i]];
169  }
170 
171  // here, we can insert the new node. if ind + 1 == index.size(), this means
172  // that
173  // the index vector was not empty, else the vector was empty and we are at
174  // the
175  // root of the tree
176  if (i + 1 == index.size()) {
177  // if the node to be inserted already exist, throw an exception
178  if (current_node->children.exists(index[i])) {
179  GUM_ERROR(DuplicateElement, "the indexed tree already contains the node");
180  }
181 
182  // here, the node to be inserted does not exist, so we must create it
183  IndexedTree< Key, Data >* new_node =
184  new IndexedTree< Key, Data >(index[i], const_cast< Data* >(theData));
185 
186  current_node->children.insert(index[i], new_node);
187 
188  new_node->parent = current_node;
189  } else {
190  // here, the node to be inserted is the root of the tree (so it already
191  // exists)
192  GUM_ERROR(DuplicateElement, "the indexed tree already contains the node");
193  }
194  }
HashTable< Key, IndexedTree< Key, Data > *> children
The list of children nodes of the current node.
Definition: indexedTree.h:192
#define GUM_ERROR(type, msg)
Definition: exceptions.h:55

◆ insertNode() [2/2]

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 199 of file indexedTree_tpl.h.

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

200  {
201  // parse the tree until we are on the proper index. Then, insert the new
202  // node.
203  // current_node is a pointer on the node of the tree corresponding to
204  // position
205  // i in vector index. When i+2 < index.size(), we need go down into the tree
206  // structure before we can insert the new node
207  IndexedTree< Key, Data >* current_node = this;
208  unsigned int i;
209 
210  for (i = 0; i + 1 < index.size(); ++i) {
211  // if the node that should be on the path between the root of the tree and
212  // the node that we wish to insert does not exist, create it
213  if (!children.exists(index[i])) {
214  IndexedTree< Key, Data >* new_node =
215  new IndexedTree< Key, Data >(index[i], (Data*)0);
216  current_node->children.insert(index[i], new_node);
217  new_node->parent = this;
218  current_node = new_node;
219  } else
220  current_node = current_node->children[index[i]];
221  }
222 
223  // here, we can insert the new node. if ind + 1 == index.size(), this means
224  // that
225  // the index vector was not empty, else the vector was empty and we are at
226  // the
227  // root of the tree
228  if (i + 1 == index.size()) {
229  // if the node to be inserted already exist, throw an exception
230  if (current_node->children.exists(index[i])) {
231  GUM_ERROR(DuplicateElement, "the indexed tree already contains the node");
232  }
233 
234  // here, the node to be inserted does not exist, so we must create it
235  IndexedTree< Key, Data >* new_node =
236  new IndexedTree< Key, Data >(index[i], theData);
237 
238  current_node->children.insert(index[i], new_node);
239 
240  new_node->parent = current_node;
241  } else {
242  // here, the node to be inserted is the root of the tree (so it already
243  // exists)
244  GUM_ERROR(DuplicateElement, "the indexed tree already contains the node");
245  }
246  }
HashTable< Key, IndexedTree< Key, Data > *> children
The list of children nodes of the current node.
Definition: indexedTree.h:192
#define GUM_ERROR(type, msg)
Definition: exceptions.h:55

◆ operator=()

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 99 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().

99  {
100  // avoid self assignment
101  if (this != &from) {
102  // for debugging purposes
103  GUM_OP_CPY(IndexedTree);
104 
105  try {
106  key = from.key;
107 
108  if (data) delete data;
109 
110  if (from.data)
111  data = new Data(*from.data);
112  else
113  data = 0;
114 
115  children = from.children;
116 
117  for (HashTableIteratorSafe< Key, IndexedTree< Key, Data > > iter =
118  children.begin();
119  iter != children.end();
120  ++iter)
121  iter->parent = this;
122  } catch (...) {
123  if (data) delete data;
124 
125  children.clear();
126 
127  throw;
128  }
129  }
130 
131  return *this;
132  }
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:192
Data * data
The data stored into the node.
Definition: indexedTree.h:186
Key key
The key of the current node.
Definition: indexedTree.h:183
+ Here is the caller graph for this function:

◆ setNode() [1/2]

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 251 of file indexedTree_tpl.h.

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

252  {
253  // parse the tree until we are on the proper index. Then, insert the new
254  // node.
255  // current_node is a pointer on the node of the tree corresponding to
256  // position
257  // i in vector index. When i+2 < index.size(), we need go down into the tree
258  // structure before we can insert the new node
259  IndexedTree< Key, Data >* current_node = this;
260  unsigned int i;
261 
262  for (i = 0; i + 1 < index.size(); ++i) {
263  // if the node that should be on the path between the root of the tree and
264  // the node that we wish to insert does not exist, create it
265  if (!children.exists(index[i])) {
266  IndexedTree< Key, Data >* new_node =
267  new IndexedTree< Key, Data >(index[i], (Data*)0);
268  current_node->children.insert(index[i], new_node);
269  new_node->parent = this;
270  current_node = new_node;
271  } else
272  current_node = current_node->children[index[i]];
273  }
274 
275  // here, we can set the new node. if ind + 1 == index.size(), this means
276  // that
277  // the index vector was not empty, else the vector was empty and we are at
278  // the
279  // root of the tree
280  if (i + 1 == index.size()) {
281  // if the node to be set does not exist, create it, else modify it
282  if (current_node->children.exists(index[i])) {
283  IndexedTree< Key, Data >* node = current_node->children[index[i]];
284 
285  if (node->data) delete node->data;
286 
287  node->data = theData;
288  } else {
289  // here, the node tobe set does not exist, so we must create it
290  IndexedTree< Key, Data >* new_node =
291  new IndexedTree< Key, Data >(index[i], theData);
292  current_node->children.insert(index[i], new_node);
293  new_node->parent = current_node;
294  }
295  } else {
296  // here, the node to be set is the root of the tree (so it does already
297  // exist
298  if (data) delete data;
299 
300  data = theData;
301  }
302  }
HashTable< Key, IndexedTree< Key, Data > *> children
The list of children nodes of the current node.
Definition: indexedTree.h:192
Data * data
The data stored into the node.
Definition: indexedTree.h:186

◆ setNode() [2/2]

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 307 of file indexedTree_tpl.h.

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

308  {
309  // parse the tree until we are on the proper index. Then, insert the new
310  // node.
311  // current_node is a pointer on the node of the tree corresponding to
312  // position
313  // i in vector index. When i+2 < index.size(), we need go down into the tree
314  // structure before we can insert the new node
315  IndexedTree< Key, Data >* current_node = this;
316  unsigned int i;
317 
318  for (i = 0; i + 1 < index.size(); ++i) {
319  // if the node that should be on the path between the root of the tree and
320  // the node that we wish to insert does not exist, create it
321  if (!children.exists(index[i])) {
322  IndexedTree< Key, Data >* new_node =
323  new IndexedTree< Key, Data >(index[i], (Data*)0);
324  current_node->children.insert(index[i], new_node);
325  new_node->parent = this;
326  current_node = new_node;
327  } else
328  current_node = current_node->children[index[i]];
329  }
330 
331  // here, we can set the new node. if ind + 1 == index.size(), this means
332  // that
333  // the index vector was not empty, else the vector was empty and we are at
334  // the
335  // root of the tree
336  if (i + 1 == index.size()) {
337  // if the node to be set does not exist, create it, else modify it
338  if (current_node->children.exists(index[i])) {
339  IndexedTree< Key, Data >* node = current_node->children[index[i]];
340 
341  if (node->data) delete node->data;
342 
343  node->data = new Data(theData);
344  } else {
345  // here, the node tobe set does not exist, so we must create it
346  IndexedTree< Key, Data >* new_node =
347  new IndexedTree< Key, Data >(index[i], theData);
348  current_node->children.insert(index[i], new_node);
349  new_node->parent = current_node;
350  }
351  } else {
352  // here, the node to be set is the root of the tree (so it does already
353  // exist
354  if (data) delete data;
355 
356  data = new Data(theData);
357  }
358  }
HashTable< Key, IndexedTree< Key, Data > *> children
The list of children nodes of the current node.
Definition: indexedTree.h:192
Data * data
The data stored into the node.
Definition: indexedTree.h:186

Member Data Documentation

◆ children

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

◆ data

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

◆ key

template<typename Key, typename Data>
Key gum::IndexedTree< Key, Data >::key
private

The key of the current node.

Definition at line 183 of file indexedTree.h.

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

◆ parent

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

The parent of the node.

Definition at line 189 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: