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};
  }
  [download]

  (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};
  }
  [download]

  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;
                }
        }
}
[download]

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

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.