| 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 = 20230511; # 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=>29" unless caller; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 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 FindComparison_lower {0} # Comparison result | ||||||||||||||||||||||||||
|
Subroutine
FindComparison_lower: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 53 | 0 | ▶ | my sub FindComparison_equal {1} | ||||||||||||||||||||||||||
|
Subroutine
FindComparison_equal: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 54 | 0 | ▶ | my sub FindComparison_higher {2} | ||||||||||||||||||||||||||
|
Subroutine
FindComparison_higher: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 55 | 0 | ▶ | my sub FindComparison_notFound{3} | ||||||||||||||||||||||||||
|
Subroutine
FindComparison_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
Condition0%0/3
$n > 2 and $n % 2
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
| |||||||||||||||||||||||||||||
| 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_getIndex($$$) # Get the indexed field from a node | ||||||||||||||||||||||||||||
| 153 | 0 | ▶ | {my ($node, $index, $field) = @_; # Node, index of field, field name | ||||||||||||||||||||||||||
|
Subroutine
Node_getIndex: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 154 | 0 | my $F = Mov [$node, $Node->address($field), 'Node']; # Fields | |||||||||||||||||||||||||||
| 155 | 0 | Mov [$F, \$index, ucfirst $field]; # Field | |||||||||||||||||||||||||||
| 156 | } | ||||||||||||||||||||||||||||
| 157 | |||||||||||||||||||||||||||||
| 158 | my sub Node_setIndex($$$$) # Set an indexed field to a specified value | ||||||||||||||||||||||||||||
| 159 | 0 | ▶ | {my ($node, $index, $field, $value) = @_; # Node, index, field name, value | ||||||||||||||||||||||||||
|
Subroutine
Node_setIndex: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 160 | 0 | my $F = Mov [$node, $Node->address($field), 'Node']; # Fields | |||||||||||||||||||||||||||
| 161 | 0 | 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 | 0 | ▶ | {my ($node, $index) = @_; # Node, index of key | ||||||||||||||||||||||||||
|
Subroutine
Node_keys: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 166 | 0 | Node_getIndex($node, $index, q(keys)); # Keys | |||||||||||||||||||||||||||
| 167 | } | ||||||||||||||||||||||||||||
| 168 | |||||||||||||||||||||||||||||
| 169 | my sub Node_data($$) # Get the indexed data from a node | ||||||||||||||||||||||||||||
| 170 | 0 | ▶ | {my ($node, $index) = @_; # Node, index of data | ||||||||||||||||||||||||||
|
Subroutine
Node_data: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 171 | 0 | Node_getIndex($node, $index, q(data)); # Data | |||||||||||||||||||||||||||
| 172 | } | ||||||||||||||||||||||||||||
| 173 | |||||||||||||||||||||||||||||
| 174 | my sub Node_down($$) # Get the indexed child node from a node | ||||||||||||||||||||||||||||
| 175 | 0 | ▶ | {my ($node, $index) = @_; # Node, index of child | ||||||||||||||||||||||||||
|
Subroutine
Node_down: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 176 | 0 | 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 | 0 | ▶ | {my ($node) = @_; # Node | ||||||||||||||||||||||||||
|
Subroutine
Node_isLeaf: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 181 | 0 | 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 | 0 | ▶ | {my ($node, $index, $value) = @_; # Node, index, value | ||||||||||||||||||||||||||
|
Subroutine
Node_setKeys: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 186 | 0 | Node_setIndex($node, $index, q(keys), $value) # Set indexed key | |||||||||||||||||||||||||||
| 187 | } | ||||||||||||||||||||||||||||
| 188 | |||||||||||||||||||||||||||||
| 189 | my sub Node_setData($$$) # Set a data field by index | ||||||||||||||||||||||||||||
| 190 | 0 | ▶ | {my ($node, $index, $value) = @_; # Node, index, value | ||||||||||||||||||||||||||
|
Subroutine
Node_setData: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 191 | 0 | Node_setIndex($node, $index, q(data), $value) # Set indexed key | |||||||||||||||||||||||||||
| 192 | } | ||||||||||||||||||||||||||||
| 193 | |||||||||||||||||||||||||||||
| 194 | my sub Node_setDown($$$) # Set a child by index | ||||||||||||||||||||||||||||
| 195 | 0 | ▶ | {my ($node, $index, $value) = @_; # Node, index, value | ||||||||||||||||||||||||||
|
Subroutine
Node_setDown: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 196 | 0 | 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 | 0 | ▶ | {my ($tree, %options) = @_; # Tree node is being created in, options | ||||||||||||||||||||||||||
|
Subroutine
Node_new: not called CC=2 SCAR=17.9
| |||||||||||||||||||||||||||||
| 201 | 0 | my $n = Array "Node"; # Allocate node | |||||||||||||||||||||||||||
| 202 | 0 | my $k = Array "Keys"; # Allocate keys | |||||||||||||||||||||||||||
| 203 | 0 | my $d = Array "Data"; # Allocate data | |||||||||||||||||||||||||||
| 204 | |||||||||||||||||||||||||||||
| 205 | 0 | ▶ | Node_setLength $n, $options{length} // 0; # Length | ||||||||||||||||||||||||||
|
Condition0%0/2
$options{"length"} // 0
MC/DC0%0/1
$options{"length"} // 0
$options{"length"}
Truth table0%0/2
A
A= $options{"length"}
| |||||||||||||||||||||||||||||
| 206 | |||||||||||||||||||||||||||||
| 207 | 0 | Node_setUp $n, 0; # Parent | |||||||||||||||||||||||||||
| 208 | |||||||||||||||||||||||||||||
| 209 | 0 | Mov [$n, $Node->address(q(keys)), 'Node'], $k; # Keys area | |||||||||||||||||||||||||||
| 210 | 0 | Mov [$n, $Node->address(q(data)), 'Node'], $d; # Data area | |||||||||||||||||||||||||||
| 211 | 0 | Mov [$n, $Node->address(q(down)), 'Node'], 0; # Down area | |||||||||||||||||||||||||||
| 212 | 0 | Mov [$n, $Node->address(q(tree)), 'Node'], $tree; # Containing tree | |||||||||||||||||||||||||||
| 213 | 0 | incNodes($tree); | |||||||||||||||||||||||||||
| 214 | 0 | Mov [$n, $Node->address(q(id)), 'Node'], # Assign an id to this node within the tree | |||||||||||||||||||||||||||
| 215 | [$tree, $Tree->address(q(nodes)), 'Tree']; | ||||||||||||||||||||||||||||
| 216 | 0 | my $N = maximumNumberOfKeys($tree); # Get the maximum number of keys per node for a tree | |||||||||||||||||||||||||||
| 217 | 0 | $n # Return reference to new node | |||||||||||||||||||||||||||
| 218 | } | ||||||||||||||||||||||||||||
| 219 | |||||||||||||||||||||||||||||
| 220 | my sub Node_allocDown($%) # Upgrade a leaf node to an internal node | ||||||||||||||||||||||||||||
| 221 | 0 | ▶ | {my ($node, %options) = @_; # Node to upgrade, options | ||||||||||||||||||||||||||
|
Subroutine
Node_allocDown: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 222 | 0 | my $d = Array "Down"; # Allocate down | |||||||||||||||||||||||||||
| 223 | 0 | 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 | 0 | ▶ | {my ($findResult, $field) = @_; # Find result, name of field | ||||||||||||||||||||||||||
|
Subroutine
FindResult_getField: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 228 | 0 | Mov [$findResult, $FindResult->address($field), q(FindResult)]; # Fields | |||||||||||||||||||||||||||
| 229 | } | ||||||||||||||||||||||||||||
| 230 | |||||||||||||||||||||||||||||
| 231 | sub FindResult_key($) # Get key from find result.. | ||||||||||||||||||||||||||||
| 232 | 0 | ▶ | {my ($f) = @_; # Find result | ||||||||||||||||||||||||||
|
Subroutine
FindResult_key: not called CC=1 SCAR=6.9
Pod
undocumented
| |||||||||||||||||||||||||||||
| 233 | 0 | FindResult_getField($f, q(key)) # Key | |||||||||||||||||||||||||||
| 234 | } | ||||||||||||||||||||||||||||
| 235 | |||||||||||||||||||||||||||||
| 236 | sub FindResult_cmp($) # Get comparison from find result.. | ||||||||||||||||||||||||||||
| 237 | 0 | ▶ | {my ($f) = @_; # Find result | ||||||||||||||||||||||||||
|
Subroutine
FindResult_cmp: not called CC=1 SCAR=6.9
Pod
undocumented
| |||||||||||||||||||||||||||||
| 238 | 0 | FindResult_getField($f, q(cmp)) # Comparison | |||||||||||||||||||||||||||
| 239 | } | ||||||||||||||||||||||||||||
| 240 | |||||||||||||||||||||||||||||
| 241 | my sub FindResult_index($) # Get index from find result | ||||||||||||||||||||||||||||
| 242 | 0 | ▶ | {my ($f) = @_; # Find result | ||||||||||||||||||||||||||
|
Subroutine
FindResult_index: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 243 | 0 | FindResult_getField($f, q(index)) # Index | |||||||||||||||||||||||||||
| 244 | } | ||||||||||||||||||||||||||||
| 245 | |||||||||||||||||||||||||||||
| 246 | my sub FindResult_node($) # Get node from find result | ||||||||||||||||||||||||||||
| 247 | 0 | ▶ | {my ($f) = @_; # Find result | ||||||||||||||||||||||||||
|
Subroutine
FindResult_node: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 248 | 0 | FindResult_getField($f, q(node)) # Node | |||||||||||||||||||||||||||
| 249 | } | ||||||||||||||||||||||||||||
| 250 | |||||||||||||||||||||||||||||
| 251 | sub FindResult_data($) # Get data field from find results.. | ||||||||||||||||||||||||||||
| 252 | 0 | ▶ | {my ($f) = @_; # Find result | ||||||||||||||||||||||||||
|
Subroutine
FindResult_data: not called CC=1 SCAR=6.9
Pod
undocumented
| |||||||||||||||||||||||||||||
| 253 | |||||||||||||||||||||||||||||
| 254 | 0 | my $n = FindResult_node ($f); | |||||||||||||||||||||||||||
| 255 | 0 | my $i = FindResult_index($f); | |||||||||||||||||||||||||||
| 256 | 0 | my $d = Node_data($n, $i); | |||||||||||||||||||||||||||
| 257 | 0 | $d | |||||||||||||||||||||||||||
| 258 | } | ||||||||||||||||||||||||||||
| 259 | |||||||||||||||||||||||||||||
| 260 | my sub FindComparison($$) # Convert a symbolic name for a find result comparison to an integer | ||||||||||||||||||||||||||||
| 261 | 0 | ▶ | {my ($f, $cmp) = @_; # Find result, comparison result name | ||||||||||||||||||||||||||
|
Subroutine
FindComparison: not called CC=5 SCAR=34.0
| |||||||||||||||||||||||||||||
| 262 | 0 | ▶ | return 0 if $cmp eq q(lower); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 263 | 0 | ▶ | return 1 if $cmp eq q(equal); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 264 | 0 | ▶ | return 2 if $cmp eq q(higher); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 265 | 0 | ▶ | return 3 if $cmp eq q(notFound); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 266 | } | ||||||||||||||||||||||||||||
| 267 | |||||||||||||||||||||||||||||
| 268 | my sub Node_open($$$$$) # Open a gap in an interior node | ||||||||||||||||||||||||||||
| 269 | 0 | ▶ | {my ($node, $offset, $length, $K, $D) = @_; # Node | ||||||||||||||||||||||||||
|
Subroutine
Node_open: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 270 | |||||||||||||||||||||||||||||
| 271 | 0 | my $k = Mov [$node, \$Node->offset(qw(keys)), 'Node']; | |||||||||||||||||||||||||||
| 272 | 0 | my $d = Mov [$node, \$Node->offset(qw(data)), 'Node']; | |||||||||||||||||||||||||||
| 273 | 0 | my $n = Mov [$node, \$Node->offset(qw(down)), 'Node']; | |||||||||||||||||||||||||||
| 274 | |||||||||||||||||||||||||||||
| 275 | 0 | ShiftUp [$k, \$offset, 'Keys'], $K; | |||||||||||||||||||||||||||
| 276 | 0 | ShiftUp [$d, \$offset, 'Data'], $D; | |||||||||||||||||||||||||||
| 277 | 0 | my $o1 = Add $offset, 1; | |||||||||||||||||||||||||||
| 278 | 0 | ShiftUp [$n, \$o1, 'Down'], 0; | |||||||||||||||||||||||||||
| 279 | 0 | Node_incLength $node; | |||||||||||||||||||||||||||
| 280 | } | ||||||||||||||||||||||||||||
| 281 | |||||||||||||||||||||||||||||
| 282 | my sub Node_openLeaf($$$$$) # Open a gap in a leaf node | ||||||||||||||||||||||||||||
| 283 | 0 | ▶ | {my ($node, $offset, $length, $K, $D) = @_; # Node | ||||||||||||||||||||||||||
|
Subroutine
Node_openLeaf: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 284 | |||||||||||||||||||||||||||||
| 285 | 0 | my $k = Mov [$node, \$Node->offset(qw(keys)), 'Node']; | |||||||||||||||||||||||||||
| 286 | 0 | my $d = Mov [$node, \$Node->offset(qw(data)), 'Node']; | |||||||||||||||||||||||||||
| 287 | |||||||||||||||||||||||||||||
| 288 | 0 | ShiftUp [$k, \$offset, 'Keys'], $K; | |||||||||||||||||||||||||||
| 289 | 0 | ShiftUp [$d, \$offset, 'Data'], $D; | |||||||||||||||||||||||||||
| 290 | 0 | Node_incLength $node; | |||||||||||||||||||||||||||
| 291 | } | ||||||||||||||||||||||||||||
| 292 | |||||||||||||||||||||||||||||
| 293 | my sub Node_copy($$$$$) # Copy part of one interior node into another node. | ||||||||||||||||||||||||||||
| 294 | 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
| |||||||||||||||||||||||||||||
| 295 | |||||||||||||||||||||||||||||
| 296 | For # Each key, data, down | ||||||||||||||||||||||||||||
| 297 | 0 | ▶ | {my ($i, $check, $next, $end) = @_; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 298 | 0 | my $S = Add $so, $i; | |||||||||||||||||||||||||||
| 299 | 0 | my $T = Add $to, $i; | |||||||||||||||||||||||||||
| 300 | |||||||||||||||||||||||||||||
| 301 | 0 | my $k = Node_keys ($s, $S); | |||||||||||||||||||||||||||
| 302 | 0 | my $d = Node_data ($s, $S); | |||||||||||||||||||||||||||
| 303 | 0 | my $n = Node_down ($s, $S); | |||||||||||||||||||||||||||
| 304 | 0 | Node_setKeys($t, $T, $k); | |||||||||||||||||||||||||||
| 305 | 0 | Node_setData($t, $T, $d); | |||||||||||||||||||||||||||
| 306 | 0 | Node_setDown($t, $T, $n); | |||||||||||||||||||||||||||
| 307 | 0 | } $length; | |||||||||||||||||||||||||||
| 308 | |||||||||||||||||||||||||||||
| 309 | 0 | my $S = Add $so, $length; | |||||||||||||||||||||||||||
| 310 | 0 | my $T = Add $to, $length; | |||||||||||||||||||||||||||
| 311 | |||||||||||||||||||||||||||||
| 312 | 0 | my $n = Node_down($s, $S); | |||||||||||||||||||||||||||
| 313 | 0 | Node_setDown($t, $T, $n); | |||||||||||||||||||||||||||
| 314 | } | ||||||||||||||||||||||||||||
| 315 | |||||||||||||||||||||||||||||
| 316 | my sub Node_copy_leaf($$$$$) # Copy part of one leaf node into another node. | ||||||||||||||||||||||||||||
| 317 | 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
| |||||||||||||||||||||||||||||
| 318 | |||||||||||||||||||||||||||||
| 319 | For # Each key, data, down | ||||||||||||||||||||||||||||
| 320 | 0 | ▶ | {my ($i, $check, $next, $end) = @_; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 321 | 0 | my $S = Add $so, $i; | |||||||||||||||||||||||||||
| 322 | 0 | my $T = Add $to, $i; | |||||||||||||||||||||||||||
| 323 | |||||||||||||||||||||||||||||
| 324 | 0 | my $k = Node_keys ($s, $S); | |||||||||||||||||||||||||||
| 325 | 0 | my $d = Node_data ($s, $S); | |||||||||||||||||||||||||||
| 326 | 0 | Node_setKeys($t, $T, $k); | |||||||||||||||||||||||||||
| 327 | 0 | Node_setData($t, $T, $d); | |||||||||||||||||||||||||||
| 328 | 0 | } $length; | |||||||||||||||||||||||||||
| 329 | } | ||||||||||||||||||||||||||||
| 330 | |||||||||||||||||||||||||||||
| 331 | my sub Node_free($) # Free a node | ||||||||||||||||||||||||||||
| 332 | 0 | ▶ | {my ($node) = @_; # Node to free | ||||||||||||||||||||||||||
|
Subroutine
Node_free: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 333 | IfFalse Node_isLeaf($node), | ||||||||||||||||||||||||||||
| 334 | Then | ||||||||||||||||||||||||||||
| 335 | 0 | ▶ | {my $K = Mov [$node, $Node->address(q(keys)), 'Node']; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 336 | 0 | my $D = Mov [$node, $Node->address(q(data)), 'Node']; | |||||||||||||||||||||||||||
| 337 | 0 | my $N = Mov [$node, $Node->address(q(down)), 'Node']; | |||||||||||||||||||||||||||
| 338 | 0 | Free $K, "Keys"; | |||||||||||||||||||||||||||
| 339 | 0 | Free $D, "Data"; | |||||||||||||||||||||||||||
| 340 | 0 | Free $N, "Down"; | |||||||||||||||||||||||||||
| 341 | 0 | }; | |||||||||||||||||||||||||||
| 342 | 0 | Free $node, "Node"; | |||||||||||||||||||||||||||
| 343 | } | ||||||||||||||||||||||||||||
| 344 | |||||||||||||||||||||||||||||
| 345 | my sub FindResult_new($$$$) # New find result on stack | ||||||||||||||||||||||||||||
| 346 | 0 | ▶ | {my ($node, $key, $cmp, $index) = @_; # Node,search key, comparison result, index | ||||||||||||||||||||||||||
|
Subroutine
FindResult_new: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 347 | 0 | my $f = Array "FindResult"; # Find result | |||||||||||||||||||||||||||
| 348 | |||||||||||||||||||||||||||||
| 349 | 0 | Mov [$f, $FindResult->address(q(node)) , 'FindResult'], $node; | |||||||||||||||||||||||||||
| 350 | 0 | Mov [$f, $FindResult->address(q(key)) , 'FindResult'], $key; | |||||||||||||||||||||||||||
| 351 | 0 | Mov [$f, $FindResult->address(q(cmp)) , 'FindResult'], $cmp; | |||||||||||||||||||||||||||
| 352 | 0 | Mov [$f, $FindResult->address(q(index)), 'FindResult'], $index; | |||||||||||||||||||||||||||
| 353 | 0 | $f | |||||||||||||||||||||||||||
| 354 | } | ||||||||||||||||||||||||||||
| 355 | |||||||||||||||||||||||||||||
| 356 | my sub ReUp($) # Reconnect the children to their new parent. | ||||||||||||||||||||||||||||
| 357 | 0 | ▶ | {my ($node) = @_; # Parameters | ||||||||||||||||||||||||||
|
Subroutine
ReUp: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 358 | 0 | my $l = Node_length($node); | |||||||||||||||||||||||||||
| 359 | 0 | my $L = Add $l, 1; | |||||||||||||||||||||||||||
| 360 | |||||||||||||||||||||||||||||
| 361 | For | ||||||||||||||||||||||||||||
| 362 | 0 | ▶ | {my ($i, $check, $next, $end) = @_; # Parameters | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 363 | 0 | my $d = Node_down ($node, $i); | |||||||||||||||||||||||||||
| 364 | 0 | Node_setUp($d, $node); | |||||||||||||||||||||||||||
| 365 | 0 | } $L; | |||||||||||||||||||||||||||
| 366 | } | ||||||||||||||||||||||||||||
| 367 | |||||||||||||||||||||||||||||
| 368 | my sub Node_indexInParent # Get the index of a node in its parent. | ||||||||||||||||||||||||||||
| 369 | 0 | ▶ | {my ($node) = @_; # Node | ||||||||||||||||||||||||||
|
Subroutine
Node_indexInParent: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 370 | 0 | my $p = Node_up($node); | |||||||||||||||||||||||||||
| 371 | 0 | AssertNe($p, 0); # Number of children as opposed to the number of keys | |||||||||||||||||||||||||||
| 372 | 0 | my $l = Node_length($p); | |||||||||||||||||||||||||||
| 373 | 0 | AssertNe($l, 0); # Number of children as opposed to the number of keys | |||||||||||||||||||||||||||
| 374 | 0 | my $L = Add $l, 1; | |||||||||||||||||||||||||||
| 375 | 0 | my $r = Var; # Index of child | |||||||||||||||||||||||||||
| 376 | |||||||||||||||||||||||||||||
| 377 | Block | ||||||||||||||||||||||||||||
| 378 | 0 | ▶ | {my ($Start, $Good, $Bad, $End) = @_; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 379 | For # Loop through each child looking for the one specified | ||||||||||||||||||||||||||||
| 380 | 0 | ▶ | {my ($i, $check, $next, $end) = @_; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 381 | IfEq Node_down($p, $i), $node, | ||||||||||||||||||||||||||||
| 382 | Then | ||||||||||||||||||||||||||||
| 383 | 0 | ▶ | {Mov $r, $i; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 384 | 0 | Jmp $End; | |||||||||||||||||||||||||||
| 385 | 0 | }; | |||||||||||||||||||||||||||
| 386 | 0 | } $L; | |||||||||||||||||||||||||||
| 387 | 0 | Assert; # Something has gone seriously wrong if we cannot find the node within its parent | |||||||||||||||||||||||||||
| 388 | 0 | }; | |||||||||||||||||||||||||||
| 389 | 0 | $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 | 0 | ▶ | {my ($node) = @_; # Node to split | ||||||||||||||||||||||||||
|
Subroutine
Node_SplitIfFull: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 394 | 0 | my $nl = Node_length($node); | |||||||||||||||||||||||||||
| 395 | 0 | my $t = Node_tree($node); # Associated tree | |||||||||||||||||||||||||||
| 396 | 0 | my $m = maximumNumberOfKeys($t); | |||||||||||||||||||||||||||
| 397 | 0 | my $split = Var; | |||||||||||||||||||||||||||
| 398 | |||||||||||||||||||||||||||||
| 399 | Block # Various splitting scenarios | ||||||||||||||||||||||||||||
| 400 | 0 | ▶ | {my ($start, $good, $bad, $end) = @_; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 401 | 0 | Jlt $bad, $nl, $m; # Must be a full node | |||||||||||||||||||||||||||
| 402 | |||||||||||||||||||||||||||||
| 403 | 0 | my $N = maximumNumberOfKeys($t); # Split points | |||||||||||||||||||||||||||
| 404 | 0 | my $n = Mov $N; # Copy | |||||||||||||||||||||||||||
| 405 | 0 | ShiftRight $n, 1; # Index of key that will be placed in parent | |||||||||||||||||||||||||||
| 406 | |||||||||||||||||||||||||||||
| 407 | 0 | my $L = Add $n, 1; | |||||||||||||||||||||||||||
| 408 | 0 | my $R = Subtract $N, $L; | |||||||||||||||||||||||||||
| 409 | |||||||||||||||||||||||||||||
| 410 | 0 | my $l = Node_new($t, length=>$n); # New child nodes | |||||||||||||||||||||||||||
| 411 | 0 | my $r = Node_new($t, length=>$R); | |||||||||||||||||||||||||||
| 412 | |||||||||||||||||||||||||||||
| 413 | IfFalse Node_isLeaf($node), # Not a leaf | ||||||||||||||||||||||||||||
| 414 | Then | ||||||||||||||||||||||||||||
| 415 | 0 | ▶ | {Node_allocDown $l; # Add down area on left | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 416 | 0 | Node_allocDown $r; # Add down area on right | |||||||||||||||||||||||||||
| 417 | 0 | Node_copy($l, $node, 0, 0, $n); # New left node | |||||||||||||||||||||||||||
| 418 | 0 | Node_copy($r, $node, 0, $L, $R); # New right node | |||||||||||||||||||||||||||
| 419 | 0 | ReUp($l); | |||||||||||||||||||||||||||
| 420 | 0 | ReUp($r); | |||||||||||||||||||||||||||
| 421 | }, | ||||||||||||||||||||||||||||
| 422 | Else | ||||||||||||||||||||||||||||
| 423 | 0 | ▶ | {Node_allocDown $node; # Add down area | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 424 | 0 | Node_copy_leaf($l, $node, 0, 0, $n); # New left leaf | |||||||||||||||||||||||||||
| 425 | 0 | Node_copy_leaf($r, $node, 0, $L, $R); # New right leaf | |||||||||||||||||||||||||||
| 426 | 0 | }; | |||||||||||||||||||||||||||
| 427 | |||||||||||||||||||||||||||||
| 428 | 0 | my $p = Node_up($node); # Existing parent node | |||||||||||||||||||||||||||
| 429 | IfTrue $p, | ||||||||||||||||||||||||||||
| 430 | Then # Not a root node | ||||||||||||||||||||||||||||
| 431 | 0 | ▶ | {my $pl = Node_length($p); | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 432 | 0 | Node_setUp($l, $p); # Connect children to parent | |||||||||||||||||||||||||||
| 433 | 0 | Node_setUp($r, $p); | |||||||||||||||||||||||||||
| 434 | |||||||||||||||||||||||||||||
| 435 | IfEq Node_down($p, 0), $node, | ||||||||||||||||||||||||||||
| 436 | Then # Splitting the first child - move everything up | ||||||||||||||||||||||||||||
| 437 | 0 | ▶ | {my $nk = Node_keys($node, $n); | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 438 | 0 | my $nd = Node_data($node, $n); | |||||||||||||||||||||||||||
| 439 | 0 | Node_open ($p, 0, $pl, $nk, $nd); | |||||||||||||||||||||||||||
| 440 | 0 | Node_setDown($p, 0, $l); | |||||||||||||||||||||||||||
| 441 | 0 | Node_setDown($p, 1, $r); | |||||||||||||||||||||||||||
| 442 | 0 | Node_free($node); | |||||||||||||||||||||||||||
| 443 | 0 | Jmp $good; | |||||||||||||||||||||||||||
| 444 | 0 | }; | |||||||||||||||||||||||||||
| 445 | |||||||||||||||||||||||||||||
| 446 | IfEq Node_down($p, $pl), $node, # Splitting the last child - just add it on the end | ||||||||||||||||||||||||||||
| 447 | Then | ||||||||||||||||||||||||||||
| 448 | 0 | ▶ | {my $pk = Node_keys($node, $n); | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 449 | 0 | my $pd = Node_data($node, $n); | |||||||||||||||||||||||||||
| 450 | 0 | Node_setKeys ($p, $pl, $pk); | |||||||||||||||||||||||||||
| 451 | 0 | Node_setDown ($p, $pl, $l); | |||||||||||||||||||||||||||
| 452 | 0 | my $nd = Node_data($node, $n); | |||||||||||||||||||||||||||
| 453 | 0 | Node_setData ($p, $pl, $nd); | |||||||||||||||||||||||||||
| 454 | 0 | my $pl1 = Add $pl, 1; | |||||||||||||||||||||||||||
| 455 | 0 | Node_setLength($p, $pl1); | |||||||||||||||||||||||||||
| 456 | 0 | Node_setDown ($p, $pl1, $r); | |||||||||||||||||||||||||||
| 457 | 0 | Node_free ($node); | |||||||||||||||||||||||||||
| 458 | 0 | Jmp $good; | |||||||||||||||||||||||||||
| 459 | 0 | }; | |||||||||||||||||||||||||||
| 460 | |||||||||||||||||||||||||||||
| 461 | For # Splitting a middle child: | ||||||||||||||||||||||||||||
| 462 | 0 | ▶ | {my ($i) = @_; # Child index | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 463 | IfEq Node_down($p, $i), $node, # Find the node that points from the parent to the current node | ||||||||||||||||||||||||||||
| 464 | Then | ||||||||||||||||||||||||||||
| 465 | 0 | ▶ | {my $pli = Subtract $pl, $i; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 466 | 0 | my $pk = Node_keys($node, $n); | |||||||||||||||||||||||||||
| 467 | 0 | my $pd = Node_data($node, $n); | |||||||||||||||||||||||||||
| 468 | 0 | Node_open ($p, $i, $pli, $pk, $pd); | |||||||||||||||||||||||||||
| 469 | 0 | Node_setDown ($p, $i, $l); | |||||||||||||||||||||||||||
| 470 | 0 | my $i1 = Add $i, 1; | |||||||||||||||||||||||||||
| 471 | 0 | Node_setDown ($p, $i1, $r); | |||||||||||||||||||||||||||
| 472 | 0 | Node_free ($node); | |||||||||||||||||||||||||||
| 473 | 0 | Jmp $good; | |||||||||||||||||||||||||||
| 474 | 0 | }; | |||||||||||||||||||||||||||
| 475 | 0 | } [1, $pl]; | |||||||||||||||||||||||||||
| 476 | 0 | Assert; # Could not find the child in the parent | |||||||||||||||||||||||||||
| 477 | 0 | }; | |||||||||||||||||||||||||||
| 478 | |||||||||||||||||||||||||||||
| 479 | 0 | Node_setUp($l, $node); # Root node with single key after split | |||||||||||||||||||||||||||
| 480 | 0 | Node_setUp($r, $node); # Connect children to parent | |||||||||||||||||||||||||||
| 481 | |||||||||||||||||||||||||||||
| 482 | 0 | my $pk = Node_keys($node, $n); # Single key | |||||||||||||||||||||||||||
| 483 | 0 | my $pd = Node_data($node, $n); # Data associated with single key | |||||||||||||||||||||||||||
| 484 | 0 | Node_setKeys ($node, 0, $pk); | |||||||||||||||||||||||||||
| 485 | 0 | Node_setData ($node, 0, $pd); | |||||||||||||||||||||||||||
| 486 | 0 | Node_setDown ($node, 0, $l); | |||||||||||||||||||||||||||
| 487 | 0 | Node_setDown ($node, 1, $r); | |||||||||||||||||||||||||||
| 488 | 0 | Node_setLength($node, 1); | |||||||||||||||||||||||||||
| 489 | |||||||||||||||||||||||||||||
| 490 | 0 | if (1) # Resize split node | |||||||||||||||||||||||||||
| 491 | 0 | {my $K = Mov [$node, $Node->address(q(keys)), 'Node']; | |||||||||||||||||||||||||||
| 492 | 0 | my $D = Mov [$node, $Node->address(q(data)), 'Node']; | |||||||||||||||||||||||||||
| 493 | 0 | my $N = Mov [$node, $Node->address(q(down)), 'Node']; | |||||||||||||||||||||||||||
| 494 | 0 | Resize $K, 1; | |||||||||||||||||||||||||||
| 495 | 0 | Resize $D, 1; | |||||||||||||||||||||||||||
| 496 | 0 | Resize $N, 2; | |||||||||||||||||||||||||||
| 497 | } | ||||||||||||||||||||||||||||
| 498 | |||||||||||||||||||||||||||||
| 499 | 0 | Jmp $good; | |||||||||||||||||||||||||||
| 500 | } | ||||||||||||||||||||||||||||
| 501 | Good # Node was split | ||||||||||||||||||||||||||||
| 502 | 0 | ▶ | {Mov $split, 1; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 503 | }, | ||||||||||||||||||||||||||||
| 504 | Bad # Node was to small to split | ||||||||||||||||||||||||||||
| 505 | 0 | ▶ | {Mov $split, 0; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 506 | 0 | }; | |||||||||||||||||||||||||||
| 507 | 0 | $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 | 0 | ▶ | {my ($tree, $key) = @_; # Parameters (NWayTree(Tree) * const tree, # Tree to search | ||||||||||||||||||||||||||
|
Subroutine
FindAndSplit: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 514 | 0 | my $node = root($tree); | |||||||||||||||||||||||||||
| 515 | |||||||||||||||||||||||||||||
| 516 | 0 | Node_SplitIfFull($node); # Split the root node if necessary | |||||||||||||||||||||||||||
| 517 | 0 | my $F = Var; | |||||||||||||||||||||||||||
| 518 | |||||||||||||||||||||||||||||
| 519 | Block # Exit this block when we have located the key | ||||||||||||||||||||||||||||
| 520 | 0 | ▶ | {my ($Start, $Good, $Bad, $Found) = @_; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 521 | |||||||||||||||||||||||||||||
| 522 | For # Step down through the tree | ||||||||||||||||||||||||||||
| 523 | 0 | ▶ | {my ($j, $check, $next, $end) = @_; # Parameters | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 524 | 0 | my $nl = Node_length($node); # Length of node | |||||||||||||||||||||||||||
| 525 | 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. | |||||||||||||||||||||||||||
| 526 | IfGt $key, Node_keys($node, $last), # Key greater than greatest key | ||||||||||||||||||||||||||||
| 527 | Then | ||||||||||||||||||||||||||||
| 528 | {IfTrue Node_isLeaf($node), # Leaf | ||||||||||||||||||||||||||||
| 529 | Then | ||||||||||||||||||||||||||||
| 530 | 0 | ▶ | {Mov $F, FindResult_new($node, $key, FindComparison_higher, $last); | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 531 | 0 | Jmp $Found; | |||||||||||||||||||||||||||
| 532 | 0 | ▶ | }; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 533 | 0 | my $last1 = Add $last, 1; | |||||||||||||||||||||||||||
| 534 | 0 | 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 | 0 | ▶ | {Mov $node, $n; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 538 | 0 | }; | |||||||||||||||||||||||||||
| 539 | 0 | Jmp $next; | |||||||||||||||||||||||||||
| 540 | 0 | }; | |||||||||||||||||||||||||||
| 541 | |||||||||||||||||||||||||||||
| 542 | For # Search the keys in this node as greater than least key and less than largest key | ||||||||||||||||||||||||||||
| 543 | 0 | ▶ | {my ($i, $check, $next, $end) = @_; # Parameters | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 544 | 0 | 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 | 0 | ▶ | {Mov $F, FindResult_new($node, $key, FindComparison_lower, $i); | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 551 | 0 | Jmp $Found; | |||||||||||||||||||||||||||
| 552 | 0 | ▶ | }; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 553 | |||||||||||||||||||||||||||||
| 554 | 0 | 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 | 0 | ▶ | {Mov $node, $n; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 558 | 0 | }; | |||||||||||||||||||||||||||
| 559 | 0 | Jmp $end; | |||||||||||||||||||||||||||
| 560 | 0 | }; | |||||||||||||||||||||||||||
| 561 | |||||||||||||||||||||||||||||
| 562 | IfEq $key, $k, # Found key | ||||||||||||||||||||||||||||
| 563 | Then | ||||||||||||||||||||||||||||
| 564 | 0 | ▶ | {Mov $F, FindResult_new($node, $key, FindComparison_equal, $i); | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 565 | 0 | Jmp $Found; | |||||||||||||||||||||||||||
| 566 | 0 | }; | |||||||||||||||||||||||||||
| 567 | 0 | } $nl; | |||||||||||||||||||||||||||
| 568 | 0 | } MaxIterations; | |||||||||||||||||||||||||||
| 569 | 0 | Assert; # Failed to descend through the tree to the key. | |||||||||||||||||||||||||||
| 570 | 0 | }; | |||||||||||||||||||||||||||
| 571 | 0 | $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 | 0 | ▶ | {my ($tree, $key) = @_; # Tree to search, key to find | ||||||||||||||||||||||||||
|
Subroutine
Find: not called CC=1 SCAR=6.9
Pod
undocumented
| |||||||||||||||||||||||||||||
| 576 | |||||||||||||||||||||||||||||
| 577 | my $p = Procedure 'NWayTree_Find', sub | ||||||||||||||||||||||||||||
| 578 | 0 | ▶ | {my ($p) = @_; # Procedure description | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 579 | 0 | my $tree = ParamsGet 0; | |||||||||||||||||||||||||||
| 580 | 0 | my $key = ParamsGet 1; | |||||||||||||||||||||||||||
| 581 | |||||||||||||||||||||||||||||
| 582 | 0 | my $node = root($tree); # Current node we are searching | |||||||||||||||||||||||||||
| 583 | |||||||||||||||||||||||||||||
| 584 | IfFalse $node, # Empty tree | ||||||||||||||||||||||||||||
| 585 | Then | ||||||||||||||||||||||||||||
| 586 | 0 | ▶ | {ReturnPut 0, FindResult_new($node, $key, FindComparison_notFound, -1); | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 587 | 0 | Return; | |||||||||||||||||||||||||||
| 588 | 0 | }; | |||||||||||||||||||||||||||
| 589 | |||||||||||||||||||||||||||||
| 590 | For # Step down through tree | ||||||||||||||||||||||||||||
| 591 | 0 | ▶ | {my ($j, $check, $next, $end) = @_; # Parameters | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 592 | 0 | my $nl = Node_length($node); | |||||||||||||||||||||||||||
| 593 | 0 | 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 | 0 | ▶ | {ReturnPut 0, FindResult_new($node, $key, FindComparison_higher, $nl); | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 600 | 0 | Return; | |||||||||||||||||||||||||||
| 601 | 0 | ▶ | }; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 602 | 0 | Mov $node, Node_down($node, $nl); | |||||||||||||||||||||||||||
| 603 | 0 | Jmp $next; | |||||||||||||||||||||||||||
| 604 | 0 | }; | |||||||||||||||||||||||||||
| 605 | |||||||||||||||||||||||||||||
| 606 | For # Search the keys in this node as less than largest key | ||||||||||||||||||||||||||||
| 607 | 0 | ▶ | {my ($i, $check, $next, $end) = @_; # Parameters | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 608 | 0 | my $k = Node_keys($node, $i); # Key from tree | |||||||||||||||||||||||||||
| 609 | IfEq $key, $k, # Found key | ||||||||||||||||||||||||||||
| 610 | Then | ||||||||||||||||||||||||||||
| 611 | 0 | ▶ | {ReturnPut 0, FindResult_new($node, $key, FindComparison_equal, $i); | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 612 | 0 | Return; | |||||||||||||||||||||||||||
| 613 | 0 | }; | |||||||||||||||||||||||||||
| 614 | IfLt $key, $k, # Lower than current key | ||||||||||||||||||||||||||||
| 615 | Then | ||||||||||||||||||||||||||||
| 616 | {IfTrue Node_isLeaf($node), # Leaf | ||||||||||||||||||||||||||||
| 617 | Then | ||||||||||||||||||||||||||||
| 618 | 0 | ▶ | {ReturnPut 0, FindResult_new($node, $key, FindComparison_lower, $i); | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 619 | 0 | Return; | |||||||||||||||||||||||||||
| 620 | 0 | ▶ | }; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 621 | 0 | Mov $node, Node_down($node, $i); | |||||||||||||||||||||||||||
| 622 | 0 | Jmp $end; | |||||||||||||||||||||||||||
| 623 | 0 | }; | |||||||||||||||||||||||||||
| 624 | 0 | } $nl; | |||||||||||||||||||||||||||
| 625 | 0 | } MaxIterations; | |||||||||||||||||||||||||||
| 626 | 0 | Assert; | |||||||||||||||||||||||||||
| 627 | 0 | }; | |||||||||||||||||||||||||||
| 628 | |||||||||||||||||||||||||||||
| 629 | 0 | ParamsPut 0, $tree; # Set parameters and call insert procedure | |||||||||||||||||||||||||||
| 630 | 0 | ParamsPut 1, $key; | |||||||||||||||||||||||||||
| 631 | 0 | Call $p; | |||||||||||||||||||||||||||
| 632 | 0 | 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 | 0 | ▶ | {my ($tree, $key, $data, %options) = @_; # Tree, key, data | ||||||||||||||||||||||||||
|
Subroutine
Insert: not called CC=1 SCAR=6.9
Pod
undocumented
| |||||||||||||||||||||||||||||
| 639 | |||||||||||||||||||||||||||||
| 640 | my $p = Procedure 'NWayTree_Insert', sub | ||||||||||||||||||||||||||||
| 641 | 0 | ▶ | {my ($p) = @_; # Procedure description | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 642 | |||||||||||||||||||||||||||||
| 643 | Block | ||||||||||||||||||||||||||||
| 644 | 0 | ▶ | {my ($Start, $Good, $Bad, $Finish) = @_; # Parameters | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 645 | |||||||||||||||||||||||||||||
| 646 | 0 | my $tree = ParamsGet 0; | |||||||||||||||||||||||||||
| 647 | 0 | my $key = ParamsGet 1; | |||||||||||||||||||||||||||
| 648 | 0 | my $data = ParamsGet 2; | |||||||||||||||||||||||||||
| 649 | 0 | my $n = root($tree); # Root node of tree | |||||||||||||||||||||||||||
| 650 | |||||||||||||||||||||||||||||
| 651 | IfFalse $n, # Empty tree | ||||||||||||||||||||||||||||
| 652 | Then | ||||||||||||||||||||||||||||
| 653 | 0 | ▶ | {my $n = Node_new($tree, length=>1); | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 654 | 0 | Node_setKeys ($n, 0, $key); | |||||||||||||||||||||||||||
| 655 | 0 | Node_setData ($n, 0, $data); | |||||||||||||||||||||||||||
| 656 | 0 | incKeys($tree); | |||||||||||||||||||||||||||
| 657 | 0 | setRoot($tree, $n); | |||||||||||||||||||||||||||
| 658 | 0 | Jmp $Finish; | |||||||||||||||||||||||||||
| 659 | 0 | }; | |||||||||||||||||||||||||||
| 660 | |||||||||||||||||||||||||||||
| 661 | 0 | 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 | 0 | ▶ | {my ($i, $check, $next, $end) = @_; # Parameters | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 670 | 0 | my $k = Node_keys($n, $i); # Key to check | |||||||||||||||||||||||||||
| 671 | IfEq $key, $k, # Key already present | ||||||||||||||||||||||||||||
| 672 | Then | ||||||||||||||||||||||||||||
| 673 | 0 | ▶ | {Node_setData($n, $i, $data); | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 674 | 0 | Jmp $Finish; | |||||||||||||||||||||||||||
| 675 | 0 | }; | |||||||||||||||||||||||||||
| 676 | IfLt $key, $k, # We have reached the insertion point | ||||||||||||||||||||||||||||
| 677 | Then | ||||||||||||||||||||||||||||
| 678 | 0 | ▶ | {my $nli = Subtract $nl, $i; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 679 | 0 | Node_openLeaf($n, $i, $nli, $key, $data); | |||||||||||||||||||||||||||
| 680 | 0 | incKeys($tree); | |||||||||||||||||||||||||||
| 681 | 0 | Jmp $Finish; | |||||||||||||||||||||||||||
| 682 | 0 | }; | |||||||||||||||||||||||||||
| 683 | 0 | ▶ | } $nl; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 684 | 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 | |||||||||||||||||||||||||||
| 685 | 0 | Node_setData($n, $nl, $data); | |||||||||||||||||||||||||||
| 686 | 0 | my $nl1 = Add $nl, 1; | |||||||||||||||||||||||||||
| 687 | 0 | Node_setLength($n, $nl1); | |||||||||||||||||||||||||||
| 688 | 0 | incKeys($tree); | |||||||||||||||||||||||||||
| 689 | 0 | Jmp $Finish; | |||||||||||||||||||||||||||
| 690 | 0 | ▶ | }; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 691 | 0 | ▶ | }; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 692 | 0 | }; | |||||||||||||||||||||||||||
| 693 | # Insert node | ||||||||||||||||||||||||||||
| 694 | 0 | my $r = FindAndSplit($tree, $key); # Check for existing key | |||||||||||||||||||||||||||
| 695 | 0 | my $N = FindResult_node($r); | |||||||||||||||||||||||||||
| 696 | 0 | my $c = FindResult_cmp($r); | |||||||||||||||||||||||||||
| 697 | 0 | my $i = FindResult_index($r); | |||||||||||||||||||||||||||
| 698 | 0 | Free $r, "FindResult"; | |||||||||||||||||||||||||||
| 699 | |||||||||||||||||||||||||||||
| 700 | IfEq $c, FindComparison_equal, # Found an equal key whose data we can update | ||||||||||||||||||||||||||||
| 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 | |||||||||||||||||||||||||||||
| 706 | 0 | my $Nl = Node_length($N); | |||||||||||||||||||||||||||
| 707 | 0 | my $Nl1 = Add $Nl, 1; | |||||||||||||||||||||||||||
| 708 | IfEq $c, FindComparison_higher, # Found a key that is greater than the one being inserted | ||||||||||||||||||||||||||||
| 709 | Then | ||||||||||||||||||||||||||||
| 710 | 0 | ▶ | {my $i1 = Add $i, 1; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 711 | 0 | my $l = Subtract $Nl, $i1; | |||||||||||||||||||||||||||
| 712 | 0 | Node_openLeaf($N, $i1, $l, $key, $data); | |||||||||||||||||||||||||||
| 713 | }, | ||||||||||||||||||||||||||||
| 714 | Else | ||||||||||||||||||||||||||||
| 715 | 0 | ▶ | {my $l = Subtract $Nl, $i; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 716 | 0 | Node_openLeaf($N, $i, $l, $key, $data); | |||||||||||||||||||||||||||
| 717 | 0 | }; | |||||||||||||||||||||||||||
| 718 | |||||||||||||||||||||||||||||
| 719 | 0 | incKeys($tree); | |||||||||||||||||||||||||||
| 720 | 0 | Node_SplitIfFull($N); # Split if the leaf is full to force keys up the tree | |||||||||||||||||||||||||||
| 721 | 0 | }; | |||||||||||||||||||||||||||
| 722 | 0 | Return; | |||||||||||||||||||||||||||
| 723 | 0 | }; | |||||||||||||||||||||||||||
| 724 | |||||||||||||||||||||||||||||
| 725 | 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. | |||||||||||||||||||||||||||
| 726 | 0 | ParamsPut 1, $key; | |||||||||||||||||||||||||||
| 727 | 0 | ParamsPut 2, $data; | |||||||||||||||||||||||||||
| 728 | 0 | 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 | 0 | ▶ | {my ($node) = @_; # Node | ||||||||||||||||||||||||||
|
Subroutine
GoAllTheWayLeft: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 735 | 0 | my $f = Var; | |||||||||||||||||||||||||||
| 736 | |||||||||||||||||||||||||||||
| 737 | IfFalse $node, # Empty tree | ||||||||||||||||||||||||||||
| 738 | Then | ||||||||||||||||||||||||||||
| 739 | 0 | ▶ | {Mov $f, FindResult_new($node, 0, FindComparison_notFound, 0); | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 740 | }, | ||||||||||||||||||||||||||||
| 741 | Else | ||||||||||||||||||||||||||||
| 742 | {For # Step down through tree | ||||||||||||||||||||||||||||
| 743 | 0 | ▶ | {my ($i, $check, $next, $end) = @_; # Parameters | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 744 | IfTrue Node_isLeaf($node), # Reached leaf | ||||||||||||||||||||||||||||
| 745 | Then | ||||||||||||||||||||||||||||
| 746 | 0 | ▶ | {Jmp $end; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 747 | 0 | }; | |||||||||||||||||||||||||||
| 748 | 0 | Mov $node, Node_down($node, 0); | |||||||||||||||||||||||||||
| 749 | 0 | ▶ | } MaxIterations; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 750 | 0 | Mov $f, FindResult_new($node, Node_keys($node, 0), FindComparison_equal, 0);# Leaf - place us on the first key | |||||||||||||||||||||||||||
| 751 | 0 | }; | |||||||||||||||||||||||||||
| 752 | 0 | $f | |||||||||||||||||||||||||||
| 753 | } | ||||||||||||||||||||||||||||
| 754 | |||||||||||||||||||||||||||||
| 755 | my sub GoUpAndAround($) # Go up until it is possible to go right or we can go no further | ||||||||||||||||||||||||||||
| 756 | 0 | ▶ | {my ($find) = @_; # Find | ||||||||||||||||||||||||||
|
Subroutine
GoUpAndAround: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 757 | 0 | my $f = Var; | |||||||||||||||||||||||||||
| 758 | Block | ||||||||||||||||||||||||||||
| 759 | 0 | ▶ | {my ($Start, $Good, $Bad, $Finish) = @_; # Parameters | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 760 | 0 | my $node = FindResult_node($find); | |||||||||||||||||||||||||||
| 761 | |||||||||||||||||||||||||||||
| 762 | IfTrue Node_isLeaf($node), # Leaf | ||||||||||||||||||||||||||||
| 763 | Then | ||||||||||||||||||||||||||||
| 764 | 0 | ▶ | {my $I = FindResult_index($find); | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 765 | 0 | my $L = Node_length($node); | |||||||||||||||||||||||||||
| 766 | 0 | my $L1 = Subtract $L, 1; | |||||||||||||||||||||||||||
| 767 | IfLt $I, $L1, # More keys in leaf | ||||||||||||||||||||||||||||
| 768 | Then | ||||||||||||||||||||||||||||
| 769 | 0 | ▶ | {my $i = Add $I, 1; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 770 | 0 | Mov $f, FindResult_new($node, Node_keys($node, $i), | |||||||||||||||||||||||||||
| 771 | FindComparison_equal, $i); | ||||||||||||||||||||||||||||
| 772 | 0 | Jmp $Finish; | |||||||||||||||||||||||||||
| 773 | 0 | }; | |||||||||||||||||||||||||||
| 774 | |||||||||||||||||||||||||||||
| 775 | 0 | my $parent = Node_up($node); # Parent | |||||||||||||||||||||||||||
| 776 | IfTrue $parent, | ||||||||||||||||||||||||||||
| 777 | Then | ||||||||||||||||||||||||||||
| 778 | {For # Not the only node in the tree | ||||||||||||||||||||||||||||
| 779 | 0 | ▶ | {my ($j, $check, $next, $end) = @_; # Parameters | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 780 | 0 | my $i = Node_indexInParent($node); # Index in parent | |||||||||||||||||||||||||||
| 781 | |||||||||||||||||||||||||||||
| 782 | IfEq $i, Node_length($parent), # Last key - continue up | ||||||||||||||||||||||||||||
| 783 | Then | ||||||||||||||||||||||||||||
| 784 | 0 | ▶ | {Mov $node, $parent; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 785 | 0 | my $Parent = Node_up($parent); # Parent | |||||||||||||||||||||||||||
| 786 | 0 | Mov $parent, $Parent; | |||||||||||||||||||||||||||
| 787 | IfFalse $parent, | ||||||||||||||||||||||||||||
| 788 | Then | ||||||||||||||||||||||||||||
| 789 | 0 | ▶ | {Jmp $end; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 790 | 0 | }; | |||||||||||||||||||||||||||
| 791 | }, | ||||||||||||||||||||||||||||
| 792 | Else | ||||||||||||||||||||||||||||
| 793 | 0 | ▶ | {Mov $f, FindResult_new($parent, Node_keys($parent, $i), # Not the last key | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 794 | FindComparison_equal, $i); | ||||||||||||||||||||||||||||
| 795 | 0 | Jmp $Finish; | |||||||||||||||||||||||||||
| 796 | 0 | }; | |||||||||||||||||||||||||||
| 797 | 0 | ▶ | } MaxIterations; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 798 | 0 | }; | |||||||||||||||||||||||||||
| 799 | 0 | Mov $f, FindResult_new($node, 0, FindComparison_notFound, 0); # Last key of root | |||||||||||||||||||||||||||
| 800 | 0 | Jmp $Finish; | |||||||||||||||||||||||||||
| 801 | 0 | }; | |||||||||||||||||||||||||||
| 802 | |||||||||||||||||||||||||||||
| 803 | 0 | my $i = FindResult_index($find); # Not a leaf so on an interior key so we can go right then all the way left | |||||||||||||||||||||||||||
| 804 | 0 | my $I = Add $i, 1; | |||||||||||||||||||||||||||
| 805 | 0 | my $d = Node_down($node, $I); | |||||||||||||||||||||||||||
| 806 | 0 | Mov $f, GoAllTheWayLeft($d); | |||||||||||||||||||||||||||
| 807 | 0 | }; | |||||||||||||||||||||||||||
| 808 | 0 | $f | |||||||||||||||||||||||||||
| 809 | } | ||||||||||||||||||||||||||||
| 810 | |||||||||||||||||||||||||||||
| 811 | my sub IterStart($) # Start an iterator | ||||||||||||||||||||||||||||
| 812 | 0 | ▶ | {my ($tree) = @_; # Tree to iterate | ||||||||||||||||||||||||||
|
Subroutine
IterStart: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 813 | 0 | my $n = root($tree); | |||||||||||||||||||||||||||
| 814 | 0 | GoAllTheWayLeft($n); | |||||||||||||||||||||||||||
| 815 | } | ||||||||||||||||||||||||||||
| 816 | |||||||||||||||||||||||||||||
| 817 | my sub IterCheck($) # True if we can continue to iterate | ||||||||||||||||||||||||||||
| 818 | 0 | ▶ | {my ($F) = @_; # Parameters (NWayTree(FindResult) const find) # Find result of last iteration | ||||||||||||||||||||||||||
|
Subroutine
IterCheck: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 819 | 0 | my $r = Var; | |||||||||||||||||||||||||||
| 820 | IfEq FindResult_cmp($F), FindComparison_notFound, | ||||||||||||||||||||||||||||
| 821 | Then | ||||||||||||||||||||||||||||
| 822 | 0 | ▶ | {Mov $r, 0; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 823 | }, | ||||||||||||||||||||||||||||
| 824 | Else | ||||||||||||||||||||||||||||
| 825 | 0 | ▶ | {Mov $r, 1; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 826 | 0 | }; | |||||||||||||||||||||||||||
| 827 | 0 | $r | |||||||||||||||||||||||||||
| 828 | } | ||||||||||||||||||||||||||||
| 829 | |||||||||||||||||||||||||||||
| 830 | my sub IterNext($) # Next element of an iteration | ||||||||||||||||||||||||||||
| 831 | 0 | ▶ | {my ($F) = @_; # Parameters (NWayTree(FindResult) const find) # Find result of last iteration | ||||||||||||||||||||||||||
|
Subroutine
IterNext: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 832 | 0 | GoUpAndAround($F); | |||||||||||||||||||||||||||
| 833 | } | ||||||||||||||||||||||||||||
| 834 | |||||||||||||||||||||||||||||
| 835 | sub Iterate(&$) # Iterate over a tree. | ||||||||||||||||||||||||||||
| 836 | 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
| |||||||||||||||||||||||||||||
| 837 | 0 | my $f = IterStart($tree); | |||||||||||||||||||||||||||
| 838 | |||||||||||||||||||||||||||||
| 839 | For | ||||||||||||||||||||||||||||
| 840 | 0 | ▶ | {my ($i, $check, $next, $end) = @_; # Parameters | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 841 | |||||||||||||||||||||||||||||
| 842 | IfFalse IterCheck($f), | ||||||||||||||||||||||||||||
| 843 | Then | ||||||||||||||||||||||||||||
| 844 | 0 | ▶ | {Jmp $end; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 845 | 0 | }; | |||||||||||||||||||||||||||
| 846 | |||||||||||||||||||||||||||||
| 847 | 0 | &$block($f); | |||||||||||||||||||||||||||
| 848 | |||||||||||||||||||||||||||||
| 849 | 0 | my $F = Mov $f; | |||||||||||||||||||||||||||
| 850 | 0 | Mov $f, IterNext($f); | |||||||||||||||||||||||||||
| 851 | 0 | Free $F, "FindResult"; | |||||||||||||||||||||||||||
| 852 | 0 | } 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 | 0 | ▶ | {my ($memory, $node, $indent, $out, $keyNotData) = @_; | ||||||||||||||||||||||||||
|
Subroutine
printNode: not called CC=7 SCAR=40.3
| |||||||||||||||||||||||||||||
| 859 | 0 | ▶ | ref($node) =~ m(Node) or confess "Not a node: ".dump($node); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 860 | 0 | my $k = $$node[$Node->offset(q(keys))]; | |||||||||||||||||||||||||||
| 861 | 0 | my $d = $$node[$Node->offset(q(data))]; | |||||||||||||||||||||||||||
| 862 | 0 | my $n = $$node[$Node->offset(q(down))]; | |||||||||||||||||||||||||||
| 863 | |||||||||||||||||||||||||||||
| 864 | 0 | ▶ | if ($n) # Interior node | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 865 | 0 | {my $K = $$memory{$k}; | |||||||||||||||||||||||||||
| 866 | 0 | my $D = $$memory{$d}; | |||||||||||||||||||||||||||
| 867 | 0 | my $N = $$memory{$n}; | |||||||||||||||||||||||||||
| 868 | 0 | my $l = $$node[$Node->offset(q(length))]; | |||||||||||||||||||||||||||
| 869 | |||||||||||||||||||||||||||||
| 870 | 0 | for my $i(0..$l-1) | |||||||||||||||||||||||||||
| 871 | 0 | {my $c = $$memory{$$N[$i]}; # Child node | |||||||||||||||||||||||||||
| 872 | 0 | my $p = $$memory{$$c[$Node->offset(q(up))]}; | |||||||||||||||||||||||||||
| 873 | |||||||||||||||||||||||||||||
| 874 | 0 | __SUB__->($memory, $c, $indent+1, $out, $keyNotData); | |||||||||||||||||||||||||||
| 875 | 0 | ▶ | push @$out, [$indent, $keyNotData ? $$K[$i] : $$D[$i]]; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 876 | } | ||||||||||||||||||||||||||||
| 877 | |||||||||||||||||||||||||||||
| 878 | 0 | __SUB__->($memory, $$memory{$$N[$l]}, $indent+1, $out, $keyNotData); | |||||||||||||||||||||||||||
| 879 | } | ||||||||||||||||||||||||||||
| 880 | |||||||||||||||||||||||||||||
| 881 | else # Leaf node | ||||||||||||||||||||||||||||
| 882 | 0 | {my $K = $$memory{$k}; | |||||||||||||||||||||||||||
| 883 | 0 | my $D = $$memory{$d}; | |||||||||||||||||||||||||||
| 884 | 0 | my $l = $$node[$Node->offset(q(length))]; | |||||||||||||||||||||||||||
| 885 | |||||||||||||||||||||||||||||
| 886 | 0 | for my $i(0..$l-1) | |||||||||||||||||||||||||||
| 887 | 0 | {my $k = $$K[$i]; | |||||||||||||||||||||||||||
| 888 | 0 | my $d = $$D[$i]; | |||||||||||||||||||||||||||
| 889 | 0 | ▶ | push @$out, [$indent, $keyNotData ? $k : $d]; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 890 | } | ||||||||||||||||||||||||||||
| 891 | } | ||||||||||||||||||||||||||||
| 892 | 0 | $out | |||||||||||||||||||||||||||
| 893 | } | ||||||||||||||||||||||||||||
| 894 | |||||||||||||||||||||||||||||
| 895 | my sub printTree($$) # Print a tree | ||||||||||||||||||||||||||||
| 896 | 0 | ▶ | {my ($m, $keyNotData) = @_; # Memory, key or data | ||||||||||||||||||||||||||
|
Subroutine
printTree: not called CC=5 SCAR=34.0
| |||||||||||||||||||||||||||||
| 897 | 0 | my $t = $$m{1}; | |||||||||||||||||||||||||||
| 898 | 0 | my $r = $$m{$$t[$Tree->offset(q(root))]}; | |||||||||||||||||||||||||||
| 899 | 0 | my $o = printNode($m, $r, 0, [], $keyNotData); | |||||||||||||||||||||||||||
| 900 | |||||||||||||||||||||||||||||
| 901 | 0 | my $C = $#$o; # Number of columns | |||||||||||||||||||||||||||
| 902 | 0 | my $R = max(map {$$o[$_][0]} keys @$o); # Number of rows | |||||||||||||||||||||||||||
| 903 | |||||||||||||||||||||||||||||
| 904 | 0 | my $W = 3; # Field width for each key | |||||||||||||||||||||||||||
| 905 | 0 | my @o; # Output area | |||||||||||||||||||||||||||
| 906 | 0 | for my $r(0..$R) | |||||||||||||||||||||||||||
| 907 | 0 | {for my $c(0..$C) | |||||||||||||||||||||||||||
| 908 | 0 | {$o[$r][$c] = ' ' x $W; | |||||||||||||||||||||||||||
| 909 | } | ||||||||||||||||||||||||||||
| 910 | } | ||||||||||||||||||||||||||||
| 911 | |||||||||||||||||||||||||||||
| 912 | 0 | for my $p(keys @$o) # Write tree horizontally | |||||||||||||||||||||||||||
| 913 | 0 | ▶ | {next unless defined(my $v = $$o[$p][1]); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 914 | 0 | my $r = $$o[$p][0]; | |||||||||||||||||||||||||||
| 915 | 0 | my $c = $p; | |||||||||||||||||||||||||||
| 916 | |||||||||||||||||||||||||||||
| 917 | 0 | $o[$r][$c] = sprintf("%${W}d", $v); | |||||||||||||||||||||||||||
| 918 | } | ||||||||||||||||||||||||||||
| 919 | |||||||||||||||||||||||||||||
| 920 | 0 | 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 | 0 | ▶ | {my ($m) = @_; # Memory | ||||||||||||||||||||||||||
|
Subroutine
printTreeKeys: not called CC=1 SCAR=6.9
Pod
undocumented
| |||||||||||||||||||||||||||||
| 925 | 0 | printTree($m, 1); | |||||||||||||||||||||||||||
| 926 | } | ||||||||||||||||||||||||||||
| 927 | |||||||||||||||||||||||||||||
| 928 | sub printTreeData($) # Print the data held in a tree. | ||||||||||||||||||||||||||||
| 929 | 0 | ▶ | {my ($m) = @_; # Memory | ||||||||||||||||||||||||||
|
Subroutine
printTreeData: not called CC=1 SCAR=6.9
Pod
undocumented
| |||||||||||||||||||||||||||||
| 930 | 0 | printTree($m, 0); | |||||||||||||||||||||||||||
| 931 | } | ||||||||||||||||||||||||||||
| 932 | |||||||||||||||||||||||||||||
| 933 | #D1 Utilities # Utility functions. | ||||||||||||||||||||||||||||
| 934 | |||||||||||||||||||||||||||||
| 935 | sub randomArray($) # Create a random array. | ||||||||||||||||||||||||||||
| 936 | 0 | ▶ | {my ($N) = @_; # Size of array | ||||||||||||||||||||||||||
|
Subroutine
randomArray: not called CC=2 SCAR=17.9
Pod
undocumented
| |||||||||||||||||||||||||||||
| 937 | |||||||||||||||||||||||||||||
| 938 | 0 | my @r = 1..$N; | |||||||||||||||||||||||||||
| 939 | 0 | srand(1); | |||||||||||||||||||||||||||
| 940 | |||||||||||||||||||||||||||||
| 941 | 0 | for my $i(keys @r) # Disarrange the array | |||||||||||||||||||||||||||
| 942 | 0 | {my $s = int rand @r; | |||||||||||||||||||||||||||
| 943 | 0 | my $t = int rand @r; | |||||||||||||||||||||||||||
| 944 | 0 | ($r[$t], $r[$s]) = ($r[$s], $r[$t]); | |||||||||||||||||||||||||||
| 945 | } | ||||||||||||||||||||||||||||
| 946 | @r | ||||||||||||||||||||||||||||
| 947 | 0 | } | |||||||||||||||||||||||||||
| 948 | |||||||||||||||||||||||||||||
| 949 | 1 | ▶ | use Exporter qw(import); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 950 | 1 | ▶ | use vars qw(@ISA @EXPORT @EXPORT_OK %EXPORT_TAGS); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 951 | |||||||||||||||||||||||||||||
| 952 | 1 | @ISA = qw(Exporter); | |||||||||||||||||||||||||||
| 953 | 1 | @EXPORT = qw(); | |||||||||||||||||||||||||||
| 954 | 1 | @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 | 1 | %EXPORT_TAGS = (all=>[@EXPORT, @EXPORT_OK]); | |||||||||||||||||||||||||||
| 957 | |||||||||||||||||||||||||||||
| 958 | 1 | ▶ | return 1 if caller; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 959 | |||||||||||||||||||||||||||||
| 960 | #D0 Tests | ||||||||||||||||||||||||||||
| 961 | |||||||||||||||||||||||||||||
| 962 | 0 | Test::More->builder->output("/dev/null"); # Reduce number of confirmation messages during testing | |||||||||||||||||||||||||||
| 963 | |||||||||||||||||||||||||||||
| 964 | 0 | eval {goto latest}; | |||||||||||||||||||||||||||
| 965 | |||||||||||||||||||||||||||||
| 966 | sub is_deeply; | ||||||||||||||||||||||||||||
| 967 | sub ok($;$); | ||||||||||||||||||||||||||||
| 968 | sub done_testing; | ||||||||||||||||||||||||||||
| 969 | |||||||||||||||||||||||||||||
| 970 | #latest:; | ||||||||||||||||||||||||||||
| 971 | 0 | if (1) | |||||||||||||||||||||||||||
| 972 | 0 | {Start 1; | |||||||||||||||||||||||||||
| 973 | 0 | Out New(3); | |||||||||||||||||||||||||||
| 974 | 0 | my $e = Execute(suppressOutput=>1); | |||||||||||||||||||||||||||
| 975 | 0 | is_deeply $e->out, [1]; | |||||||||||||||||||||||||||
| 976 | 0 | is_deeply $e->memory, { 1 => bless([0, 0, 3, 0], "Tree") }; | |||||||||||||||||||||||||||
| 977 | } | ||||||||||||||||||||||||||||
| 978 | |||||||||||||||||||||||||||||
| 979 | #latest:; | ||||||||||||||||||||||||||||
| 980 | 0 | if (1) | |||||||||||||||||||||||||||
| 981 | 0 | {Start 1; | |||||||||||||||||||||||||||
| 982 | 0 | my $t = New(3); | |||||||||||||||||||||||||||
| 983 | 0 | my $r = root($t); | |||||||||||||||||||||||||||
| 984 | |||||||||||||||||||||||||||||
| 985 | 0 | setRoot($t, 1); | |||||||||||||||||||||||||||
| 986 | 0 | my $R = root($t); | |||||||||||||||||||||||||||
| 987 | |||||||||||||||||||||||||||||
| 988 | 0 | my $n = maximumNumberOfKeys($t); | |||||||||||||||||||||||||||
| 989 | |||||||||||||||||||||||||||||
| 990 | 0 | incKeys($t) for 1..3; | |||||||||||||||||||||||||||
| 991 | 0 | Out [$t, $Tree->address(q(keys)), 'Tree']; | |||||||||||||||||||||||||||
| 992 | |||||||||||||||||||||||||||||
| 993 | 0 | incNodes($t) for 1..5; | |||||||||||||||||||||||||||
| 994 | 0 | Out nodes($t); | |||||||||||||||||||||||||||
| 995 | |||||||||||||||||||||||||||||
| 996 | 0 | my $e = Execute(suppressOutput=>1); | |||||||||||||||||||||||||||
| 997 | 0 | is_deeply $e->out, [3, 5]; | |||||||||||||||||||||||||||
| 998 | 0 | is_deeply $e->memory, { 1 => bless([3, 5, 3, 1], "Tree") }; | |||||||||||||||||||||||||||
| 999 | } | ||||||||||||||||||||||||||||
| 1000 | |||||||||||||||||||||||||||||
| 1001 | #latest:; | ||||||||||||||||||||||||||||
| 1002 | 0 | if (1) #TNode_open | |||||||||||||||||||||||||||
| 1003 | 0 | {Start 1; | |||||||||||||||||||||||||||
| 1004 | 0 | my $t = New(7); # Create tree | |||||||||||||||||||||||||||
| 1005 | 0 | my $n = Node_new($t); # Create node | |||||||||||||||||||||||||||
| 1006 | 0 | my $e = Execute(suppressOutput=>1); | |||||||||||||||||||||||||||
| 1007 | 0 | 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 | 0 | if (1) #TNode_open | |||||||||||||||||||||||||||
| 1016 | 0 | {Start 1; | |||||||||||||||||||||||||||
| 1017 | 0 | my $N = 7; | |||||||||||||||||||||||||||
| 1018 | 0 | my $t = New($N); # Create tree | |||||||||||||||||||||||||||
| 1019 | 0 | my $n = Node_new($t); # Create node | |||||||||||||||||||||||||||
| 1020 | |||||||||||||||||||||||||||||
| 1021 | 0 | Node_allocDown $n; | |||||||||||||||||||||||||||
| 1022 | |||||||||||||||||||||||||||||
| 1023 | 0 | for my $i(0..$N-1) | |||||||||||||||||||||||||||
| 1024 | 0 | {Node_setKeys($n, $i, 1+$i); | |||||||||||||||||||||||||||
| 1025 | 0 | Node_setData($n, $i, 11+$i); | |||||||||||||||||||||||||||
| 1026 | 0 | Node_setDown($n, $i, 21+$i); | |||||||||||||||||||||||||||
| 1027 | } | ||||||||||||||||||||||||||||
| 1028 | |||||||||||||||||||||||||||||
| 1029 | 0 | Node_setDown($n, $N, 28); | |||||||||||||||||||||||||||
| 1030 | |||||||||||||||||||||||||||||
| 1031 | 0 | Node_open($n, 2, 4, 3, 13); | |||||||||||||||||||||||||||
| 1032 | 0 | my $e = Execute(suppressOutput=>1); | |||||||||||||||||||||||||||
| 1033 | |||||||||||||||||||||||||||||
| 1034 | 0 | 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 | 0 | if (1) #TNode_copy | |||||||||||||||||||||||||||
| 1044 | 0 | {Start 1; | |||||||||||||||||||||||||||
| 1045 | 0 | my $t = New(7); # Create tree | |||||||||||||||||||||||||||
| 1046 | 0 | my $p = Node_new($t); Node_allocDown($p); # Create a node | |||||||||||||||||||||||||||
| 1047 | 0 | my $q = Node_new($t); Node_allocDown($q); # Create a node | |||||||||||||||||||||||||||
| 1048 | |||||||||||||||||||||||||||||
| 1049 | 0 | for my $i(0..6) | |||||||||||||||||||||||||||
| 1050 | 0 | {Node_setKeys($p, $i, 11+$i); | |||||||||||||||||||||||||||
| 1051 | 0 | Node_setData($p, $i, 21+$i); | |||||||||||||||||||||||||||
| 1052 | 0 | Node_setDown($p, $i, 31+$i); | |||||||||||||||||||||||||||
| 1053 | 0 | Node_setKeys($q, $i, 41+$i); | |||||||||||||||||||||||||||
| 1054 | 0 | Node_setData($q, $i, 51+$i); | |||||||||||||||||||||||||||
| 1055 | 0 | Node_setDown($q, $i, 61+$i); | |||||||||||||||||||||||||||
| 1056 | } | ||||||||||||||||||||||||||||
| 1057 | |||||||||||||||||||||||||||||
| 1058 | 0 | Node_setDown($p, 7, 97); | |||||||||||||||||||||||||||
| 1059 | 0 | Node_setDown($q, 7, 99); | |||||||||||||||||||||||||||
| 1060 | |||||||||||||||||||||||||||||
| 1061 | 0 | Node_copy( $q, $p, 1, 3, 2); | |||||||||||||||||||||||||||
| 1062 | |||||||||||||||||||||||||||||
| 1063 | 0 | my $e = Execute(suppressOutput=>1); | |||||||||||||||||||||||||||
| 1064 | |||||||||||||||||||||||||||||
| 1065 | 0 | 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 | 0 | if (1) #TFindResult_new #TFindResult_cmp | |||||||||||||||||||||||||||
| 1079 | 0 | {Start 1; | |||||||||||||||||||||||||||
| 1080 | 0 | my $f = FindResult_new(1, 2, 3, 4); | |||||||||||||||||||||||||||
| 1081 | 0 | my $n = FindResult_node($f); | |||||||||||||||||||||||||||
| 1082 | 0 | my $k = FindResult_key($f); | |||||||||||||||||||||||||||
| 1083 | 0 | my $c = FindResult_cmp($f); | |||||||||||||||||||||||||||
| 1084 | 0 | my $i = FindResult_index($f); | |||||||||||||||||||||||||||
| 1085 | 0 | Out $_ for $n, $c, $k, $i; | |||||||||||||||||||||||||||
| 1086 | 0 | my $e = Execute(suppressOutput=>1); | |||||||||||||||||||||||||||
| 1087 | 0 | is_deeply $e->out, [1, 3, 2, 4]; | |||||||||||||||||||||||||||
| 1088 | 0 | is_deeply $e->memory, {1=>[1, 3, 2, 4]}; | |||||||||||||||||||||||||||
| 1089 | } | ||||||||||||||||||||||||||||
| 1090 | |||||||||||||||||||||||||||||
| 1091 | #latest:; | ||||||||||||||||||||||||||||
| 1092 | 0 | if (1) #TInsert | |||||||||||||||||||||||||||
| 1093 | 0 | {Start 1; | |||||||||||||||||||||||||||
| 1094 | 0 | my $t = New(3); # Create tree | |||||||||||||||||||||||||||
| 1095 | 0 | my $f = Find($t, 1); | |||||||||||||||||||||||||||
| 1096 | 0 | my $c = FindResult_cmp($f); | |||||||||||||||||||||||||||
| 1097 | 0 | AssertEq($c, FindComparison_notFound); | |||||||||||||||||||||||||||
| 1098 | 0 | my $e = Execute(suppressOutput=>1); | |||||||||||||||||||||||||||
| 1099 | 0 | is_deeply $e->out, []; | |||||||||||||||||||||||||||
| 1100 | } | ||||||||||||||||||||||||||||
| 1101 | |||||||||||||||||||||||||||||
| 1102 | #latest:; | ||||||||||||||||||||||||||||
| 1103 | 0 | if (1) #TInsert | |||||||||||||||||||||||||||
| 1104 | 0 | {Start 1; | |||||||||||||||||||||||||||
| 1105 | 0 | my $t = New(3); | |||||||||||||||||||||||||||
| 1106 | 0 | Insert($t, 1, 11); | |||||||||||||||||||||||||||
| 1107 | 0 | my $e = Execute(suppressOutput=>1); | |||||||||||||||||||||||||||
| 1108 | |||||||||||||||||||||||||||||
| 1109 | 0 | 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 | 0 | if (1) #TInsert | |||||||||||||||||||||||||||
| 1118 | 0 | {Start 1; | |||||||||||||||||||||||||||
| 1119 | 0 | my $t = New(3); | |||||||||||||||||||||||||||
| 1120 | 0 | Insert($t, 1, 11); | |||||||||||||||||||||||||||
| 1121 | 0 | Insert($t, 2, 22); | |||||||||||||||||||||||||||
| 1122 | 0 | my $e = Execute(suppressOutput=>1); | |||||||||||||||||||||||||||
| 1123 | |||||||||||||||||||||||||||||
| 1124 | 0 | 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 | 0 | if (1) #TInsert | |||||||||||||||||||||||||||
| 1133 | 0 | {Start 1; | |||||||||||||||||||||||||||
| 1134 | 0 | my $t = New(3); | |||||||||||||||||||||||||||
| 1135 | 0 | Insert($t, $_, "$_$_") for 1..3; | |||||||||||||||||||||||||||
| 1136 | 0 | my $e = Execute(suppressOutput=>1); | |||||||||||||||||||||||||||
| 1137 | |||||||||||||||||||||||||||||
| 1138 | 0 | 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 | 0 | if (1) #TInsert | |||||||||||||||||||||||||||
| 1147 | 0 | {Start 1; | |||||||||||||||||||||||||||
| 1148 | 0 | my $t = New(3); | |||||||||||||||||||||||||||
| 1149 | 0 | Insert($t, $_, "$_$_") for 1..4; | |||||||||||||||||||||||||||
| 1150 | 0 | my $e = Execute(suppressOutput=>1); | |||||||||||||||||||||||||||
| 1151 | |||||||||||||||||||||||||||||
| 1152 | 0 | 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 | 0 | if (1) #TInsert | |||||||||||||||||||||||||||
| 1169 | 0 | {Start 1; | |||||||||||||||||||||||||||
| 1170 | 0 | my $t = New(3); | |||||||||||||||||||||||||||
| 1171 | 0 | Insert($t, $_, "$_$_") for 1..5; | |||||||||||||||||||||||||||
| 1172 | |||||||||||||||||||||||||||||
| 1173 | 0 | my $e = Execute(suppressOutput=>1); | |||||||||||||||||||||||||||
| 1174 | |||||||||||||||||||||||||||||
| 1175 | 0 | 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 | 0 | if (1) #TInsert | |||||||||||||||||||||||||||
| 1194 | 0 | {Start 1; | |||||||||||||||||||||||||||
| 1195 | 0 | my $t = New(3); | |||||||||||||||||||||||||||
| 1196 | 0 | Insert($t, $_, "$_$_") for 1..6; | |||||||||||||||||||||||||||
| 1197 | 0 | my $e = Execute(suppressOutput=>1); | |||||||||||||||||||||||||||
| 1198 | |||||||||||||||||||||||||||||
| 1199 | 0 | 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 | 0 | if (1) #TNew #TInsert | |||||||||||||||||||||||||||
| 1218 | 0 | {my $W = 3; my $N = 66; my @r = randomArray $N; | |||||||||||||||||||||||||||
| 1219 | |||||||||||||||||||||||||||||
| 1220 | 0 | Start 1; | |||||||||||||||||||||||||||
| 1221 | 0 | my $t = New($W); | |||||||||||||||||||||||||||
| 1222 | |||||||||||||||||||||||||||||
| 1223 | 0 | for my $i(1..$N) | |||||||||||||||||||||||||||
| 1224 | 0 | {Insert($t, $r[$i-1], $r[$i-1]); | |||||||||||||||||||||||||||
| 1225 | } | ||||||||||||||||||||||||||||
| 1226 | |||||||||||||||||||||||||||||
| 1227 | 0 | my $e = Execute(suppressOutput=>1); | |||||||||||||||||||||||||||
| 1228 | 0 | 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 | 0 | if (1) # Print tree - random - 5 | |||||||||||||||||||||||||||
| 1239 | 0 | {my $W = 5; my $N = 66; my @r = randomArray $N; | |||||||||||||||||||||||||||
| 1240 | |||||||||||||||||||||||||||||
| 1241 | 0 | Start 1; | |||||||||||||||||||||||||||
| 1242 | 0 | my $t = New($W); | |||||||||||||||||||||||||||
| 1243 | |||||||||||||||||||||||||||||
| 1244 | 0 | for my $i(1..$N) | |||||||||||||||||||||||||||
| 1245 | 0 | {Insert($t, $r[$i-1], $r[$i-1]); | |||||||||||||||||||||||||||
| 1246 | } | ||||||||||||||||||||||||||||
| 1247 | |||||||||||||||||||||||||||||
| 1248 | 0 | my $e = Execute(suppressOutput=>1); | |||||||||||||||||||||||||||
| 1249 | 0 | 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 | 0 | if (1) # Print tree keys | |||||||||||||||||||||||||||
| 1258 | 0 | {my $W = 3; my $N = 65; | |||||||||||||||||||||||||||
| 1259 | |||||||||||||||||||||||||||||
| 1260 | 0 | Start 1; | |||||||||||||||||||||||||||
| 1261 | 0 | my $t = New($W); | |||||||||||||||||||||||||||
| 1262 | |||||||||||||||||||||||||||||
| 1263 | 0 | for my $i(1..$N) | |||||||||||||||||||||||||||
| 1264 | 0 | {Insert($t, $i, $i); | |||||||||||||||||||||||||||
| 1265 | } | ||||||||||||||||||||||||||||
| 1266 | |||||||||||||||||||||||||||||
| 1267 | 0 | my $e = Execute(suppressOutput=>1); | |||||||||||||||||||||||||||
| 1268 | 0 | 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 | 0 | if (1) # Print tree keys - reverse | |||||||||||||||||||||||||||
| 1279 | 0 | {my $W = 3; my $N = 65; | |||||||||||||||||||||||||||
| 1280 | |||||||||||||||||||||||||||||
| 1281 | 0 | Start 1; | |||||||||||||||||||||||||||
| 1282 | 0 | my $t = New($W); | |||||||||||||||||||||||||||
| 1283 | |||||||||||||||||||||||||||||
| 1284 | 0 | for my $i(reverse 1..$N) | |||||||||||||||||||||||||||
| 1285 | 0 | {Insert($t, $i, $i); | |||||||||||||||||||||||||||
| 1286 | } | ||||||||||||||||||||||||||||
| 1287 | |||||||||||||||||||||||||||||
| 1288 | 0 | my $e = Execute(suppressOutput=>1); | |||||||||||||||||||||||||||
| 1289 | 0 | 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 | 0 | if (1) # Print tree data | |||||||||||||||||||||||||||
| 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 data - 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 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 | 0 | if (1) # Compare trees of keys and data | |||||||||||||||||||||||||||
| 1342 | 0 | {my $W = 3; my $N = 165; my @r = randomArray $N; | |||||||||||||||||||||||||||
| 1343 | |||||||||||||||||||||||||||||
| 1344 | 0 | Start 1; | |||||||||||||||||||||||||||
| 1345 | 0 | my $t = New($W); | |||||||||||||||||||||||||||
| 1346 | |||||||||||||||||||||||||||||
| 1347 | 0 | for my $i(0..$N-1) | |||||||||||||||||||||||||||
| 1348 | 0 | {Insert($t, $r[$i], $r[$i]); | |||||||||||||||||||||||||||
| 1349 | } | ||||||||||||||||||||||||||||
| 1350 | |||||||||||||||||||||||||||||
| 1351 | 0 | my $e = Execute(suppressOutput=>1); | |||||||||||||||||||||||||||
| 1352 | 0 | is_deeply printTreeKeys($e->memory), | |||||||||||||||||||||||||||
| 1353 | printTreeData($e->memory); | ||||||||||||||||||||||||||||
| 1354 | } | ||||||||||||||||||||||||||||
| 1355 | |||||||||||||||||||||||||||||
| 1356 | #latest:; | ||||||||||||||||||||||||||||
| 1357 | 0 | if (1) #TprintTreeKeys #TprintTreeData | |||||||||||||||||||||||||||
| 1358 | 0 | {my $W = 7; my $N = 165; my @r = randomArray $N; | |||||||||||||||||||||||||||
| 1359 | |||||||||||||||||||||||||||||
| 1360 | 0 | Start 1; | |||||||||||||||||||||||||||
| 1361 | 0 | my $t = New($W); | |||||||||||||||||||||||||||
| 1362 | |||||||||||||||||||||||||||||
| 1363 | 0 | for my $i(0..$N-1) | |||||||||||||||||||||||||||
| 1364 | 0 | {Insert($t, $r[$i], $r[$i]); | |||||||||||||||||||||||||||
| 1365 | } | ||||||||||||||||||||||||||||
| 1366 | |||||||||||||||||||||||||||||
| 1367 | 0 | my $e = Execute(suppressOutput=>1); | |||||||||||||||||||||||||||
| 1368 | 0 | is_deeply printTreeKeys($e->memory), | |||||||||||||||||||||||||||
| 1369 | printTreeData($e->memory); | ||||||||||||||||||||||||||||
| 1370 | } | ||||||||||||||||||||||||||||
| 1371 | |||||||||||||||||||||||||||||
| 1372 | #latest:; | ||||||||||||||||||||||||||||
| 1373 | 0 | if (1) # Compare trees of keys and data | |||||||||||||||||||||||||||
| 1374 | 0 | {my $W = 3; my $N = 75; my @r = randomArray $N; | |||||||||||||||||||||||||||
| 1375 | |||||||||||||||||||||||||||||
| 1376 | 0 | Start 1; | |||||||||||||||||||||||||||
| 1377 | 0 | my $t = New($W); | |||||||||||||||||||||||||||
| 1378 | |||||||||||||||||||||||||||||
| 1379 | 0 | for my $i(0..$N-1) | |||||||||||||||||||||||||||
| 1380 | 0 | {Insert($t, $r[$i], $r[$i]); | |||||||||||||||||||||||||||
| 1381 | } | ||||||||||||||||||||||||||||
| 1382 | |||||||||||||||||||||||||||||
| 1383 | Iterate # Iterate tree | ||||||||||||||||||||||||||||
| 1384 | 0 | ▶ | {my ($find) = @_; # Find result | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 1385 | 0 | my $k = FindResult_key($find); | |||||||||||||||||||||||||||
| 1386 | 0 | Out $k; | |||||||||||||||||||||||||||
| 1387 | 0 | } $t; | |||||||||||||||||||||||||||
| 1388 | |||||||||||||||||||||||||||||
| 1389 | 0 | my $e = Execute(suppressOutput=>1); | |||||||||||||||||||||||||||
| 1390 | 0 | is_deeply $e->out, [1..$N]; | |||||||||||||||||||||||||||
| 1391 | } | ||||||||||||||||||||||||||||
| 1392 | |||||||||||||||||||||||||||||
| 1393 | #latest:; | ||||||||||||||||||||||||||||
| 1394 | 0 | if (1) #TrandomArray | |||||||||||||||||||||||||||
| 1395 | 0 | {my $W = 3; my $N = 76; my @r = randomArray $N; | |||||||||||||||||||||||||||
| 1396 | |||||||||||||||||||||||||||||
| 1397 | 0 | Start 1; | |||||||||||||||||||||||||||
| 1398 | 0 | my $t = New($W); | |||||||||||||||||||||||||||
| 1399 | |||||||||||||||||||||||||||||
| 1400 | 0 | for my $i(0..$N-1) | |||||||||||||||||||||||||||
| 1401 | 0 | {Insert($t, $r[$i], $r[$i]); | |||||||||||||||||||||||||||
| 1402 | } | ||||||||||||||||||||||||||||
| 1403 | |||||||||||||||||||||||||||||
| 1404 | Iterate # Iterate tree | ||||||||||||||||||||||||||||
| 1405 | 0 | ▶ | {my ($find) = @_; # Find result | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 1406 | 0 | my $k = FindResult_key($find); | |||||||||||||||||||||||||||
| 1407 | 0 | Out $k; | |||||||||||||||||||||||||||
| 1408 | 0 | } $t; | |||||||||||||||||||||||||||
| 1409 | |||||||||||||||||||||||||||||
| 1410 | 0 | my $e = Execute(suppressOutput=>1); | |||||||||||||||||||||||||||
| 1411 | 0 | is_deeply $e->out, [1..$N]; | |||||||||||||||||||||||||||
| 1412 | } | ||||||||||||||||||||||||||||
| 1413 | |||||||||||||||||||||||||||||
| 1414 | #latest:; | ||||||||||||||||||||||||||||
| 1415 | 0 | if (1) #TIterate #TKeys #TFindResult_key #TFindResult_data #TFind | |||||||||||||||||||||||||||
| 1416 | 0 | {my $W = 3; my $N = 107; my @r = randomArray $N; | |||||||||||||||||||||||||||
| 1417 | |||||||||||||||||||||||||||||
| 1418 | 0 | Start 1; | |||||||||||||||||||||||||||
| 1419 | 0 | my $t = New($W); # Create tree at expected location in memory | |||||||||||||||||||||||||||
| 1420 | |||||||||||||||||||||||||||||
| 1421 | 0 | my $a = Array "aaa"; | |||||||||||||||||||||||||||
| 1422 | 0 | for my $I(1..$N) # Load array | |||||||||||||||||||||||||||
| 1423 | 0 | {my $i = $I-1; | |||||||||||||||||||||||||||
| 1424 | 0 | Mov [$a, $i, "aaa"], $r[$i]; | |||||||||||||||||||||||||||
| 1425 | } | ||||||||||||||||||||||||||||
| 1426 | |||||||||||||||||||||||||||||
| 1427 | ForArray # Create tree | ||||||||||||||||||||||||||||
| 1428 | 0 | ▶ | {my ($i, $k) = @_; | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 1429 | 0 | my $n = Keys($t); | |||||||||||||||||||||||||||
| 1430 | 0 | AssertEq $n, $i; # Check tree size | |||||||||||||||||||||||||||
| 1431 | 0 | my $K = Add $k, $k; | |||||||||||||||||||||||||||
| 1432 | 0 | Tally 1; | |||||||||||||||||||||||||||
| 1433 | 0 | Insert($t, $k, $K); # Insert a new node | |||||||||||||||||||||||||||
| 1434 | 0 | Tally 0; | |||||||||||||||||||||||||||
| 1435 | 0 | } $a, q(aaa); | |||||||||||||||||||||||||||
| 1436 | |||||||||||||||||||||||||||||
| 1437 | Iterate # Iterate tree | ||||||||||||||||||||||||||||
| 1438 | 0 | ▶ | {my ($find) = @_; # Find result | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 1439 | 0 | my $k = FindResult_key($find); | |||||||||||||||||||||||||||
| 1440 | 0 | Out $k; | |||||||||||||||||||||||||||
| 1441 | 0 | my $f = Find($t, $k); # Find | |||||||||||||||||||||||||||
| 1442 | 0 | my $d = FindResult_data($f); | |||||||||||||||||||||||||||
| 1443 | 0 | my $K = Add $k, $k; | |||||||||||||||||||||||||||
| 1444 | 0 | AssertEq $K, $d; # Check result | |||||||||||||||||||||||||||
| 1445 | 0 | } $t; | |||||||||||||||||||||||||||
| 1446 | |||||||||||||||||||||||||||||
| 1447 | 0 | my $e = Execute(suppressOutput=>1); | |||||||||||||||||||||||||||
| 1448 | |||||||||||||||||||||||||||||
| 1449 | 0 | is_deeply $e->out, [1..$N]; # Expected sequence | |||||||||||||||||||||||||||
| 1450 | |||||||||||||||||||||||||||||
| 1451 | 0 | is_deeply $e->tallyCount, 26177; # Insertion instruction counts | |||||||||||||||||||||||||||
| 1452 | 0 | 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 | 0 | done_testing; | |||||||||||||||||||||||||||
| 1478 | |||||||||||||||||||||||||||||
| 1479 | # (\A.{80})\s+(#.*\Z) \1\2 | ||||||||||||||||||||||||||||