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

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

#include <agrum/tools/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 52 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 51 of file indexedTree_tpl.h.

References gum::Set< Key, Alloc >::emplace().

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

Here is the call 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 42 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 59 of file indexedTree_tpl.h.

References gum::Set< Key, Alloc >::emplace().

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

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

References gum::Set< Key, Alloc >::emplace().

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

References gum::Set< Key, Alloc >::emplace().

                                         {
    // for debugging purposes
    GUM_DESTRUCTOR(IndexedTree);

    if (data) delete data;
  }

Here is the call graph for this function:

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

References gum::Set< Key, Alloc >::emplace().

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

Here is the call graph for this function:

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

References gum::Set< Key, Alloc >::emplace().

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

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

References gum::Set< Key, Alloc >::emplace().

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

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

References gum::Set< Key, Alloc >::emplace().

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

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

References gum::Set< Key, Alloc >::emplace().

                                                                             {
    // 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 call 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 250 of file indexedTree_tpl.h.

References gum::Set< Key, Alloc >::emplace().

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

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

References gum::Set< Key, Alloc >::emplace().

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

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

data

template<typename Key , typename Data >

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

private

The data stored into the node.

Definition at line 185 of file indexedTree.h.

key

template<typename Key , typename Data >

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

private

The key of the current node.

Definition at line 182 of file indexedTree.h.

parent

template<typename Key , typename Data >

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

private

The parent of the node.

Definition at line 188 of file indexedTree.h.

---

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

• agrum/tools/core/indexedTree.h
• agrum/tools/core/indexedTree_tpl.h