blib/lib/Tree/Bulk.pm

filter: Statementstmt 96.2% 381 / 396 Branchbran 75.0% 258 / 344 Conditioncond 75.8% 88 / 116 MC/DCmcdc 45.9% 28 / 61 Subroutinesub 96.7% 60 / 62 Podpod 31.1% 14 / 45 totaltotal 80.9% 829 / 1024 CC 223 SCAR 25.6
CC
223
Cov
85%
__ANON__
62.4
printKeys2
14.0
insertUnchecked
11.1
CRAP 13.0
↑ Summary
1 #!/usr/bin/perl -I/home/phil/perl/cpan/DataTableText/lib/ -I.
2 #-------------------------------------------------------------------------------
3 # Bulk Tree operations
4 # Philip R Brenan at appaapps dot com, Appa Apps Ltd Inc., 2021
5 #-------------------------------------------------------------------------------
6 # podDocumentation
7 package Tree::Bulk;
8 1 our $VERSION = "20240415";
9 1 ▶use warnings FATAL => qw(all);
Subroutine BEGIN: called CC=1 SCAR=0.0
10 1 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
11 1 ▶use Carp qw(confess cluck);
Subroutine BEGIN: called CC=1 SCAR=0.0
12 1 ▶use Data::Dump qw(dump);
Subroutine BEGIN: called CC=1 SCAR=0.0
13 1 ▶use Data::Table::Text qw(:all);
Subroutine BEGIN: called CC=1 SCAR=0.0
14 1 ▶use feature qw(say current_sub);
Subroutine BEGIN: called CC=1 SCAR=0.0
15  
16 sub saveLog($) #P Save a result to the log file if we are developing.
17 0 ▶ {my ($string) = @_; # String to save
Subroutine saveLog: not called CC=2 SCAR=17.9
Pod undocumented
18 0 my $l = q(/home/phil/perl/z/bulkTree/zzz.txt); # Log file if available
19  
20 0 ▶ owf($l, $string) if -e $l;
Branch: 1 branch
BranchTrueFalseTotal
if -e $l 0 0 0
21 0 confess "Saved to logfile:\n$l\n";
22 exit
23 0 }
24  
25 sub save # Simplified save.
26 0 ▶ {my ($t) = @_; # Tree
Subroutine save: not called CC=1 SCAR=6.9
Pod undocumented
27 0 saveLog($t->printKeys);
28 }
29  
30 74428 ▶sub Left {q(left)} # Left.
Subroutine Left: called CC=1 SCAR=0.0
Pod undocumented
31 74370 ▶sub Right {q(right)} # Right.
Subroutine Right: called CC=1 SCAR=0.0
Pod undocumented
32  
33 #D1 Bulk Tree # Bulk Tree.
34  
35 sub node(;$$$$) #P Create a new bulk tree node.
36 562 ▶ {my ($key, $data, $up, $side) = @_; # Key, $data, parent node, side of parent node
Subroutine node: called CC=7 SCAR=20.0
Pod documented
37 562 ▶ my $t = genHash(__PACKAGE__, # Bulk tree node
Branch: 3 branches
BranchTrueFalseTotal
$up ? : 518 44 562
$key ? : 548 14 562
$data ? : 548 14 562
38 keysPerNode => $up ? $up->keysPerNode : 4, # Maximum number of keys per node
39 up => $up, # Parent node
40 left => undef, # Left node
41 right => undef, # Right node
42 height => 1, # Height of node
43 keys => [$key ? $key : ()], # Array of data items for this node
44 data => [$data ? $data : ()], # Data corresponding to each key
45 );
46  
47 562 ▶ if ($up) # Install new node in tree
Branch: 1 branch
BranchTrueFalseTotal
if ($up) 518 44 562
48 518 ▶ {if ($side)
Branch: 1 branch
BranchTrueFalseTotal
if ($side) { } 518 0 518
49 518 {$up->{$side} = $t;
50 518 $up->setHeights;
51 }
52 else
53 0 ▶ {confess 'Specify side' if !$side;
Branch: 1 branch
BranchTrueFalseTotal
unless $side 0 0 0
54 }
55 }
56 $t
57 562 }
58  
59 14 ▶sub new {node} # Create a new tree.
Subroutine new: called CC=1 SCAR=0.0
Pod documented
60  
61 sub isRoot($) # Return the tree if it is the root.
62 116664 ▶ {my ($tree) = @_; # Tree
Subroutine isRoot: called CC=3 SCAR=11.1
Pod undocumented
63 116664 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 116664 116664
64 116664 ▶ !$tree->up ? $tree : undef
Branch: 1 branch
BranchTrueFalseTotal
!$tree->up ? : 3069 113595 116664
65 }
66  
67 sub root($) # Return the root node of a tree.
68 1334 ▶ {my ($tree) = @_; # Tree
Subroutine root: called CC=3 SCAR=11.0
Pod documented
69 1334 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 1334 1334
70 1334 ▶ for(; $tree->up; $tree = $tree->up) {}
Branch: 1 branch
BranchTrueFalseTotal
if ($tree->up) 2 1334 1336
71 1334 $tree
72 }
73  
74 sub leaf($) # Return the tree if it is a leaf.
75 93847 ▶ {my ($tree) = @_; # Tree
Subroutine leaf: called CC=5 SCAR=16.3
Pod documented
76 93847 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 93847 93847
77 93847 ▶ $tree and !$tree->right and !$tree->left ? $tree : undef
Branch: 2 branches
BranchTrueFalseTotal
$tree and not $tree->right and !$tree->left ? $tree : undef 54637 39210 93847
!$tree->left ? : 47958 6679 54637
Condition66%2/3
$tree and not $tree->right
!ll&&!rl&&r
03921054637
MC/DC50%1/2
$tree and not $tree->right
$tree not $tree->right
Truth table66%2/3
A and not(B)
A= $treeB= not $tree->right
ABresult
0X0
100
111
78 }
79  
80 sub duplex($) # Return the tree if it has left and right children.
81 489 ▶ {my ($tree) = @_; # Tree
Subroutine duplex: called CC=4 SCAR=13.9
Pod undocumented
82 489 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 489 489
83 489 ▶ $tree->right and $tree->left ? $tree : undef
Branch: 2 branches
BranchTrueFalseTotal
$tree->right and $tree->left ? $tree : undef 3 486 489
$tree->left ? : 2 1 3
84 }
85  
86 sub simplex($) # Return the tree if it has either a left child or a right child but not both.
87 73696 ▶ {my ($tree) = @_; # Tree
Subroutine simplex: called CC=4 SCAR=13.9
Pod undocumented
88 73696 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 73696 73696
89 73696 ▶ $tree->right xor $tree->left ? $tree : undef
Branch: 1 branch
BranchTrueFalseTotal
$tree->left ? : 36310 37386 73696
Condition100%4/4
$tree->right ^^ ($tree->left ? $tree : undef)
l&&rl&&!r!l&&r!l&&!r
314524601485832785
MC/DC100%2/2
$tree->right ^^ ($tree->left ? $tree : undef)
$tree->right ($tree->left ? $tree : undef)
Truth table100%4/4
A ^^ B
A= $tree->rightB= ($tree->left ? $tree : undef)
ABresult
110
101
011
000
90 }
91  
92 sub simplexWithLeaf($) # Return the tree if it has either a left child or a right child but not both and the child it has a leaf.
93 9460 ▶ {my ($tree) = @_; # Tree
Subroutine simplexWithLeaf: called CC=8 SCAR=21.2
Pod undocumented
94 9460 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 9460 9460
95 9460 ▶ return undef unless $tree->right xor $tree->left;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree->right xor $tree->left 0 9460 9460
Condition50%2/4
$tree->right xor $tree->left
l&&rl&&!r!l&&r!l&&!r
0460248580
MC/DC0%0/2
$tree->right xor $tree->left
$tree->right $tree->left
Truth table50%2/4
A xor B
A= $tree->rightB= $tree->left
ABresult
110
101
011
000
96 9460 ▶ return undef if $tree->right and !$tree->right->leaf;
Branch: 1 branch
BranchTrueFalseTotal
if $tree->right and not $tree->right->leaf 31 9429 9460
Condition100%3/3
$tree->right and not $tree->right->leaf
!ll&&!rl&&r
4858457131
MC/DC100%2/2
$tree->right and not $tree->right->leaf
$tree->right not $tree->right->leaf
Truth table100%3/3
A and not(B)
A= $tree->rightB= not $tree->right->leaf
ABresult
0X0
100
111
97 9429 ▶ return undef if $tree->left and !$tree->left ->leaf;
Branch: 1 branch
BranchTrueFalseTotal
if $tree->left and not $tree->left->leaf 8 9421 9429
Condition100%3/3
$tree->left and not $tree->left->leaf
!ll&&!rl&&r
457148508
MC/DC100%2/2
$tree->left and not $tree->left->leaf
$tree->left not $tree->left->leaf
Truth table100%3/3
A and not(B)
A= $tree->leftB= not $tree->left->leaf
ABresult
0X0
100
111
98 9421 $tree
99 }
100  
101 sub empty($) # Return the tree if it is empty.
102 3442 ▶ {my ($tree) = @_; # Tree
Subroutine empty: called CC=4 SCAR=13.9
Pod undocumented
103 3442 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 3442 3442
104 3442 ▶ $tree->leaf and !$tree->keys->@* ? $tree : undef
Branch: 2 branches
BranchTrueFalseTotal
$tree->leaf and !@{$tree->keys} ? $tree : undef 2248 1194 3442
!@{$tree->keys} ? : 492 1756 2248
105 }
106  
107 sub singleton($) # Return the tree if it contains only the root node and nothing else.
108 4378 ▶ {my ($tree) = @_; # Tree
Subroutine singleton: called CC=4 SCAR=13.9
Pod undocumented
109 4378 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 4378 4378
110 4378 ▶ $tree->leaf and $tree->isRoot ? $tree : undef;
Branch: 2 branches
BranchTrueFalseTotal
$tree->leaf and $tree->isRoot ? $tree : undef 1747 2631 4378
$tree->isRoot ? : 394 1353 1747
111 }
112  
113 sub isLeftChild($) # Return the tree if it is the left child.
114 726 ▶ {my ($tree) = @_; # Tree
Subroutine isLeftChild: called CC=5 SCAR=16.3
Pod undocumented
115 726 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 726 726
116 726 ▶ $tree->up and $tree->up->left and $tree->up->left == $tree ? $tree : undef;
Branch: 2 branches
BranchTrueFalseTotal
$tree->up and $tree->up->left and $tree->up->left == $tree ? $tree : undef 572 154 726
$tree->up->left == $tree ? : 379 193 572
Condition66%2/3
$tree->up and $tree->up->left
!ll&&!rl&&r
0154572
MC/DC50%1/2
$tree->up and $tree->up->left
$tree->up $tree->up->left
Truth table66%2/3
A and B
A= $tree->upB= $tree->up->left
ABresult
0X0
100
111
117 }
118  
119 sub isRightChild($) # Return the tree if it is the right child.
120 170 ▶ {my ($tree) = @_; # Tree
Subroutine isRightChild: called CC=5 SCAR=16.3
Pod documented
121 170 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 170 170
122 170 ▶ $tree->up and $tree->up->right and $tree->up->right == $tree ? $tree : undef;
Branch: 2 branches
BranchTrueFalseTotal
$tree->up and $tree->up->right and $tree->up->right == $tree ? $tree : undef 124 46 170
$tree->up->right == $tree ? : 90 34 124
Condition66%2/3
$tree->up and $tree->up->right
!ll&&!rl&&r
046124
MC/DC50%1/2
$tree->up and $tree->up->right
$tree->up $tree->up->right
Truth table66%2/3
A and B
A= $tree->upB= $tree->up->right
ABresult
0X0
100
111
123 }
124  
125 sub name($) # Name of a tree.
126 74474 ▶ {my ($tree) = @_; # Tree
Subroutine name: called CC=2 SCAR=7.1
Pod documented
127 74474 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 74474 74474
128 74474 join ' ', $tree->keys->@*
129 }
130  
131 sub names($) # Names of all nodes in a tree in order.
132 3 ▶ {my ($tree) = @_; # Tree
Subroutine names: called CC=2 SCAR=7.0
Pod undocumented
133 3 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 3 3
134 3 join ' ', map {$_->name} $tree->inorder;
135 }
136  
137 sub setHeights($) #P Set heights along path to root.
138 1011 ▶ {my ($tree) = @_; # Tree
Subroutine setHeights: called CC=3 SCAR=11.0
Pod undocumented
139 1011 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 1011 1011
140 1011 ▶ for(my $n = $tree; $n; $n = $n->up)
Branch: 1 branch
BranchTrueFalseTotal
if ($n) 6257 1011 7268
141 6257 {$n->setHeight;
142 6257 $n->balance;
143 }
144 1011 $tree
145 } # setHeights
146  
147 sub actualHeight($) #P Get the height of a node.
148 30182 ▶ {my ($tree) = @_; # Tree
Subroutine actualHeight: called CC=2 SCAR=6.9
Pod documented
149 30182 ▶ return 0 unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 5894 24288 30182
150 24288 $tree->height
151 }
152  
153 sub setHeight($) #P Set height of a tree from its left and right trees.
154 7472 ▶ {my ($tree) = @_; # Tree
Subroutine setHeight: called CC=2 SCAR=7.0
Pod undocumented
155 7472 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 7472 7472
156 7472 my $l = actualHeight($tree->left);
157 7472 my $r = actualHeight($tree->right);
158 7472 $tree->height = 1 + maximum($l, $r);
159 7472 $tree
160 } # setHeight
161  
162 # Rotate left
163  
164 # p p
165 # n r
166 # l r n R
167 # L R l L
168  
169 sub rotateLeft($) #P Rotate a node left.
170 487 ▶ {my ($n) = @_; # Node
Subroutine rotateLeft: called CC=7 SCAR=19.5
Pod undocumented
171 487 ▶ confess unless $n;
Branch: 1 branch
BranchTrueFalseTotal
unless $n 0 487 487
172 487 my $p = $n->up;
173 487 ▶ return unless $p;
Branch: 1 branch
BranchTrueFalseTotal
unless $p 318 169 487
174 169 my $r = $n->right;
175 169 ▶ return unless $r;
Branch: 1 branch
BranchTrueFalseTotal
unless $r 1 168 169
176 168 my $L = $r->left;
177 168 ▶ $p->{$n->isRightChild ? Right : Left} = $r; $r->up = $p;
Branch: 1 branch
BranchTrueFalseTotal
$n->isRightChild ? : 89 79 168
178 168 $r->left = $n; $n->up = $r;
179 168 ▶ $n->right = $L; $L->up = $n if $L;
Branch: 1 branch
BranchTrueFalseTotal
if $L 43 125 168
180 168 setHeight $_ for $n, $r, $p;
181 168 $r->refill;
182 } # rotateLeft
183  
184 sub rotateRight($) #P Rotate a node right.
185 467 ▶ {my ($n) = @_; # Node
Subroutine rotateRight: called CC=7 SCAR=19.5
Pod undocumented
186 467 ▶ confess unless $n;
Branch: 1 branch
BranchTrueFalseTotal
unless $n 0 467 467
187 467 my $p = $n->up;
188 467 ▶ return unless $p;
Branch: 1 branch
BranchTrueFalseTotal
unless $p 229 238 467
189 238 my $l = $n->left;
190 238 ▶ return unless $l;
Branch: 1 branch
BranchTrueFalseTotal
unless $l 1 237 238
191 237 my $R = $l->right;
192 237 ▶ $p->{$n->isLeftChild ? Left : Right} = $l; $l->up = $p;
Branch: 1 branch
BranchTrueFalseTotal
$n->isLeftChild ? : 134 103 237
193 237 $l->right = $n; $n->up = $l;
194 237 ▶ $n->left = $R; $R->up = $n if $R;
Branch: 1 branch
BranchTrueFalseTotal
if $R 94 143 237
195 237 setHeight $_ for $n, $l, $p;
196 237 $l->refill;
197 } # rotateLeft
198  
199 # Balance - make the deepest sub tree one less deep
200  
201 # 1 1
202 # 2 5
203 # 6 2 6
204 # 5 4
205 # 4 3
206 # 3
207  
208 sub balance($) # Balance a node.
209 6751 ▶ {my ($t) = @_; # Tree
Subroutine balance: called CC=8 SCAR=20.9
Pod undocumented
210 6751 ▶ confess unless $t;
Branch: 1 branch
BranchTrueFalseTotal
unless $t 0 6751 6751
211 6751 my ($l, $r) = (actualHeight($t->left), actualHeight($t->right));
212  
213 6751 ▶ if ($l > 2 * $r + 1) # Rotate right
Branch: 2 branches
BranchTrueFalseTotal
if ($l > 2 * $r + 1) { } 425 6326 6751
elsif ($r > 2 * $l + 1) { } 437 5889 6326
214 425 ▶ {if (my $l = $t->left) # Counter balance if necessary
Branch: 1 branch
BranchTrueFalseTotal
if (my $l = $t->left) 425 0 425
215 425 ▶ {if (actualHeight($l->right) > actualHeight($l->left))
Branch: 1 branch
BranchTrueFalseTotal
if (&actualHeight(scalar $l->right) > &actualHeight(scalar $l->left)) 48 377 425
216 48 {$l->rotateLeft
217 }
218 }
219 425 $t->rotateRight;
220 }
221 elsif ($r > 2 * $l + 1) # Rotate left
222 437 ▶ {if (my $r = $t->right) # Counter balance if necessary
Branch: 1 branch
BranchTrueFalseTotal
if (my $r = $t->right) 437 0 437
223 437 ▶ {if (actualHeight($r->left) > actualHeight($r->right))
Branch: 1 branch
BranchTrueFalseTotal
if (&actualHeight(scalar $r->left) > &actualHeight(scalar $r->right)) 40 397 437
224 40 {$r->rotateRight
225 }
226 }
227 437 $t->rotateLeft;
228 }
229  
230 $t
231 6751 } # balance
232  
233 sub insertUnchecked($$$) #P Insert a key and some data into a tree.
234 7640 ▶ {my ($tree, $key, $data) = @_; # Tree, key, data
Subroutine insertUnchecked: called CC=11 SCAR=24.1
Pod undocumented
235 7640 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 7640 7640
236 7640 ▶ confess unless defined $key;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $key 0 7640 7640
237  
238 my sub insertIntoNode # Insert the current key into the specified node
239 995 ▶ {my @k; my @d; # Rebuilt node
Subroutine insertIntoNode: called CC=6 SCAR=17.9
240 995 my $low = 1; # Keys less than the key
241 995 for my $i(keys $tree->keys->@*) # Insert key and data in node
242 3312 {my $k = $tree->keys->[$i];
243 3312 ▶ confess "Duplicate key" if $k == $key;
Branch: 1 branch
BranchTrueFalseTotal
if $k == $key 0 3312 3312
244 3312 ▶ if ($low and $k > $key) # Insert key and data before first greater key
Branch: 1 branch
BranchTrueFalseTotal
if ($low and $k > $key) 893 2419 3312
Condition100%3/3
$low and $k > $key
!ll&&!rl&&r
12791140893
MC/DC100%2/2
$low and $k > $key
$low $k > $key
Truth table100%3/3
A and B
A= $lowB= $k > $key
ABresult
0X0
100
111
245 893 {$low = undef;
246 893 push @k, $key;
247 893 push @d, $data;
248 }
249 3312 push @k, $k;
250 3312 push @d, $tree->data->[$i];
251 }
252 995 ▶ if ($low) # Key bigger than largest key
Branch: 1 branch
BranchTrueFalseTotal
if ($low) 102 893 995
253 102 {push @d, $data;
254 102 push @k, $key;
255 }
256 995 $tree->keys = \@k; $tree->data = \@d; # Keys and data in node
257 } # insertIntoNode
258  
259 7640 ▶ if ($tree->keys->@* < $tree->keysPerNode and leaf $tree) # Small node so we can add within the node
Branch: 3 branches
BranchTrueFalseTotal
if (@{$tree->keys} < $tree->keysPerNode and &leaf($tree)) { } 741 6899 7640
elsif ($key < $tree->keys->[0]) { } 4439 2460 6899
elsif ($key > $tree->keys->[-1]) { } 2206 254 2460
Condition66%2/3
@{$tree->keys} < $tree->keysPerNode and &leaf($tree)
!ll&&!rl&&r
68990741
MC/DC50%1/2
@{$tree->keys} < $tree->keysPerNode and &leaf($tree)
@{$tree->keys} < $tree->keysPerNode &leaf($tree)
Truth table66%2/3
A and B
A= @{$tree->keys} < $tree->keysPerNodeB= &leaf($tree)
ABresult
0X0
100
111
260 741 {insertIntoNode;
261 741 return $tree;
262 }
263  
264 elsif ($key < $tree->keys->[0]) # Less than least - Go left
265 4439 ▶ {if ($tree->left) # New node left
Branch: 1 branch
BranchTrueFalseTotal
if ($tree->left) { } 4162 277 4439
266 4162 {return __SUB__->($tree->left, $key, $data);
267 }
268 else
269 277 {return node $key, $data, $tree, Left; # Add a new node left
270 }
271 }
272  
273 elsif ($key > $tree->keys->[-1]) # Greater than most - go right
274 2206 ▶ {if ($tree->right) # New node right
Branch: 1 branch
BranchTrueFalseTotal
if ($tree->right) { } 2007 199 2206
275 2007 {return __SUB__->($tree->right, $key, $data);
276 }
277 else
278 199 {return node $key, $data, $tree, Right; # Add a new node right
279 }
280 }
281  
282 else # Full node and key is inside it
283 254 {insertIntoNode; # Keys in node
284 254 ▶ if ($tree->keys->@* > $tree->keysPerNode) # Reinsert last key and data if the node is now to big
Branch: 1 branch
BranchTrueFalseTotal
if (@{$tree->keys} > $tree->keysPerNode) 254 0 254
285 254 {my $k = pop $tree->keys->@*;
286 254 my $d = pop $tree->data->@*;
287 254 ▶ if (my $r = $tree->right)
Branch: 1 branch
BranchTrueFalseTotal
if (my $r = $tree->right) { } 212 42 254
288 212 {return $r->insertUnchecked($k, $d);
289 }
290 else # Insert right in new node and balance
291 42 {return node $k, $d, $tree, Right;
292 }
293 }
294 0 return $tree;
295 }
296 } # insertUnchecked
297  
298 sub insert($$$) # Insert a key and some data into a tree.
299 1234 ▶ {my ($tree, $key, $data) = @_; # Tree, key, data
Subroutine insert: called CC=3 SCAR=11.4
Pod undocumented
300 1234 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 1234 1234
301 1234 ▶ confess unless defined $key;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $key 0 1234 1234
302 1234 $tree->insertUnchecked($key, $data);
303 } # insert
304  
305 sub find($$) # Find a key in a tree and returns its data.
306 97922 ▶ {my ($tree, $key) = @_; # Tree, key
Subroutine find: called CC=4 SCAR=14.0
Pod documented
307 97922 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 97922 97922
308 97922 ▶ confess "No key" unless defined $key;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $key 0 97922 97922
309 97922 ▶ confess "Non numeric key" unless $key =~ m(\A\d+\Z);
Branch: 1 branch
BranchTrueFalseTotal
unless $key =~ /\A\d+\Z/ 0 97922 97922
310  
311 sub # Find the key in the sub-tree
312 515873 ▶ {my ($tree) = @_; # Sub-tree
Subroutine __ANON__: called CC=8 SCAR=20.8
313 515873 ▶ if ($tree)
Branch: 1 branch
BranchTrueFalseTotal
if ($tree) 515871 2 515873
314 515871 {my $keys = $tree->keys;
315 515871 ▶ confess "Empty node" unless $keys->@*;
Branch: 1 branch
BranchTrueFalseTotal
unless @$keys 0 515871 515871
316  
317 515871 ▶ return __SUB__->($tree->left) if $key < $$keys[ 0];
Branch: 1 branch
BranchTrueFalseTotal
if $key < $keys->[0] 192595 323276 515871
318 323276 ▶ return __SUB__->($tree->right) if $key > $$keys[-1];
Branch: 1 branch
BranchTrueFalseTotal
if $key > $keys->[-1] 225356 97920 323276
319  
320 97920 for my $i(keys $keys->@*) # Find key in node
321 237672 {my $v = $tree->data->[$i];
322 237672 ▶ confess "undefined data for key $key" unless defined $v;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $v 0 237672 237672
323 237672 ▶ return $tree->data->[$i] if $key == $$keys[$i];
Branch: 1 branch
BranchTrueFalseTotal
if $key == $keys->[$i] 97920 139752 237672
324 }
325 }
326 undef
327 97922 }->($tree)
328 } # find
329  
330 sub first($) # First node in a tree.
331 356 ▶ {my ($n) = @_; # Tree
Subroutine first: called CC=3 SCAR=11.0
Pod undocumented
332 356 ▶ confess unless $n;
Branch: 1 branch
BranchTrueFalseTotal
unless $n 0 356 356
333 356 ▶ $n = $n->left while $n->left;
Branch: 1 branch
BranchTrueFalseTotal
$n->left and do { $n = $n->left } 256 356 612
334 356 $n
335 }
336  
337 sub last($) # Last node in a tree.
338 412 ▶ {my ($n) = @_; # Tree
Subroutine last: called CC=3 SCAR=11.0
Pod documented
339 412 ▶ confess unless $n;
Branch: 1 branch
BranchTrueFalseTotal
unless $n 0 412 412
340 412 ▶ $n = $n->right while $n->right;
Branch: 1 branch
BranchTrueFalseTotal
$n->right and do { $n = $n->right } 392 412 804
341 412 $n
342 }
343  
344 sub next($) # Next node in order.
345 1079 ▶ {my ($tree) = @_; # Tree
Subroutine next: called CC=8 SCAR=20.9
Pod documented
346 1079 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 1079 1079
347 1079 ▶ if (my $r = $tree->right)
Branch: 1 branch
BranchTrueFalseTotal
if (my $r = $tree->right) 830 249 1079
348 830 ▶ {return $r->left ? $r->left->first : $r;
Branch: 1 branch
BranchTrueFalseTotal
$r->left ? : 347 483 830
349 }
350 249 my $p = $tree;
351 249 ▶ for(; $p; $p = $p->up)
Branch: 1 branch
BranchTrueFalseTotal
if ($p) 489 0 489
352 489 ▶ {return $p->up unless $p->up and $p->up->right and $p->up->right == $p;
Branch: 1 branch
BranchTrueFalseTotal
unless $p->up and $p->up->right and $p->up->right == $p 249 240 489
Condition100%6/6
$p->up and $p->up->right and $p->up->right == $p
!ll&&!rl&&r
35214240
$p->up and $p->up->right
!ll&&!rl&&r
926454
MC/DC100%3/3
$p->up and $p->up->right and $p->up->right == $p
$p->up $p->up->right $p->up->right == $p
Truth table100%4/4
A and B and C
A= $p->upB= $p->up->rightC= $p->up->right == $p
ABCresult
0XX0
10X0
1100
1111
353 }
354 undef
355 0 }
356  
357 sub prev($) # Previous node in order.
358 827 ▶ {my ($tree) = @_; # Tree
Subroutine prev: called CC=8 SCAR=21.2
Pod documented
359 827 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 827 827
360 827 ▶ if (my $l = $tree->left)
Branch: 1 branch
BranchTrueFalseTotal
if (my $l = $tree->left) 800 27 827
361 800 ▶ {return $l->right ? $l->right->last : $l;
Branch: 1 branch
BranchTrueFalseTotal
$l->right ? : 411 389 800
362 }
363 27 my $p = $tree;
364 27 ▶ for(; $p; $p = $p->up)
Branch: 1 branch
BranchTrueFalseTotal
if ($p) 55 0 55
365 55 ▶ {return $p->up unless $p->up and $p->up->left and $p->up->left == $p;
Branch: 1 branch
BranchTrueFalseTotal
unless $p->up and $p->up->left and $p->up->left == $p 27 28 55
Condition83%5/6
$p->up and $p->up->left and $p->up->left == $p
!ll&&!rl&&r
12628
$p->up and $p->up->left
!ll&&!rl&&r
1054
MC/DC66%2/3
$p->up and $p->up->left and $p->up->left == $p
$p->up $p->up->left $p->up->left == $p
Truth table75%3/4
A and B and C
A= $p->upB= $p->up->leftC= $p->up->left == $p
ABCresult
0XX0
10X0
1100
1111
366 }
367 undef
368 0 }
369  
370 sub inorder($) # Return a list of all the nodes in a tree in order.
371 8 ▶ {my ($tree) = @_; # Tree
Subroutine inorder: called CC=3 SCAR=11.0
Pod undocumented
372 8 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 8 8
373 8 my @n;
374 8 ▶ for(my $n = $tree->first; $n; $n = $n->next)
Branch: 1 branch
BranchTrueFalseTotal
if ($n) 434 8 442
375 434 {push @n, $n;
376 }
377 @n
378 8 }
379  
380 sub unchain($) #P Remove a tree from the middle of a chain. A leaf is considered to be in the middle of a chain and so can be removed with this method.
381 487 ▶ {my ($t) = @_; # Tree
Subroutine unchain: called CC=9 SCAR=22.2
Pod undocumented
382 487 ▶ confess unless $t;
Branch: 1 branch
BranchTrueFalseTotal
unless $t 0 487 487
383 487 ▶ confess "Duplex tree cannot be unchained" if duplex $t;
Branch: 1 branch
BranchTrueFalseTotal
if &duplex($t) 0 487 487
384 487 ▶ confess "Root cannot be unchained" unless my $p = $t->up;
Branch: 1 branch
BranchTrueFalseTotal
unless my $p = $t->up 0 487 487
385  
386 487 ▶ my $c = $t->left // $t->right; # Not duplex so at most one of these
Condition66%2/3
$t->left // $t->right
l!l&&r!l&&!r
01486
MC/DC50%1/2
$t->left // $t->right
$t->left $t->right
Truth table66%2/3
A // B
A= $t->leftB= $t->right
ABresult
1X1
011
000
387 487 ▶ $p->{$t->isLeftChild ? Left : Right} = $c; # Unchain
Branch: 1 branch
BranchTrueFalseTotal
$t->isLeftChild ? : 244 243 487
388 487 ▶ $c->up = $p if $c;
Branch: 1 branch
BranchTrueFalseTotal
if $c 1 486 487
389 487 $t->up = undef;
390  
391 487 ▶ if (my $l = $p->left) {$l->setHeights} # Set heights from a known point
Branch: 2 branches
BranchTrueFalseTotal
if (my $l = $p->left) { } 129 358 487
elsif (my $r = $p->right) { } 129 229 358
392 129 elsif (my $r = $p->right) {$r->setHeights}
393 229 else {$p->setHeights}
394  
395 487 $p->balance; # Rebalance parent
396  
397 487 $p # Unchained node
398 } # unchain
399  
400 sub refillFromRight($) #P Push a key to the target node from the next node.
401 590 ▶ {my ($target) = @_; # Target tree
Subroutine refillFromRight: called CC=8 SCAR=21.0
Pod undocumented
402  
403 590 ▶ confess unless $target;
Branch: 1 branch
BranchTrueFalseTotal
unless $target 0 590 590
404 590 ▶ confess "No right" unless $target->right; # Ensure source will be in this sub tree
Branch: 1 branch
BranchTrueFalseTotal
unless $target->right 0 590 590
405 590 ▶ confess "No source" unless my $source = $target->next; # No source
Branch: 1 branch
BranchTrueFalseTotal
unless my $source = $target->next 0 590 590
406  
407 590 ▶ while ($source->keys->@* > 0 and $target->keys->@* < $target->keysPerNode) # Transfer fill from source
Branch: 1 branch
BranchTrueFalseTotal
if (@{$source->keys} > 0 and @{$target->keys} < $target->keysPerNode) 595 590 1185
Condition100%3/3
@{$source->keys} > 0 and @{$target->keys} < $target->keysPerNode
!ll&&!rl&&r
236354595
MC/DC100%2/2
@{$source->keys} > 0 and @{$target->keys} < $target->keysPerNode
@{$source->keys} > 0 @{$target->keys} < $target->keysPerNode
Truth table100%3/3
A and B
A= @{$source->keys} > 0B= @{$target->keys} < $target->keysPerNode
ABresult
0X0
100
111
408 595 {push $target->keys->@*, shift $source->keys->@*;
409 595 push $target->data->@*, shift $source->data->@*;
410 }
411 590 ▶ $source->unchain if $source->empty;
Branch: 1 branch
BranchTrueFalseTotal
if $source->empty 222 368 590
412 590 $_->refill for $target, $source;
413 } # refillFromRight
414  
415 sub refillFromLeft($) #P Push a key to the target node from the previous node.
416 772 ▶ {my ($target) = @_; # Target tree
Subroutine refillFromLeft: called CC=8 SCAR=21.0
Pod undocumented
417  
418 772 ▶ confess unless $target;
Branch: 1 branch
BranchTrueFalseTotal
unless $target 0 772 772
419 772 ▶ confess "No left" unless $target->left; # Ensure source will be in this sub tree
Branch: 1 branch
BranchTrueFalseTotal
unless $target->left 0 772 772
420 772 ▶ confess "No source" unless my $source = $target->prev; # No source
Branch: 1 branch
BranchTrueFalseTotal
unless my $source = $target->prev 0 772 772
421  
422 772 ▶ while ($source->keys->@* > 0 and $target->keys->@* < $target->keysPerNode) # Transfer fill from source
Branch: 1 branch
BranchTrueFalseTotal
if (@{$source->keys} > 0 and @{$target->keys} < $target->keysPerNode) 418 772 1190
Condition100%3/3
@{$source->keys} > 0 and @{$target->keys} < $target->keysPerNode
!ll&&!rl&&r
93679418
MC/DC100%2/2
@{$source->keys} > 0 and @{$target->keys} < $target->keysPerNode
@{$source->keys} > 0 @{$target->keys} < $target->keysPerNode
Truth table100%3/3
A and B
A= @{$source->keys} > 0B= @{$target->keys} < $target->keysPerNode
ABresult
0X0
100
111
423 418 {unshift $target->keys->@*, pop $source->keys->@*;
424 418 unshift $target->data->@*, pop $source->data->@*;
425 }
426  
427 772 ▶ $source->unchain if $source->empty;
Branch: 1 branch
BranchTrueFalseTotal
if $source->empty 93 679 772
428 772 $_->refill for $target, $source;
429 } # refillFromLeft
430  
431 sub refill($) #P Refill a node so it has the expected number of keys.
432 4377 ▶ {my ($tree) = @_; # Tree
Subroutine refill: called CC=11 SCAR=24.0
Pod undocumented
433 4377 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 4377 4377
434  
435 4377 ▶ return if $tree->singleton; # No need to refill a leaf
Branch: 1 branch
BranchTrueFalseTotal
if $tree->singleton 393 3984 4377
436 3984 ▶ return if $tree->keys->@* == $tree->keysPerNode; # Interior node is full so no need of refill
Branch: 1 branch
BranchTrueFalseTotal
if @{$tree->keys} == $tree->keysPerNode 1910 2074 3984
437  
438 2074 ▶ if ($tree->empty) # Remove an empty leaf that is not the root
Branch: 2 branches
BranchTrueFalseTotal
if ($tree->empty) { } 171 1903 2074
elsif (@{$tree->keys} < $tree->keysPerNode) { } 1886 17 1903
439 171 ▶ {$tree->unchain unless $tree->isRoot;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree->isRoot 171 0 171
440 }
441  
442 elsif ($tree->keys->@* < $tree->keysPerNode) # Refill the node from neighboring leaf nodes
443 1886 ▶ {if (!$tree->leaf) # Do not refill leaves
Branch: 1 branch
BranchTrueFalseTotal
if (not $tree->leaf) 982 904 1886
444 982 ▶ {$tree->refillFromRight if $tree->right;
Branch: 1 branch
BranchTrueFalseTotal
if $tree->right 590 392 982
445 982 ▶ $tree->refillFromLeft if $tree->left;
Branch: 1 branch
BranchTrueFalseTotal
if $tree->left 772 210 982
446 }
447 }
448  
449 else
450 17 ▶ {while($tree->keys->@* > $tree->keysPerNode) # Empty node if over full
Branch: 1 branch
BranchTrueFalseTotal
if (@{$tree->keys} > $tree->keysPerNode) 25 17 42
451 25 {$tree->insertUnchecked(pop $tree->keys->@*, pop $tree->data->@*); # Reinsert lower down
452 }
453 }
454 } # refill
455  
456 sub delete($$) # Delete a key in a tree.
457 1167 ▶ {my ($tree, $key) = @_; # Tree, key
Subroutine delete: called CC=3 SCAR=11.1
Pod undocumented
458 1167 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 1167 1167
459 1167 ▶ confess "No key" unless defined $key;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $key 0 1167 1167
460  
461 sub # Find then delete the key in the sub-tree
462 4661 ▶ {my ($tree) = @_; # Sub-tree
Subroutine __ANON__: called CC=8 SCAR=20.9
463 4661 ▶ return unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 4661 4661
464 4661 ▶ return unless $tree->keys->@*; # Empty tree
Branch: 1 branch
BranchTrueFalseTotal
unless @{$tree->keys} 0 4661 4661
465 4661 ▶ if ($key < $tree->keys->[ 0]) {__SUB__->($tree->left)} # Less than least key so go left
Branch: 3 branches
BranchTrueFalseTotal
if ($key < $tree->keys->[0]) { } 1653 3008 4661
elsif ($key > $tree->keys->[-1]) { } 1841 1167 3008
elsif (grep {$_ == $key;} @{$tree->keys}) { } 1167 0 1167
466 1841 elsif ($key > $tree->keys->[-1]) {__SUB__->($tree->right)} # Greater than most key so go right
467 4201 elsif (grep {$_ == $key} $tree->keys->@*) # Key present in current node
468 1167 {my @k, my @d;
469 1167 for my $i(keys $tree->keys->@*) # Remove the key and corresponding data
470 4201 ▶ {next if $tree->keys->[$i] == $key;
Branch: 1 branch
BranchTrueFalseTotal
if $tree->keys->[$i] == $key 1167 3034 4201
471 3034 push @d, $tree->data->[$i];
472 3034 push @k, $tree->keys->[$i];
473 }
474 1167 $tree->keys = \@k; $tree->data = \@d;
475 1167 $tree->refill; # Refill the tree
476 }
477 1167 }->($tree);
478 } # delete
479  
480 sub printKeys2($$$) #P Print the keys for a tree.
481 522 ▶ {my ($t, $in, $g) = @_; # Tree, indentation, list of keys,
Subroutine printKeys2: called CC=14 SCAR=26.4
Pod undocumented
482 522 ▶ return unless $t;
Branch: 1 branch
BranchTrueFalseTotal
unless $t 279 243 522
483 243 __SUB__->($t->left, $in+1, $g); # Left
484  
485 243 my $h = $t->height;
486 243 ▶ my $s = $t->up && $t->up->left && $t->up->left == $t ? 'L' : # Print
Branch: 2 branches
BranchTrueFalseTotal
$t->up && $t->up->left && $t->up->left == $t ? : 81 162 243
$t->up && $t->up->right && $t->up->right == $t ? : 126 36 162
Condition83%10/12
$t->up and $t->up->left and $t->up->left == $t
!ll&&!rl&&r
887481
$t->up and $t->up->left
!ll&&!rl&&r
3652155
$t->up and $t->up->right and $t->up->right == $t
!ll&&!rl&&r
360126
$t->up and $t->up->right
!ll&&!rl&&r
360126
MC/DC100%3/3
$t->up and $t->up->left and $t->up->left == $t
$t->up $t->up->left $t->up->left == $t
MC/DC33%1/3
$t->up and $t->up->right and $t->up->right == $t
$t->up $t->up->right $t->up->right == $t
Truth table100%4/4
A and B and C
A= $t->upB= $t->up->leftC= $t->up->left == $t
ABCresult
0XX0
10X0
1100
1111
Truth table50%2/4
A and B and C
A= $t->upB= $t->up->rightC= $t->up->right == $t
ABCresult
0XX0
10X0
1100
1111
487 $t->up && $t->up->right && $t->up->right == $t ? 'R' : 'S';
488 243 ▶ $s .= $t->leaf ? 'z' : $t->isRoot ? 'A' : $t->left && $t->right ? 'd' : $t->left ? 'l' : 'r';
Branch: 4 branches
BranchTrueFalseTotal
$t->leaf ? : 110 133 243
$t->isRoot ? : 33 100 133
$t->left && $t->right ? : 74 26 100
$t->left ? : 5 21 26
Condition100%3/3
$t->left and $t->right
!ll&&!rl&&r
21574
MC/DC100%2/2
$t->left and $t->right
$t->left $t->right
Truth table100%3/3
A and B
A= $t->leftB= $t->right
ABresult
0X0
100
111
489 243 $s .= "$in $h ".(' ' x $in);
490 243 $s .= $t->name;
491 243 ▶ $s .= '->'.$t->up->name if $t->up;
Branch: 1 branch
BranchTrueFalseTotal
if $t->up 207 36 243
492 243 push @$g, $s;
493  
494 243 __SUB__->($t->right, $in+1, $g); # Right
495 }
496  
497 sub printKeys($) # Print the keys in a tree.
498 36 ▶ {my ($t) = @_; # Tree
Subroutine printKeys: called CC=2 SCAR=7.0
Pod undocumented
499 36 ▶ confess unless $t;
Branch: 1 branch
BranchTrueFalseTotal
unless $t 0 36 36
500  
501 36 my @s;
502 36 printKeys2 $t, 0, \@s;
503  
504 36 (join "\n", @s, "") =~ s(\s+\Z) (\n)sr
505 } # printKeys
506  
507 sub setKeysPerNode($$) # Set the number of keys for the current node.
508 81 ▶ {my ($tree, $N) = @_; # Tree, keys per node to be set
Subroutine setKeysPerNode: called CC=4 SCAR=15.0
Pod undocumented
509 81 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 81 81
510 81 ▶ confess unless $N and $N > 0;
Branch: 1 branch
BranchTrueFalseTotal
unless $N and $N > 0 0 81 81
Condition33%1/3
$N and $N > 0
!ll&&!rl&&r
0081
MC/DC0%0/2
$N and $N > 0
$N $N > 0
Truth table33%1/3
A and B
A= $NB= $N > 0
ABresult
0X0
100
111
511 81 $tree->keysPerNode = $N; # Set
512 81 $tree->refill; # Refill if necessary
513 81 $tree # Allow chaining
514 } # setKeysPerNode
515  
516 sub printKeysAndData($) # Print the mapping from keys to data in a tree.
517 2 ▶ {my ($t) = @_; # Tree
Subroutine printKeysAndData: called CC=2 SCAR=6.9
Pod documented
518 2 ▶ confess unless $t;
Branch: 1 branch
BranchTrueFalseTotal
unless $t 0 2 2
519 2 my @s;
520 my sub print($$)
521 20 ▶ {my ($t, $in) = @_;
Subroutine print: called CC=3 SCAR=11.0
522 20 ▶ return unless $t;
Branch: 1 branch
BranchTrueFalseTotal
unless $t 11 9 20
523 9 __SUB__->($t->left, $in+1); # Left
524 9 push @s, [$t->keys->[$_], $t->data->[$_]] for keys $t->keys->@*; # Find key in node
525 9 __SUB__->($t->right, $in+1); # Right
526 }
527 2 print $t, 0;
528 2 formatTableBasic(\@s)
529 } # printKeysAndData
530  
531 sub checkLRU($) #P Confirm pointers in tree.
532 1332 ▶ {my ($tree) = @_; # Tree
Subroutine checkLRU: called CC=1 SCAR=0.0
Pod documented
533 1332 my %seen; # Nodes we have already seen
534  
535 sub # Check pointers in a tree
536 148720 ▶ {my ($tree, $dir) = @_; # Tree
Subroutine __ANON__: called CC=3 SCAR=11.0
537 148720 ▶ return unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 75026 73694 148720
538  
539 73694 ▶ confess "Recursed $dir into: ".$tree->name if $seen{$tree->name}++;
Branch: 1 branch
BranchTrueFalseTotal
if $seen{$tree->name}++ 0 73694 73694
540  
541 73694 __SUB__->($tree->left, Left);
542 73694 __SUB__->($tree->right, Right);
543 1332 }->($tree->root);
544 }
545  
546 sub check($) #P Confirm that each node in a tree is ordered correctly.
547 1332 ▶ {my ($tree) = @_; # Tree
Subroutine check: called CC=3 SCAR=11.8
Pod undocumented
548 1332 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 1332 1332
549 1332 $tree->checkLRU;
550  
551 1332 my $maxHeight = 0;
552  
553 sub
554 148720 ▶ {my ($tree) = @_; # Tree
Subroutine __ANON__: called CC=33 SCAR=41.3
555 148720 ▶ return unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 75026 73694 148720
556  
557 73694 __SUB__->($tree->left);
558 73694 __SUB__->($tree->right);
559  
560 73694 ▶ confess $tree->name unless $tree->keys->@* == $tree->data->@*; # Check key count matches data count
Branch: 1 branch
BranchTrueFalseTotal
unless @{$tree->keys} == @{$tree->data} 0 73694 73694
561  
562 73694 ▶ if ( !$tree->leaf and !$tree->isRoot # Confirm that all interior nodes are fully filled
Branch: 1 branch
BranchTrueFalseTotal
if (not $tree->leaf || $tree->isRoot and @{$tree->keys} != $tree->keysPerNode) 0 73694 73694
Condition83%5/6
not $tree->leaf || $tree->isRoot and @{$tree->keys} != $tree->keysPerNode
!ll&&!rl&&r
34087396070
$tree->leaf || $tree->isRoot
l!l&&r!l&&!r
32784130339607
MC/DC0%0/3
not $tree->leaf || $tree->isRoot and @{$tree->keys} != $tree->keysPerNode
$tree->leaf $tree->isRoot @{$tree->keys} != $tree->keysPerNode
Truth table75%3/4
not(A || B) and C
A= $tree->leafB= $tree->isRootC= @{$tree->keys} != $tree->keysPerNode
ABCresult
1XX0
01X0
0000
0011
563 and $tree->keys->@* != $tree->keysPerNode)
564 0 {confess "Interior node not full: "
565 .$tree->name."\n". $tree->root->printKeys;
566 }
567  
568 73694 ▶ confess $tree->name unless $tree->isRoot or # Node is either a root or a left or right child
Branch: 1 branch
BranchTrueFalseTotal
unless $tree->isRoot or $tree->up and $tree->up->left and $tree == $tree->up->left or $tree->up and $tree->up->right and $tree == $tree->up->right 0 73694 73694
Condition66%12/18
$tree->isRoot or $tree->up and $tree->up->left and $tree == $tree->up->left or $tree->up and $tree->up->right and $tree == $tree->up->right
l!l&&r!l&&!r
37642360520
$tree->isRoot or $tree->up and $tree->up->left and $tree == $tree->up->left
l!l&&r!l&&!r
13323631036052
$tree->up and $tree->up->left and $tree == $tree->up->left
!ll&&!rl&&r
46003145236310
$tree->up and $tree->up->left
!ll&&!rl&&r
0460067762
$tree->up and $tree->up->right and $tree == $tree->up->right
!ll&&!rl&&r
0036052
$tree->up and $tree->up->right
!ll&&!rl&&r
0036052
MC/DC0%0/7
$tree->isRoot or $tree->up and $tree->up->left and $tree == $tree->up->left or $tree->up and $tree->up->right and $tree == $tree->up->right
$tree->isRoot $tree->up $tree->up->left $tree == $tree->up->left $tree->up $tree->up->right $tree == $tree->up->right
Truth table28%4/14
A or B and C and D or E and F and G
A= $tree->isRootB= $tree->upC= $tree->up->leftD= $tree == $tree->up->leftE= $tree->upF= $tree->up->rightG= $tree == $tree->up->right
ABCDEFGresult
1XXXXXX1
0111XXX1
00XX1111
010X1111
01101111
00XX0XX0
00XX10X0
00XX1100
010X0XX0
010X10X0
010X1100
01100XX0
011010X0
01101100
569 $tree->up && $tree->up->left && $tree == $tree->up->left or
570 $tree->up && $tree->up->right && $tree == $tree->up->right;
571  
572 73694 ▶ confess 'Left:'.$tree->name if $tree->left and # Left child has correct parent
Branch: 1 branch
BranchTrueFalseTotal
if $tree->left and !$tree->left->up || $tree->left->up != $tree 0 73694 73694
Condition50%3/6
$tree->left and !$tree->left->up || $tree->left->up != $tree
!ll&&!rl&&r
37384363100
not $tree->left->up or $tree->left->up != $tree
l!l&&r!l&&!r
0036310
MC/DC0%0/3
$tree->left and !$tree->left->up || $tree->left->up != $tree
$tree->left not $tree->left->up $tree->left->up != $tree
Truth table50%2/4
A and not(B) or C
A= $tree->leftB= not $tree->left->upC= $tree->left->up != $tree
ABCresult
0XX0
1000
11X1
1011
573 !$tree->left->up || $tree->left->up != $tree;
574  
575 73694 ▶ confess 'Right:'.$tree->name if $tree->right and # Right child has correct parent
Branch: 1 branch
BranchTrueFalseTotal
if $tree->right and !$tree->right->up || $tree->right->up != $tree 0 73694 73694
Condition50%3/6
$tree->right and !$tree->right->up || $tree->right->up != $tree
!ll&&!rl&&r
37642360520
not $tree->right->up or $tree->right->up != $tree
l!l&&r!l&&!r
0036052
MC/DC0%0/3
$tree->right and !$tree->right->up || $tree->right->up != $tree
$tree->right not $tree->right->up $tree->right->up != $tree
Truth table50%2/4
A and not(B) or C
A= $tree->rightB= not $tree->right->upC= $tree->right->up != $tree
ABCresult
0XX0
1000
11X1
1011
576 !$tree->right->up || $tree->right->up != $tree;
577  
578 73694 ▶ if ($tree->simplex and !$tree->simplexWithLeaf and $tree->up # Simplex children must always have duplex parents
Branch: 1 branch
BranchTrueFalseTotal
if ($tree->simplex and not $tree->simplexWithLeaf and $tree->up and not $tree->up->isRoot and not $tree->up->duplex) 0 73694 73694
Condition75%9/12
$tree->simplex and not $tree->simplexWithLeaf and $tree->up and not $tree->up->isRoot and not $tree->up->duplex
!ll&&!rl&&r
7369400
$tree->simplex and not $tree->simplexWithLeaf and $tree->up and not $tree->up->isRoot
!ll&&!rl&&r
7368860
$tree->simplex and not $tree->simplexWithLeaf and $tree->up
!ll&&!rl&&r
73656326
$tree->simplex and not $tree->simplexWithLeaf
!ll&&!rl&&r
64236942038
MC/DC0%0/5
$tree->simplex and not $tree->simplexWithLeaf and $tree->up and not $tree->up->isRoot and not $tree->up->duplex
$tree->simplex not $tree->simplexWithLeaf $tree->up not $tree->up->isRoot not $tree->up->duplex
Truth table66%4/6
A and not(B) and C and not(D) and not(E)
A= $tree->simplexB= not $tree->simplexWithLeafC= $tree->upD= not $tree->up->isRootE= not $tree->up->duplex
ABCDEresult
0XXXX0
10XXX0
110XX0
1110X0
111100
111111
579 and !$tree->up->isRoot and !$tree->up->duplex)
580 0 {confess "Simplex does not have duplex parent: ".$tree->name
581 ."\n".$tree->root->printKeys;
582 }
583  
584 73694 ▶ $maxHeight = $tree->height if $tree->height > $maxHeight;
Branch: 1 branch
BranchTrueFalseTotal
if $tree->height > $maxHeight 9677 64017 73694
585  
586 73694 my @k = $tree->keys->@*; # Check keys
587 73694 ▶ @k <= $tree->keysPerNode or confess "Too many keys:".scalar(@k);
Branch: 1 branch
BranchTrueFalseTotal
@k <= $tree->keysPerNode or confess('Too many keys:' . scalar(@k)) 73694 0 73694
588 73694 for my $i(keys @k)
589 147852 ▶ {confess "undef key position $i" unless defined $k[$i];
Branch: 1 branch
BranchTrueFalseTotal
unless defined $k[$i] 0 147852 147852
590 }
591  
592 73694 my @d = $tree->data->@*; # Check data
593 73694 ▶ @d <= $tree->keysPerNode or confess "Too many data:".scalar(@d);
Branch: 1 branch
BranchTrueFalseTotal
@d <= $tree->keysPerNode or confess('Too many data:' . scalar(@d)) 73694 0 73694
594  
595 73694 my %k;
596 73694 for my $i(1..$#k)
597 74161 ▶ {confess "Out of order: ", dump(\@k) if $k[$i-1] >= $k[$i];
Branch: 1 branch
BranchTrueFalseTotal
if $k[$i - 1] >= $k[$i] 0 74161 74161
598 74161 ▶ confess "Duplicate key: ", $k[$i] if $k{$k[$i]}++;
Branch: 1 branch
BranchTrueFalseTotal
if $k{$k[$i]}++ 0 74161 74161
599 74161 ▶ confess "Undefined data: ", $k[$i] unless defined $d[$i];
Branch: 1 branch
BranchTrueFalseTotal
unless defined $d[$i] 0 74161 74161
600 }
601 1332 }->($tree);
602  
603 1332 ▶ if ($tree->height < $maxHeight) # Check tree heights
Branch: 1 branch
BranchTrueFalseTotal
if ($tree->height < $maxHeight) 0 1332 1332
604 0 {cluck "Tree height failure at: ", $tree->name;
605 0 save($tree);
606 }
607 } # check
608  
609 sub checkAgainstHash($%) #P Check a tree against a hash.
610 908 ▶ {my ($t, %t) = @_; # Tree, expected
Subroutine checkAgainstHash: called CC=5 SCAR=16.3
Pod documented
611  
612 908 for my $k(keys %t) # Check we can find all the keys expected
613 97914 {my ($t) = @_;
614 97914 my $v = $t{$k};
615 97914 ▶ confess "Cannot find $k" unless my $f = find($t, $k);
Branch: 1 branch
BranchTrueFalseTotal
unless my $f = &find($t, $k) 0 97914 97914
616 97914 ▶ confess "Found $f but expected $v" unless $f == $v;
Branch: 1 branch
BranchTrueFalseTotal
unless $f == $v 0 97914 97914
617 }
618  
619 sub # Check that the tree does not contain unexpected keys
620 88474 ▶ {my ($t) = @_;
Subroutine __ANON__: called CC=4 SCAR=13.9
621 88474 ▶ return unless $t;
Branch: 1 branch
BranchTrueFalseTotal
unless $t 44691 43783 88474
622  
623 43783 __SUB__->($t->left); # Left
624 43783 for($t->keys->@*)
625 97914 ▶ {confess $_ unless delete $t{$_};
Branch: 1 branch
BranchTrueFalseTotal
unless delete $t{$_} 0 97914 97914
626 }
627 43783 __SUB__->($t->right); # Right
628 908 }->($t);
629  
630 908 ▶ confess if keys %t; # They should have all been deleted
Branch: 1 branch
BranchTrueFalseTotal
if CORE::keys %t 0 908 908
631 } # checkAgainstHash
632 #d
633 #-------------------------------------------------------------------------------
634 # Export - eeee
635 #-------------------------------------------------------------------------------
636  
637 1 ▶use Exporter qw(import);
Subroutine BEGIN: called CC=1 SCAR=0.0
638  
639 1 ▶use vars qw(@ISA @EXPORT @EXPORT_OK %EXPORT_TAGS);
Subroutine BEGIN: called CC=1 SCAR=0.0
640  
641 1 @ISA = qw(Exporter);
642 1 @EXPORT = qw();
643 1 @EXPORT_OK = qw(
644 );
645 1 %EXPORT_TAGS = (all=>[@EXPORT, @EXPORT_OK]);
646  
647 # podDocumentation
648 =pod
649  
650 =encoding utf-8
651  
652 =head1 Name
653  
654 Tree::Bulk - Bulk Tree operations
655  
656 =head1 Synopsis
657  
658 Bulk trees store several (key,data) pairs in each node of a balanced tree to
659 reduce the number of tree pointers: up, left, right, etc. used to maintain the
660 tree. This has no useful effect in Perl code, but in C code, especially C code
661 that uses SIMD instructions, the savings in space can be considerable which
662 allows the processor caches to be used more effectively. This module
663 demonstrates insert, find, delete operations on bulk trees as a basis for
664 coding these algorithms more efficiently in assembler code.
665  
666 is_deeply $t->printKeys, <<END;
667 SA0 4 1 2 3 4
668 Lz2 1 5 6 7 8->9 10 11 12
669 Rd1 3 9 10 11 12->1 2 3 4
670 Lz3 1 13 14 15 16->17 18 19 20
671 Rd2 2 17 18 19 20->9 10 11 12
672 Rz3 1 21 22->17 18 19 20
673 END
674  
675 for my $n($t->inorder)
676 {$n->setKeysPerNode(2);
677 }
678  
679 is_deeply $t->printKeys, <<END;
680 SA0 5 1 2
681 Lz3 1 3 4->5 6
682 Ld2 2 5 6->9 10
683 Rz3 1 7 8->5 6
684 Rd1 4 9 10->1 2
685 Lz4 1 11 12->13 14
686 Ld3 2 13 14->17 18
687 Rz4 1 15 16->13 14
688 Rd2 3 17 18->9 10
689 Rr3 2 19 20->17 18
690 Rz4 1 21 22->19 20
691 END
692  
693 =head1 Description
694  
695 Bulk Tree operations
696  
697  
698 Version "20240415".
699  
700  
701 The following sections describe the methods in each functional area of this
702 module. For an alphabetic listing of all methods by name see L<Index|/Index>.
703  
704  
705  
706 =head1 Bulk Tree
707  
708 Bulk Tree
709  
710 =head2 isRoot  ($tree)
711  
712 Return the tree if it is the root
713  
714 Parameter Description
715 1 $tree Tree
716  
717 B<Example:>
718  
719  
720 if (1)
721 {lll "Attributes";
722 my $t = Tree::Bulk::new->setKeysPerNode(1);
723 my $b = $t->insert(2,4);
724 my $a = $t->insert(1,2);
725 my $c = $t->insert(3,6);
726 ok $a->isLeftChild;
727 ok $c->isRightChild;
728 ok !$a->isRightChild;
729 ok !$c->isLeftChild;
730  
731 ok $b->isRoot; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
732  
733  
734 ok !$a->isRoot; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
735  
736  
737 ok !$c->isRoot; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
738  
739 ok $a->leaf;
740 ok $c->leaf;
741 ok $b->duplex;
742 ok $c->root == $b;
743 ok $c->root != $a;
744 }
745  
746  
747 =head2 root($tree)
748  
749 Return the root node of a tree
750  
751 Parameter Description
752 1 $tree Tree
753  
754 B<Example:>
755  
756  
757 if (1)
758 {lll "Attributes";
759 my $t = Tree::Bulk::new->setKeysPerNode(1);
760 my $b = $t->insert(2,4);
761 my $a = $t->insert(1,2);
762 my $c = $t->insert(3,6);
763 ok $a->isLeftChild;
764 ok $c->isRightChild;
765 ok !$a->isRightChild;
766 ok !$c->isLeftChild;
767 ok $b->isRoot;
768 ok !$a->isRoot;
769 ok !$c->isRoot;
770 ok $a->leaf;
771 ok $c->leaf;
772 ok $b->duplex;
773  
774 ok $c->root == $b; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
775  
776  
777 ok $c->root != $a; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
778  
779 }
780  
781  
782 =head2 leaf($tree)
783  
784 Return the tree if it is a leaf
785  
786 Parameter Description
787 1 $tree Tree
788  
789 B<Example:>
790  
791  
792 if (1)
793 {lll "Attributes";
794 my $t = Tree::Bulk::new->setKeysPerNode(1);
795 my $b = $t->insert(2,4);
796 my $a = $t->insert(1,2);
797 my $c = $t->insert(3,6);
798 ok $a->isLeftChild;
799 ok $c->isRightChild;
800 ok !$a->isRightChild;
801 ok !$c->isLeftChild;
802 ok $b->isRoot;
803 ok !$a->isRoot;
804 ok !$c->isRoot;
805  
806 ok $a->leaf; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
807  
808  
809 ok $c->leaf; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
810  
811 ok $b->duplex;
812 ok $c->root == $b;
813 ok $c->root != $a;
814 }
815  
816  
817 =head2 duplex  ($tree)
818  
819 Return the tree if it has left and right children
820  
821 Parameter Description
822 1 $tree Tree
823  
824 B<Example:>
825  
826  
827 if (1)
828 {lll "Attributes";
829 my $t = Tree::Bulk::new->setKeysPerNode(1);
830 my $b = $t->insert(2,4);
831 my $a = $t->insert(1,2);
832 my $c = $t->insert(3,6);
833 ok $a->isLeftChild;
834 ok $c->isRightChild;
835 ok !$a->isRightChild;
836 ok !$c->isLeftChild;
837 ok $b->isRoot;
838 ok !$a->isRoot;
839 ok !$c->isRoot;
840 ok $a->leaf;
841 ok $c->leaf;
842  
843 ok $b->duplex; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
844  
845 ok $c->root == $b;
846 ok $c->root != $a;
847 }
848  
849  
850 =head2 simplex ($tree)
851  
852 Return the tree if it has either a left child or a right child but not both.
853  
854 Parameter Description
855 1 $tree Tree
856  
857 B<Example:>
858  
859  
860 if (1)
861 {lll "SetHeights";
862 my $a = node(1,1)->setKeysPerNode(1);
863 my $b = node(2,2)->setKeysPerNode(1);
864 my $c = node(3,3)->setKeysPerNode(1);
865 my $d = node(4,4)->setKeysPerNode(1);
866 my $e = node(5,5);
867 $a->right = $b; $b->up = $a;
868 $b->right = $c; $c->up = $b;
869 $c->right = $d; $d->up = $c;
870 $d->right = $e; $e->up = $d;
871  
872 is_deeply $a->printKeys, <<END;
873 SA0 1 1
874 Rr1 1 2->1
875 Rr2 1 3->2
876 Rr3 1 4->3
877 Rz4 1 5->4
878 END
879 #save $a;
880  
881 $e->setHeights(1);
882 is_deeply $a->printKeys, <<END;
883 SA0 4 1
884 Rr1 3 2->1
885 Lz3 1 3->4
886 Rd2 2 4->2
887 Rz3 1 5->4
888 END
889 #save $a;
890  
891 ok $b->simplex; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
892  
893  
894 ok !$c->simplex; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
895  
896  
897 $c->balance;
898 is_deeply $a->printKeys, <<END;
899 SA0 4 1
900 Rr1 3 2->1
901 Lz3 1 3->4
902 Rd2 2 4->2
903 Rz3 1 5->4
904 END
905 #save $a;
906  
907 $b->balance;
908 is_deeply $a->printKeys, <<END;
909 SA0 4 1
910 Lr2 2 2->4
911 Rz3 1 3->2
912 Rd1 3 4->1
913 Rz2 1 5->4
914 END
915 #save $a;
916 }
917  
918  
919 =head2 simplexWithLeaf ($tree)
920  
921 Return the tree if it has either a left child or a right child but not both and the child it has a leaf.
922  
923 Parameter Description
924 1 $tree Tree
925  
926 B<Example:>
927  
928  
929 if (1)
930 {lll "Balance";
931 my $a = node(1,1)->setKeysPerNode(1); $a->height = 5;
932 my $b = node(2,2)->setKeysPerNode(1); $b->height = 4;
933 my $c = node(3,3)->setKeysPerNode(1); $c->height = 3;
934 my $d = node(4,4)->setKeysPerNode(1); $d->height = 2;
935 my $e = node(5,5); $e->height = 1;
936 $a->right = $b; $b->up = $a;
937 $b->right = $c; $c->up = $b;
938 $c->right = $d; $d->up = $c;
939 $d->right = $e; $e->up = $d;
940  
941 $e->balance;
942 is_deeply $a->printKeys, <<END;
943 SA0 5 1
944 Rr1 4 2->1
945 Rr2 3 3->2
946 Rr3 2 4->3
947 Rz4 1 5->4
948 END
949 #save $a;
950  
951 ok $d->simplexWithLeaf; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
952  
953  
954 ok !$c->simplexWithLeaf; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
955  
956  
957 $d->balance;
958 is_deeply $a->printKeys, <<END;
959 SA0 5 1
960 Rr1 4 2->1
961 Rr2 3 3->2
962 Rr3 2 4->3
963 Rz4 1 5->4
964 END
965 #save $a;
966  
967 $c->balance;
968 is_deeply $a->printKeys, <<END;
969 SA0 5 1
970 Rr1 3 2->1
971 Lz3 1 3->4
972 Rd2 2 4->2
973 Rz3 1 5->4
974 END
975 #save $a;
976  
977 $b->balance;
978 is_deeply $a->printKeys, <<END;
979 SA0 4 1
980 Lr2 2 2->4
981 Rz3 1 3->2
982 Rd1 3 4->1
983 Rz2 1 5->4
984 END
985 #save $a;
986 }
987  
988  
989 =head2 empty   ($tree)
990  
991 Return the tree if it is empty
992  
993 Parameter Description
994 1 $tree Tree
995  
996 B<Example:>
997  
998  
999 if (1)
1000 {lll "Balance";
1001 my $t = Tree::Bulk::new->setKeysPerNode(1);
1002  
1003 ok $t->empty; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1004  
1005 ok $t->singleton;
1006 }
1007  
1008  
1009 =head2 singleton   ($tree)
1010  
1011 Return the tree if it contains only the root node and nothing else
1012  
1013 Parameter Description
1014 1 $tree Tree
1015  
1016 B<Example:>
1017  
1018  
1019 if (1)
1020 {lll "Balance";
1021 my $t = Tree::Bulk::new->setKeysPerNode(1);
1022 ok $t->empty;
1023  
1024 ok $t->singleton; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1025  
1026 }
1027  
1028  
1029 =head2 isLeftChild ($tree)
1030  
1031 Return the tree if it is the left child
1032  
1033 Parameter Description
1034 1 $tree Tree
1035  
1036 B<Example:>
1037  
1038  
1039 if (1)
1040 {lll "Attributes";
1041 my $t = Tree::Bulk::new->setKeysPerNode(1);
1042 my $b = $t->insert(2,4);
1043 my $a = $t->insert(1,2);
1044 my $c = $t->insert(3,6);
1045  
1046 ok $a->isLeftChild; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1047  
1048 ok $c->isRightChild;
1049 ok !$a->isRightChild;
1050  
1051 ok !$c->isLeftChild; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1052  
1053 ok $b->isRoot;
1054 ok !$a->isRoot;
1055 ok !$c->isRoot;
1056 ok $a->leaf;
1057 ok $c->leaf;
1058 ok $b->duplex;
1059 ok $c->root == $b;
1060 ok $c->root != $a;
1061 }
1062  
1063  
1064 =head2 isRightChild($tree)
1065  
1066 Return the tree if it is the right child
1067  
1068 Parameter Description
1069 1 $tree Tree
1070  
1071 B<Example:>
1072  
1073  
1074 if (1)
1075 {lll "Attributes";
1076 my $t = Tree::Bulk::new->setKeysPerNode(1);
1077 my $b = $t->insert(2,4);
1078 my $a = $t->insert(1,2);
1079 my $c = $t->insert(3,6);
1080 ok $a->isLeftChild;
1081  
1082 ok $c->isRightChild; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1083  
1084  
1085 ok !$a->isRightChild; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1086  
1087 ok !$c->isLeftChild;
1088 ok $b->isRoot;
1089 ok !$a->isRoot;
1090 ok !$c->isRoot;
1091 ok $a->leaf;
1092 ok $c->leaf;
1093 ok $b->duplex;
1094 ok $c->root == $b;
1095 ok $c->root != $a;
1096 }
1097  
1098  
1099 =head2 name($tree)
1100  
1101 Name of a tree
1102  
1103 Parameter Description
1104 1 $tree Tree
1105  
1106 B<Example:>
1107  
1108  
1109 if (1)
1110 {lll "Split and Refill";
1111 my $N = 22;
1112 my $t = Tree::Bulk::new;
1113 for my $k(1..$N)
1114 {$t->insert($k, 2 * $k);
1115 }
1116  
1117  
1118 is_deeply $t->name, "1 2 3 4"; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1119  
1120  
1121 is_deeply $t->printKeys, <<END;
1122 SA0 4 1 2 3 4
1123 Lz2 1 5 6 7 8->9 10 11 12
1124 Rd1 3 9 10 11 12->1 2 3 4
1125 Lz3 1 13 14 15 16->17 18 19 20
1126 Rd2 2 17 18 19 20->9 10 11 12
1127 Rz3 1 21 22->17 18 19 20
1128 END
1129 #save $t;
1130  
1131 for my $n($t->inorder)
1132 {$n->setKeysPerNode(2);
1133 }
1134 is_deeply $t->printKeys, <<END;
1135 SA0 5 1 2
1136 Lz3 1 3 4->5 6
1137 Ld2 2 5 6->9 10
1138 Rz3 1 7 8->5 6
1139 Rd1 4 9 10->1 2
1140 Lz4 1 11 12->13 14
1141 Ld3 2 13 14->17 18
1142 Rz4 1 15 16->13 14
1143 Rd2 3 17 18->9 10
1144 Rr3 2 19 20->17 18
1145 Rz4 1 21 22->19 20
1146 END
1147 #save $t;
1148  
1149 for my $n($t->inorder)
1150 {$n->setKeysPerNode(1);
1151 }
1152 is_deeply $t->printKeys, <<END;
1153 SA0 6 1
1154 Lz4 1 2->3
1155 Ld3 2 3->5
1156 Rz4 1 4->3
1157 Ld2 3 5->9
1158 Lz4 1 6->7
1159 Rd3 2 7->5
1160 Rz4 1 8->7
1161 Rd1 5 9->1
1162 Lz5 1 10->11
1163 Ld4 2 11->13
1164 Rz5 1 12->11
1165 Ld3 3 13->17
1166 Lz5 1 14->15
1167 Rd4 2 15->13
1168 Rz5 1 16->15
1169 Rd2 4 17->9
1170 Lz4 1 18->19
1171 Rd3 3 19->17
1172 Lz5 1 20->21
1173 Rd4 2 21->19
1174 Rz5 1 22->21
1175 END
1176 #save $t;
1177  
1178 $_->setKeysPerNode(2) for $t->inorder;
1179 is_deeply $t->printKeys, <<END;
1180 SA0 5 1 2
1181 Lz3 1 3 4->5 6
1182 Ld2 2 5 6->9 10
1183 Rz3 1 7 8->5 6
1184 Rd1 4 9 10->1 2
1185 Lz4 1 11 12->13 14
1186 Ld3 2 13 14->17 18
1187 Rz4 1 15 16->13 14
1188 Rd2 3 17 18->9 10
1189 Lz4 1 19 20->21 22
1190 Rl3 2 21 22->17 18
1191 END
1192 #save $t;
1193  
1194 $_->setKeysPerNode(4) for $t->inorder;
1195 is_deeply $t->printKeys, <<END;
1196 SA0 4 1 2 3 4
1197 Lz2 1 5 6 7 8->9 10 11 12
1198 Rd1 3 9 10 11 12->1 2 3 4
1199 Lz3 1 13 14 15 16->17 18 19 20
1200 Rd2 2 17 18 19 20->9 10 11 12
1201 Rz3 1 21 22->17 18 19 20
1202 END
1203 #save $t;
1204 }
1205  
1206  
1207 =head2 names   ($tree)
1208  
1209 Names of all nodes in a tree in order
1210  
1211 Parameter Description
1212 1 $tree Tree
1213  
1214 B<Example:>
1215  
1216  
1217 if (1)
1218 {my sub randomLoad($$$) # Randomly load different size nodes
1219 {my ($N, $keys, $height) = @_; # Number of elements, number of keys per node, expected height
1220  
1221 lll "Random load $keys";
1222  
1223 srand(1); # Same randomization
1224 my $t = Tree::Bulk::new->setKeysPerNode($keys);
1225 for my $r(randomizeArray 1..$N)
1226 {$t->insert($r, 2 * $r);
1227 $t->check;
1228 }
1229  
1230 is_deeply $t->actualHeight, $height; # Check height
1231 confess unless $t->actualHeight == $height;
1232  
1233 is_deeply join(' ', 1..$N), $t->names; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1234  
1235  
1236 my %t = map {$_=>2*$_} 1..$N;
1237 for my $r(randomizeArray 1..$N) # Delete in random order
1238 {$t->delete ($r);
1239 delete $t{$r};
1240 checkAgainstHash $t, %t;
1241 check($t);
1242 }
1243  
1244 ok $t->empty;
1245 is_deeply $t->actualHeight, 1;
1246 }
1247  
1248 randomLoad(222, 1, 11); # Random loads
1249 randomLoad(222, 8, 8);
1250 randomLoad(222, 4, 9);
1251 }
1252  
1253  
1254 =head2 balance ($t)
1255  
1256 Balance a node
1257  
1258 Parameter Description
1259 1 $t Tree
1260  
1261 B<Example:>
1262  
1263  
1264 if (1)
1265 {lll "Balance";
1266 my $t = Tree::Bulk::new->setKeysPerNode(1);
1267  
1268 my $a = node(1,2) ->setKeysPerNode(1);
1269 my $b = node(2,4) ->setKeysPerNode(1);
1270 my $c = node(6,12)->setKeysPerNode(1);
1271 my $d = node(5,10)->setKeysPerNode(1);
1272 my $e = node(4,8) ->setKeysPerNode(1);
1273 my $f = node(3,6) ->setKeysPerNode(1);
1274 $a->right = $b; $b->up = $a;
1275 $b->right = $c; $c->up = $b;
1276 $c->left = $d; $d->up = $c;
1277 $d->left = $e; $e->up = $d;
1278 $e->left = $f; $f->up = $e;
1279 $f->setHeights(1);
1280 is_deeply $a->printKeys, <<END;
1281 SA0 4 1
1282 Lr2 2 2->4
1283 Rz3 1 3->2
1284 Rd1 3 4->1
1285 Lz3 1 5->6
1286 Rl2 2 6->4
1287 END
1288 #save $a;
1289  
1290  
1291 $b->balance; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1292  
1293 is_deeply $a->printKeys, <<END;
1294 SA0 4 1
1295 Lr2 2 2->4
1296 Rz3 1 3->2
1297 Rd1 3 4->1
1298 Lz3 1 5->6
1299 Rl2 2 6->4
1300 END
1301 #save $a;
1302 }
1303  
1304  
1305 =head2 insert  ($tree, $key, $data)
1306  
1307 Insert a key and some data into a tree
1308  
1309 Parameter Description
1310 1 $tree Tree
1311 2 $key Key
1312 3 $data Data
1313  
1314 B<Example:>
1315  
1316  
1317 if (1)
1318 {lll "Insert";
1319 my $N = 23;
1320 my $t = Tree::Bulk::new->setKeysPerNode(1);
1321 for(1..$N)
1322  
1323 {$t->insert($_, 2 * $_); # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1324  
1325 }
1326  
1327 is_deeply $t->printKeys, <<END;
1328 SA0 8 1
1329 Lz4 1 2->3
1330 Ld3 2 3->5
1331 Rz4 1 4->3
1332 Ld2 3 5->9
1333 Lz4 1 6->7
1334 Rd3 2 7->5
1335 Rz4 1 8->7
1336 Rd1 7 9->1
1337 Lz4 1 10->11
1338 Ld3 2 11->13
1339 Rz4 1 12->11
1340 Rd2 6 13->9
1341 Lz5 1 14->15
1342 Ld4 2 15->17
1343 Rz5 1 16->15
1344 Rd3 5 17->13
1345 Lz5 1 18->19
1346 Rd4 4 19->17
1347 Lz6 1 20->21
1348 Rd5 3 21->19
1349 Rr6 2 22->21
1350 Rz7 1 23->22
1351 END
1352 #save $t;
1353 ok $t->height == 8;
1354 }
1355  
1356  
1357 =head2 find($tree, $key)
1358  
1359 Find a key in a tree and returns its data
1360  
1361 Parameter Description
1362 1 $tree Tree
1363 2 $key Key
1364  
1365 B<Example:>
1366  
1367  
1368 if (1)
1369 {my $t = Tree::Bulk::new;
1370 $t->insert($_, $_*$_) for 1..20;
1371  
1372 ok !find($t, 0); # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1373  
1374  
1375 ok !find($t, 21); # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1376  
1377  
1378 ok find($t, $_) == $_ * $_ for qw(1 5 10 11 15 20); # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1379  
1380 }
1381  
1382  
1383 =head2 first   ($n)
1384  
1385 First node in a tree
1386  
1387 Parameter Description
1388 1 $n Tree
1389  
1390 B<Example:>
1391  
1392  
1393 if (1)
1394 {my $N = 220;
1395 my $t = Tree::Bulk::new;
1396  
1397 for(reverse 1..$N)
1398 {$t->insert($_, 2*$_);
1399 }
1400  
1401 is_deeply $t->actualHeight, 10;
1402  
1403 if (1)
1404 {my @n;
1405  
1406 for (my $n = $t->first; $n; $n = $n->next) # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1407  
1408 {push @n, $n->keys->@*
1409 }
1410 is_deeply \@n, [1..$N];
1411 }
1412  
1413 if (1)
1414 {my @p;
1415 for my $p(reverse $t->inorder)
1416 {push @p, reverse $p->keys->@*;
1417 }
1418 is_deeply \@p, [reverse 1..$N];
1419 }
1420  
1421 my @p;
1422 for(my $p = $t->last; $p; $p = $p->prev)
1423 {push @p, reverse $p->keys->@*
1424 }
1425 is_deeply \@p, [reverse 1..$N];
1426  
1427 my %t = map {$_=>2*$_} 1..$N;
1428 for my $i(0..3)
1429 {for my $j(map {4 * $_-$i} 1..$N/4)
1430 {$t->delete ($j);
1431 delete $t{$j};
1432 checkAgainstHash $t, %t;
1433 }
1434 }
1435  
1436 ok $t->empty;
1437 is_deeply $t->actualHeight, 1;
1438 }
1439  
1440  
1441 =head2 last($n)
1442  
1443 Last node in a tree
1444  
1445 Parameter Description
1446 1 $n Tree
1447  
1448 B<Example:>
1449  
1450  
1451 if (1)
1452 {my $N = 220;
1453 my $t = Tree::Bulk::new;
1454  
1455 for(reverse 1..$N)
1456 {$t->insert($_, 2*$_);
1457 }
1458  
1459 is_deeply $t->actualHeight, 10;
1460  
1461 if (1)
1462 {my @n;
1463 for (my $n = $t->first; $n; $n = $n->next)
1464 {push @n, $n->keys->@*
1465 }
1466 is_deeply \@n, [1..$N];
1467 }
1468  
1469 if (1)
1470 {my @p;
1471 for my $p(reverse $t->inorder)
1472 {push @p, reverse $p->keys->@*;
1473 }
1474 is_deeply \@p, [reverse 1..$N];
1475 }
1476  
1477 my @p;
1478  
1479 for(my $p = $t->last; $p; $p = $p->prev) # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1480  
1481 {push @p, reverse $p->keys->@*
1482 }
1483 is_deeply \@p, [reverse 1..$N];
1484  
1485 my %t = map {$_=>2*$_} 1..$N;
1486 for my $i(0..3)
1487 {for my $j(map {4 * $_-$i} 1..$N/4)
1488 {$t->delete ($j);
1489 delete $t{$j};
1490 checkAgainstHash $t, %t;
1491 }
1492 }
1493  
1494 ok $t->empty;
1495 is_deeply $t->actualHeight, 1;
1496 }
1497  
1498  
1499 =head2 next($tree)
1500  
1501 Next node in order
1502  
1503 Parameter Description
1504 1 $tree Tree
1505  
1506 B<Example:>
1507  
1508  
1509 if (1)
1510 {my $N = 220;
1511 my $t = Tree::Bulk::new;
1512  
1513 for(reverse 1..$N)
1514 {$t->insert($_, 2*$_);
1515 }
1516  
1517 is_deeply $t->actualHeight, 10;
1518  
1519 if (1)
1520 {my @n;
1521  
1522 for (my $n = $t->first; $n; $n = $n->next) # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1523  
1524 {push @n, $n->keys->@*
1525 }
1526 is_deeply \@n, [1..$N];
1527 }
1528  
1529 if (1)
1530 {my @p;
1531 for my $p(reverse $t->inorder)
1532 {push @p, reverse $p->keys->@*;
1533 }
1534 is_deeply \@p, [reverse 1..$N];
1535 }
1536  
1537 my @p;
1538 for(my $p = $t->last; $p; $p = $p->prev)
1539 {push @p, reverse $p->keys->@*
1540 }
1541 is_deeply \@p, [reverse 1..$N];
1542  
1543 my %t = map {$_=>2*$_} 1..$N;
1544 for my $i(0..3)
1545 {for my $j(map {4 * $_-$i} 1..$N/4)
1546 {$t->delete ($j);
1547 delete $t{$j};
1548 checkAgainstHash $t, %t;
1549 }
1550 }
1551  
1552 ok $t->empty;
1553 is_deeply $t->actualHeight, 1;
1554 }
1555  
1556  
1557 =head2 prev($tree)
1558  
1559 Previous node in order
1560  
1561 Parameter Description
1562 1 $tree Tree
1563  
1564 B<Example:>
1565  
1566  
1567 if (1)
1568 {my $N = 220;
1569 my $t = Tree::Bulk::new;
1570  
1571 for(reverse 1..$N)
1572 {$t->insert($_, 2*$_);
1573 }
1574  
1575 is_deeply $t->actualHeight, 10;
1576  
1577 if (1)
1578 {my @n;
1579 for (my $n = $t->first; $n; $n = $n->next)
1580 {push @n, $n->keys->@*
1581 }
1582 is_deeply \@n, [1..$N];
1583 }
1584  
1585 if (1)
1586 {my @p;
1587 for my $p(reverse $t->inorder)
1588 {push @p, reverse $p->keys->@*;
1589 }
1590 is_deeply \@p, [reverse 1..$N];
1591 }
1592  
1593 my @p;
1594  
1595 for(my $p = $t->last; $p; $p = $p->prev) # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1596  
1597 {push @p, reverse $p->keys->@*
1598 }
1599 is_deeply \@p, [reverse 1..$N];
1600  
1601 my %t = map {$_=>2*$_} 1..$N;
1602 for my $i(0..3)
1603 {for my $j(map {4 * $_-$i} 1..$N/4)
1604 {$t->delete ($j);
1605 delete $t{$j};
1606 checkAgainstHash $t, %t;
1607 }
1608 }
1609  
1610 ok $t->empty;
1611 is_deeply $t->actualHeight, 1;
1612 }
1613  
1614  
1615 =head2 inorder ($tree)
1616  
1617 Return a list of all the nodes in a tree in order
1618  
1619 Parameter Description
1620 1 $tree Tree
1621  
1622 B<Example:>
1623  
1624  
1625 if (1)
1626 {my $N = 220;
1627 my $t = Tree::Bulk::new;
1628  
1629 for(reverse 1..$N)
1630 {$t->insert($_, 2*$_);
1631 }
1632  
1633 is_deeply $t->actualHeight, 10;
1634  
1635 if (1)
1636 {my @n;
1637 for (my $n = $t->first; $n; $n = $n->next)
1638 {push @n, $n->keys->@*
1639 }
1640 is_deeply \@n, [1..$N];
1641 }
1642  
1643 if (1)
1644 {my @p;
1645  
1646 for my $p(reverse $t->inorder) # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1647  
1648 {push @p, reverse $p->keys->@*;
1649 }
1650 is_deeply \@p, [reverse 1..$N];
1651 }
1652  
1653 my @p;
1654 for(my $p = $t->last; $p; $p = $p->prev)
1655 {push @p, reverse $p->keys->@*
1656 }
1657 is_deeply \@p, [reverse 1..$N];
1658  
1659 my %t = map {$_=>2*$_} 1..$N;
1660 for my $i(0..3)
1661 {for my $j(map {4 * $_-$i} 1..$N/4)
1662 {$t->delete ($j);
1663 delete $t{$j};
1664 checkAgainstHash $t, %t;
1665 }
1666 }
1667  
1668 ok $t->empty;
1669 is_deeply $t->actualHeight, 1;
1670 }
1671  
1672  
1673 =head2 delete  ($tree, $key)
1674  
1675 Delete a key in a tree
1676  
1677 Parameter Description
1678 1 $tree Tree
1679 2 $key Key
1680  
1681 B<Example:>
1682  
1683  
1684 if (1)
1685 {lll "Delete";
1686 my $N = 28;
1687 my $t = Tree::Bulk::new->setKeysPerNode(1);
1688 for(1..$N)
1689 {$t->insert($_, 2 * $_);
1690 }
1691  
1692 is_deeply $t->printKeys, <<END;
1693 SA0 8 1
1694 Lz4 1 2->3
1695 Ld3 2 3->5
1696 Rz4 1 4->3
1697 Ld2 3 5->9
1698 Lz4 1 6->7
1699 Rd3 2 7->5
1700 Rz4 1 8->7
1701 Rd1 7 9->1
1702 Lz5 1 10->11
1703 Ld4 2 11->13
1704 Rz5 1 12->11
1705 Ld3 3 13->17
1706 Lz5 1 14->15
1707 Rd4 2 15->13
1708 Rz5 1 16->15
1709 Rd2 6 17->9
1710 Lz5 1 18->19
1711 Ld4 2 19->21
1712 Rz5 1 20->19
1713 Rd3 5 21->17
1714 Lz5 1 22->23
1715 Rd4 4 23->21
1716 Lz6 1 24->25
1717 Rd5 3 25->23
1718 Lz7 1 26->27
1719 Rd6 2 27->25
1720 Rz7 1 28->27
1721 END
1722 #save $t;
1723  
1724 for my $k(reverse 1..$N)
1725  
1726 {$t->delete($k); # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1727  
1728 is_deeply $t->printKeys, <<END if $k == 17;
1729 SA0 5 1
1730 Lz4 1 2->3
1731 Ld3 2 3->5
1732 Rz4 1 4->3
1733 Ld2 3 5->9
1734 Lz4 1 6->7
1735 Rd3 2 7->5
1736 Rz4 1 8->7
1737 Rd1 4 9->1
1738 Lz4 1 10->11
1739 Ld3 2 11->13
1740 Rz4 1 12->11
1741 Rd2 3 13->9
1742 Lz4 1 14->15
1743 Rd3 2 15->13
1744 Rz4 1 16->15
1745 END
1746 #save $t if $k == 17;
1747  
1748 is_deeply $t->printKeys, <<END if $k == 9;
1749 SA0 4 1
1750 Lz3 1 2->3
1751 Ld2 2 3->5
1752 Rz3 1 4->3
1753 Rd1 3 5->1
1754 Lz3 1 6->7
1755 Rd2 2 7->5
1756 Rz3 1 8->7
1757 END
1758 #save $t if $k == 9;
1759  
1760 is_deeply $t->printKeys, <<END if $k == 6;
1761 SA0 4 1
1762 Lz2 1 2->3
1763 Rd1 3 3->1
1764 Lz3 1 4->5
1765 Rl2 2 5->3
1766 END
1767 #save $t if $k == 6;
1768  
1769 is_deeply $t->printKeys, <<END if $k == 4;
1770 SA0 3 1
1771 Rr1 2 2->1
1772 Rz2 1 3->2
1773 END
1774 #save $t if $k == 4;
1775  
1776 is_deeply $t->printKeys, <<END if $k == 3;
1777 SA0 2 1
1778 Rz1 1 2->1
1779 END
1780 #save $t if $k == 3;
1781  
1782 is_deeply $t->printKeys, <<END if $k == 1;
1783 Sz0 1
1784 END
1785 #save $t if $k == 1;
1786 }
1787 }
1788  
1789  
1790 =head2 printKeys   ($t)
1791  
1792 Print the keys in a tree
1793  
1794 Parameter Description
1795 1 $t Tree
1796  
1797 B<Example:>
1798  
1799  
1800 if (1)
1801 {lll "Insert";
1802 my $N = 23;
1803 my $t = Tree::Bulk::new->setKeysPerNode(1);
1804 for(1..$N)
1805 {$t->insert($_, 2 * $_);
1806 }
1807  
1808  
1809 is_deeply $t->printKeys, <<END; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1810  
1811 SA0 8 1
1812 Lz4 1 2->3
1813 Ld3 2 3->5
1814 Rz4 1 4->3
1815 Ld2 3 5->9
1816 Lz4 1 6->7
1817 Rd3 2 7->5
1818 Rz4 1 8->7
1819 Rd1 7 9->1
1820 Lz4 1 10->11
1821 Ld3 2 11->13
1822 Rz4 1 12->11
1823 Rd2 6 13->9
1824 Lz5 1 14->15
1825 Ld4 2 15->17
1826 Rz5 1 16->15
1827 Rd3 5 17->13
1828 Lz5 1 18->19
1829 Rd4 4 19->17
1830 Lz6 1 20->21
1831 Rd5 3 21->19
1832 Rr6 2 22->21
1833 Rz7 1 23->22
1834 END
1835 #save $t;
1836 ok $t->height == 8;
1837 }
1838  
1839  
1840 =head2 setKeysPerNode  ($tree, $N)
1841  
1842 Set the number of keys for the current node
1843  
1844 Parameter Description
1845 1 $tree Tree
1846 2 $N Keys per node to be set
1847  
1848 B<Example:>
1849  
1850  
1851 if (1)
1852 {lll "Split and Refill";
1853 my $N = 22;
1854 my $t = Tree::Bulk::new;
1855 for my $k(1..$N)
1856 {$t->insert($k, 2 * $k);
1857 }
1858  
1859 is_deeply $t->name, "1 2 3 4";
1860  
1861 is_deeply $t->printKeys, <<END;
1862 SA0 4 1 2 3 4
1863 Lz2 1 5 6 7 8->9 10 11 12
1864 Rd1 3 9 10 11 12->1 2 3 4
1865 Lz3 1 13 14 15 16->17 18 19 20
1866 Rd2 2 17 18 19 20->9 10 11 12
1867 Rz3 1 21 22->17 18 19 20
1868 END
1869 #save $t;
1870  
1871 for my $n($t->inorder)
1872  
1873 {$n->setKeysPerNode(2); # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1874  
1875 }
1876 is_deeply $t->printKeys, <<END;
1877 SA0 5 1 2
1878 Lz3 1 3 4->5 6
1879 Ld2 2 5 6->9 10
1880 Rz3 1 7 8->5 6
1881 Rd1 4 9 10->1 2
1882 Lz4 1 11 12->13 14
1883 Ld3 2 13 14->17 18
1884 Rz4 1 15 16->13 14
1885 Rd2 3 17 18->9 10
1886 Rr3 2 19 20->17 18
1887 Rz4 1 21 22->19 20
1888 END
1889 #save $t;
1890  
1891 for my $n($t->inorder)
1892  
1893 {$n->setKeysPerNode(1); # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1894  
1895 }
1896 is_deeply $t->printKeys, <<END;
1897 SA0 6 1
1898 Lz4 1 2->3
1899 Ld3 2 3->5
1900 Rz4 1 4->3
1901 Ld2 3 5->9
1902 Lz4 1 6->7
1903 Rd3 2 7->5
1904 Rz4 1 8->7
1905 Rd1 5 9->1
1906 Lz5 1 10->11
1907 Ld4 2 11->13
1908 Rz5 1 12->11
1909 Ld3 3 13->17
1910 Lz5 1 14->15
1911 Rd4 2 15->13
1912 Rz5 1 16->15
1913 Rd2 4 17->9
1914 Lz4 1 18->19
1915 Rd3 3 19->17
1916 Lz5 1 20->21
1917 Rd4 2 21->19
1918 Rz5 1 22->21
1919 END
1920 #save $t;
1921  
1922  
1923 $_->setKeysPerNode(2) for $t->inorder; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1924  
1925 is_deeply $t->printKeys, <<END;
1926 SA0 5 1 2
1927 Lz3 1 3 4->5 6
1928 Ld2 2 5 6->9 10
1929 Rz3 1 7 8->5 6
1930 Rd1 4 9 10->1 2
1931 Lz4 1 11 12->13 14
1932 Ld3 2 13 14->17 18
1933 Rz4 1 15 16->13 14
1934 Rd2 3 17 18->9 10
1935 Lz4 1 19 20->21 22
1936 Rl3 2 21 22->17 18
1937 END
1938 #save $t;
1939  
1940  
1941 $_->setKeysPerNode(4) for $t->inorder; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1942  
1943 is_deeply $t->printKeys, <<END;
1944 SA0 4 1 2 3 4
1945 Lz2 1 5 6 7 8->9 10 11 12
1946 Rd1 3 9 10 11 12->1 2 3 4
1947 Lz3 1 13 14 15 16->17 18 19 20
1948 Rd2 2 17 18 19 20->9 10 11 12
1949 Rz3 1 21 22->17 18 19 20
1950 END
1951 #save $t;
1952 }
1953  
1954  
1955 =head2 printKeysAndData($t)
1956  
1957 Print the mapping from keys to data in a tree
1958  
1959 Parameter Description
1960 1 $t Tree
1961  
1962 B<Example:>
1963  
1964  
1965 if (1)
1966 {my $N = 22;
1967 my $t = Tree::Bulk::new;
1968 ok $t->empty;
1969 ok $t->leaf;
1970  
1971 for(1..$N)
1972 {$t->insert($_, 2 * $_);
1973 }
1974  
1975 ok $t->right->duplex;
1976 is_deeply actualHeight($t), 4;
1977  
1978 is_deeply $t->printKeys, <<END;
1979 SA0 4 1 2 3 4
1980 Lz2 1 5 6 7 8->9 10 11 12
1981 Rd1 3 9 10 11 12->1 2 3 4
1982 Lz3 1 13 14 15 16->17 18 19 20
1983 Rd2 2 17 18 19 20->9 10 11 12
1984 Rz3 1 21 22->17 18 19 20
1985 END
1986 #save $t;
1987  
1988  
1989 is_deeply $t->printKeysAndData, <<END; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1990  
1991 1 2
1992 2 4
1993 3 6
1994 4 8
1995 5 10
1996 6 12
1997 7 14
1998 8 16
1999 9 18
2000 10 20
2001 11 22
2002 12 24
2003 13 26
2004 14 28
2005 15 30
2006 16 32
2007 17 34
2008 18 36
2009 19 38
2010 20 40
2011 21 42
2012 22 44
2013 END
2014  
2015 my %t = map {$_=>2*$_} 1..$N;
2016  
2017 for(map {2 * $_} 1..$N/2)
2018 {$t->delete($_);
2019 delete $t{$_};
2020 checkAgainstHash $t, %t;
2021 }
2022  
2023 is_deeply $t->printKeys, <<END;
2024 SA0 3 1 3 5 7
2025 Rr1 2 9 11 13 15->1 3 5 7
2026 Rz2 1 17 19 21->9 11 13 15
2027 END
2028 #save($t);
2029  
2030  
2031 is_deeply $t->printKeysAndData, <<END; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
2032  
2033 1 2
2034 3 6
2035 5 10
2036 7 14
2037 9 18
2038 11 22
2039 13 26
2040 15 30
2041 17 34
2042 19 38
2043 21 42
2044 END
2045  
2046 for(map {2 * $_-1} 1..$N/2)
2047 {$t->delete($_);
2048 delete $t{$_};
2049 checkAgainstHash $t, %t;
2050 }
2051  
2052 is_deeply $t->printKeys, <<END;
2053 Sz0 1
2054 END
2055 #save($t);
2056 }
2057  
2058  
2059  
2060 =head1 Hash Definitions
2061  
2062  
2063  
2064  
2065 =head2 Tree::Bulk Definition
2066  
2067  
2068 Bulk tree node
2069  
2070  
2071  
2072  
2073 =head3 Output fields
2074  
2075  
2076 =head4 data
2077  
2078 Data corresponding to each key
2079  
2080 =head4 height
2081  
2082 Height of node
2083  
2084 =head4 keys
2085  
2086 Array of data items for this node
2087  
2088 =head4 keysPerNode
2089  
2090 Maximum number of keys per node
2091  
2092 =head4 left
2093  
2094 Left node
2095  
2096 =head4 right
2097  
2098 Right node
2099  
2100 =head4 up
2101  
2102 Parent node
2103  
2104  
2105  
2106 =head1 Attributes
2107  
2108  
2109 The following is a list of all the attributes in this package. A method coded
2110 with the same name in your package will over ride the method of the same name
2111 in this package and thus provide your value for the attribute in place of the
2112 default value supplied for this attribute by this package.
2113  
2114 =head2 Replaceable Attribute List
2115  
2116  
2117 new
2118  
2119  
2120 =head2 new
2121  
2122 Create a new tree
2123  
2124  
2125  
2126  
2127 =head1 Private Methods
2128  
2129 =head2 node($key, $data, $up, $side)
2130  
2131 Create a new bulk tree node
2132  
2133 Parameter Description
2134 1 $key Key
2135 2 $data $data
2136 3 $up Parent node
2137 4 $side Side of parent node
2138  
2139 =head2 setHeights  ($tree)
2140  
2141 Set heights along path to root
2142  
2143 Parameter Description
2144 1 $tree Tree
2145  
2146 B<Example:>
2147  
2148  
2149 if (1)
2150 {lll "Balance";
2151 my $t = Tree::Bulk::new->setKeysPerNode(1);
2152  
2153 my $a = node(1,2) ->setKeysPerNode(1);
2154 my $b = node(2,4) ->setKeysPerNode(1);
2155 my $c = node(6,12)->setKeysPerNode(1);
2156 my $d = node(5,10)->setKeysPerNode(1);
2157 my $e = node(4,8) ->setKeysPerNode(1);
2158 my $f = node(3,6) ->setKeysPerNode(1);
2159 $a->right = $b; $b->up = $a;
2160 $b->right = $c; $c->up = $b;
2161 $c->left = $d; $d->up = $c;
2162 $d->left = $e; $e->up = $d;
2163 $e->left = $f; $f->up = $e;
2164  
2165 $f->setHeights(1); # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
2166  
2167 is_deeply $a->printKeys, <<END;
2168 SA0 4 1
2169 Lr2 2 2->4
2170 Rz3 1 3->2
2171 Rd1 3 4->1
2172 Lz3 1 5->6
2173 Rl2 2 6->4
2174 END
2175 #save $a;
2176  
2177 $b->balance;
2178 is_deeply $a->printKeys, <<END;
2179 SA0 4 1
2180 Lr2 2 2->4
2181 Rz3 1 3->2
2182 Rd1 3 4->1
2183 Lz3 1 5->6
2184 Rl2 2 6->4
2185 END
2186 #save $a;
2187 }
2188  
2189  
2190 =head2 actualHeight($tree)
2191  
2192 Get the height of a node
2193  
2194 Parameter Description
2195 1 $tree Tree
2196  
2197 B<Example:>
2198  
2199  
2200 if (1)
2201 {my $N = 22;
2202 my $t = Tree::Bulk::new;
2203 ok $t->empty;
2204 ok $t->leaf;
2205  
2206 for(1..$N)
2207 {$t->insert($_, 2 * $_);
2208 }
2209  
2210 ok $t->right->duplex;
2211  
2212 is_deeply actualHeight($t), 4; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
2213  
2214  
2215 is_deeply $t->printKeys, <<END;
2216 SA0 4 1 2 3 4
2217 Lz2 1 5 6 7 8->9 10 11 12
2218 Rd1 3 9 10 11 12->1 2 3 4
2219 Lz3 1 13 14 15 16->17 18 19 20
2220 Rd2 2 17 18 19 20->9 10 11 12
2221 Rz3 1 21 22->17 18 19 20
2222 END
2223 #save $t;
2224  
2225 is_deeply $t->printKeysAndData, <<END;
2226 1 2
2227 2 4
2228 3 6
2229 4 8
2230 5 10
2231 6 12
2232 7 14
2233 8 16
2234 9 18
2235 10 20
2236 11 22
2237 12 24
2238 13 26
2239 14 28
2240 15 30
2241 16 32
2242 17 34
2243 18 36
2244 19 38
2245 20 40
2246 21 42
2247 22 44
2248 END
2249  
2250 my %t = map {$_=>2*$_} 1..$N;
2251  
2252 for(map {2 * $_} 1..$N/2)
2253 {$t->delete($_);
2254 delete $t{$_};
2255 checkAgainstHash $t, %t;
2256 }
2257  
2258 is_deeply $t->printKeys, <<END;
2259 SA0 3 1 3 5 7
2260 Rr1 2 9 11 13 15->1 3 5 7
2261 Rz2 1 17 19 21->9 11 13 15
2262 END
2263 #save($t);
2264  
2265 is_deeply $t->printKeysAndData, <<END;
2266 1 2
2267 3 6
2268 5 10
2269 7 14
2270 9 18
2271 11 22
2272 13 26
2273 15 30
2274 17 34
2275 19 38
2276 21 42
2277 END
2278  
2279 for(map {2 * $_-1} 1..$N/2)
2280 {$t->delete($_);
2281 delete $t{$_};
2282 checkAgainstHash $t, %t;
2283 }
2284  
2285 is_deeply $t->printKeys, <<END;
2286 Sz0 1
2287 END
2288 #save($t);
2289 }
2290  
2291  
2292 =head2 setHeight   ($tree)
2293  
2294 Set height of a tree from its left and right trees
2295  
2296 Parameter Description
2297 1 $tree Tree
2298  
2299 =head2 rotateLeft  ($n)
2300  
2301 Rotate a node left
2302  
2303 Parameter Description
2304 1 $n Node
2305  
2306 B<Example:>
2307  
2308  
2309 if (1)
2310 {lll "Rotate";
2311 my $a = node(1,2)->setKeysPerNode(1);
2312 my $b = node(2,4)->setKeysPerNode(1);
2313 my $c = node(3,6)->setKeysPerNode(1);
2314 my $d = node(4,8)->setKeysPerNode(1);
2315 $a->right = $b; $b->up = $a;
2316 $b->right = $c; $c->up = $b;
2317 $c->right = $d; $d->up = $c;
2318 $d->setHeights(1);
2319  
2320 is_deeply $a->printKeys, <<END;
2321 SA0 3 1
2322 Lz2 1 2->3
2323 Rd1 2 3->1
2324 Rz2 1 4->3
2325 END
2326 #save $a;
2327  
2328 $b->rotateLeft; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
2329  
2330 is_deeply $a->printKeys, <<END;
2331 SA0 3 1
2332 Lz2 1 2->3
2333 Rd1 2 3->1
2334 Rz2 1 4->3
2335 END
2336 #save $a;
2337  
2338  
2339 $c->rotateLeft; $c->setHeights(2); # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
2340  
2341 is_deeply $a->printKeys, <<END;
2342 SA0 3 1
2343 Lz2 1 2->3
2344 Rd1 2 3->1
2345 Rz2 1 4->3
2346 END
2347 #save $a;
2348  
2349 $d->rotateRight; $d->setHeights(1);
2350 is_deeply $a->printKeys, <<END;
2351 SA0 3 1
2352 Lz2 1 2->3
2353 Rd1 2 3->1
2354 Rz2 1 4->3
2355 END
2356 #save $a;
2357  
2358 $c->rotateRight; $c->setHeights(2);
2359 is_deeply $a->printKeys, <<END;
2360 SA0 3 1
2361 Lz2 1 2->3
2362 Rd1 2 3->1
2363 Rz2 1 4->3
2364 END
2365 #save $a;
2366 }
2367  
2368  
2369 =head2 rotateRight ($n)
2370  
2371 Rotate a node right
2372  
2373 Parameter Description
2374 1 $n Node
2375  
2376 B<Example:>
2377  
2378  
2379 if (1)
2380 {lll "Rotate";
2381 my $a = node(1,2)->setKeysPerNode(1);
2382 my $b = node(2,4)->setKeysPerNode(1);
2383 my $c = node(3,6)->setKeysPerNode(1);
2384 my $d = node(4,8)->setKeysPerNode(1);
2385 $a->right = $b; $b->up = $a;
2386 $b->right = $c; $c->up = $b;
2387 $c->right = $d; $d->up = $c;
2388 $d->setHeights(1);
2389  
2390 is_deeply $a->printKeys, <<END;
2391 SA0 3 1
2392 Lz2 1 2->3
2393 Rd1 2 3->1
2394 Rz2 1 4->3
2395 END
2396 #save $a;
2397 $b->rotateLeft;
2398 is_deeply $a->printKeys, <<END;
2399 SA0 3 1
2400 Lz2 1 2->3
2401 Rd1 2 3->1
2402 Rz2 1 4->3
2403 END
2404 #save $a;
2405  
2406 $c->rotateLeft; $c->setHeights(2);
2407 is_deeply $a->printKeys, <<END;
2408 SA0 3 1
2409 Lz2 1 2->3
2410 Rd1 2 3->1
2411 Rz2 1 4->3
2412 END
2413 #save $a;
2414  
2415  
2416 $d->rotateRight; $d->setHeights(1); # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
2417  
2418 is_deeply $a->printKeys, <<END;
2419 SA0 3 1
2420 Lz2 1 2->3
2421 Rd1 2 3->1
2422 Rz2 1 4->3
2423 END
2424 #save $a;
2425  
2426  
2427 $c->rotateRight; $c->setHeights(2); # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
2428  
2429 is_deeply $a->printKeys, <<END;
2430 SA0 3 1
2431 Lz2 1 2->3
2432 Rd1 2 3->1
2433 Rz2 1 4->3
2434 END
2435 #save $a;
2436 }
2437  
2438  
2439 =head2 insertUnchecked ($tree, $key, $data)
2440  
2441 Insert a key and some data into a tree
2442  
2443 Parameter Description
2444 1 $tree Tree
2445 2 $key Key
2446 3 $data Data
2447  
2448 =head2 unchain ($t)
2449  
2450 Remove a tree from the middle of a chain. A leaf is considered to be in the middle of a chain and so can be removed with this method
2451  
2452 Parameter Description
2453 1 $t Tree
2454  
2455 =head2 refillFromRight ($target)
2456  
2457 Push a key to the target node from the next node
2458  
2459 Parameter Description
2460 1 $target Target tree
2461  
2462 =head2 refillFromLeft  ($target)
2463  
2464 Push a key to the target node from the previous node
2465  
2466 Parameter Description
2467 1 $target Target tree
2468  
2469 =head2 refill  ($tree)
2470  
2471 Refill a node so it has the expected number of keys
2472  
2473 Parameter Description
2474 1 $tree Tree
2475  
2476 =head2 printKeys2  ($t, $in, $g)
2477  
2478 print the keys for a tree
2479  
2480 Parameter Description
2481 1 $t Tree
2482 2 $in Indentation
2483 3 $g List of keys
2484  
2485 =head2 checkLRU($tree)
2486  
2487 Confirm pointers in tree
2488  
2489 Parameter Description
2490 1 $tree Tree
2491  
2492 =head2 check   ($tree)
2493  
2494 Confirm that each node in a tree is ordered correctly
2495  
2496 Parameter Description
2497 1 $tree Tree
2498  
2499 =head2 checkAgainstHash($t, %t)
2500  
2501 Check a tree against a hash
2502  
2503 Parameter Description
2504 1 $t Tree
2505 2 %t Expected
2506  
2507  
2508 =head1 Index
2509  
2510  
2511 1 L<actualHeight|/actualHeight> - Get the height of a node
2512  
2513 2 L<balance|/balance> - Balance a node
2514  
2515 3 L<check|/check> - Confirm that each node in a tree is ordered correctly
2516  
2517 4 L<checkAgainstHash|/checkAgainstHash> - Check a tree against a hash
2518  
2519 5 L<checkLRU|/checkLRU> - Confirm pointers in tree
2520  
2521 6 L<delete|/delete> - Delete a key in a tree
2522  
2523 7 L<duplex|/duplex> - Return the tree if it has left and right children
2524  
2525 8 L<empty|/empty> - Return the tree if it is empty
2526  
2527 9 L<find|/find> - Find a key in a tree and returns its data
2528  
2529 10 L<first|/first> - First node in a tree
2530  
2531 11 L<inorder|/inorder> - Return a list of all the nodes in a tree in order
2532  
2533 12 L<insert|/insert> - Insert a key and some data into a tree
2534  
2535 13 L<insertUnchecked|/insertUnchecked> - Insert a key and some data into a tree
2536  
2537 14 L<isLeftChild|/isLeftChild> - Return the tree if it is the left child
2538  
2539 15 L<isRightChild|/isRightChild> - Return the tree if it is the right child
2540  
2541 16 L<isRoot|/isRoot> - Return the tree if it is the root
2542  
2543 17 L<last|/last> - Last node in a tree
2544  
2545 18 L<leaf|/leaf> - Return the tree if it is a leaf
2546  
2547 19 L<name|/name> - Name of a tree
2548  
2549 20 L<names|/names> - Names of all nodes in a tree in order
2550  
2551 21 L<next|/next> - Next node in order
2552  
2553 22 L<node|/node> - Create a new bulk tree node
2554  
2555 23 L<prev|/prev> - Previous node in order
2556  
2557 24 L<printKeys|/printKeys> - Print the keys in a tree
2558  
2559 25 L<printKeys2|/printKeys2> - print the keys for a tree
2560  
2561 26 L<printKeysAndData|/printKeysAndData> - Print the mapping from keys to data in a tree
2562  
2563 27 L<refill|/refill> - Refill a node so it has the expected number of keys
2564  
2565 28 L<refillFromLeft|/refillFromLeft> - Push a key to the target node from the previous node
2566  
2567 29 L<refillFromRight|/refillFromRight> - Push a key to the target node from the next node
2568  
2569 30 L<root|/root> - Return the root node of a tree
2570  
2571 31 L<rotateLeft|/rotateLeft> - Rotate a node left
2572  
2573 32 L<rotateRight|/rotateRight> - Rotate a node right
2574  
2575 33 L<setHeight|/setHeight> - Set height of a tree from its left and right trees
2576  
2577 34 L<setHeights|/setHeights> - Set heights along path to root
2578  
2579 35 L<setKeysPerNode|/setKeysPerNode> - Set the number of keys for the current node
2580  
2581 36 L<simplex|/simplex> - Return the tree if it has either a left child or a right child but not both.
2582  
2583 37 L<simplexWithLeaf|/simplexWithLeaf> - Return the tree if it has either a left child or a right child but not both and the child it has a leaf.
2584  
2585 38 L<singleton|/singleton> - Return the tree if it contains only the root node and nothing else
2586  
2587 39 L<unchain|/unchain> - Remove a tree from the middle of a chain.
2588  
2589 =head1 Installation
2590  
2591 This module is written in 100% Pure Perl and, thus, it is easy to read,
2592 comprehend, use, modify and install via B<cpan>:
2593  
2594 sudo cpan install Tree::Bulk
2595  
2596 =head1 Author
2597  
2598 L<philiprbrenan@gmail.com|mailto:philiprbrenan@gmail.com>
2599  
2600 L<http://prb.appaapps.com|http://prb.appaapps.com>
2601  
2602 =head1 Copyright
2603  
2604 Copyright (c) 2016-2023 Philip R Brenan.
2605  
2606 This module is free software. It may be used, redistributed and/or modified
2607 under the same terms as Perl itself.
2608  
2609 =cut
2610  
2611  
2612  
2613 # Tests and documentation
2614  
2615 sub test
2616 1 ▶ {my $p = __PACKAGE__;
Subroutine test: called CC=5 SCAR=16.3
Pod undocumented
2617 1 binmode($_, ":utf8") for *STDOUT, *STDERR;
2618 1 ▶ return if eval "eof(${p}::DATA)";
Branch: 1 branch
BranchTrueFalseTotal
if eval "eof(${p}::DATA)" 0 1 1
2619 1 my $s = eval "join('', <${p}::DATA>)";
2620 1 ▶ $@ and die $@;
Branch: 1 branch
BranchTrueFalseTotal
$@ and die $@ 0 1 1
2621 1 ▶ eval $s;
Subroutine BEGIN: called CC=1 SCAR=0.0
Subroutine BEGIN: called CC=1 SCAR=0.0
2622 1 ▶ $@ and die $@;
Branch: 1 branch
BranchTrueFalseTotal
$@ and die $@ 0 1 1
2623 1 1
2624 }
2625  
2626 1 ▶test unless caller;
Branch: 1 branch
BranchTrueFalseTotal
unless caller 0 1 1
2627  
2628 1 1;
2629 # podDocumentation
2630 __DATA__
↑ Summary