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 ChoiceList &	bounds () 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

ChoiceIndex

Value 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

bounds

The 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

bounds

The 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

values

The 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

chooseFunction

Function 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_error

If 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

values

The value list to insert into the prefix trie

Exceptions

std::logic_error

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

• Molassembler/Temple/BoundedNodeTrie.h