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:
- Events may be far apart. No problem.
- Events may be at the same time. No problem.
- $queue->qpush($time, $eventref) No problem:
sub qpush
{
my ($self, $time, $eventref) = @_;
push @{$self}, {time=>$time, event=>$eventref};
}
(assuming you treat the queue as an object and it's underlying structure is an arrayref).
- $eventref = $queue->qpop(); No problem:
sub qpop
{
my ($self) = @_;
my $ref = pop @{$self};
return $ref->{event};
}
Update:The astute will have spotted this, but that "pop" up there really ought to be a "shift". I won't change it, but if you use this code, hopefully you will.
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