Molassembler  3.0.0
Molecule graph and conformer library
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Scine::Molassembler::Temple::BoundedNodeTrie< ChoiceIndex > Struct Template Reference

Data structure to store chains of discrete choices with an finite range of choices at each position. More...

#include <BoundedNodeTrie.h>

Inheritance diagram for Scine::Molassembler::Temple::BoundedNodeTrie< ChoiceIndex >:

Data Structures

struct  AbstractNode
 Abstract base class for nodes to allow differentiation. More...
 
struct  InsertResult
 
class  Leaf
 Leaf node at bottom of the tree. More...
 
class  Node
 Most common type of nodes have other AbstractNodes as children. More...
 

Public Types

Public types
using ChoiceList = std::vector< ChoiceIndex >
 Type used to represent choices made at each level of the tree.
 
using ChoosingFunction = std::function< ChoiceIndex(const std::vector< ChoiceIndex > &, const boost::dynamic_bitset<> &)>
 Function signature needed to choose which child to descend to at a level in the tree.
 

Public Member Functions

Constructors
 BoundedNodeTrie ()=default
 Construct an empty trie, setting the upper exclusive bound on values at each level. More...
 
 BoundedNodeTrie (ChoiceList bounds)
 Construct an empty trie, setting the upper exclusive bound on values at each level. More...
 
Modification
bool insert (const ChoiceList &values)
 Inserts a value list into the prefix trie if not already present. More...
 
ChoiceList generateNewEntry (const ChoosingFunction &chooseFunction)
 Create a new entry by choosing branch at each level of the trie. More...
 
void setBounds (ChoiceList bounds)
 Changes the bounds of the trie. Clears the trie. More...
 
void clear ()
 Removes all inserted lists from the trie. More...
 
Information
bool contains (const ChoiceList &values) const
 Checks whether a value list is present in the trie. More...
 
const ChoiceListbounds () const
 Accessor for underlying bounds.
 
unsigned size () const
 Returns the number of value lists this trie contains. More...
 
unsigned capacity () const
 Returns the total number of value lists this trie might contain. More...
 

Private Types

Private types
using NodePtr = std::unique_ptr< AbstractNode >
 Owning pointer to base class.
 

Private Member Functions

Private member functions
void establishRoot_ ()
 Generate a root node.
 
void establishCapacity_ ()
 Generate a root node.
 

Private Attributes

Private members
ChoiceList bounds_
 
NodePtr root_
 
unsigned size_ = 0
 
unsigned capacity_ = 0
 

Detailed Description

template<typename ChoiceIndex>
struct Scine::Molassembler::Temple::BoundedNodeTrie< ChoiceIndex >

Data structure to store chains of discrete choices with an finite range of choices at each position.

Template Parameters
ChoiceIndexValue type in which the count of possible choices is representable. This needs to be an integer type.
Note
Complexiy annotations use \(N\) for the length of the set ChoiceList

Constructor & Destructor Documentation

template<typename ChoiceIndex>
Scine::Molassembler::Temple::BoundedNodeTrie< ChoiceIndex >::BoundedNodeTrie ( )
default

Construct an empty trie, setting the upper exclusive bound on values at each level.

Parameters
boundsThe upper exclusive bound on values at each level.
template<typename ChoiceIndex>
Scine::Molassembler::Temple::BoundedNodeTrie< ChoiceIndex >::BoundedNodeTrie ( ChoiceList  bounds)
inline

Construct an empty trie, setting the upper exclusive bound on values at each level.

Parameters
boundsThe upper exclusive bound on values at each level.

Member Function Documentation

template<typename ChoiceIndex>
unsigned Scine::Molassembler::Temple::BoundedNodeTrie< ChoiceIndex >::capacity ( ) const
inline

Returns the total number of value lists this trie might contain.

Complexity \(\Theta(1)\)

template<typename ChoiceIndex>
void Scine::Molassembler::Temple::BoundedNodeTrie< ChoiceIndex >::clear ( )
inline

Removes all inserted lists from the trie.

Complexity \(\Theta(N)\)

template<typename ChoiceIndex>
bool Scine::Molassembler::Temple::BoundedNodeTrie< ChoiceIndex >::contains ( const ChoiceList values) const
inline

Checks whether a value list is present in the trie.

Complexity \(O(N)\)

Note
If you are planning to insert values if contains returns false, just use insert. That way you have only one trie traversal in all cases, and you get the information of whether it was already in the trie or not too.
Parameters
valuesThe value list to check for
Returns
Whether the value list is in the tree
template<typename ChoiceIndex>
ChoiceList Scine::Molassembler::Temple::BoundedNodeTrie< ChoiceIndex >::generateNewEntry ( const ChoosingFunction chooseFunction)
inline

Create a new entry by choosing branch at each level of the trie.

Complexity \(\Theta(N)\)

Parameters
chooseFunctionFunction that chooses the branch to descend to at each level. The function is supplied a list of viable choices at the depth (indicating which parts of the tree are full) and a bitset indicating which children exist.
Exceptions
std::logic_errorIf the trie is full, i.e. size() == capacity()
Returns
The newly generated entry
template<typename ChoiceIndex>
bool Scine::Molassembler::Temple::BoundedNodeTrie< ChoiceIndex >::insert ( const ChoiceList values)
inline

Inserts a value list into the prefix trie if not already present.

Complexity \(\Theta(N)\)

Parameters
valuesThe value list to insert into the prefix trie
Exceptions
std::logic_errorIf no bounds are set.
Returns
Whether anything was inserted. I.e. returns true if values was not yet a member of the set.
template<typename ChoiceIndex>
void Scine::Molassembler::Temple::BoundedNodeTrie< ChoiceIndex >::setBounds ( ChoiceList  bounds)
inline

Changes the bounds of the trie. Clears the trie.

Complexity \(\Theta(N)\)

template<typename ChoiceIndex>
unsigned Scine::Molassembler::Temple::BoundedNodeTrie< ChoiceIndex >::size ( ) const
inline

Returns the number of value lists this trie contains.

Complexity \(\Theta(1)\)


The documentation for this struct was generated from the following file: