Molassembler  3.0.0
Molecule graph and conformer library
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Data Structures
Scine::Molassembler::Temple::BTree< T, minDegree, numElements, LessThanComparator, EqualityComparator > Class Template Reference

A constexpr B-Tree. More...

#include <BTree.h>

Inheritance diagram for Scine::Molassembler::Temple::BTree< T, minDegree, numElements, LessThanComparator, EqualityComparator >:

Data Structures

class  const_iterator
 Nonmodifiable in-order iteration. More...
 
struct  Node
 Type for Nodes. More...
 

Public Member Functions

Modification
constexpr void clear ()
 Clears the tree. More...
 
constexpr void insert (const T &value)
 Add a value to the tree. More...
 
constexpr void remove (const T &value)
 Remove a value from the tree. More...
 
Information
PURITY_WEAK constexpr bool contains (const T &value) const
 Check whether a value exists in the tree. More...
 
PURITY_WEAK constexpr Optional
< const T & > 		getOption (const T &value) const
 Checks if the tree contains T. If so, returns a const-ref to it. More...
 
PURITY_WEAK std::string dumpGraphviz () const
 Dumps a graphViz representation of the B-Tree.
 
constexpr void validate () const
 Validates the state of the tree by DFS traversal. Throws if anything is off.
 
PURITY_WEAK constexpr unsigned size () const
 Returns the number of elements in the tree. More...
 
Iterators
PURITY_WEAK constexpr
const_iterator 		begin () const
 Returns a const iterator to the first value in the tree.
 
PURITY_WEAK constexpr
const_iterator 		end () const
 Returns a past-the-end const iterator.
 
Operators
PURITY_WEAK constexpr bool operator< (const BTree &other) const
 Lexicographical comparison.
 
PURITY_WEAK constexpr bool operator> (const BTree &other) const
 Lexicographical comparison.
 
PURITY_WEAK constexpr bool operator== (const BTree &other) const
 Lexicographical comparison.
 
PURITY_WEAK constexpr bool operator!= (const BTree &other) const
 Lexicographical comparison.
 

Static Public Attributes

Static properties
static constexpr size_t maxHeight = BTreeProperties::maxHeightBound(numElements, minDegree)
 The height needed to be able to hold at least numElements elements.
 
static constexpr size_t maxNodes = BTreeProperties::maxNodesInTree(maxHeight, minDegree)
 The maximum number of nodes that the tree can hold.
 
static constexpr size_t maxElements = maxNodes * (2 * minDegree - 1)
 The maximum number of values that the tree can hold.
 

Private Member Functions

Private member functions
constexpr unsigned newNode_ ()
 'Allocates' a new node and returns a 'pointer' to it
 
constexpr void markNodeDeleted_ (unsigned nodeIndex)
 Marks a node as 'deleted' for recycling in newNode_.
 
constexpr Node & getNode_ (unsigned nodeIndex)
 Fetch a modifiable node by its 'pointer'.
 
PURITY_WEAK constexpr const Node & getNode_ (unsigned nodeIndex) const
 Fetch an unmodifiable node by its 'pointer'.
 
PURITY_WEAK constexpr Optional
< unsigned > 		search_ (unsigned nodeIndex, const T &value) const
 Recursive search for an element in a subtree rooted at node.
 
constexpr void splitChild_ (unsigned nodeIndex, const unsigned i)
 If a child we want to descend into during insertion is full, we have to split it in order to be certain we can insert into it if necessary.
 
constexpr void insertNonFull_ (unsigned nodeIndex, const T &value)
 Insert case if the node we can insert into isn't full yet.
 
PURITY_WEAK constexpr bool isRootNode_ (unsigned nodeIndex) const
 Returns whether a node is the root.
 
PURITY_WEAK constexpr unsigned smallestLeafNode_ (unsigned nodeIndex) const
 Returns the smallest leaf node in the sub-tree rooted at nodePtr.
 
PURITY_WEAK constexpr unsigned largestLeafNode_ (unsigned nodeIndex) const
 Returns the largest leaf node in the sub-tree rooted at nodePtr.
 
constexpr void delete_ (unsigned nodeIndex, const T &value)
 Recursively deletes a value from a sub-tree rooted at node.
 
constexpr void validate_ (unsigned nodeIndex) const
 Checks whether the node is a valid B-Tree node, and throws if anything is off.
 

Private Attributes

Private state
unsigned rootPtr_
 'Pointer' to root node
 
DynamicArray< Node, maxNodes > nodes_
 Array holding all tree nodes.
 
DynamicArray< unsigned, maxNodes > garbage_
 Array holding 'pointers' to any 'deleted' tree nodes.
 
LessThanComparator lt_
 Less-than comparator instance.
 
EqualityComparator eq_
 Equality comparator instance.
 
unsigned count_ = 0
 Number of contained elements.
 

Detailed Description

