File Coverage

blib/lib/Math/PlanePath/CellularRule57.pm

Criterion	Covered	Total	%
statement	141	154	91.5
branch	70	80	87.5
condition	17	18	94.4
subroutine	20	23	86.9
pod	6	6	100.0
total	254	281	90.3

# Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde

# This file is part of Math-PlanePath.
#
# Math-PlanePath 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-PlanePath 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-PlanePath.  If not, see .



package Math::PlanePath::CellularRule57;
use 5.004;
use strict;

use vars '$VERSION', '@ISA';
$VERSION = 127;
use Math::PlanePath;
@ISA = ('Math::PlanePath');
*_sqrtint = \&Math::PlanePath::_sqrtint;

use Math::PlanePath::Base::Generic
  'round_nearest';

use Math::PlanePath::CellularRule54;
*_rect_for_V = \&Math::PlanePath::CellularRule54::_rect_for_V;

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


use constant class_y_negative => 0;
use constant n_frac_discontinuity => .5;

use constant parameter_info_array =>
  [ { name        => 'mirror',
      display     => 'Mirror',
      type        => 'boolean',
      default     => 0,
      description => 'Mirror to "rule 99" instead.',
    },
    Math::PlanePath::Base::Generic::parameter_info_nstart1(),
  ];

sub x_negative_at_n {
  my ($self) = @_;
  return $self->n_start + ($self->{'mirror'} ? 1 : 2);
}
use constant sumxy_minimum => 0;  # triangular X>=-Y so X+Y>=0
use constant diffxy_maximum => 0; # triangular X<=Y so X-Y<=0
use constant dx_maximum => 3;
use constant dy_minimum => 0;
use constant dy_maximum => 1;

sub absdx_minimum {
  my ($self) = @_;
  return ($self->{'mirror'} ? 0 : 1);
}
use constant dsumxy_maximum => 3;  # straight East dX=+3
use constant ddiffxy_maximum => 3; # straight East dX=+3
use constant dir_maximum_dxdy => (-1,0); # supremum, West and dY=+1 up


#------------------------------------------------------------------------------

sub new {
  my $self = shift->SUPER::new (@_);
  if (! defined $self->{'n_start'}) {
    $self->{'n_start'} = $self->default_n_start;
  }
  return $self;
}

#            left
# even  y=3     5
#         5    12
#         7    23
#         9    38
# [1,2,3,4], [5,12,23,38]
#
# N = (2 d^2 + d + 2)
#   = (2*$d**2 + $d + 2)
#   = ((2*$d + 1)*$d + 2)
# d = -1/4 + sqrt(1/2 * $n + -15/16)
#   = (-1 + 4*sqrt(1/2 * $n + -15/16)) / 4
#   = (sqrt(8*$n-15)-1)/4
# with Y=2*d+1

# row 19, d=9
# N=173 to N=181 is 9 cells rem=0..8  is d-1
# 1/3 section 3 cells rem=0,1,2  floor((d-1)/3)
# 2/3 section 6 cells
# right solid N=191 to N=200 is 10 of is rem
#
# row 21, d=10
# 1/3 section 4 cells rem=0,1,2,3  floor((d-1)/3)
# 2/3 section 6 cells
#
# row 23, d=11
# 1/3 section 4 cells rem=0,1,2,3  floor((d-1)/3)
# 2/3 section 7 cells
#
# row 25, d=12
# 2/3 section 8 cells
#
# row 27, d=13
# 2/3 section 8 cells
#
# row 29, d=14
# 2/3 section 9 cells    floor(2d/3)
#
# row 31, d=15
# 2/3 section 10 cells   floor(2d/3)
#
#
# row 18 d=8
# odd 1/3 section   4 cells  (d+4)/3
#
# row 20 d=9
# odd 1/3 section   4 cells
#
# row 22 d=10
# odd 1/3 section   4 cells
#
# row 23 d=11
# odd 1/3 section   5 cells


sub n_to_xy {
  my ($self, $n) = @_;
  ### CellularRule57 n_to_xy(): $n

  $n = $n - $self->{'n_start'} + 1; # to N=1 basis, and warn if $n undef
  my $frac;
  {
    my $int = int($n);
    $frac = $n - $int;
    $n = $int;       # BigFloat int() gives BigInt, use that
    if (2*$frac >= 1) {
      $frac -= 1;
      $n += 1;
    }
    # -0.5 <= $frac < 0.5
    ### assert: 2*$frac >= -1
    ### assert: 2*$frac < 1
  }

  if ($n <= 1) {
    if ($n == 1) {
      return (0,0);
    } else {
      return;
    }
  }

  # d is the two-row group number, y=2*d+1, where n belongs
  #
  my $d = int( (_sqrtint(8*$n-15)-1)/4 );
  $n -= ((2*$d + 1)*$d + 2);   # remainder
  ### $d
  ### remainder: $n

  if ($self->{'mirror'}) {
    if ($n <= $d) {
      ### right solid: $n
      return ($frac + $n - 2*$d - 1,
              2*$d+1);
    }
    $n -= $d+1;

    if ($n < int(2*$d/3)) {
      ### right 2/3: $n
      return ($frac + int(3*$n/2) - $d + 1,
              2*$d+1);
    }
    $n -= int(2*$d/3);

    if ($n < int(($d+2)/3)) {
      ### left 1/3: $n
      return ($frac + 3*$n + ((2+$d)%3),
              2*$d+1);
    }
    $n -= int(($d+2)/3);

    if ($n < $d) {
      ### left solid: $n
      return ($frac + $n + $d+2,
              2*$d+1);
    }
    $n -= $d;

    if ($n < int((2*$d+5)/3)) {
      ### odd 2/3: $n
      return ($frac + int((3*$n)/2) - $d +  - 1,
              2*$d+2);
    }
    $n -= int((2*$d+5)/3);

    ### odd 1/3: $n
    return ($frac + 3*$n + ($d%3) + 1,
            2*$d+2);

  } else {
    if ($n < $d) {
      ### left solid: $n
      return ($frac + $n - 2*$d - 1,
              2*$d+1);
    }
    $n -= $d;

    if ($n < int(($d+2)/3)) {
      ### left 1/3: $n
      return ($frac + 3*$n - $d + 1,
              2*$d+1);
    }
    $n -= int(($d+2)/3);

    if ($n < int(2*$d/3)) {
      ### right 2/3: $n
      return ($frac + $n + int(($n+(-$d%3))/2) + 1,
              2*$d+1);
    }
    $n -= int(2*$d/3);

    if ($n <= $d) {
      ### right solid: $n
      return ($frac + $d + $n + 1,
              2*$d+1);
    }
    $n -= $d+1;

    if ($n < int(($d+4)/3)) {
      ### odd 1/3: $n
      return ($frac + 3*$n - $d - 1,
              2*$d+2);
    }
    $n -= int(($d+4)/3);

    ### odd 2/3: $n
    return ($frac + $n + int(($n+((1-$d)%3))/2) + 1,
            2*$d+2);
  }
}

