#!/usr/bin/env perl
use strict;
use warnings;

use File::Map qw/map_anonymous unmap/;
use MCE::Flow;
use MCE::Candy;

my $size = shift || 1e6;

$size = 1e6 if $size < 1e6;  # minimum
$size = 1e9 if $size > 1e9;  # maximum

map_anonymous my $cache, $size * 2, 'shared';

# init cache with -1's, then set 0, 1, 2
substr($cache, 0, $size * 2, ( my $neg1 = pack('s', -1) ) x $size);
substr($cache, $_ * 2, 2, pack('s', $_)) for 0..2;

# local to workers and the manager process
my @seqs;

sub collatz_seq {
    my ( $seq_beg, $seq_end ) = @_;
    my ( $n, $steps, $tmp );
    for my $input ( $seq_beg..$seq_end ) {
        $n = $input, $steps = 0;
        while ( $n != 1 ) {
            $steps += unpack('s', $tmp), last
                if ($n < $size && ($tmp = substr($cache, $n * 2, 2)) ne $neg1);

            $n % 2 ? ( $steps += 2, $n = (3 * $n + 1) >> 1 )
                   : ( $steps += 1, $n = $n >> 1 );
        }
        substr($cache, $input * 2, 2, pack('s', $steps)) if $input < $size;
        push @seqs, [ $input, $steps ] if $steps > 400;
    }
}

my $chunk_size;

$chunk_size  = int( $size / MCE::Util::get_ncpu() / 80 + 1 );
$chunk_size += 1 if $chunk_size % 2;

mce_flow_s {
    max_workers => MCE::Util::get_ncpu(),
    chunk_size  => $chunk_size,
    bounds_only => 1,
    gather      => MCE::Candy::out_iter_array(\@seqs),
}, sub {
    my ($mce, $chunk_ref, $chunk_id) = @_;
    collatz_seq(@{ $chunk_ref });
    @seqs > 20
        ? MCE->gather($chunk_id, ( sort { $b->[1] <=> $a->[1] } @seqs )[ 0..19 ])
        : MCE->gather($chunk_id, @seqs);
    @seqs = ();
}, 2, $size;

MCE::Flow->finish; unmap $cache;
@seqs = ( sort { $b->[1] <=> $a->[1]} @seqs )[ 0..19 ];

printf "Collatz(%5d) has sequence length of %3d steps\n", @$_
    for @seqs;