| 1 | # | ||||||||||||||||||||||||||||
| 2 | # Copyright (c) 2015-2021 Christian Jaeger, copying@christianjaeger.ch | ||||||||||||||||||||||||||||
| 3 | # | ||||||||||||||||||||||||||||
| 4 | # This is free software, offered under either the same terms as perl 5 | ||||||||||||||||||||||||||||
| 5 | # or the terms of the Artistic License version 2 or the terms of the | ||||||||||||||||||||||||||||
| 6 | # MIT License (Expat version). See the file COPYING.md that came | ||||||||||||||||||||||||||||
| 7 | # bundled with this file. | ||||||||||||||||||||||||||||
| 8 | # | ||||||||||||||||||||||||||||
| 9 | |||||||||||||||||||||||||||||
| 10 | =head1 NAME | ||||||||||||||||||||||||||||
| 11 | |||||||||||||||||||||||||||||
| 12 | FP::Trie - purely functional prefix tree | ||||||||||||||||||||||||||||
| 13 | |||||||||||||||||||||||||||||
| 14 | =head1 SYNOPSIS | ||||||||||||||||||||||||||||
| 15 | |||||||||||||||||||||||||||||
| 16 | use FP::Trie; | ||||||||||||||||||||||||||||
| 17 | |||||||||||||||||||||||||||||
| 18 | my $t = empty_trie->set(string_to_list ("Hello"), "World"); | ||||||||||||||||||||||||||||
| 19 | $t->perhaps_ref(string_to_list("Hell")); # () | ||||||||||||||||||||||||||||
| 20 | if (my ($subt) = $t->perhaps_skip(string_to_list("Hell"))) { | ||||||||||||||||||||||||||||
| 21 | print $subt->sublevels_length; | ||||||||||||||||||||||||||||
| 22 | if (my ($v) = $subt->perhaps_ref(string_to_list("o"))) { | ||||||||||||||||||||||||||||
| 23 | print $v; | ||||||||||||||||||||||||||||
| 24 | } | ||||||||||||||||||||||||||||
| 25 | } | ||||||||||||||||||||||||||||
| 26 | # -> prints "1World" | ||||||||||||||||||||||||||||
| 27 | |||||||||||||||||||||||||||||
| 28 | $t->maybe_ref ($keylist) | ||||||||||||||||||||||||||||
| 29 | $t->ref ($keylist) | ||||||||||||||||||||||||||||
| 30 | $t->ref_or ($keylist, $alternativevalue) | ||||||||||||||||||||||||||||
| 31 | $t->exists ($keylist) # boolean | ||||||||||||||||||||||||||||
| 32 | |||||||||||||||||||||||||||||
| 33 | $t->xdelete(string_to_list("Hello")) | ||||||||||||||||||||||||||||
| 34 | ->delete(string_to_list("Hello")) # silently does not change anything; | ||||||||||||||||||||||||||||
| 35 | ->xdelete(string_to_list("Hello")) # throws "key not found" exception | ||||||||||||||||||||||||||||
| 36 | |||||||||||||||||||||||||||||
| 37 | $t->keys # stream of keys | ||||||||||||||||||||||||||||
| 38 | $t->values # stream of values | ||||||||||||||||||||||||||||
| 39 | $t->alist # stream of [ key, value ] | ||||||||||||||||||||||||||||
| 40 | |||||||||||||||||||||||||||||
| 41 | $t->update($keylist, $fn) # $fn receives () if no such value is in | ||||||||||||||||||||||||||||
| 42 | # the trie; if it returns (), the entry | ||||||||||||||||||||||||||||
| 43 | # will be deleted | ||||||||||||||||||||||||||||
| 44 | |||||||||||||||||||||||||||||
| 45 | |||||||||||||||||||||||||||||
| 46 | =head1 DESCRIPTION | ||||||||||||||||||||||||||||
| 47 | |||||||||||||||||||||||||||||
| 48 | The trie operations expect an efficiently dissectable sequence (linked | ||||||||||||||||||||||||||||
| 49 | list, stream) as the key. Each item denotes the next level in the | ||||||||||||||||||||||||||||
| 50 | nested trie levels. The items in the list can be anything with a | ||||||||||||||||||||||||||||
| 51 | sensible stringification. To use FP::Trie for string keys, turn the | ||||||||||||||||||||||||||||
| 52 | strings to character lists using `string_to_list`. | ||||||||||||||||||||||||||||
| 53 | |||||||||||||||||||||||||||||
| 54 | `perhaps_skip` returns the remainder of the trie with the given prefix | ||||||||||||||||||||||||||||
| 55 | skipped (again a trie, if available). | ||||||||||||||||||||||||||||
| 56 | |||||||||||||||||||||||||||||
| 57 | `skip` returns ($ending_level, $maybe_keyremainder, | ||||||||||||||||||||||||||||
| 58 | $maybe_lastvaluelevel, $maybe_keyremainder_lvl), where | ||||||||||||||||||||||||||||
| 59 | $maybe_keyremainder is the remainder of the key list after the last | ||||||||||||||||||||||||||||
| 60 | matching level, $ending_level is that level, and $maybe_lastvaluelevel | ||||||||||||||||||||||||||||
| 61 | is the last level holding a value and $maybe_keyremainder_lvl the | ||||||||||||||||||||||||||||
| 62 | remainder of the key at that point. | ||||||||||||||||||||||||||||
| 63 | |||||||||||||||||||||||||||||
| 64 | =head1 PERFORMANCE | ||||||||||||||||||||||||||||
| 65 | |||||||||||||||||||||||||||||
| 66 | Update performance is bad because we don't have an efficiently | ||||||||||||||||||||||||||||
| 67 | updatable pure (hash) table datastructure yet. | ||||||||||||||||||||||||||||
| 68 | |||||||||||||||||||||||||||||
| 69 | =head1 NAMES | ||||||||||||||||||||||||||||
| 70 | |||||||||||||||||||||||||||||
| 71 | Are the method names ok? What names are other common implementations | ||||||||||||||||||||||||||||
| 72 | using? (todo: check Hoogle etc.) | ||||||||||||||||||||||||||||
| 73 | |||||||||||||||||||||||||||||
| 74 | =head1 SEE ALSO | ||||||||||||||||||||||||||||
| 75 | |||||||||||||||||||||||||||||
| 76 | Implements: L<FP::Abstract::Show>, L<FP::Abstract::Pure> | ||||||||||||||||||||||||||||
| 77 | |||||||||||||||||||||||||||||
| 78 | =head1 NOTE | ||||||||||||||||||||||||||||
| 79 | |||||||||||||||||||||||||||||
| 80 | This is alpha software! Read the status section in the package README | ||||||||||||||||||||||||||||
| 81 | or on the L<website|http://functional-perl.org/>. | ||||||||||||||||||||||||||||
| 82 | |||||||||||||||||||||||||||||
| 83 | =cut | ||||||||||||||||||||||||||||
| 84 | |||||||||||||||||||||||||||||
| 85 | package FP::Trie; | ||||||||||||||||||||||||||||
| 86 | 1 | ▶ | use strict; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 87 | 1 | ▶ | use warnings; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 88 | 1 | ▶ | use warnings FATAL => 'uninitialized'; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 89 | 1 | ▶ | use Exporter "import"; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 90 | |||||||||||||||||||||||||||||
| 91 | 1 | our @EXPORT = qw(empty_trie); | |||||||||||||||||||||||||||
| 92 | 1 | our @EXPORT_OK = qw($empty_trie); # ok? | |||||||||||||||||||||||||||
| 93 | 1 | our %EXPORT_TAGS = (all => [@EXPORT, @EXPORT_OK]); | |||||||||||||||||||||||||||
| 94 | |||||||||||||||||||||||||||||
| 95 | 1 | ▶ | use FP::Carp; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 96 | |||||||||||||||||||||||||||||
| 97 | 1 | package FP::Trie::KeyNotFoundException { | |||||||||||||||||||||||||||
| 98 | 1 | ▶ | use FP::Struct [], 'FP::Struct::Show', 'FP::Abstract::Pure'; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 99 | 1 | ▶ | use overload '""' => 'string'; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 100 | 0 | ▶ | sub string {"key not found"} | ||||||||||||||||||||||||||
|
Subroutine
string: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 101 | 1 | _END_ | |||||||||||||||||||||||||||
| 102 | } | ||||||||||||||||||||||||||||
| 103 | |||||||||||||||||||||||||||||
| 104 | 1 | package FP::Trie::Trie { | |||||||||||||||||||||||||||
| 105 | 1 | ▶ | use FP::Struct [], 'FP::Struct::Show', 'FP::Abstract::Pure'; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 106 | 1 | _END_ | |||||||||||||||||||||||||||
| 107 | } | ||||||||||||||||||||||||||||
| 108 | |||||||||||||||||||||||||||||
| 109 | 1 | package FP::Trie::BareLevel { | |||||||||||||||||||||||||||
| 110 | 1 | ▶ | use FP::Hash ':all'; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 111 | 1 | ▶ | use FP::Optional qw(perhaps_to_maybe perhaps_to_x | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 112 | 1 | perhaps_to_or perhaps_to_exists); | |||||||||||||||||||||||||||
| 113 | 1 | ▶ | use FP::Lazy; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 114 | 1 | ▶ | use FP::List; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 115 | 1 | ▶ | use FP::Stream; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 116 | 1 | ▶ | use Scalar::Util qw(blessed); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 117 | 1 | ▶ | use FP::Carp; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 118 | |||||||||||||||||||||||||||||
| 119 | 1 | ▶ | use FP::Struct ["sublevels"], "FP::Trie::Trie"; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 120 | |||||||||||||||||||||||||||||
| 121 | 0 | ▶ | sub perhaps_value { () } | ||||||||||||||||||||||||||
|
Subroutine
perhaps_value: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 122 | |||||||||||||||||||||||||||||
| 123 | 0 | ▶ | sub perhaps_skip { | ||||||||||||||||||||||||||
|
Subroutine
perhaps_skip: not called CC=3 SCAR=24.8
| |||||||||||||||||||||||||||||
| 124 | 0 | ▶ | @_ == 2 or fp_croak_arity 2; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 125 | 0 | my ($t, $l) = @_; | |||||||||||||||||||||||||||
| 126 | 0 | my ($t2, $maybe_l2) = $t->skip($l); | |||||||||||||||||||||||||||
| 127 | 0 | ▶ | defined $maybe_l2 ? () : ($t2) | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 128 | } | ||||||||||||||||||||||||||||
| 129 | |||||||||||||||||||||||||||||
| 130 | 1 | our $key_not_found_exception = FP::Trie::KeyNotFoundException->new; | |||||||||||||||||||||||||||
| 131 | |||||||||||||||||||||||||||||
| 132 | 0 | ▶ | sub perhaps_ref { | ||||||||||||||||||||||||||
|
Subroutine
perhaps_ref: not called CC=3 SCAR=24.8
| |||||||||||||||||||||||||||||
| 133 | 0 | ▶ | @_ == 2 or fp_croak_arity 2; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 134 | 0 | my ($t, $l) = @_; | |||||||||||||||||||||||||||
| 135 | 0 | ▶ | if (my ($t2) = $t->perhaps_skip($l)) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 136 | 0 | $t2->perhaps_value | |||||||||||||||||||||||||||
| 137 | } else { | ||||||||||||||||||||||||||||
| 138 | () | ||||||||||||||||||||||||||||
| 139 | 0 | } | |||||||||||||||||||||||||||
| 140 | } | ||||||||||||||||||||||||||||
| 141 | 1 | *maybe_ref = perhaps_to_maybe \&perhaps_ref; | |||||||||||||||||||||||||||
| 142 | 1 | *ref_or = perhaps_to_or \&perhaps_ref; | |||||||||||||||||||||||||||
| 143 | 1 | *ref = perhaps_to_x \&perhaps_ref, $key_not_found_exception; | |||||||||||||||||||||||||||
| 144 | 1 | *exists = perhaps_to_exists \&perhaps_ref; | |||||||||||||||||||||||||||
| 145 | |||||||||||||||||||||||||||||
| 146 | # returns ($ending_level, $maybe_keyremainder, | ||||||||||||||||||||||||||||
| 147 | # $maybe_lastvaluelevel, $maybe_keyremainder_lvl) | ||||||||||||||||||||||||||||
| 148 | 0 | ▶ | sub skip { | ||||||||||||||||||||||||||
|
Subroutine
skip: not called CC=7 SCAR=40.3
| |||||||||||||||||||||||||||||
| 149 | 0 | ▶ | @_ == 2 or @_ == 4 or fp_croak_arity "2 or 4"; | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition0%0/3
@_ == 2 or @_ == 4
MC/DC0%0/2
@_ == 2 or @_ == 4
@_ == 2
@_ == 4
Truth table0%0/3
A or B
A= @_ == 2B= @_ == 4
| |||||||||||||||||||||||||||||
| 150 | 0 | my ($t, $l, $maybe_lastvaluelevel, $maybe_keyremainder_lvl) = @_; | |||||||||||||||||||||||||||
| 151 | 0 | ▶ | my ($maybe_lvl, $maybe_r_lvl) | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition0%0/3
defined builtin::blessed($t) and $t->isa("FP::Trie::ValueLevel")
MC/DC0%0/2
defined builtin::blessed($t) and $t->isa("FP::Trie::ValueLevel")
defined builtin::blessed($t)
$t->isa("FP::Trie::ValueLevel")
Truth table0%0/3
A and B
A= defined builtin::blessed($t)B= $t->isa("FP::Trie::ValueLevel")
| |||||||||||||||||||||||||||||
| 152 | = (defined blessed $t) | ||||||||||||||||||||||||||||
| 153 | && $t->isa("FP::Trie::ValueLevel") | ||||||||||||||||||||||||||||
| 154 | ? ($t, $l) | ||||||||||||||||||||||||||||
| 155 | : ($maybe_lastvaluelevel, $maybe_keyremainder_lvl); | ||||||||||||||||||||||||||||
| 156 | 0 | ▶ | if ($l->is_null) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 157 | |||||||||||||||||||||||||||||
| 158 | # found the node, which is perhaps holding a value | ||||||||||||||||||||||||||||
| 159 | 0 | ($t, undef, $maybe_lvl, $maybe_r_lvl) | |||||||||||||||||||||||||||
| 160 | } else { | ||||||||||||||||||||||||||||
| 161 | 0 | my ($a, $l2) = $l->first_and_rest; | |||||||||||||||||||||||||||
| 162 | 0 | ▶ | if (my ($t2) = hash_perhaps_ref($$t{sublevels}, $a)) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 163 | |||||||||||||||||||||||||||||
| 164 | # XX TCO | ||||||||||||||||||||||||||||
| 165 | 0 | $t2->skip($l2, $maybe_lvl, $maybe_r_lvl) | |||||||||||||||||||||||||||
| 166 | } else { | ||||||||||||||||||||||||||||
| 167 | |||||||||||||||||||||||||||||
| 168 | # no value for the full key; $t is the last seen | ||||||||||||||||||||||||||||
| 169 | # level, $l the remainder of the key | ||||||||||||||||||||||||||||
| 170 | 0 | ($t, $l, $maybe_lvl, $maybe_r_lvl) | |||||||||||||||||||||||||||
| 171 | } | ||||||||||||||||||||||||||||
| 172 | } | ||||||||||||||||||||||||||||
| 173 | } | ||||||||||||||||||||||||||||
| 174 | |||||||||||||||||||||||||||||
| 175 | 0 | ▶ | sub update { | ||||||||||||||||||||||||||
|
Subroutine
update: not called CC=3 SCAR=24.8
| |||||||||||||||||||||||||||||
| 176 | 0 | ▶ | @_ == 3 or fp_croak_arity 3; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 177 | 0 | my ($t, $l, $fn) = @_; | |||||||||||||||||||||||||||
| 178 | 0 | ▶ | if ($l->is_null) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 179 | 0 | FP::Trie::ValueLevel->new($$t{sublevels}, &$fn($t->perhaps_value)) | |||||||||||||||||||||||||||
| 180 | } else { | ||||||||||||||||||||||||||||
| 181 | 0 | my ($a, $l2) = $l->first_and_rest; | |||||||||||||||||||||||||||
| 182 | $t->sublevels_update( | ||||||||||||||||||||||||||||
| 183 | 0 | ▶ | sub { | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 184 | 0 | ▶ | hash_update $_[0], $a, sub { | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=2 SCAR=17.9
| |||||||||||||||||||||||||||||
| 185 | 0 | do { | |||||||||||||||||||||||||||
| 186 | 0 | ▶ | if (my ($t2) = @_) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 187 | 0 | $t2 | |||||||||||||||||||||||||||
| 188 | } else { | ||||||||||||||||||||||||||||
| 189 | 0 | $FP::Trie::empty_trie | |||||||||||||||||||||||||||
| 190 | } | ||||||||||||||||||||||||||||
| 191 | } | ||||||||||||||||||||||||||||
| 192 | ->update($l2, $fn) | ||||||||||||||||||||||||||||
| 193 | } | ||||||||||||||||||||||||||||
| 194 | 0 | } | |||||||||||||||||||||||||||
| 195 | ) | ||||||||||||||||||||||||||||
| 196 | 0 | } | |||||||||||||||||||||||||||
| 197 | } | ||||||||||||||||||||||||||||
| 198 | |||||||||||||||||||||||||||||
| 199 | 0 | ▶ | sub xdelete { | ||||||||||||||||||||||||||
|
Subroutine
xdelete: not called CC=6 SCAR=37.4
| |||||||||||||||||||||||||||||
| 200 | 0 | ▶ | @_ == 2 or fp_croak_arity 2; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 201 | 0 | my ($t, $l) = @_; | |||||||||||||||||||||||||||
| 202 | 0 | ▶ | if ($l->is_null) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 203 | 0 | ▶ | if ((defined blessed $t) && $t->isa("FP::Trie::ValueLevel")) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition0%0/3
defined builtin::blessed($t) and $t->isa("FP::Trie::ValueLevel")
MC/DC0%0/2
defined builtin::blessed($t) and $t->isa("FP::Trie::ValueLevel")
defined builtin::blessed($t)
$t->isa("FP::Trie::ValueLevel")
Truth table0%0/3
A and B
A= defined builtin::blessed($t)B= $t->isa("FP::Trie::ValueLevel")
| |||||||||||||||||||||||||||||
| 204 | 0 | ▶ | if (keys %{ $$t{sublevels} }) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 205 | FP::Trie::BareLevel->new($$t{sublevels}) | ||||||||||||||||||||||||||||
| 206 | 0 | } else { | |||||||||||||||||||||||||||
| 207 | |||||||||||||||||||||||||||||
| 208 | # equivalent but detectable to be empty from outer | ||||||||||||||||||||||||||||
| 209 | # layers | ||||||||||||||||||||||||||||
| 210 | 0 | $FP::Trie::empty_trie | |||||||||||||||||||||||||||
| 211 | } | ||||||||||||||||||||||||||||
| 212 | } else { | ||||||||||||||||||||||||||||
| 213 | 0 | die $key_not_found_exception | |||||||||||||||||||||||||||
| 214 | } | ||||||||||||||||||||||||||||
| 215 | } else { | ||||||||||||||||||||||||||||
| 216 | 0 | my ($a, $l2) = $l->first_and_rest; | |||||||||||||||||||||||||||
| 217 | $t->sublevels_update( | ||||||||||||||||||||||||||||
| 218 | 0 | ▶ | sub { | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 219 | 0 | ▶ | hash_update $_[0], $a, sub { | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=3 SCAR=24.8
| |||||||||||||||||||||||||||||
| 220 | 0 | ▶ | if (my ($t2) = @_) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 221 | 0 | my $t3 = $t2->xdelete($l2); | |||||||||||||||||||||||||||
| 222 | 0 | ▶ | $t3 eq $FP::Trie::empty_trie ? () : $t3 | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 223 | } else { | ||||||||||||||||||||||||||||
| 224 | |||||||||||||||||||||||||||||
| 225 | #() | ||||||||||||||||||||||||||||
| 226 | # When does this happen? When the key goes | ||||||||||||||||||||||||||||
| 227 | # past the existing tree. | ||||||||||||||||||||||||||||
| 228 | 0 | die $key_not_found_exception | |||||||||||||||||||||||||||
| 229 | } | ||||||||||||||||||||||||||||
| 230 | } | ||||||||||||||||||||||||||||
| 231 | 0 | } | |||||||||||||||||||||||||||
| 232 | ) | ||||||||||||||||||||||||||||
| 233 | 0 | } | |||||||||||||||||||||||||||
| 234 | } | ||||||||||||||||||||||||||||
| 235 | |||||||||||||||||||||||||||||
| 236 | 0 | ▶ | sub delete { | ||||||||||||||||||||||||||
|
Subroutine
delete: not called CC=5 SCAR=34.0
| |||||||||||||||||||||||||||||
| 237 | 0 | ▶ | @_ == 2 or fp_croak_arity 2; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 238 | 0 | my ($t, $l) = @_; | |||||||||||||||||||||||||||
| 239 | |||||||||||||||||||||||||||||
| 240 | # This is really calling for call/cc (parametrize the end case | ||||||||||||||||||||||||||||
| 241 | # in xdelete, with either a continuation call or the call to | ||||||||||||||||||||||||||||
| 242 | # an exception handler). But we have what we have (for now). | ||||||||||||||||||||||||||||
| 243 | 0 | my $res; | |||||||||||||||||||||||||||
| 244 | 0 | ▶ | if ( | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 245 | eval { | ||||||||||||||||||||||||||||
| 246 | 0 | $res = $t->xdelete($l); | |||||||||||||||||||||||||||
| 247 | 0 | 1 | |||||||||||||||||||||||||||
| 248 | } | ||||||||||||||||||||||||||||
| 249 | ) | ||||||||||||||||||||||||||||
| 250 | { | ||||||||||||||||||||||||||||
| 251 | 0 | $res | |||||||||||||||||||||||||||
| 252 | } else { | ||||||||||||||||||||||||||||
| 253 | 0 | my $e = $@; | |||||||||||||||||||||||||||
| 254 | 0 | ▶ | if ((defined blessed $e) | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition0%0/3
defined builtin::blessed($e) and $e->isa("FP::Trie::KeyNotFoundException")
MC/DC0%0/2
defined builtin::blessed($e) and $e->isa("FP::Trie::KeyNotFoundException")
defined builtin::blessed($e)
$e->isa("FP::Trie::KeyNotFoundException")
Truth table0%0/3
A and B
A= defined builtin::blessed($e)B= $e->isa("FP::Trie::KeyNotFoundException")
| |||||||||||||||||||||||||||||
| 255 | and $e->isa("FP::Trie::KeyNotFoundException")) | ||||||||||||||||||||||||||||
| 256 | { | ||||||||||||||||||||||||||||
| 257 | 0 | $t | |||||||||||||||||||||||||||
| 258 | } else { | ||||||||||||||||||||||||||||
| 259 | 0 | die $e | |||||||||||||||||||||||||||
| 260 | } | ||||||||||||||||||||||||||||
| 261 | } | ||||||||||||||||||||||||||||
| 262 | } | ||||||||||||||||||||||||||||
| 263 | |||||||||||||||||||||||||||||
| 264 | 0 | ▶ | sub set { | ||||||||||||||||||||||||||
|
Subroutine
set: not called CC=2 SCAR=17.9
| |||||||||||||||||||||||||||||
| 265 | 0 | ▶ | @_ == 3 or fp_croak_arity 3; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 266 | 0 | my ($t, $l, $v) = @_; | |||||||||||||||||||||||||||
| 267 | 0 | ▶ | $t->update($l, sub {$v}) | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 268 | 0 | } | |||||||||||||||||||||||||||
| 269 | |||||||||||||||||||||||||||||
| 270 | 0 | ▶ | sub sublevels_length { | ||||||||||||||||||||||||||
|
Subroutine
sublevels_length: not called CC=2 SCAR=17.9
| |||||||||||||||||||||||||||||
| 271 | 0 | ▶ | @_ == 1 or fp_croak_arity 1; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 272 | 0 | my ($t) = @_; | |||||||||||||||||||||||||||
| 273 | 0 | hash_length $t->sublevels | |||||||||||||||||||||||||||
| 274 | } | ||||||||||||||||||||||||||||
| 275 | |||||||||||||||||||||||||||||
| 276 | # key_and_value_s, association list | ||||||||||||||||||||||||||||
| 277 | 0 | ▶ | sub alist { | ||||||||||||||||||||||||||
|
Subroutine
alist: not called CC=3 SCAR=24.8
| |||||||||||||||||||||||||||||
| 278 | 0 | my ($t, $maybe_rprefix, $maybe_tail) = @_; | |||||||||||||||||||||||||||
| 279 | 0 | ▶ | my $rprefix = $maybe_rprefix // null; | ||||||||||||||||||||||||||
|
Condition0%0/3
$maybe_rprefix // &null()
MC/DC0%0/2
$maybe_rprefix // &null()
$maybe_rprefix
&null()
Truth table0%0/3
A // B
A= $maybe_rprefixB= &null()
| |||||||||||||||||||||||||||||
| 280 | 0 | if (0) { | |||||||||||||||||||||||||||
| 281 | |||||||||||||||||||||||||||||
| 282 | # XXX Why the hell does this not work, while the non-OO | ||||||||||||||||||||||||||||
| 283 | # variant does? | ||||||||||||||||||||||||||||
| 284 | stream(keys %{ $$t{sublevels} })->fold_right( | ||||||||||||||||||||||||||||
| 285 | 0 | ▶ | sub { | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 286 | 0 | my ($k, $rest) = @_; | |||||||||||||||||||||||||||
| 287 | 0 | $$t{sublevels}{$k}->alist(cons($k, $rprefix), $rest) | |||||||||||||||||||||||||||
| 288 | }, | ||||||||||||||||||||||||||||
| 289 | $maybe_tail // null | ||||||||||||||||||||||||||||
| 290 | ); | ||||||||||||||||||||||||||||
| 291 | } else { | ||||||||||||||||||||||||||||
| 292 | stream_fold_right( | ||||||||||||||||||||||||||||
| 293 | 0 | ▶ | sub { | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 294 | 0 | my ($k, $rest) = @_; | |||||||||||||||||||||||||||
| 295 | 0 | $$t{sublevels}{$k}->alist(cons($k, $rprefix), $rest) | |||||||||||||||||||||||||||
| 296 | }, | ||||||||||||||||||||||||||||
| 297 | $maybe_tail // null, | ||||||||||||||||||||||||||||
| 298 | 0 | ▶ | stream keys %{ $$t{sublevels} } | ||||||||||||||||||||||||||
|
Condition0%0/3
$maybe_tail // &null()
MC/DC0%0/2
$maybe_tail // &null()
$maybe_tail
&null()
Truth table0%0/3
A // B
A= $maybe_tailB= &null()
| |||||||||||||||||||||||||||||
| 299 | ); | ||||||||||||||||||||||||||||
| 300 | } | ||||||||||||||||||||||||||||
| 301 | } | ||||||||||||||||||||||||||||
| 302 | |||||||||||||||||||||||||||||
| 303 | 0 | ▶ | sub keys { | ||||||||||||||||||||||||||
|
Subroutine
keys: not called CC=2 SCAR=17.9
| |||||||||||||||||||||||||||||
| 304 | 0 | ▶ | @_ == 1 or fp_croak_arity 1; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 305 | 0 | my ($t) = @_; | |||||||||||||||||||||||||||
| 306 | 0 | ▶ | $t->alist->stream_map(sub { $_[0][0] }) | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 307 | 0 | } | |||||||||||||||||||||||||||
| 308 | |||||||||||||||||||||||||||||
| 309 | # XX usually I'm using `values` to return a Perl "list"! But what | ||||||||||||||||||||||||||||
| 310 | # else should this be named? `valuestream`? And the above | ||||||||||||||||||||||||||||
| 311 | # `keystream`? | ||||||||||||||||||||||||||||
| 312 | 0 | ▶ | sub values { | ||||||||||||||||||||||||||
|
Subroutine
values: not called CC=2 SCAR=17.9
| |||||||||||||||||||||||||||||
| 313 | 0 | ▶ | @_ == 1 or fp_croak_arity 1; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 314 | 0 | my ($t) = @_; | |||||||||||||||||||||||||||
| 315 | 0 | ▶ | $t->alist->stream_map(sub { $_[0][1] }) | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 316 | 0 | } | |||||||||||||||||||||||||||
| 317 | |||||||||||||||||||||||||||||
| 318 | # Turn trie to a nested list representation, for debugging or | ||||||||||||||||||||||||||||
| 319 | # interoperation; call `write_sexpr` on it to get a readable | ||||||||||||||||||||||||||||
| 320 | # printout. | ||||||||||||||||||||||||||||
| 321 | 0 | ▶ | sub sexpr { | ||||||||||||||||||||||||||
|
Subroutine
sexpr: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 322 | 0 | my ($t) = @_; | |||||||||||||||||||||||||||
| 323 | 0 | my $sublevels = $t->sublevels; | |||||||||||||||||||||||||||
| 324 | cons( | ||||||||||||||||||||||||||||
| 325 | list($t->perhaps_value), | ||||||||||||||||||||||||||||
| 326 | list( | ||||||||||||||||||||||||||||
| 327 | 0 | map { list($_, $$sublevels{$_}->sexpr) } | |||||||||||||||||||||||||||
| 328 | sort CORE::keys(%$sublevels) | ||||||||||||||||||||||||||||
| 329 | ) | ||||||||||||||||||||||||||||
| 330 | ) | ||||||||||||||||||||||||||||
| 331 | } | ||||||||||||||||||||||||||||
| 332 | |||||||||||||||||||||||||||||
| 333 | 1 | _END_ | |||||||||||||||||||||||||||
| 334 | } | ||||||||||||||||||||||||||||
| 335 | |||||||||||||||||||||||||||||
| 336 | 1 | package FP::Trie::ValueLevel { | |||||||||||||||||||||||||||
| 337 | |||||||||||||||||||||||||||||
| 338 | 1 | ▶ | use FP::List; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 339 | 1 | ▶ | use FP::Lazy; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 340 | |||||||||||||||||||||||||||||
| 341 | 1 | ▶ | use FP::Struct ["value"], "FP::Trie::BareLevel"; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 342 | |||||||||||||||||||||||||||||
| 343 | 0 | ▶ | sub perhaps_value { | ||||||||||||||||||||||||||
|
Subroutine
perhaps_value: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 344 | 0 | my ($t) = @_; | |||||||||||||||||||||||||||
| 345 | $$t{value} | ||||||||||||||||||||||||||||
| 346 | 0 | } | |||||||||||||||||||||||||||
| 347 | |||||||||||||||||||||||||||||
| 348 | 0 | ▶ | sub alist { | ||||||||||||||||||||||||||
|
Subroutine
alist: not called CC=2 SCAR=17.9
| |||||||||||||||||||||||||||||
| 349 | 0 | my ($t, $maybe_rprefix, $maybe_tail) = @_; | |||||||||||||||||||||||||||
| 350 | 0 | ▶ | my $rprefix = $maybe_rprefix // null; | ||||||||||||||||||||||||||
|
Condition0%0/3
$maybe_rprefix // &null()
MC/DC0%0/2
$maybe_rprefix // &null()
$maybe_rprefix
&null()
Truth table0%0/3
A // B
A= $maybe_rprefixB= &null()
| |||||||||||||||||||||||||||||
| 351 | 0 | ▶ | lazy { | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 352 | cons( | ||||||||||||||||||||||||||||
| 353 | 0 | [$rprefix->reverse, $$t{value}], | |||||||||||||||||||||||||||
| 354 | $t->SUPER::alist($rprefix, $maybe_tail) | ||||||||||||||||||||||||||||
| 355 | ) | ||||||||||||||||||||||||||||
| 356 | } | ||||||||||||||||||||||||||||
| 357 | 0 | } | |||||||||||||||||||||||||||
| 358 | |||||||||||||||||||||||||||||
| 359 | 1 | _END_ | |||||||||||||||||||||||||||
| 360 | } | ||||||||||||||||||||||||||||
| 361 | |||||||||||||||||||||||||||||
| 362 | 1 | our $empty_trie = FP::Trie::BareLevel->new({}); | |||||||||||||||||||||||||||
| 363 | |||||||||||||||||||||||||||||
| 364 | 0 | ▶ | sub empty_trie { | ||||||||||||||||||||||||||
|
Subroutine
empty_trie: not called CC=1 SCAR=6.9
Pod
undocumented
| |||||||||||||||||||||||||||||
| 365 | 0 | $empty_trie | |||||||||||||||||||||||||||
| 366 | } | ||||||||||||||||||||||||||||
| 367 | |||||||||||||||||||||||||||||
| 368 | 1 | 1 | |||||||||||||||||||||||||||