Re: [QUIZ] Perl 'Medium' Quiz of the Week #2005-05-06 - Ranges' Lookup

On Fri, May 06, 2005 at 11:16:36PM +0300, Shlomi Fish wrote:
> Well, the previous quiz did not seem to be very popular.

Nor this one :)

> $ret is a hash ref that should contain a field 'verdict' that is a boolean 
> specifying if any of the ranges contain $x. It may also contain 'match_set' 
> which points to a reference to a hash whose keys are the indexes of the 
> matching ranges.

I wonder why match_set would be a hash.  Oh well.

The really neat way to solve this would be to return a tied, lazy
verdict and match_set, that only do the work to the extent necessary,
but I opted for a simple solution instead.

I have the feeling that there's another optimization (other than
sorting by one of the endpoints) that doesn't depend on having some
clue about what kind of values are being dealt with, but couldn't
bring it to the top of my mind.

sub prepare_ranges_handle {
   [
      # copy incoming data, lest caller change it
      # and store as array of low value, high value, original index
      map [@{$_[$_]}[0,1], $_],
      # sort indicies by low value
      sort {$_[$a][0] <=> $_[$b][0]}
      0..$#_
   ]
}

sub lookup_ranges {
   my $ranges = shift;
   my $value = shift;
   my %result = ( verdict => !1, match_set => {} );
   for my $range (@$ranges) {
      # give up if all following ranges begin above $value
      last if $range->[0] > $value;
      # is it in range?
      if ($range->[1] >= $value) {
         $result{verdict} = 1;
         # record this range's original index as having matched
         undef ${$result{match_set}}{$range->[2]};
      }
   }
   \%result;
}

1;