blib/lib/Zero/NWayTree.pm untested

filter: Statementstmt 0.0% 0 / 1015 Branchbran 0.0% 0 / 70 Conditioncond 0.0% 0 / 9 MC/DCmcdc n/a Subroutinesub 0.0% 0 / 75 Podpod 0.0% 0 / 66 totaltotal 0.0% 0 / 1235 CC 10 SCAR 15.7
CC
10
Cov
0%
FindComparison
30.0
printNode
20.0
Node_SplitIfFull
6.0
CRAP 4.8
1 #!/usr/bin/perl -I/home/phil/perl/cpan/ZeroEmulator/lib/ -Ilib
2 #-------------------------------------------------------------------------------
3 # Zero assembler language implemention of a generic N-Way tree.
4 # Philip R Brenan at appaapps dot com, Appa Apps Ltd Inc., 2023
5 #-------------------------------------------------------------------------------
6 # Key compression in each node by eliminating any common prefix present in each key in each node especially useful if we were to add attributes like userid, process, string position, rwx etc to front of each key. Data does does not need this additional information.
7 use v5.30;
8 package Zero::NWayTree;
9 our $VERSION = 20230511; # Version
10 use warnings FATAL => qw(all);
11 use strict;
12 use Carp qw(cluck confess);
13 use Data::Dump qw(dump);
14 use Data::Table::Text qw(:all);
15 use Zero::Emulator qw(:all);
16 eval "use Test::More tests=>29" unless caller;
17  
18 makeDieConfess;
19  
20 my sub MaxIterations{99}; # The maximum number of levels in a tree
21  
22 my $Tree = sub # The structure of an n-way tree
23 {my $t = Zero::Emulator::AreaStructure("Structure");
24 $t->name(q(keys)); # Number of keys in tree
25 $t->name(q(nodes)); # Number of nodes in tree
26 $t->name(q(NumberOfKeysPerNode)); # The maximum number of keys in a node of this tree
27 $t->name(q(root)); # Root node
28 $t
29 }->();
30  
31 my $Node = sub # The structure of an n-way tree node
32 {my $n = Zero::Emulator::AreaStructure("Node_Structure");
33 $n->name(q(length)); # The current number of keys in the node
34 $n->name(q(id)); # A number identifying this node within this tree
35 $n->name(q(up)); # Parent node unless at the root node
36 $n->name(q(tree)); # The definition of the containing tree
37 $n->name(q(keys)); # Keys associated with this node
38 $n->name(q(data)); # Data associated with each key associated with this node
39 $n->name(q(down)); # Next layer of nodes down from this node
40 $n
41 }->();
42  
43 my $FindResult = sub # The structure of a find result
44 {my $f = Zero::Emulator::AreaStructure("FindResult");
45 $f->name(q(node)); # Node found
46 $f->name(q(cmp)); # Result of the last comparison
47 $f->name(q(key)); # Key searched for
48 $f->name(q(index)); # Index in the node of located element
49 $f
50 }->();
51  
52 my sub FindComparison_lower {0} # Comparison result
53 my sub FindComparison_equal {1}
54 my sub FindComparison_higher {2}
55 my sub FindComparison_notFound{3}
56  
57 #D1 Constructor # Create a new tree.
58  
59 sub New($) # Create a variable referring to a new tree descriptor.
60 {my ($n) = @_; # Maximum number of keys per node in this tree
61  
62 $n > 2 && $n % 2 or confess "Number of key/data elements per node must be > 2 and odd";
63  
64 my $t = Array "Tree"; # Allocate tree descriptor
65 Mov [$t, $Tree->address(q(NumberOfKeysPerNode)), 'Tree'], $n; # Save maximum number of keys per node
66 Mov [$t, $Tree->address(q(root)), 'Tree'], 0; # Clear root
67 Mov [$t, $Tree->address(q(keys)), 'Tree'], 0; # Clear keys
68 Mov [$t, $Tree->address(q(nodes)), 'Tree'], 0; # Clear nodes
69 $t
70 }
71  
72 my sub Tree_getField($$) # Get a field from a tree descriptor
73 {my ($tree, $field) = @_; # Tree, field name
74 Mov [$tree, $Tree->address($field), 'Tree'] # Get attribute from tree descriptor
75 }
76  
77 my sub maximumNumberOfKeys($) # Get the maximum number of keys per node for a tree
78 {my ($tree) = @_; # Tree to examine
79 Tree_getField($tree, q(NumberOfKeysPerNode)); # Get attribute from tree descriptor
80 };
81  
82 my sub root($) # Get the root node of a tree
83 {my ($tree) = @_; # Tree to examine
84 Tree_getField($tree, q(root)); # Get attribute from tree descriptor
85 };
86  
87 my sub setRoot($$) # Set the root node of a tree
88 {my ($tree, $root) = @_; # Tree, root
89 Mov [$tree, $Tree->address(q(root)), 'Tree'], $root; # Set root attribute
90 };
91  
92 sub Keys($) # Get the number of keys in the tree..
93 {my ($tree) = @_; # Tree to examine
94 Tree_getField($tree, q(keys)); # Keys
95 };
96  
97 my sub incKeys($) # Increment the number of keys in a tree
98 {my ($tree) = @_; # Tree
99 Inc [$tree, $Tree->address(q(keys)), 'Tree']; # Number of keys
100 };
101  
102 my sub nodes($) # Get the number of nodes in the tree
103 {my ($tree) = @_; # Tree to examine
104 Tree_getField($tree, q(nodes)); # Nodes
105 };
106  
107 my sub incNodes($) # Increment the number of nodes n a tree
108 {my ($tree) = @_; # Tree
109 Inc [$tree, $Tree->address(q(nodes)), 'Tree']; # Number of nodes
110 };
111  
112 my sub Node_getField($$) # Get a field from a node descriptor
113 {my ($node, $field) = @_; # Node, field name
114 Mov [$node, $Node->address($field), 'Node']; # Get attribute from node descriptor
115 }
116  
117 my sub Node_length($) # Get number of keys in a node
118 {my ($node) = @_; # Node
119 Node_getField($node, q(length)); # Get length
120 }
121  
122 my sub Node_setLength($$) # Set the length of a node
123 {my ($node, $length) = @_; # Node, length
124 Mov [$node, $Node->address(q(length)), 'Node'], $length; # Set length attribute
125 }
126  
127 my sub Node_incLength($) # Increment the length of a node
128 {my ($node) = @_; # Node
129 Inc [$node, $Node->address(q(length)), 'Node']; # Increment length attribute
130 }
131  
132 my sub Node_id($) # Get id of a node
133 {my ($node) = @_; # Node
134 Node_getField($node, q(id)); # Get id
135 }
136  
137 my sub Node_up($) # Get parent node from this node
138 {my ($node) = @_; # Node
139 Node_getField($node, q(up)); # Get up
140 }
141  
142 my sub Node_setUp($$) # Set the parent of a node
143 {my ($node, $parent) = @_; # Node, parent node, area containing parent node reference
144 Mov [$node, $Node->address(q(up)), 'Node'], $parent; # Set parent
145 }
146  
147 my sub Node_tree($) # Get tree containing a node
148 {my ($node) = @_; # Node
149 Node_getField($node, q(tree)); # Get tree
150 }
151  
152 my sub Node_getIndex($$$) # Get the indexed field from a node
153 {my ($node, $index, $field) = @_; # Node, index of field, field name
154 my $F = Mov [$node, $Node->address($field), 'Node']; # Fields
155 Mov [$F, \$index, ucfirst $field]; # Field
156 }
157  
158 my sub Node_setIndex($$$$) # Set an indexed field to a specified value
159 {my ($node, $index, $field, $value) = @_; # Node, index, field name, value
160 my $F = Mov [$node, $Node->address($field), 'Node']; # Fields
161 Mov [$F, \$index, ucfirst $field], $value; # Set field to value
162 }
163  
164 my sub Node_keys($$) # Get the indexed key from a node
165 {my ($node, $index) = @_; # Node, index of key
166 Node_getIndex($node, $index, q(keys)); # Keys
167 }
168  
169 my sub Node_data($$) # Get the indexed data from a node
170 {my ($node, $index) = @_; # Node, index of data
171 Node_getIndex($node, $index, q(data)); # Data
172 }
173  
174 my sub Node_down($$) # Get the indexed child node from a node
175 {my ($node, $index) = @_; # Node, index of child
176 Node_getIndex($node, $index, q(down)); # Child
177 }
178  
179 my sub Node_isLeaf($) # Put 1 in a temporary variable if a node is a leaf else 0
180 {my ($node) = @_; # Node
181 Not [$node, $Node->address('down'), 'Node']; # Whether the down field is present or not . 0 is never a user allocated memory area
182 }
183  
184 my sub Node_setKeys($$$) # Set a key by index
185 {my ($node, $index, $value) = @_; # Node, index, value
186 Node_setIndex($node, $index, q(keys), $value) # Set indexed key
187 }
188  
189 my sub Node_setData($$$) # Set a data field by index
190 {my ($node, $index, $value) = @_; # Node, index, value
191 Node_setIndex($node, $index, q(data), $value) # Set indexed key
192 }
193  
194 my sub Node_setDown($$$) # Set a child by index
195 {my ($node, $index, $value) = @_; # Node, index, value
196 Node_setIndex($node, $index, q(down), $value) # Set indexed key
197 }
198  
199 my sub Node_new($%) # Create a variable referring to a new node descriptor
200 {my ($tree, %options) = @_; # Tree node is being created in, options
201 my $n = Array "Node"; # Allocate node
202 my $k = Array "Keys"; # Allocate keys
203 my $d = Array "Data"; # Allocate data
204  
205 Node_setLength $n, $options{length} // 0; # Length
206  
207 Node_setUp $n, 0; # Parent
208  
209 Mov [$n, $Node->address(q(keys)), 'Node'], $k; # Keys area
210 Mov [$n, $Node->address(q(data)), 'Node'], $d; # Data area
211 Mov [$n, $Node->address(q(down)), 'Node'], 0; # Down area
212 Mov [$n, $Node->address(q(tree)), 'Node'], $tree; # Containing tree
213 incNodes($tree);
214 Mov [$n, $Node->address(q(id)), 'Node'], # Assign an id to this node within the tree
215 [$tree, $Tree->address(q(nodes)), 'Tree'];
216 my $N = maximumNumberOfKeys($tree); # Get the maximum number of keys per node for a tree
217 $n # Return reference to new node
218 }
219  
220 my sub Node_allocDown($%) # Upgrade a leaf node to an internal node
221 {my ($node, %options) = @_; # Node to upgrade, options
222 my $d = Array "Down"; # Allocate down
223 Mov [$node, $Node->address(q(down)), 'Node'], $d; # Down area
224 }
225  
226 my sub FindResult_getField($$) # Get a field from a find result
227 {my ($findResult, $field) = @_; # Find result, name of field
228 Mov [$findResult, $FindResult->address($field), q(FindResult)]; # Fields
229 }
230  
231 sub FindResult_key($) # Get key from find result..
232 {my ($f) = @_; # Find result
233 FindResult_getField($f, q(key)) # Key
234 }
235  
236 sub FindResult_cmp($) # Get comparison from find result..
237 {my ($f) = @_; # Find result
238 FindResult_getField($f, q(cmp)) # Comparison
239 }
240  
241 my sub FindResult_index($) # Get index from find result
242 {my ($f) = @_; # Find result
243 FindResult_getField($f, q(index)) # Index
244 }
245  
246 my sub FindResult_node($) # Get node from find result
247 {my ($f) = @_; # Find result
248 FindResult_getField($f, q(node)) # Node
249 }
250  
251 sub FindResult_data($) # Get data field from find results..
252 {my ($f) = @_; # Find result
253  
254 my $n = FindResult_node ($f);
255 my $i = FindResult_index($f);
256 my $d = Node_data($n, $i);
257 $d
258 }
259  
260 my sub FindComparison($$) # Convert a symbolic name for a find result comparison to an integer
261 {my ($f, $cmp) = @_; # Find result, comparison result name
262 return 0 if $cmp eq q(lower);
263 return 1 if $cmp eq q(equal);
264 return 2 if $cmp eq q(higher);
265 return 3 if $cmp eq q(notFound);
266 }
267  
268 my sub Node_open($$$$$) # Open a gap in an interior node
269 {my ($node, $offset, $length, $K, $D) = @_; # Node
270  
271 my $k = Mov [$node, \$Node->offset(qw(keys)), 'Node'];
272 my $d = Mov [$node, \$Node->offset(qw(data)), 'Node'];
273 my $n = Mov [$node, \$Node->offset(qw(down)), 'Node'];
274  
275 ShiftUp [$k, \$offset, 'Keys'], $K;
276 ShiftUp [$d, \$offset, 'Data'], $D;
277 my $o1 = Add $offset, 1;
278 ShiftUp [$n, \$o1, 'Down'], 0;
279 Node_incLength $node;
280 }
281  
282 my sub Node_openLeaf($$$$$) # Open a gap in a leaf node
283 {my ($node, $offset, $length, $K, $D) = @_; # Node
284  
285 my $k = Mov [$node, \$Node->offset(qw(keys)), 'Node'];
286 my $d = Mov [$node, \$Node->offset(qw(data)), 'Node'];
287  
288 ShiftUp [$k, \$offset, 'Keys'], $K;
289 ShiftUp [$d, \$offset, 'Data'], $D;
290 Node_incLength $node;
291 }
292  
293 my sub Node_copy($$$$$) # Copy part of one interior node into another node.
294 {my ($t, $s, $to, $so, $length) = @_; # Target node, source node, target offset, source offset, length
295  
296 For # Each key, data, down
297 {my ($i, $check, $next, $end) = @_;
298 my $S = Add $so, $i;
299 my $T = Add $to, $i;
300  
301 my $k = Node_keys ($s, $S);
302 my $d = Node_data ($s, $S);
303 my $n = Node_down ($s, $S);
304 Node_setKeys($t, $T, $k);
305 Node_setData($t, $T, $d);
306 Node_setDown($t, $T, $n);
307 } $length;
308  
309 my $S = Add $so, $length;
310 my $T = Add $to, $length;
311  
312 my $n = Node_down($s, $S);
313 Node_setDown($t, $T, $n);
314 }
315  
316 my sub Node_copy_leaf($$$$$) # Copy part of one leaf node into another node.
317 {my ($t, $s, $to, $so, $length) = @_; # Target node, source node, target offset, source offset, length
318  
319 For # Each key, data, down
320 {my ($i, $check, $next, $end) = @_;
321 my $S = Add $so, $i;
322 my $T = Add $to, $i;
323  
324 my $k = Node_keys ($s, $S);
325 my $d = Node_data ($s, $S);
326 Node_setKeys($t, $T, $k);
327 Node_setData($t, $T, $d);
328 } $length;
329 }
330  
331 my sub Node_free($) # Free a node
332 {my ($node) = @_; # Node to free
333 IfFalse Node_isLeaf($node),
334 Then
335 {my $K = Mov [$node, $Node->address(q(keys)), 'Node'];
336 my $D = Mov [$node, $Node->address(q(data)), 'Node'];
337 my $N = Mov [$node, $Node->address(q(down)), 'Node'];
338 Free $K, "Keys";
339 Free $D, "Data";
340 Free $N, "Down";
341 };
342 Free $node, "Node";
343 }
344  
345 my sub FindResult_new($$$$) # New find result on stack
346 {my ($node, $key, $cmp, $index) = @_; # Node,search key, comparison result, index
347 my $f = Array "FindResult"; # Find result
348  
349 Mov [$f, $FindResult->address(q(node)) , 'FindResult'], $node;
350 Mov [$f, $FindResult->address(q(key)) , 'FindResult'], $key;
351 Mov [$f, $FindResult->address(q(cmp)) , 'FindResult'], $cmp;
352 Mov [$f, $FindResult->address(q(index)), 'FindResult'], $index;
353 $f
354 }
355  
356 my sub ReUp($) # Reconnect the children to their new parent.
357 {my ($node) = @_; # Parameters
358 my $l = Node_length($node);
359 my $L = Add $l, 1;
360  
361 For
362 {my ($i, $check, $next, $end) = @_; # Parameters
363 my $d = Node_down ($node, $i);
364 Node_setUp($d, $node);
365 } $L;
366 }
367  
368 my sub Node_indexInParent # Get the index of a node in its parent.
369 {my ($node) = @_; # Node
370 my $p = Node_up($node);
371 AssertNe($p, 0); # Number of children as opposed to the number of keys
372 my $l = Node_length($p);
373 AssertNe($l, 0); # Number of children as opposed to the number of keys
374 my $L = Add $l, 1;
375 my $r = Var; # Index of child
376  
377 Block
378 {my ($Start, $Good, $Bad, $End) = @_;
379 For # Loop through each child looking for the one specified
380 {my ($i, $check, $next, $end) = @_;
381 IfEq Node_down($p, $i), $node,
382 Then
383 {Mov $r, $i;
384 Jmp $End;
385 };
386 } $L;
387 Assert; # Something has gone seriously wrong if we cannot find the node within its parent
388 };
389 $r
390 }
391  
392 my sub Node_SplitIfFull($) # Split a node if it is full. Return true if the node was split else false
393 {my ($node) = @_; # Node to split
394 my $nl = Node_length($node);
395 my $t = Node_tree($node); # Associated tree
396 my $m = maximumNumberOfKeys($t);
397 my $split = Var;
398  
399 Block # Various splitting scenarios
400 {my ($start, $good, $bad, $end) = @_;
401 Jlt $bad, $nl, $m; # Must be a full node
402  
403 my $N = maximumNumberOfKeys($t); # Split points
404 my $n = Mov $N; # Copy
405 ShiftRight $n, 1; # Index of key that will be placed in parent
406  
407 my $L = Add $n, 1;
408 my $R = Subtract $N, $L;
409  
410 my $l = Node_new($t, length=>$n); # New child nodes
411 my $r = Node_new($t, length=>$R);
412  
413 IfFalse Node_isLeaf($node), # Not a leaf
414 Then
415 {Node_allocDown $l; # Add down area on left
416 Node_allocDown $r; # Add down area on right
417 Node_copy($l, $node, 0, 0, $n); # New left node
418 Node_copy($r, $node, 0, $L, $R); # New right node
419 ReUp($l);
420 ReUp($r);
421 },
422 Else
423 {Node_allocDown $node; # Add down area
424 Node_copy_leaf($l, $node, 0, 0, $n); # New left leaf
425 Node_copy_leaf($r, $node, 0, $L, $R); # New right leaf
426 };
427  
428 my $p = Node_up($node); # Existing parent node
429 IfTrue $p,
430 Then # Not a root node
431 {my $pl = Node_length($p);
432 Node_setUp($l, $p); # Connect children to parent
433 Node_setUp($r, $p);
434  
435 IfEq Node_down($p, 0), $node,
436 Then # Splitting the first child - move everything up
437 {my $nk = Node_keys($node, $n);
438 my $nd = Node_data($node, $n);
439 Node_open ($p, 0, $pl, $nk, $nd);
440 Node_setDown($p, 0, $l);
441 Node_setDown($p, 1, $r);
442 Node_free($node);
443 Jmp $good;
444 };
445  
446 IfEq Node_down($p, $pl), $node, # Splitting the last child - just add it on the end
447 Then
448 {my $pk = Node_keys($node, $n);
449 my $pd = Node_data($node, $n);
450 Node_setKeys ($p, $pl, $pk);
451 Node_setDown ($p, $pl, $l);
452 my $nd = Node_data($node, $n);
453 Node_setData ($p, $pl, $nd);
454 my $pl1 = Add $pl, 1;
455 Node_setLength($p, $pl1);
456 Node_setDown ($p, $pl1, $r);
457 Node_free ($node);
458 Jmp $good;
459 };
460  
461 For # Splitting a middle child:
462 {my ($i) = @_; # Child index
463 IfEq Node_down($p, $i), $node, # Find the node that points from the parent to the current node
464 Then
465 {my $pli = Subtract $pl, $i;
466 my $pk = Node_keys($node, $n);
467 my $pd = Node_data($node, $n);
468 Node_open ($p, $i, $pli, $pk, $pd);
469 Node_setDown ($p, $i, $l);
470 my $i1 = Add $i, 1;
471 Node_setDown ($p, $i1, $r);
472 Node_free ($node);
473 Jmp $good;
474 };
475 } [1, $pl];
476 Assert; # Could not find the child in the parent
477 };
478  
479 Node_setUp($l, $node); # Root node with single key after split
480 Node_setUp($r, $node); # Connect children to parent
481  
482 my $pk = Node_keys($node, $n); # Single key
483 my $pd = Node_data($node, $n); # Data associated with single key
484 Node_setKeys ($node, 0, $pk);
485 Node_setData ($node, 0, $pd);
486 Node_setDown ($node, 0, $l);
487 Node_setDown ($node, 1, $r);
488 Node_setLength($node, 1);
489  
490 if (1) # Resize split node
491 {my $K = Mov [$node, $Node->address(q(keys)), 'Node'];
492 my $D = Mov [$node, $Node->address(q(data)), 'Node'];
493 my $N = Mov [$node, $Node->address(q(down)), 'Node'];
494 Resize $K, 1;
495 Resize $D, 1;
496 Resize $N, 2;
497 }
498  
499 Jmp $good;
500 }
501 Good # Node was split
502 {Mov $split, 1;
503 },
504 Bad # Node was to small to split
505 {Mov $split, 0;
506 };
507 $split
508 }
509  
510 #D1 Find # Find a key in a tree.
511  
512 my sub FindAndSplit($$) # Find a key in a tree splitting full nodes along the path to the key.
513 {my ($tree, $key) = @_; # Parameters (NWayTree(Tree) * const tree, # Tree to search
514 my $node = root($tree);
515  
516 Node_SplitIfFull($node); # Split the root node if necessary
517 my $F = Var;
518  
519 Block # Exit this block when we have located the key
520 {my ($Start, $Good, $Bad, $Found) = @_;
521  
522 For # Step down through the tree
523 {my ($j, $check, $next, $end) = @_; # Parameters
524 my $nl = Node_length($node); # Length of node
525 my $last = Subtract $nl, 1; # Greater than largest key in node. Data often gets inserted in ascending order so we do this check first rather than last.
526 IfGt $key, Node_keys($node, $last), # Key greater than greatest key
527 Then
528 {IfTrue Node_isLeaf($node), # Leaf
529 Then
530 {Mov $F, FindResult_new($node, $key, FindComparison_higher, $last);
531 Jmp $Found;
532 };
533 my $last1 = Add $last, 1;
534 my $n = Node_down($node, $last1); # We will be heading down through the last node so split it in advance if necessary
535 IfFalse Node_SplitIfFull($n), # No split needed
536 Then
537 {Mov $node, $n;
538 };
539 Jmp $next;
540 };
541  
542 For # Search the keys in this node as greater than least key and less than largest key
543 {my ($i, $check, $next, $end) = @_; # Parameters
544 my $k = Node_keys($node, $i); # Current key
545  
546 IfLt $key, $k, # Greater than current key
547 Then
548 {IfTrue Node_isLeaf($node),
549 Then
550 {Mov $F, FindResult_new($node, $key, FindComparison_lower, $i);
551 Jmp $Found;
552 };
553  
554 my $n = Node_down($node, $i);
555 IfFalse Node_SplitIfFull($n), # Split the node we have stepped to if necessary - if we do we will have to restart the descent from one level up because the key might have moved to the other node.
556 Then
557 {Mov $node, $n;
558 };
559 Jmp $end;
560 };
561  
562 IfEq $key, $k, # Found key
563 Then
564 {Mov $F, FindResult_new($node, $key, FindComparison_equal, $i);
565 Jmp $Found;
566 };
567 } $nl;
568 } MaxIterations;
569 Assert; # Failed to descend through the tree to the key.
570 };
571 $F # Results of find
572 }
573  
574 sub Find($$) # Find a key in a tree returning its associated data or undef if the key does not exist..
575 {my ($tree, $key) = @_; # Tree to search, key to find
576  
577 my $p = Procedure 'NWayTree_Find', sub
578 {my ($p) = @_; # Procedure description
579 my $tree = ParamsGet 0;
580 my $key = ParamsGet 1;
581  
582 my $node = root($tree); # Current node we are searching
583  
584 IfFalse $node, # Empty tree
585 Then
586 {ReturnPut 0, FindResult_new($node, $key, FindComparison_notFound, -1);
587 Return;
588 };
589  
590 For # Step down through tree
591 {my ($j, $check, $next, $end) = @_; # Parameters
592 my $nl = Node_length($node);
593 my $nl1 = Subtract $nl, 1;
594  
595 IfGt $key, Node_keys($node, $nl1), # Bigger than every key
596 Then
597 {IfTrue Node_isLeaf($node), # Leaf
598 Then
599 {ReturnPut 0, FindResult_new($node, $key, FindComparison_higher, $nl);
600 Return;
601 };
602 Mov $node, Node_down($node, $nl);
603 Jmp $next;
604 };
605  
606 For # Search the keys in this node as less than largest key
607 {my ($i, $check, $next, $end) = @_; # Parameters
608 my $k = Node_keys($node, $i); # Key from tree
609 IfEq $key, $k, # Found key
610 Then
611 {ReturnPut 0, FindResult_new($node, $key, FindComparison_equal, $i);
612 Return;
613 };
614 IfLt $key, $k, # Lower than current key
615 Then
616 {IfTrue Node_isLeaf($node), # Leaf
617 Then
618 {ReturnPut 0, FindResult_new($node, $key, FindComparison_lower, $i);
619 Return;
620 };
621 Mov $node, Node_down($node, $i);
622 Jmp $end;
623 };
624 } $nl;
625 } MaxIterations;
626 Assert;
627 };
628  
629 ParamsPut 0, $tree; # Set parameters and call insert procedure
630 ParamsPut 1, $key;
631 Call $p;
632 ReturnGet 0;
633 }
634  
635 #D1 Insert # Create a new entry ina tree connecting a key to data.
636  
637 sub Insert($$$%) # Insert a key and its associated data into a tree.
638 {my ($tree, $key, $data, %options) = @_; # Tree, key, data
639  
640 my $p = Procedure 'NWayTree_Insert', sub
641 {my ($p) = @_; # Procedure description
642  
643 Block
644 {my ($Start, $Good, $Bad, $Finish) = @_; # Parameters
645  
646 my $tree = ParamsGet 0;
647 my $key = ParamsGet 1;
648 my $data = ParamsGet 2;
649 my $n = root($tree); # Root node of tree
650  
651 IfFalse $n, # Empty tree
652 Then
653 {my $n = Node_new($tree, length=>1);
654 Node_setKeys ($n, 0, $key);
655 Node_setData ($n, 0, $data);
656 incKeys($tree);
657 setRoot($tree, $n);
658 Jmp $Finish;
659 };
660  
661 my $nl = Node_length($n); # Current length of node
662 IfLt $nl, maximumNumberOfKeys($tree), # Node has room for another key
663 Then
664 {IfFalse Node_up($n), # Root node
665 Then
666 {IfTrue Node_isLeaf($n),
667 Then
668 {For # Each key
669 {my ($i, $check, $next, $end) = @_; # Parameters
670 my $k = Node_keys($n, $i); # Key to check
671 IfEq $key, $k, # Key already present
672 Then
673 {Node_setData($n, $i, $data);
674 Jmp $Finish;
675 };
676 IfLt $key, $k, # We have reached the insertion point
677 Then
678 {my $nli = Subtract $nl, $i;
679 Node_openLeaf($n, $i, $nli, $key, $data);
680 incKeys($tree);
681 Jmp $Finish;
682 };
683 } $nl;
684 Node_setKeys($n, $nl, $key); # Insert the key at the end of the block because it is greater than all the other keys in the block
685 Node_setData($n, $nl, $data);
686 my $nl1 = Add $nl, 1;
687 Node_setLength($n, $nl1);
688 incKeys($tree);
689 Jmp $Finish;
690 };
691 };
692 };
693 # Insert node
694 my $r = FindAndSplit($tree, $key); # Check for existing key
695 my $N = FindResult_node($r);
696 my $c = FindResult_cmp($r);
697 my $i = FindResult_index($r);
698 Free $r, "FindResult";
699  
700 IfEq $c, FindComparison_equal, # Found an equal key whose data we can update
701 Then
702 {Node_setData($N, $i, $data);
703 Jmp $Finish;
704 };
705  
706 my $Nl = Node_length($N);
707 my $Nl1 = Add $Nl, 1;
708 IfEq $c, FindComparison_higher, # Found a key that is greater than the one being inserted
709 Then
710 {my $i1 = Add $i, 1;
711 my $l = Subtract $Nl, $i1;
712 Node_openLeaf($N, $i1, $l, $key, $data);
713 },
714 Else
715 {my $l = Subtract $Nl, $i;
716 Node_openLeaf($N, $i, $l, $key, $data);
717 };
718  
719 incKeys($tree);
720 Node_SplitIfFull($N); # Split if the leaf is full to force keys up the tree
721 };
722 Return;
723 };
724  
725 ParamsPut 0, $tree; # Set parameters and call insert procedure. As the tree parameter does not change very often the user has the option of setting it themselves out side of a loop.
726 ParamsPut 1, $key;
727 ParamsPut 2, $data;
728 Call $p;
729 }
730  
731 #D1 Iteration # Iterate over the keys and their associated data held in a tree.
732  
733 my sub GoAllTheWayLeft($) # Go as left as possible from the current node
734 {my ($node) = @_; # Node
735 my $f = Var;
736  
737 IfFalse $node, # Empty tree
738 Then
739 {Mov $f, FindResult_new($node, 0, FindComparison_notFound, 0);
740 },
741 Else
742 {For # Step down through tree
743 {my ($i, $check, $next, $end) = @_; # Parameters
744 IfTrue Node_isLeaf($node), # Reached leaf
745 Then
746 {Jmp $end;
747 };
748 Mov $node, Node_down($node, 0);
749 } MaxIterations;
750 Mov $f, FindResult_new($node, Node_keys($node, 0), FindComparison_equal, 0);# Leaf - place us on the first key
751 };
752 $f
753 }
754  
755 my sub GoUpAndAround($) # Go up until it is possible to go right or we can go no further
756 {my ($find) = @_; # Find
757 my $f = Var;
758 Block
759 {my ($Start, $Good, $Bad, $Finish) = @_; # Parameters
760 my $node = FindResult_node($find);
761  
762 IfTrue Node_isLeaf($node), # Leaf
763 Then
764 {my $I = FindResult_index($find);
765 my $L = Node_length($node);
766 my $L1 = Subtract $L, 1;
767 IfLt $I, $L1, # More keys in leaf
768 Then
769 {my $i = Add $I, 1;
770 Mov $f, FindResult_new($node, Node_keys($node, $i),
771 FindComparison_equal, $i);
772 Jmp $Finish;
773 };
774  
775 my $parent = Node_up($node); # Parent
776 IfTrue $parent,
777 Then
778 {For # Not the only node in the tree
779 {my ($j, $check, $next, $end) = @_; # Parameters
780 my $i = Node_indexInParent($node); # Index in parent
781  
782 IfEq $i, Node_length($parent), # Last key - continue up
783 Then
784 {Mov $node, $parent;
785 my $Parent = Node_up($parent); # Parent
786 Mov $parent, $Parent;
787 IfFalse $parent,
788 Then
789 {Jmp $end;
790 };
791 },
792 Else
793 {Mov $f, FindResult_new($parent, Node_keys($parent, $i), # Not the last key
794 FindComparison_equal, $i);
795 Jmp $Finish;
796 };
797 } MaxIterations;
798 };
799 Mov $f, FindResult_new($node, 0, FindComparison_notFound, 0); # Last key of root
800 Jmp $Finish;
801 };
802  
803 my $i = FindResult_index($find); # Not a leaf so on an interior key so we can go right then all the way left
804 my $I = Add $i, 1;
805 my $d = Node_down($node, $I);
806 Mov $f, GoAllTheWayLeft($d);
807 };
808 $f
809 }
810  
811 my sub IterStart($) # Start an iterator
812 {my ($tree) = @_; # Tree to iterate
813 my $n = root($tree);
814 GoAllTheWayLeft($n);
815 }
816  
817 my sub IterCheck($) # True if we can continue to iterate
818 {my ($F) = @_; # Parameters (NWayTree(FindResult) const find) # Find result of last iteration
819 my $r = Var;
820 IfEq FindResult_cmp($F), FindComparison_notFound,
821 Then
822 {Mov $r, 0;
823 },
824 Else
825 {Mov $r, 1;
826 };
827 $r
828 }
829  
830 my sub IterNext($) # Next element of an iteration
831 {my ($F) = @_; # Parameters (NWayTree(FindResult) const find) # Find result of last iteration
832 GoUpAndAround($F);
833 }
834  
835 sub Iterate(&$) # Iterate over a tree.
836 {my ($block, $tree) = @_; # Block of code to execute for each key in tree, tree
837 my $f = IterStart($tree);
838  
839 For
840 {my ($i, $check, $next, $end) = @_; # Parameters
841  
842 IfFalse IterCheck($f),
843 Then
844 {Jmp $end;
845 };
846  
847 &$block($f);
848  
849 my $F = Mov $f;
850 Mov $f, IterNext($f);
851 Free $F, "FindResult";
852 } 1e99;
853 }
854  
855 #D1 Print # Print trees horizontally.
856  
857 my sub printNode($$$$$) # Print the keys or data in a node in memory
858 {my ($memory, $node, $indent, $out, $keyNotData) = @_;
859 ref($node) =~ m(Node) or confess "Not a node: ".dump($node);
860 my $k = $$node[$Node->offset(q(keys))];
861 my $d = $$node[$Node->offset(q(data))];
862 my $n = $$node[$Node->offset(q(down))];
863  
864 if ($n) # Interior node
865 {my $K = $$memory{$k};
866 my $D = $$memory{$d};
867 my $N = $$memory{$n};
868 my $l = $$node[$Node->offset(q(length))];
869  
870 for my $i(0..$l-1)
871 {my $c = $$memory{$$N[$i]}; # Child node
872 my $p = $$memory{$$c[$Node->offset(q(up))]};
873  
874 __SUB__->($memory, $c, $indent+1, $out, $keyNotData);
875 push @$out, [$indent, $keyNotData ? $$K[$i] : $$D[$i]];
876 }
877  
878 __SUB__->($memory, $$memory{$$N[$l]}, $indent+1, $out, $keyNotData);
879 }
880  
881 else # Leaf node
882 {my $K = $$memory{$k};
883 my $D = $$memory{$d};
884 my $l = $$node[$Node->offset(q(length))];
885  
886 for my $i(0..$l-1)
887 {my $k = $$K[$i];
888 my $d = $$D[$i];
889 push @$out, [$indent, $keyNotData ? $k : $d];
890 }
891 }
892 $out
893 }
894  
895 my sub printTree($$) # Print a tree
896 {my ($m, $keyNotData) = @_; # Memory, key or data
897 my $t = $$m{1};
898 my $r = $$m{$$t[$Tree->offset(q(root))]};
899 my $o = printNode($m, $r, 0, [], $keyNotData);
900  
901 my $C = $#$o; # Number of columns
902 my $R = max(map {$$o[$_][0]} keys @$o); # Number of rows
903  
904 my $W = 3; # Field width for each key
905 my @o; # Output area
906 for my $r(0..$R)
907 {for my $c(0..$C)
908 {$o[$r][$c] = ' ' x $W;
909 }
910 }
911  
912 for my $p(keys @$o) # Write tree horizontally
913 {next unless defined(my $v = $$o[$p][1]);
914 my $r = $$o[$p][0];
915 my $c = $p;
916  
917 $o[$r][$c] = sprintf("%${W}d", $v);
918 }
919  
920 join "\n", (map { (join "", $o[$_]->@*) =~ s(\s+\Z) ()r;} keys @o), ''; # As a single string after removing trailing spaces on each line
921 }
922  
923 sub printTreeKeys($) # Print the keys held in a tree.
924 {my ($m) = @_; # Memory
925 printTree($m, 1);
926 }
927  
928 sub printTreeData($) # Print the data held in a tree.
929 {my ($m) = @_; # Memory
930 printTree($m, 0);
931 }
932  
933 #D1 Utilities # Utility functions.
934  
935 sub randomArray($) # Create a random array.
936 {my ($N) = @_; # Size of array
937  
938 my @r = 1..$N;
939 srand(1);
940  
941 for my $i(keys @r) # Disarrange the array
942 {my $s = int rand @r;
943 my $t = int rand @r;
944 ($r[$t], $r[$s]) = ($r[$s], $r[$t]);
945 }
946 @r
947 }
948  
949 use Exporter qw(import);
950 use vars qw(@ISA @EXPORT @EXPORT_OK %EXPORT_TAGS);
951  
952 @ISA = qw(Exporter);
953 @EXPORT = qw();
954 @EXPORT_OK = qw(Find FindResult_cmp FindResult_data FindResult_key Insert Iterate New printTreeKeys printTreeData randomArray);
955 #say STDERR '@EXPORT_OK = qw(', (join ' ', sort @EXPORT_OK), ');'; exit;
956 %EXPORT_TAGS = (all=>[@EXPORT, @EXPORT_OK]);
957  
958 return 1 if caller;
959  
960 #D0 Tests
961  
962 Test::More->builder->output("/dev/null"); # Reduce number of confirmation messages during testing
963  
964 eval {goto latest};
965  
966 sub is_deeply;
967 sub ok($;$);
968 sub done_testing;
969  
970 #latest:;
971 if (1)
972 {Start 1;
973 Out New(3);
974 my $e = Execute(suppressOutput=>1);
975 is_deeply $e->out, [1];
976 is_deeply $e->memory, { 1 => bless([0, 0, 3, 0], "Tree") };
977 }
978  
979 #latest:;
980 if (1)
981 {Start 1;
982 my $t = New(3);
983 my $r = root($t);
984  
985 setRoot($t, 1);
986 my $R = root($t);
987  
988 my $n = maximumNumberOfKeys($t);
989  
990 incKeys($t) for 1..3;
991 Out [$t, $Tree->address(q(keys)), 'Tree'];
992  
993 incNodes($t) for 1..5;
994 Out nodes($t);
995  
996 my $e = Execute(suppressOutput=>1);
997 is_deeply $e->out, [3, 5];
998 is_deeply $e->memory, { 1 => bless([3, 5, 3, 1], "Tree") };
999 }
1000  
1001 #latest:;
1002 if (1) #TNode_open
1003 {Start 1;
1004 my $t = New(7); # Create tree
1005 my $n = Node_new($t); # Create node
1006 my $e = Execute(suppressOutput=>1);
1007 is_deeply $e->memory, {
1008 1 => bless([0, 1, 7, 0], "Tree"),
1009 2 => bless([0, 1, 0, 1, 3, 4, 0], "Node"),
1010 3 => bless([], "Keys"),
1011 4 => bless([], "Data")};
1012 }
1013  
1014 #latest:;
1015 if (1) #TNode_open
1016 {Start 1;
1017 my $N = 7;
1018 my $t = New($N); # Create tree
1019 my $n = Node_new($t); # Create node
1020  
1021 Node_allocDown $n;
1022  
1023 for my $i(0..$N-1)
1024 {Node_setKeys($n, $i, 1+$i);
1025 Node_setData($n, $i, 11+$i);
1026 Node_setDown($n, $i, 21+$i);
1027 }
1028  
1029 Node_setDown($n, $N, 28);
1030  
1031 Node_open($n, 2, 4, 3, 13);
1032 my $e = Execute(suppressOutput=>1);
1033  
1034 is_deeply $e->memory, {
1035 1 => bless([0, 1, 7, 0], "Tree"),
1036 2 => bless([1, 1, 0, 1, 3, 4, 5], "Node"),
1037 3 => bless([1, 2, 3, 3 .. 7], "Keys"),
1038 4 => bless([11, 12, 13, 13 .. 17], "Data"),
1039 5 => bless([21, 22, 23, 0, 24 .. 28], "Down")};
1040 }
1041  
1042 #latest:;
1043 if (1) #TNode_copy
1044 {Start 1;
1045 my $t = New(7); # Create tree
1046 my $p = Node_new($t); Node_allocDown($p); # Create a node
1047 my $q = Node_new($t); Node_allocDown($q); # Create a node
1048  
1049 for my $i(0..6)
1050 {Node_setKeys($p, $i, 11+$i);
1051 Node_setData($p, $i, 21+$i);
1052 Node_setDown($p, $i, 31+$i);
1053 Node_setKeys($q, $i, 41+$i);
1054 Node_setData($q, $i, 51+$i);
1055 Node_setDown($q, $i, 61+$i);
1056 }
1057  
1058 Node_setDown($p, 7, 97);
1059 Node_setDown($q, 7, 99);
1060  
1061 Node_copy( $q, $p, 1, 3, 2);
1062  
1063 my $e = Execute(suppressOutput=>1);
1064  
1065 is_deeply $e->memory, {
1066 1 => bless([0, 2, 7, 0], "Tree"),
1067 2 => bless([0, 1, 0, 1, 3, 4, 5], "Node"),
1068 3 => bless([11 .. 17], "Keys"),
1069 4 => bless([21 .. 27], "Data"),
1070 5 => bless([31 .. 37, 97], "Down"),
1071 6 => bless([0, 2, 0, 1, 7, 8, 9], "Node"),
1072 7 => bless([41, 14, 15, 44 .. 47], "Keys"),
1073 8 => bless([51, 24, 25, 54 .. 57], "Data"),
1074 9 => bless([61, 34, 35, 36, 65, 66, 67, 99], "Down")}
1075 }
1076  
1077 #latest:;
1078 if (1) #TFindResult_new #TFindResult_cmp
1079 {Start 1;
1080 my $f = FindResult_new(1, 2, 3, 4);
1081 my $n = FindResult_node($f);
1082 my $k = FindResult_key($f);
1083 my $c = FindResult_cmp($f);
1084 my $i = FindResult_index($f);
1085 Out $_ for $n, $c, $k, $i;
1086 my $e = Execute(suppressOutput=>1);
1087 is_deeply $e->out, [1, 3, 2, 4];
1088 is_deeply $e->memory, {1=>[1, 3, 2, 4]};
1089 }
1090  
1091 #latest:;
1092 if (1) #TInsert
1093 {Start 1;
1094 my $t = New(3); # Create tree
1095 my $f = Find($t, 1);
1096 my $c = FindResult_cmp($f);
1097 AssertEq($c, FindComparison_notFound);
1098 my $e = Execute(suppressOutput=>1);
1099 is_deeply $e->out, [];
1100 }
1101  
1102 #latest:;
1103 if (1) #TInsert
1104 {Start 1;
1105 my $t = New(3);
1106 Insert($t, 1, 11);
1107 my $e = Execute(suppressOutput=>1);
1108  
1109 is_deeply $e->memory, {
1110 1 => bless([1, 1, 3, 2], "Tree"),
1111 2 => bless([1, 1, 0, 1, 3, 4, 0], "Node"),
1112 3 => bless([1], "Keys"),
1113 4 => bless([11], "Data")};
1114 }
1115  
1116 #latest:;
1117 if (1) #TInsert
1118 {Start 1;
1119 my $t = New(3);
1120 Insert($t, 1, 11);
1121 Insert($t, 2, 22);
1122 my $e = Execute(suppressOutput=>1);
1123  
1124 is_deeply $e->memory, {
1125 1 => bless([2, 1, 3, 2], "Tree"),
1126 2 => bless([2, 1, 0, 1, 3, 4, 0], "Node"),
1127 3 => bless([1, 2], "Keys"),
1128 4 => bless([11, 22], "Data")};
1129 }
1130  
1131 #latest:;
1132 if (1) #TInsert
1133 {Start 1;
1134 my $t = New(3);
1135 Insert($t, $_, "$_$_") for 1..3;
1136 my $e = Execute(suppressOutput=>1);
1137  
1138 is_deeply $e->memory, {
1139 1 => bless([3, 1, 3, 2], "Tree"),
1140 2 => bless([3, 1, 0, 1, 3, 4, 0], "Node"),
1141 3 => bless([1, 2, 3], "Keys"),
1142 4 => bless([11, 22, 33], "Data")}
1143 }
1144  
1145 #latest:;
1146 if (1) #TInsert
1147 {Start 1;
1148 my $t = New(3);
1149 Insert($t, $_, "$_$_") for 1..4;
1150 my $e = Execute(suppressOutput=>1);
1151  
1152 is_deeply $e->memory, {
1153 1 => bless([4, 3, 3, 2], "Tree"),
1154 2 => bless([1, 1, 0, 1, 3, 4, 11], "Node"),
1155 3 => bless([2], "Keys"),
1156 4 => bless([22], "Data"),
1157 5 => bless([1, 2, 2, 1, 6, 7, 0], "Node"),
1158 6 => bless([1], "Keys"),
1159 7 => bless([11], "Data"),
1160 8 => bless([2, 3, 2, 1, 9, 10, 0], "Node"),
1161 9 => bless([3, 4], "Keys"),
1162 10 => bless([33, 44], "Data"),
1163 11 => bless([5, 8], "Down"),
1164 };
1165 }
1166  
1167 #latest:;
1168 if (1) #TInsert
1169 {Start 1;
1170 my $t = New(3);
1171 Insert($t, $_, "$_$_") for 1..5;
1172  
1173 my $e = Execute(suppressOutput=>1);
1174  
1175 is_deeply $e->memory, {
1176 1 => bless([5, 5, 3, 2], "Tree"),
1177 2 => bless([2, 1, 0, 1, 3, 4, 11], "Node"),
1178 3 => bless([2, 4], "Keys"),
1179 4 => bless([22, 44], "Data"),
1180 5 => bless([1, 2, 2, 1, 6, 7, 0], "Node"),
1181 6 => bless([1], "Keys"),
1182 7 => bless([11], "Data"),
1183 11 => bless([5, 14, 17], "Down"),
1184 14 => bless([1, 4, 2, 1, 15, 16, 0], "Node"),
1185 15 => bless([3], "Keys"),
1186 16 => bless([33], "Data"),
1187 17 => bless([1, 5, 2, 1, 18, 19, 0], "Node"),
1188 18 => bless([5], "Keys"),
1189 19 => bless([55], "Data")}
1190 }
1191  
1192 #latest:;
1193 if (1) #TInsert
1194 {Start 1;
1195 my $t = New(3);
1196 Insert($t, $_, "$_$_") for 1..6;
1197 my $e = Execute(suppressOutput=>1);
1198  
1199 is_deeply $e->memory, {
1200 1 => bless([6, 5, 3, 2], "Tree"),
1201 2 => bless([2, 1, 0, 1, 3, 4, 11], "Node"),
1202 3 => bless([2, 4], "Keys"),
1203 4 => bless([22, 44], "Data"),
1204 5 => bless([1, 2, 2, 1, 6, 7, 0], "Node"),
1205 6 => bless([1], "Keys"),
1206 7 => bless([11], "Data"),
1207 11 => bless([5, 14, 17], "Down"),
1208 14 => bless([1, 4, 2, 1, 15, 16, 0], "Node"),
1209 15 => bless([3], "Keys"),
1210 16 => bless([33], "Data"),
1211 17 => bless([2, 5, 2, 1, 18, 19, 0], "Node"),
1212 18 => bless([5, 6], "Keys"),
1213 19 => bless([55, 66], "Data")};
1214 }
1215  
1216 #latest:;
1217 if (1) #TNew #TInsert
1218 {my $W = 3; my $N = 66; my @r = randomArray $N;
1219  
1220 Start 1;
1221 my $t = New($W);
1222  
1223 for my $i(1..$N)
1224 {Insert($t, $r[$i-1], $r[$i-1]);
1225 }
1226  
1227 my $e = Execute(suppressOutput=>1);
1228 is_deeply printTreeKeys($e->memory), <<END;
1229 30
1230 13 44 55
1231 7 20 25 37 50 61
1232 2 4 9 11 15 17 23 27 33 35 39 41 47 52 58 63 65
1233 1 3 5 6 8 10 12 14 16 18 19 21 22 24 26 28 29 31 32 34 36 38 40 42 43 45 46 48 49 51 53 54 56 57 59 60 62 64 66
1234 END
1235 }
1236  
1237 #latest:;
1238 if (1) # Print tree - random - 5
1239 {my $W = 5; my $N = 66; my @r = randomArray $N;
1240  
1241 Start 1;
1242 my $t = New($W);
1243  
1244 for my $i(1..$N)
1245 {Insert($t, $r[$i-1], $r[$i-1]);
1246 }
1247  
1248 my $e = Execute(suppressOutput=>1);
1249 is_deeply printTreeKeys($e->memory), <<END;
1250 23 39 51
1251 4 7 12 17 20 27 30 33 36 43 47 55 58 62
1252 1 2 3 5 6 8 9 10 11 13 14 15 16 18 19 21 22 24 25 26 28 29 31 32 34 35 37 38 40 41 42 44 45 46 48 49 50 52 53 54 56 57 59 60 61 63 64 65 66
1253 END
1254 }
1255  
1256 #latest:;
1257 if (1) # Print tree keys
1258 {my $W = 3; my $N = 65;
1259  
1260 Start 1;
1261 my $t = New($W);
1262  
1263 for my $i(1..$N)
1264 {Insert($t, $i, $i);
1265 }
1266  
1267 my $e = Execute(suppressOutput=>1);
1268 is_deeply printTreeKeys($e->memory), <<END;
1269 16 32
1270 8 24 40 48 56
1271 4 12 20 28 36 44 52 60
1272 2 6 10 14 18 22 26 30 34 38 42 46 50 54 58 62 64
1273 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65
1274 END
1275 }
1276  
1277 #latest:;
1278 if (1) # Print tree keys - reverse
1279 {my $W = 3; my $N = 65;
1280  
1281 Start 1;
1282 my $t = New($W);
1283  
1284 for my $i(reverse 1..$N)
1285 {Insert($t, $i, $i);
1286 }
1287  
1288 my $e = Execute(suppressOutput=>1);
1289 is_deeply printTreeKeys($e->memory), <<END;
1290 34 50
1291 10 18 26 42 58
1292 6 14 22 30 38 46 54 62
1293 2 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64
1294 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65
1295 END
1296 }
1297  
1298 #latest:;
1299 if (1) # Print tree data
1300 {my $W = 3; my $N = 65;
1301  
1302 Start 1;
1303 my $t = New($W);
1304  
1305 for my $i(1..$N)
1306 {Insert($t, $i, $i);
1307 }
1308  
1309 my $e = Execute(suppressOutput=>1);
1310 is_deeply printTreeKeys($e->memory), <<END;
1311 16 32
1312 8 24 40 48 56
1313 4 12 20 28 36 44 52 60
1314 2 6 10 14 18 22 26 30 34 38 42 46 50 54 58 62 64
1315 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65
1316 END
1317 }
1318  
1319 #latest:;
1320 if (1) # Print tree data - reverse
1321 {my $W = 3; my $N = 65;
1322  
1323 Start 1;
1324 my $t = New($W);
1325  
1326 for my $i(reverse 1..$N)
1327 {Insert($t, $i, $i);
1328 }
1329  
1330 my $e = Execute(suppressOutput=>1);
1331 is_deeply printTreeData($e->memory), <<END;
1332 34 50
1333 10 18 26 42 58
1334 6 14 22 30 38 46 54 62
1335 2 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64
1336 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65
1337 END
1338 }
1339  
1340 #latest:;
1341 if (1) # Compare trees of keys and data
1342 {my $W = 3; my $N = 165; my @r = randomArray $N;
1343  
1344 Start 1;
1345 my $t = New($W);
1346  
1347 for my $i(0..$N-1)
1348 {Insert($t, $r[$i], $r[$i]);
1349 }
1350  
1351 my $e = Execute(suppressOutput=>1);
1352 is_deeply printTreeKeys($e->memory),
1353 printTreeData($e->memory);
1354 }
1355  
1356 #latest:;
1357 if (1) #TprintTreeKeys #TprintTreeData
1358 {my $W = 7; my $N = 165; my @r = randomArray $N;
1359  
1360 Start 1;
1361 my $t = New($W);
1362  
1363 for my $i(0..$N-1)
1364 {Insert($t, $r[$i], $r[$i]);
1365 }
1366  
1367 my $e = Execute(suppressOutput=>1);
1368 is_deeply printTreeKeys($e->memory),
1369 printTreeData($e->memory);
1370 }
1371  
1372 #latest:;
1373 if (1) # Compare trees of keys and data
1374 {my $W = 3; my $N = 75; my @r = randomArray $N;
1375  
1376 Start 1;
1377 my $t = New($W);
1378  
1379 for my $i(0..$N-1)
1380 {Insert($t, $r[$i], $r[$i]);
1381 }
1382  
1383 Iterate # Iterate tree
1384 {my ($find) = @_; # Find result
1385 my $k = FindResult_key($find);
1386 Out $k;
1387 } $t;
1388  
1389 my $e = Execute(suppressOutput=>1);
1390 is_deeply $e->out, [1..$N];
1391 }
1392  
1393 #latest:;
1394 if (1) #TrandomArray
1395 {my $W = 3; my $N = 76; my @r = randomArray $N;
1396  
1397 Start 1;
1398 my $t = New($W);
1399  
1400 for my $i(0..$N-1)
1401 {Insert($t, $r[$i], $r[$i]);
1402 }
1403  
1404 Iterate # Iterate tree
1405 {my ($find) = @_; # Find result
1406 my $k = FindResult_key($find);
1407 Out $k;
1408 } $t;
1409  
1410 my $e = Execute(suppressOutput=>1);
1411 is_deeply $e->out, [1..$N];
1412 }
1413  
1414 #latest:;
1415 if (1) #TIterate #TKeys #TFindResult_key #TFindResult_data #TFind
1416 {my $W = 3; my $N = 107; my @r = randomArray $N;
1417  
1418 Start 1;
1419 my $t = New($W); # Create tree at expected location in memory
1420  
1421 my $a = Array "aaa";
1422 for my $I(1..$N) # Load array
1423 {my $i = $I-1;
1424 Mov [$a, $i, "aaa"], $r[$i];
1425 }
1426  
1427 ForArray # Create tree
1428 {my ($i, $k) = @_;
1429 my $n = Keys($t);
1430 AssertEq $n, $i; # Check tree size
1431 my $K = Add $k, $k;
1432 Tally 1;
1433 Insert($t, $k, $K); # Insert a new node
1434 Tally 0;
1435 } $a, q(aaa);
1436  
1437 Iterate # Iterate tree
1438 {my ($find) = @_; # Find result
1439 my $k = FindResult_key($find);
1440 Out $k;
1441 my $f = Find($t, $k); # Find
1442 my $d = FindResult_data($f);
1443 my $K = Add $k, $k;
1444 AssertEq $K, $d; # Check result
1445 } $t;
1446  
1447 my $e = Execute(suppressOutput=>1);
1448  
1449 is_deeply $e->out, [1..$N]; # Expected sequence
1450  
1451 is_deeply $e->tallyCount, 26177; # Insertion instruction counts
1452 is_deeply $e->tallyCounts->{1}, {
1453 add => 860,
1454 array => 607,
1455 call => 107,
1456 free => 360,
1457 inc => 1044,
1458 jEq => 631,
1459 jGe => 1667,
1460 jLe => 461,
1461 jLt => 565,
1462 jmp => 1436,
1463 jNe => 1095,
1464 mov => 12328,
1465 not => 695,
1466 paramsGet => 321,
1467 paramsPut => 321,
1468 resize => 12,
1469 return => 107,
1470 shiftRight => 68,
1471 shiftUp => 300,
1472 subtract => 641,
1473 tracePoint => 2551,
1474 };
1475 }
1476  
1477 done_testing;
1478  
1479 # (\A.{80})\s+(#.*\Z) \1\2