blib/lib/Games/Tournament/RoundRobin.pm

filter: Statementstmt 88.1% 156 / 177 Branchbran 87.9% 51 / 58 Conditioncond 37.5% 6 / 16 MC/DCmcdc 10.0% 1 / 10 Subroutinesub 85.0% 17 / 20 Podpod 100% 17 / 17 totaltotal 83.2% 248 / 298 CC 51 SCAR 20.5
CC
51
Cov
85%
hasBye
20.0
realPartners
20.0
new
14.2
CRAP 7.8
↑ Summary lib/Games/League/Member.pm »
1 package Games::Tournament::RoundRobin;
2  
3 # Last Edit: 2015 Nov 15, 09:57:44
4  
5 15 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
6 15 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
7  
8 =encoding utf-8
9  
10 =head1 NAME
11  
12 Games::Tournament::RoundRobin - Round-Robin Tournament Schedule Pairings
13  
14 =head1 VERSION
15  
16 Version 0.03
17  
18 =cut
19  
20 15 our $VERSION = '0.03';
21  
22 =head1 SYNOPSIS
23  
24 $schedule = Games::Tournament::RoundRobin->new;
25  
26 $pairings = $schedule->indexesInRound($roundm);
27 $round = $schedule->meeting($member1, [$member2, $member3]);
28 ...
29  
30 =head1 DESCRIPTION
31  
32 Every member of a league of 2n players can be paired with every other member in 2n-1 rounds.
33  
34 If the league members are (Inf, 1 .. 2n-1), then in round i, i can be paired with Inf, and a can meet b, where a+b = 2i (mod 2n-1).
35  
36 =head1 REQUIREMENTS
37  
38 Installing this module requires Module::Build.
39  
40 =head1 METHODS
41  
42 =head2 new
43  
44 Games::Tournament::RoundRobin->new( v => 5, league => [qw/Ha Be He/])
45 Games::Tournament::RoundRobin->new( league => {A => $a, B => $b})
46  
47 Where v (optional) is the number of league members, and league (optional) is a list (or a hash) reference to the individual unique league members. One of v, or league (which takes precedence) is necessary, and if league is not given, the members are identified by the numbers 0 .. n-1.
48  
49 If the league is a list (or hash) of n objects, they should be instances of a class that overloads both string quoting with a 'name' method and arithmetical operations with an 'index' method. The index method, called on the n objects in order, should return the n numbers, 0 .. n-1, and in that order if they are presented as an array. If they are presented as a hash, the hash is stored internally as an array and the keys are discarded.
50  
51 If the league is a list of strings or numbers, indexes are constructed for the values on the basis of their positions in the list, and if a hash of strings or numbers, on the basis of the lexicographic order of their keys. Each string is expected to be unique.
52  
53 If n is odd, an additional n-1, 'Bye' or object (a Games::League::Member object, by default) member, depending on the type of the first member in the league, is added at the end and n is increased by 1.
54  
55 TODO This was not such a good idea. v should not change if it is odd. That is the size of the league is the number of real members. The Bye member should not be included. This will require some refactoring.
56  
57 =cut
58  
59 sub new
60 78 ▶{
Subroutine new: called CC=14 SCAR=26.6
Pod documented
61 78 my $class = shift;
62 78 my %args = @_;
63 78 my $n;
64 my $members;
65 78 $members = $args{league};
66 78 ▶ if ( ref $members )
Branch: 1 branch
BranchTrueFalseTotal
if (ref $members) { } 75 3 78
67 {
68 75 ▶ $members = _hash2array( $members ) if ref $members eq 'HASH';
Branch: 1 branch
BranchTrueFalseTotal
if ref $members eq "HASH" 18 57 75
69 75 $n = $#$members + 1;
70 75 my $memberClass;
71 75 ▶ if ( $memberClass = ref $members->[0] )
Branch: 2 branches
BranchTrueFalseTotal
if ($memberClass = ref $members->[0]) { } 18 57 75
elsif ($members->[0] =~ /^\d+$/) { } 26 31 57
72 {
73 $members->[$_]->index == $_ or warn
74 "Index of ${_}th member is $members->[$_]->{index}, not $_,"
75 18 ▶ foreach ( 0 .. $n-1 );
Branch: 1 branch
BranchTrueFalseTotal
$members->[$_]->index == $_ or warn qq[Index of ${_}th member is $members->[$_]{"index"}, not $_,] 73 0 73
76 18 ▶ $memberClass ||= 'Games::League::Member';
Condition50%1/2
$memberClass ||= "Games::League::Member"
l!l
180
MC/DC0%0/1
$memberClass ||= "Games::League::Member"
$memberClass
Truth table50%1/2
A
A= $memberClass
Aresult
11
00
77 18 ▶ push @$members, $memberClass->new(
Branch: 1 branch
BranchTrueFalseTotal
if $n % 2 11 7 18
78 index => $n++, name => 'Bye' ) if $n%2;
79 }
80 elsif ($members->[0] =~ m/^\d+$/)
81 {
82 26 ▶ push @$members, $n++ if $n%2;
Branch: 1 branch
BranchTrueFalseTotal
if $n % 2 15 11 26
83 }
84 else {
85 31 ▶ if ($n%2)
Branch: 1 branch
BranchTrueFalseTotal
if ($n % 2) 18 13 31
86 18 { push @$members, 'Bye' ;
87 18 $n++;
88 }
89 }
90 }
91 else {
92 3 ▶ $n ||= $args{v};
Condition33%1/3
$n ||= $args{"v"}
l!l&&r!l&&!r
030
MC/DC0%0/2
$n ||= $args{"v"}
$n $args{"v"}
Truth table33%1/3
A ||= B
A= $nB= $args{"v"}
ABresult
1X1
011
000
93 3 ▶ $n++ if $n%2;
Branch: 1 branch
BranchTrueFalseTotal
if $n % 2 3 0 3
94 }
95 78 ▶ $members ||= [ 0 .. $n-1 ];
Condition100%2/2
$members ||= [0 .. $n - 1]
l!l
753
MC/DC100%1/1
$members ||= [0 .. $n - 1]
$members
Truth table100%2/2
A
A= $members
Aresult
11
00
96 78 $args{v} = $n;
97 78 $args{league} = $members;
98 78 bless \%args, $class;
99 }
100  
101 # Converts an hash into a array discarding the keys. Used internally to
102 # store the league argument if a hash is passed.
103  
104 sub _hash2array
105 18 ▶{
Subroutine _hash2array: called CC=4 SCAR=13.9
106 18 my $hash = shift;
107 18 my $array;
108 my $index;
109 18 my $n = 0;
110 # $array->[$n++] = $hash->{$_} foreach ( keys %$hash );
111 18 foreach my $key ( sort keys %$hash )
112 {
113 59 ▶ if ( ref $hash->{$key} )
Branch: 1 branch
BranchTrueFalseTotal
if (ref $hash->{$key}) { } 19 40 59
114 {
115 $hash->{$key}->{index} = $n
116 19 ▶ unless exists $hash->{$key}->{index};
Branch: 1 branch
BranchTrueFalseTotal
unless exists $hash->{$key}{"index"} 0 19 19
117 19 my $index = $hash->{$key}->{index};
118 19 $array->[$index] = $hash->{$key};
119 19 $n++;
120 }
121 else
122 {
123 40 $array->[$n++] = $hash->{$key};
124 }
125 }
126 18 return $array;
127 }
128  
129 =head2 indexesInRound
130  
131 $schedule->indexesInRound($m)
132  
133 Returns an array reference of the pairings in round $m. This method is useful if you are using numbers to represent your league members. It is not so useful if you are using strings or objects and you don't know their index numbers. Positions in the array represent members. The values represent their partners. Each member is thus represented twice.
134  
135 =cut
136  
137 sub indexesInRound
138 120 ▶{
Subroutine indexesInRound: called CC=4 SCAR=13.9
Pod documented
139 120 my $self = shift;
140 120 my $n = $self->size;
141 120 my $round = shift;
142 120 my @pairings = ($round);
143 120 for my $i (1 .. $n-1)
144 {
145 966 ▶ if ($i == $round)
Branch: 1 branch
BranchTrueFalseTotal
if ($i == $round) { } 120 846 966
146 {
147 120 push @pairings, 0;
148 }
149 else
150 {
151 846 my $modPartner = ((2*$round-$i) % ($n-1));
152 846 ▶ my $partner = $modPartner? $modPartner: $n-1;
Branch: 1 branch
BranchTrueFalseTotal
$modPartner ? : 752 94 846
153 846 push @pairings, $partner;
154 }
155 }
156 120 return \@pairings;
157 }
158  
159 =head2 roundsInTournament
160  
161 $t = $schedule-> roundsInTournament;
162 $round1 = $t[0];
163 $inRound1FourthWith = $t->[0]->[3];
164 $inLastRoundLastWith = $$t[-1][-1];
165  
166 Returns, as a reference to an array of arrays, the pairings in all rounds of the tournament. This method is useful if you are using the algorithm indexes.
167  
168 =cut
169  
170 sub roundsInTournament
171 3 ▶{
Subroutine roundsInTournament: called CC=2 SCAR=6.9
Pod documented
172 3 my $self = shift;
173 3 my $matrix;
174 push @$matrix, $self->indexesInRound($_)
175 3 foreach 1 .. $self->rounds;
176 3 return $matrix;
177 }
178  
179 =head2 partner
180  
181 $schedule->partner($member, $m)
182  
183 Returns the partner of $member in round $m.
184  
185 =cut
186  
187 sub partner
188 8 ▶{
Subroutine partner: called CC=1 SCAR=0.0
Pod documented
189 8 my $self = shift;
190 8 my $member = shift;
191 8 my $round = shift;
192 8 my @partners = @{$self->indexesInRound($round)};
193 8 my $index = $self->index($member);
194 8 my $partner = $self->member($partners[$index]);
195 8 return $partner;
196 }
197  
198 =head2 membersInRound
199  
200 $schedule->membersInRound($m)
201  
202 Returns an hash reference of the pairings in round $m. This method is useful if you are using strings or objects. Keys in the hash represent league members. If the league members are objects, their names are used as keys. If 2 names are the same, the names are changed to ${name}1, ${name}2 etc. The values are their partners. Each player is thus represented twice.
203  
204 =cut
205  
206 sub membersInRound
207 4 ▶{
Subroutine membersInRound: called CC=3 SCAR=11.0
Pod documented
208 4 my $self = shift;
209 4 my $n = $self->size;
210 4 my $round = shift;
211 4 my %pairings;
212 4 my @indexes = @{$self->indexesInRound($round)};
213 4 for my $i (0 .. $n-1)
214 {
215 24 my $member = $self->member($i);
216 # my $index = $self->index($member);
217 24 ▶ if ( defined $pairings{$member} ) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $pairings{$member}) 2 22 24
218 2 my $clobbered = $member . 1;
219 2 $pairings{$clobbered} = $pairings{$member};
220 2 delete $pairings{$member};
221 2 $member = $member . 2;
222 }
223 24 my $partner = $indexes[$i];
224 24 $partner = $self->member($partner);
225 24 $pairings{$member} = $partner;
226 }
227 4 return \%pairings;
228 }
229  
230 =head2 wholeSchedule
231  
232 $schedule->wholeSchedule();
233  
234 Returns a reference to an array of arrays, with each of the latter 2-element arrays representing the players in each match in each round. Thus, you can iterate through the top-level array and inner-loop through the lower-level array and print the schedule as it has to be.
235  
236 This does not work with numbers as the names of the members and also not with "v >= n".
237  
238 =cut
239  
240 sub wholeSchedule
241 19 ▶{
Subroutine wholeSchedule: called CC=4 SCAR=13.9
Pod documented
242 19 my $self = shift;
243 19 my @schedule;
244 19 for my $i ( 1 .. $self->rounds ) {
245 71 my @pairings = @{ $self->indexesInRound($i) };
246 71 my @round;
247 71 for my $member ( 0 .. $#pairings ) {
248 466 ▶ next unless exists $pairings[$member];
Branch: 1 branch
BranchTrueFalseTotal
unless exists $pairings[$member] 233 233 466
249 233 my $partner = $pairings[$member];
250 233 delete $pairings[$partner];
251 233 push @round, [ $self->member($member),
252 $self->member($partner) ];
253 }
254 71 push @schedule, \@round;
255 }
256 19 return \@schedule;
257 }
258  
259 =head2 byelessSchedule
260  
261 $schedule->byelessSchedule();
262  
263 Returns a reference to an array of arrays. The arrays are the same as returned by C<wholeSchedule> without the "Byes," so you can iterate through them and print the schedule as it has to be.
264  
265 This does not work with numbers as the names of the members and also not with "v >= n".
266  
267 =cut
268  
269 sub byelessSchedule
270 5 ▶{
Subroutine byelessSchedule: called CC=4 SCAR=13.9
Pod documented
271 5 my $self = shift;
272 5 my $schedule = $self->wholeSchedule;
273 5 my @byeless;
274 5 for my $round ( @$schedule ) {
275 21 my @matches;
276 21 for my $match ( @$round ) {
277 73 my @contestants = @$match;
278 push @matches, $match unless
279 73 ▶ grep { $_ eq 'Bye' } @contestants;
Branch: 1 branch
BranchTrueFalseTotal
unless grep {$_ eq "Bye";} @contestants 65 8 73
280 }
281 21 push @byeless, \@matches;
282 }
283 5 return \@byeless;
284 }
285  
286 =head2 memberSchedule
287  
288 $schedule->memberSchedule($member)
289  
290 Returns, as an array reference, the partners who $member is matched with in the order in which they meet, ie round by round.
291  
292 =cut
293  
294 sub memberSchedule
295 0 ▶{
Subroutine memberSchedule: not called CC=2 SCAR=17.9
Pod documented
296 0 my $self = shift;
297 0 my $member = shift;
298 0 my $schedule;
299 0 foreach my $round ( 0 .. $self->rounds-1 )
300 {
301 0 my $allMembers = $self->indexesInRound($round);
302 0 push @$schedule, $$allMembers[$member];
303 }
304 0 return $schedule;
305 }
306  
307 =head2 meeting
308  
309 $schedule->meeting($member,$partner)
310  
311 Returns the rounds (TODO and the venue) at which $member meets $partner.
312  
313 =cut
314  
315 sub meeting
316 65 ▶{
Subroutine meeting: called CC=5 SCAR=16.1
Pod documented
317 65 my $self = shift;
318 65 my $n = $self->size;
319 65 my ($member, $partner) = @_;
320 65 my $a = $self->index($member);
321 65 my $b = $self->index($partner);
322 65 my $round = $a+$b;
323 65 ▶ if ($a == 0)
Branch: 3 branches
BranchTrueFalseTotal
if ($a == 0) { } 13 52 65
elsif ($b == 0) { } 10 42 52
elsif ($round % 2) { } 25 17 42
324 {
325 13 return 0+$b;
326 }
327 elsif ($b == 0)
328 {
329 10 return 0+$a;
330 }
331 elsif ( $round % 2) {
332 25 $round = ($round + $n-1)/2 % ($n-1);
333 25 ▶ $round ||= $n-1;
Condition66%2/3
$round ||= $n - 1
l!l&&r!l&&!r
1870
MC/DC0%0/2
$round ||= $n - 1
$round $n - 1
Truth table66%2/3
A ||= B
A= $roundB= $n - 1
ABresult
1X1
011
000
334 25 return 0+$round;
335 }
336 else {
337 17 return 0+($round/2)%($n-1);
338 }
339 }
340  
341 =head2 meetings
342  
343 $schedule->meetings($member1,[$member2,$member3,...])
344  
345 Returns, as an array reference, the rounds (TODO and the venue) at which $member1 meets $member2, $member3, ...
346  
347 =cut
348  
349 sub meetings
350 18 ▶{
Subroutine meetings: called CC=1 SCAR=0.0
Pod documented
351 18 my $self = shift;
352 18 my $n = $self->size;
353 18 my ($member, $partners) = @_;
354 my @meetings = map {
355 18 $self->meeting($member,$_);
356 } @$partners;
357 18 return \@meetings;
358 }
359  
360 =head2 index
361  
362 $schedule->index($member)
363  
364 Returns $member's index, the number which is used to pair it with other members. The index is the position, 0..n-1, of the $member in the league argument to the constructor (if an array) or the constructed array (if a hash.)
365  
366 If $member is not a member of the array, or is itself an index, undef is returned.
367  
368 =cut
369  
370 sub index
371 336 ▶{
Subroutine index: called CC=5 SCAR=16.1
Pod documented
372 336 my $self = shift;
373 336 my $member = shift;
374 336 my $members = $self->{league};
375 336 my $i = 0;
376 336 foreach my $candidate ( @$members )
377 {
378 2374 ▶ if ( $candidate =~ m/^\d+$/)
Branch: 1 branch
BranchTrueFalseTotal
if ($candidate =~ /^\d+$/) { } 2109 265 2374
379 {
380 2109 ▶ return $i if $candidate == $member;
Branch: 1 branch
BranchTrueFalseTotal
if $candidate == $member 239 1870 2109
381 }
382 else {
383 265 ▶ return $i if $candidate eq $member;
Branch: 1 branch
BranchTrueFalseTotal
if $candidate eq $member 93 172 265
384 }
385 2042 $i++;
386 }
387 4 return undef;
388 }
389  
390 =head2 member
391  
392 $schedule->member($index)
393 $schedule->member($name)
394 $bye = $schedule->member( $schedule->size-1 )
395  
396 Returns the member represented by $index, a number which ranges from 0..n-1, or by $name, a string. If there is no such member, undef is returned.
397  
398 =cut
399  
400 sub member
401 572 ▶{
Subroutine member: called CC=4 SCAR=13.9
Pod documented
402 572 my $self = shift;
403 572 my $handle = shift;
404 572 my $members = $self->{league};
405 572 ▶ if ( $handle =~ /\d+/ ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($handle =~ /\d+/) { } 562 10 572
406 562 return $members->[$handle];
407 }
408 else
409 {
410 10 foreach my $member ( @$members )
411 {
412 38 ▶ return $member if $member eq $handle;
Branch: 1 branch
BranchTrueFalseTotal
if $member eq $handle 8 30 38
413 }
414 2 return undef;
415 }
416 }
417  
418 =head2 hasBye
419  
420 $schedule->hasBye($index)
421  
422 Returns an array reference of all the partners of the $indexed member, excluding the 'Bye' member. Don't use this if you have no 'Bye' member, as it just leaves off the last member.
423  
424 =cut
425  
426 sub hasBye
427 0 ▶{
Subroutine hasBye: not called CC=4 SCAR=30.0
Pod documented
428 0 my $self = shift;
429 0 my $index = shift;
430 0 my $members = $self->{league};
431 0 my @partners;
432 0 foreach my $member ( @$members )
433 {
434 0 ▶ push @partners, $member unless
Branch: 1 branch
BranchTrueFalseTotal
unless $member == $index or $member == $self->size - 1 0 0 0
Condition0%0/3
$member == $index or $member == $self->size - 1
l!l&&r!l&&!r
000
MC/DC0%0/2
$member == $index or $member == $self->size - 1
$member == $index $member == $self->size - 1
Truth table0%0/3
A or B
A= $member == $indexB= $member == $self->size - 1
ABresult
1X1
011
000
435 ($member == $index or $member == $self->size-1);
436 }
437 0 return \@partners;
438 }
439  
440 =head2 partners
441  
442 $schedule->partners($index)
443 $schedule->partners($name)
444  
445 Returns an array reference of all the partners of the $indexed or $named member, in index order, or the order in the league argument.
446  
447 =cut
448  
449 sub partners
450 21 ▶{
Subroutine partners: called CC=5 SCAR=16.1
Pod documented
451 21 my $self = shift;
452 21 my $handle = shift;
453 21 my $members = $self->{league};
454 21 my $partneredOne = $self->member($handle);
455 21 my @partners;
456 21 foreach my $member ( @$members )
457 {
458 200 ▶ if ( $handle =~ /\d+/ )
Branch: 1 branch
BranchTrueFalseTotal
if ($handle =~ /\d+/) { } 178 22 200
459 {
460 178 ▶ push @partners, $member unless
Branch: 1 branch
BranchTrueFalseTotal
unless $self->index($member) == $handle 162 16 178
461 $self->index($member) == $handle;
462 }
463 else
464 {
465 22 ▶ push @partners, $member unless $member eq $handle;
Branch: 1 branch
BranchTrueFalseTotal
unless $member eq $handle 18 4 22
466 }
467 }
468 21 return \@partners;
469 }
470  
471 =head2 realPartners
472  
473 $schedule->realPartners($index)
474  
475 Returns an array reference of all the partners of the $indexed member, excluding the 'Bye' member. Don't use this if you have no 'Bye' member, as it just leaves off the last member.
476  
477 =cut
478  
479 sub realPartners
480 0 ▶{
Subroutine realPartners: not called CC=4 SCAR=30.0
Pod documented
481 0 my $self = shift;
482 0 my $index = shift;
483 0 my $members = $self->{league};
484 0 my @partners;
485 0 foreach my $member ( @$members )
486 {
487 0 ▶ push @partners, $member unless
Branch: 1 branch
BranchTrueFalseTotal
unless $member == $index or $member == $self->size - 1 0 0 0
Condition0%0/3
$member == $index or $member == $self->size - 1
l!l&&r!l&&!r
000
MC/DC0%0/2
$member == $index or $member == $self->size - 1
$member == $index $member == $self->size - 1
Truth table0%0/3
A or B
A= $member == $indexB= $member == $self->size - 1
ABresult
1X1
011
000
488 ($member == $index or $member == $self->size-1);
489 }
490 0 return \@partners;
491 }
492  
493 =head2 size
494  
495 $schedule->size
496  
497 Returns the number of members in the round robin. Sometimes this may not be the same as the number of league members specified, because the array of league members takes precedence if supplied, and a bye is added if the number is odd.
498  
499 =cut
500  
501 sub size
502 256 ▶{
Subroutine size: called CC=1 SCAR=0.0
Pod documented
503 256 my $self = shift;
504 256 $self->{v};
505 }
506  
507 =head2 rounds
508  
509 $schedule->rounds
510  
511 Returns the number of rounds in the round robin. This equals the number of league members, minus 1.
512  
513 =cut
514  
515 sub rounds
516 38 ▶{
Subroutine rounds: called CC=1 SCAR=0.0
Pod documented
517 38 my $self = shift;
518 38 $self->size - 1;
519 }
520  
521 =head1 AUTHOR
522  
523 Dr Bean, C<< <drbean at (ie, the at sign) cpan dot (ie the dot sign) org> >>
524  
525 =head1 BUGS
526  
527 Please report any bugs or feature requests to C<bug-games-tournament-roundrobin@rt.cpan.org>, or through the web interface at L<http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Games-Tournament-RoundRobin>. I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.
528  
529 =head1 SUPPORT
530  
531 You can find documentation for this module with the perldoc command.
532  
533 perldoc Games::Tournament::RoundRobin
534  
535 You can also look for information at:
536  
537 =over 4
538  
539 =item * AnnoCPAN: Annotated CPAN documentation
540  
541 L<http://annocpan.org/dist/Games-Tournament-RoundRobin>
542  
543 =item * CPAN Ratings
544  
545 L<http://cpanratings.perl.org/d/Games-Tournament-RoundRobin>
546  
547 =item * RT: CPAN's request tracker
548  
549 L<http://rt.cpan.org/NoAuth/Bugs.html?Dist=Games-Tournament-RoundRobin>
550  
551 =item * Search CPAN
552  
553 L<http://search.cpan.org/dist/Games-Tournament-RoundRobin>
554  
555 =back
556  
557 =head1 ACKNOWLEDGEMENTS
558  
559 The algorithm saw perl attention on Mark Jason Dominus's Quiz of the Week in January 2005, last seen on the Internet at L<http://perl.plover.com/~alias/list.cgi?1:msp:2343>
560  
561 The wholeSchedule method is due to Richard Möhn.
562  
563 =head1 COPYRIGHT & LICENSE
564  
565 Copyright 2008 Dr Bean, All Rights Reserved.
566  
567 This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.
568  
569 =cut
570  
571 15 1; # End of Games::Tournament::RoundRobin
↑ Summary lib/Games/League/Member.pm »