-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathBtreeStuckStatic.java
1494 lines (1335 loc) · 97.7 KB
/
BtreeStuckStatic.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
//------------------------------------------------------------------------------
// BtreeStuck using a static Stuck instead of Stack
// Philip R Brenan at appaapps dot com, Appa Apps Ltd Inc., 2024
//------------------------------------------------------------------------------
package com.AppaApps.Silicon; // Design, simulate and layout a btree in a block on the surface of a silicon chip.
import java.util.*;
class BtreeStuckStatic extends Test // Manipulate a btree
{final int
maxKeysPerLeaf, // Maximum number of leafs in a key
maxKeysPerBranch, // Maximum number of keys in a branch
splitLeafSize, // The number of key, data pairs to split out of a leaf
splitBranchSize; // The number of key, next pairs to split out of a branch
final Node root; // The root of the tree
final Stack<Node> nodes = new Stack<>(); // The leaves and branches comprising the tree
final static int
linesToPrintABranch = 4, // The number of lines required to print a branch
maxPrintLevels = 10, // Maximum number of levels to print in a tree
maxDepth = 99; // Maximum depth of any realistic tree
int nodeCount = 0; // Unique number for each node
int maxNodeUsed = 0; // Maximum branch or leaf index used
static boolean debug = false; // Debugging enabled
//D1 Construction // Create a BTree from nodes which can be branches or leaves. The data associated with the BTree is stored only in the leaves opposite the keys
BtreeStuckStatic(int MaxKeysPerLeaf, int MaxKeysPerBranch) // Define a BTree with the specified dimensions
{z();
maxKeysPerLeaf = MaxKeysPerLeaf;
maxKeysPerBranch = MaxKeysPerBranch;
splitLeafSize = maxKeysPerLeaf >> 1;
splitBranchSize = maxKeysPerBranch >> 1;
nodes.push(root = new Node()); // The root
root.isLeaf = true; // The root starts as a leaf
}
//D1 Control // Testing, control and integrity
void ok(String expected) {Test.ok(toString(), expected);} // Confirm tree is as expected
void stop() {Test.stop(toString());} // Stop after printing the tree
public String toString() {return print();} // Print the tree
//D1 Components // A branch or leaf in the tree
class Node // A branch or leaf in the tree
{boolean isLeaf; // A leaf if true
final int node = nodeCount++;
class KeyStuck extends StuckStatic {int maxSize() {return maxKeysPerLeaf;}}; // Key, data pairs when a leaf
class NextStuck extends StuckStatic {int maxSize() {return maxKeysPerBranch+1;}}; // Key, next pairs when a branch. The last entry is top and so this stack must always have at least one element in it when the node is acting as a branch
final StuckStatic keyData = new KeyStuck(); // Key, data pairs when a leaf
final StuckStatic keyNext = new NextStuck(); // Key, next pairs when a branch. The last entry is top and so this stack must always have at least one element in it when the node is acting as a branch
void assertLeaf() {if (!isLeaf) stop("Leaf required");}
void assertBranch() {if ( isLeaf) stop("Branch required");}
Node allocLeaf() {z();
final Node n = new Node(); nodes.push(n); n.isLeaf = true; return n;}
Node allocBranch() {z();
final Node n = new Node(); nodes.push(n); n.isLeaf = false; return n;}
int leafSize() {z(); return keyData.size();} // Number of children in body of leaf
int branchSize() {z(); return keyNext.size() - 1;} // Number of children in body of branch
boolean isFull() // The node is full
{z(); return isLeaf ? leafSize() == maxKeysPerLeaf : branchSize() == maxKeysPerBranch;
}
boolean isLow() // The node is low on children making it impossible to merge two sibling children
{z(); return (isLeaf ? leafSize() : branchSize()) < 2;
}
boolean hasLeavesForChildren() // The node has leaves for children
{z(); assertBranch();
final int last = keyNext.lastElement1().data;
return nodes.elementAt(last).isLeaf;
}
int top() // The top next element of a branch
{z(); assertBranch();
return keyNext.elementAt1(branchSize()).data;
}
public String toString() // Print a node
{final StringBuilder s = new StringBuilder();
if (isLeaf) // Print a leaf
{s.append("Leaf(node:"+node+" size:"+leafSize()+")\n");
for (int i = 0; i < keyData.size(); i++)
{final StuckStatic.ElementAt kd = keyData.elementAt1(i);
s.append(" "+(i+1)+" key:"+kd.key+" data:"+kd.data+"\n");
}
}
else // Print a branch
{s.append("Branch(node:"+node+
" size:"+branchSize()+
" top:"+top()+"\n");
for (int i = 0; i < keyNext.size(); i++)
{final StuckStatic.ElementAt kn = keyNext.elementAt1(i);
s.append(" "+(i+1)+" key:"+kn.key+" next:"+kn.data+"\n");
}
}
return s.toString();
}
//D2 Search // Search within a node
class FindEqualInLeaf // Find the first key in the leaf that is equal to the search key
{Node leaf; // The leaf being searched
int search; // Search key
boolean found; // Whether the key was found
int data; // Data associated with the key
int index; // Index of first such key if found
FindEqualInLeaf() {} // Find the first key in the leaf that is equal to the search key
FindEqualInLeaf findEqualInLeaf(int Search) // Find the first key in the leaf that is equal to the search key
{z(); assertLeaf();
leaf = Node.this;
search = Search;
final StuckStatic.Search s = keyData.search1(Search);
found = s.found;
index = s.index;
data = s.data;
return this;
}
public String toString() // Print details of find equal in leaf
{final StringBuilder s = new StringBuilder();
s.append("FindEqualInLeaf(Leaf:"+leaf.node);
s.append(" Key:"+search+" found:"+found);
if (found) s.append(" data:"+data+" index:"+index);
s.append(")\n");
return s.toString();
}
}
final FindEqualInLeaf FindEqualInLeaf1 = new FindEqualInLeaf();
final FindEqualInLeaf FindEqualInLeaf2 = new FindEqualInLeaf();
FindEqualInLeaf findEqualInLeaf1(int Search) {return FindEqualInLeaf1.findEqualInLeaf(Search);}
FindEqualInLeaf findEqualInLeaf2(int Search) {return FindEqualInLeaf2.findEqualInLeaf(Search);}
class FindFirstGreaterThanOrEqualInLeaf // Find the first key in the leaf that is equal to or greater than the search key
{Node leaf; // The leaf being searched
int search; // Search key
boolean found; // Whether the key was found
int first; // Index of first such key if found
FindFirstGreaterThanOrEqualInLeaf // Find the first key in the leaf that is equal to or greater than the search key
findFirstGreaterThanOrEqualInLeaf(int Search) // Find the first key in the leaf that is equal to or greater than the search key
{z(); assertLeaf();
leaf = Node.this;
search = Search;
final StuckStatic.SearchFirstGreaterThanOrEqual s =
keyData.searchFirstGreaterThanOrEqual1(Search);
found = s.found;
first = s.index;
return this;
}
public String toString() // Print results of search
{final StringBuilder s = new StringBuilder();
s.append("FindFirstGreaterThanOrEqualInLeaf(Leaf:"+leaf.node);
s.append(" Key:"+search+" found:"+found);
if (found) s.append(" first:"+first);
s.append(")\n");
return s.toString();
}
}
final FindFirstGreaterThanOrEqualInLeaf FindFirstGreaterThanOrEqualInLeaf1 = new FindFirstGreaterThanOrEqualInLeaf();
final FindFirstGreaterThanOrEqualInLeaf FindFirstGreaterThanOrEqualInLeaf2 = new FindFirstGreaterThanOrEqualInLeaf();
FindFirstGreaterThanOrEqualInLeaf findFirstGreaterThanOrEqualInLeaf1(int Search) {return FindFirstGreaterThanOrEqualInLeaf1.findFirstGreaterThanOrEqualInLeaf(Search);}
FindFirstGreaterThanOrEqualInLeaf findFirstGreaterThanOrEqualInLeaf2(int Search) {return FindFirstGreaterThanOrEqualInLeaf2.findFirstGreaterThanOrEqualInLeaf(Search);}
class FindFirstGreaterThanOrEqualInBranch // Find the first key in the branch that is equal to or greater than the search key
{Node branch; // The branch being searched
int search; // Search key
boolean found; // Whether the key was found
int first; // Index of first such key if found
int next; // The corresponding next field or top if no such key was found
FindFirstGreaterThanOrEqualInBranch // Find the first key in the branch that is equal to or greater than the search key
findFirstGreaterThanOrEqualInBranch(int Search) // Find the first key in the branch that is equal to or greater than the search key
{z(); assertBranch();
branch = Node.this;
search = Search;
final StuckStatic.SearchFirstGreaterThanOrEqualExceptLast s =
keyNext.searchFirstGreaterThanOrEqualExceptLast1(Search);
found = s.found;
first = s.index;
next = s.found ? s.data : keyNext.lastElement1().data; // Next if no key matches
return this;
}
public String toString() // Print search results
{final StringBuilder s = new StringBuilder();
s.append("FindFirstGreaterThanOrEqualInBranch(branch:"+branch.node);
s.append(" Key:"+search+" found:"+found+" next:"+next);
if (found) s.append(" first:"+first);
s.append(")\n");
return s.toString();
}
}
final FindFirstGreaterThanOrEqualInBranch FindFirstGreaterThanOrEqualInBranch1 = new FindFirstGreaterThanOrEqualInBranch();
final FindFirstGreaterThanOrEqualInBranch FindFirstGreaterThanOrEqualInBranch2 = new FindFirstGreaterThanOrEqualInBranch();
FindFirstGreaterThanOrEqualInBranch findFirstGreaterThanOrEqualInBranch1(int Search) {return FindFirstGreaterThanOrEqualInBranch1.findFirstGreaterThanOrEqualInBranch(Search);}
FindFirstGreaterThanOrEqualInBranch findFirstGreaterThanOrEqualInBranch2(int Search) {return FindFirstGreaterThanOrEqualInBranch2.findFirstGreaterThanOrEqualInBranch(Search);}
//D2 Array // Represent the contents of the tree as an array
void leafToArray(Stack<KeyData>s) // Leaf as an array
{z(); assertLeaf();
final int K = leafSize();
for (int i = 0; i < K; i++)
{z();
final StuckStatic.ElementAt e = keyData.elementAt1(i);
s.push(new KeyData(e.key, e.data));
}
}
void branchToArray(Stack<KeyData>s) // Branch to array
{z(); assertBranch();
final int K = branchSize() + 1; // To allow for top next
if (K > 0) // Branch has key, next pairs
{z();
for (int i = 0; i < K; i++)
{z();
final int next = keyNext.elementAt1(i).data; // Each key, next pair
if (nodes.elementAt(next).isLeaf)
{z(); nodes.elementAt(next).leafToArray(s);
}
else
{z();
if (next == 0)
{say("Cannot descend through root from index", i,
"in branch", node);
break;
}
z(); nodes.elementAt(next).branchToArray(s);
}
}
}
}
//D2 Print // Print the contents of the tree
void printLeaf(Stack<StringBuilder>S, int level) // Print leaf horizontally
{assertLeaf();
padStrings(S, level);
final StringBuilder s = new StringBuilder(); // String builder
final int K = leafSize();
for (int i = 0; i < K; i++) s.append(""+keyData.elementAt1(i).key+",");
if (s.length() > 0) s.setLength(s.length()-1); // Remove trailing comma if present
s.append("="+node+" ");
S.elementAt(level*linesToPrintABranch).append(s.toString());
padStrings(S, level);
}
void printBranch(Stack<StringBuilder>S, int level) // Print branch horizontally
{ assertBranch();
if (level > maxPrintLevels) return;
padStrings(S, level);
final int K = branchSize();
final int L = level * linesToPrintABranch;
if (K > 0) // Branch has key, next pairs
{for (int i = 0; i < K; i++)
{final int next = keyNext.elementAt1(i).data; // Each key, next pair
if (nodes.elementAt(next).isLeaf)
{nodes.elementAt(next).printLeaf(S, level+1);
}
else
{if (next == 0)
{say("Cannot descend through root from index", i,
"in branch", node);
break;
}
nodes.elementAt(next).printBranch(S, level+1);
}
S.elementAt(L+0).append(""+keyNext.elementAt1(i).key); // Key
S.elementAt(L+1).append(""+node+(i > 0 ? "."+i : "")); // Branch,key, next pair
S.elementAt(L+2).append(""+keyNext.elementAt1(i).data);
}
}
else // Branch is empty so print just the index of the branch
{S.elementAt(L+0).append(""+node+"Empty");
}
final int top = top(); // Top next will always be present
S.elementAt(L+3).append(top); // Append top next
if (nodes.elementAt(top).isLeaf) // Print leaf
{ nodes.elementAt(top).printLeaf(S, level+1);
}
else // Print branch
{if (top == 0)
{say("Cannot descend through root from top in branch", node);
return;
}
nodes.elementAt(top).printBranch(S, level+1);
}
padStrings(S, level);
}
//D2 Split // Split nodes in half to increase the number of nodes in the tree
void splitLeafRoot() // Split a leaf which happens to be a full root into two half full leaves while transforming the root leaf into a branch
{z(); assertLeaf();
if (node != 0) stop("Wanted root, but got node:", node);
if (!isFull()) stop("Root is not full, but has size:", leafSize());
keyNext.clear();
isLeaf = false;
final Node l = allocLeaf(); // New left leaf
final Node r = allocLeaf(); // New right leaf
for (int i = 0; i < splitLeafSize; i++) // Build left leaf
{z();
final StuckStatic.Shift f = keyData.shift1();
l.keyData.push(f.key, f.data);
}
for (int i = 0; i < splitLeafSize; i++) // Build right leaf
{z();
final StuckStatic.Shift f = keyData.shift1();
r.keyData.push(f.key, f.data);
}
final int first = r.keyData.firstElement1().key; // First of right leaf
final int last = l.keyData. lastElement1().key; // Last of left leaf
final int kv = (last + first) / 2; // Insert left leaf into root
keyNext.push(kv, l.node); // Insert left leaf into root
keyNext.push(0, r.node); // Insert right into root. This will be the top node and so ignored by search ... except last.
keyData.clear(); // A leaf no more
}
void splitBranchRoot() // Split a branch which happens to be a full root into two half full branches while retaining the current branch as the root
{z(); assertBranch();
if (node != 0) stop("Not root, but node:", node);
if (!isFull()) stop("Root is not full, but has size:", branchSize());
final Node l = allocBranch(); // New left branch
final Node r = allocBranch(); // New right branch
for (int i = 0; i < splitBranchSize; i++) // Left
{z();
final StuckStatic.Shift f = keyNext.shift1();
l.keyNext.push(f.key, f.data);
}
final StuckStatic.Shift pl = keyNext.shift2(); // This key, next pair will be part of the root
l.keyNext.push(0, pl.data); // Becomes top and so ignored by search ... except last
for(int i = 0; i < splitBranchSize; i++) // Right
{z();
final StuckStatic.Shift f = keyNext.shift1();
r.keyNext.push(f.key, f.data);
}
final StuckStatic.Shift pr = keyNext.shift3(); // Top of root
r.keyNext.push(0, pr.data); // Becomes top and so ignored by search ... except last
keyData.clear(); keyNext.clear();
keyNext.push(pl.key, l.node);
keyNext.push(0, r.node); // Becomes top and so ignored by search ... except last
}
void splitLeaf(Node parent, int index) // Split a leaf which is not the root
{z(); assertLeaf();
if (node == 0) stop("Cannot split root with this method");
if (!isFull()) stop("Leaf:", node, "is not full, but has:", leafSize(), this);
if (parent.isFull()) stop("Parent:", parent, "must not be full");
if (index < 0) stop("Index", index, "too small");
if (index > leafSize()) stop("Index", index, "too big for leaf with:", leafSize());
final Node p = parent; // Parent
final Node l = allocLeaf(); // New split out leaf
final Node r = this; // Existing leaf
for (int i = 0; i < splitLeafSize; i++) // Build left leaf
{z();
final StuckStatic.Shift f = r.keyData.shift1();
l.keyData.push(f.key, f.data);
}
final int F = r.keyData.firstElement1().key;
final int L = l.keyData.lastElement1 ().key;
final int splitKey = (F + L) / 2;
p.keyNext.insertElementAt(splitKey, l.node, index); // Insert new key, next pair in parent
}
void splitBranch(Node parent, int index) // Split a branch which is not the root by splitting right to left
{z(); assertBranch();
if (node == 0) stop("Cannot split root with this method");
if (!isFull()) stop("Branch:", node, "is not full, but", branchSize());
if (parent.isFull()) stop("Parent:", parent.node, "must not be full");
if (index < 0) stop("Index", index, "too small in node:", node);
if (index > branchSize()) stop("Index", index, "too big for branch with:", branchSize(), "in node:", node);
final Node p = parent;
final Node l = allocBranch();
final Node r = this;
for (int i = 0; i < splitBranchSize; i++) // Build left branch
{z();
final StuckStatic.Shift f = r.keyNext.shift1();
l.keyNext.push(f.key, f.data);
}
final StuckStatic.Shift split = r.keyNext.shift1(); // Build right branch
l .keyNext.push(0, split.data); // Becomes top and so is iognored by search ... except last
parent.keyNext.insertElementAt(split.key, l.node, index);
}
boolean stealFromLeft(int index) // Steal from the left sibling of the indicated child if possible to give to the right - Dennis Moore, Dennis Moore, Dennis Moore.
{z(); assertBranch();
if (index == 0) return false;
if (index < 0) stop("Index", index, "too small");
if (index > branchSize()) stop("Index", index, "too big");
final StuckStatic.ElementAt L = keyNext.elementAt1(index-1);
final StuckStatic.ElementAt R = keyNext.elementAt2(index+0);
final StuckStatic p = keyNext;
if (hasLeavesForChildren()) // Children are leaves
{z();
final StuckStatic l = nodes.elementAt(L.data).keyData;
final StuckStatic r = nodes.elementAt(R.data).keyData;
final int nl = nodes.elementAt(L.data).leafSize();
final int nr = nodes.elementAt(R.data).leafSize();
if (nr >= maxKeysPerLeaf) return false; // Steal not possible because there is no where to put the steal
if (nl <= 1) return false; // Steal not allowed because it would leave the leaf sibling empty
final StuckStatic.LastElement ll = l.lastElement1();
r.insertElementAt(ll.key, ll.data, 0); // Increase right
l.pop(); // Reduce left
p.setElementAt (l.elementAt1(nl-2).key, L.data, index-1); // Swap key of parent
}
else // Children are branches
{z();
final StuckStatic l = nodes.elementAt(L.data).keyNext;
final StuckStatic r = nodes.elementAt(R.data).keyNext;
final int nl = nodes.elementAt(L.data).branchSize();
final int nr = nodes.elementAt(R.data).branchSize();
if (nr >= maxKeysPerBranch) return false; // Steal not possible because there is no where to put the steal
if (nl <= 1) return false; // Steal not allowed because it would leave the left sibling empty
final StuckStatic.LastElement t = l.lastElement1(); // Increase right with left top
r.insertElementAt(p.elementAt1(index).key, t.data, 0); // Increase right with left top
l.pop(); // Remove left top
final StuckStatic.FirstElement b = r.firstElement1(); // Increase right with left top
r.setElementAt(p.elementAt1(index-1).key, b.data, 0); // Reduce key of parent of left
p.setElementAt(l.lastElement1().key, L.data, index-1); // Reduce key of parent of left
}
return true;
}
boolean stealFromRight(int index) // Steal from the right sibling of the indicated child if possible
{z(); assertBranch();
if (index == branchSize()) return false;
if (index < 0) stop("Index", index, "too small");
if (index >= branchSize()) stop("Index", index, "too big");
final StuckStatic.ElementAt L = keyNext.elementAt1(index+0);
final StuckStatic.ElementAt R = keyNext.elementAt2(index+1);
final StuckStatic p = keyNext;
if (hasLeavesForChildren()) // Children are leaves
{z();
final StuckStatic l = nodes.elementAt(L.data).keyData;
final StuckStatic r = nodes.elementAt(R.data).keyData;
final int nl = nodes.elementAt(L.data).leafSize();
final int nr = nodes.elementAt(R.data).leafSize();
if (nl >= maxKeysPerLeaf) return false; // Steal not possible because there is no where to put the steal
if (nr <= 1) return false; // Steal not allowed because it would leave the right sibling empty
final int k = r.firstElement1().key;
l.push (k, r.firstElement1().data); // Increase left
p.setElementAt(k, L.data, index); // Swap key of parent
r.removeElementAt1(0); // Reduce right
}
else // Children are branches
{z();
final StuckStatic l = nodes.elementAt(L.data).keyNext;
final StuckStatic r = nodes.elementAt(R.data).keyNext;
final int nl = nodes.elementAt(L.data).branchSize();
final int nr = nodes.elementAt(R.data).branchSize();
if (nl >= maxKeysPerBranch) return false; // Steal not possible because there is no where to put the steal
if (nr <= 1) return false; // Steal not allowed because it would leave the right sibling empty
l.setElementAt(L.key, l.lastElement1().data, nl); // Left top becomes real
l.push (0, r.firstElement1().data); // New top for left is ignored by search ,.. except last
p.setElementAt(r.firstElement1().key, L.data, index); // Swap key of parent
r.removeElementAt1(0); // Reduce right
}
return true;
}
//D2 Merge // Merge two nodes together and free the resulting free node
boolean mergeRoot() // Merge into the root
{z();
if (root.isLeaf || branchSize() > 1) return false;
if (node != 0) stop("Expected root, got:", node);
final Node p = this;
final Node l = nodes.elementAt(keyNext.firstElement1().data);
final Node r = nodes.elementAt(keyNext. lastElement1().data);
if (p.hasLeavesForChildren()) // Leaves
{z();
if (l.leafSize() + r.leafSize() <= maxKeysPerLeaf)
{z(); p.keyData.clear();
final int nl = l.leafSize();
for (int i = 0; i < nl; ++i)
{z();
final StuckStatic.Shift f = l.keyData.shift1();
p.keyData.push(f.key, f.data);
}
final int nr = r.leafSize();
for (int i = 0; i < nr; ++i)
{z();
final StuckStatic.Shift f = r.keyData.shift1();
p.keyData.push(f.key, f.data);
}
p.keyNext.clear();
isLeaf = true;
return true;
}
}
else if (l.branchSize() + 1 + r.branchSize() <= maxKeysPerBranch) // Branches
{z();
final StuckStatic.FirstElement pkn = p.keyNext.firstElement1();
p.keyNext.clear();
final int nl = l.branchSize();
for (int i = 0; i < nl; ++i)
{z();
final StuckStatic.Shift f = l.keyNext.shift1();
p.keyNext.push(f.key, f.data);
}
p.keyNext.push(pkn.key, l.keyNext.lastElement1().data);
final int nr = r.branchSize();
for (int i = 0; i < nr; ++i)
{z();
final StuckStatic.Shift f = r.keyNext.shift1();
p.keyNext.push(f.key, f.data);
}
p.keyNext.push(0, r.keyNext.lastElement2().data); // Top so ignored by search ... except last
return true;
}
return false;
}
boolean mergeLeftSibling(int index) // Merge the left sibling
{z(); assertBranch();
if (index == 0) return false;
if (index < 0) stop("Index", index, "too small for branch of size:", branchSize());
if (index > branchSize()) stop("Index", index, "too big for branch of size:", branchSize());
//if (branchSize() < 2) stop("Node:", this, "must have two or more children");
if (branchSize() < 2) return false;
final StuckStatic.ElementAt L = keyNext.elementAt1(index-1);
final StuckStatic.ElementAt R = keyNext.elementAt2(index-0);
final StuckStatic p = keyNext;
if (hasLeavesForChildren()) // Children are leaves
{z();
final StuckStatic l = nodes.elementAt(L.data).keyData;
final StuckStatic r = nodes.elementAt(R.data).keyData;
final int nl = nodes.elementAt(L.data).leafSize();
final int nr = nodes.elementAt(R.data).leafSize();
if (nl + nr >= maxKeysPerLeaf) return false; // Combined body would be too big
for (int i = 0; i < maxKeysPerLeaf && l.size() > 0; i++) // Transfer left to right
{z();
final StuckStatic.Pop q = l.pop();
r.insertElementAt(q.key, q.data, 0);
}
}
else // Children are branches
{z();
final StuckStatic l = nodes.elementAt(L.data).keyNext;
final StuckStatic r = nodes.elementAt(R.data).keyNext;
final int nl = nodes.elementAt(L.data).branchSize();
final int nr = nodes.elementAt(R.data).branchSize();
if (nl + 1 + nr > maxKeysPerBranch) return false; // Merge not possible because there is not enough room for the combined result
final int t = p.elementAt1(index-1).key; // Top key
r.insertElementAt(t, l.lastElement1().data, 0); // Left top to right
l.pop(); // Remove left top
for (int i = 0; i < maxKeysPerBranch && l.size() > 0; i++) // Transfer left to right
{z();
final StuckStatic.Pop q = l.pop();
r.insertElementAt(q.key, q.data, 0);
}
}
p.removeElementAt1(index-1); // Reduce parent on left
return true;
}
boolean mergeRightSibling(int index) // Merge the right sibling
{z(); assertBranch();
if (index >= branchSize()) return false;
if (index < 0) stop("Index", index, "too small");
if (index > branchSize()) stop("Index", index, "too big");
//if (branchSize() < 2) stop("Node:", this, "must have two or more children");
if (branchSize() < 2) return false;
final StuckStatic.ElementAt L = keyNext.elementAt1(index+0);
final StuckStatic.ElementAt R = keyNext.elementAt2(index+1);
final StuckStatic p = keyNext;
if (hasLeavesForChildren()) // Children are leaves
{z();
final StuckStatic l = nodes.elementAt(L.data).keyData;
final StuckStatic r = nodes.elementAt(R.data).keyData;
final int nl = nodes.elementAt(L.data).leafSize();
final int nr = nodes.elementAt(R.data).leafSize();
if (nl + nr > maxKeysPerLeaf) return false; // Combined body would be too big
for (int i = 0; i < maxKeysPerLeaf && r.size() > 0; i++) // Transfer right to left
{z();
final StuckStatic.Shift q = r.shift1();
l.push(q.key, q.data);
}
}
else // Children are branches
{z();
final StuckStatic l = nodes.elementAt(L.data).keyNext;
final StuckStatic r = nodes.elementAt(R.data).keyNext;
final int nl = nodes.elementAt(L.data).branchSize();
final int nr = nodes.elementAt(R.data).branchSize();
if (nl + 1 + nr > maxKeysPerBranch) return false; // Merge not possible because there is no where to put the steal
final StuckStatic.LastElement ll = l.lastElement1();
l.setElementAt(p.elementAt1(index).key, ll.data, nl); // Re-key left top
for (int i = 0; i < maxKeysPerBranch && r.size() > 0; i++) // Transfer right to left
{z();
final StuckStatic.Shift f = r.shift1();
l.push(f.key, f.data);
}
}
final StuckStatic.ElementAt pkn = p.elementAt1(index+1); // Key of right sibling
p.setElementAt(pkn.key, p.elementAt2(index).data, index); // Install key of right sibling in this child
p.removeElementAt1(index+1); // Reduce parent on right
return true;
}
//D2 Balance // Balance the tree by merging and stealing
void balance(int index) // Augment the indexed child so it has at least two children in its body
{z(); assertBranch();
if (index < 0) stop("Index", index, "too small");
if (index > branchSize()) stop("Index", index, "too big");
if (isLow() && node != root.node) stop("Parent:", node, "must not be low on children");
final StuckStatic.ElementAt p = nodes.elementAt(node).keyNext.elementAt1(index);
final Node c = nodes.elementAt(p.data);
if (!c.isLow()) return;
if (stealFromLeft (index)) return;
if (stealFromRight (index)) return;
if (mergeLeftSibling (index)) return;
if (mergeRightSibling(index)) return;
stop("Unable to balance child:", c.node);
}
} // Node
class KeyData // A key, data pair
{final int key, data;
KeyData(int Key, int Data) {z(); key = Key; data = Data;}
public String toString()
{return"KeyData(Key:"+key+" data:"+data+")\n";
}
}
class KeyNext // A key, next pair
{final int key, next;
KeyNext(int Key, int Next) {z(); key = Key; next = Next;}
KeyNext( int Next) {z(); key = 0; next = Next;} // The zero can in fact be any number so it is not magic.
public String toString()
{return"KeyNext(Key:"+key+" next:"+next+")\n";
}
}
//D1 Array // Key, data pairs in the tree as an array
Stack<KeyData> toArray() // Key, data pairs in the tree as an array
{z();
final Stack<KeyData> s = new Stack<>();
if (root.isLeaf) {z(); root. leafToArray(s);}
else {z(); root.branchToArray(s);}
return s;
}
//D1 Print // Print a BTree horizontally
String printBoxed() // Print a tree in a box
{final String s = toString();
final int n = longestLine(s)-1;
final String[]L = s.split("\n");
final StringBuilder t = new StringBuilder();
t.append("+"); t.append("-".repeat(n)); t.append("+\n");
for(String l : L) t.append("| "+l+"\n");
t.append("+"); t.append("-".repeat(n)); t.append("+\n");
return t.toString();
}
void padStrings(Stack<StringBuilder> S, int level) // Pad the strings at each level of the tree so we have a vertical face to continue with - a bit like Marc Brunel's tunneling shield
{final int N = level * linesToPrintABranch + maxKeysPerLeaf; // Number of lines we might want
for (int i = S.size(); i <= N; ++i) S.push(new StringBuilder()); // Make sure we have a full deck of strings
int m = 0; // Maximum length
for (StringBuilder s : S) m = m < s.length() ? s.length() : m; // Find maximum length
for (StringBuilder s : S) // Pad each string to maximum length
{if (s.length() < m) s.append(" ".repeat(m - s.length())); // Pad string to maximum length
}
}
String printCollapsed(Stack<StringBuilder> S) // Collapse horizontal representation into a string
{z();
final StringBuilder t = new StringBuilder(); // Print the lines of the tree that are not blank
for (StringBuilder s : S)
{z();
final String l = s.toString();
if (l.isBlank()) continue;
t.append(l+"|\n");
}
return t.toString();
}
String print() // Print a tree horizontally
{z();
final Stack<StringBuilder> S = new Stack<>();
if (root.isLeaf)
{z();
root.printLeaf(S, 0);
}
else
{z();
root.printBranch(S, 0);
}
return printCollapsed(S);
}
//D1 Find // Find the data associated with a key
class Find // Find the data associated with a key in the tree
{Node.FindEqualInLeaf search; // Details of the search of the containing leaf
Find find(int Key) // Find the data associated with a key in the tree
{z();
if (root.isLeaf) // The root is a leaf
{z();
search = root.findEqualInLeaf1(Key);
return this;
}
Node parent = root; // Parent starts at root which is known to be a branch
for (int i = 0; i < maxDepth; i++) // Step down through tree
{z();
final Node.FindFirstGreaterThanOrEqualInBranch down = // Find next child in search path of key
parent.findFirstGreaterThanOrEqualInBranch1(Key);
final int n = down.next;
if (nodes.elementAt(n).isLeaf) // Found the containing search
{z();
final Node l = nodes.elementAt(n);
search = l.findEqualInLeaf1(Key);
return this;
}
parent = nodes.elementAt(n); // Step down to lower branch
}
stop("Search did not terminate in a leaf");
return this;
}
Node leaf() {z(); return search.leaf;}
boolean found() {z(); return search.found;}
int index() {z(); return search.index;}
int data() {z(); return search.data;}
public String toString() // Print find result
{final StringBuilder s = new StringBuilder();
s.append("Find(search:"+search);
s.append( " search:"+index());
if (found())
{s.append( " data:"+data());
s.append(" index:"+index());
}
s.append(")\n");
return s.toString();
}
}
final Find Find1 = new Find();
final Find Find2 = new Find();
Find find1(int Search) {z(); return Find1.find(Search);}
Find find2(int Search) {z(); return Find2.find(Search);}
class FindAndInsert extends Find // Insert the specified key and data into the tree if there is room in the target leaf,or update the key with the data if the key already exists
{int key; // Key to insert
int data; // Data being inserted or updated
boolean success; // Inserted or updated if true
boolean inserted; // Inserted if true
FindAndInsert() {}
FindAndInsert findAndInsert(int Key, int Data) // Find the leaf that should contain this key and insert or update it is possible
{z();
find(Key); // Find the leaf that should contain this key
key = Key; data = Data;
if (found()) // Found the key in the leaf so update it with the new data
{z();
leaf().keyData.setElementAt(Key, Data, index());
success = true; inserted = false;
return this;
}
if (!leaf().isFull()) // Leaf is not full so we can insert immediately
{z();
final Node.FindFirstGreaterThanOrEqualInLeaf f =
leaf().findFirstGreaterThanOrEqualInLeaf1(Key);
if (f.found) // Overwrite existing key
{z();
leaf().keyData.insertElementAt(Key, Data, f.first);
}
else // Insert into position
{z();
leaf().keyData.push(Key, Data);
}
success = true;
return this;
}
success = false;
return this;
}
public String toString() // Print find and insert
{final StringBuilder s = new StringBuilder();
s.append("FindAndInsert(key:"+key);
s.append(" data:"+data);
s.append(" success:"+success);
if (success) s.append(" inserted:"+inserted);
s.append(")\n" );
return s.toString();
}
}
final FindAndInsert FindAndInsert1 = new FindAndInsert();
final FindAndInsert FindAndInsert2 = new FindAndInsert();
final FindAndInsert FindAndInsert3 = new FindAndInsert();
FindAndInsert findAndInsert1(int Key, int Data) {z(); return FindAndInsert1.findAndInsert(Key, Data);}
FindAndInsert findAndInsert2(int Key, int Data) {z(); return FindAndInsert2.findAndInsert(Key, Data);}
FindAndInsert findAndInsert3(int Key, int Data) {z(); return FindAndInsert3.findAndInsert(Key, Data);}
//D1 Insertion // Insert a key, data pair into the tree or update and existing key with a new datum
void put(int Key, int Data) // Insert a key, data pair into the tree or update and existing key with a new datum
{z();
final FindAndInsert f = findAndInsert1(Key, Data); // Try direct insertion with no modifications to the shape of the tree
if (f.success) return; // Inserted or updated successfully
if (root.isFull()) // Start the insertion at the root, after splitting it if necessary
{z();
if (root.isLeaf)
{z();
root.splitLeafRoot();
}
else
{z();
root.splitBranchRoot();
}
final FindAndInsert F = findAndInsert2(Key, Data); // Splitting the root might have been enough
if (F.success) return; // Inserted or updated successfully
}
Node p = root;
for (int i = 0; i < maxDepth; i++) // Step down from branch to branch through the tree until reaching a leaf repacking as we go
{z();
final Node.FindFirstGreaterThanOrEqualInBranch // Step down
down = p.findFirstGreaterThanOrEqualInBranch1(Key);
final Node q = nodes.elementAt(down.next);
if (q.isLeaf) // Reached a leaf
{z();
q.splitLeaf(p, down.first);
findAndInsert3(Key, Data);
merge(Key);
return;
}
if (q.isFull())
{z();
q.splitBranch(p, down.first); // Split the child branch in the search path for the key from the parent so the the search path does not contain a full branch above the containing leaf
final Node.FindFirstGreaterThanOrEqualInBranch // Step down again as the split will have altered the local layout
Down = p.findFirstGreaterThanOrEqualInBranch1(Key);
p = nodes.elementAt(Down.next);
}
else
{z();
p = q;
}
}
stop("Fallen off the end of the tree"); // The tree must be missing a leaf
}
void put(int Key) // Put some test data into the tree
{z();
put(Key, Key);
}
//D1 Deletion // Delete a key, data pair from the tree
Integer findAndDelete(int Key) // Delete a key from the tree and returns its data if present without modifying the shape of tree
{z();
final Find f = find1(Key); // Try direct insertion with no modifications to the shape of the tree
if (!f.found()) return null; // Inserted or updated successfully
final Node l = f.leaf(); // The leaf that contains the key
final int i = f.index(); // Position in the leaf of the key
final StuckStatic.ElementAt kd = l.keyData.elementAt1(i); // Key, data pairs in the leaf
l.keyData.removeElementAt1(i); // Remove the key, data pair from the leaf
return kd.data;
}
Integer delete(int Key) // Insert a key, data pair into the tree or update and existing key with a new datum
{z(); root.mergeRoot();
if (root.isLeaf) // Find and delete directly in root as a leaf
{z(); return findAndDelete(Key);
}
Node p = root; // Start at root
for (int i = 0; i < maxDepth; i++) // Step down from branch to branch through the tree until reaching a leaf repacking as we go
{z();
final Node.FindFirstGreaterThanOrEqualInBranch // Step down
down = p.findFirstGreaterThanOrEqualInBranch1(Key);
p.balance(down.first);
final Node q = nodes.elementAt(down.next);
if (q.isLeaf) // Reached a leaf
{z();
final int data = findAndDelete(Key);
merge(Key);
return data;
}
p = q;
}
stop("Fallen off the end of the tree"); // The tree must be missing a leaf
return null;
}
//D1 Merge // Merge along the specified search path
void merge(int Key) // Merge along the specified search path
{z();
root.mergeRoot();
Node p = root; // Start at root
for (int i = 0; i < maxDepth; i++) // Step down from branch to branch through the tree until reaching a leaf repacking as we go
{z();
if (p.isLeaf) return;
for (int j = 0; j < p.branchSize(); j++) // Try merging each sibling pair
{z();
p.mergeLeftSibling (j);
p.mergeRightSibling(j);
}
final Node.FindFirstGreaterThanOrEqualInBranch // Step down
down = p.findFirstGreaterThanOrEqualInBranch1(Key);
p = nodes.elementAt(down.next);
}
stop("Fallen off the end of the tree"); // The tree must be missing a leaf
}
//D0 Tests // Testing
final static int[]random_small = {27, 442, 545, 317, 511, 578, 391, 993, 858, 586, 472, 906, 658, 704, 882, 246, 261, 501, 354, 903, 854, 279, 526, 686, 987, 403, 401, 989, 650, 576, 436, 560, 806, 554, 422, 298, 425, 912, 503, 611, 135, 447, 344, 338, 39, 804, 976, 186, 234, 106, 667, 494, 690, 480, 288, 151, 773, 769, 260, 809, 438, 237, 516, 29, 376, 72, 946, 103, 961, 55, 358, 232, 229, 90, 155, 657, 681, 43, 907, 564, 377, 615, 612, 157, 922, 272, 490, 679, 830, 839, 437, 826, 577, 937, 884, 13, 96, 273, 1, 188};
final static int[]random_large = {5918,5624,2514,4291,1791,5109,7993,60,1345,2705,5849,1034,2085,4208,4590,7740,9367,6582,4178,5578,1120,378,7120,8646,5112,4903,1482,8005,3801,5439,4534,9524,6111,204,5459,248,4284,8037,5369,7334,3384,5193,2847,1660,5605,7371,3430,1786,1216,4282,2146,1969,7236,2187,136,2726,9480,5,4515,6082,969,5017,7809,9321,3826,9179,5781,3351,4819,4545,8607,4146,6682,1043,2890,2964,7472,9405,4348,8333,2915,9674,7225,4743,995,1321,3885,6061,9958,3901,4710,4185,4776,5070,8892,8506,6988,2317,9342,3764,9859,4724,5195,673,359,9740,2089,9942,3749,9208,1,7446,7023,5496,4206,3272,3527,8593,809,3149,4173,9605,9021,5120,5265,7121,8667,6911,4717,2535,2743,1289,1494,3788,6380,9366,2732,1501,8543,8013,5612,2393,7041,3350,3204,288,7213,1741,1238,9830,6722,4687,6758,8067,4443,5013,5374,6986,282,6762,192,340,5075,6970,7723,5913,1060,1641,1495,5738,1618,157,6891,173,7535,4952,9166,8950,8680,1974,5466,2383,3387,3392,2188,3140,6806,3131,6237,6249,7952,1114,9017,4285,7193,3191,3763,9087,7284,9170,6116,3717,6695,6538,6165,6449,8960,2897,6814,3283,6600,6151,4624,3992,5860,9557,1884,5585,2966,1061,6414,2431,9543,6654,7417,2617,878,8848,8241,3790,3370,8768,1694,9875,9882,8802,7072,3772,2689,5301,7921,7774,1614,494,2338,8638,4161,4523,5709,4305,17,9626,843,9284,3492,7755,5525,4423,9718,2237,7401,2686,8751,1585,5919,9444,3271,1490,7004,5980,3904,370,5930,6304,7737,93,5941,9079,4968,9266,262,2766,4999,2450,9518,5137,8405,483,8840,2231,700,8049,8823,9811,9378,3811,8074,153,1940,1998,4354,7830,7086,6132,9967,5680,448,1976,4101,7839,3122,4379,9296,4881,1246,4334,9457,5401,1945,9548,8290,1184,3464,132,2458,7704,1056,7554,6203,2270,6070,4889,7369,1676,485,3648,357,1912,9661,4246,1576,1836,4521,7667,6907,2098,8825,7404,4019,8284,3710,7202,7050,9870,3348,3624,9224,6601,7897,6288,3713,932,5596,353,2615,3273,833,1446,8624,2489,3872,486,1091,2493,4157,3611,6570,7107,9153,4543,9504,4746,1342,9737,3247,8984,3640,5698,7814,307,8775,1150,4330,3059,5784,2370,5248,4806,6107,9700,231,3566,5627,3957,5317,5415,8119,2588,9440,2961,9786,4769,466,5411,3080,7623,5031,2378,9286,4801,797,1527,2325,847,6341,5310,1926,9481,2115,2165,5255,5465,5561,3606,7673,7443,7243,8447,2348,7925,6447,8311,6729,4441,7763,8107,267,8135,9194,6775,3883,9639,612,5024,1351,7557,9241,5181,2239,8002,5446,747,166,325,9925,3820,9531,5163,3545,558,7103,7658,5670,8323,4821,6263,7982,59,3700,1082,4474,4353,8637,9558,5191,842,5925,6455,4092,9929,9961,290,3523,6290,7787,8266,7986,7269,6408,3620,406,5964,7289,1620,6726,1257,1993,7006,5545,2913,5093,5066,3019,7081,6760,6779,7061,9051,8852,8118,2340,6596,4594,9708,8430,8659,8920,9268,5431,9203,2823,1427,2203,6422,6193,5214,9566,8791,4964,7575,4350,56,2227,8545,5646,3089,2204,4081,487,8496,2258,4336,6955,3452,556,8602,8251,8569,8636,9430,1025,9459,7137,8392,3553,5945,9414,3078,1688,5480,327,8117,2289,2195,8564,9423,103,7724,3091,8548,7298,5279,6042,2855,3286,3542,9361,420,7020,4112,5320,5366,6379,114,9174,9744,592,5346,3985,3174,5157,9890,1605,3082,8099,4346,7256,8670,5687,6613,6620,1458,1045,7917,2980,2399,1433,3315,4084,178,7056,2132,2728,4421,9195,4181,6017,6229,2945,4627,2809,8816,6737,18,8981,3813,8890,5304,3789,6959,7476,1856,4197,6944,9578,5915,3060,9932,3463,67,7393,9857,5822,3187,501,653,8453,3691,9736,6845,1365,9645,4120,2157,8471,4436,6435,2758,7591,9805,7142,7612,4891,7342,5764,8683,8365,2967,6947,441,2116,6612,1399,7585,972,6548,5481,7733,7209,222,5903,6161,9172,9628,7348,1588,5992,6094,7176,4214,8702,2987,74,8486,9788,7164,5788,8535,8422,6826,1800,8965,4965,565,5609,4686,2556,9324,5000,9809,1994,4737,63,8992,4783,2536,4462,8868,6346,5553,3980,2670,1601,4272,8725,4698,7333,7826,9233,4198,1997,1687,4851,62,7893,8149,8015,341,2230,1280,5559,9756,3761,7834,6805,9287,4622,5748,2320,1958,9129,9649,1644,4323,5096,9490,7529,6444,7478,7044,9525,7713,234,7553,9099,9885,7135,6493,9793,6268,8363,2267,9157,9451,1438,9292,1637,3739,695,1090,4731,4549,5171,5975,7347,5192,5243,1084,2216,9860,3318,5594,5790,1107,220,9397,3378,1353,4498,6497,5442,7929,7377,9541,9871,9895,6742,9146,9409,292,6278,50,5288,2217,4923,6790,4730,9240,3006,3547,9347,7863,4275,3287,2673,7485,1915,9837,2931,3918,635,9131,1197,6250,3853,4303,790,5548,9993,3702,2446,3862,9652,4432,973,41,3507,8585,2444,1633,956,5789,1523,8657,4869,8580,8474,7093,7812,2549,7363,9315,6731,1130,7645,7018,7852,362,1636,2905,8006,4040,6643,8052,7021,3665,8383,715,1876,2783,3065,604,4566,8761,7911,1983,3836,5547,8495,8144,1950,2537,8575,640,8730,8303,1454,8165,6647,4762,909,9449,8640,9253,7293,8767,3004,4623,6862,8994,2520,1215,6299,8414,2576,6148,1510,313,3693,9843,8757,5774,8871,8061,8832,5573,5275,9452,1248,228,9749,2730};
static void test_put_ascending()
{final BtreeStuckStatic t = new BtreeStuckStatic(4, 3);
final int N = 64;
for (int i = 1; i <= N; i++) t.put(i);
//t.stop();
t.ok("""
32 |