sub xy_to_n {
  my ($self, $x, $y) = @_;
  $x = round_nearest ($x);
  $y = round_nearest ($y);
  ### CellularRule57 xy_to_n(): "$x,$y"

  if ($y < 0
      || $x < -$y
      || $x > $y) {
    ### outside pyramid region ...
    return undef;
  }

  if ($self->{'mirror'}) {
    # mirrored, rule 99

    if ($y % 2) {
      my $d = ($y+1)/2;
      ### odd row, solids, d: $d

      if ($x < -$d) {
        return ($y+1)*$y/2 + $x + 1 + $self->{'n_start'};
      }
      if ($x < 0) {
        ### mirror left 2 of 3 ...
        if (($x += $d+2) % 3) {
          return ($y+1)*$y/2 + $x-int($x/3) - $d + $self->{'n_start'} - 1;
        }
      } elsif ($x > $d) {
        return ($y+1)*$y/2 + $x - $d + $self->{'n_start'};
      } else {
        ### mirror right 1 of 3 ...
        $x += 2-$d;
        unless ($x % 3) {
          return ($y+1)*$y/2 + $x/3 + $self->{'n_start'};
        }
      }

    } else {
      ### even row, sparse ...
      my $d = $y/2;
      if ($x >= 0) {
        ### mirror sparse right 1 of 3 ...
        if ($x <= $d  # only to half way
            && (($x -= $d) % 3) == 0) {
          return ($y+1)*$y/2 + $x/3 + $self->{'n_start'};
        }
      } else { # $x < 0
        ### mirror sparse left 2 of 3 ...
        if ($x >= -$d  # only to half way
            && (($x += $d+1) % 3)) {
          return ($y+1)*$y/2 + $x-int($x/3) - $d + $self->{'n_start'} - 1;
        }
      }
    }
  } else {
    # unmirrored, rule 57

    if ($y % 2) {
      my $d = ($y+1)/2;
      ### odd row, solids, d: $d

      if ($x <= -$d) {
        ### solid left ...
        if ($x < -$d) {  # always skip the -$d cell
          return ($y+1)*$y/2 + $x + 1 + $self->{'n_start'};
        }
      } elsif ($x <= 0) {
        ### 1 of 3 ...
        unless (($x += $d+1) % 3) {
          return ($y+1)*$y/2 + $x/3 - $d + $self->{'n_start'};
        }
      } elsif ($x >= $d) {
        ### solid right ...
        return ($y+1)*$y/2 + $x - $d + $self->{'n_start'};
      } else {
        ### 2 of 3 ...
        $x += 1-$d;
        if ($x % 3) {
          return ($y+1)*$y/2 + $x-int($x/3) + $self->{'n_start'};
        }
      }

    } else {
      ### even row, sparse ...

      my $d = $y/2;
      if ($x > 0) {
        ### right 2 of 3 ...
        if ($x <= $d  # goes to half way only
            && (($x -= $d+1) % 3)) {
          return ($y+1)*$y/2 + $x-int($x/3) + 1 + $self->{'n_start'};
        }
      } else { # $x <= 0
        ### left 1 of 3 ...
        if (($x += $d) >= 0   # goes to half way only
            && ! ($x % 3)) {
          return ($y+1)*$y/2 + $x/3 - $d + $self->{'n_start'};
        }
      }
    }
  }
  return undef;
}

# left edge ((2*$d + 1)*$d + 2)
# where y=2*d+1
#       d=floor((y-1)/2)
# left N = (2*floor((y-1)/2) + 1)*floor((y-1)/2) + 2
#        = (yodd + 1)*yodd/2 + 2


# not exact
sub rect_to_n_range {
  my ($self, $x1,$y1, $x2,$y2) = @_;
  ### CellularRule57 rect_to_n_range(): "$x1,$y1, $x2,$y2"

  ($x1,$y1, $x2,$y2) = _rect_for_V ($x1,$y1, $x2,$y2)
    or return (1,0); # rect outside pyramid

  my $zero = ($x1 * 0 * $y1 * $x2 * $y2);  # inherit bignum

  $y1 -= ! ($y1 % 2);
  $y2 -= ! ($y2 % 2);
  return ($zero + ($y1 < 1
                   ? $self->{'n_start'}
                   : ($y1-1)*$y1/2 + 1 + $self->{'n_start'}),
          $zero + ($y2+2)*($y2+1)/2 + $self->{'n_start'});
}

1;
__END__