template<typename T, size_t minDegree, size_t numElements, class LessThanComparator = std::less<T>, class EqualityComparator = std::equal_to<T>>
class Scine::Molassembler::Temple::BTree< T, minDegree, numElements, LessThanComparator, EqualityComparator >

A constexpr B-Tree.

This class is a B-Tree that stores values in its nodes. (This can be turned into an associative container with a simple modification, though: Set T to std::pair<KeyType, ValueType> and supply custom LessThanComparator and EqualityComparators that merely compare using the KeyType. Then return the ValueType from a lookup with a default-constructed ValueType.)

Template Parameters
TThe desired stored type
minDegreeThe minimum degree t of the B-Tree. Must be >= 2, since Nodes store a minimum of t-1 values. A Node of degree t can store up to 2t-1 values and has up to 2t children.
numElementsThe intended maximimum amount of stored elements. The class must allocate all nodes that may possibly be stored at any time, so a tree height that allows the storage of at least numElements is chosen and then space is allocated for the case that this height is filled with nodes. This has the consequence that the instantiated tree can typically store quite a bit more elements than originally intended (see the static member maxElements). Play with the minimum order a bit if you need space-efficiency.
LessThanComparatorA pure binary functor that takes two values and returns whether a is smaller than b. Must implement strict weak ordering. Defaults to std::less<T>.
EqualityComparatorA pure binary functor that takes two values and returns whether they are equal. Defaults to std::equal_to<T>.
Warning
Since we are working in constexpr, we have to work around a large range of constraints, one of which is that we cannot dynamically allocate or delete objects. This is particularly bad for BTrees since the height of the tree can vary by a full level for the same contained information, so the total amount of allocated values may exceed the desired maximum number of elements by a factor proportional to the minimum degree. The amount of pre-allocated values is accessible via the maxElements static member.
Note
Nodes of the tree cannot be truly allocated or deleted dynamically, so they are all pre-allocated on construction and merely marked deleted. Indices into the pre-allocated array of nodes are the 'pointers' of this implementation.
No differentiation is made in the type system for internal or leaf nodes. Leaves just have no children.
Regarding complexity annotations, \(t\) is used as the symbol for the minimum degree of the tree, and \(N\) is the number of contained elements.

Member Function Documentation

template<typename T, size_t minDegree, size_t numElements, class LessThanComparator = std::less<T>, class EqualityComparator = std::equal_to<T>>
constexpr void Scine::Molassembler::Temple::BTree< T, minDegree, numElements, LessThanComparator, EqualityComparator >::clear ( )
inline

Clears the tree.

Complexity \(O(N)\)

template<typename T, size_t minDegree, size_t numElements, class LessThanComparator = std::less<T>, class EqualityComparator = std::equal_to<T>>
PURITY_WEAK constexpr bool Scine::Molassembler::Temple::BTree< T, minDegree, numElements, LessThanComparator, EqualityComparator >::contains ( const T &  value) const
inline

Check whether a value exists in the tree.

Check whether a value is stored in the tree.

Complexity \(\Theta(t \log_t N)\)

template<typename T, size_t minDegree, size_t numElements, class LessThanComparator = std::less<T>, class EqualityComparator = std::equal_to<T>>
PURITY_WEAK constexpr Optional<const T&> Scine::Molassembler::Temple::BTree< T, minDegree, numElements, LessThanComparator, EqualityComparator >::getOption ( const T &  value) const
inline

Checks if the tree contains T. If so, returns a const-ref to it.

Note
This function may seem nonsensical, but it is an important building block for maps in which what not all that is stored is compared against in the search.

Complexity \(\Theta(t \log_t N)\)

template<typename T, size_t minDegree, size_t numElements, class LessThanComparator = std::less<T>, class EqualityComparator = std::equal_to<T>>
constexpr void Scine::Molassembler::Temple::BTree< T, minDegree, numElements, LessThanComparator, EqualityComparator >::insert ( const T &  value)
inline

Add a value to the tree.

Inserts a new value into the tree. This value must not already be in the tree.

Complexity \(\Theta(t \log_t N)\)

Precondition
The tree does not contain value
template<typename T, size_t minDegree, size_t numElements, class LessThanComparator = std::less<T>, class EqualityComparator = std::equal_to<T>>
constexpr void Scine::Molassembler::Temple::BTree< T, minDegree, numElements, LessThanComparator, EqualityComparator >::remove ( const T &  value)
inline

Remove a value from the tree.

Deletes a value from the tree.

Complexity \(\Theta(t \log_t N)\)

Precondition
The value must exist in the tree.
template<typename T, size_t minDegree, size_t numElements, class LessThanComparator = std::less<T>, class EqualityComparator = std::equal_to<T>>
PURITY_WEAK constexpr unsigned Scine::Molassembler::Temple::BTree< T, minDegree, numElements, LessThanComparator, EqualityComparator >::size ( ) const
inline

Returns the number of elements in the tree.

Complexity \(\Theta(1)\)

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