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

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

Private Attributes
Key	key
	The key of the current node.
Data *	data
	The data stored into the node.
IndexedTree< Key, Data > *	parent
	The parent of the node.
HashTable< Key, IndexedTree< Key, Data > * >	children
	The list of children nodes of the current node.

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

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

References IndexedTree(), data, and parent.

Referenced by IndexedTree(), IndexedTree(), IndexedTree(), IndexedTree(), ~IndexedTree(), getData(), getNode(), insertNode(), insertNode(), operator=(), setNode(), and setNode().

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

References IndexedTree(), data, key, and parent.

Here is the call graph for this function:

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

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

References IndexedTree(), data, key, and parent.

Here is the call graph for this function:

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

                                                                            :
      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;
    }
  }

References IndexedTree(), children, data, key, and parent.

Here is the call graph for this function:

◆ ~IndexedTree()

template<typename Key, typename Data>

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

Class destructor.

Definition at line 154 of file indexedTree_tpl.h.

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

References IndexedTree(), and data.

Here is the call graph for this function:

Member Function Documentation

◆ getData()

template<typename Key, typename Data>

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

                                                                             {
    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);
  }

References IndexedTree(), children, data, and GUM_ERROR.

Here is the call graph for this function:

◆ getNode()

template<typename Key, typename Data>

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.

                                                                           {
    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;
  }

References IndexedTree(), and children.

Here is the call graph for this function:

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

                                                                                              {
    // 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")
    }
  }

References IndexedTree(), children, GUM_ERROR, and parent.

Here is the call graph for this function:

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

                                                                                              {
    // 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")
    }
  }

References IndexedTree(), children, GUM_ERROR, and parent.

Here is the call graph for this function:

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

                                                                            {
    // 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;
  }

References IndexedTree(), children, data, and key.

Here is the call graph for this function:

◆ setNode() [1/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 313 of file indexedTree_tpl.h.

                                                                                           {
    // 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);
    }
  }

References IndexedTree(), children, data, and parent.

Here is the call graph for this function:

◆ setNode() [2/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 261 of file indexedTree_tpl.h.

                                                                                     {
    // 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;
    }
  }

References IndexedTree(), children, data, and parent.

Here is the call graph for this function:

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 212 of file indexedTree.h.

Referenced by IndexedTree(), getData(), getNode(), insertNode(), insertNode(), operator=(), setNode(), and setNode().

◆ data

template<typename Key, typename Data>

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

private

The data stored into the node.

Definition at line 206 of file indexedTree.h.

Referenced by IndexedTree(), IndexedTree(), IndexedTree(), IndexedTree(), ~IndexedTree(), getData(), operator=(), setNode(), and setNode().

◆ key

template<typename Key, typename Data>

Key gum::IndexedTree< Key, Data >::key

private

The key of the current node.

Definition at line 203 of file indexedTree.h.

Referenced by IndexedTree(), IndexedTree(), IndexedTree(), and operator=().

◆ parent

template<typename Key, typename Data>

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

private

The parent of the node.

Definition at line 209 of file indexedTree.h.

Referenced by IndexedTree(), IndexedTree(), IndexedTree(), IndexedTree(), insertNode(), insertNode(), setNode(), and setNode().

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

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

Public Member Functions

Private Attributes

Detailed Description

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