lib/FP/Trie.pm

filter: Statementstmt 44.6% 75 / 168 Branchbran 0.0% 0 / 48 Conditioncond 0.0% 0 / 21 MC/DCmcdc 0.0% 0 / 14 Subroutinesub 41.3% 19 / 46 Podpod 0.0% 0 / 1 totaltotal 31.5% 94 / 298 CC 32 SCAR 26.5
CC
32
Cov
32%
skip
56.0
xdelete
42.0
delete
30.0
CRAP 14.2
« lib/FP/Show.pm ↑ Summary lib/FP/Ops.pm »
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
BranchTrueFalseTotal
@_ == 2 or fp_croak_arity(2) 0 0 0
125 0 my ($t, $l) = @_;
126 0 my ($t2, $maybe_l2) = $t->skip($l);
127 0 ▶ defined $maybe_l2 ? () : ($t2)
Branch: 1 branch
BranchTrueFalseTotal
defined $maybe_l2 ? : 0 0 0
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
BranchTrueFalseTotal
@_ == 2 or fp_croak_arity(2) 0 0 0
134 0 my ($t, $l) = @_;
135 0 ▶ if (my ($t2) = $t->perhaps_skip($l)) {
Branch: 1 branch
BranchTrueFalseTotal
if (my($t2) = $t->perhaps_skip($l)) { } 0 0 0
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
BranchTrueFalseTotal
@_ == 2 or @_ == 4 or fp_croak_arity("2 or 4") 0 0 0
Condition0%0/3
@_ == 2 or @_ == 4
l!l&&r!l&&!r
000
MC/DC0%0/2
@_ == 2 or @_ == 4
@_ == 2 @_ == 4
Truth table0%0/3
A or B
A= @_ == 2B= @_ == 4
ABresult
1X1
011
000
150 0 my ($t, $l, $maybe_lastvaluelevel, $maybe_keyremainder_lvl) = @_;
151 0 ▶ my ($maybe_lvl, $maybe_r_lvl)
Branch: 1 branch
BranchTrueFalseTotal
defined builtin::blessed($t) && $t->isa('FP::Trie::ValueLevel') ? : 0 0 0
Condition0%0/3
defined builtin::blessed($t) and $t->isa("FP::Trie::ValueLevel")
!ll&&!rl&&r
000
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")
ABresult
0X0
100
111
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
BranchTrueFalseTotal
if ($l->is_null) { } 0 0 0
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
BranchTrueFalseTotal
if (my($t2) = hash_perhaps_ref($t->{'sublevels'}, $a)) { } 0 0 0
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
BranchTrueFalseTotal
@_ == 3 or fp_croak_arity(3) 0 0 0
177 0 my ($t, $l, $fn) = @_;
178 0 ▶ if ($l->is_null) {
Branch: 1 branch
BranchTrueFalseTotal
if ($l->is_null) { } 0 0 0
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
BranchTrueFalseTotal
if (my($t2) = ) { } 0 0 0
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
BranchTrueFalseTotal
@_ == 2 or fp_croak_arity(2) 0 0 0
201 0 my ($t, $l) = @_;
202 0 ▶ if ($l->is_null) {
Branch: 1 branch
BranchTrueFalseTotal
if ($l->is_null) { } 0 0 0
203 0 ▶ if ((defined blessed $t) && $t->isa("FP::Trie::ValueLevel")) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined builtin::blessed($t) and $t->isa('FP::Trie::ValueLevel')) { } 0 0 0
Condition0%0/3
defined builtin::blessed($t) and $t->isa("FP::Trie::ValueLevel")
!ll&&!rl&&r
000
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")
ABresult
0X0
100
111
204 0 ▶ if (keys %{ $$t{sublevels} }) {
Branch: 1 branch
BranchTrueFalseTotal
if (CORE::keys %{$$t{'sublevels'};}) { } 0 0 0
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
BranchTrueFalseTotal
if (my($t2) = ) { } 0 0 0
221 0 my $t3 = $t2->xdelete($l2);
222 0 ▶ $t3 eq $FP::Trie::empty_trie ? () : $t3
Branch: 1 branch
BranchTrueFalseTotal
$t3 eq $FP::Trie::empty_trie ? : 0 0 0
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
BranchTrueFalseTotal
@_ == 2 or fp_croak_arity(2) 0 0 0
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
BranchTrueFalseTotal
if (eval { do { $res = $t->xdelete($l); 1 } }) { } 0 0 0
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
BranchTrueFalseTotal
if (defined builtin::blessed($e) and $e->isa('FP::Trie::KeyNotFoundException')) { } 0 0 0
Condition0%0/3
defined builtin::blessed($e) and $e->isa("FP::Trie::KeyNotFoundException")
!ll&&!rl&&r
000
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")
ABresult
0X0
100
111
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
BranchTrueFalseTotal
@_ == 3 or fp_croak_arity(3) 0 0 0
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
BranchTrueFalseTotal
@_ == 1 or fp_croak_arity(1) 0 0 0
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()
l!l&&r!l&&!r
000
MC/DC0%0/2
$maybe_rprefix // &null()
$maybe_rprefix &null()
Truth table0%0/3
A // B
A= $maybe_rprefixB= &null()
ABresult
1X1
011
000
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()
l!l&&r!l&&!r
000
MC/DC0%0/2
$maybe_tail // &null()
$maybe_tail &null()
Truth table0%0/3
A // B
A= $maybe_tailB= &null()
ABresult
1X1
011
000
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
BranchTrueFalseTotal
@_ == 1 or fp_croak_arity(1) 0 0 0
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
BranchTrueFalseTotal
@_ == 1 or fp_croak_arity(1) 0 0 0
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()
l!l&&r!l&&!r
000
MC/DC0%0/2
$maybe_rprefix // &null()
$maybe_rprefix &null()
Truth table0%0/3
A // B
A= $maybe_rprefixB= &null()
ABresult
1X1
011
000
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
« lib/FP/Show.pm ↑ Summary lib/FP/Ops.pm »