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

Key	The tree's keys type.
Data	The 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

data	Adds data as the root of the tree.

Definition at line 52 of file indexedTree_tpl.h.

                                                      : data(theData), parent(0) {
     // for debugging purposes
     GUM_CONSTRUCTOR(IndexedTree);
   }

◆ 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

theKey	The data's key.
data	The data added to the tree.

Definition at line 43 of file indexedTree_tpl.h.

                                                                         :
       key(theKey), data(theData), parent(0) {
     // for debugging purposes
     GUM_CONSTRUCTOR(IndexedTree);
   }

◆ 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

theKey	The data's key.
data	The data added to the tree.

Definition at line 60 of file indexedTree_tpl.h.

                                                                               :
       key(theKey), data(new Data(theData)), parent(0) {
     // for debugging purposes
     GUM_CONSTRUCTOR(IndexedTree);
   }

◆ IndexedTree() [4/4]

template<typename Key , typename Data >

gum::IndexedTree< Key, Data >::IndexedTree ( const IndexedTree< Key, Data > & from )

Copy constructor.

Parameters

from	The 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=().

                                                                             :
       key(from.key), data(0), parent(0) {
     // for debugging purposes
     GUM_CONS_CPY(IndexedTree);
 
     try {
       // create the data of the node
       if (from.data) data = new Data(*from.data);
 
       // create and link properly the children
       children = from.children;
 
       for (HashTableIteratorSafe< Key, IndexedTree< Key, Data > > iter =
               children.begin();
            iter != children.end();
            ++iter)
         iter->parent = this;
     } catch (...) {
       if (data) delete data;
 
       children.clear();
 
       throw;
     }
   }

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.

                                          {
     // for debugging purposes
     GUM_DESTRUCTOR(IndexedTree);
 
     if (data) delete data;
   }

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

index The node's index.

Returns: Returns the data at index.

Exceptions

NotFound exception 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.

                                                                               {
     IndexedTree< Key, Data >* current_node =
        const_cast< IndexedTree< Key, Data >* >(this);
 
     for (unsigned int i = 0; i < index.size(); ++i)
       current_node = current_node->children[index[i]];
 
     if (data == 0) { GUM_ERROR(NotFound, "the datum could not be found"); }
 
     return *(current_node->data);
   }

◆ 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

index The node's index.

Returns: Returns a given node of the tree.

Exceptions

NotFound exception 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.

                                                                               {
     IndexedTree< Key, Data >* current_node =
        const_cast< IndexedTree< Key, Data >* >(this);
 
     for (unsigned int i = 0; i < index.size(); ++i)
       current_node = current_node->children[index[i]];
 
     return *current_node;
   }

◆ 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

index	The node's index.
data	The node's data.

Exceptions

DuplicateElement exception 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.

                                                                                {
     // parse the tree until we are on the proper index. Then, insert the new
     // node.
     // current_node is a pointer on the node of the tree corresponding to
     // position
     // i in vector index. When i+2 < index.size(), we need go down into the tree
     // structure before we can insert the new node
     IndexedTree< Key, Data >* current_node = this;
     unsigned int              i;
 
     for (i = 0; i + 1 < index.size(); ++i) {
       // if the node that should be on the path between the root of the tree and
       // the node that we wish to insert does not exist, create it
       if (!children.exists(index[i])) {
         IndexedTree< Key, Data >* new_node =
            new IndexedTree< Key, Data >(index[i], (Data*)0);
         current_node->children.insert(index[i], new_node);
         new_node->parent = this;
         current_node = new_node;
       } else
         current_node = current_node->children[index[i]];
     }
 
     // here, we can insert the new node. if ind + 1 == index.size(), this means
     // that
     // the index vector was not empty, else the vector was empty and we are at
     // the
     // root of the tree
     if (i + 1 == index.size()) {
       // if the node to be inserted already exist, throw an exception
       if (current_node->children.exists(index[i])) {
         GUM_ERROR(DuplicateElement, "the indexed tree already contains the node");
       }
 
       // here, the node to be inserted does not exist, so we must create it
       IndexedTree< Key, Data >* new_node =
          new IndexedTree< Key, Data >(index[i], const_cast< Data* >(theData));
 
       current_node->children.insert(index[i], new_node);
 
       new_node->parent = current_node;
     } else {
       // here, the node to be inserted is the root of the tree (so it already
       // exists)
       GUM_ERROR(DuplicateElement, "the indexed tree already contains the node");
     }
   }

