#!/usr/bin/perl -w

# Copyright 2014 Kevin Ryde

# This file is part of Math-NumSeq.
#
# Math-NumSeq is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by the
# Free Software Foundation; either version 3, or (at your option) any later
# version.
#
# Math-NumSeq is distributed in the hope that it will be useful, but
# WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
# or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
# for more details.
#
# You should have received a copy of the GNU General Public License along
# with Math-NumSeq.  If not, see <http://www.gnu.org/licenses/>.

use 5.010;
use strict;
use warnings;
use POSIX;
use List::Util 'max','min';
use Math::NumSeq::Fibonacci;
use Math::NumSeq::FibonacciRepresentations;

# uncomment this to run the ### lines
# use Smart::Comments;

{
  # print array by rows

  my $seq = Math::NumSeq::FibonacciRepresentations->new;
  my ($v0,$v1) = $seq->ith_pair(12);
  print "ith_pair  $v0  $v1\n";
  exit 0;
}
{
  # print array by rows

  my $depth = 10;

  my $fib = Math::NumSeq::Fibonacci->new;
  my $diatomic = Math::NumSeq::FibonacciRepresentations->new;

  my $width = $fib->ith($depth);
  foreach my $y (1 .. $depth) {
    my $i_lo = $fib->ith($y)-1;
    my $i_hi = $fib->ith($y+1)-1;
    foreach my $i ($i_lo .. $i_hi) {
      my $r = $diatomic->ith($i);
      printf "%1d ",$r;
    }
    print "      i=$i_lo to $i_hi\n";
  }
  exit 0;

  # 1                                         1
  # 1                    2                    1
  # 1               2         2               1
  # 1       3       2         2       3       1
  # 1     3   3     2    4    2     3   3     1
  # 1  4  3   3  5  2   4 4   2  5  3   3  4  1
  # 1 4 4 3 6 3 5 5 2 6 4 4 6 2 5 5 3 6 3 4 4 1

  # 1 5 4 4 7 3 6 6 3 8 5 5 7 2 6 6 4 8 4 6 6 2 7 5 5 8 3 6 6 3 7 4 4 5 1

}
{
  # vs A000119
  require Math::NumSeq::Fibbinary;
  require Math::NumSeq::OEIS::File;
  my $zeck = Math::NumSeq::Fibbinary->new;
  my $diatomic = Math::NumSeq::FibonacciRepresentations->new;
  my $oeis = Math::NumSeq::OEIS::File->new(anum=>'A000119');
  foreach my $i (0 .. 3) {
    my $z = $zeck->ith($i);
    my $got = $diatomic->ith($i);
    my $want = $oeis->ith($i);
    my $diff = ($got == $want ? '' : '  ***');
    printf "i=%2d z=%8b  $want $got$diff\n",
      $i, $z;
  }
  exit 0;
}
{
  # R(i) and R(i+1)

  # 0-bit
  # down_r = r0+r1 when z1 = z-1 has low 1-zeck
  # which is z even trailing zero bits
  #
  # 1-bit
  # down_r unchanged always
  # down_r1

  # 4 = 101
  # r     = 1   R(1) = 1
  # rsub1 = 0   R(0) = 1
  #
  # 0-bit, even trailing, no change
  # r     = 10  R(2) = 1
  # rsub1 =  1  R(1) = 1
  #
  # r     = 101  R(4) = 1
  # rsub1 = 100  R(3) = 2

  # 16 = 100100
  # r     = 1   R(1) = 1
  # rsub1 = 0   R(0) = 1
  #
  # r     = 10   R(2) = 1
  # rsub1 =  1   R(1) = 1
  #
  # r     = 100  R(3) = 2
  # rsub1 =  10  R(2) = 1
  #
  # r     = 1001  R(6) = 2
  # rsub1 = 1000  R(5) = 2

  # 3 = 100
  # r      = 0   R(0) = 1
  # rplus1 = 1   R(1) = 1
  #
  # r      =  1   R(1) = 1
  # rplus1 = 10   R(2) = 1
  #
  # r      =  10  R(2) = 1
  # rplus1 = 100  R(3) = 2
  #
  # r      = 100  R(3) = 2
  # rplus1 = 101  R(4) = 1
  #
  #   001   0010  00101  001010   0010101   
  #   010   0100  01000  010000   0100000   trailing zeros
  #   odd   even   odd    even     odd
  # 10 is 00 in i+1 at low end, but no change above low

  require Math::NumSeq::Fibbinary;
  require Math::NumSeq::OEIS::File;
  my $zeck = Math::NumSeq::Fibbinary->new;
  my $fib = Math::NumSeq::Fibonacci->new;
  my $diatomic = Math::NumSeq::OEIS::File->new(anum=>'A000119');
  # my $diatomic = Math::NumSeq::FibonacciRepresentations->new;

  $fib->next;
  $fib->next;
  (undef, my $target) = $fib->next;
  my $delta = -1;
  my %saw_types;
  for my $i (1 .. $fib->ith(14)) {
    if ($i >= $target) {
      print "\n";
      (undef, $target) = $fib->next;
    }
    my $i1 = $i + $delta;
    my $z = $zeck->ith($i);
    my $z1 = $zeck->ith($i1);
    my $r0 = $diatomic->ith($i);
    my $r1 = $diatomic->ith($i1);

    foreach my $bit (0,
                     # ($z & 1) ? () : (1)
                    ) {
      my $down_z = 2*$z + $bit;
      my $down_i = $zeck->value_to_i($down_z) // die;
      my $down_r = $diatomic->ith($down_i);
      my $down_i1 = $down_i + $delta;
      my $down_r1 = $diatomic->ith($down_i1);
      my $down_z1 = $zeck->ith($down_i1);

      my $down_type = '?';
      if ($down_r == $r0 && $down_r == $r1) {
        $down_type = 'r0=r1';
      } elsif ($down_r == $r0) {
        $down_type = 'r0';
      } elsif ($down_r == $r1) {
        $down_type = 'r1';
      } elsif ($down_r == $r0 + $r1) {
        $down_type = 'r0 + r1';
      }

      my $down_type1 = '?';
      if ($down_r1 == $r0 && $down_r1 == $r1) {
        $down_type1 = 'r0=r1';
      } elsif ($down_r1 == $r0) {
        $down_type1 = 'r0';
      } elsif ($down_r1 == $r1) {
        $down_type1 = 'r1';
      } elsif ($down_r1 == $r0 + $r1) {
        $down_type1 = 'r0 + r1';
      }

      my $star = ' ';;
      if ($bit == 0) {
        $star = (0 && end_10_p($z) && end_01_p($z1)
                 ? '*' : ' ');  # no ?
        $star = ($z1 & 1 ? '*' : ' '); # yes
        $star = (count_low_0_bits($z) & 1 ? '*' : ' '); # yes
      } else {
        # $star = ($z & 1 ? '*' : ' ');
        $star = (count_low_0_bits($z) & 1 ? '*' : ' ');
      }
      my $bad = ($bit == 0 && ($star eq '*') ne ($down_type eq 'r0 + r1') ? '  bad' : '');
      my $bad1 = ($bit == 1 && ($star eq '*') ne ($down_type1 eq 'r0 + r1') ? '  bad' : '');

      printf "z  %12b  $bit-bit\n", $z;
      printf "z1 %12b\n", $z1;
      printf "   %12b %-7s    %2d %2d -> %2d $star $bad\n",
        $down_z, $down_type, $r0, $r1, $down_r;
      printf "   %12b %-7s    %2d %2d -> %2d $star $bad1\n",
        $down_z1, $down_type1, $r0, $r1, $down_r1;
      print "\n";

      my $z_end = sprintf '%04b', $z & 0b1111;
      my $z1_end = sprintf '%04b', $z1 & 0b1111;
      $saw_types{$bit}->{'z-e'}->{$z_end}->{$down_type} = 1;
      $saw_types{$bit}->{'z1-e'}->{$z1_end}->{$down_type} = 1;
      $saw_types{$bit}->{'z-e1'}->{$z_end}->{$down_type1} = 1;
      $saw_types{$bit}->{'z1-e1'}->{$z1_end}->{$down_type1} = 1;
    }
  }
  # ### types: %saw_types

  exit 0;

  sub count_low_0_bits {
    my ($n) = @_;
    if ($n <= 0) {
      return 0;
    }
    my $count = 0;
    until ($n % 2) {
      $count++;
      $n /= 2;
    }
    return $count;
  }
}

