12 #ifndef INCLUDE_MOLASSEMBLER_TEMPLE_CONSTEXPR_BTREE_H
13 #define INCLUDE_MOLASSEMBLER_TEMPLE_CONSTEXPR_BTREE_H
23 namespace Molassembler {
25 namespace BTreeProperties {
33 PURITY_STRONG constexpr
size_t maxNodesInTree(
const size_t height,
const size_t minDegree) {
34 return static_cast<double>(
35 Math::pow(2 * minDegree, static_cast<unsigned>(height + 1)) - 1
47 PURITY_STRONG constexpr std::size_t minHeight(
const std::size_t numValues,
const std::size_t minDegree) {
50 static_cast<double>(numValues + 1),
51 static_cast<double>(2 * minDegree)
63 PURITY_STRONG constexpr
size_t maxHeightBound(
const size_t numValues,
const size_t minDegree) {
66 static_cast<double>(numValues + 1) / 2,
67 static_cast<double>(minDegree)
128 class LessThanComparator = std::less<T>,
129 class EqualityComparator = std::equal_to<T>
139 static constexpr
size_t maxHeight = BTreeProperties::maxHeightBound(numElements, minDegree);
206 constexpr
void remove(
const T& value) {
234 return nodeIndexOptional.hasValue();
248 if(!nodeIndexOptional.hasValue()) {
252 auto valueLowerBound = lowerBound<T, LessThanComparator>(
253 getNode_(nodeIndexOptional.value()).values.begin(),
254 getNode_(nodeIndexOptional.value()).values.end(),
264 using namespace std::string_literals;
266 std::stringstream graph;
267 graph <<
"digraph g {\n"
268 <<
" node [shape=record, height=.1]\n\n";
272 while(stack.size() > 0) {
273 unsigned nodeIndex = stack.back();
276 for(
auto& childIndex :
getNode_(nodeIndex).children) {
277 stack.push_back(childIndex);
280 const auto& node =
getNode_(nodeIndex);
282 graph <<
" node" << nodeIndex <<
"[label=\"";
285 for(
unsigned i = 0; i < node.values.size(); ++i) {
286 graph << node.values.at(i);
287 if(i != node.values.size() - 1) {
293 for(
unsigned i = 1; i < node.children.size(); ++i) {
294 graph << node.values.at(i-1) <<
"|<f" << i <<
">";
295 if(i != node.children.size() - 1) {
305 for(
unsigned i = 0; i < node.children.size(); ++i) {
306 graph <<
" \"node" << nodeIndex <<
"\":f" << i
307 <<
" -> \"node" << node.children.at(i) <<
"\";\n";
323 while(stack.size() > 0) {
324 unsigned nodeIndex = stack.back();
328 for(
auto& childIndex : node.children) {
329 stack.push_back(childIndex);
352 using iterator_category = std::bidirectional_iterator_tag;
353 using value_type = T;
354 using difference_type = int;
355 using pointer =
const T*
const;
356 using reference =
const T&;
358 enum class InitializeAs : unsigned {
368 const InitializeAs& initDecision
374 if(!static_cast<bool>(static_cast<unsigned>(initDecision))) {
377 while(!getCurrentNode_().
isLeaf()) {
378 indexStack_.push_back(0);
380 nodeStack_.push_back(
381 getCurrentNode_().children.front()
386 indexStack_.push_back(0);
390 while(!getCurrentNode_().isLeaf()) {
391 indexStack_.push_back(
392 2 * getCurrentNode_().values.size()
395 nodeStack_.push_back(
396 getCurrentNode_().children.back()
401 indexStack_.push_back(getCurrentNode_().values.size());
408 const_iterator() =
delete;
409 constexpr const_iterator(
const const_iterator& other)
410 : baseRef_(other.baseRef_),
411 leftMostNode_(other.leftMostNode_),
412 rightMostNode_(other.rightMostNode_),
413 nodeStack_(other.nodeStack_),
414 indexStack_(other.indexStack_)
416 constexpr const_iterator(const_iterator&& other) noexcept =
default;
417 constexpr const_iterator& operator = (
const const_iterator& other) {
418 if(this->baseRef_ != other.baseRef_) {
419 throw "Assigning BTree const_iterator to another base instance!";
422 leftMostNode_ = other.leftMostNode_;
423 rightMostNode_ = other.rightMostNode_;
424 nodeStack_ = other.nodeStack_;
425 indexStack_ = other.indexStack_;
429 constexpr const_iterator& operator = (const_iterator&& other) noexcept =
default;
430 ~const_iterator() =
default;
435 auto indexLimit = currentNodeIndexLimit_();
437 if(indexStack_.back() == indexLimit) {
443 if(getCurrentNode_().
isLeaf()) {
444 ++indexStack_.back();
450 indexStack_.back() == indexLimit
451 && nodeStack_.back() != rightMostNode_
455 indexStack_.pop_back();
456 nodeStack_.pop_back();
457 }
while(indexStack_.back() >= currentNodeIndexLimit_() - 1);
460 ++indexStack_.back();
467 ++indexStack_.back();
468 nodeStack_.push_back(
469 getCurrentNode_().children.at(
470 indexStack_.back() / 2
474 while(!getCurrentNode_().
isLeaf()) {
475 indexStack_.push_back(0);
476 nodeStack_.push_back(
477 getCurrentNode_().children.front()
482 indexStack_.push_back(0);
489 const_iterator retval = *
this;
496 if(nodeStack_.back() == leftMostNode_ && indexStack_.back() == 0) {
502 if(getCurrentNode_().
isLeaf()) {
504 if(indexStack_.back() == 0) {
507 indexStack_.pop_back();
508 nodeStack_.pop_back();
509 }
while(indexStack_.back() == 0);
513 --indexStack_.back();
518 --indexStack_.back();
519 nodeStack_.push_back(
520 getCurrentNode_().children.at(
521 indexStack_.back() / 2
525 while(!getCurrentNode_().
isLeaf()) {
526 indexStack_.push_back(
527 2 * getCurrentNode_().values.size()
529 nodeStack_.push_back(
530 getCurrentNode_().children.back()
534 indexStack_.push_back(
535 getCurrentNode_().values.size() - 1
543 const_iterator retval = *
this;
551 nodeStack_ == other.nodeStack_
552 && indexStack_ == other.indexStack_
553 && leftMostNode_ == other.leftMostNode_
554 && rightMostNode_ == other.rightMostNode_
558 PURITY_WEAK constexpr
bool operator != (
const const_iterator& other)
const {
566 if(getCurrentNode_().isLeaf()) {
567 return getCurrentNode_().values.at(
572 return getCurrentNode_().values.at(
573 indexStack_.back() / 2
580 const BTree& baseRef_;
581 const unsigned leftMostNode_;
582 const unsigned rightMostNode_;
590 return baseRef_.
getNode_(nodeStack_.back());
593 PURITY_WEAK constexpr
unsigned currentNodeIndexLimit_()
const {
595 if(getCurrentNode_().isLeaf()) {
596 return getCurrentNode_().values.size();
602 return 2 * getCurrentNode_().values.size() + 1;
608 return const_iterator(
610 const_iterator::InitializeAs::Begin
616 return const_iterator(
618 const_iterator::InitializeAs::End
635 auto thisIter = this->
begin();
636 auto thisEnd = this->
end();
638 auto otherIter = other.
begin();
640 while(thisIter != thisEnd) {
641 if(*thisIter < *otherIter) {
645 if(*thisIter > *otherIter) {
658 return (other < *
this);
667 auto thisIter = this->
begin();
668 auto thisEnd = this->
end();
670 auto otherIter = other.
begin();
672 while(thisIter != thisEnd) {
673 if(*thisIter != *otherIter) {
686 return !(*
this == other);
697 static constexpr
unsigned minSize = minDegree - 1;
698 static constexpr
unsigned maxSize = 2 * minDegree - 1;
708 constexpr
Node() =
default;
714 return children.size() == 0;
719 return values.size() == maxSize;
751 if(garbage_.size() > 0) {
752 unsigned newNodeIndex = garbage_.back();
756 nodes_.at(newNodeIndex) = Node {};
763 throw "The maximum number of nodes has been reached for a BTree!";
767 nodes_.push_back(Node {});
768 return nodes_.size() - 1;
773 garbage_.push_back(nodeIndex);
778 return nodes_.at(nodeIndex);
783 return nodes_.at(nodeIndex);
790 auto valueLowerBound = lowerBound<T, LessThanComparator>(
798 if(valueLowerBound != node.values.end() &&
eq_(*valueLowerBound, value)) {
813 valueLowerBound - node.values.begin()
824 constexpr
void splitChild_(
unsigned nodeIndex,
const unsigned i) {
835 throw "Inserting into full BTree";
842 right.values = left.values.splice(minDegree);
846 right.children = left.children.splice(minDegree);
850 parent.values.insertAt(
851 parent.values.begin() + i,
856 left.values.pop_back();
859 parent.children.insertAt(
860 parent.children.begin() + i + 1,
870 auto valueLowerBound = lowerBound<T, LessThanComparator>(
877 if(valueLowerBound != node.values.end() &&
eq_(*valueLowerBound, value)) {
878 throw "That key already exists in the tree!";
881 node.values.insertAt(valueLowerBound, value);
884 auto valueLowerBound = lowerBound<T, LessThanComparator>(
891 auto childPos = valueLowerBound - node.values.begin();
894 if(
getNode_(node.children.at(childPos)).isFull()) {
900 if(
lt_(node.values.at(childPos), value)) {
917 while(!
getNode_(nodeIndex).isLeaf()) {
918 nodeIndex =
getNode_(nodeIndex).children.front();
926 while(!
getNode_(nodeIndex).isLeaf()) {
927 nodeIndex =
getNode_(nodeIndex).children.back();
934 constexpr
void delete_(
unsigned nodeIndex,
const T& value) {
937 auto valueLowerBound = lowerBound<T, LessThanComparator>(
944 unsigned indexOfLB = valueLowerBound - node.values.begin();
946 if(valueLowerBound != node.values.end() &&
eq_(*valueLowerBound, value)) {
950 node.values.removeAt(valueLowerBound);
953 if(
getNode_(node.children.at(indexOfLB)).values.size() >= minDegree) {
958 node.children.at(indexOfLB)
962 *valueLowerBound = predecessor;
965 delete_(node.children.at(indexOfLB), predecessor);
966 }
else if(
getNode_(node.children.at(indexOfLB + 1)).values.size() >= minDegree) {
971 node.children.at(indexOfLB + 1)
975 *valueLowerBound = successor;
978 delete_(node.children.at(indexOfLB + 1), successor);
985 unsigned leftChildIndex = node.children.at(indexOfLB);
986 auto& leftChild =
getNode_(leftChildIndex);
988 unsigned rightChildIndex = node.children.at(indexOfLB + 1);
989 auto& rightChild =
getNode_(rightChildIndex);
992 leftChild.values.push_back(value);
995 leftChild.values.copyIn(rightChild.values);
996 if(!leftChild.isLeaf()) {
997 leftChild.children.copyIn(rightChild.children);
1001 node.values.removeAt(valueLowerBound);
1002 node.children.removeAt(
1003 node.children.begin() + indexOfLB + 1
1010 delete_(leftChildIndex, value);
1018 unsigned targetChildIndex = node.children.at(indexOfLB);
1019 auto& targetChild =
getNode_(targetChildIndex);
1021 if(targetChild.values.size() == minDegree - 1) {
1026 &&
getNode_(node.children.at(indexOfLB - 1)).values.size() >= minDegree
1028 unsigned leftSiblingIndex = node.children.at(indexOfLB - 1);
1029 auto& leftSibling =
getNode_(leftSiblingIndex);
1032 targetChild.values.insertAt(
1033 targetChild.values.begin(),
1034 node.values.at(indexOfLB - 1)
1038 node.values.at(indexOfLB - 1) = leftSibling.values.back();
1039 leftSibling.values.pop_back();
1042 if(!targetChild.isLeaf()) {
1043 targetChild.children.insertAt(
1044 targetChild.children.begin(),
1045 leftSibling.children.back()
1048 leftSibling.children.pop_back();
1051 indexOfLB < node.values.size()
1052 &&
getNode_(node.children.at(indexOfLB + 1)).values.size() >= minDegree
1054 unsigned rightSiblingIndex = node.children.at(indexOfLB + 1);
1055 auto& rightSibling =
getNode_(rightSiblingIndex);
1058 targetChild.values.push_back(
1059 node.values.at(indexOfLB)
1063 *valueLowerBound = rightSibling.values.front();
1064 rightSibling.values.removeAt(
1065 rightSibling.values.begin()
1069 if(!targetChild.isLeaf()) {
1070 targetChild.children.push_back(
1071 rightSibling.children.front()
1074 rightSibling.children.removeAt(
1075 rightSibling.children.begin()
1081 if(indexOfLB != 0) {
1082 unsigned leftSiblingIndex = node.children.at(indexOfLB - 1);
1083 auto& leftSibling =
getNode_(leftSiblingIndex);
1086 leftSibling.values.push_back(
1087 node.values.at(indexOfLB - 1)
1089 node.values.removeAt(
1090 node.values.begin() + indexOfLB - 1
1094 leftSibling.values.copyIn(targetChild.values);
1095 if(!targetChild.isLeaf()) {
1096 leftSibling.children.copyIn(targetChild.children);
1099 node.children.removeAt(
1100 node.children.begin() + indexOfLB
1107 unsigned rightSiblingIndex = node.children.at(indexOfLB + 1);
1108 auto& rightSibling =
getNode_(rightSiblingIndex);
1110 targetChild.values.push_back(
1111 node.values.at(indexOfLB)
1113 node.values.removeAt(
1114 node.values.begin() + indexOfLB
1117 targetChild.values.copyIn(rightSibling.values);
1118 if(!targetChild.isLeaf()) {
1119 targetChild.children.copyIn(rightSibling.children);
1122 node.children.removeAt(
1123 node.children.begin() + indexOfLB + 1
1131 delete_(node.children.at(indexOfLB), value);
1138 auto foundIter = garbage_.begin();
1140 while(foundIter != garbage_.end()) {
1141 if(*foundIter == nodeIndex) {
1149 if(foundIter != garbage_.end()) {
1150 throw "An active node is marked as garbage!";
1158 && node.values.size() < minDegree - 1
1160 throw "Not every internal node has min. t-1 values!";
1167 && node.values.size() != node.children.size() - 1
1169 throw "Not every internal node with n values has n+1 children!";
1174 throw "Not all value lists are totally ordered!";
1180 if(!node.isLeaf()) {
1181 for(
unsigned i = 1; i < node.children.size(); ++i) {
1184 getNode_(node.children.at(i - 1)).values.back(),
1185 node.values.at(i - 1)
1187 node.values.at(i - 1),
1188 getNode_(node.children.at(i)).values.front()
1191 throw "Not all children's values are bounded by the parent!";
PURITY_WEAK constexpr const Node & getNode_(unsigned nodeIndex) const
Fetch an unmodifiable node by its 'pointer'.
Definition: BTree.h:782
PURITY_WEAK constexpr bool isLeaf() const
Returns whether the node is a leaf node (i.e. has no children)
Definition: BTree.h:713
static constexpr size_t maxHeight
The height needed to be able to hold at least numElements elements.
Definition: BTree.h:139
PURITY_WEAK constexpr unsigned largestLeafNode_(unsigned nodeIndex) const
Returns the largest leaf node in the sub-tree rooted at nodePtr.
Definition: BTree.h:925
PURITY_WEAK constexpr bool operator==(const const_iterator &other) const
Compares on basis of positional equality.
Definition: BTree.h:549
PURITY_WEAK constexpr bool operator<(const BTree &other) const
Lexicographical comparison.
Definition: BTree.h:626
constexpr math implementations
constexpr const_iterator & operator--()
Prefix decrement.
Definition: BTree.h:495
#define PURITY_WEAK
Definition: Preprocessor.h:36
PURITY_WEAK constexpr bool operator!=(const BTree &other) const
Lexicographical comparison.
Definition: BTree.h:685
An Option monadic type.
Definition: Optional.h:33
DynamicArray< Node, maxNodes > nodes_
Array holding all tree nodes.
Definition: BTree.h:731
PURITY_WEAK constexpr bool operator>(const BTree &other) const
Lexicographical comparison.
Definition: BTree.h:657
unsigned rootPtr_
'Pointer' to root node
Definition: BTree.h:728
PURITY_WEAK constexpr reference operator*() const
Non-modifiable access.
Definition: BTree.h:565
constexpr bool isTotallyOrdered(const ContainerType &container, LessThanComparator comparator=LessThanComparator{})
Checks if the container hold strictly increasing values.
Definition: Containers.h:482
PURITY_WEAK constexpr bool isRootNode_(unsigned nodeIndex) const
Returns whether a node is the root.
Definition: BTree.h:911
PURITY_WEAK constexpr const_iterator end() const
Returns a past-the-end const iterator.
Definition: BTree.h:615
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.
Definition: BTree.h:245
PURITY_WEAK constexpr unsigned size() const
Returns the number of elements in the tree.
Definition: BTree.h:340
A constexpr B-Tree.
Definition: BTree.h:130
constexpr void markNodeDeleted_(unsigned nodeIndex)
Marks a node as 'deleted' for recycling in newNode_.
Definition: BTree.h:772
PURITY_WEAK constexpr bool operator==(const BTree &other) const
Lexicographical comparison.
Definition: BTree.h:662
PURITY_WEAK constexpr bool isFull() const
Returns whether the node is full.
Definition: BTree.h:718
constexpr void validate() const
Validates the state of the tree by DFS traversal. Throws if anything is off.
Definition: BTree.h:320
constexpr void insert(const T &value)
Add a value to the tree.
Definition: BTree.h:181
LessThanComparator lt_
Less-than comparator instance.
Definition: BTree.h:737
PURITY_WEAK constexpr const_iterator begin() const
Returns a const iterator to the first value in the tree.
Definition: BTree.h:607
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 certa...
Definition: BTree.h:824
constexpr unsigned newNode_()
'Allocates' a new node and returns a 'pointer' to it
Definition: BTree.h:749
static constexpr size_t maxNodes
The maximum number of nodes that the tree can hold.
Definition: BTree.h:142
Type for Nodes.
Definition: BTree.h:694
constexpr void insertNonFull_(unsigned nodeIndex, const T &value)
Insert case if the node we can insert into isn't full yet.
Definition: BTree.h:866
PURITY_WEAK std::string dumpGraphviz() const
Dumps a graphViz representation of the B-Tree.
Definition: BTree.h:263
EqualityComparator eq_
Equality comparator instance.
Definition: BTree.h:740
PURITY_WEAK constexpr unsigned smallestLeafNode_(unsigned nodeIndex) const
Returns the smallest leaf node in the sub-tree rooted at nodePtr.
Definition: BTree.h:916
constexpr Node()=default
Default constructor.
constexpr void clear()
Clears the tree.
Definition: BTree.h:160
constexpr void delete_(unsigned nodeIndex, const T &value)
Recursively deletes a value from a sub-tree rooted at node.
Definition: BTree.h:934
constexpr const_iterator & operator++()
Prefix increment.
Definition: BTree.h:434
PURITY_WEAK constexpr bool contains(const T &value) const
Check whether a value exists in the tree.
Definition: BTree.h:231
std::vector-like class (but max size is size allocated)
static constexpr size_t maxElements
The maximum number of values that the tree can hold.
Definition: BTree.h:145
constexpr Node & getNode_(unsigned nodeIndex)
Fetch a modifiable node by its 'pointer'.
Definition: BTree.h:777
unsigned count_
Number of contained elements.
Definition: BTree.h:743
Nonmodifiable in-order iteration.
Definition: BTree.h:348
DynamicArray< unsigned, maxNodes > garbage_
Array holding 'pointers' to any 'deleted' tree nodes.
Definition: BTree.h:734
#define PURITY_STRONG
Definition: Preprocessor.h:65
constexpr void validate_(unsigned nodeIndex) const
Checks whether the node is a valid B-Tree node, and throws if anything is off.
Definition: BTree.h:1136
Functional-style constexpr container algorithms.
PURITY_WEAK constexpr Optional< unsigned > search_(unsigned nodeIndex, const T &value) const
Recursive search for an element in a subtree rooted at node.
Definition: BTree.h:787