in reply to Data Structure needed for Event Queue

How about an array of hashes? Each search could then be done using a binary search (if you need to search), each pop is a pop, each push is a push (or if you're perverse a shift and an unshift). Your hash would of course contain your timestamp and eventref.

Looking at your requirements:

Of course you might want an insert function as well, that's where binary searching would come in:

# to call it: $queue->qinsert($time, $eventref); # implementation sub qinsert { my ($self, $time, $eventref) = @_; unless (@{$self} > 0) { return $self->qpush($time, $eventref); } my $bot = 0; my $top = @$self - 1; my $mid = int (@{$self} / 2); while(1) { # put it before this bottom place if($time < $self->[$bot]{time}) { my @new = (@$self[0..($bot-1)], {time=>$time, event=>$eventref}, @$self[$bot..(@$self -1)] ); @{$self} = @new; return; } # put it after the top place elsif($time > $self->[$top]{time}) { my @new = (@$self[0..$top], {time=>$time, event=>$eventref}, @$self[($top+1)..(@$self - 1)] ); @{$self} = @new; return; } # put it in the middle here elsif($top - $bot == 1) { my @new = (@$self[0..$bot], {time=>$time, event=>$eventref}, @$self[$top..(@$self-1)] ); @{$self} = @new; return; } # else it's somewhere between my $mid = int(($top - $bot)/2 + $bot); if($time < $self->[$mid]{time}) { $top = $mid; } else { $bot = $mid; } } }
Of course the implementation can always be different too. :) I've only ever writen a binary search/insert in C and I can tell that it shows.

Hope this helps.

jarich