{
  # zeck
  require Math::NumSeq::Fibbinary;
  my $zeck = Math::NumSeq::Fibbinary->new;
  my $fib = Math::NumSeq::Fibonacci->new;
  my $diatomic = Math::NumSeq::FibonacciRepresentations->new;

  $fib->next;
  $fib->next;
  (undef, my $target) = $fib->next;
  for my $i (1 .. $fib->ith(12)) {
    if ($i >= $target) {
      print "\n";
      (undef, $target) = $fib->next;
    }
    my $z = $zeck->ith($i);
    my $d = $diatomic->ith($i);
    my $z_next = $zeck->ith($i+1);
    my $z_prev = $zeck->ith($i-1);

    my $p = $z >> 1;
    my $pi = $zeck->value_to_i($p);
    my $pd = $diatomic->ith($pi);

    my $qi = $pi-1;                  # q at i-1
    my $q = $zeck->ith($qi);
    my $qd = $diatomic->ith($qi);

    my $which;
    if ($d == $pd) { $which = 'p'; }
    elsif ($d == $qd) { $which = 'q'; }
    elsif ($d == $pd + $qd) { $which = 'p+q'; }
    else { $which = ''; }

    my $star = ((! end_101_p($z_next) && end_101_p($z_prev))
                || (! end_101_p($z_prev) && end_101_p($z_next))
                ? '*'
                : ' ');
    $star = (end_1010_p($z_prev) || end_101_p($z_next)
             ? '*' : ' ');
    $star = (end_01_p($q)        # wrong
             ? '*' : ' ');
    $star = (end_10_p($p) && end_01_p($q)   # right for low 0-bit
             ? '*' : ' ');

    my $bad = (($star eq '*') ne ($which eq 'p+q') ? '  bad' : '');
    printf "%3d %8b%s %2d   %7b %2d %2d %7b  %-3s%s\n",
      $i, $z,$star, $d,
        $p, $pd, $qd, $q,
          $which, $bad;
  }
  exit 0;

  sub end_10_p {
    my ($n) = @_;
    return (($n & 0b11) == 0b10);
  }
  sub end_01_p {
    my ($n) = @_;
    return (($n & 0b11) == 0b01);
  }
  sub end_101_p {
    my ($n) = @_;
    return (($n & 0b111) == 0b101);
  }
  sub end_1010_p {
    my ($n) = @_;
    return (($n & 0b1111) == 0b1010);
  }

  #     101010010
  #     101010001
  #     101010010
  #
  #     101010000
  #     101010001
  # 138 1010100010   4     4  7   p
  # 139 1010100100*  8     4  4   p+q
  # 140 1010100101*  4     4  4 101010001  p    bad
  #
  #
  # 101010001
  # 1010100010
  # 101010010
  # 1010100100
  #
  # 101010001     *2+1
  # 1010100100
  # 101010010     *2+1
  # 1010100101
}