use strict;
use warnings;

use 5.014;
use List::Util  qw{ max };
use Time::HiRes qw{ gettimeofday tv_interval };

my $t0 = [ gettimeofday() ];
srand 1234567;

my $vec = q{};
vec( $vec, 536_870_911, 1 ) = 0;
vec( $vec, $_         , 1 ) = 1 for 1 .. 21143;
vec( $vec, int rand 536_870_911, 1 ) = 1 for 1 .. 1e7;

my $t1 = [ gettimeofday() ];
say qq{Creating vector - @{ [ tv_interval( $t0, $t1 ) ] }};

my $bitStr = unpack q{b*}, $vec;

my $t2 = [ gettimeofday() ];
say qq{Unpacking bitstring - @{ [ tv_interval( $t1, $t2 ) ] }};

say
   qq{Longest contiguous block of zeros is },
   max map length, $bitStr =~ m{(0+)}g,
   q{ bits long};

my $t3 = [ gettimeofday() ];
say qq{Finding longest block - @{ [ tv_interval( $t2, $t3 ) ] }};

say qq{\nSearch using regex};
for my $numZeros ( 25, 10, 78, 3, 943, 307, 5, 599, 19, 345 )
{
    my $ts = [ gettimeofday() ];

    say
       qq{At least $numZeros contiguous 0s },
       $bitStr =~ m{(0{$numZeros,})}
       ? qq{found at offset $-[ 0 ], length @{ [ length $1 ] }}
       : q{could not be found};

    say qq{     Search took - @{ [ tv_interval( $ts, [ gettimeofday() ] ) ] }};
}

say qq{\nSearch using index};
for my $numZeros ( 25, 10, 78, 3, 943, 307, 5, 599, 19, 345 )
{
    my $ts = [ gettimeofday() ];

    if ( $numZeros < 23 )
    {
        my $buffer   = q{};
        my $offset   = -1;
        my $bufStart = 0;
        my $lookFor  = q{0} x $numZeros;
        while ( $bufStart < length $vec )
        {
            $buffer = unpack q{b*}, substr $vec, $bufStart, 131;
            do {
               say
                  qq{At least $numZeros contiguous 0s found at },
                  $bufStart * 8 + $offset;
               last;
               } unless ( $offset = index $buffer, $lookFor ) == -1;

            $bufStart += 128;
        }
        say qq{At least $numZeros contiguous 0s could not be found}
           if $offset == -1;
    }
    else
    {
        my $wholeBytes      = int( ( $numZeros - 7 ) / 8 );
        my $lookFor         = qq{\0} x $wholeBytes;
        my $offset          = -1;
        my $zerosToTheLeft  = 0;
        my $zerosToTheRight = 0;

        while ( ( $offset = index $vec, $lookFor, $offset ) > -1 )
        {
            $zerosToTheLeft  = zerosToTheLeft( $offset );
            $zerosToTheRight = zerosToTheRight( $offset, $wholeBytes );
            last if ( $wholeBytes * 8 + $zerosToTheLeft + $zerosToTheRight )
               >= $numZeros;

            $offset += $wholeBytes;
        }

        if ( $offset == -1 )
        {
            say qq{At least $numZeros contiguous 0s could not be found};
        }
        else
        {
            say
               qq{At least $numZeros contiguous 0s found at },
               $offset * 8 - $zerosToTheLeft;
        }
    }

    say qq{     Search took - @{ [ tv_interval( $ts, [ gettimeofday() ] ) ] }};
}

sub zerosToTheLeft
{
    my $offset = shift;
    return 0 unless $offset;
    my $byteStr = unpack q{b*}, substr $vec, $offset - 1, 1;
    return 0 unless $byteStr =~ m{(0+)$};
    return length $1;
}

sub zerosToTheRight
{
    my( $offset, $wholeBytes ) = @_;
    return 0 if ( $offset + $wholeBytes ) == length $vec;
    my $byteStr = unpack q{b*}, substr $vec, $offset + $wholeBytes, 2;
    return 0 unless $byteStr =~ m{^(0+)};
    return length $1;
}