Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re: Data Structure needed for Event Queue

by jarich (Curate)
on May 28, 2002 at 05:10 UTC ( #169706=note: print w/ replies, xml ) Need Help??


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:

  • 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


Comment on Re: Data Structure needed for Event Queue
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://169706]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (5)
As of 2014-09-03 00:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite cookbook is:










    Results (34 votes), past polls