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:
(assuming you treat the queue as an object and it's underlying structure is an arrayref).sub qpush { my ($self, $time, $eventref) = @_; push @{$self}, {time=>$time, event=>$eventref}; } - $eventref = $queue->qpop(); No problem:
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.sub qpop { my ($self) = @_; my $ref = pop @{$self}; return $ref->{event}; }
Of course you might want an insert function as well, that's where binary searching would come in:
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.# 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; } } }
Hope this helps.
jarich
|
---|
In Section
Seekers of Perl Wisdom