You could always just shove it into a database with an index. {grin}
I'm not a CS expert, but I think a B-tree might be the right structure (see http://perl.plover.com/BTree/). Pure Perl
B-Tree managers are available, such as Tree and Btrees. I think even a Berkeley DB can be stored "in core"
with the BerkeleyDB module, and there's a B-Tree version of that.
-- Randal L. Schwartz, Perl hacker
update:
yes, with DB_File, you can set up an in-memory DB (use undef for the filename), and with the right comparison callback, you get basic operations like
## add a new $nextevent at $time:
push @{$db{$time}}, $nextevent;
## get the lowest event list
keys %db; # reset pointer
my ($time, $events) = each %db; # lowest events
| [reply]
[d/l] |
| [reply] |
Like a number of others in the monastery, I would suggest you not use Heap. This may be one of those rare cases where it's faster and more reliable to write and debug your own version than go to CPAN. Alternatively,
the authors of "Elements of Programming with Perl" have been kind enough to put a kinder, gentler implementation on the web.
I haven't tested it, but it's at least simple enough that it's possible to read and understand the code, and relatively painless to use it.
/s
| [reply] |
| [reply] |
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 | [reply]
[d/l]
[select] |
Have you considered using Event instead of rolling your own?
MeowChow
s aamecha.s a..a\u$&owag.print | [reply] |
A Heap as a priority queue.
| [reply] |
