#!/usr/bin/env perl

package MyArray;
use Tie::Array;
use strict;
use warnings;

our @ISA = qw(Tie::StdArray);

my %inside_out;
sub FETCH {
    my ($self, $index) = @_;
    if (!defined($inside_out{"$self"}->{'cache'}->[$index])) {
        my $count = ++$inside_out{"$self"}->{'cache_miss_count'};
        warn "FETCH (miss) $count: $index\n";
        sleep 1;
        $inside_out{"$self"}->{'cache'}->[$index] = $self->[$index];
    }
    else {
        my $count = ++$inside_out{"$self"}->{'cache_hit_count'};
        warn "FETCH (hit) $count: $index\n";
    }
    return $inside_out{"$self"}->{'cache'}->[$index];
}

1;

package main;

use strict;
use warnings;

use List::BinarySearch qw(binsearch);

my ($min_sample_index, $max_sample_index)
    = sort {$a <=> $b}
      map {int(rand(100))}
      (0,1); # Generate two random indices in low to high order.

my ($min_find_value, $max_find_value);

tie my @array, 'MyArray';

my $curr_value = 0;
foreach (1 .. 100) {
   $curr_value += int(rand(10));
   push @array, $curr_value;
   $min_find_value = $curr_value if $_ == $min_sample_index;
   $max_find_value = $curr_value if $_ == $max_sample_index;
}

print "Looking for the range $min_find_value, $max_find_value in an array with ", scalar(@array), " elements\n";

my ($min_found_ix, $max_found_ix) = binsearch_range($min_find_value, $max_find_value, @array);


print "Found indexes of $min_found_ix, $max_found_ix\n";

# This algorithm was taken from Mastering Algorithms with Perl, OReilly.
sub binsearch_range {
    my $min = shift;
    my $max = shift;
    my $min_found_ix = binsearch {$a <=> $b} $min, @_;
    my $max_found_ix = binsearch {$a <=> $b} $max, @_;
    if ($max_found_ix == scalar(@array) || ($array[$max_found_ix] <=> $max_find_value) > 0) {
        $max_found_ix--;
    }
    return($min_found_ix, $max_found_ix);
}