| 1 | # -*- Perl -*- | ||||||||||
| 2 | # | ||||||||||
| 3 | # based on List::PriorityQueue execpt that payloads with identical | ||||||||||
| 4 | # priorities are grouped together | ||||||||||
| 5 | |||||||||||
| 6 | package List::GroupingPriorityQueue; | ||||||||||
| 7 | |||||||||||
| 8 | 2 | ▶ | use 5.6.0; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 9 | 2 | ▶ | use strict; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 10 | 2 | ▶ | use warnings; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 11 | 2 | our $VERSION = '0.01'; | |||||||||
| 12 | |||||||||||
| 13 | 2 | ▶ | use parent qw(Exporter); | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 14 | 2 | our @EXPORT_OK = | |||||||||
| 15 | qw(grpriq_add grpriq_min grpriq_min_values grpriq_max grpriq_max_values); | ||||||||||
| 16 | |||||||||||
| 17 | ######################################################################## | ||||||||||
| 18 | # | ||||||||||
| 19 | # FUNCTIONS | ||||||||||
| 20 | |||||||||||
| 21 | 18 | ▶ | sub grpriq_add { | ||||||||
|
Subroutine
grpriq_add: called CC=9 SCAR=22.0
Pod
documented
| |||||||||||
| 22 | 18 | my ( $qref, $priority, @rest ) = @_; | |||||||||
| 23 | # special cases | ||||||||||
| 24 | 18 | ▶ | unless (@$qref) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 25 | 4 | @$qref = [ [@rest], $priority ]; | |||||||||
| 26 | 4 | return; | |||||||||
| 27 | } | ||||||||||
| 28 | 14 | ▶ | if ( $priority > $qref->[-1][1] ) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 29 | 3 | push @$qref, [ [@rest], $priority ]; | |||||||||
| 30 | 3 | return; | |||||||||
| 31 | } | ||||||||||
| 32 | 11 | ▶ | if ( $priority < $qref->[0][1] ) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 33 | 2 | unshift @$qref, [ [@rest], $priority ]; | |||||||||
| 34 | 2 | return; | |||||||||
| 35 | } | ||||||||||
| 36 | 9 | ▶ | if ( $priority == $qref->[-1][1] ) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 37 | 2 | push @{ $qref->[-1][0] }, @rest; | |||||||||
| 38 | 2 | return; | |||||||||
| 39 | } | ||||||||||
| 40 | 7 | ▶ | if ( $priority == $qref->[0][1] ) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 41 | 2 | push @{ $qref->[0][0] }, @rest; | |||||||||
| 42 | 2 | return; | |||||||||
| 43 | } | ||||||||||
| 44 | 5 | my $lower = 0; | |||||||||
| 45 | 5 | my $midpoint; | |||||||||
| 46 | 5 | my $upper = $#$qref; | |||||||||
| 47 | 5 | ▶ | while ( $lower <= $upper ) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 48 | 12 | $midpoint = ( $lower + $upper ) >> 1; | |||||||||
| 49 | 12 | ▶ | if ( $priority < $qref->[$midpoint][1] ) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 50 | 4 | $upper = $midpoint - 1; | |||||||||
| 51 | 4 | next; | |||||||||
| 52 | } | ||||||||||
| 53 | 8 | ▶ | if ( $priority > $qref->[$midpoint][1] ) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 54 | 7 | $lower = $midpoint + 1; | |||||||||
| 55 | 7 | next; | |||||||||
| 56 | } | ||||||||||
| 57 | 1 | push @{ $qref->[$midpoint][0] }, @rest; | |||||||||
| 58 | 1 | return; | |||||||||
| 59 | } | ||||||||||
| 60 | 4 | splice @$qref, $lower, 0, [ [@rest], $priority ]; | |||||||||
| 61 | 4 | return; | |||||||||
| 62 | } | ||||||||||
| 63 | |||||||||||
| 64 | 2 | ▶ | sub grpriq_min { shift @{ $_[0] } } | ||||||||
|
Subroutine
grpriq_min: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||
| 65 | |||||||||||
| 66 | 2 | ▶ | sub grpriq_min_values { | ||||||||
|
Subroutine
grpriq_min_values: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||
| 67 | 2 | my $ref = shift @{ $_[0] }; | |||||||||
| 68 | 2 | ▶ | return unless defined $ref; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 69 | 1 | $ref->[0]; | |||||||||
| 70 | } | ||||||||||
| 71 | |||||||||||
| 72 | 1 | ▶ | sub grpriq_max { pop @{ $_[0] } } | ||||||||
|
Subroutine
grpriq_max: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||
| 73 | |||||||||||
| 74 | 2 | ▶ | sub grpriq_max_values { | ||||||||
|
Subroutine
grpriq_max_values: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||
| 75 | 2 | my $ref = pop @{ $_[0] }; | |||||||||
| 76 | 2 | ▶ | return unless defined $ref; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 77 | 1 | $ref->[0]; | |||||||||
| 78 | } | ||||||||||
| 79 | |||||||||||
| 80 | ######################################################################## | ||||||||||
| 81 | # | ||||||||||
| 82 | # METHODS | ||||||||||
| 83 | |||||||||||
| 84 | 1 | ▶ | sub each { | ||||||||
|
Subroutine
each: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||
| 85 | 1 | my ( $self, $callback ) = @_; | |||||||||
| 86 | 1 | ▶ | while ( my $entry = shift @{ $self->{queue} } ) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 87 | 2 | $callback->(@$entry); | |||||||||
| 88 | } | ||||||||||
| 89 | } | ||||||||||
| 90 | |||||||||||
| 91 | 1 | ▶ | sub new { bless { queue => [] }, $_[0] } | ||||||||
|
Subroutine
new: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||
| 92 | |||||||||||
| 93 | 8 | ▶ | sub insert { | ||||||||
|
Subroutine
insert: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||
| 94 | 8 | my ( $self, $priority, @rest ) = @_; | |||||||||
| 95 | 8 | grpriq_add( $self->{queue}, $priority, @rest ); | |||||||||
| 96 | 8 | return $self; | |||||||||
| 97 | } | ||||||||||
| 98 | |||||||||||
| 99 | 1 | ▶ | sub min { shift @{ $_[0]->{queue} } } | ||||||||
|
Subroutine
min: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||
| 100 | |||||||||||
| 101 | 3 | ▶ | sub min_values { | ||||||||
|
Subroutine
min_values: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||
| 102 | 3 | my $ref = shift @{ $_[0]->{queue} }; | |||||||||
| 103 | 3 | ▶ | return unless defined $ref; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 104 | 2 | $ref->[0]; | |||||||||
| 105 | } | ||||||||||
| 106 | 2 | *pop = \&min_values; | |||||||||
| 107 | |||||||||||
| 108 | 1 | ▶ | sub max { pop @{ $_[0]->{queue} } } | ||||||||
|
Subroutine
max: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||
| 109 | |||||||||||
| 110 | 2 | ▶ | sub max_values { | ||||||||
|
Subroutine
max_values: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||
| 111 | 2 | my $ref = pop @{ $_[0]->{queue} }; | |||||||||
| 112 | 2 | ▶ | return unless defined $ref; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 113 | 1 | $ref->[0]; | |||||||||
| 114 | } | ||||||||||
| 115 | |||||||||||
| 116 | 2 | 1; | |||||||||
| 117 | __END__ | ||||||||||