| 1 | # Copyrights and documentation are at the end. | ||||||||||||
| 2 | |||||||||||||
| 3 | package POE::Queue::Array; | ||||||||||||
| 4 | |||||||||||||
| 5 | 203 | ▶ | use strict; | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 6 | |||||||||||||
| 7 | 203 | ▶ | use vars qw($VERSION @ISA); | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 8 | 203 | $VERSION = '1.370'; # NOTE - Should be #.### (three decimal places) | |||||||||||
| 9 | 203 | @ISA = qw(POE::Queue); | |||||||||||
| 10 | |||||||||||||
| 11 | 203 | ▶ | use Errno qw(ESRCH EPERM); | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 12 | 203 | ▶ | use Carp qw(confess); | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 13 | |||||||||||||
| 14 | sub DEBUG () { 0 } | ||||||||||||
| 15 | |||||||||||||
| 16 | ### Helpful offsets. | ||||||||||||
| 17 | |||||||||||||
| 18 | sub ITEM_PRIORITY () { 0 } | ||||||||||||
| 19 | sub ITEM_ID () { 1 } | ||||||||||||
| 20 | sub ITEM_PAYLOAD () { 2 } | ||||||||||||
| 21 | |||||||||||||
| 22 | 203 | ▶ | sub import { | ||||||||||
|
Subroutine
import: called CC=1 SCAR=0.0
| |||||||||||||
| 23 | 203 | my $package = caller(); | |||||||||||
| 24 | 203 | ▶ | no strict 'refs'; | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 25 | 203 | *{ $package . '::ITEM_PRIORITY' } = \&ITEM_PRIORITY; | |||||||||||
| 26 | 203 | *{ $package . '::ITEM_ID' } = \&ITEM_ID; | |||||||||||
| 27 | 203 | *{ $package . '::ITEM_PAYLOAD' } = \&ITEM_PAYLOAD; | |||||||||||
| 28 | } | ||||||||||||
| 29 | |||||||||||||
| 30 | # Item IDs are unique across all queues. | ||||||||||||
| 31 | |||||||||||||
| 32 | 203 | my $queue_seq = 0; | |||||||||||
| 33 | 203 | my %item_priority; | |||||||||||
| 34 | |||||||||||||
| 35 | ### A very simple constructor. | ||||||||||||
| 36 | |||||||||||||
| 37 | 201 | ▶ | sub new { | ||||||||||
|
Subroutine
new: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||
| 38 | 201 | bless [], shift(); | |||||||||||
| 39 | } | ||||||||||||
| 40 | |||||||||||||
| 41 | ### Add an item to the queue. Returns the new item's ID. | ||||||||||||
| 42 | |||||||||||||
| 43 | 7413 | ▶ | sub enqueue { | ||||||||||
|
Subroutine
enqueue: called CC=6 SCAR=17.9
Pod
documented
| |||||||||||||
| 44 | 7413 | my ($self, $priority, $payload) = @_; | |||||||||||
| 45 | |||||||||||||
| 46 | # Get the next item ID. This clever loop will hang indefinitely if | ||||||||||||
| 47 | # you ever run out of integers to store things under. Map the ID to | ||||||||||||
| 48 | # its due time for search-by-ID functions. | ||||||||||||
| 49 | |||||||||||||
| 50 | 7413 | my $item_id; | |||||||||||
| 51 | 7413 | ▶ | 1 while exists $item_priority{$item_id = ++$queue_seq}; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 52 | 7413 | $item_priority{$item_id} = $priority; | |||||||||||
| 53 | |||||||||||||
| 54 | 7413 | my $item_to_enqueue = [ | |||||||||||
| 55 | $priority, # ITEM_PRIORITY | ||||||||||||
| 56 | $item_id, # ITEM_ID | ||||||||||||
| 57 | $payload, # ITEM_PAYLOAD | ||||||||||||
| 58 | ]; | ||||||||||||
| 59 | |||||||||||||
| 60 | # Special case: No items in the queue. The queue IS the item. | ||||||||||||
| 61 | 7413 | ▶ | unless (@$self) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 62 | 1362 | $self->[0] = $item_to_enqueue; | |||||||||||
| 63 | 1362 | DEBUG and warn $self->_dump_splice(0); | |||||||||||
| 64 | 1362 | return $item_id; | |||||||||||
| 65 | } | ||||||||||||
| 66 | |||||||||||||
| 67 | # Special case: The new item belongs at the end of the queue. | ||||||||||||
| 68 | 6051 | ▶ | if ($priority >= $self->[-1]->[ITEM_PRIORITY]) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 69 | 1138 | push @$self, $item_to_enqueue; | |||||||||||
| 70 | 1138 | DEBUG and warn $self->_dump_splice(@$self-1); | |||||||||||
| 71 | 1138 | return $item_id; | |||||||||||
| 72 | } | ||||||||||||
| 73 | |||||||||||||
| 74 | # Special case: The new item belongs at the head of the queue. | ||||||||||||
| 75 | 4913 | ▶ | if ($priority < $self->[0]->[ITEM_PRIORITY]) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 76 | 610 | unshift @$self, $item_to_enqueue; | |||||||||||
| 77 | 610 | DEBUG and warn $self->_dump_splice(0); | |||||||||||
| 78 | 610 | return $item_id; | |||||||||||
| 79 | } | ||||||||||||
| 80 | |||||||||||||
| 81 | # Special case: There are only two items in the queue. This item | ||||||||||||
| 82 | # naturally belongs between them. | ||||||||||||
| 83 | 4303 | ▶ | if (@$self == 2) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 84 | 89 | splice @$self, 1, 0, $item_to_enqueue; | |||||||||||
| 85 | 89 | DEBUG and warn $self->_dump_splice(1); | |||||||||||
| 86 | 89 | return $item_id; | |||||||||||
| 87 | } | ||||||||||||
| 88 | |||||||||||||
| 89 | # And finally we have a nontrivial queue. Insert the item using a | ||||||||||||
| 90 | # binary seek. | ||||||||||||
| 91 | |||||||||||||
| 92 | 4214 | $self->_insert_item(0, $#$self, $priority, $item_to_enqueue); | |||||||||||
| 93 | 4214 | return $item_id; | |||||||||||
| 94 | } | ||||||||||||
| 95 | |||||||||||||
| 96 | ### Dequeue the next thing from the queue. Returns an empty list if | ||||||||||||
| 97 | ### the queue is empty. There are different flavors of this | ||||||||||||
| 98 | ### operation. | ||||||||||||
| 99 | |||||||||||||
| 100 | 5383 | ▶ | sub dequeue_next { | ||||||||||
|
Subroutine
dequeue_next: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||
| 101 | 5383 | my $self = shift; | |||||||||||
| 102 | |||||||||||||
| 103 | 5383 | ▶ | return unless @$self; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 104 | 5378 | my ($priority, $id, $stuff) = @{shift @$self}; | |||||||||||
| 105 | 5378 | delete $item_priority{$id}; | |||||||||||
| 106 | 5378 | return ($priority, $id, $stuff); | |||||||||||
| 107 | } | ||||||||||||
| 108 | |||||||||||||
| 109 | ### Return the next item's priority, undef if the queue is empty. | ||||||||||||
| 110 | # This is POE's most-called method. We could greatly benefit from | ||||||||||||
| 111 | # finding ways to reduce the number of calls. | ||||||||||||
| 112 | |||||||||||||
| 113 | 13940 | ▶ | sub get_next_priority { | ||||||||||
|
Subroutine
get_next_priority: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||
| 114 | # This is Ton Hospel's optimization. | ||||||||||||
| 115 | # He measured a 4% improvement by avoiding $self. | ||||||||||||
| 116 | 13940 | ▶ | return (shift->[0] || return undef)->[ITEM_PRIORITY]; | ||||||||||
|
Condition100%2/2
+(shift())->[0] || (return undef)
MC/DC100%1/1
+(shift())->[0] || (return undef)
+(shift())->[0]
Truth table100%2/2
A
A= +(shift())->[0]
| |||||||||||||
| 117 | } | ||||||||||||
| 118 | |||||||||||||
| 119 | ### Return the number of items currently in the queue. | ||||||||||||
| 120 | |||||||||||||
| 121 | 5457 | ▶ | sub get_item_count { | ||||||||||
|
Subroutine
get_item_count: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||
| 122 | 5457 | return scalar @{$_[0]}; | |||||||||||
| 123 | } | ||||||||||||
| 124 | |||||||||||||
| 125 | ### Internal method to insert an item using a binary seek and splice. | ||||||||||||
| 126 | ### We accept the bounds as parameters because the alarm adjustment | ||||||||||||
| 127 | ### functions may also use it. | ||||||||||||
| 128 | |||||||||||||
| 129 | 6190 | ▶ | sub _insert_item { | ||||||||||
|
Subroutine
_insert_item: called CC=3 SCAR=11.0
| |||||||||||||
| 130 | 6190 | my ($self, $lower, $upper, $priority, $item) = @_; | |||||||||||
| 131 | |||||||||||||
| 132 | 6190 | while (1) { | |||||||||||
| 133 | 54939 | my $midpoint = ($upper + $lower) >> 1; | |||||||||||
| 134 | |||||||||||||
| 135 | # Upper and lower bounds crossed. Insert at the lower point. | ||||||||||||
| 136 | 54939 | ▶ | if ($upper < $lower) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 137 | 6190 | splice @$self, $lower, 0, $item; | |||||||||||
| 138 | 6190 | DEBUG and warn $self->_dump_splice($lower); | |||||||||||
| 139 | 6190 | return; | |||||||||||
| 140 | } | ||||||||||||
| 141 | |||||||||||||
| 142 | # We're looking for a priority lower than the one at the midpoint. | ||||||||||||
| 143 | # Set the new upper point to just before the midpoint. | ||||||||||||
| 144 | 48749 | ▶ | if ($priority < $self->[$midpoint]->[ITEM_PRIORITY]) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 145 | 21900 | $upper = $midpoint - 1; | |||||||||||
| 146 | 21900 | next; | |||||||||||
| 147 | } | ||||||||||||
| 148 | |||||||||||||
| 149 | # We're looking for a priority greater or equal to the one at the | ||||||||||||
| 150 | # midpoint. The new lower bound is just after the midpoint. | ||||||||||||
| 151 | 26849 | $lower = $midpoint + 1; | |||||||||||
| 152 | } | ||||||||||||
| 153 | } | ||||||||||||
| 154 | |||||||||||||
| 155 | ### Internal method to find a queue item by its priority and ID. We | ||||||||||||
| 156 | ### assume the priority and ID have been verified already, so the item | ||||||||||||
| 157 | ### must exist. Returns the index of the item that matches the | ||||||||||||
| 158 | ### priority/ID pair. | ||||||||||||
| 159 | |||||||||||||
| 160 | 3764 | ▶ | sub _find_item { | ||||||||||
|
Subroutine
_find_item: called CC=5 SCAR=16.1
| |||||||||||||
| 161 | 3764 | my ($self, $id, $priority) = @_; | |||||||||||
| 162 | |||||||||||||
| 163 | # Use a binary seek. | ||||||||||||
| 164 | |||||||||||||
| 165 | 3764 | my $upper = $#$self; # Last index of @$self. | |||||||||||
| 166 | 3764 | my $lower = 0; | |||||||||||
| 167 | 3764 | while (1) { | |||||||||||
| 168 | 40111 | my $midpoint = ($upper + $lower) >> 1; | |||||||||||
| 169 | |||||||||||||
| 170 | # Upper and lower bounds crossed. The lower point is aimed at an | ||||||||||||
| 171 | # element with a priority higher than our target. | ||||||||||||
| 172 | 40111 | ▶ | last if $upper < $lower; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 173 | |||||||||||||
| 174 | # We're looking for a priority lower than the one at the midpoint. | ||||||||||||
| 175 | # Set the new upper point to just before the midpoint. | ||||||||||||
| 176 | 36347 | ▶ | if ($priority < $self->[$midpoint]->[ITEM_PRIORITY]) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 177 | 19201 | $upper = $midpoint - 1; | |||||||||||
| 178 | 19201 | next; | |||||||||||
| 179 | } | ||||||||||||
| 180 | |||||||||||||
| 181 | # We're looking for a priority greater or equal to the one at the | ||||||||||||
| 182 | # midpoint. The new lower bound is just after the midpoint. | ||||||||||||
| 183 | 17146 | $lower = $midpoint + 1; | |||||||||||
| 184 | } | ||||||||||||
| 185 | |||||||||||||
| 186 | # The lower index is pointing to an element with a priority higher | ||||||||||||
| 187 | # than our target. Scan backwards until we find the item with the | ||||||||||||
| 188 | # target ID. | ||||||||||||
| 189 | 3764 | ▶ | while ($lower-- >= 0) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 190 | 4177 | ▶ | return $lower if $self->[$lower]->[ITEM_ID] == $id; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 191 | } | ||||||||||||
| 192 | |||||||||||||
| 193 | 0 | die "should never get here... maybe the queue is out of order"; | |||||||||||
| 194 | } | ||||||||||||
| 195 | |||||||||||||
| 196 | ### Remove an item by its ID. Takes a coderef filter, too, for | ||||||||||||
| 197 | ### examining the payload to be sure it really wants to leave. Sets | ||||||||||||
| 198 | ### $! and returns undef on failure. | ||||||||||||
| 199 | |||||||||||||
| 200 | 234 | ▶ | sub remove_item { | ||||||||||
|
Subroutine
remove_item: called CC=3 SCAR=11.0
Pod
documented
| |||||||||||||
| 201 | 234 | my ($self, $id, $filter) = @_; | |||||||||||
| 202 | |||||||||||||
| 203 | 234 | my $priority = $item_priority{$id}; | |||||||||||
| 204 | 234 | ▶ | unless (defined $priority) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 205 | 2 | $! = ESRCH; | |||||||||||
| 206 | 2 | return; | |||||||||||
| 207 | } | ||||||||||||
| 208 | |||||||||||||
| 209 | # Find that darn item. | ||||||||||||
| 210 | 232 | my $item_index = $self->_find_item($id, $priority); | |||||||||||
| 211 | |||||||||||||
| 212 | # Test the item against the filter. | ||||||||||||
| 213 | 232 | ▶ | unless ($filter->($self->[$item_index]->[ITEM_PAYLOAD])) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 214 | 1 | $! = EPERM; | |||||||||||
| 215 | 1 | return; | |||||||||||
| 216 | } | ||||||||||||
| 217 | |||||||||||||
| 218 | # Remove the item, and return it. | ||||||||||||
| 219 | 231 | delete $item_priority{$id}; | |||||||||||
| 220 | 231 | return @{splice @$self, $item_index, 1}; | |||||||||||
| 221 | } | ||||||||||||
| 222 | |||||||||||||
| 223 | ### Remove items matching a filter. Regrettably, this must scan the | ||||||||||||
| 224 | ### entire queue. An optional count limits the number of items to | ||||||||||||
| 225 | ### remove, and it may shorten execution times. Returns a list of | ||||||||||||
| 226 | ### references to priority/id/payload lists. This is intended to | ||||||||||||
| 227 | ### return all the items matching the filter, and the function's | ||||||||||||
| 228 | ### behavior is undefined when $count is less than the number of | ||||||||||||
| 229 | ### matching items. | ||||||||||||
| 230 | |||||||||||||
| 231 | 4644 | ▶ | sub remove_items { | ||||||||||
|
Subroutine
remove_items: called CC=5 SCAR=16.1
Pod
documented
| |||||||||||||
| 232 | 4644 | my ($self, $filter, $count) = @_; | |||||||||||
| 233 | 4644 | ▶ | $count = @$self unless $count; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 234 | |||||||||||||
| 235 | 4644 | my @items; | |||||||||||
| 236 | 4644 | my $i = @$self; | |||||||||||
| 237 | 4644 | ▶ | while ($i--) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 238 | 800680 | ▶ | if ($filter->($self->[$i]->[ITEM_PAYLOAD])) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 239 | 1642 | my $removed_item = splice(@$self, $i, 1); | |||||||||||
| 240 | 1642 | delete $item_priority{$removed_item->[ITEM_ID]}; | |||||||||||
| 241 | 1642 | unshift @items, $removed_item; | |||||||||||
| 242 | 1642 | ▶ | last unless --$count; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 243 | } | ||||||||||||
| 244 | } | ||||||||||||
| 245 | |||||||||||||
| 246 | 4644 | return @items; | |||||||||||
| 247 | } | ||||||||||||
| 248 | |||||||||||||
| 249 | ### Adjust the priority of an item by a relative amount. Adds $delta | ||||||||||||
| 250 | ### to the priority of the $id'd object (if it matches $filter), and | ||||||||||||
| 251 | ### moves it in the queue. | ||||||||||||
| 252 | |||||||||||||
| 253 | 2032 | ▶ | sub adjust_priority { | ||||||||||
|
Subroutine
adjust_priority: called CC=4 SCAR=14.2
Pod
documented
| |||||||||||||
| 254 | 2032 | my ($self, $id, $filter, $delta) = @_; | |||||||||||
| 255 | |||||||||||||
| 256 | 2032 | my $old_priority = $item_priority{$id}; | |||||||||||
| 257 | 2032 | ▶ | unless (defined $old_priority) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 258 | 0 | $! = ESRCH; | |||||||||||
| 259 | 0 | return; | |||||||||||
| 260 | } | ||||||||||||
| 261 | |||||||||||||
| 262 | # Find that darn item. | ||||||||||||
| 263 | 2032 | my $item_index = $self->_find_item($id, $old_priority); | |||||||||||
| 264 | |||||||||||||
| 265 | # Test the item against the filter. | ||||||||||||
| 266 | 2032 | ▶ | unless ($filter->($self->[$item_index]->[ITEM_PAYLOAD])) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 267 | 1000 | $! = EPERM; | |||||||||||
| 268 | 1000 | return; | |||||||||||
| 269 | } | ||||||||||||
| 270 | |||||||||||||
| 271 | # Nothing to do if the delta is zero. | ||||||||||||
| 272 | # TODO Actually we may need to ensure that the item is moved to the | ||||||||||||
| 273 | # end of its current priority bucket, since it should have "moved". | ||||||||||||
| 274 | 1032 | ▶ | return $self->[$item_index]->[ITEM_PRIORITY] unless $delta; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 275 | |||||||||||||
| 276 | # Remove the item, and adjust its priority. | ||||||||||||
| 277 | 1032 | my $item = splice(@$self, $item_index, 1); | |||||||||||
| 278 | 1032 | my $new_priority = $item->[ITEM_PRIORITY] += $delta; | |||||||||||
| 279 | 1032 | $item_priority{$id} = $new_priority; | |||||||||||
| 280 | |||||||||||||
| 281 | 1032 | $self->_reinsert_item($new_priority, $delta, $item_index, $item); | |||||||||||
| 282 | } | ||||||||||||
| 283 | |||||||||||||
| 284 | ### Set the priority to a specific amount. Replaces the item's | ||||||||||||
| 285 | ### priority with $new_priority (if it matches $filter), and moves it | ||||||||||||
| 286 | ### to the new location in the queue. | ||||||||||||
| 287 | |||||||||||||
| 288 | 2000 | ▶ | sub set_priority { | ||||||||||
|
Subroutine
set_priority: called CC=4 SCAR=14.0
Pod
documented
| |||||||||||||
| 289 | 2000 | my ($self, $id, $filter, $new_priority) = @_; | |||||||||||
| 290 | |||||||||||||
| 291 | 2000 | my $old_priority = $item_priority{$id}; | |||||||||||
| 292 | 2000 | ▶ | unless (defined $old_priority) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 293 | 0 | $! = ESRCH; | |||||||||||
| 294 | 0 | return; | |||||||||||
| 295 | } | ||||||||||||
| 296 | |||||||||||||
| 297 | # Nothing to do if the old and new priorities match. | ||||||||||||
| 298 | # TODO Actually we may need to ensure that the item is moved to the | ||||||||||||
| 299 | # end of its current priority bucket, since it should have "moved". | ||||||||||||
| 300 | 2000 | ▶ | return $new_priority if $new_priority == $old_priority; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 301 | |||||||||||||
| 302 | # Find that darn item. | ||||||||||||
| 303 | 1500 | my $item_index = $self->_find_item($id, $old_priority); | |||||||||||
| 304 | |||||||||||||
| 305 | # Test the item against the filter. | ||||||||||||
| 306 | 1500 | ▶ | unless ($filter->($self->[$item_index]->[ITEM_PAYLOAD])) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 307 | 500 | $! = EPERM; | |||||||||||
| 308 | 500 | return; | |||||||||||
| 309 | } | ||||||||||||
| 310 | |||||||||||||
| 311 | # Remove the item, and calculate the delta. | ||||||||||||
| 312 | 1000 | my $item = splice(@$self, $item_index, 1); | |||||||||||
| 313 | 1000 | my $delta = $new_priority - $old_priority; | |||||||||||
| 314 | 1000 | $item->[ITEM_PRIORITY] = $item_priority{$id} = $new_priority; | |||||||||||
| 315 | |||||||||||||
| 316 | 1000 | $self->_reinsert_item($new_priority, $delta, $item_index, $item); | |||||||||||
| 317 | } | ||||||||||||
| 318 | |||||||||||||
| 319 | ### Sanity-check the results of an item insert. Verify that it | ||||||||||||
| 320 | ### belongs where it was put. Only called during debugging. | ||||||||||||
| 321 | |||||||||||||
| 322 | 0 | ▶ | sub _dump_splice { | ||||||||||
|
Subroutine
_dump_splice: not called CC=5 SCAR=34.0
| |||||||||||||
| 323 | 0 | my ($self, $index) = @_; | |||||||||||
| 324 | 0 | my @return; | |||||||||||
| 325 | 0 | my $at = $self->[$index]->[ITEM_PRIORITY]; | |||||||||||
| 326 | 0 | ▶ | if ($index > 0) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 327 | 0 | my $before = $self->[$index-1]->[ITEM_PRIORITY]; | |||||||||||
| 328 | 0 | push @return, "before($before)"; | |||||||||||
| 329 | 0 | ▶ | confess "out of order: $before should be < $at" if $before > $at; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 330 | } | ||||||||||||
| 331 | 0 | push @return, "at($at)"; | |||||||||||
| 332 | 0 | ▶ | if ($index < $#$self) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 333 | 0 | my $after = $self->[$index+1]->[ITEM_PRIORITY]; | |||||||||||
| 334 | 0 | push @return, "after($after)"; | |||||||||||
| 335 | 0 | my @priorities = map {$_->[ITEM_PRIORITY]} @$self; | |||||||||||
| 336 | 0 | ▶ | confess "out of order: $at should be < $after (@priorities)" if ( | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 337 | $at >= $after | ||||||||||||
| 338 | ); | ||||||||||||
| 339 | } | ||||||||||||
| 340 | 0 | return "@return"; | |||||||||||
| 341 | } | ||||||||||||
| 342 | |||||||||||||
| 343 | ### Reinsert an item into the queue. It has just been removed by | ||||||||||||
| 344 | ### adjust_priority() or set_priority() and needs to be replaced. | ||||||||||||
| 345 | ### This tries to be clever by not doing more work than necessary. | ||||||||||||
| 346 | |||||||||||||
| 347 | 2032 | ▶ | sub _reinsert_item { | ||||||||||
|
Subroutine
_reinsert_item: called CC=6 SCAR=18.6
| |||||||||||||
| 348 | 2032 | my ($self, $new_priority, $delta, $item_index, $item) = @_; | |||||||||||
| 349 | |||||||||||||
| 350 | # Now insert it back. | ||||||||||||
| 351 | # The special cases are duplicates from enqueue(). We use the delta | ||||||||||||
| 352 | # (direction) of the move and the old item index to narrow down the | ||||||||||||
| 353 | # subsequent nontrivial insert if none of the special cases apply. | ||||||||||||
| 354 | |||||||||||||
| 355 | # Special case: No events in the queue. The queue IS the item. | ||||||||||||
| 356 | 2032 | ▶ | unless (@$self) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 357 | 0 | $self->[0] = $item; | |||||||||||
| 358 | 0 | DEBUG and warn $self->_dump_splice(0); | |||||||||||
| 359 | 0 | return $new_priority; | |||||||||||
| 360 | } | ||||||||||||
| 361 | |||||||||||||
| 362 | # Special case: The item belongs at the end of the queue. | ||||||||||||
| 363 | 2032 | ▶ | if ($new_priority >= $self->[-1]->[ITEM_PRIORITY]) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 364 | 40 | push @$self, $item; | |||||||||||
| 365 | 40 | DEBUG and warn $self->_dump_splice(@$self-1); | |||||||||||
| 366 | 40 | return $new_priority; | |||||||||||
| 367 | } | ||||||||||||
| 368 | |||||||||||||
| 369 | # Special case: The item belongs at the head of the queue. | ||||||||||||
| 370 | 1992 | ▶ | if ($new_priority < $self->[0]->[ITEM_PRIORITY]) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 371 | 16 | unshift @$self, $item; | |||||||||||
| 372 | 16 | DEBUG and warn $self->_dump_splice(0); | |||||||||||
| 373 | 16 | return $new_priority; | |||||||||||
| 374 | } | ||||||||||||
| 375 | |||||||||||||
| 376 | # Special case: There are only two items in the queue. This item | ||||||||||||
| 377 | # naturally belongs between them. | ||||||||||||
| 378 | |||||||||||||
| 379 | 1976 | ▶ | if (@$self == 2) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 380 | 0 | splice @$self, 1, 0, $item; | |||||||||||
| 381 | 0 | DEBUG and warn $self->_dump_splice(1); | |||||||||||
| 382 | 0 | return $new_priority; | |||||||||||
| 383 | } | ||||||||||||
| 384 | |||||||||||||
| 385 | # The item has moved towards an end of the queue, but there are a | ||||||||||||
| 386 | # lot of items into which it may be inserted. We'll binary seek. | ||||||||||||
| 387 | |||||||||||||
| 388 | 1976 | my ($upper, $lower); | |||||||||||
| 389 | 1976 | ▶ | if ($delta > 0) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 390 | 1475 | $upper = $#$self; # Last index in @$self. | |||||||||||
| 391 | 1475 | $lower = $item_index; | |||||||||||
| 392 | } | ||||||||||||
| 393 | else { | ||||||||||||
| 394 | 501 | $upper = $item_index; | |||||||||||
| 395 | 501 | $lower = 0; | |||||||||||
| 396 | } | ||||||||||||
| 397 | |||||||||||||
| 398 | 1976 | $self->_insert_item($lower, $upper, $new_priority, $item); | |||||||||||
| 399 | 1976 | return $new_priority; | |||||||||||
| 400 | } | ||||||||||||
| 401 | |||||||||||||
| 402 | ### Peek at items that match a filter. Returns a list of payloads | ||||||||||||
| 403 | ### that match the supplied coderef. | ||||||||||||
| 404 | |||||||||||||
| 405 | 1229 | ▶ | sub peek_items { | ||||||||||
|
Subroutine
peek_items: called CC=5 SCAR=16.1
Pod
documented
| |||||||||||||
| 406 | 1229 | my ($self, $filter, $count) = @_; | |||||||||||
| 407 | 1229 | ▶ | $count = @$self unless $count; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 408 | |||||||||||||
| 409 | 1229 | my @items; | |||||||||||
| 410 | 1229 | my $i = @$self; | |||||||||||
| 411 | 1229 | ▶ | while ($i--) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 412 | 6166 | ▶ | if ($filter->($self->[$i]->[ITEM_PAYLOAD])) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 413 | 5901 | unshift @items, $self->[$i]; | |||||||||||
| 414 | 5901 | ▶ | last unless --$count; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 415 | } | ||||||||||||
| 416 | } | ||||||||||||
| 417 | |||||||||||||
| 418 | 1229 | return @items; | |||||||||||
| 419 | } | ||||||||||||
| 420 | |||||||||||||
| 421 | 203 | 1; | |||||||||||
| 422 | |||||||||||||
| 423 | __END__ | ||||||||||||