blib/lib/Statistics/WeightedSelection.pm

filter: Statementstmt 97.5% 117 / 120 Branchbran 90.0% 36 / 40 Conditioncond 57.1% 8 / 14 MC/DCmcdc 37.5% 3 / 8 Subroutinesub 100% 14 / 14 Podpod 100% 7 / 7 totaltotal 91.1% 185 / 203 CC 30 SCAR 17.2
CC
30
Cov
93%
_consolidate
9.3
add
7.0
get
7.0
CRAP 5.6
↑ Summary
1 package Statistics::WeightedSelection;
2 1 $Statistics::WeightedSelection::VERSION = '0.002';
3 1 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
4 1 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
5 1 ▶use Carp qw/croak cluck/;
Subroutine BEGIN: called CC=1 SCAR=0.0
6  
7 1 ▶use Storable qw/freeze/;
Subroutine BEGIN: called CC=1 SCAR=0.0
8  
9 3 ▶sub new {
Subroutine new: called CC=2 SCAR=6.9
Pod documented
10 3 my ($class, %args) = @_;
11  
12 return bless {
13 objects => [],
14 id_lookup => {},
15 3 ▶ replace_after_get => $args{replace_after_get} || 0,
Condition100%2/2
$args{'replace_after_get'} || 0
l!l
21
MC/DC100%1/1
$args{'replace_after_get'} || 0
$args{'replace_after_get'}
Truth table100%2/2
A
A= $args{'replace_after_get'}
Aresult
11
00
16 }, $class;
17 }
18  
19 65 ▶sub add {
Subroutine add: called CC=7 SCAR=19.5
Pod documented
20 65 my ($self, %args) = @_;
21  
22 # a non-zero number which can include a decimal
23 65 my $weight = $args{weight};
24  
25 # the scalar item that becomes a candidate for random selection
26 65 my $object = $args{object};
27  
28 # an optional id, which can be used for later removal from pool
29 65 ▶ my $id = defined $args{id} ? $args{id} : (ref $object ? freeze($object) : $object);
Branch: 2 branches
BranchTrueFalseTotal
defined $args{'id'} ? : 3 62 65
ref $object ? : 2 60 62
30  
31 65 ▶ unless ($weight && $object) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($weight and $object) 2 63 65
Condition100%3/3
$weight and $object
!ll&&!rl&&r
1163
MC/DC100%2/2
$weight and $object
$weight $object
Truth table100%3/3
A and B
A= $weightB= $object
ABresult
0X0
100
111
32 2 croak 'Calls to ' . __PACKAGE__ . "::add() must include an arg named 'object'"
33 . " and a non-zero weight\n";
34 }
35  
36 63 ▶ unless ($weight =~ /^\d+(\.\d*)?/) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($weight =~ /^\d+(\.\d*)?/) 0 63 63
37 0 croak 'Calls to ' . __PACKAGE__ . "::add()'s must include an arg named 'weight'"
38 . " that must be a whole integer or number with decimal\n";
39 }
40  
41 # in order to derive the starting_index (see the next stanza),
42 # we need the last item in @$self
43 63 my $last = $self->_get_last;
44  
45 # develops a structure that looks like the following, with each element being
46 # [
47 # {
48 # starting_index => 0,
49 # length => 40,
50 # object => 'apple',
51 # id => 'gwr3723',
52 # },
53 # {
54 # starting_index => 40,
55 # length => 16,
56 # object => 'plum',
57 # id => 'avx9716',
58 # },
59 # {
60 # starting_index => 56,
61 # length => 3.4
62 # object => 'peach',
63 # id => 'zzi1250',
64 # },
65 # {
66 # starting_index => 59.4,
67 # length => 60,
68 # object => 'mango',
69 # id => 'umn2932',
70 # },
71 # ]
72  
73 63 ▶ push @{$self->{objects}}, {
Branch: 1 branch
BranchTrueFalseTotal
defined $last ? : 48 15 63
74 # if this is the first object, our starting index is zero, and otherwise, we add the
75 # new weight to the previous starting_index + weight for future binary search.
76 63 starting_index => defined $last ? $last->{starting_index} + $last->{weight} : 0,
77 weight => $weight,
78 object => $object,
79 id => $id,
80 };
81  
82 # I decided to use a hash with empty values for pointers to the index for a given
83 # id or frozen object scalar, rather than using an arrayref, which might have been
84 # more intuitive. More than one added object can have the same id, and I wanted a
85 # quick way to remove individual object pointers without having to iterate over an
86 # array somehow.
87 63 $self->{id_lookup}->{$id}->{$#{$self->{objects}}} = undef;
88  
89 63 return $#{$self->{objects}};
90 }
91  
92 12 ▶sub remove {
Subroutine remove: called CC=6 SCAR=18.3
Pod documented
93 12 my ($self, $id) = @_;
94  
95 12 ▶ unless (defined $id) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $id) 1 11 12
96 1 croak 'Calls to ' . __PACKAGE__ . "::remove() must include an id to remove\n";
97 }
98  
99 11 ▶ $id = ref $id ? freeze($id) : $id;
Branch: 1 branch
BranchTrueFalseTotal
ref $id ? : 2 9 11
100  
101 # delete the pointer altogether, as all of the objects with this id will be removed.
102 11 my $indexes = delete $self->{id_lookup}->{$id};
103  
104 11 ▶ unless ($indexes && %{$indexes}) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($indexes and %{$indexes;}) 0 11 11
Condition33%1/3
$indexes and %{$indexes;}
!ll&&!rl&&r
0011
MC/DC0%0/2
$indexes and %{$indexes;}
$indexes %{$indexes;}
Truth table33%1/3
A and B
A= $indexesB= %{$indexes;}
ABresult
0X0
100
111
105 # no need for this to be fatal, but it might indicate a bug in caller's code
106 0 cluck "Key $id contains no associated indexes currently\n";
107 0 return;
108 }
109  
110 11 my @reverse_sorted_indexes = sort {$b <=> $a} keys %{$indexes};
111  
112 11 my @removed;
113 11 for my $index (@reverse_sorted_indexes) {
114 # remove all items that were pointed to that had this id
115 # doing them in reverse, so that splicing out an earlier item won't
116 # alter the indexes of items we want to splice out later.
117 18 push @removed, splice(@{$self->{objects}}, $index, 1);
118 }
119  
120 # we've altered our items, and need to fix our object starting indexes
121 # and pointers for our keys.
122 11 $self->_consolidate(reverse @reverse_sorted_indexes);
123  
124 # return the removed items
125 11 return map {$_->{object}} @removed;
126 }
127  
128 1410009 ▶sub get {
Subroutine get: called CC=7 SCAR=19.5
Pod documented
129 1410009 my ($self, $override_replacement) = @_;
130 1410009 ▶ return unless @{ $self->{objects} };
Branch: 1 branch
BranchTrueFalseTotal
unless @{$self->{"objects"};} 1 1410008 1410009
131  
132 # when adding the starting_index and length together of the last item in @$self,
133 # (see the generated structure note in the add() method for more info), the
134 # max random number to generate is determined.
135 1410008 my $last = $self->_get_last;
136 1410008 my $random = rand($last->{starting_index} + $last->{weight});
137  
138 # binary search to quickly find the weighted index range. the random number ($random)
139 # is tested against the range of starting_index and (starting_index + length) to
140 # determine if the number is lower or higher than the current arrayref until a match
141 # is found.
142 1410008 my $max = $#{ $self->{objects} };
143 1410008 my $min = 0;
144 1410008 my $index = 0;
145 1410008 ▶ while ( $max >= $min ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($max >= $min) 2196461 0 2196461
146 2196461 $index = int( ( $max + $min ) / 2 );
147 2196461 my $current_object = $self->{objects}->[$index];
148  
149 2196461 ▶ if ( $random < $current_object->{starting_index} ) {
Branch: 2 branches
BranchTrueFalseTotal
if ($random < $current_object->{'starting_index'}) { } 335928 1860533 2196461
elsif ($random >= $current_object->{'starting_index'} + $current_object->{'weight'}) { } 450525 1410008 1860533
150 335928 $max = $index - 1;
151 }
152 elsif ( $random >= ($current_object->{starting_index} + $current_object->{weight}) ) {
153 450525 $min = $index + 1;
154 }
155 else {
156 1410008 last;
157 }
158 }
159  
160 1410008 my $random_element;
161  
162 # don't run the removal logic in the else block if the user instructed us to replace
163 # the object
164 1410008 ▶ if ($self->replace_after_get) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->replace_after_get) { } 10002 1400006 1410008
165 10002 $random_element = $self->{objects}->[$index];
166 }
167 else {
168 # remove the element in question
169 1400006 $random_element = splice(@{$self->{objects}}, $index, 1);
170  
171 # delete out the specific pointer to this item
172 1400006 delete $self->{id_lookup}->{$random_element->{id}}->{$index};
173 1400006 ▶ unless (keys %{$self->{id_lookup}->{$random_element->{id}}}) {
Branch: 1 branch
BranchTrueFalseTotal
unless (keys %{$self->{"id_lookup"}{$random_element->{"id"}};}) 1325519 74487 1400006
174 1325519 delete $self->{id_lookup}->{$random_element->{id}};
175 }
176  
177 # fix starting indexes and pointers for other objects.
178 1400006 $self->_consolidate($index);
179 }
180  
181 # return our selected object:
182 1410008 return $random_element->{object};
183 }
184  
185 1410011 ▶sub replace_after_get {
Subroutine replace_after_get: called CC=2 SCAR=6.9
Pod documented
186 1410011 my ($self, $new_setting) = @_;
187 1410011 ▶ $self->{replace_after_get} = $new_setting if defined $new_setting;
Branch: 1 branch
BranchTrueFalseTotal
if defined $new_setting 1 1410010 1410011
188 1410011 return $self->{replace_after_get};
189 }
190  
191 17 ▶sub clear {
Subroutine clear: called CC=1 SCAR=0.0
Pod documented
192 17 my ($self) = @_;
193 17 $self->{objects} = [];
194 17 $self->{id_lookup} = {};
195 17 return;
196 }
197  
198 1410067 ▶sub count {
Subroutine count: called CC=2 SCAR=6.9
Pod documented
199 1410067 my ($self) = @_;
200 1410067 ▶ return 0 if !@{ $self->{objects} };
Branch: 1 branch
BranchTrueFalseTotal
unless @{$self->{"objects"};} 280005 1130062 1410067
201 1130062 return $#{ $self->{objects} } + 1;
202 }
203  
204 1130152 ▶sub _dump {
Subroutine _dump: called CC=1 SCAR=0.0
205 1130152 my ($self) = @_;
206 # basically, don't return starting_index, as that is an internal implementation
207 # detail, and doesn't need to be shown to the user
208 2450418 return [map { {object => $_->{object}, weight => $_->{weight}, id => $_->{id}} }
209 1130152 @{$self->{objects}}];
210 }
211  
212 # internal method to fix id pointers and starting_indexes after a remove() or get() call
213 1400017 ▶sub _consolidate {
Subroutine _consolidate: called CC=9 SCAR=22.3
214 1400017 my $self = shift;
215  
216 # disregard all indexes greater than the current length of our objects property array
217 1400017 my @removed_indexes = sort grep {$_ <= $#{ $self->{objects} }} @_;
218  
219 # separate our list of objects into segments bookended by our removed indexes
220 # say we started with something like:
221 # 0 1 2 3 4 5 6
222 # 'alan', 'nate', 'brian', 'bob', 'nate', 'ryan', 'nate'
223 #
224 # and we called remove() on 'nate', then (1, 4, 6) would be passed to this routine, which
225 # are array indexes, NOT our starting_indexes. 6 will be removed from consideration, as
226 # it was at the end of the array.
227 #
228 # our first segment (former indexes 2 and 3) would be fixed as such:
229 # well, we need to change the following as a result:
230 # update 'brian''s starting index to be the starting index of 'alan' + its weight,
231 # and subtract 1 (as we removed 1 objects before this one) from its pointer in the id lookup.
232 # update 'bob''s starting index to be the starting index of 'brian' + its weight
233 # and subtract 1 (as we removed 1 objects before this one) from its pointer in the id lookup.
234 #
235 # our second segment (former index 5) would be fixed as such:
236 # well, we need to change the following as a result:
237 # update 'ryan''s starting index to be the starting index of 'bob' + its weight
238 # and subtract 2 (as we removed 2 objects before this one) from its pointer in the id lookup.
239  
240 1400017 for my $removed_index_index (0..$#removed_indexes) {
241 # find our range bookends
242 833466 my $range_start = $removed_indexes[$removed_index_index];
243 my $range_end = $removed_index_index == $#removed_indexes
244 833466 ▶ ? $#{ $self->{objects} }
Branch: 1 branch
BranchTrueFalseTotal
$removed_index_index == $#removed_indexes ? : 833466 0 833466
245 : $removed_indexes[$removed_index_index + 1] - 1;
246  
247 # how many indexes were removed before our current segment, and thus the amount to subtract
248 # from the respective pointers
249 833466 my $to_subtract = @removed_indexes - $removed_index_index;
250  
251 833466 my %ids_evaluated_for_range;
252 833466 for my $object_index ($range_start..$range_end) {
253 1481544 my $object = $self->{objects}->[$object_index];
254  
255 # do all of the subtractions of pointer indexes at once for each segment.
256 1481544 ▶ if (!$ids_evaluated_for_range{$object->{id}}++) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($ids_evaluated_for_range{$object->{"id"}}++) 1407456 74088 1481544
257 1407456 for my $index (
258 1396316 ▶ grep {$_ >= $range_start && ($removed_index_index == $#removed_indexes || $_ <= $range_end)}
Condition33%2/6
$_ >= $range_start && ($removed_index_index == $#removed_indexes || $_ <= $range_end)
!ll&&!rl&&r
001396316
$removed_index_index == $#removed_indexes or $_ <= $range_end
l!l&&r!l&&!r
139631600
MC/DC0%0/3
$_ >= $range_start && ($removed_index_index == $#removed_indexes || $_ <= $range_end)
$_ >= $range_start $removed_index_index == $#removed_indexes $_ <= $range_end
Truth table25%1/4
A && B or C
A= $_ >= $range_startB= $removed_index_index == $#removed_indexesC= $_ <= $range_end
ABCresult
0XX0
1000
11X1
1011
259 1407456 keys %{$self->{id_lookup}->{$object->{id}}}
260 ) {
261 1396316 delete $self->{id_lookup}->{$object->{id}}->{$index};
262 1396316 $self->{id_lookup}->{$object->{id}}->{$index - $to_subtract} = undef;
263 }
264 }
265  
266 # fix the starting indexes
267 $object->{starting_index} = $object_index == 0
268 ? 0
269 1481544 ▶ : do {
Branch: 1 branch
BranchTrueFalseTotal
$object_index == 0 ? : 519865 961679 1481544
270 961679 my $previous_object = $self->{objects}->[$object_index - 1];
271 961679 $previous_object->{starting_index} + $previous_object->{weight};
272 };
273 }
274 }
275  
276 1400017 return;
277 }
278  
279  
280 # simply a utility method to get the last item in the blessed array, as it contains all
281 # the information needed to add items and generate a random number.
282 1410071 ▶sub _get_last {
Subroutine _get_last: called CC=2 SCAR=6.9
283 1410071 my ($self) = @_;
284 1410071 ▶ return unless @{ $self->{objects} };
Branch: 1 branch
BranchTrueFalseTotal
unless @{$self->{"objects"};} 15 1410056 1410071
285 1410056 return $self->{objects}->[$#{ $self->{objects} }];
286 }
287  
288 1 1;
289  
290 __END__
↑ Summary