◆ 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

index	The node's index.
data	The node's data.

Exceptions

DuplicateElement exception 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.

                                                                                {
     // parse the tree until we are on the proper index. Then, insert the new
     // node.
     // current_node is a pointer on the node of the tree corresponding to
     // position
     // i in vector index. When i+2 < index.size(), we need go down into the tree
     // structure before we can insert the new node
     IndexedTree< Key, Data >* current_node = this;
     unsigned int              i;
 
     for (i = 0; i + 1 < index.size(); ++i) {
       // if the node that should be on the path between the root of the tree and
       // the node that we wish to insert does not exist, create it
       if (!children.exists(index[i])) {
         IndexedTree< Key, Data >* new_node =
            new IndexedTree< Key, Data >(index[i], (Data*)0);
         current_node->children.insert(index[i], new_node);
         new_node->parent = this;
         current_node = new_node;
       } else
         current_node = current_node->children[index[i]];
     }
 
     // here, we can insert the new node. if ind + 1 == index.size(), this means
     // that
     // the index vector was not empty, else the vector was empty and we are at
     // the
     // root of the tree
     if (i + 1 == index.size()) {
       // if the node to be inserted already exist, throw an exception
       if (current_node->children.exists(index[i])) {
         GUM_ERROR(DuplicateElement, "the indexed tree already contains the node");
       }
 
       // here, the node to be inserted does not exist, so we must create it
       IndexedTree< Key, Data >* new_node =
          new IndexedTree< Key, Data >(index[i], theData);
 
       current_node->children.insert(index[i], new_node);
 
       new_node->parent = current_node;
     } else {
       // here, the node to be inserted is the root of the tree (so it already
       // exists)
       GUM_ERROR(DuplicateElement, "the indexed tree already contains the node");
     }
   }

◆ operator=()

template<typename Key , typename Data >

IndexedTree< Key, Data > & gum::IndexedTree< Key, Data >::operator= ( const IndexedTree< Key, Data > & from )

Copy operator.

Parameters

from	The 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().

                                                                             {
     // avoid self assignment
     if (this != &from) {
       // for debugging purposes
       GUM_OP_CPY(IndexedTree);
 
       try {
         key = from.key;
 
         if (data) delete data;
 
         if (from.data)
           data = new Data(*from.data);
         else
           data = 0;
 
         children = from.children;
 
         for (HashTableIteratorSafe< Key, IndexedTree< Key, Data > > iter =
                 children.begin();
              iter != children.end();
              ++iter)
           iter->parent = this;
       } catch (...) {
         if (data) delete data;
 
         children.clear();
 
         throw;
       }
     }
 
     return *this;
   }

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

index	The node's index.
data	The 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.

                                                                             {
     // parse the tree until we are on the proper index. Then, insert the new
     // node.
     // current_node is a pointer on the node of the tree corresponding to
     // position
     // i in vector index. When i+2 < index.size(), we need go down into the tree
     // structure before we can insert the new node
     IndexedTree< Key, Data >* current_node = this;
     unsigned int              i;
 
     for (i = 0; i + 1 < index.size(); ++i) {
       // if the node that should be on the path between the root of the tree and
       // the node that we wish to insert does not exist, create it
       if (!children.exists(index[i])) {
         IndexedTree< Key, Data >* new_node =
            new IndexedTree< Key, Data >(index[i], (Data*)0);
         current_node->children.insert(index[i], new_node);
         new_node->parent = this;
         current_node = new_node;
       } else
         current_node = current_node->children[index[i]];
     }
 
     // here, we can set the new node. if ind + 1 == index.size(), this means
     // that
     // the index vector was not empty, else the vector was empty and we are at
     // the
     // root of the tree
     if (i + 1 == index.size()) {
       // if the node to be set does not exist, create it, else modify it
       if (current_node->children.exists(index[i])) {
         IndexedTree< Key, Data >* node = current_node->children[index[i]];
 
         if (node->data) delete node->data;
 
         node->data = theData;
       } else {
         // here, the node tobe set does not exist, so we must create it
         IndexedTree< Key, Data >* new_node =
            new IndexedTree< Key, Data >(index[i], theData);
         current_node->children.insert(index[i], new_node);
         new_node->parent = current_node;
       }
     } else {
       // here, the node to be set is the root of the tree (so it does already
       // exist
       if (data) delete data;
 
       data = theData;
     }
   }

