package Data::MultiValued::RangeContainer;
use Moose;
use Moose::Util::TypeConstraints;
use MooseX::Types::Moose qw(Num Str Any Undef ArrayRef);
use MooseX::Types::Structured qw(Dict);
use Data::MultiValued::Exceptions;
has _storage => (
is => 'rw',
isa => ArrayRef[
Dict[
from => Num,
to => Num,
value => Any,
],
],
init_arg => undef,
default => sub { [ ] },
);
sub get {
my ($self,$args) = @_;
my $at = $args->{at} // 0-'inf';
my ($range) = $self->_get_slot_at($at);
if (!$range) {
Data::MultiValued::Exceptions::RangeNotFound->throw({
value => $at,
});
}
return $range;
}
sub _get_slot_at {
my ($self,$at) = @_;
for my $slot (@{$self->_storage}) {
next if $slot->{to} <= $at;
last if $slot->{from} > $at;
return $slot;
}
return;
}
sub _partition_slots {
my ($self,$from,$to) = @_;
my (@before,@overlap,@after);
my $st=$self->_storage;
keys @$st;
while (my ($idx,$slot) = each @$st) {
my ($sf,$st) = @$slot{'from','to'};
if ($st<$from) {
push @before,$idx;
}
elsif ($sf>=$to) {
push @after,$idx;
}
else {
push @overlap,$idx;
}
}
return \@before,\@overlap,\@after;
}
sub set_or_create {
my ($self,$args) = @_;
my $from = $args->{from} // 0-'inf';
my $to = $args->{to} // 0+'inf';
Data::MultiValued::Exceptions::BadRange->({
from => $from,
to => $to,
}) if $from > $to;
my ($range) = $self->_get_slot_at($from);
if ($range && $range->{from}==$from && $range->{to}==$to) {
return $range;
}
$range = $self->_create_slot($from,$to);
return $range;
}
sub _create_slot {
my ($self,$from,$to) = @_;
my $new = {
from => $from,
to => $to,
value => undef,
};
if (!@{$self->_storage}) {
push @{$self->_storage},$new;
return $new;
}
my ($before,$overlap,$after) = $self->_partition_slots($from,$to);
if (!@$before && !@$overlap) {
unshift @{$self->_storage},$new;
return $new;
}
if (!@$after && !@$overlap) {
push @{$self->_storage},$new;
return $new;
}
my $first_to_replace = $overlap->[0],
my $last_to_replace = $overlap->[-1],
my $how_many = @$overlap;
my @replacement = ($new);
if ($how_many > 0) {
my $first = $self->_storage->[$first_to_replace];
my $last = $self->_storage->[$last_to_replace];
if ($first->{from} < $from && $first->{to} >= $from) {
unshift @replacement, {
from => $first->{from},
to => $from,
value => $first->{value},
}
}
if ($last->{from} < $to && $last->{to} >= $to) {
push @replacement, {
from => $to,
to => $last->{to},
value => $last->{value},
}
}
}
splice @{$self->_storage},
$first_to_replace,$how_many,
@replacement;
return $new;
}
1;