| 1 | #!/usr/bin/perl -I/home/phil/perl/cpan/DataTableText/lib/ | ||||||||||||
| 2 | #------------------------------------------------------------------------------- | ||||||||||||
| 3 | # Trek through a tree one character at a time. | ||||||||||||
| 4 | # Philip R Brenan at appaapps dot com, Appa Apps Ltd Inc., 2021 | ||||||||||||
| 5 | #------------------------------------------------------------------------------- | ||||||||||||
| 6 | # podDocumentation | ||||||||||||
| 7 | package Tree::Trek; | ||||||||||||
| 8 | 1 | our $VERSION = "20210425"; | |||||||||||
| 9 | 1 | ▶ | use warnings FATAL => qw(all); | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 10 | 1 | ▶ | use strict; | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 11 | 1 | ▶ | use Carp qw(confess cluck); | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 12 | 1 | ▶ | use Data::Dump qw(dump); | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 13 | 1 | ▶ | use Data::Table::Text qw(:all); | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 14 | 1 | ▶ | use feature qw(say current_sub); | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 15 | |||||||||||||
| 16 | 1 | my $debug = -e q(/home/phil/); # Developing | |||||||||||
| 17 | |||||||||||||
| 18 | #D1 Tree::Trek # Methods to create and traverse a trekkable tree. | ||||||||||||
| 19 | |||||||||||||
| 20 | sub node(;$$) # Create a new node | ||||||||||||
| 21 | 8 | ▶ | {my ($parent, $char) = @_; # Optional parent, character we came through on | ||||||||||
|
Subroutine
node: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||
| 22 | 8 | ▶ | genHash(__PACKAGE__, | ||||||||||
|
Condition100%2/2
$char // ""
MC/DC100%1/1
$char // ""
$char
Truth table100%2/2
A
A= $char
| |||||||||||||
| 23 | jumps => {}, # {character => node} | ||||||||||||
| 24 | data => undef, # The data attached to this node | ||||||||||||
| 25 | parent => $parent, # The node from whence we came | ||||||||||||
| 26 | char => $char//'', # The character we trekked in on or the empty string if we are at the root | ||||||||||||
| 27 | ); | ||||||||||||
| 28 | } | ||||||||||||
| 29 | |||||||||||||
| 30 | sub put($$) # Add a key to the tree | ||||||||||||
| 31 | 5 | ▶ | {my ($tree, $key) = @_; # Tree, key | ||||||||||
|
Subroutine
put: called CC=4 SCAR=13.9
Pod
documented
| |||||||||||||
| 32 | |||||||||||||
| 33 | 5 | ▶ | return $tree unless $key; # Key is empty so we have found the desired node | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 34 | |||||||||||||
| 35 | 5 | for my $i(1..length $key) # Jump on each character | |||||||||||
| 36 | 11 | {my $c = substr $key, $i-1, 1; # Next character of the key | |||||||||||
| 37 | |||||||||||||
| 38 | 11 | ▶ | if (exists $tree->jumps->{$c}) # Jump through existing node | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 39 | 4 | {$tree = $tree->jumps->{$c}; | |||||||||||
| 40 | } | ||||||||||||
| 41 | else # Create a new node and jump through it | ||||||||||||
| 42 | 7 | {$tree = ($tree->jumps->{$c} = node $tree, $c); | |||||||||||
| 43 | } | ||||||||||||
| 44 | } | ||||||||||||
| 45 | |||||||||||||
| 46 | $tree # Last node we reached at the end of the string | ||||||||||||
| 47 | 5 | } | |||||||||||
| 48 | |||||||||||||
| 49 | sub key($) # Return the key of a node | ||||||||||||
| 50 | 5 | ▶ | {my ($node) = @_; # Node | ||||||||||
|
Subroutine
key: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||
| 51 | 5 | my $k = ''; | |||||||||||
| 52 | 5 | ▶ | for(my $n = $node; $n; $n = $n->parent) | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 53 | 16 | {$k .= $n->char | |||||||||||
| 54 | } | ||||||||||||
| 55 | 5 | scalar reverse $k; | |||||||||||
| 56 | } | ||||||||||||
| 57 | |||||||||||||
| 58 | sub find($$) # Find a key in a tree - return its node if such a node exists else undef | ||||||||||||
| 59 | 23 | ▶ | {my ($tree, $key) = @_; # Tree, key | ||||||||||
|
Subroutine
find: called CC=4 SCAR=13.9
Pod
documented
| |||||||||||||
| 60 | |||||||||||||
| 61 | 23 | ▶ | return $tree unless $key; # We have exhausted the key so this must be the node in question as long as it has no jumps | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 62 | |||||||||||||
| 63 | 23 | for my $i(1..length $key) # Jump on each character | |||||||||||
| 64 | 38 | {my $c = substr $key, $i-1, 1; # Next character of the key | |||||||||||
| 65 | 38 | ▶ | if (exists $tree->jumps->{$c}) # Continue search | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 66 | 31 | {$tree = $tree->jumps->{$c}; | |||||||||||
| 67 | 31 | next; | |||||||||||
| 68 | } | ||||||||||||
| 69 | 7 | return undef; # No such jump | |||||||||||
| 70 | } | ||||||||||||
| 71 | $tree # Not found | ||||||||||||
| 72 | 16 | } | |||||||||||
| 73 | |||||||||||||
| 74 | sub delete($) # Remove a node from a tree | ||||||||||||
| 75 | 5 | ▶ | {my ($node) = @_; # Node to be removed | ||||||||||
|
Subroutine
delete: called CC=5 SCAR=16.1
Pod
documented
| |||||||||||||
| 76 | |||||||||||||
| 77 | 5 | $node->data = undef; # Clear data | |||||||||||
| 78 | 5 | ▶ | if (! keys $node->jumps->%*) # No jumps from this node and no data so we can clear it from the parent | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 79 | 4 | ▶ | {for(my $n = $node; $n; $n = $n->parent) # Up through ancestors | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 80 | 8 | ▶ | {if (my $p = $n->parent) # Parent of current node | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 81 | 7 | {delete $p->jumps->{$n->char}; # Delete path to empty node | |||||||||||
| 82 | 7 | ▶ | last if keys $p->jumps->%*; # Repeat for parent if this node is now empty | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 83 | } | ||||||||||||
| 84 | } | ||||||||||||
| 85 | } | ||||||||||||
| 86 | $node | ||||||||||||
| 87 | 5 | } | |||||||||||
| 88 | |||||||||||||
| 89 | sub count($) # Count the nodes addressed in the specified tree | ||||||||||||
| 90 | 34 | ▶ | {my ($node) = @_; # Node to be counted from | ||||||||||
|
Subroutine
count: called CC=3 SCAR=11.0
Pod
documented
| |||||||||||||
| 91 | 34 | ▶ | my $n = $node->data ? 1 : 0; # Count the nodes addressed in the specified tree | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 92 | 34 | for my $c(keys $node->jumps->%*) # Each possible child | |||||||||||
| 93 | 28 | {$n += $node->jumps->{$c}->count; # Each child of the parent | |||||||||||
| 94 | } | ||||||||||||
| 95 | $n # Count | ||||||||||||
| 96 | 34 | } | |||||||||||
| 97 | |||||||||||||
| 98 | sub traverse($) # Traverse a tree returning an array of nodes | ||||||||||||
| 99 | 8 | ▶ | {my ($node) = @_; # Node to be counted from | ||||||||||
|
Subroutine
traverse: called CC=3 SCAR=11.0
Pod
documented
| |||||||||||||
| 100 | 8 | my @n; | |||||||||||
| 101 | 8 | ▶ | push @n, $node if $node->data; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 102 | 8 | for my $c(sort keys $node->jumps->%*) # Each possible child in key order | |||||||||||
| 103 | 7 | {push @n, $node->jumps->{$c}->traverse; | |||||||||||
| 104 | } | ||||||||||||
| 105 | @n | ||||||||||||
| 106 | 8 | } | |||||||||||
| 107 | |||||||||||||
| 108 | #d | ||||||||||||
| 109 | #------------------------------------------------------------------------------- | ||||||||||||
| 110 | # Export | ||||||||||||
| 111 | #------------------------------------------------------------------------------- | ||||||||||||
| 112 | |||||||||||||
| 113 | 1 | ▶ | use Exporter qw(import); | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 114 | |||||||||||||
| 115 | 1 | ▶ | use vars qw(@ISA @EXPORT @EXPORT_OK %EXPORT_TAGS); | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 116 | |||||||||||||
| 117 | 1 | @ISA = qw(Exporter); | |||||||||||
| 118 | 1 | @EXPORT = qw(); | |||||||||||
| 119 | 1 | @EXPORT_OK = qw( | |||||||||||
| 120 | ); | ||||||||||||
| 121 | 1 | %EXPORT_TAGS = (all=>[@EXPORT, @EXPORT_OK]); | |||||||||||
| 122 | |||||||||||||
| 123 | # podDocumentation | ||||||||||||
| 124 | =pod | ||||||||||||
| 125 | |||||||||||||
| 126 | =encoding utf-8 | ||||||||||||
| 127 | |||||||||||||
| 128 | =head1 Name | ||||||||||||
| 129 | |||||||||||||
| 130 | Tree::Trek - Trek through a tree one character at a time. | ||||||||||||
| 131 | |||||||||||||
| 132 | =head1 Synopsis | ||||||||||||
| 133 | |||||||||||||
| 134 | Create a trekkable tree and trek through it: | ||||||||||||
| 135 | |||||||||||||
| 136 | my $n = node; | ||||||||||||
| 137 | |||||||||||||
| 138 | $n->put("aa") ->data = "AA"; | ||||||||||||
| 139 | $n->put("ab") ->data = "AB"; | ||||||||||||
| 140 | $n->put("ba") ->data = "BA"; | ||||||||||||
| 141 | $n->put("bb") ->data = "BB"; | ||||||||||||
| 142 | $n->put("aaa")->data = "AAA"; | ||||||||||||
| 143 | |||||||||||||
| 144 | is_deeply [map {[$_->key, $_->data]} $n->traverse], | ||||||||||||
| 145 | [["aa", "AA"], | ||||||||||||
| 146 | ["aaa", "AAA"], | ||||||||||||
| 147 | ["ab", "AB"], | ||||||||||||
| 148 | ["ba", "BA"], | ||||||||||||
| 149 | ["bb", "BB"]]; | ||||||||||||
| 150 | |||||||||||||
| 151 | =head1 Description | ||||||||||||
| 152 | |||||||||||||
| 153 | Trek through a tree one character at a time. | ||||||||||||
| 154 | |||||||||||||
| 155 | |||||||||||||
| 156 | Version "20210424". | ||||||||||||
| 157 | |||||||||||||
| 158 | |||||||||||||
| 159 | The following sections describe the methods in each functional area of this | ||||||||||||
| 160 | module. For an alphabetic listing of all methods by name see L<Index|/Index>. | ||||||||||||
| 161 | |||||||||||||
| 162 | |||||||||||||
| 163 | |||||||||||||
| 164 | =head1 Tree::Trek | ||||||||||||
| 165 | |||||||||||||
| 166 | Methods to create a trekkable tree. | ||||||||||||
| 167 | |||||||||||||
| 168 | =head2 node($parent) | ||||||||||||
| 169 | |||||||||||||
| 170 | Create a new node | ||||||||||||
| 171 | |||||||||||||
| 172 | Parameter Description | ||||||||||||
| 173 | 1 $parent Optional parent | ||||||||||||
| 174 | |||||||||||||
| 175 | B<Example:> | ||||||||||||
| 176 | |||||||||||||
| 177 | |||||||||||||
| 178 | if (1) | ||||||||||||
| 179 | |||||||||||||
| 180 | {my $n = node; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 181 | |||||||||||||
| 182 | $n->put("aa")->data = "AA"; | ||||||||||||
| 183 | $n->put("ab")->data = "AB"; | ||||||||||||
| 184 | $n->put("ba")->data = "BA"; | ||||||||||||
| 185 | $n->put("bb")->data = "BB"; | ||||||||||||
| 186 | $n->put("aaa")->data = "AAA"; | ||||||||||||
| 187 | is_deeply $n->count, 5; | ||||||||||||
| 188 | |||||||||||||
| 189 | is_deeply $n->find("aa") ->data, "AA"; | ||||||||||||
| 190 | is_deeply $n->find("ab") ->data, "AB"; | ||||||||||||
| 191 | is_deeply $n->find("ba") ->data, "BA"; | ||||||||||||
| 192 | is_deeply $n->find("bb") ->data, "BB"; | ||||||||||||
| 193 | is_deeply $n->find("aaa")->data, "AAA"; | ||||||||||||
| 194 | |||||||||||||
| 195 | is_deeply [map {[$_->key, $_->data]} $n->traverse], | ||||||||||||
| 196 | [["aa", "AA"], | ||||||||||||
| 197 | ["aaa", "AAA"], | ||||||||||||
| 198 | ["ab", "AB"], | ||||||||||||
| 199 | ["ba", "BA"], | ||||||||||||
| 200 | ["bb", "BB"]]; | ||||||||||||
| 201 | |||||||||||||
| 202 | ok $n->find("a"); | ||||||||||||
| 203 | ok !$n->find("a")->data; | ||||||||||||
| 204 | ok $n->find("b"); | ||||||||||||
| 205 | ok !$n->find("b")->data; | ||||||||||||
| 206 | ok !$n->find("c"); | ||||||||||||
| 207 | |||||||||||||
| 208 | ok $n->find("aa")->delete; ok $n->find("aa"); is_deeply $n->count, 4; | ||||||||||||
| 209 | ok $n->find("ab")->delete; ok !$n->find("ab"); is_deeply $n->count, 3; | ||||||||||||
| 210 | ok $n->find("ba")->delete; ok !$n->find("ba"); is_deeply $n->count, 2; | ||||||||||||
| 211 | ok $n->find("bb")->delete; ok !$n->find("bb"); is_deeply $n->count, 1; | ||||||||||||
| 212 | |||||||||||||
| 213 | ok $n->find("a"); | ||||||||||||
| 214 | ok !$n->find("b"); | ||||||||||||
| 215 | |||||||||||||
| 216 | ok $n->find("aaa")->delete; ok !$n->find("aaa"); is_deeply $n->count, 0; | ||||||||||||
| 217 | ok !$n->find("a"); | ||||||||||||
| 218 | } | ||||||||||||
| 219 | |||||||||||||
| 220 | |||||||||||||
| 221 | =head2 put($tree, $key) | ||||||||||||
| 222 | |||||||||||||
| 223 | Add a key to the tree | ||||||||||||
| 224 | |||||||||||||
| 225 | Parameter Description | ||||||||||||
| 226 | 1 $tree Tree | ||||||||||||
| 227 | 2 $key Key | ||||||||||||
| 228 | |||||||||||||
| 229 | B<Example:> | ||||||||||||
| 230 | |||||||||||||
| 231 | |||||||||||||
| 232 | if (1) | ||||||||||||
| 233 | {my $n = node; | ||||||||||||
| 234 | |||||||||||||
| 235 | $n->put("aa")->data = "AA"; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 236 | |||||||||||||
| 237 | |||||||||||||
| 238 | $n->put("ab")->data = "AB"; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 239 | |||||||||||||
| 240 | |||||||||||||
| 241 | $n->put("ba")->data = "BA"; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 242 | |||||||||||||
| 243 | |||||||||||||
| 244 | $n->put("bb")->data = "BB"; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 245 | |||||||||||||
| 246 | |||||||||||||
| 247 | $n->put("aaa")->data = "AAA"; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 248 | |||||||||||||
| 249 | is_deeply $n->count, 5; | ||||||||||||
| 250 | |||||||||||||
| 251 | is_deeply $n->find("aa") ->data, "AA"; | ||||||||||||
| 252 | is_deeply $n->find("ab") ->data, "AB"; | ||||||||||||
| 253 | is_deeply $n->find("ba") ->data, "BA"; | ||||||||||||
| 254 | is_deeply $n->find("bb") ->data, "BB"; | ||||||||||||
| 255 | is_deeply $n->find("aaa")->data, "AAA"; | ||||||||||||
| 256 | |||||||||||||
| 257 | is_deeply [map {[$_->key, $_->data]} $n->traverse], | ||||||||||||
| 258 | [["aa", "AA"], | ||||||||||||
| 259 | ["aaa", "AAA"], | ||||||||||||
| 260 | ["ab", "AB"], | ||||||||||||
| 261 | ["ba", "BA"], | ||||||||||||
| 262 | ["bb", "BB"]]; | ||||||||||||
| 263 | |||||||||||||
| 264 | ok $n->find("a"); | ||||||||||||
| 265 | ok !$n->find("a")->data; | ||||||||||||
| 266 | ok $n->find("b"); | ||||||||||||
| 267 | ok !$n->find("b")->data; | ||||||||||||
| 268 | ok !$n->find("c"); | ||||||||||||
| 269 | |||||||||||||
| 270 | ok $n->find("aa")->delete; ok $n->find("aa"); is_deeply $n->count, 4; | ||||||||||||
| 271 | ok $n->find("ab")->delete; ok !$n->find("ab"); is_deeply $n->count, 3; | ||||||||||||
| 272 | ok $n->find("ba")->delete; ok !$n->find("ba"); is_deeply $n->count, 2; | ||||||||||||
| 273 | ok $n->find("bb")->delete; ok !$n->find("bb"); is_deeply $n->count, 1; | ||||||||||||
| 274 | |||||||||||||
| 275 | ok $n->find("a"); | ||||||||||||
| 276 | ok !$n->find("b"); | ||||||||||||
| 277 | |||||||||||||
| 278 | ok $n->find("aaa")->delete; ok !$n->find("aaa"); is_deeply $n->count, 0; | ||||||||||||
| 279 | ok !$n->find("a"); | ||||||||||||
| 280 | } | ||||||||||||
| 281 | |||||||||||||
| 282 | |||||||||||||
| 283 | =head2 key($node) | ||||||||||||
| 284 | |||||||||||||
| 285 | Return the key of a node | ||||||||||||
| 286 | |||||||||||||
| 287 | Parameter Description | ||||||||||||
| 288 | 1 $node Node | ||||||||||||
| 289 | |||||||||||||
| 290 | B<Example:> | ||||||||||||
| 291 | |||||||||||||
| 292 | |||||||||||||
| 293 | if (1) | ||||||||||||
| 294 | {my $n = node; | ||||||||||||
| 295 | $n->put("aa")->data = "AA"; | ||||||||||||
| 296 | $n->put("ab")->data = "AB"; | ||||||||||||
| 297 | $n->put("ba")->data = "BA"; | ||||||||||||
| 298 | $n->put("bb")->data = "BB"; | ||||||||||||
| 299 | $n->put("aaa")->data = "AAA"; | ||||||||||||
| 300 | is_deeply $n->count, 5; | ||||||||||||
| 301 | |||||||||||||
| 302 | is_deeply $n->find("aa") ->data, "AA"; | ||||||||||||
| 303 | is_deeply $n->find("ab") ->data, "AB"; | ||||||||||||
| 304 | is_deeply $n->find("ba") ->data, "BA"; | ||||||||||||
| 305 | is_deeply $n->find("bb") ->data, "BB"; | ||||||||||||
| 306 | is_deeply $n->find("aaa")->data, "AAA"; | ||||||||||||
| 307 | |||||||||||||
| 308 | |||||||||||||
| 309 | is_deeply [map {[$_->key, $_->data]} $n->traverse], # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 310 | |||||||||||||
| 311 | [["aa", "AA"], | ||||||||||||
| 312 | ["aaa", "AAA"], | ||||||||||||
| 313 | ["ab", "AB"], | ||||||||||||
| 314 | ["ba", "BA"], | ||||||||||||
| 315 | ["bb", "BB"]]; | ||||||||||||
| 316 | |||||||||||||
| 317 | ok $n->find("a"); | ||||||||||||
| 318 | ok !$n->find("a")->data; | ||||||||||||
| 319 | ok $n->find("b"); | ||||||||||||
| 320 | ok !$n->find("b")->data; | ||||||||||||
| 321 | ok !$n->find("c"); | ||||||||||||
| 322 | |||||||||||||
| 323 | ok $n->find("aa")->delete; ok $n->find("aa"); is_deeply $n->count, 4; | ||||||||||||
| 324 | ok $n->find("ab")->delete; ok !$n->find("ab"); is_deeply $n->count, 3; | ||||||||||||
| 325 | ok $n->find("ba")->delete; ok !$n->find("ba"); is_deeply $n->count, 2; | ||||||||||||
| 326 | ok $n->find("bb")->delete; ok !$n->find("bb"); is_deeply $n->count, 1; | ||||||||||||
| 327 | |||||||||||||
| 328 | ok $n->find("a"); | ||||||||||||
| 329 | ok !$n->find("b"); | ||||||||||||
| 330 | |||||||||||||
| 331 | ok $n->find("aaa")->delete; ok !$n->find("aaa"); is_deeply $n->count, 0; | ||||||||||||
| 332 | ok !$n->find("a"); | ||||||||||||
| 333 | } | ||||||||||||
| 334 | |||||||||||||
| 335 | |||||||||||||
| 336 | =head2 find($tree, $key) | ||||||||||||
| 337 | |||||||||||||
| 338 | Find a key in a tree - return its node if such a node exists else undef | ||||||||||||
| 339 | |||||||||||||
| 340 | Parameter Description | ||||||||||||
| 341 | 1 $tree Tree | ||||||||||||
| 342 | 2 $key Key | ||||||||||||
| 343 | |||||||||||||
| 344 | B<Example:> | ||||||||||||
| 345 | |||||||||||||
| 346 | |||||||||||||
| 347 | if (1) | ||||||||||||
| 348 | {my $n = node; | ||||||||||||
| 349 | $n->put("aa")->data = "AA"; | ||||||||||||
| 350 | $n->put("ab")->data = "AB"; | ||||||||||||
| 351 | $n->put("ba")->data = "BA"; | ||||||||||||
| 352 | $n->put("bb")->data = "BB"; | ||||||||||||
| 353 | $n->put("aaa")->data = "AAA"; | ||||||||||||
| 354 | is_deeply $n->count, 5; | ||||||||||||
| 355 | |||||||||||||
| 356 | |||||||||||||
| 357 | is_deeply $n->find("aa") ->data, "AA"; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 358 | |||||||||||||
| 359 | |||||||||||||
| 360 | is_deeply $n->find("ab") ->data, "AB"; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 361 | |||||||||||||
| 362 | |||||||||||||
| 363 | is_deeply $n->find("ba") ->data, "BA"; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 364 | |||||||||||||
| 365 | |||||||||||||
| 366 | is_deeply $n->find("bb") ->data, "BB"; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 367 | |||||||||||||
| 368 | |||||||||||||
| 369 | is_deeply $n->find("aaa")->data, "AAA"; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 370 | |||||||||||||
| 371 | |||||||||||||
| 372 | is_deeply [map {[$_->key, $_->data]} $n->traverse], | ||||||||||||
| 373 | [["aa", "AA"], | ||||||||||||
| 374 | ["aaa", "AAA"], | ||||||||||||
| 375 | ["ab", "AB"], | ||||||||||||
| 376 | ["ba", "BA"], | ||||||||||||
| 377 | ["bb", "BB"]]; | ||||||||||||
| 378 | |||||||||||||
| 379 | |||||||||||||
| 380 | ok $n->find("a"); # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 381 | |||||||||||||
| 382 | |||||||||||||
| 383 | ok !$n->find("a")->data; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 384 | |||||||||||||
| 385 | |||||||||||||
| 386 | ok $n->find("b"); # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 387 | |||||||||||||
| 388 | |||||||||||||
| 389 | ok !$n->find("b")->data; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 390 | |||||||||||||
| 391 | |||||||||||||
| 392 | ok !$n->find("c"); # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 393 | |||||||||||||
| 394 | |||||||||||||
| 395 | |||||||||||||
| 396 | ok $n->find("aa")->delete; ok $n->find("aa"); is_deeply $n->count, 4; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 397 | |||||||||||||
| 398 | |||||||||||||
| 399 | ok $n->find("ab")->delete; ok !$n->find("ab"); is_deeply $n->count, 3; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 400 | |||||||||||||
| 401 | |||||||||||||
| 402 | ok $n->find("ba")->delete; ok !$n->find("ba"); is_deeply $n->count, 2; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 403 | |||||||||||||
| 404 | |||||||||||||
| 405 | ok $n->find("bb")->delete; ok !$n->find("bb"); is_deeply $n->count, 1; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 406 | |||||||||||||
| 407 | |||||||||||||
| 408 | |||||||||||||
| 409 | ok $n->find("a"); # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 410 | |||||||||||||
| 411 | |||||||||||||
| 412 | ok !$n->find("b"); # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 413 | |||||||||||||
| 414 | |||||||||||||
| 415 | |||||||||||||
| 416 | ok $n->find("aaa")->delete; ok !$n->find("aaa"); is_deeply $n->count, 0; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 417 | |||||||||||||
| 418 | |||||||||||||
| 419 | ok !$n->find("a"); # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 420 | |||||||||||||
| 421 | } | ||||||||||||
| 422 | |||||||||||||
| 423 | |||||||||||||
| 424 | =head2 delete($node) | ||||||||||||
| 425 | |||||||||||||
| 426 | Remove a node from a tree | ||||||||||||
| 427 | |||||||||||||
| 428 | Parameter Description | ||||||||||||
| 429 | 1 $node Node to be removed | ||||||||||||
| 430 | |||||||||||||
| 431 | B<Example:> | ||||||||||||
| 432 | |||||||||||||
| 433 | |||||||||||||
| 434 | if (1) | ||||||||||||
| 435 | {my $n = node; | ||||||||||||
| 436 | $n->put("aa")->data = "AA"; | ||||||||||||
| 437 | $n->put("ab")->data = "AB"; | ||||||||||||
| 438 | $n->put("ba")->data = "BA"; | ||||||||||||
| 439 | $n->put("bb")->data = "BB"; | ||||||||||||
| 440 | $n->put("aaa")->data = "AAA"; | ||||||||||||
| 441 | is_deeply $n->count, 5; | ||||||||||||
| 442 | |||||||||||||
| 443 | is_deeply $n->find("aa") ->data, "AA"; | ||||||||||||
| 444 | is_deeply $n->find("ab") ->data, "AB"; | ||||||||||||
| 445 | is_deeply $n->find("ba") ->data, "BA"; | ||||||||||||
| 446 | is_deeply $n->find("bb") ->data, "BB"; | ||||||||||||
| 447 | is_deeply $n->find("aaa")->data, "AAA"; | ||||||||||||
| 448 | |||||||||||||
| 449 | is_deeply [map {[$_->key, $_->data]} $n->traverse], | ||||||||||||
| 450 | [["aa", "AA"], | ||||||||||||
| 451 | ["aaa", "AAA"], | ||||||||||||
| 452 | ["ab", "AB"], | ||||||||||||
| 453 | ["ba", "BA"], | ||||||||||||
| 454 | ["bb", "BB"]]; | ||||||||||||
| 455 | |||||||||||||
| 456 | ok $n->find("a"); | ||||||||||||
| 457 | ok !$n->find("a")->data; | ||||||||||||
| 458 | ok $n->find("b"); | ||||||||||||
| 459 | ok !$n->find("b")->data; | ||||||||||||
| 460 | ok !$n->find("c"); | ||||||||||||
| 461 | |||||||||||||
| 462 | |||||||||||||
| 463 | ok $n->find("aa")->delete; ok $n->find("aa"); is_deeply $n->count, 4; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 464 | |||||||||||||
| 465 | |||||||||||||
| 466 | ok $n->find("ab")->delete; ok !$n->find("ab"); is_deeply $n->count, 3; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 467 | |||||||||||||
| 468 | |||||||||||||
| 469 | ok $n->find("ba")->delete; ok !$n->find("ba"); is_deeply $n->count, 2; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 470 | |||||||||||||
| 471 | |||||||||||||
| 472 | ok $n->find("bb")->delete; ok !$n->find("bb"); is_deeply $n->count, 1; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 473 | |||||||||||||
| 474 | |||||||||||||
| 475 | ok $n->find("a"); | ||||||||||||
| 476 | ok !$n->find("b"); | ||||||||||||
| 477 | |||||||||||||
| 478 | |||||||||||||
| 479 | ok $n->find("aaa")->delete; ok !$n->find("aaa"); is_deeply $n->count, 0; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 480 | |||||||||||||
| 481 | ok !$n->find("a"); | ||||||||||||
| 482 | } | ||||||||||||
| 483 | |||||||||||||
| 484 | |||||||||||||
| 485 | =head2 count($node) | ||||||||||||
| 486 | |||||||||||||
| 487 | Count the nodes addressed in the specified tree | ||||||||||||
| 488 | |||||||||||||
| 489 | Parameter Description | ||||||||||||
| 490 | 1 $node Node to be counted from | ||||||||||||
| 491 | |||||||||||||
| 492 | B<Example:> | ||||||||||||
| 493 | |||||||||||||
| 494 | |||||||||||||
| 495 | if (1) | ||||||||||||
| 496 | {my $n = node; | ||||||||||||
| 497 | $n->put("aa")->data = "AA"; | ||||||||||||
| 498 | $n->put("ab")->data = "AB"; | ||||||||||||
| 499 | $n->put("ba")->data = "BA"; | ||||||||||||
| 500 | $n->put("bb")->data = "BB"; | ||||||||||||
| 501 | $n->put("aaa")->data = "AAA"; | ||||||||||||
| 502 | |||||||||||||
| 503 | is_deeply $n->count, 5; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 504 | |||||||||||||
| 505 | |||||||||||||
| 506 | is_deeply $n->find("aa") ->data, "AA"; | ||||||||||||
| 507 | is_deeply $n->find("ab") ->data, "AB"; | ||||||||||||
| 508 | is_deeply $n->find("ba") ->data, "BA"; | ||||||||||||
| 509 | is_deeply $n->find("bb") ->data, "BB"; | ||||||||||||
| 510 | is_deeply $n->find("aaa")->data, "AAA"; | ||||||||||||
| 511 | |||||||||||||
| 512 | is_deeply [map {[$_->key, $_->data]} $n->traverse], | ||||||||||||
| 513 | [["aa", "AA"], | ||||||||||||
| 514 | ["aaa", "AAA"], | ||||||||||||
| 515 | ["ab", "AB"], | ||||||||||||
| 516 | ["ba", "BA"], | ||||||||||||
| 517 | ["bb", "BB"]]; | ||||||||||||
| 518 | |||||||||||||
| 519 | ok $n->find("a"); | ||||||||||||
| 520 | ok !$n->find("a")->data; | ||||||||||||
| 521 | ok $n->find("b"); | ||||||||||||
| 522 | ok !$n->find("b")->data; | ||||||||||||
| 523 | ok !$n->find("c"); | ||||||||||||
| 524 | |||||||||||||
| 525 | |||||||||||||
| 526 | ok $n->find("aa")->delete; ok $n->find("aa"); is_deeply $n->count, 4; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 527 | |||||||||||||
| 528 | |||||||||||||
| 529 | ok $n->find("ab")->delete; ok !$n->find("ab"); is_deeply $n->count, 3; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 530 | |||||||||||||
| 531 | |||||||||||||
| 532 | ok $n->find("ba")->delete; ok !$n->find("ba"); is_deeply $n->count, 2; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 533 | |||||||||||||
| 534 | |||||||||||||
| 535 | ok $n->find("bb")->delete; ok !$n->find("bb"); is_deeply $n->count, 1; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 536 | |||||||||||||
| 537 | |||||||||||||
| 538 | ok $n->find("a"); | ||||||||||||
| 539 | ok !$n->find("b"); | ||||||||||||
| 540 | |||||||||||||
| 541 | |||||||||||||
| 542 | ok $n->find("aaa")->delete; ok !$n->find("aaa"); is_deeply $n->count, 0; # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 543 | |||||||||||||
| 544 | ok !$n->find("a"); | ||||||||||||
| 545 | } | ||||||||||||
| 546 | |||||||||||||
| 547 | |||||||||||||
| 548 | =head2 traverse($node) | ||||||||||||
| 549 | |||||||||||||
| 550 | Traverse a tree returning an array of nodes | ||||||||||||
| 551 | |||||||||||||
| 552 | Parameter Description | ||||||||||||
| 553 | 1 $node Node to be counted from | ||||||||||||
| 554 | |||||||||||||
| 555 | B<Example:> | ||||||||||||
| 556 | |||||||||||||
| 557 | |||||||||||||
| 558 | if (1) | ||||||||||||
| 559 | {my $n = node; | ||||||||||||
| 560 | $n->put("aa")->data = "AA"; | ||||||||||||
| 561 | $n->put("ab")->data = "AB"; | ||||||||||||
| 562 | $n->put("ba")->data = "BA"; | ||||||||||||
| 563 | $n->put("bb")->data = "BB"; | ||||||||||||
| 564 | $n->put("aaa")->data = "AAA"; | ||||||||||||
| 565 | is_deeply $n->count, 5; | ||||||||||||
| 566 | |||||||||||||
| 567 | is_deeply $n->find("aa") ->data, "AA"; | ||||||||||||
| 568 | is_deeply $n->find("ab") ->data, "AB"; | ||||||||||||
| 569 | is_deeply $n->find("ba") ->data, "BA"; | ||||||||||||
| 570 | is_deeply $n->find("bb") ->data, "BB"; | ||||||||||||
| 571 | is_deeply $n->find("aaa")->data, "AAA"; | ||||||||||||
| 572 | |||||||||||||
| 573 | |||||||||||||
| 574 | is_deeply [map {[$_->key, $_->data]} $n->traverse], # 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 | ||||||||||||
| 575 | |||||||||||||
| 576 | [["aa", "AA"], | ||||||||||||
| 577 | ["aaa", "AAA"], | ||||||||||||
| 578 | ["ab", "AB"], | ||||||||||||
| 579 | ["ba", "BA"], | ||||||||||||
| 580 | ["bb", "BB"]]; | ||||||||||||
| 581 | |||||||||||||
| 582 | ok $n->find("a"); | ||||||||||||
| 583 | ok !$n->find("a")->data; | ||||||||||||
| 584 | ok $n->find("b"); | ||||||||||||
| 585 | ok !$n->find("b")->data; | ||||||||||||
| 586 | ok !$n->find("c"); | ||||||||||||
| 587 | |||||||||||||
| 588 | ok $n->find("aa")->delete; ok $n->find("aa"); is_deeply $n->count, 4; | ||||||||||||
| 589 | ok $n->find("ab")->delete; ok !$n->find("ab"); is_deeply $n->count, 3; | ||||||||||||
| 590 | ok $n->find("ba")->delete; ok !$n->find("ba"); is_deeply $n->count, 2; | ||||||||||||
| 591 | ok $n->find("bb")->delete; ok !$n->find("bb"); is_deeply $n->count, 1; | ||||||||||||
| 592 | |||||||||||||
| 593 | ok $n->find("a"); | ||||||||||||
| 594 | ok !$n->find("b"); | ||||||||||||
| 595 | |||||||||||||
| 596 | ok $n->find("aaa")->delete; ok !$n->find("aaa"); is_deeply $n->count, 0; | ||||||||||||
| 597 | ok !$n->find("a"); | ||||||||||||
| 598 | } | ||||||||||||
| 599 | |||||||||||||
| 600 | |||||||||||||
| 601 | |||||||||||||
| 602 | =head1 Index | ||||||||||||
| 603 | |||||||||||||
| 604 | |||||||||||||
| 605 | 1 L<count|/count> - Count the nodes addressed in the specified tree | ||||||||||||
| 606 | |||||||||||||
| 607 | 2 L<delete|/delete> - Remove a node from a tree | ||||||||||||
| 608 | |||||||||||||
| 609 | 3 L<find|/find> - Find a key in a tree - return its node if such a node exists else undef | ||||||||||||
| 610 | |||||||||||||
| 611 | 4 L<key|/key> - Return the key of a node | ||||||||||||
| 612 | |||||||||||||
| 613 | 5 L<node|/node> - Create a new node | ||||||||||||
| 614 | |||||||||||||
| 615 | 6 L<put|/put> - Add a key to the tree | ||||||||||||
| 616 | |||||||||||||
| 617 | 7 L<traverse|/traverse> - Traverse a tree returning an array of nodes | ||||||||||||
| 618 | |||||||||||||
| 619 | =head1 Installation | ||||||||||||
| 620 | |||||||||||||
| 621 | This module is written in 100% Pure Perl and, thus, it is easy to read, | ||||||||||||
| 622 | comprehend, use, modify and install via B<cpan>: | ||||||||||||
| 623 | |||||||||||||
| 624 | sudo cpan install Tree::Trek | ||||||||||||
| 625 | |||||||||||||
| 626 | =head1 Author | ||||||||||||
| 627 | |||||||||||||
| 628 | L<philiprbrenan@gmail.com|mailto:philiprbrenan@gmail.com> | ||||||||||||
| 629 | |||||||||||||
| 630 | L<http://www.appaapps.com|http://www.appaapps.com> | ||||||||||||
| 631 | |||||||||||||
| 632 | =head1 Copyright | ||||||||||||
| 633 | |||||||||||||
| 634 | Copyright (c) 2016-2021 Philip R Brenan. | ||||||||||||
| 635 | |||||||||||||
| 636 | This module is free software. It may be used, redistributed and/or modified | ||||||||||||
| 637 | under the same terms as Perl itself. | ||||||||||||
| 638 | |||||||||||||
| 639 | =cut | ||||||||||||
| 640 | |||||||||||||
| 641 | |||||||||||||
| 642 | |||||||||||||
| 643 | # Tests and documentation | ||||||||||||
| 644 | |||||||||||||
| 645 | sub test | ||||||||||||
| 646 | 1 | ▶ | {my $p = __PACKAGE__; | ||||||||||
|
Subroutine
test: called CC=5 SCAR=16.3
Pod
undocumented
| |||||||||||||
| 647 | 1 | binmode($_, ":utf8") for *STDOUT, *STDERR; | |||||||||||
| 648 | 1 | ▶ | return if eval "eof(${p}::DATA)"; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 649 | 1 | my $s = eval "join('', <${p}::DATA>)"; | |||||||||||
| 650 | 1 | ▶ | $@ and die $@; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 651 | 1 | ▶ | eval $s; | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 652 | 1 | ▶ | $@ and die $@; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 653 | 1 | 1 | |||||||||||
| 654 | } | ||||||||||||
| 655 | |||||||||||||
| 656 | 1 | ▶ | test unless caller; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 657 | |||||||||||||
| 658 | 1 | 1; | |||||||||||
| 659 | # podDocumentation | ||||||||||||
| 660 | __DATA__ | ||||||||||||