lib/Zero/NWayTree.pm

filter: Statementstmt 6.7% 58 / 855 Branchbran 7.1% 2 / 28 Conditioncond 0.0% 0 / 14 MC/DCmcdc 0.0% 0 / 9 Subroutinesub 8.3% 12 / 144 Podpod 0.0% 0 / 12 totaltotal 6.7% 72 / 1062 CC 23 SCAR 18.6
CC
23
Cov
7%
printNode
56.0
FindResult
30.0
printTree
30.0
CRAP 6.4
« lib/Zero/Emulator.pm ↑ Summary blib/lib/Zero/NWayTree.pm »
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 1 ▶use v5.30;
Subroutine BEGIN: called CC=1 SCAR=0.0
8 package Zero::NWayTree;
9 1 our $VERSION = 20230513; # Version
10 1 ▶use warnings FATAL => qw(all);
Subroutine BEGIN: called CC=1 SCAR=0.0
11 1 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
12 1 ▶use Carp qw(cluck confess);
Subroutine BEGIN: called CC=1 SCAR=0.0
13 1 ▶use Data::Dump qw(dump);
Subroutine BEGIN: called CC=1 SCAR=0.0
14 1 ▶use Data::Table::Text qw(:all);
Subroutine BEGIN: called CC=1 SCAR=0.0
15 1 ▶use Zero::Emulator qw(:all);
Subroutine BEGIN: called CC=1 SCAR=0.0
16 1 ▶eval "use Test::More tests=>30" unless caller;
Branch: 1 branch
BranchTrueFalseTotal
unless caller 0 1 1
17  
18 1 makeDieConfess;
19  
20 0 ▶my sub MaxIterations{99}; # The maximum number of levels in a tree
Subroutine MaxIterations: not called CC=1 SCAR=6.9
21  
22 my $Tree = sub # The structure of an n-way tree
23 1 ▶ {my $t = Zero::Emulator::AreaStructure("Structure");
Subroutine __ANON__: called CC=1 SCAR=0.0
24 1 $t->name(q(keys)); # Number of keys in tree
25 1 $t->name(q(nodes)); # Number of nodes in tree
26 1 $t->name(q(NumberOfKeysPerNode)); # The maximum number of keys in a node of this tree
27 1 $t->name(q(root)); # Root node
28 1 $t
29 1 }->();
30  
31 my $Node = sub # The structure of an n-way tree node
32 1 ▶ {my $n = Zero::Emulator::AreaStructure("Node_Structure");
Subroutine __ANON__: called CC=1 SCAR=0.0
33 1 $n->name(q(length)); # The current number of keys in the node
34 1 $n->name(q(id)); # A number identifying this node within this tree
35 1 $n->name(q(up)); # Parent node unless at the root node
36 1 $n->name(q(tree)); # The definition of the containing tree
37 1 $n->name(q(keys)); # Keys associated with this node
38 1 $n->name(q(data)); # Data associated with each key associated with this node
39 1 $n->name(q(down)); # Next layer of nodes down from this node
40 1 $n
41 1 }->();
42  
43 my $FindResult = sub # The structure of a find result
44 1 ▶ {my $f = Zero::Emulator::AreaStructure("FindResult");
Subroutine __ANON__: called CC=1 SCAR=0.0
45 1 $f->name(q(node)); # Node found
46 1 $f->name(q(cmp)); # Result of the last comparison
47 1 $f->name(q(key)); # Key searched for
48 1 $f->name(q(index)); # Index in the node of located element
49 1 $f
50 1 }->();
51  
52 0 ▶my sub FindResult_lower {0} # Comparison result
Subroutine FindResult_lower: not called CC=1 SCAR=6.9
53 0 ▶my sub FindResult_found {1}
Subroutine FindResult_found: not called CC=1 SCAR=6.9
54 0 ▶my sub FindResult_higher {2}
Subroutine FindResult_higher: not called CC=1 SCAR=6.9
55 0 ▶my sub FindResult_notFound{3}
Subroutine FindResult_notFound: not called CC=1 SCAR=6.9
56  
57 #D1 Constructor # Create a new tree.
58  
59 sub New($) # Create a variable referring to a new tree descriptor.
60 0 ▶ {my ($n) = @_; # Maximum number of keys per node in this tree
Subroutine New: not called CC=3 SCAR=24.8
Pod undocumented
61  
62 0 ▶ $n > 2 && $n % 2 or confess "Number of key/data elements per node must be > 2 and odd";
Branch: 1 branch
BranchTrueFalseTotal
$n > 2 and $n % 2 or confess("Number of key/data elements per node must be > 2 and odd") 0 0 0
Condition0%0/3
$n > 2 and $n % 2
!ll&&!rl&&r
000
MC/DC0%0/2
$n > 2 and $n % 2
$n > 2 $n % 2
Truth table0%0/3
A and B
A= $n > 2B= $n % 2
ABresult
0X0
100
111
63  
64 0 my $t = Array "Tree"; # Allocate tree descriptor
65 0 Mov [$t, $Tree->address(q(NumberOfKeysPerNode)), 'Tree'], $n; # Save maximum number of keys per node
66 0 Mov [$t, $Tree->address(q(root)), 'Tree'], 0; # Clear root
67 0 Mov [$t, $Tree->address(q(keys)), 'Tree'], 0; # Clear keys
68 0 Mov [$t, $Tree->address(q(nodes)), 'Tree'], 0; # Clear nodes
69 0 $t
70 }
71  
72 my sub Tree_getField($$) # Get a field from a tree descriptor
73 0 ▶ {my ($tree, $field) = @_; # Tree, field name
Subroutine Tree_getField: not called CC=1 SCAR=6.9
74 0 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 0 ▶ {my ($tree) = @_; # Tree to examine
Subroutine maximumNumberOfKeys: not called CC=1 SCAR=6.9
79 0 Tree_getField($tree, q(NumberOfKeysPerNode)); # Get attribute from tree descriptor
80 };
81  
82 my sub root($) # Get the root node of a tree
83 0 ▶ {my ($tree) = @_; # Tree to examine
Subroutine root: not called CC=1 SCAR=6.9
84 0 Tree_getField($tree, q(root)); # Get attribute from tree descriptor
85 };
86  
87 my sub setRoot($$) # Set the root node of a tree
88 0 ▶ {my ($tree, $root) = @_; # Tree, root
Subroutine setRoot: not called CC=1 SCAR=6.9
89 0 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 0 ▶ {my ($tree) = @_; # Tree to examine
Subroutine Keys: not called CC=1 SCAR=6.9
Pod undocumented
94 0 Tree_getField($tree, q(keys)); # Keys
95 };
96  
97 my sub incKeys($) # Increment the number of keys in a tree
98 0 ▶ {my ($tree) = @_; # Tree
Subroutine incKeys: not called CC=1 SCAR=6.9
99 0 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 0 ▶ {my ($tree) = @_; # Tree to examine
Subroutine nodes: not called CC=1 SCAR=6.9
104 0 Tree_getField($tree, q(nodes)); # Nodes
105 };
106  
107 my sub incNodes($) # Increment the number of nodes n a tree
108 0 ▶ {my ($tree) = @_; # Tree
Subroutine incNodes: not called CC=1 SCAR=6.9
109 0 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 0 ▶ {my ($node, $field) = @_; # Node, field name
Subroutine Node_getField: not called CC=1 SCAR=6.9
114 0 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 0 ▶ {my ($node) = @_; # Node
Subroutine Node_length: not called CC=1 SCAR=6.9
119 0 Node_getField($node, q(length)); # Get length
120 }
121  
122 my sub Node_setLength($$) # Set the length of a node
123 0 ▶ {my ($node, $length) = @_; # Node, length
Subroutine Node_setLength: not called CC=1 SCAR=6.9
124 0 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 0 ▶ {my ($node) = @_; # Node
Subroutine Node_incLength: not called CC=1 SCAR=6.9
129 0 Inc [$node, $Node->address(q(length)), 'Node']; # Increment length attribute
130 }
131  
132 my sub Node_id($) # Get id of a node
133 0 ▶ {my ($node) = @_; # Node
Subroutine Node_id: not called CC=1 SCAR=6.9
134 0 Node_getField($node, q(id)); # Get id
135 }
136  
137 my sub Node_up($) # Get parent node from this node
138 0 ▶ {my ($node) = @_; # Node
Subroutine Node_up: not called CC=1 SCAR=6.9
139 0 Node_getField($node, q(up)); # Get up
140 }
141  
142 my sub Node_setUp($$) # Set the parent of a node
143 0 ▶ {my ($node, $parent) = @_; # Node, parent node, area containing parent node reference
Subroutine Node_setUp: not called CC=1 SCAR=6.9
144 0 Mov [$node, $Node->address(q(up)), 'Node'], $parent; # Set parent
145 }
146  
147 my sub Node_tree($) # Get tree containing a node
148 0 ▶ {my ($node) = @_; # Node
Subroutine Node_tree: not called CC=1 SCAR=6.9
149 0 Node_getField($node, q(tree)); # Get tree
150 }
151  
152 my sub Node_field($$) # Get the value of a field in a node
153 0 ▶ {my ($node, $field) = @_; # Node, field name
Subroutine Node_field: not called CC=1 SCAR=6.9
154 0 Mov [$node, $Node->address($field), 'Node']; # Fields
155 }
156  
157 my sub Node_getIndex($$$) # Get the indexed field from a node
158 0 ▶ {my ($node, $index, $field) = @_; # Node, index of field, field name
Subroutine Node_getIndex: not called CC=1 SCAR=6.9
159 0 my $F = Node_field($node, $field); # Array
160 0 Mov [$F, \$index, ucfirst $field]; # Field
161 }
162  
163 my sub Node_setIndex($$$$) # Set an indexed field to a specified value
164 0 ▶ {my ($node, $index, $field, $value) = @_; # Node, index, field name, value
Subroutine Node_setIndex: not called CC=1 SCAR=6.9
165 0 my $F = Node_field($node, $field); # Array
166 0 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 0 ▶ {my ($node, $index) = @_; # Node, index of key
Subroutine Node_keys: not called CC=1 SCAR=6.9
171 0 Node_getIndex($node, $index, q(keys)); # Keys
172 }
173  
174 my sub Node_data($$) # Get the indexed data from a node
175 0 ▶ {my ($node, $index) = @_; # Node, index of data
Subroutine Node_data: not called CC=1 SCAR=6.9
176 0 Node_getIndex($node, $index, q(data)); # Data
177 }
178  
179 my sub Node_down($$) # Get the indexed child node from a node
180 0 ▶ {my ($node, $index) = @_; # Node, index of child
Subroutine Node_down: not called CC=1 SCAR=6.9
181 0 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 0 ▶ {my ($node) = @_; # Node
Subroutine Node_isLeaf: not called CC=1 SCAR=6.9
186 0 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 0 ▶ {my ($node, $index, $value) = @_; # Node, index, value
Subroutine Node_setKeys: not called CC=1 SCAR=6.9
191 0 Node_setIndex($node, $index, q(keys), $value) # Set indexed key
192 }
193  
194 my sub Node_setData($$$) # Set a data field by index
195 0 ▶ {my ($node, $index, $value) = @_; # Node, index, value
Subroutine Node_setData: not called CC=1 SCAR=6.9
196 0 Node_setIndex($node, $index, q(data), $value) # Set indexed key
197 }
198  
199 my sub Node_setDown($$$) # Set a child by index
200 0 ▶ {my ($node, $index, $value) = @_; # Node, index, value
Subroutine Node_setDown: not called CC=1 SCAR=6.9
201 0 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 0 ▶ {my ($tree, %options) = @_; # Tree node is being created in, options
Subroutine Node_new: not called CC=2 SCAR=17.9
206 0 my $n = Array "Node"; # Allocate node
207 0 my $k = Array "Keys"; # Allocate keys
208 0 my $d = Array "Data"; # Allocate data
209  
210 0 ▶ Node_setLength $n, $options{length} // 0; # Length
Condition0%0/2
$options{"length"} // 0
l!l
00
MC/DC0%0/1
$options{"length"} // 0
$options{"length"}
Truth table0%0/2
A
A= $options{"length"}
Aresult
11
00
211  
212 0 Node_setUp $n, 0; # Parent
213  
214 0 Mov [$n, $Node->address(q(keys)), 'Node'], $k; # Keys area
215 0 Mov [$n, $Node->address(q(data)), 'Node'], $d; # Data area
216 0 Mov [$n, $Node->address(q(down)), 'Node'], 0; # Down area
217 0 Mov [$n, $Node->address(q(tree)), 'Node'], $tree; # Containing tree
218 0 incNodes($tree);
219 0 Mov [$n, $Node->address(q(id)), 'Node'], # Assign an id to this node within the tree
220 [$tree, $Tree->address(q(nodes)), 'Tree'];
221 0 my $N = maximumNumberOfKeys($tree); # Get the maximum number of keys per node for a tree
222 0 $n # Return reference to new node
223 }
224  
225 my sub Node_allocDown($%) # Upgrade a leaf node to an internal node
226 0 ▶ {my ($node, %options) = @_; # Node to upgrade, options
Subroutine Node_allocDown: not called CC=1 SCAR=6.9
227 0 my $d = Array "Down"; # Allocate down
228 0 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 0 ▶ {my ($findResult, $field) = @_; # Find result, name of field
Subroutine FindResult_getField: not called CC=1 SCAR=6.9
233 0 Mov [$findResult, $FindResult->address($field), q(FindResult)]; # Fields
234 }
235  
236 sub FindResult_key($) # Get key from find result..
237 0 ▶ {my ($f) = @_; # Find result
Subroutine FindResult_key: not called CC=1 SCAR=6.9
Pod undocumented
238 0 FindResult_getField($f, q(key)) # Key
239 }
240  
241 sub FindResult_cmp($) # Get comparison from find result..
242 0 ▶ {my ($f) = @_; # Find result
Subroutine FindResult_cmp: not called CC=1 SCAR=6.9
Pod undocumented
243 0 FindResult_getField($f, q(cmp)) # Comparison
244 }
245  
246 my sub FindResult_index($) # Get index from find result
247 0 ▶ {my ($f) = @_; # Find result
Subroutine FindResult_index: not called CC=1 SCAR=6.9
248 0 FindResult_getField($f, q(index)) # Index
249 }
250  
251 my sub FindResult_node($) # Get node from find result
252 0 ▶ {my ($f) = @_; # Find result
Subroutine FindResult_node: not called CC=1 SCAR=6.9
253 0 FindResult_getField($f, q(node)) # Node
254 }
255  
256 sub FindResult_data($) # Get data field from find results..
257 0 ▶ {my ($f) = @_; # Find result
Subroutine FindResult_data: not called CC=1 SCAR=6.9
Pod undocumented
258  
259 0 my $n = FindResult_node ($f);
260 0 my $i = FindResult_index($f);
261 0 my $d = Node_data($n, $i);
262 0 $d
263 }
264  
265 my sub FindResult($$) # Convert a symbolic name for a find result comparison to an integer
266 0 ▶ {my ($f, $cmp) = @_; # Find result, comparison result name
Subroutine FindResult: not called CC=5 SCAR=34.0
267 0 ▶ return 0 if $cmp eq q(lower);
Branch: 1 branch
BranchTrueFalseTotal
if $cmp eq "lower" 0 0 0
268 0 ▶ return 1 if $cmp eq q(equal);
Branch: 1 branch
BranchTrueFalseTotal
if $cmp eq "equal" 0 0 0
269 0 ▶ return 2 if $cmp eq q(higher);
Branch: 1 branch
BranchTrueFalseTotal
if $cmp eq "higher" 0 0 0
270 0 ▶ return 3 if $cmp eq q(notFound);
Branch: 1 branch
BranchTrueFalseTotal
if $cmp eq "notFound" 0 0 0
271 }
272  
273 my sub Node_open($$$$$) # Open a gap in an interior node
274 0 ▶ {my ($node, $offset, $length, $K, $D) = @_; # Node
Subroutine Node_open: not called CC=1 SCAR=6.9
275  
276 0 my $k = Mov [$node, \$Node->offset(qw(keys)), 'Node'];
277 0 my $d = Mov [$node, \$Node->offset(qw(data)), 'Node'];
278 0 my $n = Mov [$node, \$Node->offset(qw(down)), 'Node'];
279  
280 0 ShiftUp [$k, \$offset, 'Keys'], $K;
281 0 ShiftUp [$d, \$offset, 'Data'], $D;
282 0 my $o1 = Add $offset, 1;
283 0 ShiftUp [$n, \$o1, 'Down'], 0;
284 0 Node_incLength $node;
285 }
286  
287 my sub Node_openLeaf($$$$$) # Open a gap in a leaf node
288 0 ▶ {my ($node, $offset, $length, $K, $D) = @_; # Node
Subroutine Node_openLeaf: not called CC=1 SCAR=6.9
289  
290 0 my $k = Mov [$node, \$Node->offset(qw(keys)), 'Node'];
291 0 my $d = Mov [$node, \$Node->offset(qw(data)), 'Node'];
292  
293 0 ShiftUp [$k, \$offset, 'Keys'], $K;
294 0 ShiftUp [$d, \$offset, 'Data'], $D;
295 0 Node_incLength $node;
296 }
297  
298 my sub Node_copy($$$$$) # Copy part of one interior node into another node.
299 0 ▶ {my ($t, $s, $to, $so, $length) = @_; # Target node, source node, target offset, source offset, length
Subroutine Node_copy: not called CC=1 SCAR=6.9
300  
301 For # Each key, data, down
302 0 ▶ {my ($i, $check, $next, $end) = @_;
Subroutine __ANON__: not called CC=1 SCAR=6.9
303 0 my $S = Add $so, $i;
304 0 my $T = Add $to, $i;
305  
306 0 my $k = Node_keys ($s, $S);
307 0 my $d = Node_data ($s, $S);
308 0 my $n = Node_down ($s, $S);
309 0 Node_setKeys($t, $T, $k);
310 0 Node_setData($t, $T, $d);
311 0 Node_setDown($t, $T, $n);
312 0 } $length;
313  
314 0 my $S = Add $so, $length;
315 0 my $T = Add $to, $length;
316  
317 0 my $n = Node_down($s, $S);
318 0 Node_setDown($t, $T, $n);
319 }
320  
321 my sub Node_copy_leaf($$$$$) # Copy part of one leaf node into another node.
322 0 ▶ {my ($t, $s, $to, $so, $length) = @_; # Target node, source node, target offset, source offset, length
Subroutine Node_copy_leaf: not called CC=1 SCAR=6.9
323  
324 For # Each key, data, down
325 0 ▶ {my ($i, $check, $next, $end) = @_;
Subroutine __ANON__: not called CC=1 SCAR=6.9
326 0 my $S = Add $so, $i;
327 0 my $T = Add $to, $i;
328  
329 0 my $k = Node_keys ($s, $S);
330 0 my $d = Node_data ($s, $S);
331 0 Node_setKeys($t, $T, $k);
332 0 Node_setData($t, $T, $d);
333 0 } $length;
334 }
335  
336 my sub Node_free($) # Free a node
337 0 ▶ {my ($node) = @_; # Node to free
Subroutine Node_free: not called CC=1 SCAR=6.9
338 IfFalse Node_isLeaf($node),
339 Then
340 0 ▶ {my $K = Mov [$node, $Node->address(q(keys)), 'Node'];
Subroutine __ANON__: not called CC=1 SCAR=6.9
341 0 my $D = Mov [$node, $Node->address(q(data)), 'Node'];
342 0 my $N = Mov [$node, $Node->address(q(down)), 'Node'];
343 0 Free $K, "Keys";
344 0 Free $D, "Data";
345 0 Free $N, "Down";
346 0 };
347 0 Free $node, "Node";
348 }
349  
350 my sub FindResult_renew($$$$$) # Reuse an existing find result
351 0 ▶ {my ($find, $node, $key, $cmp, $index) = @_; # Find result, node, search key, comparison result, index
Subroutine FindResult_renew: not called CC=1 SCAR=6.9
352 0 my $f = $find;
353  
354 0 Mov [$f, $FindResult->address(q(node)) , 'FindResult'], $node;
355 0 Mov [$f, $FindResult->address(q(key)) , 'FindResult'], $key;
356 0 Mov [$f, $FindResult->address(q(cmp)) , 'FindResult'], $cmp;
357 0 Mov [$f, $FindResult->address(q(index)), 'FindResult'], $index;
358 0 $f
359 }
360  
361 my sub FindResult_create() # Create an empty find result ready for use
362 0 ▶ {Array "FindResult"; # Find result
Subroutine FindResult_create: not called CC=1 SCAR=6.9
363 }
364  
365 my sub FindResult_free($) # Free a find result
366 0 ▶ {my ($find) = @_; # Find result
Subroutine FindResult_free: not called CC=1 SCAR=6.9
367 0 Free $find, "FindResult"; # Free find result
368 }
369  
370 my sub FindResult_new($$$$) # New find result
371 0 ▶ {my ($node, $key, $cmp, $index) = @_; # Node,search key, comparison result, index
Subroutine FindResult_new: not called CC=1 SCAR=6.9
372 0 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 0 ▶ {my ($node) = @_; # Parameters
Subroutine ReUp: not called CC=1 SCAR=6.9
377 0 my $l = Node_length($node);
378 0 my $L = Add $l, 1;
379  
380 For
381 0 ▶ {my ($i, $check, $next, $end) = @_; # Parameters
Subroutine __ANON__: not called CC=1 SCAR=6.9
382 0 my $d = Node_down ($node, $i);
383 0 Node_setUp($d, $node);
384 0 } $L;
385 }
386  
387 my sub Node_indexInParent($%) # Get the index of a node in its parent.
388 0 ▶ {my ($node, %options) = @_; # Node, options
Subroutine Node_indexInParent: not called CC=2 SCAR=17.9
389 0 ▶ my $p = $options{parent} // Node_up($node); # Parent
Condition0%0/3
$options{"parent"} // Node_up $node
l!l&&r!l&&!r
000
MC/DC0%0/2
$options{"parent"} // Node_up $node
$options{"parent"} Node_up $node
Truth table0%0/3
A // B
A= $options{"parent"}B= Node_up $node
ABresult
1X1
011
000
390 0 AssertNe($p, 0); # Number of children as opposed to the number of keys
391 0 my $d = Node_field($p, 'down');
392 0 my $r = ArrayIndex $d, $node;
393 0 Dec $r;
394 0 $r
395 }
396  
397 my sub Node_indexInParent222222222222($%) # Get the index of a node in its parent.
398 0 ▶ {my ($node, %options) = @_; # Node, options
Subroutine Node_indexInParent222222222222: not called CC=3 SCAR=24.8
399 0 ▶ my $p = $options{parent} // Node_up($node); # Parent
Condition0%0/3
$options{"parent"} // Node_up $node
l!l&&r!l&&!r
000
MC/DC0%0/2
$options{"parent"} // Node_up $node
$options{"parent"} Node_up $node
Truth table0%0/3
A // B
A= $options{"parent"}B= Node_up $node
ABresult
1X1
011
000
400 0 AssertNe($p, 0); # Number of children as opposed to the number of keys
401 0 ▶ my $l = $options{children} // Node_length($p); # Number of children
Condition0%0/3
$options{"children"} // Node_length $p
l!l&&r!l&&!r
000
MC/DC0%0/2
$options{"children"} // Node_length $p
$options{"children"} Node_length $p
Truth table0%0/3
A // B
A= $options{"children"}B= Node_length $p
ABresult
1X1
011
000
402 0 AssertNe($l, 0); # Number of children as opposed to the number of keys
403 0 my $L = Add $l, 1;
404 0 my $r = Var; # Index of child
405  
406 Block
407 0 ▶ {my ($Start, $Good, $Bad, $End) = @_;
Subroutine __ANON__: not called CC=1 SCAR=6.9
408 For # Loop through each child looking for the one specified
409 0 ▶ {my ($i, $check, $next, $end) = @_;
Subroutine __ANON__: not called CC=1 SCAR=6.9
410 IfEq Node_down($p, $i), $node,
411 Then
412 0 ▶ {Mov $r, $i;
Subroutine __ANON__: not called CC=1 SCAR=6.9
413 0 Jmp $End;
414 0 };
415 0 } $L;
416 0 Assert; # Something has gone seriously wrong if we cannot find the node within its parent
417 0 };
418 0 my $R = Node_indexInParent2($node, %options);
419 0 Out "AAAAA11";
420 0 Out $r;
421 0 Out $R;
422 0 Out "AAAAA22";
423 #AssertEq $r, $R;
424 0 $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 0 ▶ {my ($node) = @_; # Node to split
Subroutine Node_SplitIfFull: not called CC=1 SCAR=6.9
429 0 my $nl = Node_length($node);
430 0 my $t = Node_tree($node); # Associated tree
431 0 my $m = maximumNumberOfKeys($t);
432 0 my $split = Var;
433  
434 Block # Various splitting scenarios
435 0 ▶ {my ($start, $good, $bad, $end) = @_;
Subroutine __ANON__: not called CC=1 SCAR=6.9
436 0 Jlt $bad, $nl, $m; # Must be a full node
437  
438 0 my $N = maximumNumberOfKeys($t); # Split points
439 0 my $n = Mov $N; # Copy
440 0 ShiftRight $n, 1; # Index of key that will be placed in parent
441  
442 0 my $L = Add $n, 1;
443 0 my $R = Subtract $N, $L;
444  
445 0 my $l = Node_new($t, length=>$n); # New child nodes
446 0 my $r = Node_new($t, length=>$R);
447  
448 IfFalse Node_isLeaf($node), # Not a leaf
449 Then
450 0 ▶ {Node_allocDown $l; # Add down area on left
Subroutine __ANON__: not called CC=1 SCAR=6.9
451 0 Node_allocDown $r; # Add down area on right
452 0 Node_copy($l, $node, 0, 0, $n); # New left node
453 0 Node_copy($r, $node, 0, $L, $R); # New right node
454 0 ReUp($l);
455 0 ReUp($r);
456 },
457 Else
458 0 ▶ {Node_allocDown $node; # Add down area
Subroutine __ANON__: not called CC=1 SCAR=6.9
459 0 Node_copy_leaf($l, $node, 0, 0, $n); # New left leaf
460 0 Node_copy_leaf($r, $node, 0, $L, $R); # New right leaf
461 0 };
462  
463 0 my $p = Node_up($node); # Existing parent node
464 IfTrue $p,
465 Then # Not a root node
466 0 ▶ {my $pl = Node_length($p);
Subroutine __ANON__: not called CC=1 SCAR=6.9
467 0 Node_setUp($l, $p); # Connect children to parent
468 0 Node_setUp($r, $p);
469  
470 IfEq Node_down($p, 0), $node,
471 Then # Splitting the first child - move everything up
472 0 ▶ {my $nk = Node_keys($node, $n);
Subroutine __ANON__: not called CC=1 SCAR=6.9
473 0 my $nd = Node_data($node, $n);
474 0 Node_open ($p, 0, $pl, $nk, $nd);
475 0 Node_setDown($p, 0, $l);
476 0 Node_setDown($p, 1, $r);
477 0 Node_free($node);
478 0 Jmp $good;
479 0 };
480  
481 IfEq Node_down($p, $pl), $node, # Splitting the last child - just add it on the end
482 Then
483 0 ▶ {my $pk = Node_keys($node, $n);
Subroutine __ANON__: not called CC=1 SCAR=6.9
484 0 my $pd = Node_data($node, $n);
485 0 Node_setKeys ($p, $pl, $pk);
486 0 Node_setDown ($p, $pl, $l);
487 0 my $nd = Node_data($node, $n);
488 0 Node_setData ($p, $pl, $nd);
489 0 my $pl1 = Add $pl, 1;
490 0 Node_setLength($p, $pl1);
491 0 Node_setDown ($p, $pl1, $r);
492 0 Node_free ($node);
493 0 Jmp $good;
494 0 };
495  
496 0 my $i = Node_indexInParent($node, parent=>$p, children=>$pl); # Index of the node being split in its parent
497 0 my $pli = Subtract $pl, $i;
498 0 my $pk = Node_keys($node, $n);
499 0 my $pd = Node_data($node, $n);
500 0 Node_open ($p, $i, $pli, $pk, $pd);
501 0 Node_setDown ($p, $i, $l);
502 0 my $i1 = Add $i, 1;
503 0 Node_setDown ($p, $i1, $r);
504 0 Node_free ($node);
505 0 Jmp $good;
506 0 };
507  
508 0 Node_setUp($l, $node); # Root node with single key after split
509 0 Node_setUp($r, $node); # Connect children to parent
510  
511 0 my $pk = Node_keys($node, $n); # Single key
512 0 my $pd = Node_data($node, $n); # Data associated with single key
513 0 Node_setKeys ($node, 0, $pk);
514 0 Node_setData ($node, 0, $pd);
515 0 Node_setDown ($node, 0, $l);
516 0 Node_setDown ($node, 1, $r);
517 0 Node_setLength($node, 1);
518  
519 0 if (1) # Resize split node
520 0 {my $K = Mov [$node, $Node->address(q(keys)), 'Node'];
521 0 my $D = Mov [$node, $Node->address(q(data)), 'Node'];
522 0 my $N = Mov [$node, $Node->address(q(down)), 'Node'];
523 0 Resize $K, 1;
524 0 Resize $D, 1;
525 0 Resize $N, 2;
526 }
527  
528 0 Jmp $good;
529 }
530 Good # Node was split
531 0 ▶ {Mov $split, 1;
Subroutine __ANON__: not called CC=1 SCAR=6.9
532 },
533 Bad # Node was to small to split
534 0 ▶ {Mov $split, 0;
Subroutine __ANON__: not called CC=1 SCAR=6.9
535 0 };
536 0 $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 0 ▶ {my ($tree, $key) = @_; # Parameters (NWayTree(Tree) * const tree, # Tree to search
Subroutine FindAndSplit: not called CC=1 SCAR=6.9
543 0 my $node = root($tree);
544  
545 0 Node_SplitIfFull($node); # Split the root node if necessary
546 0 my $F = Var;
547  
548 Block # Exit this block when we have located the key
549 0 ▶ {my ($Start, $Good, $Bad, $Found) = @_;
Subroutine __ANON__: not called CC=1 SCAR=6.9
550  
551 For # Step down through the tree
552 0 ▶ {my ($j, $check, $next, $end) = @_; # Parameters
Subroutine __ANON__: not called CC=1 SCAR=6.9
553 0 my $nl = Node_length($node); # Length of node
554 0 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 0 ▶ {Mov $F, FindResult_new($node, $key, FindResult_higher, $last);
Subroutine __ANON__: not called CC=1 SCAR=6.9
560 0 Jmp $Found;
561 0 ▶ };
Subroutine __ANON__: not called CC=1 SCAR=6.9
562 0 my $last1 = Add $last, 1;
563 0 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 0 ▶ {Mov $node, $n;
Subroutine __ANON__: not called CC=1 SCAR=6.9
567 0 };
568 0 Jmp $next;
569 0 };
570  
571 For # Search the keys in this node as greater than least key and less than largest key
572 0 ▶ {my ($i, $check, $next, $end) = @_; # Parameters
Subroutine __ANON__: not called CC=1 SCAR=6.9
573 0 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 0 ▶ {Mov $F, FindResult_new($node, $key, FindResult_lower, $i);
Subroutine __ANON__: not called CC=1 SCAR=6.9
580 0 Jmp $Found;
581 0 ▶ };
Subroutine __ANON__: not called CC=1 SCAR=6.9
582  
583 0 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 0 ▶ {Mov $node, $n;
Subroutine __ANON__: not called CC=1 SCAR=6.9
587 0 };
588 0 Jmp $end;
589 0 };
590  
591 IfEq $key, $k, # Found key
592 Then
593 0 ▶ {Mov $F, FindResult_new($node, $key, FindResult_found, $i);
Subroutine __ANON__: not called CC=1 SCAR=6.9
594 0 Jmp $Found;
595 0 };
596 0 } $nl;
597 0 } MaxIterations;
598 0 Assert; # Failed to descend through the tree to the key.
599 0 };
600 0 $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 0 ▶ {my ($tree, $key, %options) = @_; # Tree to search, key to find, options
Subroutine Find: not called CC=1 SCAR=6.9
Pod undocumented
605  
606 my $p = Procedure 'NWayTree_Find', sub
607 0 ▶ {my ($p) = @_; # Procedure description
Subroutine __ANON__: not called CC=1 SCAR=6.9
608 0 my $tree = ParamsGet 0;
609 0 my $key = ParamsGet 1;
610  
611 0 my $node = root($tree); # Current node we are searching
612  
613 IfFalse $node, # Empty tree
614 Then
615 0 ▶ {ReturnPut 0, FindResult_new($node, $key, FindResult_notFound, -1);
Subroutine __ANON__: not called CC=1 SCAR=6.9
616 0 Return;
617 0 };
618  
619 For # Step down through tree
620 0 ▶ {my ($j, $check, $next, $end) = @_; # Parameters
Subroutine __ANON__: not called CC=1 SCAR=6.9
621 0 my $nl = Node_length($node);
622 0 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 0 ▶ {ReturnPut 0, FindResult_new($node, $key, FindResult_higher, $nl);
Subroutine __ANON__: not called CC=1 SCAR=6.9
629 0 Return;
630 0 ▶ };
Subroutine __ANON__: not called CC=1 SCAR=6.9
631 0 Mov $node, Node_down($node, $nl);
632 0 Jmp $next;
633 0 };
634  
635 For # Search the keys in this node as less than largest key
636 0 ▶ {my ($i, $check, $next, $end) = @_; # Parameters
Subroutine __ANON__: not called CC=1 SCAR=6.9
637 0 my $k = Node_keys($node, $i); # Key from tree
638 IfEq $key, $k, # Found key
639 Then
640 0 ▶ {ReturnPut 0, FindResult_new($node, $key, FindResult_found, $i);
Subroutine __ANON__: not called CC=1 SCAR=6.9
641 0 Return;
642 0 };
643 IfLt $key, $k, # Lower than current key
644 Then
645 {IfTrue Node_isLeaf($node), # Leaf
646 Then
647 0 ▶ {ReturnPut 0, FindResult_new($node, $key, FindResult_lower, $i);
Subroutine __ANON__: not called CC=1 SCAR=6.9
648 0 Return;
649 0 ▶ };
Subroutine __ANON__: not called CC=1 SCAR=6.9
650 0 Mov $node, Node_down($node, $i);
651 0 Jmp $end;
652 0 };
653 0 } $nl;
654 0 } MaxIterations;
655 0 Assert;
656 0 };
657  
658 0 ParamsPut 0, $tree; # Set parameters and call insert procedure
659 0 ParamsPut 1, $key;
660 0 Call $p;
661 0 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 0 ▶ {my ($tree, $key, $data, %options) = @_; # Tree, key, data
Subroutine Insert: not called CC=1 SCAR=6.9
Pod undocumented
668  
669 my $p = Procedure 'NWayTree_Insert', sub
670 0 ▶ {my ($p) = @_; # Procedure description
Subroutine __ANON__: not called CC=1 SCAR=6.9
671  
672 Block
673 0 ▶ {my ($Start, $Good, $Bad, $Finish) = @_; # Parameters
Subroutine __ANON__: not called CC=1 SCAR=6.9
674  
675 0 my $tree = ParamsGet 0;
676 0 my $key = ParamsGet 1;
677 0 my $data = ParamsGet 2;
678 0 my $n = root($tree); # Root node of tree
679  
680 IfFalse $n, # Empty tree
681 Then
682 0 ▶ {my $n = Node_new($tree, length=>1);
Subroutine __ANON__: not called CC=1 SCAR=6.9
683 0 Node_setKeys ($n, 0, $key);
684 0 Node_setData ($n, 0, $data);
685 0 incKeys($tree);
686 0 setRoot($tree, $n);
687 0 Jmp $Finish;
688 0 };
689  
690 0 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 0 ▶ {my ($i, $check, $next, $end) = @_; # Parameters
Subroutine __ANON__: not called CC=1 SCAR=6.9
699 0 my $k = Node_keys($n, $i); # Key to check
700 IfEq $key, $k, # Key already present
701 Then
702 0 ▶ {Node_setData($n, $i, $data);
Subroutine __ANON__: not called CC=1 SCAR=6.9
703 0 Jmp $Finish;
704 0 };
705 IfLt $key, $k, # We have reached the insertion point
706 Then
707 0 ▶ {my $nli = Subtract $nl, $i;
Subroutine __ANON__: not called CC=1 SCAR=6.9
708 0 Node_openLeaf($n, $i, $nli, $key, $data);
709 0 incKeys($tree);
710 0 Jmp $Finish;
711 0 };
712 0 ▶ } $nl;
Subroutine __ANON__: not called CC=1 SCAR=6.9
713 0 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 0 Node_setData($n, $nl, $data);
715 0 my $nl1 = Add $nl, 1;
716 0 Node_setLength($n, $nl1);
717 0 incKeys($tree);
718 0 Jmp $Finish;
719 0 ▶ };
Subroutine __ANON__: not called CC=1 SCAR=6.9
720 0 ▶ };
Subroutine __ANON__: not called CC=1 SCAR=6.9
721 0 };
722 # Insert node
723 0 my $r = FindAndSplit($tree, $key); # Check for existing key
724 0 my $N = FindResult_node($r);
725 0 my $c = FindResult_cmp($r);
726 0 my $i = FindResult_index($r);
727 0 FindResult_free($r);
728  
729 IfEq $c, FindResult_found, # Found an equal key whose data we can update
730 Then
731 0 ▶ {Node_setData($N, $i, $data);
Subroutine __ANON__: not called CC=1 SCAR=6.9
732 0 Jmp $Finish;
733 0 };
734  
735 0 my $Nl = Node_length($N);
736 0 my $Nl1 = Add $Nl, 1;
737 IfEq $c, FindResult_higher, # Found a key that is greater than the one being inserted
738 Then
739 0 ▶ {my $i1 = Add $i, 1;
Subroutine __ANON__: not called CC=1 SCAR=6.9
740 0 my $l = Subtract $Nl, $i1;
741 0 Node_openLeaf($N, $i1, $l, $key, $data);
742 },
743 Else
744 0 ▶ {my $l = Subtract $Nl, $i;
Subroutine __ANON__: not called CC=1 SCAR=6.9
745 0 Node_openLeaf($N, $i, $l, $key, $data);
746 0 };
747  
748 0 incKeys($tree);
749 0 Node_SplitIfFull($N); # Split if the leaf is full to force keys up the tree
750 0 };
751 0 Return;
752 0 };
753  
754 0 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 0 ParamsPut 1, $key;
756 0 ParamsPut 2, $data;
757 0 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 0 ▶ {my ($find, $node) = @_; # Find result, Node
Subroutine GoAllTheWayLeft: not called CC=1 SCAR=6.9
764  
765 IfFalse $node, # Empty tree
766 Then
767 0 ▶ {FindResult_renew($find, $node, 0, FindResult_notFound, 0);
Subroutine __ANON__: not called CC=1 SCAR=6.9
768 },
769 Else
770 {For # Step down through tree
771 0 ▶ {my ($i, $check, $next, $end) = @_; # Parameters
Subroutine __ANON__: not called CC=1 SCAR=6.9
772 0 JTrue $end, Node_isLeaf($node); # Reached leaf
773 0 Mov $node, Node_down($node, 0);
774 0 ▶ } MaxIterations;
Subroutine __ANON__: not called CC=1 SCAR=6.9
775 0 FindResult_renew($find, $node, Node_keys($node, 0), FindResult_found,0); # Leaf - place us on the first key
776 0 };
777 0 $find
778 }
779  
780 my sub GoUpAndAround($) # Go up until it is possible to go right or we can go no further
781 0 ▶ {my ($find) = @_; # Find
Subroutine GoUpAndAround: not called CC=1 SCAR=6.9
782  
783 Block
784 0 ▶ {my ($Start, $Good, $Bad, $Finish) = @_; # Parameters
Subroutine __ANON__: not called CC=1 SCAR=6.9
785 0 my $node = FindResult_node($find);
786  
787 IfTrue Node_isLeaf($node), # Leaf
788 Then
789 0 ▶ {my $I = FindResult_index($find);
Subroutine __ANON__: not called CC=1 SCAR=6.9
790 0 my $L = Node_length($node);
791 0 my $L1 = Subtract $L, 1;
792 IfLt $I, $L1, # More keys in leaf
793 Then
794 0 ▶ {my $i = Add $I, 1;
Subroutine __ANON__: not called CC=1 SCAR=6.9
795 0 FindResult_renew($find, $node, Node_keys($node, $i),
796 FindResult_found, $i);
797 0 Jmp $Finish;
798 0 };
799  
800 0 my $parent = Node_up($node); # Parent
801 IfTrue $parent,
802 Then
803 {For # Not the only node in the tree
804 0 ▶ {my ($j, $check, $next, $end) = @_; # Parameters
Subroutine __ANON__: not called CC=1 SCAR=6.9
805 0 my $pl = Node_length($parent); # Number of children
806 0 my $i = Node_indexInParent($node, parent=>$parent, children=>$pl); # Index in parent
807  
808 IfEq $i, $pl, # Last key - continue up
809 Then
810 0 ▶ {Mov $node, $parent;
Subroutine __ANON__: not called CC=1 SCAR=6.9
811 0 my $Parent = Node_up($parent); # Parent
812 0 Mov $parent, $Parent;
813 0 JFalse $end, $parent;
814 },
815 Else
816 0 ▶ {FindResult_renew($find, $parent, Node_keys($parent, $i), # Not the last key
Subroutine __ANON__: not called CC=1 SCAR=6.9
817 FindResult_found, $i);
818 0 Jmp $Finish;
819 0 };
820 0 ▶ } MaxIterations;
Subroutine __ANON__: not called CC=1 SCAR=6.9
821 0 };
822 0 FindResult_renew($find, $node, 0, FindResult_notFound, 0); # Last key of root
823 0 Jmp $Finish;
824 0 };
825  
826 0 my $i = FindResult_index($find); # Not a leaf so on an interior key so we can go right then all the way left
827 0 my $I = Add $i, 1;
828 0 my $d = Node_down($node, $I);
829 0 GoAllTheWayLeft($find, $d);
830 0 };
831 0 $find
832 }
833  
834 my sub IterStart($) # Start an iterator
835 0 ▶ {my ($tree) = @_; # Tree to iterate
Subroutine IterStart: not called CC=1 SCAR=6.9
836 0 my $n = root($tree);
837 0 my $f = FindResult_create;
838 0 GoAllTheWayLeft($f, $n);
839 }
840  
841 my sub IterCheck($) # True if we can continue to iterate
842 0 ▶ {my ($F) = @_; # Parameters (NWayTree(FindResult) const find) # Find result of last iteration
Subroutine IterCheck: not called CC=1 SCAR=6.9
843 0 my $r = Var;
844 IfEq FindResult_cmp($F), FindResult_notFound,
845 Then
846 0 ▶ {Mov $r, 0;
Subroutine __ANON__: not called CC=1 SCAR=6.9
847 },
848 Else
849 0 ▶ {Mov $r, 1;
Subroutine __ANON__: not called CC=1 SCAR=6.9
850 0 };
851 0 $r
852 }
853  
854 my sub IterNext($) # Next element of an iteration
855 0 ▶ {my ($F) = @_; # Parameters (NWayTree(FindResult) const find) # Find result of last iteration
Subroutine IterNext: not called CC=1 SCAR=6.9
856 0 GoUpAndAround($F);
857 }
858  
859 sub Iterate(&$) # Iterate over a tree.
860 0 ▶ {my ($block, $tree) = @_; # Block of code to execute for each key in tree, tree
Subroutine Iterate: not called CC=1 SCAR=6.9
Pod undocumented
861 0 my $f = IterStart($tree);
862  
863 For
864 0 ▶ {my ($i, $check, $next, $end) = @_; # Parameters
Subroutine __ANON__: not called CC=1 SCAR=6.9
865 0 JFalse $end, IterCheck($f);
866 0 &$block($f);
867  
868 0 IterNext($f);
869 0 } 1e99;
870 0 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 0 ▶ {my ($memory, $node, $indent, $out, $keyNotData) = @_;
Subroutine printNode: not called CC=7 SCAR=40.3
877 0 ▶ ref($node) =~ m(Node) or confess "Not a node: ".dump($node);
Branch: 1 branch
BranchTrueFalseTotal
ref($node) =~ /Node/u or confess('Not a node: ' . Zero::NWayTree::dump($node)) 0 0 0
878 0 my $k = $$node[$Node->offset(q(keys))];
879 0 my $d = $$node[$Node->offset(q(data))];
880 0 my $n = $$node[$Node->offset(q(down))];
881  
882 0 ▶ if ($n) # Interior node
Branch: 1 branch
BranchTrueFalseTotal
if ($n) { } 0 0 0
883 0 {my $K = $$memory{$k};
884 0 my $D = $$memory{$d};
885 0 my $N = $$memory{$n};
886 0 my $l = $$node[$Node->offset(q(length))];
887  
888 0 for my $i(0..$l-1)
889 0 {my $c = $$memory{$$N[$i]}; # Child node
890 0 my $p = $$memory{$$c[$Node->offset(q(up))]};
891  
892 0 __SUB__->($memory, $c, $indent+1, $out, $keyNotData);
893 0 ▶ push @$out, [$indent, $keyNotData ? $$K[$i] : $$D[$i]];
Branch: 1 branch
BranchTrueFalseTotal
$keyNotData ? : 0 0 0
894 }
895  
896 0 __SUB__->($memory, $$memory{$$N[$l]}, $indent+1, $out, $keyNotData);
897 }
898  
899 else # Leaf node
900 0 {my $K = $$memory{$k};
901 0 my $D = $$memory{$d};
902 0 my $l = $$node[$Node->offset(q(length))];
903  
904 0 for my $i(0..$l-1)
905 0 {my $k = $$K[$i];
906 0 my $d = $$D[$i];
907 0 ▶ push @$out, [$indent, $keyNotData ? $k : $d];
Branch: 1 branch
BranchTrueFalseTotal
$keyNotData ? : 0 0 0
908 }
909 }
910 0 $out
911 }
912  
913 my sub printTree($$) # Print a tree
914 0 ▶ {my ($m, $keyNotData) = @_; # Memory, key or data
Subroutine printTree: not called CC=5 SCAR=34.0
915 0 my $t = $$m{1};
916 0 my $r = $$m{$$t[$Tree->offset(q(root))]};
917 0 my $o = printNode($m, $r, 0, [], $keyNotData);
918  
919 0 my $C = $#$o; # Number of columns
920 0 my $R = max(map {$$o[$_][0]} keys @$o); # Number of rows
921  
922 0 my $W = 3; # Field width for each key
923 0 my @o; # Output area
924 0 for my $r(0..$R)
925 0 {for my $c(0..$C)
926 0 {$o[$r][$c] = ' ' x $W;
927 }
928 }
929  
930 0 for my $p(keys @$o) # Write tree horizontally
931 0 ▶ {next unless defined(my $v = $$o[$p][1]);
Branch: 1 branch
BranchTrueFalseTotal
unless defined(my $v = $o->[$p][1]) 0 0 0
932 0 my $r = $$o[$p][0];
933 0 my $c = $p;
934  
935 0 $o[$r][$c] = sprintf("%${W}d", $v);
936 }
937  
938 0 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 0 ▶ {my ($m) = @_; # Memory
Subroutine printTreeKeys: not called CC=1 SCAR=6.9
Pod undocumented
943 0 printTree($m, 1);
944 }
945  
946 sub printTreeData($) # Print the data held in a tree.
947 0 ▶ {my ($m) = @_; # Memory
Subroutine printTreeData: not called CC=1 SCAR=6.9
Pod undocumented
948 0 printTree($m, 0);
949 }
950  
951 #D1 Utilities # Utility functions.
952  
953 sub randomArray($) # Create a random array.
954 0 ▶ {my ($N) = @_; # Size of array
Subroutine randomArray: not called CC=2 SCAR=17.9
Pod undocumented
955  
956 0 my @r = 1..$N;
957 0 srand(1);
958  
959 0 for my $i(keys @r) # Disarrange the array
960 0 {my $s = int rand @r;
961 0 my $t = int rand @r;
962 0 ($r[$t], $r[$s]) = ($r[$s], $r[$t]);
963 }
964 @r
965 0 }
966  
967 1 ▶use Exporter qw(import);
Subroutine BEGIN: called CC=1 SCAR=0.0
968 1 ▶use vars qw(@ISA @EXPORT @EXPORT_OK %EXPORT_TAGS);
Subroutine BEGIN: called CC=1 SCAR=0.0
969  
970 1 @ISA = qw(Exporter);
971 1 @EXPORT = qw();
972 1 @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 1 %EXPORT_TAGS = (all=>[@EXPORT, @EXPORT_OK]);
975  
976 1 ▶return 1 if caller;
Branch: 1 branch
BranchTrueFalseTotal
if caller 1 0 1
977  
978 #D0 Tests
979  
980 0 Test::More->builder->output("/dev/null"); # Reduce number of confirmation messages during testing
981  
982 0 my $debug = -e q(/home/phil/); # Assume debugging if testing locally
983 0 ▶eval {goto latest if $debug};
Branch: 1 branch
BranchTrueFalseTotal
if $debug 0 0 0
984  
985 sub is_deeply;
986 sub ok($;$);
987 sub done_testing;
988 0 ▶sub x {exit if $debug} # Stop if debugging.
Subroutine x: not called CC=2 SCAR=17.9
Pod undocumented
Branch: 1 branch
BranchTrueFalseTotal
if $debug 0 0 0
989  
990 #latest:;
991 0 if (1) #TNew
992 0 {Start 1;
993 0 Out New(3);
994 0 my $e = Execute(suppressOutput=>1);
995 0 is_deeply $e->out, [1];
996 0 is_deeply $e->memory, { 1 => bless([0, 0, 3, 0], "Tree") };
997 }
998  
999 #latest:;
1000 0 if (1) #TsetRoot #Troot #TincKeys
1001 0 {Start 1;
1002 0 my $t = New(3);
1003 0 my $r = root($t);
1004  
1005 0 setRoot($t, 1);
1006 0 my $R = root($t);
1007  
1008 0 my $n = maximumNumberOfKeys($t);
1009  
1010 0 incKeys($t) for 1..3;
1011 0 Out [$t, $Tree->address(q(keys)), 'Tree'];
1012  
1013 0 incNodes($t) for 1..5;
1014 0 Out nodes($t);
1015  
1016 0 my $e = Execute(suppressOutput=>1);
1017 0 is_deeply $e->out, [3, 5];
1018 0 is_deeply $e->memory, { 1 => bless([3, 5, 3, 1], "Tree") };
1019 }
1020  
1021 #latest:;
1022 0 if (1) #TNode_open
1023 0 {Start 1;
1024 0 my $t = New(7); # Create tree
1025 0 my $n = Node_new($t); # Create node
1026 0 my $e = Execute(suppressOutput=>1);
1027 0 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 0 if (1) #TNode_open
1036 0 {Start 1;
1037 0 my $N = 7;
1038 0 my $t = New($N); # Create tree
1039 0 my $n = Node_new($t); # Create node
1040  
1041 0 Node_allocDown $n;
1042  
1043 0 for my $i(0..$N-1)
1044 0 {Node_setKeys($n, $i, 1+$i);
1045 0 Node_setData($n, $i, 11+$i);
1046 0 Node_setDown($n, $i, 21+$i);
1047 }
1048  
1049 0 Node_setDown($n, $N, 28);
1050  
1051 0 Node_open($n, 2, 4, 3, 13);
1052 0 my $e = Execute(suppressOutput=>1);
1053  
1054 0 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 0 if (1) #TNode_copy
1064 0 {Start 1;
1065 0 my $t = New(7); # Create tree
1066 0 my $p = Node_new($t); Node_allocDown($p); # Create a node
1067 0 my $q = Node_new($t); Node_allocDown($q); # Create a node
1068  
1069 0 for my $i(0..6)
1070 0 {Node_setKeys($p, $i, 11+$i);
1071 0 Node_setData($p, $i, 21+$i);
1072 0 Node_setDown($p, $i, 31+$i);
1073 0 Node_setKeys($q, $i, 41+$i);
1074 0 Node_setData($q, $i, 51+$i);
1075 0 Node_setDown($q, $i, 61+$i);
1076 }
1077  
1078 0 Node_setDown($p, 7, 97);
1079 0 Node_setDown($q, 7, 99);
1080  
1081 0 Node_copy( $q, $p, 1, 3, 2);
1082  
1083 0 my $e = Execute(suppressOutput=>1);
1084  
1085 0 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 0 if (1) #TFindResult_new #TFindResult_cmp
1099 0 {Start 1;
1100 0 my $f = FindResult_new(1, 2, 3, 4);
1101 0 my $n = FindResult_node($f);
1102 0 my $k = FindResult_key($f);
1103 0 my $c = FindResult_cmp($f);
1104 0 my $i = FindResult_index($f);
1105 0 Out $_ for $n, $c, $k, $i;
1106 0 my $e = Execute(suppressOutput=>1);
1107 0 is_deeply $e->out, [1, 3, 2, 4];
1108 0 is_deeply $e->memory, {1=>[1, 3, 2, 4]};
1109 }
1110  
1111 #latest:;
1112 0 if (1) #TInsert
1113 0 {Start 1;
1114 0 my $t = New(3); # Create tree
1115 0 my $f = Find($t, 1);
1116 0 my $c = FindResult_cmp($f);
1117 0 AssertEq($c, FindResult_notFound);
1118 0 my $e = Execute(suppressOutput=>1);
1119 0 is_deeply $e->out, [];
1120 }
1121  
1122 #latest:;
1123 0 if (1) #TInsert
1124 0 {Start 1;
1125 0 my $t = New(3);
1126 0 Insert($t, 1, 11);
1127 0 my $e = Execute(suppressOutput=>1);
1128  
1129 0 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 0 if (1) #TInsert
1138 0 {Start 1;
1139 0 my $t = New(3);
1140 0 Insert($t, 1, 11);
1141 0 Insert($t, 2, 22);
1142 0 my $e = Execute(suppressOutput=>1);
1143  
1144 0 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 0 if (1) #TInsert
1153 0 {Start 1;
1154 0 my $t = New(3);
1155 0 Insert($t, $_, "$_$_") for 1..3;
1156 0 my $e = Execute(suppressOutput=>1);
1157  
1158 0 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 0 if (1) #TInsert
1167 0 {Start 1;
1168 0 my $t = New(3);
1169 0 Insert($t, $_, "$_$_") for 1..4;
1170 0 my $e = Execute(suppressOutput=>1);
1171  
1172 0 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 0 if (1) #TInsert
1189 0 {Start 1;
1190 0 my $t = New(3);
1191 0 Insert($t, $_, "$_$_") for 1..5;
1192  
1193 0 my $e = Execute(suppressOutput=>1);
1194  
1195 0 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 0 if (1) #TInsert
1214 0 {Start 1;
1215 0 my $t = New(3);
1216 0 Insert($t, $_, "$_$_") for 1..6;
1217 0 my $e = Execute(suppressOutput=>1);
1218  
1219 0 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 0 if (1) #TNew #TInsert #TFind
1238 0 {my $W = 3; my $N = 66;
1239  
1240 0 Start 1;
1241 0 my $t = New($W);
1242  
1243 0 for my $i(1..$N)
1244 0 {Insert($t, $i, my $d = $i+$i);
1245 0 for my $j(1..$i)
1246 0 {AssertEq $j+$j, FindResult_data(Find($t, $j));
1247 }
1248 0 AssertNe FindResult_found, FindResult_cmp(Find($t, 0));
1249 0 AssertNe FindResult_found, FindResult_cmp(Find($t, $i+1));
1250 }
1251  
1252 0 my $e = Execute(suppressOutput=>1);
1253 0 is_deeply $e->out, [];
1254 }
1255  
1256 #latest:;
1257 0 if (1) #TNew #TInsert #TFind
1258 0 {my $W = 3; my $N = 66; my @r = randomArray $N;
1259  
1260 0 Start 1;
1261 0 my $t = New($W);
1262  
1263 0 for my $i(1..$N)
1264 0 {my $k = $r[$i-1]; my $d = $k*2;
1265 0 Insert($t, $k, $d);
1266 0 AssertEq $d, FindResult_data(Find($t, $k));
1267 }
1268  
1269 0 my $e = Execute(suppressOutput=>1);
1270 0 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 0 if (1) # Print tree - random - 5
1281 0 {my $W = 5; my $N = 66; my @r = randomArray $N;
1282  
1283 0 Start 1;
1284 0 my $t = New($W);
1285  
1286 0 for my $i(1..$N)
1287 0 {Insert($t, $r[$i-1], $r[$i-1]);
1288 }
1289  
1290 0 my $e = Execute(suppressOutput=>1);
1291 0 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 0 if (1) # Print tree keys
1300 0 {my $W = 3; my $N = 65;
1301  
1302 0 Start 1;
1303 0 my $t = New($W);
1304  
1305 0 for my $i(1..$N)
1306 0 {Insert($t, $i, $i);
1307 }
1308  
1309 0 my $e = Execute(suppressOutput=>1);
1310 0 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 0 if (1) # Print tree keys - reverse
1321 0 {my $W = 3; my $N = 65;
1322  
1323 0 Start 1;
1324 0 my $t = New($W);
1325  
1326 0 for my $i(reverse 1..$N)
1327 0 {Insert($t, $i, $i);
1328 }
1329  
1330 0 my $e = Execute(suppressOutput=>1);
1331 0 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 0 if (1) # Print tree data
1342 0 {my $W = 3; my $N = 65;
1343  
1344 0 Start 1;
1345 0 my $t = New($W);
1346  
1347 0 for my $i(1..$N)
1348 0 {Insert($t, $i, $i);
1349 }
1350  
1351 0 my $e = Execute(suppressOutput=>1);
1352 0 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 0 if (1) # Print tree data - reverse
1363 0 {my $W = 3; my $N = 65;
1364  
1365 0 Start 1;
1366 0 my $t = New($W);
1367  
1368 0 for my $i(reverse 1..$N)
1369 0 {Insert($t, $i, $i);
1370 }
1371  
1372 0 my $e = Execute(suppressOutput=>1);
1373 0 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 0 if (1) # Compare trees of keys and data
1384 0 {my $W = 3; my $N = 165; my @r = randomArray $N;
1385  
1386 0 Start 1;
1387 0 my $t = New($W);
1388  
1389 0 for my $i(0..$N-1)
1390 0 {Insert($t, $r[$i], $r[$i]);
1391 }
1392  
1393 0 my $e = Execute(suppressOutput=>1);
1394 0 is_deeply printTreeKeys($e->memory),
1395 printTreeData($e->memory);
1396 }
1397  
1398 #latest:;
1399 0 if (1) #TprintTreeKeys #TprintTreeData
1400 0 {my $W = 7; my $N = 165; my @r = randomArray $N;
1401  
1402 0 Start 1;
1403 0 my $t = New($W);
1404  
1405 0 for my $i(0..$N-1)
1406 0 {Insert($t, $r[$i], $r[$i]);
1407 }
1408  
1409 0 my $e = Execute(suppressOutput=>1);
1410 0 is_deeply printTreeKeys($e->memory),
1411 printTreeData($e->memory);
1412 }
1413  
1414 #latest:;
1415 0 if (1) # Compare trees of keys and data
1416 0 {my $W = 3; my $N = 75; my @r = randomArray $N;
1417  
1418 0 Start 1;
1419 0 my $t = New($W);
1420  
1421 0 for my $i(0..$N-1)
1422 0 {Insert($t, $r[$i], $r[$i]);
1423 }
1424  
1425 Iterate # Iterate tree
1426 0 ▶ {my ($find) = @_; # Find result
Subroutine __ANON__: not called CC=1 SCAR=6.9
1427 0 my $k = FindResult_key($find);
1428 0 Out $k;
1429 0 } $t;
1430  
1431 0 my $e = Execute(suppressOutput=>1);
1432 0 is_deeply $e->out, [1..$N];
1433 }
1434  
1435 #latest:;
1436 0 if (1) #TrandomArray
1437 0 {my $W = 3; my $N = 76; my @r = randomArray $N;
1438  
1439 0 Start 1;
1440 0 my $t = New($W);
1441  
1442 0 for my $i(0..$N-1)
1443 0 {Insert($t, $r[$i], $r[$i]);
1444 }
1445  
1446 Iterate # Iterate tree
1447 0 ▶ {my ($find) = @_; # Find result
Subroutine __ANON__: not called CC=1 SCAR=6.9
1448 0 my $k = FindResult_key($find);
1449 0 Out $k;
1450 0 } $t;
1451  
1452 0 my $e = Execute(suppressOutput=>1);
1453 0 is_deeply $e->out, [1..$N];
1454 }
1455  
1456 #latest:;
1457 0 if (1) #TIterate #TKeys #TFindResult_key #TFindResult_data #TFind
1458 0 {my $W = 3; my $N = 107; my @r = randomArray $N;
1459  
1460 0 Start 1;
1461 0 my $t = New($W); # Create tree at expected location in memory
1462  
1463 0 my $a = Array "aaa";
1464 0 for my $I(1..$N) # Load array
1465 0 {my $i = $I-1;
1466 0 Mov [$a, $i, "aaa"], $r[$i];
1467 }
1468  
1469 ForArray # Create tree
1470 0 ▶ {my ($i, $k) = @_;
Subroutine __ANON__: not called CC=1 SCAR=6.9
1471 0 my $n = Keys($t);
1472 0 AssertEq $n, $i; # Check tree size
1473 0 my $K = Add $k, $k;
1474 0 Tally 1;
1475 0 Insert($t, $k, $K); # Insert a new node
1476 0 Tally 0;
1477 0 } $a, q(aaa);
1478  
1479 Iterate # Iterate tree
1480 0 ▶ {my ($find) = @_; # Find result
Subroutine __ANON__: not called CC=1 SCAR=6.9
1481 0 my $k = FindResult_key($find);
1482 0 Out $k;
1483 0 my $f = Find($t, $k); # Find
1484 0 my $d = FindResult_data($f);
1485 0 my $K = Add $k, $k;
1486 0 AssertEq $K, $d; # Check result
1487 0 } $t;
1488  
1489 0 my $e = Execute(suppressOutput=>1);
1490  
1491 0 is_deeply $e->out, [1..$N]; # Expected sequence
1492  
1493 0 is_deeply $e->tallyCount, 23612; # Insertion instruction counts
1494  
1495 #say STDERR "AAAA\n", dump($e->tallyCounts->{1});
1496  
1497 0 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 0 done_testing;
1524  
1525 # (\A.{80})\s+(#.*\Z) \1\2
« lib/Zero/Emulator.pm ↑ Summary blib/lib/Zero/NWayTree.pm »