blib/lib/Zero/NWayTree.pm untested

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