| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 45 | 0 | my $n = $tree->keys->@*; | |||||||||||||||||||||||||||||||||||||||||||||
| 46 | 0 | ▶ | $n <= maximumNumberOfKeys or confess "Keys"; | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 53 | 1181414 | my $n = $tree->keys->@*; | |||||||||||||||||||||||||||||||||||||||||||||
| 54 | 1181414 | ▶ | $n <= maximumNumberOfKeys+1 or confess "Keys"; | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 61 | 85 | ▶ | for(; $tree->up; $tree = $tree->up) {} | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 74 | 120704 | ▶ | $tree->keys->@* <= maximumNumberOfKeys or confess "Keys"; | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 85 | 1131110 | ▶ | return unless $c == maximumNumberOfKeys; # Only split full nodes | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 86 | } | ||||||||||||||||||||||||||||||||||||||||||||||
| 87 | |||||||||||||||||||||||||||||||||||||||||||||||
| 88 | 129341 | ▶ | my ($p, $l, $r) = ($node->up // $node, new, new); # New child nodes | ||||||||||||||||||||||||||||||||||||||||||||
|
Condition66%2/3
$node->up // $node
MC/DC0%0/2
$node->up // $node
$node->up
$node
Truth table66%2/3
A // B
A= $node->upB= $node
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 137 | |||||||||||||||||||||||||||||||||||||||||||||||
| 138 | 896159 | ▶ | if ($key < $k[0]) # Less than smallest key in node | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 139 | 340484 | ▶ | {return (-1, $tree, 0) unless my $n = $tree->node->[0]; | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 140 | 257473 | $tree = $n; | |||||||||||||||||||||||||||||||||||||||||||||
| 141 | 257473 | next; | |||||||||||||||||||||||||||||||||||||||||||||
| 142 | } | ||||||||||||||||||||||||||||||||||||||||||||||
| 143 | |||||||||||||||||||||||||||||||||||||||||||||||
| 144 | 555675 | ▶ | if ($key > $k[-1]) # Greater than largest key in node | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 145 | 328042 | ▶ | {return (+1, $tree, $#k) unless my $n = $tree->node->[-1]; | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 175 | |||||||||||||||||||||||||||||||||||||||||||||||
| 176 | 1672581 | ▶ | if ($key < $k[0]) # Less than smallest key in node | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 177 | 578714 | ▶ | {return undef unless $tree = $tree->node->[0]; | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 178 | 482895 | next; | |||||||||||||||||||||||||||||||||||||||||||||
| 179 | } | ||||||||||||||||||||||||||||||||||||||||||||||
| 180 | |||||||||||||||||||||||||||||||||||||||||||||||
| 181 | 1093867 | ▶ | if ($key > $k[-1]) # Greater than largest key in node | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 182 | 556990 | ▶ | {return undef unless $tree = $tree->node->[-1]; | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 189 | 860868 | ▶ | if ($s < 0) # Less than current key | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 190 | 295389 | ▶ | {return undef unless $tree = $tree->node->[$i]; | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 202 | |||||||||||||||||||||||||||||||||||||||||||||||
| 203 | 426471 | ▶ | my @n = $p->node->@*; for my $i(keys @n) {return $i if $n[$i] == $tree} | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 210 | |||||||||||||||||||||||||||||||||||||||||||||||
| 211 | 76682 | ▶ | confess unless my $p = $node->up; # Parent of leaf | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 212 | 76682 | my $i = indexInParent $node; # Index of leaf in parent | |||||||||||||||||||||||||||||||||||||||||||||
| 213 | |||||||||||||||||||||||||||||||||||||||||||||||
| 214 | 76682 | ▶ | if ($dir) # Fill from right | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 215 | 9153 | ▶ | {$i < $p->node->@* - 1 or confess; # Cannot fill from right | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 241 | |||||||||||||||||||||||||||||||||||||||||||||||
| 242 | 119637 | ▶ | confess unless halfFull($n); # Confirm leaf is half full | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 243 | 119637 | ▶ | confess unless my $p = $n->up; # Parent of leaf | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
Condition66%2/3
&halfFull($p) and $p->up
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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 249 | 23173 | ▶ | {$i < $p->node->@* - 1 or confess; # Cannot fill from right | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 279 | 163993 | {my $l = $tree->up->node->[$i-1]; # Left node | |||||||||||||||||||||||||||||||||||||||||||||
| 280 | 163993 | ▶ | if (halfFull(my $r = $tree)) | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 281 | 163993 | ▶ | {$l->halfFull ? mergeWithLeftOrRight $r, 0 : fillFromLeftOrRight $r, 0; # Merge as left and right nodes are half full | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 282 | } | ||||||||||||||||||||||||||||||||||||||||||||||
| 283 | } | ||||||||||||||||||||||||||||||||||||||||||||||
| 284 | else | ||||||||||||||||||||||||||||||||||||||||||||||
| 285 | 32326 | {my $r = $tree->up->node->[1]; # Right node | |||||||||||||||||||||||||||||||||||||||||||||
| 286 | 32326 | ▶ | if (halfFull(my $l = $tree)) | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 287 | 32326 | ▶ | {halfFull($r) ? mergeWithLeftOrRight $l, 1 : fillFromLeftOrRight $l, 1; # Merge as left and right nodes are half full | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 295 | |||||||||||||||||||||||||||||||||||||||||||||||
| 296 | 408082 | ▶ | return unless halfFull($tree); # No need to merge of if not a half node | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 297 | 203996 | ▶ | confess unless my $p = $tree->up; # Parent exists | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 298 | |||||||||||||||||||||||||||||||||||||||||||||||
| 299 | 203996 | ▶ | if ($p->up) # Merge or fill parent which is not the root | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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])
@{$p->keys} == 1 and &halfFull(my $l = $p->node->[0])
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])
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 338 | 476 | ▶ | {return $n + 1 if $tree->keys->@*; # We are in a partially full leaf | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
Condition100%3/3
$tree->up or @{$tree->keys}
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}
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 359 | 240493 | ▶ | confess "Not a leaf" unless leaf $tree; | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 375 | 240493 | ▶ | if (leaf $tree) # Delete from a leaf | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 401 | 203957 | ▶ | {return undef unless $tree = $tree->node->[0]; | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 402 | } | ||||||||||||||||||||||||||||||||||||||||||||||
| 403 | elsif ($key > $$k[-1]) # Greater than largest key in node | ||||||||||||||||||||||||||||||||||||||||||||||
| 404 | 193491 | ▶ | {return undef unless $tree = $tree->node->[-1]; | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 426 | |||||||||||||||||||||||||||||||||||||||||||||||
| 427 | 243524 | ▶ | if (!(my $n = $tree->keys->@*)) # Empty tree | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 483 | 33522 | ▶ | confess unless my $C = $iter->node; # Current node required | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
MC/DC100%1/1
$pos //= 0
$pos
Truth table100%2/2
A
A= $pos
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 504 | 31936 | {my $i = indexInParent $n; | |||||||||||||||||||||||||||||||||||||||||||||
| 505 | 31936 | ▶ | return &$new($p, $i) if $i < $p->keys->@*; | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 512 | 16851 | ▶ | {$i < $C->keys->@* ? &$new($C, $i) : &$up; | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 538 | 2210 | ▶ | confess unless my $C = $iter->node; # Current node required | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
MC/DC100%1/1
$pos //= @{$node->keys} - 1
$pos
Truth table100%2/2
A
A= $pos
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 560 | 1897 | {my $i = indexInParent $n; | |||||||||||||||||||||||||||||||||||||||||||||
| 561 | 1897 | ▶ | return &$new($p, $i-1) if $i > 0; | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 568 | 1122 | ▶ | {$i > 0 ? &$new($C, $i-1) : &$up; | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 569 | } | ||||||||||||||||||||||||||||||||||||||||||||||
| 570 | else # Node | ||||||||||||||||||||||||||||||||||||||||||||||
| 571 | 1023 | ▶ | {$i >= 0 ? &$new($C->node->[$i]->rightMost) : &$up | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 581 | 53 | {my $d = depth $i->node; | |||||||||||||||||||||||||||||||||||||||||||||
| 582 | 53 | ▶ | $D = $d unless $D and $D > $d; | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$D and $D > $d
MC/DC100%2/2
$D and $D > $d
$D
$D > $d
Truth table100%3/3
A and B
A= $DB= $D > $d
| |||||||||||||||||||||||||||||||||||||||||||||||
| 583 | 53 | ▶ | $s[$d] //= ''; | ||||||||||||||||||||||||||||||||||||||||||||
|
Condition100%2/2
$s[$d] //= ""
MC/DC100%1/1
$s[$d] //= ""
$s[$d]
Truth table100%2/2
A
A= $s[$d]
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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] //= ""
MC/DC100%1/1
$s[$j] //= ""
$s[$j]
Truth table100%2/2
A
A= $s[$j]
| |||||||||||||||||||||||||||||||||||||||||||||||
| 588 | 175 | ▶ | $s[$j] = substr($s.(' 'x999), 0, $l) if length($s) < $l; | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
Condition33%2/6
$t and $t->keys and @{$t->keys}
$t and $t->keys
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}
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
Condition33%2/6
defined $i and $i == $j and $tree == $t
defined $i and $i == $j
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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 612 | } | ||||||||||||||||||||||||||||||||||||||||||||||
| 613 | 112 | push @s, join ' ', @t; # Details of one node | |||||||||||||||||||||||||||||||||||||||||||||
| 614 | |||||||||||||||||||||||||||||||||||||||||||||||
| 615 | 112 | ▶ | if (my $nodes = $t->node) # Each key | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
Condition50%3/6
$t and $t->keys and my(@k) = @{$t->keys}
$t and $t->keys
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}
| |||||||||||||||||||||||||||||||||||||||||||||||
| 633 | 54 | $n += @k; | |||||||||||||||||||||||||||||||||||||||||||||
| 634 | 54 | ▶ | if (my $nodes = $t->node) # Each key | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 2007 | 1 | my $s = eval "join('', <${p}::DATA>)"; | |||||||||||||||||||||||||||||||||||||||||||||
| 2008 | 1 | ▶ | $@ and die $@; | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||
| 2010 | 1 | ▶ | $@ and die $@; | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 2011 | 1 | 1 | |||||||||||||||||||||||||||||||||||||||||||||
| 2012 | } | ||||||||||||||||||||||||||||||||||||||||||||||
| 2013 | |||||||||||||||||||||||||||||||||||||||||||||||
| 2014 | 1 | ▶ | test unless caller; | ||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||
| 2015 | |||||||||||||||||||||||||||||||||||||||||||||||
| 2016 | 1 | 1; | |||||||||||||||||||||||||||||||||||||||||||||
| 2017 | # podDocumentation | ||||||||||||||||||||||||||||||||||||||||||||||
| 2018 | __DATA__ | ||||||||||||||||||||||||||||||||||||||||||||||