#!/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);
}

##</code><code>##

Looking for the range 232, 339 in an array with 100 elements
FETCH (miss) 1: 49
FETCH (miss) 2: 74
FETCH (miss) 3: 62
FETCH (miss) 4: 56
FETCH (miss) 5: 53
FETCH (miss) 6: 55
FETCH (miss) 7: 87
FETCH (miss) 8: 81
FETCH (miss) 9: 84
FETCH (miss) 10: 86
FETCH (miss) 11: 85
FETCH (hit) 1: 86
Found indexes of 56, 86

##</code><code>##

use List::BinarySearch qw(binsearch_range);

foreach my $ix (0..99) {
    my @params = params($ix);
    push @array, MyClass->new(@params);
}

my ($low_ix, $high_ix) = binsearch_range { $a <=> $b->fetch } $min_wanted, $max_wanted, @array;

##</code><code>##

package MyClass;

sub new {
    my ($class, @parameters) = @_;
    return bless {params => \@parameters}, $class;
}

sub fetch {
    my $self = 
    return $self->{'cache'} //= do {
        sleep 1;
        warn "cache miss. Generating value...\n";
        _gen_value($self->{'params'}) #; Generate the expensive value and store it in the cache.
    };
}