Re (tilly) 1: Assemble times into ranges

[tilly]

I think a better data structure is the answer.

He should use DB_File with a BTREE and specify a custom sort order if it makes sense. In there he should put the times that he changes from inside to outside of any interval, and what he did. He can then use the OO interface, and use the seq method (with the R_CURSOR flag) to find the next action efficiently, and from that he can figure out his current state.

Here is example code demonstrating this that goes one step further. Note that the API I am coding to has some things I don't like (sorry, I don't like destructive methods) but I am more than willing to put up with it for the functionality provided:

#!/usr/bin/perl -w
use strict;
use DB_File;

# The original data structure
my %interval = qw(
  5     50
  20    30
  70    90
  120   130
);

# The times
my @times = qw(4 9 30 98 125 500);

# Let us rearrange the interval information
# into events consisting of a time/action.
my @events = map {[$_, 1]} keys %interval;
push @events, map {[$_, -1]} values %interval;

# Let us turn this array into something we can
# do a fast lookup on...

# First we need a useful comparison order:
$DB_BTREE->{'compare'} = sub {$_[0] <=> $_[1]};
# Next we need a hash to store information in
my %interval_end;
tie(
  %interval_end, 'DB_File', undef,
  O_RDWR|O_CREAT, 0640, $DB_BTREE
) or die "Cannot tie hash: $!";

# Now store the information.
my $nesting = 0;
foreach my $event (sort {$a->[0] <=> $b->[0]} @events) {
  my ($time, $action) = @$event;
  # Careful, multiple intervals may share a boundary...
  unless (exists $interval_end{$time}) {
    $interval_end{$time} = $nesting;
  }
  $nesting += $action;
}

# Now we get the tied object so we can do our fast lookup.
my $interval_depth = tied %interval_end;
# And now let us get our answers:
foreach my $time (@times) {
  my $ended = $time;
  my $depth = 0;
  $interval_depth->seq($ended, $depth, R_CURSOR);
  print "$time is in an interval ending at $ended of depth $depth\n";
}
__END__
Output:
4 is in an interval ending at 5 of depth 0
9 is in an interval ending at 20 of depth 1
30 is in an interval ending at 30 of depth 2
98 is in an interval ending at 120 of depth 0
125 is in an interval ending at 130 of depth 1
500 is in an interval ending at 500 of depth 0

Note that the final entry gave a somewhat non-intuitive answer. And there could be more error checking. Plus all intervals have been made open on the left and closed on the right. But oh well.

(This should be efficient on his original data set.)

UPDATE
There is more than a little irony in my pointing out the capabilities of BTrees to Dominus. The first place that I heard of them was this article. (Which I enjoyed quite a bit.)