sub qpush
{
my ($self, $time, $eventref) = @_;
push @{$self}, {time=>$time, event=>$eventref};
}
####
sub qpop
{
my ($self) = @_;
my $ref = pop @{$self};
return $ref->{event};
}
##
##
# 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;
}
}
}