blib/lib/Tree/Multi.pm

filter: Statementstmt 95.0% 438 / 461 Branchbran 73.5% 206 / 280 Conditioncond 72.3% 34 / 47 MC/DCmcdc 53.8% 14 / 26 Subroutinesub 96.4% 54 / 56 Podpod 97.2% 35 / 36 totaltotal 86.2% 781 / 906 CC 183 SCAR 20.5
CC
183
Cov
86%
__ANON__
16.8
mergeWithLeftOrRight
13.9
findAndSplit
12.1
CRAP 7.7
↑ Summary
1 #!/usr/bin/perl -I/home/phil/perl/cpan/DataTableText/lib/ -I.
2 #-------------------------------------------------------------------------------
3 # Multi-way tree in Pure Perl with an even or odd number of keys per node.
4 # Philip R Brenan at appaapps dot com, Appa Apps Ltd Inc., 2021
5 #-------------------------------------------------------------------------------
6 # podDocumentation
7 package Tree::Multi;
8 1 our $VERSION = "20210629";
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 pp);
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 1 our $numberOfKeysPerNode = 3; # Number of keys per node which can be localized because it is ours. The number of keys can be even or odd.
17  
18 #D1 Multi-way Tree # Create and use a multi-way tree.
19  
20 sub new() #P Create a new multi-way tree node.
21 260980 ▶ {my () = @_; # Key, $data, parent node, index of link from parent node
Subroutine new: called CC=1 SCAR=0.0
Pod documented
22 260980 genHash(__PACKAGE__, # Multi tree node
23 up => undef, # Parent node
24 keys => [], # Array of key items for this node
25 data => [], # Data corresponding to each key
26 node => [], # Child nodes
27 );
28 }
29  
30 sub minimumNumberOfKeys() #P Minimum number of keys per node.
31 1181414 ▶ {int(($numberOfKeysPerNode - 1) / 2)
Subroutine minimumNumberOfKeys: called CC=1 SCAR=0.0
Pod documented
32 }
33  
34 sub maximumNumberOfKeys() #P Maximum number of keys per node.
35 3934907 ▶ {$numberOfKeysPerNode
Subroutine maximumNumberOfKeys: called CC=1 SCAR=0.0
Pod documented
36 }
37  
38 sub maximumNumberOfNodes() #P Maximum number of children per parent.
39 129341 ▶ {$numberOfKeysPerNode + 1
Subroutine maximumNumberOfNodes: called CC=1 SCAR=0.0
Pod documented
40 }
41  
42 sub full($) #P Confirm that a node is full.
43 0 ▶ {my ($tree) = @_; # Tree
Subroutine full: not called CC=3 SCAR=24.8
Pod documented
44 0 ▶ @_ == 1 or confess;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 1 or confess() 0 0 0
45 0 my $n = $tree->keys->@*;
46 0 ▶ $n <= maximumNumberOfKeys or confess "Keys";
Branch: 1 branch
BranchTrueFalseTotal
$n <= &maximumNumberOfKeys() or confess("Keys") 0 0 0
47 0 $n == maximumNumberOfKeys
48 }
49  
50 sub halfFull($) #P Confirm that a node is half full.
51 1181414 ▶ {my ($tree) = @_; # Tree
Subroutine halfFull: called CC=3 SCAR=11.3
Pod documented
52 1181414 ▶ @_ == 1 or confess;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 1 or confess() 1181414 0 1181414
53 1181414 my $n = $tree->keys->@*;
54 1181414 ▶ $n <= maximumNumberOfKeys+1 or confess "Keys";
Branch: 1 branch
BranchTrueFalseTotal
$n <= &maximumNumberOfKeys() + 1 or confess("Keys") 1181414 0 1181414
55 1181414 $n == minimumNumberOfKeys
56 }
57  
58 sub root($) # Return the root node of a tree.
59 85 ▶ {my ($tree) = @_; # Tree
Subroutine root: called CC=3 SCAR=11.4
Pod documented
60 85 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 85 85
61 85 ▶ for(; $tree->up; $tree = $tree->up) {}
Branch: 1 branch
BranchTrueFalseTotal
if ($tree->up) 0 85 85
62 85 $tree
63 }
64  
65 sub leaf($) # Confirm that the tree is a leaf.
66 918962 ▶ {my ($tree) = @_; # Tree
Subroutine leaf: called CC=2 SCAR=7.1
Pod documented
67 918962 ▶ @_ == 1 or confess;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 1 or confess() 918962 0 918962
68 918962 !scalar $tree->node->@* # No children so it must be a leaf
69 }
70  
71 sub reUp($$) #P Reconnect the children to their new parent.
72 120704 ▶ {my ($tree, $children) = @_; # Tree, children
Subroutine reUp: called CC=4 SCAR=14.5
Pod documented
73 120704 ▶ @_ > 0 or confess;
Branch: 1 branch
BranchTrueFalseTotal
@_ > 0 or confess() 120704 0 120704
74 120704 ▶ $tree->keys->@* <= maximumNumberOfKeys or confess "Keys";
Branch: 1 branch
BranchTrueFalseTotal
@{$tree->keys} <= &maximumNumberOfKeys() or confess("Keys") 120704 0 120704
75 120704 $_->up = $tree for @$children; # Connect child to parent
76 }
77  
78 sub splitFullNode($$$) #P Split a node if it is full.
79 1131110 ▶ {my ($isRoot, $isLeaf, $node) = @_; # Known to be the root if true, known to be a leaf if true, node to split
Subroutine splitFullNode: called CC=10 SCAR=23.1
Pod documented
80 1131110 ▶ @_ == 3 or confess;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 3 or confess() 1131110 0 1131110
81  
82 1131110 if (1) # Check number of keys
83 1131110 {my $c = $node->keys->@*; # Number of keys
84 1131110 ▶ confess if $c > maximumNumberOfKeys; # Complain about over full nodes
Branch: 1 branch
BranchTrueFalseTotal
if $c > &maximumNumberOfKeys() 0 1131110 1131110
85 1131110 ▶ return unless $c == maximumNumberOfKeys; # Only split full nodes
Branch: 1 branch
BranchTrueFalseTotal
unless $c == &maximumNumberOfKeys() 1001769 129341 1131110
86 }
87  
88 129341 ▶ my ($p, $l, $r) = ($node->up // $node, new, new); # New child nodes
Condition66%2/3
$node->up // $node
l!l&&r!l&&!r
12144578960
MC/DC0%0/2
$node->up // $node
$node->up $node
Truth table66%2/3
A // B
A= $node->upB= $node
ABresult
1X1
011
000
89 129341 $l->up = $r->up = $p; # Connect children to parent
90  
91 129341 my @k = $node->keys->@*;
92 129341 my @d = $node->data->@*;
93  
94 129341 my $N = int maximumNumberOfNodes / 2; # Split points
95 129341 ▶ my $n = maximumNumberOfKeys % 2 == 0 ? $N - 1 : $N - 2;
Branch: 1 branch
BranchTrueFalseTotal
&maximumNumberOfKeys() % 2 == 0 ? : 52877 76464 129341
96  
97 129341 $l->keys = [@k[0..$n]]; # Split keys
98 129341 $l->data = [@d[0..$n]]; # Split data
99 129341 $r->keys = [@k[$n+2..$#k]];
100 129341 $r->data = [@d[$n+2..$#k]];
101  
102 129341 ▶ if (!$isLeaf) # Not a leaf node
Branch: 1 branch
BranchTrueFalseTotal
unless ($isLeaf) 39760 89581 129341
103 39760 {my @n = $node->node->@*;
104 39760 reUp $l, $l->node = [@n[0 ..$n+1]];
105 39760 reUp $r, $r->node = [@n[$n+2..$#n ]];
106 }
107  
108 129341 ▶ if (!$isRoot) # Not a root node
Branch: 1 branch
BranchTrueFalseTotal
if (not $isRoot) { } 121445 7896 129341
109 121445 {my @n = $p->node->@*; # Insert new nodes in parent known to be not full
110 121445 for my $i(keys @n) # Each parent node
111 225470 ▶ {if ($n[$i] == $node) # Find the node that points from the parent to the current node
Branch: 1 branch
BranchTrueFalseTotal
if ($n[$i] == $node) 121445 104025 225470
112 121445 {splice $p->keys->@*, $i, 0, $k[$n+1]; # Insert splitting key
113 121445 splice $p->data->@*, $i, 0, $d[$n+1]; # Insert data associated with splitting key
114 121445 splice $p->node->@*, $i, 1, $l, $r; # Insert offsets on either side of the splitting key
115 121445 return; #
116 }
117 }
118 0 confess "Should not happen";
119 }
120 else # Root node with single key after split
121 7896 {$node->keys = [$k[$n+1]]; # Single key
122 7896 $node->data = [$d[$n+1]]; # Data associated with single key
123 7896 $node->node = [$l, $r]; # Nodes on either side of single key
124 }
125 }
126  
127 sub findAndSplit($$) #P Find a key in a tree splitting full nodes along the path to the key.
128 235001 ▶ {my ($root, $key) = @_; # Root of tree, key
Subroutine findAndSplit: called CC=12 SCAR=24.9
Pod documented
129 235001 ▶ @_ == 2 or confess;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 2 or confess() 235001 0 235001
130  
131 235001 my $tree = $root; # Start at the root
132  
133 235001 splitFullNode 1, !scalar($tree->node->@*), $tree; # Split the root node if necessary
134  
135 235001 for(0..999) # Step down through the tree
136 896159 ▶ {confess unless my @k = $tree->keys->@*; # We should have at least one key in the tree because we do a special case insert for an empty tree
Branch: 1 branch
BranchTrueFalseTotal
unless my(@k) = @{$tree->keys} 0 896159 896159
137  
138 896159 ▶ if ($key < $k[0]) # Less than smallest key in node
Branch: 1 branch
BranchTrueFalseTotal
if ($key < $k[0]) 340484 555675 896159
139 340484 ▶ {return (-1, $tree, 0) unless my $n = $tree->node->[0];
Branch: 1 branch
BranchTrueFalseTotal
unless my $n = $tree->node->[0] 83011 257473 340484
140 257473 $tree = $n;
141 257473 next;
142 }
143  
144 555675 ▶ if ($key > $k[-1]) # Greater than largest key in node
Branch: 1 branch
BranchTrueFalseTotal
if ($key > $k[-1]) 328042 227633 555675
145 328042 ▶ {return (+1, $tree, $#k) unless my $n = $tree->node->[-1];
Branch: 1 branch
BranchTrueFalseTotal
unless my $n = $tree->node->[-1] 80806 247236 328042
146 247236 $tree = $n;
147 247236 next;
148 }
149  
150 227633 for my $i(keys @k) # Search the keys in this node as greater than least key and less than largest key
151 565846 {my $s = $key <=> $k[$i]; # Compare key
152 565846 ▶ if ($s == 0) # Found key
Branch: 2 branches
BranchTrueFalseTotal
if ($s == 0) { } 50 565796 565846
elsif ($s < 0) { } 227583 338213 565796
153 50 {return (0, $tree, $i);
154 }
155 elsif ($s < 0) # Less than current key
156 227583 ▶ {return (-1, $tree, $i) unless my $n = $tree->node->[$i]; # Step through if possible
Branch: 1 branch
BranchTrueFalseTotal
unless my $n = $tree->node->[$i] 71134 156449 227583
157 156449 $tree = $n; # Step
158 156449 last;
159 }
160 }
161 }
162 661158 continue {splitFullNode 0, 0, $tree} # Split the node we have stepped to
163  
164 0 confess "Should not happen";
165 }
166  
167 sub find($$) # Find a key in a tree returning its associated data or undef if the key does not exist.
168 481951 ▶ {my ($root, $key) = @_; # Root of tree, key
Subroutine find: called CC=12 SCAR=24.9
Pod documented
169 481951 ▶ @_ == 2 or confess;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 2 or confess() 481951 0 481951
170  
171 481951 my $tree = $root; # Start at the root
172  
173 481951 for(0..999) # Step down through the tree
174 1674803 ▶ {return undef unless my @k = $tree->keys->@*; # Empty node
Branch: 1 branch
BranchTrueFalseTotal
unless my(@k) = @{$tree->keys} 2222 1672581 1674803
175  
176 1672581 ▶ if ($key < $k[0]) # Less than smallest key in node
Branch: 1 branch
BranchTrueFalseTotal
if ($key < $k[0]) 578714 1093867 1672581
177 578714 ▶ {return undef unless $tree = $tree->node->[0];
Branch: 1 branch
BranchTrueFalseTotal
unless $tree = $tree->node->[0] 95819 482895 578714
178 482895 next;
179 }
180  
181 1093867 ▶ if ($key > $k[-1]) # Greater than largest key in node
Branch: 1 branch
BranchTrueFalseTotal
if ($key > $k[-1]) 556990 536877 1093867
182 556990 ▶ {return undef unless $tree = $tree->node->[-1];
Branch: 1 branch
BranchTrueFalseTotal
unless $tree = $tree->node->[-1] 107949 449041 556990
183 449041 next;
184 }
185  
186 536877 for my $i(keys @k) # Search the keys in this node
187 1102356 {my $s = $key <=> $k[$i]; # Compare key
188 1102356 ▶ return $tree->data->[$i] if $s == 0; # Found key
Branch: 1 branch
BranchTrueFalseTotal
if $s == 0 241488 860868 1102356
189 860868 ▶ if ($s < 0) # Less than current key
Branch: 1 branch
BranchTrueFalseTotal
if ($s < 0) 295389 565479 860868
190 295389 ▶ {return undef unless $tree = $tree->node->[$i];
Branch: 1 branch
BranchTrueFalseTotal
unless $tree = $tree->node->[$i] 34473 260916 295389
191 260916 last;
192 }
193 }
194 }
195  
196 0 confess "Should not happen";
197 }
198  
199 sub indexInParent($) #P Get the index of a node in its parent.
200 426471 ▶ {my ($tree) = @_; # Tree
Subroutine indexInParent: called CC=5 SCAR=16.7
Pod documented
201 426471 ▶ @_ == 1 or confess; confess unless my $p = $tree->up;
Branch: 2 branches
BranchTrueFalseTotal
@_ == 1 or confess() 426471 0 426471
unless my $p = $tree->up 0 426471 426471
202  
203 426471 ▶ my @n = $p->node->@*; for my $i(keys @n) {return $i if $n[$i] == $tree}
Branch: 1 branch
BranchTrueFalseTotal
if $n[$i] == $tree 426471 602535 1029006
204 0 confess "Should not happen";
205 }
206  
207 sub fillFromLeftOrRight($$) #P Fill a node from the specified sibling.
208 76682 ▶ {my ($node, $dir) = @_; # Node to fill, node to fill from 0 for left or 1 for right
Subroutine fillFromLeftOrRight: called CC=8 SCAR=20.9
Pod documented
209 76682 ▶ @_ == 2 or confess;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 2 or confess() 76682 0 76682
210  
211 76682 ▶ confess unless my $p = $node->up; # Parent of leaf
Branch: 1 branch
BranchTrueFalseTotal
unless my $p = $node->up 0 76682 76682
212 76682 my $i = indexInParent $node; # Index of leaf in parent
213  
214 76682 ▶ if ($dir) # Fill from right
Branch: 1 branch
BranchTrueFalseTotal
if ($dir) { } 9153 67529 76682
215 9153 ▶ {$i < $p->node->@* - 1 or confess; # Cannot fill from right
Branch: 1 branch
BranchTrueFalseTotal
$i < @{$p->node} - 1 or confess() 9153 0 9153
216 9153 my $r = $p->node->[$i+1]; # Right sibling
217 9153 push $node->keys->@*, $p->keys->[$i]; $p->keys->[$i] = shift $r->keys->@*; # Transfer key
218 9153 push $node->data->@*, $p->data->[$i]; $p->data->[$i] = shift $r->data->@*; # Transfer data
219 9153 ▶ if (!leaf $node) # Transfer node if not a leaf
Branch: 1 branch
BranchTrueFalseTotal
if (not &leaf($node)) 4700 4453 9153
220 4700 {push $node->node->@*, shift $r->node->@*;
221 4700 $node->node->[-1]->up = $node;
222 }
223 }
224 else # Fill from left
225 67529 ▶ {$i > 0 or confess; # Cannot fill from left
Branch: 1 branch
BranchTrueFalseTotal
$i > 0 or confess() 67529 0 67529
226 67529 my $I = $i-1;
227 67529 my $n = $p->node->[$I]; # Left sibling
228 67529 my $k = $p->keys; my $d = $p->data;
229 67529 unshift $node->keys->@*, $k->[$I]; $k->[$I] = pop $n->keys->@*; # Transfer key
230 67529 unshift $node->data->@*, $d->[$I]; $d->[$I] = pop $n->data->@*; # Transfer data
231 67529 ▶ if (!leaf $node) # Transfer node if not a leaf
Branch: 1 branch
BranchTrueFalseTotal
if (not &leaf($node)) 24699 42830 67529
232 24699 {unshift $node->node->@*, pop $n->node->@*;
233 24699 $node->node->[0]->up = $node;
234 }
235 }
236 }
237  
238 sub mergeWithLeftOrRight($$) #P Merge two adjacent nodes.
239 119637 ▶ {my ($n, $dir) = @_; # Node to merge into, node to merge is on right if 1 else left
Subroutine mergeWithLeftOrRight: called CC=13 SCAR=26.3
Pod documented
240 119637 ▶ @_ == 2 or confess;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 2 or confess() 119637 0 119637
241  
242 119637 ▶ confess unless halfFull($n); # Confirm leaf is half full
Branch: 1 branch
BranchTrueFalseTotal
unless &halfFull($n) 0 119637 119637
243 119637 ▶ confess unless my $p = $n->up; # Parent of leaf
Branch: 1 branch
BranchTrueFalseTotal
unless my $p = $n->up 0 119637 119637
244 119637 ▶ confess if halfFull($p) and $p->up; # Parent must have more than the minimum number of keys because we need to remove one unless it is the root of the tree
Branch: 1 branch
BranchTrueFalseTotal
if &halfFull($p) and $p->up 0 119637 119637
Condition66%2/3
&halfFull($p) and $p->up
!ll&&!rl&&r
1191774600
MC/DC0%0/2
&halfFull($p) and $p->up
&halfFull($p) $p->up
Truth table66%2/3
A and B
A= &halfFull($p)B= $p->up
ABresult
0X0
100
111
245  
246 119637 my $i = indexInParent $n; # Index of leaf in parent
247  
248 119637 ▶ if ($dir) # Merge with right hand sibling
Branch: 1 branch
BranchTrueFalseTotal
if ($dir) { } 23173 96464 119637
249 23173 ▶ {$i < $p->node->@* - 1 or confess; # Cannot fill from right
Branch: 1 branch
BranchTrueFalseTotal
$i < @{$p->node} - 1 or confess() 23173 0 23173
250 23173 my $I = $i+1;
251 23173 my $r = $p->node->[$I]; # Leaf on right
252 23173 ▶ confess unless halfFull($r); # Confirm right leaf is half full
Branch: 1 branch
BranchTrueFalseTotal
unless &halfFull($r) 0 23173 23173
253 23173 push $n->keys->@*, splice($p->keys->@*, $i, 1), $r->keys->@*; # Transfer keys
254 23173 push $n->data->@*, splice($p->data->@*, $i, 1), $r->data->@*; # Transfer data
255 23173 ▶ if (!leaf $n) # Children of merged node
Branch: 1 branch
BranchTrueFalseTotal
unless (&leaf($n)) 7128 16045 23173
256 7128 {push $n->node->@*, $r->node->@*; # Children of merged node
257 7128 reUp $n, $r->node; # Update parent of children of right node
258 }
259 23173 splice $p->node->@*, $I, 1; # Remove link from parent to right child
260 }
261 else # Merge with left hand sibling
262 96464 ▶ {$i > 0 or confess; # Cannot fill from left
Branch: 1 branch
BranchTrueFalseTotal
$i > 0 or confess() 96464 0 96464
263 96464 my $I = $i-1;
264 96464 my $l = $p->node->[$I]; # Node on left
265 96464 ▶ confess unless halfFull($l); # Confirm right leaf is half full
Branch: 1 branch
BranchTrueFalseTotal
unless &halfFull($l) 0 96464 96464
266 96464 unshift $n->keys->@*, $l->keys->@*, splice $p->keys->@*, $I, 1; # Transfer keys
267 96464 unshift $n->data->@*, $l->data->@*, splice $p->data->@*, $I, 1; # Transfer data
268 96464 ▶ if (!leaf $n) # Children of merged node
Branch: 1 branch
BranchTrueFalseTotal
unless (&leaf($n)) 26379 70085 96464
269 26379 {unshift $n->node->@*, $l->node->@*; # Children of merged node
270 26379 reUp $n, $l->node; # Update parent of children of left node
271 }
272 96464 splice $p->node->@*, $I, 1; # Remove link from parent to left child
273 }
274 }
275  
276 sub merge($) #P Merge the current node with its sibling.
277 196319 ▶ {my ($tree) = @_; # Tree
Subroutine merge: called CC=6 SCAR=18.0
Pod documented
278 196319 ▶ if (my $i = indexInParent $tree) # Merge with left node
Branch: 1 branch
BranchTrueFalseTotal
if (my $i = &indexInParent($tree)) { } 163993 32326 196319
279 163993 {my $l = $tree->up->node->[$i-1]; # Left node
280 163993 ▶ if (halfFull(my $r = $tree))
Branch: 1 branch
BranchTrueFalseTotal
if (&halfFull(my $r = $tree)) 163993 0 163993
281 163993 ▶ {$l->halfFull ? mergeWithLeftOrRight $r, 0 : fillFromLeftOrRight $r, 0; # Merge as left and right nodes are half full
Branch: 1 branch
BranchTrueFalseTotal
$l->halfFull ? : 96464 67529 163993
282 }
283 }
284 else
285 32326 {my $r = $tree->up->node->[1]; # Right node
286 32326 ▶ if (halfFull(my $l = $tree))
Branch: 1 branch
BranchTrueFalseTotal
if (&halfFull(my $l = $tree)) 32326 0 32326
287 32326 ▶ {halfFull($r) ? mergeWithLeftOrRight $l, 1 : fillFromLeftOrRight $l, 1; # Merge as left and right nodes are half full
Branch: 1 branch
BranchTrueFalseTotal
&halfFull($r) ? : 23173 9153 32326
288 }
289 }
290 }
291  
292 sub mergeOrFill($) #P Make a node larger than a half node.
293 408082 ▶ {my ($tree) = @_; # Tree
Subroutine mergeOrFill: called CC=8 SCAR=20.8
Pod documented
294 408082 ▶ @_ == 1 or confess;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 1 or confess() 408082 0 408082
295  
296 408082 ▶ return unless halfFull($tree); # No need to merge of if not a half node
Branch: 1 branch
BranchTrueFalseTotal
unless &halfFull($tree) 204086 203996 408082
297 203996 ▶ confess unless my $p = $tree->up; # Parent exists
Branch: 1 branch
BranchTrueFalseTotal
unless my $p = $tree->up 0 203996 203996
298  
299 203996 ▶ if ($p->up) # Merge or fill parent which is not the root
Branch: 2 branches
BranchTrueFalseTotal
if ($p->up) { } 172514 31482 203996
elsif (@{$p->keys} == 1 and &halfFull(my $l = $p->node->[0]) and &halfFull(my $r = $p->node->[1])) { } 7677 23805 31482
300 172514 {__SUB__->($p);
301 172514 merge($tree);
302 }
303 ▶ elsif ($p->keys->@* == 1 and halfFull(my $l = $p->node->[0]) # Parent is the root and it only has one key - merge into the child if possible
Condition100%6/6
@{$p->keys} == 1 and &halfFull(my $l = $p->node->[0]) and &halfFull(my $r = $p->node->[1])
!ll&&!rl&&r
2246113447677
@{$p->keys} == 1 and &halfFull(my $l = $p->node->[0])
!ll&&!rl&&r
1872037419021
MC/DC100%3/3
@{$p->keys} == 1 and &halfFull(my $l = $p->node->[0]) and &halfFull(my $r = $p->node->[1])
@{$p->keys} == 1 &halfFull(my $l = $p->node->[0]) &halfFull(my $r = $p->node->[1])
Truth table100%4/4
A and B and C
A= @{$p->keys} == 1B= &halfFull(my $l = $p->node->[0])C= &halfFull(my $r = $p->node->[1])
ABCresult
0XX0
10X0
1100
1111
304 and halfFull(my $r = $p->node->[1]))
305 7677 {$p->keys = $tree->keys = [$l->keys->@*, $p->keys->@*, $r->keys->@*]; # Merge in place to retain addressability
306 7677 $p->data = $tree->data = [$l->data->@*, $p->data->@*, $r->data->@*];
307 7677 $p->node = $tree->node = [$l->node->@*, $r->node->@*];
308  
309 7677 reUp $p, $p->node; # Reconnect children to parent
310 }
311 else # Parent is the root but it has too may keys to merge into both sibling so merge with a sibling if possible
312 23805 {merge($tree);
313 }
314 }
315  
316 sub leftMost($) # Return the left most node below the specified one.
317 81042 ▶ {my ($tree) = @_; # Tree
Subroutine leftMost: called CC=3 SCAR=11.1
Pod documented
318 81042 for(0..999) # Step down through tree
319 133368 ▶ {return $tree if leaf $tree; # We are on a leaf so we have arrived at the left most node
Branch: 1 branch
BranchTrueFalseTotal
if &leaf($tree) 81042 52326 133368
320 52326 $tree = $tree->node->[0]; # Go left
321 }
322 0 confess "Should not happen";
323 }
324  
325 sub rightMost($) # Return the right most node below the specified one.
326 44933 ▶ {my ($tree) = @_; # Tree
Subroutine rightMost: called CC=3 SCAR=11.1
Pod documented
327 44933 for(0..999) # Step down through tree
328 70592 ▶ {return $tree if leaf $tree; # We are on a leaf so we have arrived at the left most node
Branch: 1 branch
BranchTrueFalseTotal
if &leaf($tree) 44933 25659 70592
329 25659 $tree = $tree->node->[-1]; # Go right
330 }
331 0 confess "Should not happen";
332 }
333  
334 sub height($) # Return the height of the tree.
335 476 ▶ {my ($tree) = @_; # Tree
Subroutine height: called CC=4 SCAR=13.9
Pod documented
336 476 for my $n(0..999) # Step down through tree
337 2291 ▶ {if (leaf $tree) # We are on a leaf
Branch: 1 branch
BranchTrueFalseTotal
if (&leaf($tree)) 476 1815 2291
338 476 ▶ {return $n + 1 if $tree->keys->@*; # We are in a partially full leaf
Branch: 1 branch
BranchTrueFalseTotal
if @{$tree->keys} 471 5 476
339 5 return $n; # We are on the root and it is empty
340 }
341 1815 $tree = $tree->node->[0];
342 }
343 0 confess "Should not happen";
344 }
345  
346 sub depth($) # Return the depth of a node within a tree.
347 62 ▶ {my ($tree) = @_; # Tree
Subroutine depth: called CC=5 SCAR=16.1
Pod documented
348 62 ▶ return 0 if !$tree->up and !$tree->keys->@*; # We are at the root and it is empty
Branch: 1 branch
BranchTrueFalseTotal
unless $tree->up or @{$tree->keys} 1 61 62
Condition100%3/3
$tree->up or @{$tree->keys}
l!l&&r!l&&!r
5381
MC/DC100%2/2
$tree->up or @{$tree->keys}
$tree->up @{$tree->keys}
Truth table100%3/3
A or B
A= $tree->upB= @{$tree->keys}
ABresult
1X1
011
000
349 61 for my $n(1..999) # Step down through tree
350 125 ▶ {return $n unless $tree->up; # We are at the root
Branch: 1 branch
BranchTrueFalseTotal
unless $tree->up 61 64 125
351 64 $tree = $tree->up;
352 }
353 0 confess "Should not happen";
354 }
355  
356 sub deleteLeafKey($$) #P Delete a key in a leaf.
357 240493 ▶ {my ($tree, $i) = @_; # Tree, index to delete at
Subroutine deleteLeafKey: called CC=6 SCAR=18.0
Pod documented
358 240493 ▶ @_ == 2 or confess;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 2 or confess() 240493 0 240493
359 240493 ▶ confess "Not a leaf" unless leaf $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless &leaf($tree) 0 240493 240493
360 240493 my $key = $tree->keys->[$i];
361 240493 ▶ mergeOrFill $tree if $tree->up; # Merge and fill unless we are on the root and the root is a leaf
Branch: 1 branch
BranchTrueFalseTotal
if $tree->up 235568 4925 240493
362 240493 my $k = $tree->keys;
363 240493 for my $j(keys @$k) # Search for key to delete
364 497927 ▶ {if ($$k[$j] == $key)
Branch: 1 branch
BranchTrueFalseTotal
if ($k->[$j] == $key) 240493 257434 497927
365 240493 {splice $tree->keys->@*, $j, 1; # Remove keys
366 240493 splice $tree->data->@*, $j, 1; # Remove data
367 240493 return;
368 }
369 }
370 }
371  
372 sub deleteKey($$) #P Delete a key.
373 240493 ▶ {my ($tree, $i) = @_; # Tree, index to delete at
Subroutine deleteKey: called CC=4 SCAR=13.9
Pod documented
374 240493 ▶ @_ == 2 or confess;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 2 or confess() 240493 0 240493
375 240493 ▶ if (leaf $tree) # Delete from a leaf
Branch: 2 branches
BranchTrueFalseTotal
if (&leaf($tree)) { } 132284 108209 240493
elsif ($i > 0) { } 43846 64363 108209
376 132284 {deleteLeafKey($tree, $i);
377 }
378 elsif ($i > 0) # Delete from a node
379 43846 {my $l = rightMost $tree->node->[$i]; # Find previous node
380 43846 splice $tree->keys->@*, $i, 1, $l->keys->[-1];
381 43846 splice $tree->data->@*, $i, 1, $l->data->[-1];
382 43846 deleteLeafKey $l, -1 + scalar $l->keys->@*; # Remove leaf key
383 }
384 else # Delete from a node
385 64363 {my $r = leftMost $tree->node->[1]; # Find previous node
386 64363 splice $tree->keys->@*, 0, 1, $r->keys->[0];
387 64363 splice $tree->data->@*, 0, 1, $r->data->[0];
388 64363 deleteLeafKey $r, 0; # Remove leaf key
389 }
390 }
391  
392 sub delete($$) # Find a key in a tree, delete it and return any associated data.
393 240493 ▶ {my ($root, $key) = @_; # Tree root, key
Subroutine delete: called CC=11 SCAR=24.4
Pod documented
394 240493 ▶ @_ == 2 or confess;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 2 or confess() 240493 0 240493
395  
396 240493 my $tree = $root;
397 240493 for (0..999)
398 754819 {my $k = $tree->keys;
399  
400 754819 ▶ if ($key < $$k[0]) # Less than smallest key in node
Branch: 2 branches
BranchTrueFalseTotal
if ($key < $k->[0]) { } 203957 550862 754819
elsif ($key > $k->[-1]) { } 193491 357371 550862
401 203957 ▶ {return undef unless $tree = $tree->node->[0];
Branch: 1 branch
BranchTrueFalseTotal
unless $tree = $tree->node->[0] 0 203957 203957
402 }
403 elsif ($key > $$k[-1]) # Greater than largest key in node
404 193491 ▶ {return undef unless $tree = $tree->node->[-1];
Branch: 1 branch
BranchTrueFalseTotal
unless $tree = $tree->node->[-1] 0 193491 193491
405 }
406 else
407 357371 {for my $i(keys @$k) # Search the keys in this node
408 651735 ▶ {if ((my $s = $key <=> $$k[$i]) == 0) # Delete found key
Branch: 2 branches
BranchTrueFalseTotal
if ((my $s = $key <=> $k->[$i]) == 0) { } 240493 411242 651735
elsif ($s < 0) { } 116878 294364 411242
409 240493 {my $d = $tree->data->[$i]; # Save data
410 240493 deleteKey $tree, $i; # Delete the key
411 240493 return $d; # Return data associated with key
412 }
413 elsif ($s < 0) # Less than current key
414 116878 ▶ {return undef unless $tree = $tree->node->[$i];
Branch: 1 branch
BranchTrueFalseTotal
unless $tree = $tree->node->[$i] 0 116878 116878
415 116878 last;
416 }
417 }
418 }
419 }
420 0 confess "Should not happen";
421 }
422  
423 sub insert($$$) # Insert the specified key and data into a tree.
424 243524 ▶ {my ($tree, $key, $data) = @_; # Tree, key, data
Subroutine insert: called CC=10 SCAR=23.1
Pod documented
425 243524 ▶ @_ == 3 or confess;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 3 or confess() 243524 0 243524
426  
427 243524 ▶ if (!(my $n = $tree->keys->@*)) # Empty tree
Branch: 2 branches
BranchTrueFalseTotal
if (not my $n = @{$tree->keys}) { } 2296 241228 243524
elsif ($n < &maximumNumberOfKeys() and @{$tree->node} == 0) { } 6227 235001 241228
428 2296 {push $tree->keys->@*, $key;
429 2296 push $tree->data->@*, $data;
430 2296 return $tree;
431 }
432 ▶ elsif ($n < maximumNumberOfKeys and $tree->node->@* == 0) # Node is root with no children and room for one more key
Condition100%3/3
$n < &maximumNumberOfKeys() and @{$tree->node} == 0
!ll&&!rl&&r
78962271056227
MC/DC100%2/2
$n < &maximumNumberOfKeys() and @{$tree->node} == 0
$n < &maximumNumberOfKeys() @{$tree->node} == 0
Truth table100%3/3
A and B
A= $n < &maximumNumberOfKeys()B= @{$tree->node} == 0
ABresult
0X0
100
111
433 6227 {my $k = $tree->keys;
434 6227 for my $i(reverse keys @$k) # Each key - in reverse due to the preponderance of already sorted data
435 10055 ▶ {if ((my $s = $key <=> $$k[$i]) == 0) # Key already present
Branch: 2 branches
BranchTrueFalseTotal
if ((my $s = $key <=> $k->[$i]) == 0) { } 0 10055 10055
elsif ($s > 0) { } 4082 5973 10055
436 0 {$tree->data->[$i]= $data;
437 0 return;
438 }
439 elsif ($s > 0) # Insert before greatest smaller key
440 4082 {my $I = $i + 1;
441 4082 splice $tree->keys->@*, $I, 0, $key;
442 4082 splice $tree->data->@*, $I, 0, $data;
443 4082 return;
444 }
445 }
446 2145 unshift $tree->keys->@*, $key; # Insert the key at the start of the block because it is less than all the other keys in the block
447 2145 unshift $tree->data->@*, $data;
448 }
449 else # Insert node
450 235001 {my ($compare, $node, $index) = findAndSplit $tree, $key; # Check for existing key
451  
452 235001 ▶ if ($compare == 0) # Found an equal key whose data we can update
Branch: 1 branch
BranchTrueFalseTotal
if ($compare == 0) { } 50 234951 235001
453 50 {$node->data->[$index] = $data;
454 }
455 else # We have room for the insert
456 234951 ▶ {++$index if $compare > 0; # Position at which to insert new key
Branch: 1 branch
BranchTrueFalseTotal
if $compare > 0 80806 154145 234951
457 234951 splice $node->keys->@*, $index, 0, $key;
458 234951 splice $node->data->@*, $index, 0, $data;
459 234951 splitFullNode 0, 1, $node # Split if the leaf is full to force keys up the tree
460 }
461 }
462 }
463  
464 sub iterator($) # Make an iterator for a tree.
465 263 ▶ {my ($tree) = @_; # Tree
Subroutine iterator: called CC=2 SCAR=7.0
Pod documented
466 263 ▶ @_ == 1 or confess;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 1 or confess() 263 0 263
467 263 my $i = genHash(__PACKAGE__.'::Iterator', # Iterator
468 tree => $tree, # Tree we are iterating over
469 node => $tree, # Current node within tree
470 pos => undef, # Current position within node
471 key => undef, # Key at this position
472 data => undef, # Data at this position
473 count => 0, # Counter
474 more => 1, # Iteration not yet finished
475 );
476 263 $i->next; # First element if any
477 263 $i # Iterator
478 }
479  
480 sub Tree::Multi::Iterator::next($) # Find the next key.
481 33522 ▶ {my ($iter) = @_; # Iterator
Subroutine next: called CC=8 SCAR=20.8
482 33522 ▶ @_ == 1 or confess;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 1 or confess() 33522 0 33522
483 33522 ▶ confess unless my $C = $iter->node; # Current node required
Branch: 1 branch
BranchTrueFalseTotal
unless my $C = $iter->node 0 33522 33522
484  
485 33522 ++$iter->count; # Count the calls to the iterator
486  
487 my $new = sub # Load iterator with latest position
488 33259 ▶ {my ($node, $pos) = @_; # Parameters
Subroutine __ANON__: called CC=2 SCAR=6.9
489 33259 $iter->node = $node;
490 33259 ▶ $iter->pos = $pos //= 0;
Condition100%2/2
$pos //= 0
l!l
1658816671
MC/DC100%1/1
$pos //= 0
$pos
Truth table100%2/2
A
A= $pos
Aresult
11
00
491 33259 $iter->key = $node->keys->[$pos];
492 33259 $iter->data = $node->data->[$pos]
493 33522 };
494  
495 33522 ▶ my $done = sub {$iter->more = undef}; # The tree has been completely traversed
Subroutine __ANON__: called CC=1 SCAR=0.0
496  
497 33522 ▶ if (!defined($iter->pos)) # Initial descent
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $iter->pos) 263 33259 33522
498 263 {my $l = $C->node->[0];
499 263 ▶ return $l ? &$new($l->leftMost) : $C->keys->@* ? &$new($C) : &$done; # Start node or done if empty tree
Branch: 2 branches
BranchTrueFalseTotal
$l ? : 260 3 263
@{$C->keys} ? : 3 0 3
500 }
501  
502 my $up = sub # Iterate up to next node that has not been visited
503 16671 ▶ {for(my $n = $C; my $p = $n->up; $n = $p)
Subroutine __ANON__: called CC=3 SCAR=11.0
Branch: 1 branch
BranchTrueFalseTotal
if (my $p = $n->up) 31936 263 32199
504 31936 {my $i = indexInParent $n;
505 31936 ▶ return &$new($p, $i) if $i < $p->keys->@*;
Branch: 1 branch
BranchTrueFalseTotal
if $i < @{$p->keys} 16408 15528 31936
506 }
507 263 &$done # No nodes not visited
508 33259 };
509  
510 33259 my $i = ++$iter->pos;
511 33259 ▶ if (leaf $C) # Leaf
Branch: 1 branch
BranchTrueFalseTotal
if (&leaf($C)) { } 16851 16408 33259
512 16851 ▶ {$i < $C->keys->@* ? &$new($C, $i) : &$up;
Branch: 1 branch
BranchTrueFalseTotal
$i < @{$C->keys} ? : 180 16671 16851
513 }
514 else # Node
515 16408 {&$new($C->node->[$i]->leftMost)
516 }
517 }
518  
519 sub reverseIterator($) # Create a reverse iterator for a tree.
520 65 ▶ {my ($tree) = @_; # Tree
Subroutine reverseIterator: called CC=2 SCAR=7.0
Pod documented
521 65 ▶ @_ == 1 or confess;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 1 or confess() 65 0 65
522 65 my $i = genHash(__PACKAGE__.'::ReverseIterator', # Iterator
523 tree => root($tree), # Tree we are iterating over
524 node => $tree, # Current node within tree
525 pos => undef, # Current position within node
526 key => undef, # Key at this position
527 data => undef, # Data at this position
528 count => 0, # Counter
529 less => 1, # Iteration not yet finished
530 );
531 65 $i->prev; # Last element if any
532 65 $i # Iterator
533 }
534  
535 sub Tree::Multi::ReverseIterator::prev($) # Find the previous key.
536 2210 ▶ {my ($iter) = @_; # Iterator
Subroutine prev: called CC=9 SCAR=22.1
537 2210 ▶ @_ == 1 or confess;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 1 or confess() 2210 0 2210
538 2210 ▶ confess unless my $C = $iter->node; # Current node required
Branch: 1 branch
BranchTrueFalseTotal
unless my $C = $iter->node 0 2210 2210
539  
540 2210 ++$iter->count; # Count the calls to the iterator
541  
542 my $new = sub # Load iterator with latest position
543 2145 ▶ {my ($node, $pos) = @_; # Parameters
Subroutine __ANON__: called CC=2 SCAR=6.9
544 2145 $iter->node = $node;
545 2145 ▶ $iter->pos = $pos //= ($node->keys->@* - 1);
Condition100%2/2
$pos //= @{$node->keys} - 1
l!l
10571088
MC/DC100%1/1
$pos //= @{$node->keys} - 1
$pos
Truth table100%2/2
A
A= $pos
Aresult
11
00
546 2145 $iter->key = $node->keys->[$pos];
547 2145 $iter->data = $node->data->[$pos]
548 2210 };
549  
550 2210 ▶ my $done = sub {$iter->less = undef}; # The tree has been completely traversed
Subroutine __ANON__: called CC=1 SCAR=0.0
551  
552 2210 ▶ if (!defined($iter->pos)) # Initial descent
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $iter->pos) 65 2145 2210
553 65 {my $l = $C->node->[-1];
554 65 ▶ return $l ? &$new($l->rightMost) : $C->keys->@* ? &$new($C) : &$done; # Start node or done if empty tree
Branch: 2 branches
BranchTrueFalseTotal
$l ? : 62 3 65
@{$C->keys} ? : 3 0 3
555 0 return;
556 }
557  
558 my $up = sub # Iterate up to next node that has not been visited
559 1088 ▶ {for(my $n = $C; my $p = $n->up; $n = $p)
Subroutine __ANON__: called CC=3 SCAR=11.0
Branch: 1 branch
BranchTrueFalseTotal
if (my $p = $n->up) 1897 65 1962
560 1897 {my $i = indexInParent $n;
561 1897 ▶ return &$new($p, $i-1) if $i > 0;
Branch: 1 branch
BranchTrueFalseTotal
if $i > 0 1023 874 1897
562 }
563 65 &$done # No nodes not visited
564 2145 };
565  
566 2145 my $i = $iter->pos;
567 2145 ▶ if (leaf $C) # Leaf
Branch: 1 branch
BranchTrueFalseTotal
if (&leaf($C)) { } 1122 1023 2145
568 1122 ▶ {$i > 0 ? &$new($C, $i-1) : &$up;
Branch: 1 branch
BranchTrueFalseTotal
$i > 0 ? : 34 1088 1122
569 }
570 else # Node
571 1023 ▶ {$i >= 0 ? &$new($C->node->[$i]->rightMost) : &$up
Branch: 1 branch
BranchTrueFalseTotal
$i >= 0 ? : 1023 0 1023
572 }
573 }
574  
575 sub flat($@) # Print the keys in a tree from left right to make it easier to visualize the structure of the tree.
576 4 ▶ {my ($tree, @title) = @_; # Tree, title
Subroutine flat: called CC=11 SCAR=24.0
Pod documented
577 4 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 4 4
578 4 my @s; # Print
579 my $D; # Deepest
580 4 ▶ for(my $i = iterator root $tree; $i->more; $i->next) # Traverse tree
Branch: 1 branch
BranchTrueFalseTotal
if ($i->more) 53 4 57
581 53 {my $d = depth $i->node;
582 53 ▶ $D = $d unless $D and $D > $d;
Branch: 1 branch
BranchTrueFalseTotal
unless $D and $D > $d 44 9 53
Condition100%3/3
$D and $D > $d
!ll&&!rl&&r
4409
MC/DC100%2/2
$D and $D > $d
$D $D > $d
Truth table100%3/3
A and B
A= $DB= $D > $d
ABresult
0X0
100
111
583 53 ▶ $s[$d] //= '';
Condition100%2/2
$s[$d] //= ""
l!l
494
MC/DC100%1/1
$s[$d] //= ""
$s[$d]
Truth table100%2/2
A
A= $s[$d]
Aresult
11
00
584 53 $s[$d] .= " ".$i->key; # Add key at appropriate depth
585 53 my $l = length $s[$d];
586 53 for my $j(0..$D) # Pad all strings to the current position
587 175 ▶ {my $s = $s[$j] //= '';
Condition100%2/2
$s[$j] //= ""
l!l
16510
MC/DC100%1/1
$s[$j] //= ""
$s[$j]
Truth table100%2/2
A
A= $s[$j]
Aresult
11
00
588 175 ▶ $s[$j] = substr($s.(' 'x999), 0, $l) if length($s) < $l;
Branch: 1 branch
BranchTrueFalseTotal
if length $s < $l 122 53 175
589 }
590 }
591 4 for my $i(keys @s) # Clean up trailing blanks so that tests are not affected by spurious white space mismatches
592 14 {$s[$i] =~ s/\s+\n/\n/gs;
593 14 $s[$i] =~ s/\s+\Z//gs;
594 }
595 4 ▶ unshift @s, join(' ', @title) if @title; # Add title
Branch: 1 branch
BranchTrueFalseTotal
if @title 0 4 4
596 4 join "\n", @s, '';
597 }
598  
599 sub print($;$) # Print the keys in a tree optionally marking the active key.
600 4 ▶ {my ($tree, $i) = @_; # Tree, optional index of active key
Subroutine print: called CC=2 SCAR=7.7
Pod documented
601 4 ▶ confess unless $tree;
Branch: 1 branch
BranchTrueFalseTotal
unless $tree 0 4 4
602 4 my @s; # Print
603  
604 my $print = sub # Print a node
605 112 ▶ {my ($t, $in) = @_;
Subroutine __ANON__: called CC=10 SCAR=28.2
606 112 ▶ return unless $t and $t->keys and $t->keys->@*;
Branch: 1 branch
BranchTrueFalseTotal
unless $t and $t->keys and @{$t->keys} 0 112 112
Condition33%2/6
$t and $t->keys and @{$t->keys}
!ll&&!rl&&r
00112
$t and $t->keys
!ll&&!rl&&r
00112
MC/DC0%0/3
$t and $t->keys and @{$t->keys}
$t $t->keys @{$t->keys}
Truth table25%1/4
A and B and C
A= $tB= $t->keysC= @{$t->keys}
ABCresult
0XX0
10X0
1100
1111
607  
608 112 my @t = (' 'x$in); # Print keys staring the active key if known
609 112 for my $j(keys $t->keys->@*)
610 557 {push @t, $t->keys->[$j];
611 557 ▶ push @t, '<=' if defined($i) and $i == $j and $tree == $t;
Branch: 1 branch
BranchTrueFalseTotal
if defined $i and $i == $j and $tree == $t 0 557 557
Condition33%2/6
defined $i and $i == $j and $tree == $t
!ll&&!rl&&r
55700
defined $i and $i == $j
!ll&&!rl&&r
55700
MC/DC0%0/3
defined $i and $i == $j and $tree == $t
defined $i $i == $j $tree == $t
Truth table25%1/4
A and B and C
A= defined $iB= $i == $jC= $tree == $t
ABCresult
0XX0
10X0
1100
1111
612 }
613 112 push @s, join ' ', @t; # Details of one node
614  
615 112 ▶ if (my $nodes = $t->node) # Each key
Branch: 1 branch
BranchTrueFalseTotal
if (my $nodes = $t->node) 112 0 112
616 112 {__SUB__->($_, $in+1) for $nodes->@*;
617 }
618 4 };
619  
620 4 &$print(root($tree), 0); # Print tree
621  
622 4 join "\n", @s, ''
623 }
624  
625 sub size($) # Count the number of keys in a tree.
626 11 ▶ {my ($tree) = @_; # Tree
Subroutine size: called CC=2 SCAR=7.1
Pod documented
627 11 ▶ @_ == 1 or confess;
Branch: 1 branch
BranchTrueFalseTotal
@_ == 1 or confess() 11 0 11
628 11 my $n = 0; # Print
629  
630 my $count = sub # Print a node
631 55 ▶ {my ($t) = @_;
Subroutine __ANON__: called CC=6 SCAR=19.0
632 55 ▶ return unless $t and $t->keys and my @k = $t->keys->@*;
Branch: 1 branch
BranchTrueFalseTotal
unless $t and $t->keys and my(@k) = @{$t->keys} 1 54 55
Condition50%3/6
$t and $t->keys and my(@k) = @{$t->keys}
!ll&&!rl&&r
0154
$t and $t->keys
!ll&&!rl&&r
0055
MC/DC33%1/3
$t and $t->keys and my(@k) = @{$t->keys}
$t $t->keys my(@k) = @{$t->keys}
Truth table50%2/4
A and B and C
A= $tB= $t->keysC= my(@k) = @{$t->keys}
ABCresult
0XX0
10X0
1100
1111
633 54 $n += @k;
634 54 ▶ if (my $nodes = $t->node) # Each key
Branch: 1 branch
BranchTrueFalseTotal
if (my $nodes = $t->node) 54 0 54
635 54 {__SUB__->($_) for $nodes->@*;
636 }
637 11 };
638  
639 11 &$count(root $tree); # Count nodes in tree
640  
641 11 $n;
642 }
643  
644 #d
645 #-------------------------------------------------------------------------------
646 # Export - eeee
647 #-------------------------------------------------------------------------------
648  
649 1 ▶use Exporter qw(import);
Subroutine BEGIN: called CC=1 SCAR=0.0
650  
651 1 ▶use vars qw(@ISA @EXPORT @EXPORT_OK %EXPORT_TAGS);
Subroutine BEGIN: called CC=1 SCAR=0.0
652  
653 1 @ISA = qw(Exporter);
654 1 @EXPORT = qw();
655 1 @EXPORT_OK = qw(
656 );
657 1 %EXPORT_TAGS = (all=>[@EXPORT, @EXPORT_OK]);
658  
659 # podDocumentation
660 =pod
661  
662 =encoding utf-8
663  
664 =head1 Name
665  
666 Tree::Multi - Multi-way tree in Pure Perl with an even or odd number of keys per node.
667  
668 =head1 Synopsis
669  
670 Construct and query a multi-way tree in B<100%> Pure Perl with a choice of an
671 odd or an even numbers of keys per node:
672  
673 local $Tree::Multi::numberOfKeysPerNode = 4; # Number of keys per node - can be even
674  
675 my $t = Tree::Multi::new; # Construct tree
676 $t->insert($_, 2 * $_) for reverse 1..32; # Load tree in reverse
677  
678 is_deeply $t->print, <<END;
679 15 21 27
680 3 6 9 12
681 1 2
682 4 5
683 7 8
684 10 11
685 13 14
686 18
687 16 17
688 19 20
689 24
690 22 23
691 25 26
692 30
693 28 29
694 31 32
695 END
696  
697 ok $t->height == 3; # Height
698  
699 ok $t->find (16) == 32; # Find by key
700 $t->delete(16); # Delete a key
701 ok !$t->find (16); # Key no longer present
702  
703  
704 ok $t->find (17) == 34; # Find by key
705 my @k;
706 for(my $i = $t->iterator; $i->more; $i->next) # Iterator
707 {push @k, $i->key unless $i->key == 17;
708 }
709  
710 $t->delete($_) for @k; # Delete
711  
712 ok $t->find(17) == 34 && $t->size == 1; # Size
713  
714 =head1 Description
715  
716 Multi-way tree in Pure Perl with an even or odd number of keys per node.
717  
718  
719 Version "20210629".
720  
721  
722 The following sections describe the methods in each functional area of this
723 module. For an alphabetic listing of all methods by name see L<Index|/Index>.
724  
725  
726  
727 =head1 Multi-way Tree
728  
729 Create and use a multi-way tree.
730  
731 =head2 root($tree)
732  
733 Return the root node of a tree.
734  
735 Parameter Description
736 1 $tree Tree
737  
738 B<Example:>
739  
740  
741 local $numberOfKeysPerNode = 3; my $N = 13; my $t = new;
742
743 for my $n(1..$N)
744 {$t->insert($n, $n);
745 }
746
747 ok T($t, <<END);
748 4 8
749 2
750 1
751 3
752 6
753 5
754 7
755 10 12
756 9
757 11
758 13
759 END
760
761 is_deeply $t->leftMost ->keys, [1];
762 is_deeply $t->rightMost->keys, [13];
763 ok $t->leftMost ->leaf;
764 ok $t->rightMost->leaf;
765
766 ok $t->root == $t; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
767  
768
769  
770 =head2 leaf($tree)
771  
772 Confirm that the tree is a leaf.
773  
774 Parameter Description
775 1 $tree Tree
776  
777 B<Example:>
778  
779  
780 local $numberOfKeysPerNode = 3; my $N = 13; my $t = new;
781
782 for my $n(1..$N)
783 {$t->insert($n, $n);
784 }
785
786 ok T($t, <<END);
787 4 8
788 2
789 1
790 3
791 6
792 5
793 7
794 10 12
795 9
796 11
797 13
798 END
799
800 is_deeply $t->leftMost ->keys, [1];
801 is_deeply $t->rightMost->keys, [13];
802
803 ok $t->leftMost ->leaf; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
804  
805
806 ok $t->rightMost->leaf; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
807  
808 ok $t->root == $t;
809
810  
811 =head2 find($root, $key)
812  
813 Find a key in a tree returning its associated data or undef if the key does not exist.
814  
815 Parameter Description
816 1 $root Root of tree
817 2 $key Key
818  
819 B<Example:>
820  
821  
822 local $Tree::Multi::numberOfKeysPerNode = 4; # Number of keys per node - can be even
823
824 my $t = Tree::Multi::new; # Construct tree
825 $t->insert($_, 2 * $_) for reverse 1..32; # Load tree in reverse
826
827 T($t, <<END);
828 17 25
829 9 13
830 3 5 7
831 1 2
832 4
833 6
834 8
835 11
836 10
837 12
838 15
839 14
840 16
841 21
842 19
843 18
844 20
845 23
846 22
847 24
848 29
849 27
850 26
851 28
852 31
853 30
854 32
855 END
856
857 ok $t->size == 32; # Size
858 ok $t->height == 4; # Height
859 ok $t->delete(16) == 2 * 16; # Delete a key
860
861 ok !$t->find (16); # Key no longer present # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
862  
863
864 ok $t->find (17) == 34; # Find by key # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
865  
866
867 my @k;
868 for(my $i = $t->iterator; $i->more; $i->next) # Iterator
869 {push @k, $i->key unless $i->key == 17;
870 }
871
872 ok $t->delete($_) == 2 * $_ for @k; # Delete
873
874
875 ok $t->find(17) == 34 && $t->size == 1; # Size # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
876  
877
878 local $Tree::Multi::numberOfKeysPerNode = 3; # Number of keys per node - can be even
879
880 my $t = Tree::Multi::new; # Construct tree
881 $t->insert($_, $_) for 1..8;
882
883 T($t, <<END, 1);
884
885 4
886 2 6
887 1 3 5 7 8
888 END
889
890 local $Tree::Multi::numberOfKeysPerNode = 14; # Number of keys per node - can be even
891
892 my $t = Tree::Multi::new; # Construct tree
893 $t->insert($_, $_) for 1..15;
894
895 T($t, <<END, 1);
896
897 8
898 1 2 3 4 5 6 7 9 10 11 12 13 14 15
899 END
900
901  
902 =head2 leftMost($tree)
903  
904 Return the left most node below the specified one.
905  
906 Parameter Description
907 1 $tree Tree
908  
909 B<Example:>
910  
911  
912 local $numberOfKeysPerNode = 3; my $N = 13; my $t = new;
913
914 for my $n(1..$N)
915 {$t->insert($n, $n);
916 }
917
918 ok T($t, <<END);
919 4 8
920 2
921 1
922 3
923 6
924 5
925 7
926 10 12
927 9
928 11
929 13
930 END
931
932
933 is_deeply $t->leftMost ->keys, [1]; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
934  
935 is_deeply $t->rightMost->keys, [13];
936
937 ok $t->leftMost ->leaf; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
938  
939 ok $t->rightMost->leaf;
940 ok $t->root == $t;
941
942  
943 =head2 rightMost($tree)
944  
945 Return the right most node below the specified one.
946  
947 Parameter Description
948 1 $tree Tree
949  
950 B<Example:>
951  
952  
953 local $numberOfKeysPerNode = 3; my $N = 13; my $t = new;
954
955 for my $n(1..$N)
956 {$t->insert($n, $n);
957 }
958
959 ok T($t, <<END);
960 4 8
961 2
962 1
963 3
964 6
965 5
966 7
967 10 12
968 9
969 11
970 13
971 END
972
973 is_deeply $t->leftMost ->keys, [1];
974
975 is_deeply $t->rightMost->keys, [13]; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
976  
977 ok $t->leftMost ->leaf;
978
979 ok $t->rightMost->leaf; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
980  
981 ok $t->root == $t;
982
983  
984 =head2 height($tree)
985  
986 Return the height of the tree.
987  
988 Parameter Description
989 1 $tree Tree
990  
991 B<Example:>
992  
993  
994 local $Tree::Multi::numberOfKeysPerNode = 3;
995
996 my $t = new; ok $t->height == 0; ok $t->leftMost->depth == 0; ok $t->size == 0; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
997  
998
999 $t->insert(1, 1); ok $t->height == 1; ok $t->leftMost->depth == 1; ok $t->size == 1; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1000  
1001
1002 $t->insert(2, 2); ok $t->height == 1; ok $t->leftMost->depth == 1; ok $t->size == 2; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1003  
1004
1005 $t->insert(3, 3); ok $t->height == 1; ok $t->leftMost->depth == 1; ok $t->size == 3; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1006  
1007
1008 $t->insert(4, 4); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 4; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1009  
1010
1011 $t->insert(5, 5); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 5; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1012  
1013
1014 $t->insert(6, 6); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 6; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1015  
1016
1017 $t->insert(7, 7); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 7; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1018  
1019
1020 $t->insert(8, 8); ok $t->height == 3; ok $t->leftMost->depth == 3; ok $t->size == 8; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1021  
1022
1023 T($t, <<END, 1);
1024
1025 4
1026 2 6
1027 1 3 5 7 8
1028 END
1029
1030
1031  
1032 =head2 depth($tree)
1033  
1034 Return the depth of a node within a tree.
1035  
1036 Parameter Description
1037 1 $tree Tree
1038  
1039 B<Example:>
1040  
1041  
1042 local $Tree::Multi::numberOfKeysPerNode = 3;
1043
1044 my $t = new; ok $t->height == 0; ok $t->leftMost->depth == 0; ok $t->size == 0; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1045  
1046
1047 $t->insert(1, 1); ok $t->height == 1; ok $t->leftMost->depth == 1; ok $t->size == 1; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1048  
1049
1050 $t->insert(2, 2); ok $t->height == 1; ok $t->leftMost->depth == 1; ok $t->size == 2; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1051  
1052
1053 $t->insert(3, 3); ok $t->height == 1; ok $t->leftMost->depth == 1; ok $t->size == 3; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1054  
1055
1056 $t->insert(4, 4); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 4; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1057  
1058
1059 $t->insert(5, 5); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 5; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1060  
1061
1062 $t->insert(6, 6); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 6; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1063  
1064
1065 $t->insert(7, 7); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 7; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1066  
1067
1068 $t->insert(8, 8); ok $t->height == 3; ok $t->leftMost->depth == 3; ok $t->size == 8; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1069  
1070
1071 T($t, <<END, 1);
1072
1073 4
1074 2 6
1075 1 3 5 7 8
1076 END
1077
1078
1079  
1080 =head2 delete($root, $key)
1081  
1082 Find a key in a tree, delete it and return any associated data.
1083  
1084 Parameter Description
1085 1 $root Tree root
1086 2 $key Key
1087  
1088 B<Example:>
1089  
1090  
1091 local $Tree::Multi::numberOfKeysPerNode = 4; # Number of keys per node - can be even
1092
1093 my $t = Tree::Multi::new; # Construct tree
1094 $t->insert($_, 2 * $_) for reverse 1..32; # Load tree in reverse
1095
1096 T($t, <<END);
1097 17 25
1098 9 13
1099 3 5 7
1100 1 2
1101 4
1102 6
1103 8
1104 11
1105 10
1106 12
1107 15
1108 14
1109 16
1110 21
1111 19
1112 18
1113 20
1114 23
1115 22
1116 24
1117 29
1118 27
1119 26
1120 28
1121 31
1122 30
1123 32
1124 END
1125
1126 ok $t->size == 32; # Size
1127 ok $t->height == 4; # Height
1128
1129 ok $t->delete(16) == 2 * 16; # Delete a key # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1130  
1131 ok !$t->find (16); # Key no longer present
1132 ok $t->find (17) == 34; # Find by key
1133
1134 my @k;
1135 for(my $i = $t->iterator; $i->more; $i->next) # Iterator
1136 {push @k, $i->key unless $i->key == 17;
1137 }
1138
1139
1140 ok $t->delete($_) == 2 * $_ for @k; # Delete # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1141  
1142
1143 ok $t->find(17) == 34 && $t->size == 1; # Size
1144
1145 local $Tree::Multi::numberOfKeysPerNode = 3; # Number of keys per node - can be even
1146
1147 my $t = Tree::Multi::new; # Construct tree
1148 $t->insert($_, $_) for 1..8;
1149
1150 T($t, <<END, 1);
1151
1152 4
1153 2 6
1154 1 3 5 7 8
1155 END
1156
1157 local $Tree::Multi::numberOfKeysPerNode = 14; # Number of keys per node - can be even
1158
1159 my $t = Tree::Multi::new; # Construct tree
1160 $t->insert($_, $_) for 1..15;
1161
1162 T($t, <<END, 1);
1163
1164 8
1165 1 2 3 4 5 6 7 9 10 11 12 13 14 15
1166 END
1167
1168  
1169 =head2 insert($tree, $key, $data)
1170  
1171 Insert the specified key and data into a tree.
1172  
1173 Parameter Description
1174 1 $tree Tree
1175 2 $key Key
1176 3 $data Data
1177  
1178 B<Example:>
1179  
1180  
1181 local $Tree::Multi::numberOfKeysPerNode = 4; # Number of keys per node - can be even
1182
1183 my $t = Tree::Multi::new; # Construct tree
1184
1185 $t->insert($_, 2 * $_) for reverse 1..32; # Load tree in reverse # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1186  
1187
1188 T($t, <<END);
1189 17 25
1190 9 13
1191 3 5 7
1192 1 2
1193 4
1194 6
1195 8
1196 11
1197 10
1198 12
1199 15
1200 14
1201 16
1202 21
1203 19
1204 18
1205 20
1206 23
1207 22
1208 24
1209 29
1210 27
1211 26
1212 28
1213 31
1214 30
1215 32
1216 END
1217
1218 ok $t->size == 32; # Size
1219 ok $t->height == 4; # Height
1220 ok $t->delete(16) == 2 * 16; # Delete a key
1221 ok !$t->find (16); # Key no longer present
1222 ok $t->find (17) == 34; # Find by key
1223
1224 my @k;
1225 for(my $i = $t->iterator; $i->more; $i->next) # Iterator
1226 {push @k, $i->key unless $i->key == 17;
1227 }
1228
1229 ok $t->delete($_) == 2 * $_ for @k; # Delete
1230
1231 ok $t->find(17) == 34 && $t->size == 1; # Size
1232
1233 local $Tree::Multi::numberOfKeysPerNode = 3; # Number of keys per node - can be even
1234
1235 my $t = Tree::Multi::new; # Construct tree
1236
1237 $t->insert($_, $_) for 1..8; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1238  
1239
1240 T($t, <<END, 1);
1241
1242 4
1243 2 6
1244 1 3 5 7 8
1245 END
1246
1247 local $Tree::Multi::numberOfKeysPerNode = 14; # Number of keys per node - can be even
1248
1249 my $t = Tree::Multi::new; # Construct tree
1250
1251 $t->insert($_, $_) for 1..15; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1252  
1253
1254 T($t, <<END, 1);
1255
1256 8
1257 1 2 3 4 5 6 7 9 10 11 12 13 14 15
1258 END
1259
1260  
1261 =head2 iterator($tree)
1262  
1263 Make an iterator for a tree.
1264  
1265 Parameter Description
1266 1 $tree Tree
1267  
1268 B<Example:>
1269  
1270  
1271 local $numberOfKeysPerNode = 3; my $N = 256; my $e = 0; my $t = new;
1272
1273 for my $n(0..$N)
1274 {$t->insert($n, $n);
1275
1276 my @n; for(my $i = $t->iterator; $i->more; $i->next) {push @n, $i->key} # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1277  
1278 ++$e unless dump(\@n) eq dump [0..$n];
1279 }
1280
1281 is_deeply $e, 0;
1282
1283 local $Tree::Multi::numberOfKeysPerNode = 4; # Number of keys per node - can be even
1284
1285 my $t = Tree::Multi::new; # Construct tree
1286 $t->insert($_, 2 * $_) for reverse 1..32; # Load tree in reverse
1287
1288 T($t, <<END);
1289 17 25
1290 9 13
1291 3 5 7
1292 1 2
1293 4
1294 6
1295 8
1296 11
1297 10
1298 12
1299 15
1300 14
1301 16
1302 21
1303 19
1304 18
1305 20
1306 23
1307 22
1308 24
1309 29
1310 27
1311 26
1312 28
1313 31
1314 30
1315 32
1316 END
1317
1318 ok $t->size == 32; # Size
1319 ok $t->height == 4; # Height
1320 ok $t->delete(16) == 2 * 16; # Delete a key
1321 ok !$t->find (16); # Key no longer present
1322 ok $t->find (17) == 34; # Find by key
1323
1324 my @k;
1325
1326 for(my $i = $t->iterator; $i->more; $i->next) # Iterator # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1327  
1328 {push @k, $i->key unless $i->key == 17;
1329 }
1330
1331 ok $t->delete($_) == 2 * $_ for @k; # Delete
1332
1333 ok $t->find(17) == 34 && $t->size == 1; # Size
1334
1335 local $Tree::Multi::numberOfKeysPerNode = 3; # Number of keys per node - can be even
1336
1337 my $t = Tree::Multi::new; # Construct tree
1338 $t->insert($_, $_) for 1..8;
1339
1340 T($t, <<END, 1);
1341
1342 4
1343 2 6
1344 1 3 5 7 8
1345 END
1346
1347 local $Tree::Multi::numberOfKeysPerNode = 14; # Number of keys per node - can be even
1348
1349 my $t = Tree::Multi::new; # Construct tree
1350 $t->insert($_, $_) for 1..15;
1351
1352 T($t, <<END, 1);
1353
1354 8
1355 1 2 3 4 5 6 7 9 10 11 12 13 14 15
1356 END
1357
1358  
1359 =head2 Tree::Multi::Iterator::next($iter)
1360  
1361 Find the next key.
1362  
1363 Parameter Description
1364 1 $iter Iterator
1365  
1366 B<Example:>
1367  
1368  
1369 local $numberOfKeysPerNode = 3; my $N = 256; my $e = 0; my $t = new;
1370
1371 for my $n(0..$N)
1372 {$t->insert($n, $n);
1373 my @n; for(my $i = $t->iterator; $i->more; $i->next) {push @n, $i->key}
1374 ++$e unless dump(\@n) eq dump [0..$n];
1375 }
1376
1377 is_deeply $e, 0;
1378
1379  
1380 =head2 reverseIterator($tree)
1381  
1382 Create a reverse iterator for a tree.
1383  
1384 Parameter Description
1385 1 $tree Tree
1386  
1387 B<Example:>
1388  
1389  
1390 local $numberOfKeysPerNode = 3; my $N = 64; my $e = 0;
1391
1392 for my $n(0..$N)
1393 {my $t = new;
1394 for my $i(0..$n)
1395 {$t->insert($i, $i);
1396 }
1397 my @n;
1398
1399 for(my $i = $t->reverseIterator; $i->less; $i->prev) # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1400  
1401 {push @n, $i->key;
1402 }
1403 ++$e unless dump(\@n) eq dump [reverse 0..$n];
1404 }
1405
1406 is_deeply $e, 0;
1407
1408  
1409 =head2 Tree::Multi::ReverseIterator::prev($iter)
1410  
1411 Find the previous key.
1412  
1413 Parameter Description
1414 1 $iter Iterator
1415  
1416 B<Example:>
1417  
1418  
1419 local $numberOfKeysPerNode = 3; my $N = 64; my $e = 0;
1420
1421 for my $n(0..$N)
1422 {my $t = new;
1423 for my $i(0..$n)
1424 {$t->insert($i, $i);
1425 }
1426 my @n;
1427 for(my $i = $t->reverseIterator; $i->less; $i->prev)
1428 {push @n, $i->key;
1429 }
1430 ++$e unless dump(\@n) eq dump [reverse 0..$n];
1431 }
1432
1433 is_deeply $e, 0;
1434
1435  
1436 =head2 flat($tree, @title)
1437  
1438 Print the keys in a tree from left right to make it easier to visualize the structure of the tree.
1439  
1440 Parameter Description
1441 1 $tree Tree
1442 2 @title Title
1443  
1444 B<Example:>
1445  
1446  
1447 local $Tree::Multi::numberOfKeysPerNode = 3;
1448 my $t = new; ok $t->height == 0; ok $t->leftMost->depth == 0; ok $t->size == 0;
1449 $t->insert(1, 1); ok $t->height == 1; ok $t->leftMost->depth == 1; ok $t->size == 1;
1450 $t->insert(2, 2); ok $t->height == 1; ok $t->leftMost->depth == 1; ok $t->size == 2;
1451 $t->insert(3, 3); ok $t->height == 1; ok $t->leftMost->depth == 1; ok $t->size == 3;
1452 $t->insert(4, 4); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 4;
1453 $t->insert(5, 5); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 5;
1454 $t->insert(6, 6); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 6;
1455 $t->insert(7, 7); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 7;
1456 $t->insert(8, 8); ok $t->height == 3; ok $t->leftMost->depth == 3; ok $t->size == 8;
1457
1458 T($t, <<END, 1);
1459
1460 4
1461 2 6
1462 1 3 5 7 8
1463 END
1464
1465
1466  
1467 =head2 print($tree, $i)
1468  
1469 Print the keys in a tree optionally marking the active key.
1470  
1471 Parameter Description
1472 1 $tree Tree
1473 2 $i Optional index of active key
1474  
1475 B<Example:>
1476  
1477  
1478 local $Tree::Multi::numberOfKeysPerNode = 4; # Number of keys per node - can be even
1479
1480 my $t = Tree::Multi::new; # Construct tree
1481 $t->insert($_, 2 * $_) for reverse 1..32; # Load tree in reverse
1482
1483 T($t, <<END);
1484 17 25
1485 9 13
1486 3 5 7
1487 1 2
1488 4
1489 6
1490 8
1491 11
1492 10
1493 12
1494 15
1495 14
1496 16
1497 21
1498 19
1499 18
1500 20
1501 23
1502 22
1503 24
1504 29
1505 27
1506 26
1507 28
1508 31
1509 30
1510 32
1511 END
1512
1513 ok $t->size == 32; # Size
1514 ok $t->height == 4; # Height
1515 ok $t->delete(16) == 2 * 16; # Delete a key
1516 ok !$t->find (16); # Key no longer present
1517 ok $t->find (17) == 34; # Find by key
1518
1519 my @k;
1520 for(my $i = $t->iterator; $i->more; $i->next) # Iterator
1521 {push @k, $i->key unless $i->key == 17;
1522 }
1523
1524 ok $t->delete($_) == 2 * $_ for @k; # Delete
1525
1526 ok $t->find(17) == 34 && $t->size == 1; # Size
1527
1528 local $Tree::Multi::numberOfKeysPerNode = 3; # Number of keys per node - can be even
1529
1530 my $t = Tree::Multi::new; # Construct tree
1531 $t->insert($_, $_) for 1..8;
1532
1533 T($t, <<END, 1);
1534
1535 4
1536 2 6
1537 1 3 5 7 8
1538 END
1539
1540 local $Tree::Multi::numberOfKeysPerNode = 14; # Number of keys per node - can be even
1541
1542 my $t = Tree::Multi::new; # Construct tree
1543 $t->insert($_, $_) for 1..15;
1544
1545 T($t, <<END, 1);
1546
1547 8
1548 1 2 3 4 5 6 7 9 10 11 12 13 14 15
1549 END
1550
1551  
1552 =head2 size($tree)
1553  
1554 Count the number of keys in a tree.
1555  
1556 Parameter Description
1557 1 $tree Tree
1558  
1559 B<Example:>
1560  
1561  
1562 local $Tree::Multi::numberOfKeysPerNode = 3;
1563
1564 my $t = new; ok $t->height == 0; ok $t->leftMost->depth == 0; ok $t->size == 0; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1565  
1566
1567 $t->insert(1, 1); ok $t->height == 1; ok $t->leftMost->depth == 1; ok $t->size == 1; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1568  
1569
1570 $t->insert(2, 2); ok $t->height == 1; ok $t->leftMost->depth == 1; ok $t->size == 2; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1571  
1572
1573 $t->insert(3, 3); ok $t->height == 1; ok $t->leftMost->depth == 1; ok $t->size == 3; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1574  
1575
1576 $t->insert(4, 4); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 4; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1577  
1578
1579 $t->insert(5, 5); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 5; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1580  
1581
1582 $t->insert(6, 6); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 6; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1583  
1584
1585 $t->insert(7, 7); ok $t->height == 2; ok $t->leftMost->depth == 2; ok $t->size == 7; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1586  
1587
1588 $t->insert(8, 8); ok $t->height == 3; ok $t->leftMost->depth == 3; ok $t->size == 8; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1589  
1590
1591 T($t, <<END, 1);
1592
1593 4
1594 2 6
1595 1 3 5 7 8
1596 END
1597
1598
1599  
1600  
1601 =head1 Hash Definitions
1602  
1603  
1604  
1605  
1606 =head2 Tree::Multi Definition
1607  
1608  
1609 Iterator
1610  
1611  
1612  
1613  
1614 =head3 Output fields
1615  
1616  
1617 =head4 count
1618  
1619 Counter
1620  
1621 =head4 data
1622  
1623 Data at this position
1624  
1625 =head4 key
1626  
1627 Key at this position
1628  
1629 =head4 keys
1630  
1631 Array of key items for this node
1632  
1633 =head4 less
1634  
1635 Iteration not yet finished
1636  
1637 =head4 more
1638  
1639 Iteration not yet finished
1640  
1641 =head4 node
1642  
1643 Current node within tree
1644  
1645 =head4 pos
1646  
1647 Current position within node
1648  
1649 =head4 tree
1650  
1651 Tree we are iterating over
1652  
1653 =head4 up
1654  
1655 Parent node
1656  
1657  
1658  
1659 =head1 Private Methods
1660  
1661 =head2 new()
1662  
1663 Create a new multi-way tree node.
1664  
1665  
1666 B<Example:>
1667  
1668  
1669 local $Tree::Multi::numberOfKeysPerNode = 4; # Number of keys per node - can be even
1670
1671
1672 my $t = Tree::Multi::new; # Construct tree # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1673  
1674 $t->insert($_, 2 * $_) for reverse 1..32; # Load tree in reverse
1675
1676 T($t, <<END);
1677 17 25
1678 9 13
1679 3 5 7
1680 1 2
1681 4
1682 6
1683 8
1684 11
1685 10
1686 12
1687 15
1688 14
1689 16
1690 21
1691 19
1692 18
1693 20
1694 23
1695 22
1696 24
1697 29
1698 27
1699 26
1700 28
1701 31
1702 30
1703 32
1704 END
1705
1706 ok $t->size == 32; # Size
1707 ok $t->height == 4; # Height
1708 ok $t->delete(16) == 2 * 16; # Delete a key
1709 ok !$t->find (16); # Key no longer present
1710 ok $t->find (17) == 34; # Find by key
1711
1712 my @k;
1713 for(my $i = $t->iterator; $i->more; $i->next) # Iterator
1714 {push @k, $i->key unless $i->key == 17;
1715 }
1716
1717 ok $t->delete($_) == 2 * $_ for @k; # Delete
1718
1719 ok $t->find(17) == 34 && $t->size == 1; # Size
1720
1721 local $Tree::Multi::numberOfKeysPerNode = 3; # Number of keys per node - can be even
1722
1723
1724 my $t = Tree::Multi::new; # Construct tree # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1725  
1726 $t->insert($_, $_) for 1..8;
1727
1728 T($t, <<END, 1);
1729
1730 4
1731 2 6
1732 1 3 5 7 8
1733 END
1734
1735 local $Tree::Multi::numberOfKeysPerNode = 14; # Number of keys per node - can be even
1736
1737
1738 my $t = Tree::Multi::new; # Construct tree # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲
1739  
1740 $t->insert($_, $_) for 1..15;
1741
1742 T($t, <<END, 1);
1743
1744 8
1745 1 2 3 4 5 6 7 9 10 11 12 13 14 15
1746 END
1747
1748  
1749 =head2 minimumNumberOfKeys()
1750  
1751 Minimum number of keys per node.
1752  
1753  
1754 =head2 maximumNumberOfKeys()
1755  
1756 Maximum number of keys per node.
1757  
1758  
1759 =head2 maximumNumberOfNodes()
1760  
1761 Maximum number of children per parent.
1762  
1763  
1764 =head2 full($tree)
1765  
1766 Confirm that a node is full.
1767  
1768 Parameter Description
1769 1 $tree Tree
1770  
1771 =head2 halfFull($tree)
1772  
1773 Confirm that a node is half full.
1774  
1775 Parameter Description
1776 1 $tree Tree
1777  
1778 =head2 reUp($tree, $children)
1779  
1780 Reconnect the children to their new parent.
1781  
1782 Parameter Description
1783 1 $tree Tree
1784 2 $children Children
1785  
1786 =head2 splitFullNode($isRoot, $isLeaf, $node)
1787  
1788 Split a node if it is full.
1789  
1790 Parameter Description
1791 1 $isRoot Known to be the root if true
1792 2 $isLeaf Known to be a leaf if true
1793 3 $node Node to split
1794  
1795 =head2 findAndSplit($root, $key)
1796  
1797 Find a key in a tree splitting full nodes along the path to the key.
1798  
1799 Parameter Description
1800 1 $root Root of tree
1801 2 $key Key
1802  
1803 =head2 indexInParent($tree)
1804  
1805 Get the index of a node in its parent.
1806  
1807 Parameter Description
1808 1 $tree Tree
1809  
1810 =head2 fillFromLeftOrRight($node, $dir)
1811  
1812 Fill a node from the specified sibling.
1813  
1814 Parameter Description
1815 1 $node Node to fill
1816 2 $dir Node to fill from 0 for left or 1 for right
1817  
1818 =head2 mergeWithLeftOrRight($n, $dir)
1819  
1820 Merge two adjacent nodes.
1821  
1822 Parameter Description
1823 1 $n Node to merge into
1824 2 $dir Node to merge is on right if 1 else left
1825  
1826 =head2 merge($tree)
1827  
1828 Merge the current node with its sibling.
1829  
1830 Parameter Description
1831 1 $tree Tree
1832  
1833 =head2 mergeOrFill($tree)
1834  
1835 Make a node larger than a half node.
1836  
1837 Parameter Description
1838 1 $tree Tree
1839  
1840 =head2 deleteLeafKey($tree, $i)
1841  
1842 Delete a key in a leaf.
1843  
1844 Parameter Description
1845 1 $tree Tree
1846 2 $i Index to delete at
1847  
1848 =head2 deleteKey($tree, $i)
1849  
1850 Delete a key.
1851  
1852 Parameter Description
1853 1 $tree Tree
1854 2 $i Index to delete at
1855  
1856 =head2 T($tree, $expected, $flat)
1857  
1858 Print a tree to the log file and check it against the expected result
1859  
1860 Parameter Description
1861 1 $tree Tree
1862 2 $expected Expected print
1863 3 $flat Optionally print in flat mode if true
1864  
1865 =head2 F($tree, $expected)
1866  
1867 Print a tree flatly to the log file and check its result
1868  
1869 Parameter Description
1870 1 $tree Tree
1871 2 $expected Expected print
1872  
1873 =head2 disordered($n, $N)
1874  
1875 Disordered but stable insertions
1876  
1877 Parameter Description
1878 1 $n Keys per node
1879 2 $N Nodes
1880  
1881 =head2 disorderedCheck($t, $n, $N)
1882  
1883 Check disordered insertions
1884  
1885 Parameter Description
1886 1 $t Tree to check
1887 2 $n Keys per node
1888 3 $N Nodes
1889  
1890 =head2 randomCheck($n, $N, $T)
1891  
1892 Random insertions
1893  
1894 Parameter Description
1895 1 $n Keys per node
1896 2 $N Log 10 nodes
1897 3 $T Log 10 number of tests
1898  
1899  
1900 =head1 Index
1901  
1902  
1903 1 L<delete|/delete> - Find a key in a tree, delete it and return any associated data.
1904  
1905 2 L<deleteKey|/deleteKey> - Delete a key.
1906  
1907 3 L<deleteLeafKey|/deleteLeafKey> - Delete a key in a leaf.
1908  
1909 4 L<depth|/depth> - Return the depth of a node within a tree.
1910  
1911 5 L<disordered|/disordered> - Disordered but stable insertions
1912  
1913 6 L<disorderedCheck|/disorderedCheck> - Check disordered insertions
1914  
1915 7 L<F|/F> - Print a tree flatly to the log file and check its result
1916  
1917 8 L<fillFromLeftOrRight|/fillFromLeftOrRight> - Fill a node from the specified sibling.
1918  
1919 9 L<find|/find> - Find a key in a tree returning its associated data or undef if the key does not exist.
1920  
1921 10 L<findAndSplit|/findAndSplit> - Find a key in a tree splitting full nodes along the path to the key.
1922  
1923 11 L<flat|/flat> - Print the keys in a tree from left right to make it easier to visualize the structure of the tree.
1924  
1925 12 L<full|/full> - Confirm that a node is full.
1926  
1927 13 L<halfFull|/halfFull> - Confirm that a node is half full.
1928  
1929 14 L<height|/height> - Return the height of the tree.
1930  
1931 15 L<indexInParent|/indexInParent> - Get the index of a node in its parent.
1932  
1933 16 L<insert|/insert> - Insert the specified key and data into a tree.
1934  
1935 17 L<iterator|/iterator> - Make an iterator for a tree.
1936  
1937 18 L<leaf|/leaf> - Confirm that the tree is a leaf.
1938  
1939 19 L<leftMost|/leftMost> - Return the left most node below the specified one.
1940  
1941 20 L<maximumNumberOfKeys|/maximumNumberOfKeys> - Maximum number of keys per node.
1942  
1943 21 L<maximumNumberOfNodes|/maximumNumberOfNodes> - Maximum number of children per parent.
1944  
1945 22 L<merge|/merge> - Merge the current node with its sibling.
1946  
1947 23 L<mergeOrFill|/mergeOrFill> - Make a node larger than a half node.
1948  
1949 24 L<mergeWithLeftOrRight|/mergeWithLeftOrRight> - Merge two adjacent nodes.
1950  
1951 25 L<minimumNumberOfKeys|/minimumNumberOfKeys> - Minimum number of keys per node.
1952  
1953 26 L<new|/new> - Create a new multi-way tree node.
1954  
1955 27 L<print|/print> - Print the keys in a tree optionally marking the active key.
1956  
1957 28 L<randomCheck|/randomCheck> - Random insertions
1958  
1959 29 L<reUp|/reUp> - Reconnect the children to their new parent.
1960  
1961 30 L<reverseIterator|/reverseIterator> - Create a reverse iterator for a tree.
1962  
1963 31 L<rightMost|/rightMost> - Return the right most node below the specified one.
1964  
1965 32 L<root|/root> - Return the root node of a tree.
1966  
1967 33 L<size|/size> - Count the number of keys in a tree.
1968  
1969 34 L<splitFullNode|/splitFullNode> - Split a node if it is full.
1970  
1971 35 L<T|/T> - Print a tree to the log file and check it against the expected result
1972  
1973 36 L<Tree::Multi::Iterator::next|/Tree::Multi::Iterator::next> - Find the next key.
1974  
1975 37 L<Tree::Multi::ReverseIterator::prev|/Tree::Multi::ReverseIterator::prev> - Find the previous key.
1976  
1977 =head1 Installation
1978  
1979 This module is written in 100% Pure Perl and, thus, it is easy to read,
1980 comprehend, use, modify and install via B<cpan>:
1981  
1982 sudo cpan install Tree::Multi
1983  
1984 =head1 Author
1985  
1986 L<philiprbrenan@gmail.com|mailto:philiprbrenan@gmail.com>
1987  
1988 L<http://www.appaapps.com|http://www.appaapps.com>
1989  
1990 =head1 Copyright
1991  
1992 Copyright (c) 2016-2021 Philip R Brenan.
1993  
1994 This module is free software. It may be used, redistributed and/or modified
1995 under the same terms as Perl itself.
1996  
1997 =cut
1998  
1999  
2000  
2001 # Tests and documentation
2002  
2003 sub test
2004 1 ▶ {my $p = __PACKAGE__;
Subroutine test: called CC=5 SCAR=16.6
Pod undocumented
2005 1 binmode($_, ":utf8") for *STDOUT, *STDERR;
2006 1 ▶ return if eval "eof(${p}::DATA)";
Branch: 1 branch
BranchTrueFalseTotal
if eval "eof(${p}::DATA)" 0 1 1
2007 1 my $s = eval "join('', <${p}::DATA>)";
2008 1 ▶ $@ and die $@;
Branch: 1 branch
BranchTrueFalseTotal
$@ and die $@ 0 1 1
2009 0 ▶ eval $s;
Subroutine BEGIN: called CC=1 SCAR=0.1
Subroutine BEGIN: called CC=1 SCAR=0.1
Subroutine F: not called CC=1 SCAR=0.1
Subroutine T: called CC=5 SCAR=16.6
Subroutine disordered: called CC=2 SCAR=7.1
Subroutine disorderedCheck: called CC=6 SCAR=18.5
Subroutine randomCheck: called CC=6 SCAR=18.5
Pod documented
Pod documented
Pod documented
Pod documented
Pod documented
Branch: 10 branches
BranchTrueFalseTotal
unless ref $tree 0 8 8
$flat ? : 4 4 8
unless $develop 8 0 8
unless $s 0 0 0
unless $t->find($k) == $t{$k} 0 462 462
if defined $t->find($k) 0 462 462
if $t->height > $h 0 462 462
unless $t->height == 0 0 2 2
unless $t->find($k) == $t{$k} 0 240000 240000
if defined $t->find($k) 0 240000 240000
2010 1 ▶ $@ and die $@;
Branch: 1 branch
BranchTrueFalseTotal
$@ and die $@ 0 1 1
2011 1 1
2012 }
2013  
2014 1 ▶test unless caller;
Branch: 1 branch
BranchTrueFalseTotal
unless caller 0 1 1
2015  
2016 1 1;
2017 # podDocumentation
2018 __DATA__
↑ Summary