File Coverage

lib/Math/String/Charset/Nested.pm
Criterion Covered Total %
statement 218 295 73.9
branch 85 142 59.8
condition 17 37 45.9
subroutine 15 20 75.0
pod 6 9 66.6
total 341 503 67.7


line stmt bran cond sub pod time code
1             #############################################################################
2             # Math/String/Charset/Nested -- charsets for Math/String
3             #
4             # Copyright (C) 1999-2003 by Tels. All rights reserved.
5             #############################################################################
6              
7             # todo: tri-grams etc
8             # store counts for different end-chars at the max elemt of _count?
9             # if we later need to calculate further, we could pick up there and need
10             # not to re-calculate the lower numbers
11              
12             package Math::String::Charset::Nested;
13 6     6   24 use base Math::String::Charset;
  6         10  
  6         470  
14              
15 6     6   34 use vars qw($VERSION);
  6         7  
  6         249  
16             $VERSION = '1.29'; # Current version of this package
17             require 5.005; # requires this Perl version or later
18              
19 6     6   20 use strict;
  6         6  
  6         119  
20 6     6   18 use Math::BigInt;
  6         39  
  6         41  
21              
22 6     6   1354 use vars qw/$die_on_error/;
  6         7  
  6         14052  
23             $die_on_error = 1; # set to 0 to not die
24              
25             # following hash values are used:
26             # _clen : length of one character (all chars must have same len unless sep)
27             # _start : contains array of all valid start characters
28             # _ones : list of one-character strings (cross of _end and _start)
29             # _end : contains hash (for easier lookup) of all valid end characters
30             # _order : 1,2,3.. etc, 1 => simple, 2 => bigram etc
31             # _type : 0 => simple or bi-gram, 1 => grouping
32             # _error : error message or ""
33             # _count : array of count of different strings with length x
34             # _sum : array of starting number for strings with length x
35             # _sum[x] = _sum[x-1]+_count[x-1]
36             # _cnt : number of elements in _count and _sum (as well as in _scnt & _ssum)
37             # _cnum : number of characters in _ones as BigInt (for speed)
38             # _minlen: minimum string length (anything shorter is invalid), default 0
39             # _maxlen: maximum string length (anything longer is invalid), default undef
40             # _scale : optional input/output scale
41              
42             # simple ones:
43             # _sep : separator string (undef for none)
44             # _map : mapping character to number
45              
46             # higher orders:
47             # _bi : hash with refs to array of bi-grams
48             # _bmap : hash with refs to hash of bi-grams
49             # _scnt : array of hashes, count of strings starting with this character
50             # _sm : hash w/ mapping of start characters for faster lookup
51              
52             #############################################################################
53             # private, initialize self
54              
55             sub _strict_check
56             {
57             # a per class check, to be overwritten by subclasses
58 9     9   10 my $self = shift;
59 9         10 my $value = shift;
60              
61 9         11 my $class = ref($self);
62             return $self->{_error} = "Wrong type '$self->{_type}' for $class"
63 9 50       45 if $self->{_type} != 0;
64             return $self->{_error} = "Wrong order'$self->{_order}' for $class"
65 9 50       22 if $self->{_order} != 2;
66 9         29 foreach my $key (keys %$value)
67             {
68 27 50       100 return $self->{_error} = "Illegal parameter '$key' for $class"
69             if $key !~ /^(start|minlen|maxlen|sep|bi|end|charlen|scale)$/;
70             }
71             }
72              
73             sub _initialize
74             {
75             # set yourself to the value represented by the given string
76 9     9   10 my $self = shift;
77 9         14 my $value = shift;
78              
79 9         11 my $end = {}; # we make array later on
80             # add the user-specified end set
81 9   50     22 my $bi = $value->{bi} || {};
82 9 50       28 return $self->{_error} = "Field 'bi' must be hash ref"
83             if ref($bi) ne 'HASH';
84 9         15 $self->{_order} = 2;
85             # if no end set is defined, add all followers as default
86 9 100       17 if (exists $value->{end})
87             {
88 6         12 $end = { map { $_ => 1 } @{$value->{end}} };
  18         31  
  6         20  
89             }
90             else
91             {
92 3         9 foreach my $c (keys %$bi)
93             {
94 12         9 foreach my $f (@{$bi->{$c}})
  12         16  
95             {
96 24         25 $end->{$f} = 1;
97             }
98             }
99             }
100 9 50       22 if (exists $value->{start})
101             {
102 9         9 $self->{_start} = [ @{$value->{start}} ];
  9         25  
103             }
104             else
105             {
106             # else all chars w/ followers can start a string (longer than 2)
107 0         0 my $s = { };
108 0         0 foreach my $c (keys %$bi)
109             {
110 0 0       0 $s->{$c} = 1 if @{$bi->{$c}} > 0;
  0         0  
111             }
112 0         0 $self->{_start} = [ sort keys %$s ];
113             }
114              
115             # make copy
116 9         22 foreach my $c (keys %$bi)
117             {
118 46         31 $self->{_bi}->{$c} = [ @{$bi->{$c}} ]; # make copy
  46         96  
119             }
120 9 50       24 if (!defined $self->{_sep})
121             {
122 9         30 foreach my $c (keys %$bi)
123             {
124 9         17 $self->{_clen} = CORE::length($c);
125 9         13 last;
126             }
127             }
128             # add empty array for chars with no followers
129 9         14 $bi = $self->{_bi};
130 9         28 my @keys = keys %$bi; # make copy since keys may be modified (necc?)
131 9         26 foreach my $c (@keys)
132             {
133 46 100       34 $end->{$c} = 1 if @{$bi->{$c}} == 0; # no follower
  46         100  
134              
135 46         39 foreach my $f (@{$bi->{$c}})
  46         52  
136             {
137 79 100       114 $self->{_bi}->{$f} = [] if !defined $self->{_bi}->{$f};
138 79 100       62 $end->{$f} = 1 if @{$bi->{$f}} == 0;
  79         128  
139 79 50       107 if (!defined $self->{_sep})
140             {
141             return $self->{_error} = "Illegal char '$f', length not $self->{_clen}"
142 79 50       138 if length($f) != $self->{_clen};
143             }
144             }
145             }
146              
147 9         19 $self->{_end} = $end;
148             # build _ones and _sm list (cross from start/end)
149 9         18 $self->{_ones} = [];
150 9         15 $self->{_sm} = {};
151 9         10 foreach (@{$self->{_start}})
  9         62  
152             {
153 30 100       52 push @{$self->{_ones}}, $_ if exists $end->{$_};
  22         33  
154 30         55 $self->{_sm}->{$_} = 1;
155             }
156             # print "ones => ",join(' ',@{$self->{_ones}}),"\n";
157             # remove anything from start with no followers, but keep original order
158 9         11 my @s;
159 9         9 foreach my $c (@{$self->{_start}})
  9         27  
160             {
161             push @s, $c
162 30 100 100     62 if ((!defined $self->{_bi}->{$c}) || (@{$self->{_bi}->{$c}} > 0));
  27         82  
163             }
164 9         14 $self->{_start} = \@s;
165              
166             # initialize array of counts for len of 0..1
167 9         18 $self->{_cnt} = 1; # cached amount of class-sizes
168 9         13 $self->{_count}->[0] = 1; # '' is one string
169 9         10 $self->{_count}->[1] = Math::BigInt->new (scalar @{$self->{_ones}}); # 1
  9         112  
170              
171             # initialize array of counts for len of 2
172 9         344 $end = $self->{_end};
173 9         19 my $count = Math::BigInt::bzero();
174 9         159 foreach my $c (keys %$bi)
175             {
176 50 100       3077 $count += scalar @{$bi->{$c}} if exists $end->{$c};
  38         90  
177             }
178 9         703 $self->{_count}->[2] = $count; # 2
179 9         14 $self->{_cnt}++; # adjust cache size
180              
181             # init _sum array
182 9         20 $self->{_sum}->[0] = 0;
183 9         13 $self->{_sum}->[1] = 1;
184 9         27 $self->{_sum}->[2] = $self->{_count}->[1] + 1;
185              
186             # from _ones, make mapping name => number
187 9         978 my $i = 1;
188 9         39 foreach (@{$self->{_ones}})
  9         19  
189             {
190 22         65 $self->{_map}->{$_} = $i++;
191             }
192             # create mapping for is_valid (contains number of follower)
193 9         12 foreach my $c (keys %{$self->{_bi}}) # for all chars
  9         24  
194             {
195 50         28 my $i = 0;
196 50         42 foreach my $cf (@{$self->{_bi}->{$c}}) # for all followers
  50         64  
197             {
198 79         115 $self->{_bmap}->{$c}->{$cf} = $i++; # make hash for easier lookup
199             }
200             }
201              
202             # init _scnt array ([0] not used in both)
203 9         19 $self->{_scnt}->[1] = {};
204             #foreach my $c (keys %{$self->{_map}}) # it's nearly the same
205             # {
206             # $self->{_ssum}->[1]->{$c} = $self->{_map}->{$c} - 1;
207             # }
208              
209             # class 1
210 9         10 foreach my $c (@{$self->{_start}})
  9         14  
211             {
212             $self->{_scnt}->[1]->{$c} = 1 # exactly one for each char
213 29 100       54 if exists $self->{_end}->{$c}; # but not for invalid's
214             }
215             # class 2
216 9         20 my $last = Math::BigInt::bzero();
217 9         124 foreach my $c (keys %{$self->{_bi}}) # for each possible character
  9         20  
218             {
219 50         1859 my $cnt = 0;
220 50         39 foreach my $cf (@{$bi->{$c}}) # for each follower
  50         57  
221             {
222 79 100       194 $cnt ++ if exists $self->{_end}->{$cf}; # that can end the string
223             }
224 50         61 $self->{_scnt}->[2]->{$c} = $cnt; # store
225             $last += $cnt # next one is summed up
226 50 100       113 if exists $self->{_sm}->{$c}; # if starting with valid char
227             }
228             # print $self->{_count}->[2]||0," should already be $last\n";
229 9         345 $self->{_count}->[2] = $last; # all in class #2
230 9         12 $self->{_cnt} = 2; # cache size for bi is one more
231 9         10 $self->{_cnum} = Math::BigInt->new( scalar @{$self->{_ones}} );
  9         25  
232 9 100       247 if ($self->{_cnum}->is_zero())
233             {
234 1 50       14 $self->{_minlen} = 2 if $self->{_minlen} == 1; # no one's
235             # check whether charset can have 2-character long strings
236 1 50       66 if ($self->{_count}->[2] == 0)
237             {
238 1 50       93 $self->{_minlen} = 3 if $self->{_minlen} == 2; # no two's
239             # check whether some path from start to end set exists, if not: empty
240 1         52 $self->_min_path_len();
241             }
242             }
243 9         134 return $self;
244             }
245              
246             sub _min_path_len
247             {
248             # for n-grams calculate the minimum path len
249             # Starting with each character in the start set, traverse the n-gram tree
250             # until it arrives at one of the end characters. The count between is the
251             # length of the shortes valid string.
252             # This might be greater than the length the user specified, because it is
253             # possible to have no shorter strings due to restrictions.
254 1     1   2 my $self = shift;
255              
256             # these are already know, and if non-zero, we already have minlen
257 1 50 33     3 return if $self->class(1) != 0 || $self->class(2) != 0;
258              
259 1   50     84 my $minlen = $self->{_minlen} || 3; # either the defined min len, or 3
260             }
261              
262             sub dump
263             {
264 0     0 0 0 my $self = shift;
265              
266 0         0 print "type: BIGRAM:\n";
267 0         0 my $bi = $self->{_bi};
268 0         0 foreach my $c (keys %$bi)
269             {
270 0         0 print " $c => [";
271 0         0 foreach my $f (@{$bi->{$c}})
  0         0  
272             {
273 0         0 print "'$f', ";
274             }
275 0         0 print "]\n";
276             }
277 0         0 print "start: ", join(' ',@{$self->{_start}}),"\n";
  0         0  
278 0         0 print "end : ", join(' ',keys %{$self->{_end}}),"\n";
  0         0  
279 0         0 print "ones : ", join(' ',@{$self->{_ones}}),"\n";
  0         0  
280             }
281              
282             sub _calc
283             {
284             # given count of len 1..x, calculate count for y (y > x) and all between
285             # x and y
286             # currently re-calcs from 2 on, we could save the state and only calculate
287             # the missing counts.
288              
289 8     8   172 my $self = shift;
290 8 50 50     15 my $max = shift || 1; $max = 1 if $max < 1;
  8         13  
291 8 100       32 return if $max <= $self->{_cnt};
292              
293             # my ($counts,$org_counts);
294             # map to hash
295             # my $end = $self->{_end};
296             # %$counts = map { $_, $end->{$_} } keys %$end; # make copy
297              
298 7         9 my ($c,$cf,$cnt,$last,$count);
299 7         10 my $i = $self->{_cnt}+1; # start with next undefined level
300 7         20 while ($i <= $max)
301             {
302             # take current level, calculate all possible ending characters
303             # and count them (e.g. 2 times 'b', 2 times 'c' and 3 times 'a')
304             # each of the ending chars has a number of possible bi-grams. For the next
305             # length, we must add the count of the ending char to each of the possible
306             # bi-grams. After this, we get the new count for all new ending chars.
307             # %$org_counts = map { $_, $counts->{$_} } keys %$counts; # make copy
308             # $counts = {}; # init to 0
309             # $cnt = Math::BigInt::bzero();
310             # # for each of the ending chars
311             # foreach my $char (keys %$org_counts)
312             # {
313             # # and for each of it's bigrams
314             # $c = $org_counts->{$char}; # speed up
315             # foreach my $ec ( @{$self->{_bi}->{$char}})
316             # {
317             # # add to the new ending char the number of possibilities
318             # $counts->{$ec} += $c;
319             # }
320             # # now sum them up by multiplying bi-grams times org_char count
321             # $cnt += @{$self->{_bi}->{$char}} * $org_counts->{$char};
322             # }
323             # $self->{_count}->[$i] = $cnt; # store this level
324             #print "$i => $self->{_count}->[$i]\n";
325              
326             #########################################################################
327             # for each starting char, add together how many strings each follower
328             # starts in level-1
329             # print "level $i\n";
330 8         16 $last = Math::BigInt::bzero();
331 8         113 $count = Math::BigInt::bzero(); # all counts
332 8         80 my $bi = $self->{_bi};
333 8         18 foreach my $c (keys %$bi) # for each possible char
334             {
335 44         1350 my $cnt = 0;
336 44         33 foreach my $cf (@{$bi->{$c}}) # for each follower
  44         63  
337             {
338 64   100     141 my $ci = $self->{_scnt}->[$i-1]->{$cf} || 0;
339             # print "$c followed by $cf $ci times\n",
340 64         61 $cnt += $ci; # add count in level-1
341             }
342 44         52 $self->{_scnt}->[$i]->{$c} = $cnt; # store
343             # $self->{_ssum}->[$i]->{$c} = $last; # store sum up to here
344 44         74 $last += $cnt; # next one is summed up
345 44 100       3738 $count += $cnt if exists $self->{_sm}->{$c}; # only valid starts
346             # print "last $last count $count cnt $cnt\n";
347             }
348 8         230 $self->{_count}->[$i] = $count; # all in class w/ valid starts
349 8         30 $self->{_sum}->[$i] = $self->{_count}->[$i-1] + $self->{_sum}->[$i-1];
350              
351             # $last = Math::BigInt->bzero(); # set to 0
352             # foreach $c (@{$self->{_start}})
353             # {
354             # $cnt = Math::BigInt->bzero(); # number of followers
355             # foreach $cf (@{$self->{_bi}->{$c}}) # for each follower
356             # {
357             # my $ci = $self->{_scnt}->[$i-1]->{$cf} || 0;
358             # print "$c $cnt += ",$ci," ($cf)\n";
359             # $cnt += $ci; # add count in level-1
360             # }
361             # $self->{_scnt}->[$i]->{$c} = $cnt; # and store it
362             # $self->{_ssum}->[$i]->{$c} = $last; # store sum up to here
363             # $last += $cnt; # next one is summed up
364             # }
365             # $self->{_count}->[$i] = $last; # sum of all strings
366             # $self->{_sum}->[$i] = $self->{_count}->[$i-1] + $self->{_sum}->[$i-1];
367 8         376 $i++;
368             }
369 7         122 $self->{_cnt} = $i-1; # store new cache size
370             }
371              
372             sub is_valid
373             {
374             # check wether a string conforms to the given charset set
375 7     7 1 10 my $self = shift;
376 7         7 my $str = shift;
377              
378             # print "$str\n";
379 7 50       12 return 0 if !defined $str;
380 7 50 33     16 return 1 if $str eq '' && $self->{_minlen} <= 0;
381              
382 7         14 my $int = Math::BigInt::bzero();
383 7         101 my @chars;
384 7 50       14 if (defined $self->{_sep})
385             {
386 0         0 @chars = split /$self->{_sep}/,$str;
387 0 0       0 shift @chars if $chars[0] eq '';
388 0 0       0 pop @chars if $chars[-1] eq $self->{_sep};
389             }
390             else
391             {
392 7         3 my $i = 0; my $len = CORE::length($str); my $clen = $self->{_clen};
  7         7  
  7         6  
393 7         15 while ($i < $len)
394             {
395 23         27 push @chars, substr($str,$i,$clen); $i += $clen;
  23         26  
396             }
397             }
398             # length okay?
399 7 50       18 return 0 if scalar @chars < $self->{_minlen};
400 7 50       304 return 0 if scalar @chars > $self->{_maxlen};
401              
402             # valid start char?
403 7         236 my $map = $self->{_map};
404 7 100       46 return 0 unless exists $map->{$chars[0]};
405             # check if conforms to bi-grams
406 6 50       11 return 1 if @chars == 1;
407             # further checks for strings longer than 1
408 6         4 my $i = 1; # start at second char
409 6         7 $map = $self->{_bmap};
410 6         11 while ($i < @chars)
411             {
412             #print "is valid $i $chars[$i-1] $chars[$i]\n";
413             # print "$chars[$i-1] $chars[$i]: ",
414             # $map->{$chars[$i-1]} || 'undef'," ",
415             # $map->{$chars[$i-1]}->{$chars[$i]} || 'undef',"\n";
416 13 100       26 return 0 unless exists $map->{$chars[$i-1]};
417 12 100       57 return 0 unless exists $map->{$chars[$i-1]}->{$chars[$i]};
418 8         11 $i++;
419             }
420 1         4 return 1;
421             }
422              
423             sub num2str
424             {
425             # convert Math::BigInt/Math::String to string
426 0     0 0 0 my $self = shift;
427 0         0 my $x = shift;
428              
429 0 0       0 $x = new Math::BigInt($x) unless ref $x;
430 0 0       0 return undef if ($x->sign() !~ /^[+-]$/);
431 0 0       0 if ($x->is_zero())
432             {
433 0 0       0 return wantarray ? ('',0) : '';
434             }
435 0         0 my $j = $self->{_cnum}; # nr of chars
436              
437 0 0       0 if ($x <= $j)
438             {
439 0         0 my $c = $self->{_ones}->[$x-1];
440 0 0       0 return wantarray ? ($c,1) : $c; # string len == 1
441             }
442              
443 0         0 my $digits = $self->chars($x); my $d = $digits;
  0         0  
444              
445             # now treat the string as it were a zero-padded string of length $digits
446              
447 0         0 my $es = "num2str() for bi-grams not ready yet";
448 0 0       0 return wantarray ? ($es,$d) : $es;
449             }
450              
451             sub str2num
452             {
453             # convert Math::String to Math::BigInt
454 4     4 0 356 my $self = shift;
455 4         5 my $str = shift; # simple string
456              
457 4         9 my $int = Math::BigInt::bzero();
458 4         57 my $i = CORE::length($str);
459              
460 4 100       10 return $int if $i == 0;
461 3         4 my $map = $self->{_map};
462 3         3 my $clen = $self->{_clen}; # len of one char
463 3 50       12 return new Math::BigInt($map->{$str}) if $i == $clen;
464 0 0       0 if (!defined $self->{_sep})
465             {
466 0         0 my $class = $i / $clen;
467 0 0       0 $self->_calc($class) if $class > $self->{_cnt}; # not yet cached?
468 0         0 $int = $self->{_sum}->[$class]; # base number
469             # print "base $int class $class\n";
470 0         0 $i = $clen; $class--;
  0         0  
471             # print "start with pos $i, class $class\n";
472 0         0 while ($class > 0)
473             {
474 0         0 $int += $self->{_ssum}->[$class]->{substr($str,$i,$clen)};
475             # print "$i $class $int ",substr($str,$i,$clen)," ",
476             # $self->{_ssum}->[$class]->{substr($str,$i,$clen)},"\n";
477 0         0 $class --;
478 0         0 $i += $clen;
479             #print "s2n $int j: $j i: $i m: $mul c: ",
480             #substr($str,$i+$clen,$clen),"\n";
481             }
482             # print "$int\n";
483             }
484             else
485             {
486             # sep char
487 0         0 my @chars = split /$self->{_sep}/, $str;
488 0 0       0 shift @chars if $chars[0] eq ''; # strip leading sep
489 0         0 my $class = scalar @chars;
490 0         0 foreach (@chars)
491             {
492 0         0 $int += $self->{_ssum}->[$class]->{$_};
493 0         0 $class --;
494             # print "$class $int\n";
495             }
496             }
497 0         0 return $int;
498             }
499              
500             sub chars
501             {
502             # return number of characters in output string
503 0     0 1 0 my $self = shift;
504 0         0 my $x = shift;
505              
506 0 0 0     0 return 0 if $x->is_zero() || $x->is_nan() || $x->is_inf();
      0        
507              
508 0         0 my $i = 1;
509             # not done yet
510 0         0 return $i;
511             }
512              
513             sub first
514             {
515 13     13 1 16 my $self = shift;
516 13   100     34 my $count = abs(shift || 0);
517              
518 13 100       58 return if $count < $self->{_minlen};
519 11 100 66     349 return if defined $self->{_maxlen} && $count > $self->{_maxlen};
520 10 100       250 return '' if $count == 0;
521              
522 9 100       30 return $self->{_ones}->[0] if $count == 1;
523 8         6 my $f;
524 8         9 foreach my $c (@{$self->{_start}})
  8         12  
525             {
526 8         13 $f = $self->_first('',$c,1,$count);
527 8 50       27 return $f if defined $f;
528             }
529 0         0 return;
530             }
531              
532             sub _first
533             {
534             # recursively check followers whether they are okay, or not
535             # $self, $f, $ending, $level, $count,
536              
537 29     29   40 my ($self,$f,$ending,$level,$count) = @_;
538              
539 29 100       37 if ($level >= $count) # overshot
540             {
541 8 50       21 return $f.$ending if exists $self->{_end}->{$ending};
542 0         0 return;
543             }
544              
545 21 50       34 return if !exists $self->{_bi}->{$ending};
546 21         13 foreach my $c (@{$self->{_bi}->{$ending}})
  21         24  
547             {
548 21         43 my $rc = $self->_first($f.$ending,$c,$level+1,$count);
549 21 100       38 return $rc if defined $rc;
550             }
551 1         2 return; # found nothing
552             }
553              
554             sub _last
555             {
556             # recursively check followers whether they are okay, or not
557             # $self, $f, $ending, $level, $count,
558              
559 28     28   29 my ($self,$f,$ending,$level,$count) = @_;
560              
561 28 100       35 if ($level >= $count) # overshot
562             {
563 6 50       16 return $f.$ending if exists $self->{_end}->{$ending};
564 0         0 return;
565             }
566              
567 22 100       54 return if !exists $self->{_bi}->{$ending};
568              
569 16         12 foreach my $c (reverse @{$self->{_bi}->{$ending}})
  16         20  
570             {
571 16         47 my $rc = $self->_last($f.$ending,$c,$level+1,$count);
572 16 100       37 return $rc if defined $rc;
573             }
574 3         4 return; # found nothing
575             }
576              
577             sub last
578             {
579 10     10 1 16 my $self = shift;
580 10   100     25 my $count = abs(shift || 0);
581              
582 10 100       29 return if $count < $self->{_minlen};
583 8 50 33     367 return if defined $self->{_maxlen} && $count > $self->{_maxlen};
584 8 100       351 return '' if $count == 0;
585              
586 7 100       52 return $self->{_ones}->[-1] if $count == 1;
587 6         6 my $f;
588 6         6 foreach my $c (reverse @{$self->{_start}})
  6         10  
589             {
590 12         16 $f = $self->_last('',$c,1,$count);
591 12 100       34 return $f if defined $f;
592             }
593 0           return;
594             }
595              
596             sub next
597             {
598 0     0 1   my $self = shift;
599 0           my $str = shift;
600              
601 0 0         if ($str->{_cache} eq '') # 0 => 1
602             {
603 0   0       $str->{_cache} = $self->first($self->minlen()||1);
604 0           return;
605             }
606              
607             # only the rightmost digit is adjusted. If this overflows, we simple
608             # invalidate the cache. The time saved by updating the cache would be to
609             # small to be of use, especially since updating the cache takes more time
610             # then. Also, if the cached isn't used later, we would have spent the
611             # update-time in vain.
612              
613             # for higher orders not ready yet
614 0           $str->{_cache} = undef;
615              
616 0           $self;
617             }
618              
619             sub prev
620             {
621 0     0 1   my $self = shift;
622 0           my $str = shift;
623              
624 0 0         if ($str->{_cache} eq '') # 0 => 1
625             {
626 0   0       $str->{_cache} = $self->first($self->minlen()||1);
627 0           return;
628             }
629              
630             # for higher orders not ready yet
631 0           $str->{_cache} = undef;
632              
633 0           $self;
634             }
635              
636              
637             __END__