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