Re: Data Structure needed for Event Queue

[jarich]

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