1 /**
2 * Vanilla B-Tree implementation.
3 * Note that this is an implementation detail of dplug.core.map and not part of
4 * the public dplug:core API.
5 *
6 * Copyright: Copyright Guillaume Piolat 2024.
7 * License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
8 * Authors: Guillaume Piolat
9 */
10 module dplug.core.btree;
11
12 import dplug.core.nogc;
13
14 import std.functional: binaryFun;
15
16 //debug = btree;
17
18 debug(btree)
19 {
20 import core.stdc.stdio;
21 }
22
23 /**
24 An implementation of a vanilla B-Tree.
25
26 The API should looks closely like the builtin associative arrays.
27 O(lg(n)) insertion, removal, and search time.
28 This `BTree` is designed to operate even without initialization through
29 `makeBTree`.
30
31 Note: the keys don't need opEquals, but !(a < b) && !(b > a) should
32 imply that a == b
33
34 Reference:
35 http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap19.htm
36 https://en.wikipedia.org/wiki/B-tree
37 */
38 // TODO: map over range of keys
39 // PERF: tune minDegree vs size of K and V, there must be a sweet spot
40 // PERF: allocate nodes in memory pool, to be built in bulk.
41 // How does reclaim works in that case, in a way that doesn't explode
42 // memory?
43 // PERF: first node could be interned in the struct itself (interior pointer)
44 // however that requires first to tweak the branching factor with size
45 // of item.
46 // PERF: (requires: Node memory pool) find a way to deallocate all at once
47 // PERF: find how to use duplicateKeyIsUB for Map and Set
48 struct BTree(K, // type of the keys
49 V, // type of the values
50 alias less = "a < b", // must be strict inequality
51
52 bool allowDuplicates = false, // dupe keys allowed or not
53
54 bool duplicateKeyIsUB = false) // user guarantees no duplicates
55 // for faster inserts
56 // (works when !allowDuplicates)
57 {
58 public:
59 nothrow:
60 @nogc:
61
62 /// Called "t" or "minimum degree" in litterature, can never be < 2.
63 /// Make it lower (eg: 2) to test tree algorithms.
64 /// See <digression> below to see why this is not B-Tree "order".
65 enum minDegree = 16;
66
67 // Every node must have >= minKeysPerNode and <= maxKeysPerNode.
68 // The root node is allowed to have < minKeysPerNode (but not zero).
69 enum int minKeys = minDegree - 1;
70 enum int maxKeys = 2 * minDegree - 1;
71 enum int minChildren = minDegree;
72 enum int maxChildren = 2 * minDegree;
73
74 debug(btree) invariant()
75 {
76 checkInvariant();
77 }
78
79 // Not copyable.
80 @disable this(this);
81
82 /**
83 Constructor.
84 */
85 this(int dummy)
86 {
87 // It does nothing, because T.init is valid.
88 }
89
90 /**
91 Destructor. All nodes are cleared.
92 */
93 ~this()
94 {
95 if (_root)
96 {
97 _root.reclaimMemory();
98 _root = null;
99 }
100 }
101
102 /**
103 Number of items in the B-Tree.
104 Returns: Number of elements.
105 */
106 size_t length() const
107 {
108 return _count;
109 }
110
111 /**
112 Is this B-Tree empty?
113 Returns: `true` if zero elements.
114 */
115 bool empty() const
116 {
117 return _count == 0;
118 }
119
120 /**
121 Insert an element in the container.
122
123 Returns: `true` if the insertion took place.
124 If duplicates are supported, return true.
125
126 WARNING: inserting duplicate keys when duplicates are not supported
127 is Undefined Behaviour. Use `contains()` to avoid that case.
128 */
129 bool insert(K key, V value)
130 {
131 lazyInitialize();
132
133 // Runtime check to prevent accidental dupe keys.
134 static if (!allowDuplicates)
135 {
136 static if (duplicateKeyIsUB)
137 {
138 // Detect dupes, but in -release it will be Undefined Behaviour
139 assert(findKeyValue(_root, key) is null);
140 }
141 else
142 {
143 // Always detect dupes, this slows down insertion by a lot
144 if (findKeyValue(_root, key) !is null)
145 return false;
146 }
147 }
148
149 Node* r = _root;
150
151 if (r.isFull())
152 {
153 Node* s = allocateNode();
154 _root = s;
155 s.parent = null;
156 s.isLeaf = false;
157 s.numKeys = 0;
158 s.children[0] = r;
159 r.parent = s;
160 splitChild(s, 0, r);
161 insertNonFull(s, key, value);
162 }
163 else
164 {
165 insertNonFull(r, key, value);
166 }
167
168 _count += 1;
169 return true;
170 }
171
172 /**
173 Return forward range of values, over all elements.
174 */
175 auto byValue()
176 {
177 return BTreeRange!(RangeType.value)(this);
178 }
179 ///ditto
180 auto byValue() const
181 {
182 return const(BTreeRange!(RangeType.value))(this);
183 }
184
185 /**
186 Return forward range of keys, over all elements.
187 */
188 auto byKey()
189 {
190 return BTreeRange!(RangeType.key)(this);
191 }
192 ///ditto
193 auto byKey() const
194 {
195 return const(BTreeRange!(RangeType.key))(this);
196 }
197
198 /**
199 Return forward range of a struct that has .key and .value.
200 */
201 auto byKeyValue()
202 {
203 return BTreeRange!(RangeType.keyValue)(this);
204 }
205 ///ditto
206 auto byKeyValue() const
207 {
208 return const(BTreeRange!(RangeType.keyValue))(this);
209 }
210
211 /**
212 Erases an element from the tree, if found.
213 Returns: Number of elements erased (for now: 0 or 1 only).
214 */
215 size_t remove(K key)
216 {
217 if (_root is null)
218 return 0;
219
220 int keyIndex;
221 Node* node = findNode(_root, key, keyIndex);
222 if (node is null)
223 return 0; // not found
224
225 _count -= 1;
226
227 // Reference: https://www.youtube.com/watch?app=desktop&v=0NvlyJDfk1M
228 if (node.isLeaf)
229 {
230 // First, remove key, then eventually rebalance.
231 deleteKeyValueAtIndexAndShift(node, keyIndex);
232 rebalanceAfterDeletion(node);
233 }
234 else
235 {
236 // Exchange key with either highest of the smaller key in leaf,
237 // or largest of the highest keys
238 // . value .
239 // / \
240 // / \
241 // / \
242 // left subtree right subtree
243
244 // But I'm not sure why people tout this solution.
245 // Here we simply always get to the rightmost leaf node of left
246 // subtree. It seems it's always possible indeed, and it's not
247 // faster to look at the other sub-tree.
248 Node* leafNode = node.children[keyIndex];
249 while (!leafNode.isLeaf)
250 leafNode = leafNode.children[leafNode.numKeys];
251 assert(leafNode);
252
253 // Remove key from leaf node, put it instead of target.
254 node.kv[keyIndex] = leafNode.kv[leafNode.numKeys-1];
255 leafNode.numKeys -= 1;
256
257 // and then rebalance
258 rebalanceAfterDeletion(leafNode);
259 }
260
261 return 1;
262 }
263
264 /**
265 `in` operator. Check to see if the given element exists in the
266 container.
267 In case of duplicate keys, it returns one of those, unspecified order.
268 */
269 inout(V)* opBinaryRight(string op)(K key) inout if (op == "in")
270 {
271 if (_root is null)
272 return null;
273 inout(KeyValue)* kv = findKeyValue(_root, key);
274 if (!kv) return null;
275 return &kv.value;
276 }
277
278 /**
279 Index the B-Tree by key.
280 Returns: A reference to the value corresponding to this key.
281 In case of duplicate keys, it returns one of the values,
282 in unspecified order.
283 */
284 ref inout(V) opIndex(K key) inout
285 {
286 inout(V)* p = key in this;
287 return *p;
288 }
289
290 /**
291 Search for an element.
292 Returns: `true` if the element is present.
293 */
294 bool contains(K key) const
295 {
296 if (_root is null)
297 return false;
298 return findKeyValue(_root, key) !is null;
299 }
300
301 private:
302
303 alias _less = binaryFun!less;
304
305 Node* _root;
306 size_t _count;
307
308 void checkInvariant() const
309 {
310 int count = 0;
311 if (_root)
312 {
313 assert(_count > 0);
314 checkNodeInvariant(_root, null, count);
315 }
316 else
317 {
318 assert(_count == 0); // No elements <=> null _root node.
319 }
320 assert(count == _count);
321 }
322
323 // null if not found
324 inout(KeyValue)* findKeyValue(inout(Node)* x, K key) inout
325 {
326 int index;
327 inout(Node)* node = findNode(x, key, index);
328 if (node is null)
329 return null;
330 else
331 return &(node.kv[index]);
332 }
333
334 // Return containing node + index of value in store, or null if not found.
335 inout(Node)* findNode(inout(Node)* x, K key, out int index) inout
336 {
337 int i = 0;
338 while (i < x.numKeys && _less(x.kv[i].key, key))
339 i += 1;
340
341 // Like in Phobos' Red Black tree, use !less(a,b) && !less(b,a) instead
342 // of opEquals.
343
344 if (i < x.numKeys && !_less(key, x.kv[i].key))
345 {
346 index = i;
347 return x;
348 }
349 else
350 {
351 if (x.isLeaf)
352 return null;
353 else
354 return findNode(x.children[i], key, index);
355 }
356 }
357
358 // Create root node if none.
359 void lazyInitialize()
360 {
361 if (_root)
362 return;
363
364 _root = allocateNode;
365 _root.isLeaf = true;
366 _root.numKeys = 0;
367 _root.parent = null;
368 }
369
370 void insertNonFull(Node* x, K key, V value)
371 {
372 int i = x.numKeys - 1;
373 if (x.isLeaf)
374 {
375 while (i >= 0 && _less(key, x.kv[i].key))
376 {
377 x.kv[i+1] = x.kv[i];
378 i -= 1;
379 }
380 x.kv[i+1] = KeyValue(key, value);
381 x.numKeys++;
382 }
383 else
384 {
385 while (i >= 0 && _less(key, x.kv[i].key))
386 {
387 i -= 1;
388 }
389 i += 1;
390 Node* c = x.children[i];
391 if (c.isFull)
392 {
393 splitChild(x, i, c);
394 if (_less(x.kv[i].key, key))
395 {
396 i = i + 1;
397 c = x.children[i];
398 }
399 }
400 insertNonFull(c, key, value);
401 }
402 }
403
404 // x = a parent with at least one slot available
405 // y = a full node to split
406 void splitChild(Node* x, int i, Node* y)
407 {
408 // create new child, that will take half the keyvalues and children of
409 // the full y node
410 Node* z = allocateNode();
411 z.isLeaf = y.isLeaf;
412 z.numKeys = minDegree - 1;
413 z.parent = x;
414
415 // copy half of values (highest) in new child
416 for (int j = 0; j < minDegree - 1; ++j)
417 {
418 z.kv[j] = y.kv[minDegree + j];
419 }
420
421 // same for child pointer if any
422 if (!y.isLeaf)
423 {
424 for (int j = 0; j < minDegree; ++j)
425 {
426 z.children[j] = y.children[minDegree + j];
427 z.children[j].parent = z;
428 }
429 }
430
431 // Formerly full child now has room again
432 y.numKeys = minDegree - 1;
433
434 // And now for the parent node:
435 // * new child is inserted right of its older sibling
436 for (int j = x.numKeys; j > i; --j)
437 {
438 x.children[j+1] = x.children[j];
439 }
440 x.children[i+1] = z;
441 for (int j = x.numKeys - 1; j >= i; --j)
442 {
443 x.kv[j+1] = x.kv[j];
444 }
445 // * middle key is choosen as pivot
446 x.kv[i] = y.kv[minDegree-1];
447 x.numKeys += 1;
448 }
449
450 // Take one node that is exactly below capacity, and reinstate
451 // the invariant by merging nodes and exchanging with neighbours.
452 // Is called on nodes that might be missing exactly one item.
453 void rebalanceAfterDeletion(Node* node)
454 {
455 if (node.parent is null) // is this the tree _root?
456 {
457 assert(_root is node);
458
459 if (_root.numKeys == 0)
460 {
461 if (_root.isLeaf) // no more items in tree
462 {
463 destroyFree(_root);
464 _root = null;
465 }
466 else // tree is reduced by one level
467 {
468 Node* oldRoot = _root;
469 _root = oldRoot.children[0];
470 _root.parent = null;
471 oldRoot.numKeys = -1;
472 oldRoot.children[0] = null; // so that it is not destroyed
473 destroyFree(oldRoot); // <- here
474 }
475 }
476 return;
477 }
478
479 if (node.numKeys >= minKeys)
480 return; // no balance issue, exit
481
482 // Else, the node is missing one key
483 assert(node.numKeys == minKeys - 1);
484
485 Node* parent = node.parent;
486 assert(parent !is null);
487
488 Node* left;
489 Node* right;
490 int childIndex = -1;
491 for (int n = 0; n < parent.numChildren; ++n)
492 {
493 if (parent.children[n] == node)
494 {
495 childIndex = n;
496 break;
497 }
498 }
499
500 if (childIndex != 0) // has left sibling?
501 left = parent.children[childIndex-1];
502
503 if (childIndex + 1 < parent.numChildren) // has right sibling?
504 right = parent.children[childIndex+1];
505
506 assert(left || right); // one of those must exists
507
508 if (left && left.numKeys > minKeys)
509 {
510 // Take largest key from left sibling, it becomes the new pivot in
511 // parent. Old pivot erase our key (and if non-leaf, gets the left
512 // sibling right subtree + the node one child).
513 assert(left.isLeaf == node.isLeaf);
514 KeyValue largest = left.kv[left.numKeys - 1];
515 Node* rightMostChild = left.children[left.numKeys];
516 left.numKeys -= 1;
517 KeyValue pivot = node.parent.kv[childIndex-1];
518 node.parent.kv[childIndex-1] = largest;
519
520 // Pivot enter at position 0.
521 // Need to shift a few kv.
522 for (int n = minKeys - 1; n > 0; --n)
523 {
524 node.kv[n] = node.kv[n-1];
525 }
526 node.kv[0] = pivot;
527 if (!node.isLeaf)
528 {
529 for (int n = minKeys; n > 0; --n)
530 {
531 node.children[n] = node.children[n-1];
532 }
533 node.children[0] = rightMostChild;
534 rightMostChild.parent = node;
535 }
536 node.numKeys = minKeys;
537 }
538 else if (right && right.numKeys > minKeys)
539 {
540 // Take smallest key from right sibling, it becomes the new pivot
541 // in parent. Old pivot erase our key.
542 assert(right.isLeaf == node.isLeaf);
543 KeyValue smallest = right.kv[0];
544 Node* leftMostChild = right.children[0];
545
546 // Delete first key (and first child, if any) of right sibling.
547 if (!node.isLeaf)
548 {
549 for (int n = 0; n < right.numKeys; ++n)
550 right.children[n] = right.children[n+1];
551 }
552 deleteKeyValueAtIndexAndShift(right, 0);
553
554 KeyValue pivot = parent.kv[childIndex];
555 parent.kv[childIndex] = smallest;
556 node.kv[minKeys - 1] = pivot;
557 if (!node.isLeaf)
558 {
559 leftMostChild.parent = node;
560 node.children[minKeys] = leftMostChild;
561 }
562 node.numKeys = minKeys;
563 }
564 else
565 {
566 // merge with either left or right
567 if (right)
568 {
569 mergeChild(parent, childIndex);
570 }
571 else if (left)
572 {
573 mergeChild(parent, childIndex - 1);
574 }
575 else
576 assert(0);
577 }
578 }
579
580 // Merge children nth and nth+1, which must both have min amount of keys
581 // it makes one node with max amount of keys
582 void mergeChild(Node* parent, int nth)
583 {
584 Node* left = parent.children[nth];
585 Node* right = parent.children[nth+1];
586 KeyValue pivot = parent.kv[nth];
587 assert(left.isLeaf == right.isLeaf);
588
589 // One key is missing already
590 assert(left.numKeys + right.numKeys == 2*minKeys - 1);
591
592 left.kv[left.numKeys] = pivot;
593
594 for (int n = 0; n < right.numKeys; ++n)
595 {
596 left.kv[left.numKeys + 1 + n] = right.kv[n];
597 }
598 if (!left.isLeaf)
599 {
600 for (int n = 0; n < right.numKeys+1; ++n)
601 {
602 left.children[left.numKeys + 1 + n] = right.children[n];
603 assert(right.children[n].parent == right);
604 left.children[left.numKeys + 1 + n].parent = left;
605 }
606 }
607 left.numKeys = 2 * minKeys;
608
609 // in parent, shift all by one
610 parent.numKeys -= 1;
611 for (int n = nth; n < parent.numKeys; ++n)
612 {
613 parent.kv[n] = parent.kv[n+1];
614 parent.children[n+1] = parent.children[n+2];
615 }
616
617 // in case the parent has too few elements
618 rebalanceAfterDeletion(parent);
619
620 destroyFree(right);
621 }
622
623 // internal use, delete a kv and shift remaining kv
624 void deleteKeyValueAtIndexAndShift(Node* node, int index)
625 {
626 node.numKeys -= 1;
627 for (int n = index; n < node.numKeys; ++n)
628 {
629 node.kv[n] = node.kv[n+1];
630 }
631 }
632
633 void checkNodeInvariant(const(Node)* node, const(Node)* parent,
634 ref int count) const
635 {
636 // Each node of the tree except the root must contain at least
637 // `minDegree − 1` keys (and hence must have at least `minDegree`
638 // children if it is not a leaf).
639 if (parent !is null)
640 {
641 assert(node.numKeys >= minKeys);
642 assert(node.numKeys <= maxKeys);
643
644 // parent can't be a leaf
645 assert(!parent.isLeaf);
646 }
647 else
648 {
649 assert(node.numKeys >= 1);
650 }
651
652 assert(parent is node.parent);
653
654 count += node.numKeys;
655
656 if (!node.isLeaf)
657 {
658 // Check child invariants.
659 for (int n = 0; n < node.numChildren(); ++n)
660 {
661 checkNodeInvariant(node.children[n], node, count);
662 }
663
664 // Check internal key ordering
665 for (int n = 0; n + 1 < node.numKeys; ++n)
666 {
667 const(K) k1 = node.kv[n].key;
668 const(K) k2 = node.kv[n+1].key;
669 static if (allowDuplicates)
670 {
671 assert(! _less(k2, k1));
672 }
673 else
674 {
675 assert(_less(k1, k2));
676 }
677 }
678
679 // Check key orderings with children. All keys of child must be
680 // inside parent range.
681 for (int n = 0; n < node.numKeys; ++n)
682 {
683 const(K) k = node.kv[n].key;
684
685 // All key of left children must be smaller, right must be
686 // larger.
687 const(Node)* left = node.children[n];
688 const(Node)* right = node.children[n+1];
689
690 for (int m = 0; m < left.numKeys; ++m)
691 {
692 static if (allowDuplicates)
693 {
694 assert(! _less(k, left.kv[m].key));
695 }
696 else
697 {
698 assert(_less(left.kv[m].key, k));
699 }
700 }
701
702 for (int m = 0; m < right.numKeys; ++m)
703 {
704 static if (allowDuplicates)
705 {
706 assert(!_less(right.kv[m].key, k));
707 }
708 else
709 {
710 assert(_less(k, right.kv[m].key));
711 }
712 }
713 }
714 }
715 }
716
717 static struct KeyValue
718 {
719 K key;
720 V value;
721 }
722
723 debug(btree)
724 public void display()
725 {
726 printf("Tree has %zu elements\n", _count);
727 if (_root)
728 _root.display();
729 else
730 {
731 printf(" * no root\n");
732 }
733 }
734
735 Node* allocateNode()
736 {
737 Node* node = mallocNew!Node();
738 node.treeRef = &this;
739 return node;
740 }
741
742 void deallocateNode(Node* node)
743 {
744 destroyFree!Node(node);
745 }
746
747
748 static struct Node
749 {
750 nothrow @nogc:
751 // Is this a leaf node?
752 bool isLeaf;
753
754 // This node stored numKeys keys, and numKeys+1 children.
755 int numKeys;
756
757 // Keys and values together.
758 KeyValue[maxKeys] kv;
759
760 // (borrowed) Parent node. Can be null, for the root.
761 Node* parent;
762
763 // (owning) Pointer to child nodes.
764 Node*[maxChildren] children;
765
766 BTree* treeRef;
767
768 /// Number of children = numKeys + 1
769 int numChildren() const
770 {
771 assert(!isLeaf); // leaves have no child
772 return numKeys + 1;
773 }
774
775 bool isFull() const
776 {
777 return numKeys == maxKeys;
778 }
779
780 void reclaimMemory()
781 {
782 if (isLeaf)
783 return;
784
785 for (int c = 0; c < numChildren(); ++c)
786 {
787 children[c].reclaimMemory();
788 }
789
790 treeRef.deallocateNode(&this);
791 }
792
793 debug(btree)
794 void display()
795 {
796 printf("\nNode %p\n", &this);
797 printf(" * parent = %p\n", parent);
798 printf(" * leaf = %s\n", isLeaf ? "yes".ptr: "no".ptr);
799 printf(" * numKeys = %d\n", numKeys);
800
801 if (numKeys > 0)
802 {
803 for (int v = 0; v < numKeys; ++v)
804 {
805 static if (is(V == string))
806 printf(" - Contains key %d and value %s\n",
807 kv[v].key, kv[v].value.ptr);
808 else
809 printf(" - Contains key %d\n", kv[v].key);
810 }
811 }
812 if (!isLeaf)
813 {
814 for (int v = 0; v < numKeys+1; ++v)
815 {
816 printf(" - Point to child %p\n", children[v]);
817 }
818 }
819 printf("\n");
820
821 if (!isLeaf)
822 {
823 for (int v = 0; v < numKeys+1; ++v)
824 {
825 children[v].display;
826 }
827 }
828 }
829 }
830
831
832 public:
833
834 enum RangeType
835 {
836 key,
837 value,
838 keyValue
839 }
840
841 /// Btree Range
842 static struct BTreeRange(RangeType type)
843 {
844 nothrow @nogc:
845 this(ref BTree tree)
846 {
847 _current = tree._root;
848 if (_current is null)
849 return;
850 while(!_current.isLeaf)
851 _current = _current.children[0];
852 }
853
854 this(ref const(BTree) tree)
855 {
856 _current = cast(Node*)(tree._root); // const_cast here
857 if (_current is null)
858 return;
859 while(!_current.isLeaf)
860 _current = _current.children[0];
861 }
862
863 bool empty() const
864 {
865 return _current is null;
866 }
867
868 auto front()
869 {
870 static if (type == RangeType.key)
871 return _current.kv[_currentItem].key;
872 static if (type == RangeType.value)
873 return _current.kv[_currentItem].value;
874 static if (type == RangeType.keyValue)
875 return _current.kv[_currentItem];
876 }
877
878 void popFront()
879 {
880 // Basically, _current and _currentItem points at a key.
881 //
882 // 3
883 // / \
884 // 1-2 4-5
885 //
886 // Case 1: increment _currentItem
887 // Case 2: increment _currentItem, see that it's out of bounds.
888 // go up the parent chain, find position of child
889 // repeat if needed
890 // then point at pivot if any, or terminate.
891 // Case 3: See that you're not in a leaf.
892 // Go down to the leftmost leaf of the right sub-tree.
893 // Start at first item. This one always exist.
894 // Case 4: same as case 1.
895 // Case 5: same as case 2.
896
897 // If not a leaf, go inside the next children
898 if (!_current.isLeaf)
899 {
900 // Case 3
901 assert(_currentItem + 1 < _current.numChildren);
902 _current = _current.children[_currentItem+1];
903 while (!_current.isLeaf)
904 _current = _current.children[0];
905 _currentItem = 0;
906 }
907 else
908 {
909 _currentItem += 1;
910 if (_currentItem >= _current.numKeys)
911 {
912 while(true)
913 {
914 if (_current.parent is null)
915 {
916 _current = null; // end of iteration
917 break;
918 }
919 else
920 {
921 // Find position of child in parent
922 int posInParent = -2;
923 Node* child = _current;
924 Node* parent = _current.parent;
925
926 // Possibly there is a better way to do it with a
927 // stack somewhere. But that would require to know
928 // the maximum level.
929 // That, or change everything to be B+Tree.
930 for (int n = 0; n < parent.numChildren(); ++n)
931 {
932 if (parent.children[n] == child)
933 {
934 posInParent = n;
935 break;
936 }
937 }
938
939 assert(posInParent != -2); // else tree invalid
940
941 if (posInParent < parent.numKeys)
942 {
943 // Point at pivot
944 _current = parent;
945 _currentItem = posInParent;
946 break;
947 }
948 else
949 {
950 // continue searching up for a pivot
951 _current = parent;
952 }
953 }
954 }
955 }
956 else
957 {
958 // Case 1, nothing to do.
959 }
960 }
961 }
962
963 private:
964 // Next item returned by .front
965 Node* _current;
966 int _currentItem;
967 }
968 }
969
970 // <digression>
971 //
972 // A short note about B-tree "Knuth order" vs t/minDegree.
973 //
974 // t or "minimum degree" ensures an even number of children in full nodes.
975 //
976 // .----------------+---------------+-------------------.
977 // | minDegree max | keys per node | children per node |
978 // |----------------+---------------+-------------------|
979 // | 2 | 1 to 3 | 2 to 4 |
980 // | 3 | 2 to 5 | 3 to 6 |
981 // | 4 | 3 to 7 | 4 to 8 |
982 // +----------------+---------------+-------------------+
983 //
984 // However Knuth defines that as an "order" m, which can be _odd_.
985 // https://stackoverflow.com/questions/42705423/can-an-m-way-b-tree-have-m-odd
986 //
987 // In this case, the possible B-tree item bounds are:
988 //
989 // .----------------+---------------+-------------------.
990 // | m | keys per node | children per node |
991 // |----------------+---------------+-------------------|
992 // | 4 | 1 to 3 | 2 to 4 |
993 // | 5 | 2 to 4 | 3 to 5 |
994 // | 6 | 2 to 5 | 3 to 6 |
995 // | 7 | 3 to 6 | 4 to 7 |
996 // | 8 | 3 to 7 | 4 to 8 |
997 // +----------------+---------------+-------------------+
998 //
999 // So, while things are similar for even m, they are different
1000 // for odd m and some Internet example use m = 5.
1001 // If we disallow non-even m, then it's impossible to
1002 // It makes a difference in deletion, because two minimally
1003 // filled nodes + a pivot can be merged together if m is even.
1004 //
1005 // Our implementation does NOT allow for odd m.
1006 //
1007 // </digression>
1008
1009 unittest // .init testing, basics
1010 {
1011 // It should be possible to use most function of an uninitialized Map
1012 // All except functions returning a range will work.
1013 BTree!(int, string) m;
1014
1015 assert(m.length == 0);
1016 assert(m.empty);
1017 assert(!m.contains(7));
1018 m.insert(7, "lol");
1019 assert(m.contains(7));
1020 assert(m[7] == "lol");
1021 m.remove(7);
1022 assert(!m.contains(7));
1023 assert(m.length == 0);
1024 assert(m.empty);
1025 assert(m._root == null);
1026 }
1027
1028 unittest // add and delete in reverse order
1029 {
1030 enum int N = 10;
1031 for (int G = 0; G < 1; ++G)
1032 {
1033 BTree!(int, string) m;
1034 for (int k = 0; k < N; ++k)
1035 {
1036 m.insert(k, "l");
1037 }
1038
1039 assert(m.length == N);
1040 for (int k = N-1; k >= 0; --k)
1041 {
1042 assert(1 == m.remove(k));
1043 }
1044 assert(m.length == 0);
1045 assert(m.empty);
1046 }
1047 }
1048
1049 unittest // dupe keys
1050 {
1051 BTree!(int, int, "a < b", true) m;
1052 enum KEY = 4;
1053
1054 for (int n = 0; n < 32; ++n)
1055 {
1056 m.insert(KEY, 1 << n);
1057 }
1058
1059 foreach(k; m.byKey)
1060 assert(k == KEY);
1061
1062 int r = 0;
1063 for (int n = 0; n < 32; ++n)
1064 {
1065 int* p = KEY in m;
1066 assert(p);
1067 r |= *p;
1068 assert(m.remove(KEY) == 1);
1069 }
1070 assert(r == -1); // all were popped
1071 }
1072
1073 unittest // "in" without initialization
1074 {
1075 BTree!(int, int) m;
1076 void* p = 1 in m;
1077 assert(p is null);
1078 }
1079
1080 unittest
1081 {
1082 BTree!(int, int) m;
1083 m.insert(4, 5);
1084 m.insert(4, 9);
1085 }