view release on metacpan or  search on metacpan

lib/Statistics/Sampler/Multinomial/Indexed.pm  view on Meta::CPAN

package Statistics::Sampler::Multinomial::Indexed;

use 5.014;
use warnings;
use strict;

our $VERSION = '1.02';

use Carp;
use Ref::Util qw /is_arrayref/;
use List::Util 1.29 qw /min max sum pairmap/;
#use List::MoreUtils qw /first_index/;
use Scalar::Util qw /blessed looks_like_number/;

#use POSIX qw /ceil floor/;

use parent qw /Statistics::Sampler::Multinomial/;

sub new {
    my $pkg = shift;
    my $self = Statistics::Sampler::Multinomial->new(@_);
    bless $self, __PACKAGE__;
    
    $self->build_index;
    
    return $self;
}

sub _clone_inner {
    my $self = shift;
    #  parent class handles most details
    my $clone = $self->SUPER::_clone_inner;
    
    #  generate a dup of the index array-of-arrays
    $clone->{index} = [map {[@$_]} @{$self->{index}}];

    return $clone;
}


#  Build a tree based index of cumulative values.
#  This will help the single draw methods.
#  Idea from 
#  https://www.chiark.greenend.org.uk/~sgtatham/algorithms/cumulative.html
sub build_index {
    my $self = shift;
    my $data = $self->{data};

    #my $max_depth = 1 + logb (scalar @$data);
    my $max_depth = 1 + int (log (scalar @$data) / log (2));

    # each index entry contains the cumulative sum of its terminals
    # and each level is half the length of the one below 
    my @indexed;

    #  bottom is just the data
    $indexed[$max_depth] = $data;

    for my $level (reverse (0..$max_depth-1)) {
        my $pop;
        if (@{$indexed[$level+1]} % 2) {
            push @{$indexed[$level+1]}, 0;
            $pop = 1;
        }
        @{$indexed[$level]} = pairmap {($a//0)+($b//0)} @{$indexed[$level+1]};
        if ($pop) {
            pop @{$indexed[$level+1]};
        }
    }