Molassembler  3.0.0
Molecule graph and conformer library
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
BTree.h
Go to the documentation of this file.
1 
12 #ifndef INCLUDE_MOLASSEMBLER_TEMPLE_CONSTEXPR_BTREE_H
13 #define INCLUDE_MOLASSEMBLER_TEMPLE_CONSTEXPR_BTREE_H
14 
19 
20 #include <sstream>
21 
22 namespace Scine {
23 namespace Molassembler {
24 namespace Temple {
25 namespace BTreeProperties {
26 
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
36  ) / (
37  2 * minDegree - 1
38  );
39 }
40 
47 PURITY_STRONG constexpr std::size_t minHeight(const std::size_t numValues, const std::size_t minDegree) {
48  return Math::ceil(
49  Math::log(
50  static_cast<double>(numValues + 1),
51  static_cast<double>(2 * minDegree)
52  ) - 1
53  );
54 }
55 
63 PURITY_STRONG constexpr size_t maxHeightBound(const size_t numValues, const size_t minDegree) {
64  return Math::floor(
65  Math::log(
66  static_cast<double>(numValues + 1) / 2,
67  static_cast<double>(minDegree)
68  )
69  );
70 }
71 
72 } // namespace BTreeImpl
73 
124 template<
125  typename T,
126  size_t minDegree,
127  size_t numElements,
128  class LessThanComparator = std::less<T>,
129  class EqualityComparator = std::equal_to<T>
130 > class BTree {
131 private:
132  // Forward-declare Node
133  struct Node;
134 
135 public:
139  static constexpr size_t maxHeight = BTreeProperties::maxHeightBound(numElements, minDegree);
140 
142  static constexpr size_t maxNodes = BTreeProperties::maxNodesInTree(maxHeight, minDegree);
143 
145  static constexpr size_t maxElements = maxNodes * (2 * minDegree - 1);
147 
148 
149 public:
150  constexpr BTree() : rootPtr_ {0} {
151  rootPtr_ = newNode_();
152  }
153 
156 
160  constexpr void clear() {
161  // Refresh all nodes
162  for(auto& node: nodes_) {
163  node = Node {};
164  }
165 
166  // Clear the garbage
167  garbage_.clear();
168 
169  // Assign a new root
170  rootPtr_ = newNode_();
171  }
172 
181  constexpr void insert(const T& value) {
182  unsigned r = rootPtr_;
183 
184  if(getNode_(r).isFull()) { // Root is full, must be split
185  unsigned s = newNode_();
186 
187  rootPtr_ = s;
188 
189  getNode_(s).children.push_back(r);
190  splitChild_(s, 0);
191  insertNonFull_(s, value);
192  } else {
193  insertNonFull_(r, value);
194  }
195 
196  ++count_;
197  }
198 
206  constexpr void remove(const T& value) {
207  delete_(rootPtr_, value);
208 
209  // In case the root node is valueless but has a child, shrink the tree
210  if(getNode_(rootPtr_).values.size() == 0 && !getNode_(rootPtr_).isLeaf()) {
211  unsigned emptyRoot = rootPtr_;
212 
213  rootPtr_ = getNode_(rootPtr_).children.front();
214 
215  markNodeDeleted_(emptyRoot);
216  }
217 
218  --count_;
219  }
220 
222 
225 
231  PURITY_WEAK constexpr bool contains(const T& value) const {
232  auto nodeIndexOptional = search_(rootPtr_, value);
233 
234  return nodeIndexOptional.hasValue();
235  }
236 
245  PURITY_WEAK constexpr Optional<const T&> getOption(const T& value) const {
246  auto nodeIndexOptional = search_(rootPtr_, value);
247 
248  if(!nodeIndexOptional.hasValue()) {
249  return {};
250  }
251 
252  auto valueLowerBound = lowerBound<T, LessThanComparator>(
253  getNode_(nodeIndexOptional.value()).values.begin(),
254  getNode_(nodeIndexOptional.value()).values.end(),
255  value,
256  lt_
257  );
258 
259  return Optional<const T&> {*valueLowerBound};
260  }
261 
263  PURITY_WEAK std::string dumpGraphviz() const {
264  using namespace std::string_literals;
265 
266  std::stringstream graph;
267  graph << "digraph g {\n"
268  << " node [shape=record, height=.1]\n\n";
269 
271 
272  while(stack.size() > 0) {
273  unsigned nodeIndex = stack.back();
274  stack.pop_back();
275 
276  for(auto& childIndex : getNode_(nodeIndex).children) {
277  stack.push_back(childIndex);
278  }
279 
280  const auto& node = getNode_(nodeIndex);
281 
282  graph << " node" << nodeIndex << "[label=\"";
283 
284  if(node.isLeaf()) {
285  for(unsigned i = 0; i < node.values.size(); ++i) {
286  graph << node.values.at(i);
287  if(i != node.values.size() - 1) {
288  graph << "|";
289  }
290  }
291  } else {
292  graph << "<f0>|";
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) {
296  graph << "|";
297  }
298  }
299  }
300 
301  graph << "\"];\n";
302 
303  // Write all connections
304  if(!node.isLeaf()) {
305  for(unsigned i = 0; i < node.children.size(); ++i) {
306  graph << " \"node" << nodeIndex << "\":f" << i
307  << " -> \"node" << node.children.at(i) << "\";\n";
308  }
309  }
310  }
311 
312  graph << "}";
313 
314  return graph.str();
315  }
316 
320  constexpr void validate() const {
322 
323  while(stack.size() > 0) {
324  unsigned nodeIndex = stack.back();
325  auto& node = getNode_(nodeIndex);
326  stack.pop_back();
327 
328  for(auto& childIndex : node.children) {
329  stack.push_back(childIndex);
330  }
331 
332  validate_(nodeIndex);
333  }
334  }
335 
340  PURITY_WEAK constexpr unsigned size() const {
341  return count_;
342  }
344 
349  public:
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&;
357 
358  enum class InitializeAs : unsigned {
359  Begin = 0,
360  End = 1
361  };
363 
366  constexpr const_iterator(
367  const BTree& tree,
368  const InitializeAs& initDecision
369  ) : baseRef_(tree),
370  leftMostNode_(tree.smallestLeafNode_(tree.rootPtr_)),
371  rightMostNode_(tree.largestLeafNode_(tree.rootPtr_)),
372  nodeStack_ {tree.rootPtr_}
373  {
374  if(!static_cast<bool>(static_cast<unsigned>(initDecision))) {
375  // 0 is Begin, so not-false is begin
376 
377  while(!getCurrentNode_().isLeaf()) {
378  indexStack_.push_back(0);
379 
380  nodeStack_.push_back(
381  getCurrentNode_().children.front()
382  );
383  }
384 
385  // At pos 0 of the leaf indices
386  indexStack_.push_back(0);
387  } else {
388  // End const_iterator initialization
389 
390  while(!getCurrentNode_().isLeaf()) {
391  indexStack_.push_back(
392  2 * getCurrentNode_().values.size()
393  );
394 
395  nodeStack_.push_back(
396  getCurrentNode_().children.back()
397  );
398  }
399 
400  // past-the-end of indices
401  indexStack_.push_back(getCurrentNode_().values.size());
402  }
403  }
405 
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_)
415  {}
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!";
420  }
421 
422  leftMostNode_ = other.leftMostNode_;
423  rightMostNode_ = other.rightMostNode_;
424  nodeStack_ = other.nodeStack_;
425  indexStack_ = other.indexStack_;
426 
427  return *this;
428  }
429  constexpr const_iterator& operator = (const_iterator&& other) noexcept = default;
430  ~const_iterator() = default;
432 
434  constexpr const_iterator& operator ++ () {
435  auto indexLimit = currentNodeIndexLimit_();
436 
437  if(indexStack_.back() == indexLimit) { // We are already the end const_iterator
438  // Do nothing and return immediately
439  return *this;
440  }
441 
442  // In case we are a leaf, increment and re-check
443  if(getCurrentNode_().isLeaf()) {
444  ++indexStack_.back();
445 
446  /* If we hit the index limit for the node and we're not the rightmost
447  * node, we have to go up the tree and to the right
448  */
449  if(
450  indexStack_.back() == indexLimit
451  && nodeStack_.back() != rightMostNode_
452  ) {
453  // Unwind the stack until we are at an incrementable position
454  do {
455  indexStack_.pop_back();
456  nodeStack_.pop_back();
457  } while(indexStack_.back() >= currentNodeIndexLimit_() - 1);
458 
459  // Increment here, now we are placed on a value at an internal node
460  ++indexStack_.back();
461  }
462 
463  return *this;
464  }
465 
466  // We are on an internal node, incrementing puts us on a child
467  ++indexStack_.back();
468  nodeStack_.push_back(
469  getCurrentNode_().children.at(
470  indexStack_.back() / 2 // children are at even indices
471  )
472  );
473 
474  while(!getCurrentNode_().isLeaf()) {
475  indexStack_.push_back(0);
476  nodeStack_.push_back(
477  getCurrentNode_().children.front()
478  );
479  }
480 
481  // Now we are a leaf, and placed on the first value
482  indexStack_.push_back(0);
483 
484  return *this;
485  }
486 
488  constexpr const_iterator operator ++ (int) {
489  const_iterator retval = *this;
490  ++(*this);
491  return retval;
492  }
493 
495  constexpr const_iterator& operator -- () {
496  if(nodeStack_.back() == leftMostNode_ && indexStack_.back() == 0) {
497  // We are the begin const_iterator
498  return *this;
499  }
500 
501  // In case we are a leaf, decrement and re-check
502  if(getCurrentNode_().isLeaf()) {
503  // If we are at zero, we have to find a decrementable position
504  if(indexStack_.back() == 0) {
505  // Unwind the stack until we can decrement
506  do {
507  indexStack_.pop_back();
508  nodeStack_.pop_back();
509  } while(indexStack_.back() == 0);
510  }
511 
512  // Decrement and return
513  --indexStack_.back();
514  return *this;
515  }
516 
517  // We are an internal node, decrementing puts us on a child
518  --indexStack_.back();
519  nodeStack_.push_back(
520  getCurrentNode_().children.at(
521  indexStack_.back() / 2
522  )
523  );
524 
525  while(!getCurrentNode_().isLeaf()) {
526  indexStack_.push_back(
527  2 * getCurrentNode_().values.size()
528  );
529  nodeStack_.push_back(
530  getCurrentNode_().children.back()
531  );
532  }
533 
534  indexStack_.push_back(
535  getCurrentNode_().values.size() - 1
536  );
537 
538  return *this;
539  }
540 
542  constexpr const_iterator operator -- (int) {
543  const_iterator retval = *this;
544  --(*this);
545  return retval;
546  }
547 
549  PURITY_WEAK constexpr bool operator == (const const_iterator& other) const {
550  return (
551  nodeStack_ == other.nodeStack_
552  && indexStack_ == other.indexStack_
553  && leftMostNode_ == other.leftMostNode_
554  && rightMostNode_ == other.rightMostNode_
555  );
556  }
557 
558  PURITY_WEAK constexpr bool operator != (const const_iterator& other) const {
559  return !(
560  *this == other
561  );
562  }
563 
565  PURITY_WEAK constexpr reference operator *() const {
566  if(getCurrentNode_().isLeaf()) {
567  return getCurrentNode_().values.at(
568  indexStack_.back()
569  );
570  }
571 
572  return getCurrentNode_().values.at(
573  indexStack_.back() / 2
574  );
575  }
576 
577  private:
580  const BTree& baseRef_;
581  const unsigned leftMostNode_;
582  const unsigned rightMostNode_;
586 
589  PURITY_WEAK constexpr const Node& getCurrentNode_() const {
590  return baseRef_.getNode_(nodeStack_.back());
591  }
592 
593  PURITY_WEAK constexpr unsigned currentNodeIndexLimit_() const {
594  // For leaves, the past-the-end position is the size of values
595  if(getCurrentNode_().isLeaf()) {
596  return getCurrentNode_().values.size();
597  }
598 
599  /* For internal nodes, the past-the-end position is the size of values
600  * plus the size of children + 1
601  */
602  return 2 * getCurrentNode_().values.size() + 1;
603  }
605  };
607  PURITY_WEAK constexpr const_iterator begin() const {
608  return const_iterator(
609  *this,
610  const_iterator::InitializeAs::Begin
611  );
612  }
613 
615  PURITY_WEAK constexpr const_iterator end() const {
616  return const_iterator(
617  *this,
618  const_iterator::InitializeAs::End
619  );
620  }
622 
626  PURITY_WEAK constexpr bool operator < (const BTree& other) const {
627  if(this->size() < other.size()) {
628  return true;
629  }
630 
631  if(this->size() > other.size()) {
632  return false;
633  }
634 
635  auto thisIter = this->begin();
636  auto thisEnd = this->end();
637 
638  auto otherIter = other.begin();
639 
640  while(thisIter != thisEnd) {
641  if(*thisIter < *otherIter) {
642  return true;
643  }
644 
645  if(*thisIter > *otherIter) {
646  return false;
647  }
648 
649  ++thisIter;
650  ++otherIter;
651  }
652 
653  return false;
654  }
655 
657  PURITY_WEAK constexpr bool operator > (const BTree& other) const {
658  return (other < *this);
659  }
660 
662  PURITY_WEAK constexpr bool operator == (const BTree& other) const {
663  if(this->size() != other.size()) {
664  return false;
665  }
666 
667  auto thisIter = this->begin();
668  auto thisEnd = this->end();
669 
670  auto otherIter = other.begin();
671 
672  while(thisIter != thisEnd) {
673  if(*thisIter != *otherIter) {
674  return false;
675  }
676 
677  ++thisIter;
678  ++otherIter;
679  }
680 
681  return true;
682  }
683 
685  PURITY_WEAK constexpr bool operator != (const BTree& other) const {
686  return !(*this == other);
687  }
689 
690 private:
694  struct Node {
697  static constexpr unsigned minSize = minDegree - 1;
698  static constexpr unsigned maxSize = 2 * minDegree - 1;
700 
706 
708  constexpr Node() = default;
709 
713  PURITY_WEAK constexpr bool isLeaf() const {
714  return children.size() == 0;
715  }
716 
718  PURITY_WEAK constexpr bool isFull() const {
719  return values.size() == maxSize;
720  }
722  };
724 
728  unsigned rootPtr_;
729 
732 
735 
737  LessThanComparator lt_;
738 
740  EqualityComparator eq_;
741 
743  unsigned count_ = 0;
745 
749  constexpr unsigned newNode_() {
750  // If there are nodes in the garbage, take those first
751  if(garbage_.size() > 0) {
752  unsigned newNodeIndex = garbage_.back();
753  garbage_.pop_back();
754 
755  // Refresh the node
756  nodes_.at(newNodeIndex) = Node {};
757 
758  return newNodeIndex;
759  }
760 
761  if(nodes_.size() == maxNodes) {
762  // We cannot get any new nodes! Nothing in the garbage
763  throw "The maximum number of nodes has been reached for a BTree!";
764  }
765 
766  // Default: Just expand the dynamic array with a fresh Node
767  nodes_.push_back(Node {});
768  return nodes_.size() - 1;
769  }
770 
772  constexpr void markNodeDeleted_(unsigned nodeIndex) {
773  garbage_.push_back(nodeIndex);
774  }
775 
777  constexpr Node& getNode_(unsigned nodeIndex) {
778  return nodes_.at(nodeIndex);
779  }
780 
782  PURITY_WEAK constexpr const Node& getNode_(unsigned nodeIndex) const {
783  return nodes_.at(nodeIndex);
784  }
785 
787  PURITY_WEAK constexpr Optional<unsigned> search_(unsigned nodeIndex, const T& value) const {
788  auto node = getNode_(nodeIndex);
789 
790  auto valueLowerBound = lowerBound<T, LessThanComparator>(
791  node.values.begin(),
792  node.values.end(),
793  value,
794  lt_
795  );
796 
797  // In case the lower bound is actually our sought value, return this node
798  if(valueLowerBound != node.values.end() && eq_(*valueLowerBound, value)) {
799  return Optional<unsigned> {nodeIndex};
800  }
801 
802  // If we haven't found the value and this node is a leaf, search fails
803  if(node.isLeaf()) {
804  return Optional<unsigned> {};
805  }
806 
807  /* Otherwise descend to the child at the same index as the lower bound in
808  * values (this also works in case LB is at values.end() since children.size()
809  * == values.size() + 1) and look there
810  */
811  return search_(
812  node.children.at(
813  valueLowerBound - node.values.begin()
814  ),
815  value
816  );
817  }
818 
824  constexpr void splitChild_(unsigned nodeIndex, const unsigned i) {
825  // i is the child index in node's values being split since that node is full
826  auto& parent = getNode_(nodeIndex);
827 
828  // The node being split is afterwards considered the "left" node
829  auto& left = getNode_(
830  getNode_(nodeIndex).children.at(i)
831  );
832 
833  // Allocate a new "right" node
834  if(nodes_.size() == maxNodes) {
835  throw "Inserting into full BTree";
836  }
837 
838  auto rightIndex = newNode_();
839  auto& right = getNode_(rightIndex);
840 
841  // Move values
842  right.values = left.values.splice(minDegree);
843 
844  // In case left is not a leaf, move the children too
845  if(!left.isLeaf()) {
846  right.children = left.children.splice(minDegree);
847  }
848 
849  // Insert the original median value into the non-full node
850  parent.values.insertAt(
851  parent.values.begin() + i,
852  left.values.back()
853  );
854 
855  // Have to remove it from left, too
856  left.values.pop_back();
857 
858  // And assign right as the child to the right of the inserted median value
859  parent.children.insertAt(
860  parent.children.begin() + i + 1,
861  rightIndex
862  );
863  }
864 
866  constexpr void insertNonFull_(unsigned nodeIndex, const T& value) {
867  auto& node = getNode_(nodeIndex);
868 
869  if(node.isLeaf()) {
870  auto valueLowerBound = lowerBound<T, LessThanComparator>(
871  node.values.begin(),
872  node.values.end(),
873  value,
874  lt_
875  );
876 
877  if(valueLowerBound != node.values.end() && eq_(*valueLowerBound, value)) {
878  throw "That key already exists in the tree!";
879  }
880 
881  node.values.insertAt(valueLowerBound, value);
882  } else {
883  // Where to go?
884  auto valueLowerBound = lowerBound<T, LessThanComparator>(
885  node.values.begin(),
886  node.values.end(),
887  value,
888  lt_
889  );
890 
891  auto childPos = valueLowerBound - node.values.begin();
892 
893  // In case the purported child is full, split it!
894  if(getNode_(node.children.at(childPos)).isFull()) {
895  splitChild_(nodeIndex, childPos);
896 
897  /* values has an additional value from the split, check if index has to
898  * be incremented
899  */
900  if(lt_(node.values.at(childPos), value)) {
901  ++childPos;
902  }
903  }
904 
905  // The target child cannot be full anymore, so we can call
906  insertNonFull_(node.children.at(childPos), value);
907  }
908  }
909 
911  PURITY_WEAK constexpr bool isRootNode_(unsigned nodeIndex) const {
912  return nodeIndex == rootPtr_;
913  }
914 
916  PURITY_WEAK constexpr unsigned smallestLeafNode_(unsigned nodeIndex) const {
917  while(!getNode_(nodeIndex).isLeaf()) {
918  nodeIndex = getNode_(nodeIndex).children.front();
919  }
920 
921  return nodeIndex;
922  }
923 
925  PURITY_WEAK constexpr unsigned largestLeafNode_(unsigned nodeIndex) const {
926  while(!getNode_(nodeIndex).isLeaf()) {
927  nodeIndex = getNode_(nodeIndex).children.back();
928  }
929 
930  return nodeIndex;
931  }
932 
934  constexpr void delete_(unsigned nodeIndex, const T& value) {
935  auto& node = getNode_(nodeIndex);
936 
937  auto valueLowerBound = lowerBound<T, LessThanComparator>(
938  node.values.begin(),
939  node.values.end(),
940  value,
941  lt_
942  );
943 
944  unsigned indexOfLB = valueLowerBound - node.values.begin();
945 
946  if(valueLowerBound != node.values.end() && eq_(*valueLowerBound, value)) {
947  // value to remove is in this node's values
948  if(node.isLeaf()) {
949  // Case 1
950  node.values.removeAt(valueLowerBound);
951  } else {
952  // Case 2
953  if(getNode_(node.children.at(indexOfLB)).values.size() >= minDegree) {
954  // Case 2a: Predecessor of value is maximum in subtree to the left
955 
956  // Predecessor value is largest value of largest leaf node in left subtree
957  T predecessor = getNode_(largestLeafNode_(
958  node.children.at(indexOfLB)
959  )).values.back();
960 
961  // Replace the value to be deleted by its predecessor
962  *valueLowerBound = predecessor;
963 
964  // Recursively delete the predecessor
965  delete_(node.children.at(indexOfLB), predecessor);
966  } else if(getNode_(node.children.at(indexOfLB + 1)).values.size() >= minDegree) {
967  // Case 2b: Successor of value is minimum in subtree to the right
968 
969  // The successor value is the leftmost / smallest one
970  T successor = getNode_(smallestLeafNode_(
971  node.children.at(indexOfLB + 1)
972  )).values.front();
973 
974  // Replace the value to be deleted by its successor
975  *valueLowerBound = successor;
976 
977  // Recursively delete the successor
978  delete_(node.children.at(indexOfLB + 1), successor);
979  } else {
980  /* Case 2c: Merge the value to delete, all of the right child into the
981  * left child. The current node loses both k and the pointer to the
982  * right child
983  */
984 
985  unsigned leftChildIndex = node.children.at(indexOfLB);
986  auto& leftChild = getNode_(leftChildIndex);
987 
988  unsigned rightChildIndex = node.children.at(indexOfLB + 1);
989  auto& rightChild = getNode_(rightChildIndex);
990 
991  // Add the value to the left child
992  leftChild.values.push_back(value);
993 
994  // Merge the right child into the left child
995  leftChild.values.copyIn(rightChild.values);
996  if(!leftChild.isLeaf()) {
997  leftChild.children.copyIn(rightChild.children);
998  }
999 
1000  // Remove the value and child pointer to rightChild from left
1001  node.values.removeAt(valueLowerBound);
1002  node.children.removeAt(
1003  node.children.begin() + indexOfLB + 1
1004  );
1005 
1006  // Delete the right child
1007  markNodeDeleted_(rightChildIndex);
1008 
1009  // Delete the value recursively from the left child
1010  delete_(leftChildIndex, value);
1011  }
1012  }
1013  } else {
1014  /* Case 3: The value to delete is not in this node's values and we have to
1015  * descend in the tree. Need to ensure that any node we descend to has
1016  * at least minDegree values!
1017  */
1018  unsigned targetChildIndex = node.children.at(indexOfLB);
1019  auto& targetChild = getNode_(targetChildIndex);
1020 
1021  if(targetChild.values.size() == minDegree - 1) {
1022  // Case 3a Move some values around from left or right siblings
1023 
1024  if(
1025  indexOfLB != 0
1026  && getNode_(node.children.at(indexOfLB - 1)).values.size() >= minDegree
1027  ) {
1028  unsigned leftSiblingIndex = node.children.at(indexOfLB - 1);
1029  auto& leftSibling = getNode_(leftSiblingIndex);
1030 
1031  // Move value at LB into targetChild
1032  targetChild.values.insertAt(
1033  targetChild.values.begin(),
1034  node.values.at(indexOfLB - 1)
1035  );
1036 
1037  // Last value of left sibling replaces value at LB
1038  node.values.at(indexOfLB - 1) = leftSibling.values.back();
1039  leftSibling.values.pop_back();
1040 
1041  // In case it is not a leaf, we move the child pointer too
1042  if(!targetChild.isLeaf()) {
1043  targetChild.children.insertAt(
1044  targetChild.children.begin(),
1045  leftSibling.children.back()
1046  );
1047 
1048  leftSibling.children.pop_back();
1049  }
1050  } else if(
1051  indexOfLB < node.values.size()
1052  && getNode_(node.children.at(indexOfLB + 1)).values.size() >= minDegree
1053  ) {
1054  unsigned rightSiblingIndex = node.children.at(indexOfLB + 1);
1055  auto& rightSibling = getNode_(rightSiblingIndex);
1056 
1057  // Move value at LB into targetChild
1058  targetChild.values.push_back(
1059  node.values.at(indexOfLB)
1060  );
1061 
1062  // First value of right sibling replaces value at LB
1063  *valueLowerBound = rightSibling.values.front();
1064  rightSibling.values.removeAt(
1065  rightSibling.values.begin()
1066  );
1067 
1068  // In case the target is not a leaf, we move the child pointer too
1069  if(!targetChild.isLeaf()) {
1070  targetChild.children.push_back(
1071  rightSibling.children.front()
1072  );
1073 
1074  rightSibling.children.removeAt(
1075  rightSibling.children.begin()
1076  );
1077  }
1078  } else {
1079  // Case 3b
1080 
1081  if(indexOfLB != 0) { // Merge with left sibling
1082  unsigned leftSiblingIndex = node.children.at(indexOfLB - 1);
1083  auto& leftSibling = getNode_(leftSiblingIndex);
1084 
1085  // Move value down to left sibling
1086  leftSibling.values.push_back(
1087  node.values.at(indexOfLB - 1)
1088  );
1089  node.values.removeAt(
1090  node.values.begin() + indexOfLB - 1
1091  );
1092 
1093  // Merge values and children of targetChild into leftSibling
1094  leftSibling.values.copyIn(targetChild.values);
1095  if(!targetChild.isLeaf()) {
1096  leftSibling.children.copyIn(targetChild.children);
1097  }
1098 
1099  node.children.removeAt(
1100  node.children.begin() + indexOfLB
1101  );
1102 
1103  markNodeDeleted_(targetChildIndex);
1104 
1105  --indexOfLB;
1106  } else { // Merge with right sibling
1107  unsigned rightSiblingIndex = node.children.at(indexOfLB + 1);
1108  auto& rightSibling = getNode_(rightSiblingIndex);
1109 
1110  targetChild.values.push_back(
1111  node.values.at(indexOfLB)
1112  );
1113  node.values.removeAt(
1114  node.values.begin() + indexOfLB
1115  );
1116 
1117  targetChild.values.copyIn(rightSibling.values);
1118  if(!targetChild.isLeaf()) {
1119  targetChild.children.copyIn(rightSibling.children);
1120  }
1121 
1122  node.children.removeAt(
1123  node.children.begin() + indexOfLB + 1
1124  );
1125 
1126  markNodeDeleted_(rightSiblingIndex);
1127  }
1128  }
1129  }
1130 
1131  delete_(node.children.at(indexOfLB), value);
1132  }
1133  }
1134 
1136  constexpr void validate_(unsigned nodeIndex) const {
1137  // The node should not be in the garbage
1138  auto foundIter = garbage_.begin();
1139 
1140  while(foundIter != garbage_.end()) {
1141  if(*foundIter == nodeIndex) {
1142  break;
1143  }
1144 
1145  ++foundIter;
1146  }
1147 
1148  // Skip if the current node is in the garbage
1149  if(foundIter != garbage_.end()) {
1150  throw "An active node is marked as garbage!";
1151  }
1152 
1153  auto& node = getNode_(nodeIndex);
1154 
1155  // A non-root node has min. t-1 values
1156  if(
1157  !isRootNode_(nodeIndex)
1158  && node.values.size() < minDegree - 1
1159  ) {
1160  throw "Not every internal node has min. t-1 values!";
1161  }
1162 
1163  // Every internal node with n values has n+1 children
1164  if(
1165  !isRootNode_(nodeIndex)
1166  && !node.isLeaf()
1167  && node.values.size() != node.children.size() - 1
1168  ) {
1169  throw "Not every internal node with n values has n+1 children!";
1170  }
1171 
1172  // Every value list is ordered
1173  if(!isTotallyOrdered(node.values)) {
1174  throw "Not all value lists are totally ordered!";
1175  }
1176 
1177  /* Children 'between' values have values that are within the interval set by
1178  * the parents
1179  */
1180  if(!node.isLeaf()) {
1181  for(unsigned i = 1; i < node.children.size(); ++i) {
1182  if(
1183  !lt_(
1184  getNode_(node.children.at(i - 1)).values.back(),
1185  node.values.at(i - 1)
1186  ) || !lt_(
1187  node.values.at(i - 1),
1188  getNode_(node.children.at(i)).values.front()
1189  )
1190  ) {
1191  throw "Not all children's values are bounded by the parent!";
1192  }
1193  }
1194  }
1195  }
1197 };
1198 
1199 } // namespace Temple
1200 } // namespace Molassembler
1201 } // namespace Scine
1202 
1203 #endif
PURITY_WEAK constexpr const Node & getNode_(unsigned nodeIndex) const
Fetch an unmodifiable node by its &#39;pointer&#39;.
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_
&#39;Pointer&#39; 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 &#39;deleted&#39; 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_()
&#39;Allocates&#39; a new node and returns a &#39;pointer&#39; 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&#39;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 &#39;pointer&#39;.
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 &#39;pointers&#39; to any &#39;deleted&#39; 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.
Basic optional type.
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