Algorithm::BIT - http://d.hatena.ne.jp/naoya/20090606/1244284915
以下、全然そうする必要はなかったけど、敢えてMoose化をしてみた。なんとなく、例としてご参照ください。
ppackage Algorithm::BIT;
use Moose;
use MooseX::AttributeHelpers;
use namespace::clean -except => qw(meta);
has size => (
is => 'ro',
isa => 'Int',
required => 1,
);
has data => (
metaclass => 'Collection::Array',
is => 'ro',
isa => 'ArrayRef',
lazy_build => 1,
provides => {
get => 'data_get',
set => 'data_set',
}
);
sub _build_data {
my $self = shift;
return [ map { 0 } 1 .. $self->size ]
}
sub BUILDARGS {
my ($self, $n) = @_;
return { size => $n };
}
sub read {
my ($self, $idx) = @_;
if ($idx > $self->size) {
confess 'assert: index overflow';
}
my $sum = 0;
while ($idx > 0) {
use integer;
$sum += $self->data_get($idx);
$idx = $idx & $idx - 1;
}
return $sum;
}
sub update {
my ($self, $idx, $val) = @_;
my $max = $self->size;
while ($idx <= $max) {
use integer;
$self->data_set($idx, $self->data_get($idx) + $val);
$idx += ($idx & -$idx);
}
}
__PACKAGE__->meta->make_immutable;
1;
コメント