◆ 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

index	The node's index.
data	The 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.

                                                                             {
     // parse the tree until we are on the proper index. Then, insert the new
     // node.
     // current_node is a pointer on the node of the tree corresponding to
     // position
     // i in vector index. When i+2 < index.size(), we need go down into the tree
     // structure before we can insert the new node
     IndexedTree< Key, Data >* current_node = this;
     unsigned int              i;
 
     for (i = 0; i + 1 < index.size(); ++i) {
       // if the node that should be on the path between the root of the tree and
       // the node that we wish to insert does not exist, create it
       if (!children.exists(index[i])) {
         IndexedTree< Key, Data >* new_node =
            new IndexedTree< Key, Data >(index[i], (Data*)0);
         current_node->children.insert(index[i], new_node);
         new_node->parent = this;
         current_node = new_node;
       } else
         current_node = current_node->children[index[i]];
     }
 
     // here, we can set the new node. if ind + 1 == index.size(), this means
     // that
     // the index vector was not empty, else the vector was empty and we are at
     // the
     // root of the tree
     if (i + 1 == index.size()) {
       // if the node to be set does not exist, create it, else modify it
       if (current_node->children.exists(index[i])) {
         IndexedTree< Key, Data >* node = current_node->children[index[i]];
 
         if (node->data) delete node->data;
 
         node->data = new Data(theData);
       } else {
         // here, the node tobe set does not exist, so we must create it
         IndexedTree< Key, Data >* new_node =
            new IndexedTree< Key, Data >(index[i], theData);
         current_node->children.insert(index[i], new_node);
         new_node->parent = current_node;
       }
     } else {
       // here, the node to be set is the root of the tree (so it does already
       // exist
       if (data) delete data;
 
       data = new Data(theData);
     }
   }

Member Data Documentation

◆ children

template<typename Key, typename Data>

HashTable< Key, IndexedTree< Key, Data >* > gum::IndexedTree< Key, Data >::children

private

The list of children nodes of the current node.

Definition at line 192 of file indexedTree.h.

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

◆ data

template<typename Key, typename Data>

Data* gum::IndexedTree< Key, Data >::data

private

The data stored into the node.

Definition at line 186 of file indexedTree.h.

Referenced by gum::IndexedTree< Key, Data >::getData(), gum::IndexedTree< Key, Data >::IndexedTree(), gum::IndexedTree< Key, Data >::operator=(), gum::IndexedTree< Key, Data >::setNode(), and gum::IndexedTree< Key, Data >::~IndexedTree().

◆ 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:

agrum/core/indexedTree.h
agrum/core/indexedTree_tpl.h

Public Member Functions

Detailed Description

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

Constructor & Destructor Documentation

◆ IndexedTree() [1/4]

◆ IndexedTree() [2/4]

◆ IndexedTree() [3/4]

◆ IndexedTree() [4/4]

◆ ~IndexedTree()

Member Function Documentation

◆ getData()

◆ getNode()

◆ insertNode() [1/2]

◆ insertNode() [2/2]

◆ operator=()

◆ setNode() [1/2]

◆ setNode() [2/2]

Member Data Documentation

◆ children

◆ data

◆ key

◆ parent

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