File Coverage

blib/lib/Math/PlanePath/StaircaseAlternating.pm

Criterion	Covered	Total	%
statement	115	134	85.8
branch	51	64	79.6
condition	46	50	92.0
subroutine	17	21	80.9
pod	7	7	100.0
total	236	276	85.5

# Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019 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 .



# math-image --path=StaircaseAlternating --all --output=numbers_dash --size=70x30
# math-image --path=StaircaseAlternating,end_type=square --all --output=numbers_dash --size=70x30

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

use vars '$VERSION', '@ISA';
$VERSION = 128;
use Math::PlanePath;
@ISA = ('Math::PlanePath');

use Math::PlanePath::Base::Generic
  'round_nearest';
use Math::PlanePath::Base::NSEW;
*_sqrtint = \&Math::PlanePath::_sqrtint;

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


use constant class_x_negative => 0;
use constant class_y_negative => 0;

my %n_frac_discontinuity = (jump => .5);
sub n_frac_discontinuity {
  my ($self) = @_;
  return $n_frac_discontinuity{$self->{'end_type'}};
}

use constant parameter_info_array =>
  [ { name      => 'end_type',
      share_key => 'end_type_jumpsquare',
      display   => 'Type',
      type      => 'enum',
      default   => 'jump',
      choices         => ['jump','square'],
      choices_display => ['Jump','Wquare'],
    },
    Math::PlanePath::Base::Generic::parameter_info_nstart1(),
  ];


#------------------------------------------------------------------------------
use constant dx_minimum => -1;
{
  my %dx_maximum = (jump   => 2,
                    square => 1);
  sub dx_maximum {
    my ($self) = @_;
    return $dx_maximum{$self->{'end_type'}};
  }
}
use constant dy_minimum => -1;
*dy_maximum = \&dx_maximum;
sub _UNDOCUMENTED__dxdy_list {
  my ($self) = @_;
  return ($self->{'end_type'} eq 'jump'
          ? (1,0,   # E
             2,0,   # E by 2
             0,1,   # N
             0,2,   # N by 2
             -1,0,  # W
             0,-1)  # S
          : Math::PlanePath::Base::NSEW->_UNDOCUMENTED__dxdy_list);
}

use constant dsumxy_minimum => -1; # straight S
*dsumxy_maximum = \&dx_maximum;

{
  my %dDiffXY_max = (jump   => -2,
                     square => -1);
  sub ddiffxy_minimum {
    my ($self) = @_;
    return $dDiffXY_max{$self->{'end_type'}};
  }
}
*ddiffxy_maximum = \&dx_maximum;

use constant dir_maximum_dxdy => (0,-1); # South


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

# --16
#    |
#   17--18
#        |
# --15  19--20
#    |       |
#   14--13  21--22
#        |       |
#  --2  12--11  23--24  34--33
#    |       |       |       |
#    3-- 4  10-- 9  25--26  32--31
#        |       |       |       |
#  --1   5-- 6   8-- 7  27--28  30--29

# 17
#  |\
# 16 18
#  |  |
# 15 19-20
#  |     |
# 14-13 21-22
#     |     |
#  3 12-11 23-24 34-33
#  |\    |     |     |
#  2  4 10--9 25-26 32-31
#  |  |      \   |       \
#  1  5--6--7--8 27-28-29-30

#  .
#
# 42-43
#  |  |
# 41 44-45
#  |     |
# 40-39 46-47
#     |     |
#  . 38-37 48-
#        |
# 14-15 35-36
#  |  |     |
# 13 16-17 34-33
#  |     |     |
# 12-11 18-19 32-31
#     |     |     |
#  . 10--9 20-21 30-29
#        |     |     |
#  2--3  8--7 22-23 28-27
#  |  |     |    |      |
#  1  4--5--6  . 24-25-26  .
#
# start from integer vertical
# d = [ 2,  3,  4, 5 ]
# N = [ 5, 13, 25, 41 ]
# N = (2 d^2 - 2 d + 1)
#   = ((2*$d - 2)*$d + 1)
# d = 1/2 + sqrt(1/2 * $n + -1/4)
#   = (1 + sqrt(2*$n - 1)) / 2
#

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

  # adjust to N=1 at origin X=0,Y=0
  $n = $n - $self->{'n_start'} + 1;

  my $d;
  if ($self->{'end_type'} eq 'square') {
    if ($n < 1) { return; }

    $d = int( (1 + _sqrtint(2*$n-1)) / 2 );
    $n -= (2*$d - 2)*$d;
    ### $d
    ### remainder n: $n

    if ($n < 2) {
      if ($d % 2) {
        return (0, $n+2*$d-3);
      } else {
        return ($n+2*$d-3, 0);
      }
    }

  } else {
    if (2*$n < 1) { return; }

    $d = int ((1 + _sqrtint(8*$n-3)) / 4);
    $n -= (2*$d - 1)*$d;
    ### rem: $n
  }

  my $int = int($n);
  my $frac = $n - $int;
  my $r = int($int/2);

  my ($x,$y);
  if ($int % 2) {
    ### down ...
    $x = $r;
    $y = -$frac + 2*$d - $r;
  } else {
    ### across ...
    $x = $frac + $r-1;
    $y = 2*$d - $r;
  }

  if ($d % 2) {
    return ($x,$y);
  } else {
    return ($y,$x);
  }
}

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

  $x = round_nearest ($x);
  $y = round_nearest ($y);
  if ($x < 0 || $y < 0) {
    return undef;
  }

  my $jump = ($self->{'end_type'} ne 'square');
  unless ($jump) {
    # square omitted endpoints
    if ($x == 0) {
      if (($y % 4) == 2) {
        return undef;
      }
    } elsif ($y == 0 && ($x % 4) == 0) {
      return undef;
    }
  }

  my $d = int(($x + $y + 1) / 2);
  return ((2*$d + $jump) * $d
          + ($d % 2
             ? $x - $y
             : $y - $x)
          + $self->{'n_start'});
}

# 12--11  18--19      14--13  21--22
#      |       |           |       |
#  .  10-- 9  20       2  12--11  23
#          |           |       |
#  2-- 3   8-- 7       3-- 4  10-- 9
#  |   |       |           |       |
#  1   4-- 5-- 6       1   5-- 6   8
#
my @yx_to_min_dx = (0, 0, 0, -1,
                    0, 0, 1, 0,
                    0, 1, 0, 0,
                    1, 0, 0, 0);
my @yx_to_min_dy = (0, 1, 0, 0,
                    -1, 0, 0, 0,
                    0, 0, 0, 1,
                    0, 0, 1, 0);

my @yx_to_max_dx = (1, 0, 0, 0,
                    0, 0, 0, 1,
                    0, 0, 1, 0,
                    0, 1, 0, 0);
my @yx_to_max_dy = (0, 0, 1, 0,
                    0, 1, 0, 0,
                    1, 0, 0, 0,
                    0, 0, 0, 1);

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

  $x1 = round_nearest ($x1);
  $y1 = round_nearest ($y1);
  $x2 = round_nearest ($x2);
  $y2 = round_nearest ($y2);
  if ($x1 > $x2) { ($x1,$x2) = ($x2,$x1); }  # x2 > x1
  if ($y1 > $y2) { ($y1,$y2) = ($y2,$y1); }  # y2 > y1

  if ($x2 < 0 || $y2 < 0) {
    ### entirely outside first quadrant ...
    return (1, 0);
  }

  # not less than 0,0
  if ($x1 < 0) { $x1 *= 0; }
  if ($y1 < 0) { $y1 *= 0; }

  my $corner_x1 = $x1;
  my $corner_y1 = $y1;
  my $corner_x2 = $x2;
  my $corner_y2 = $y2;
  {
    my $key = 4*($y2 % 4) + ($x2 % 4);
    if ($x2 > $x1 && $yx_to_max_dx[$key]) {
      $corner_x2 -= 1;
    } elsif ($y2 > 0 && $y2 > $y1) {
      $corner_y2 -= $yx_to_max_dy[$key];
    }
  }

  my $square = ($self->{'end_type'} eq 'square');
  if ($square && $x1 == 0 && ($y1 % 4) == 2) {
    ### x1,y1 is an omitted Y axis point ...
    if ($corner_x1 < $x2) {
      $corner_x1 += 1;
    } elsif ($corner_y1 < $y2) {
      $corner_y1 += 1;
    } else {
      ### only this point ...
      return (1, 0);
    }

  } elsif ($square && $y1 == 0 && $x1 > 0 && ($x1 % 4) == 0) {
    if ($corner_y1 < $y2) {
      $corner_y1 += 1;
    } elsif ($corner_x1 < $x2) {
      $corner_x1 += 1;
    } else {
      ### only an omitted X axis point ...
      return (1, 0);
    }

  }
  {
    my $key = 4*($corner_y1 % 4) + ($corner_x1 % 4);
    ### min key: $key
    if ($corner_x1 < $x2 && (my $dx = $yx_to_min_dx[$key])) {
      ### x1 incr ...
      unless ($square && $dx < 0 && $corner_y1 == 0) {
        $corner_x1 += 1;
      }
    } elsif ($corner_y1 < $y2 && (my $dy = $yx_to_min_dy[$key])) {
      ### y1 incr ...
      unless ($square && $dy < 0 && $corner_x1 == 0) {
        $corner_y1 += 1;
      }
    }
  }

  ### corners: "$x1,$y1  $x2,$y2"

  return ($self->xy_to_n($corner_x1,$corner_y1),
          $self->xy_to_n($corner_x2,$corner_y2));
}

# inexact but easier ...
#
# if ($self->{'end_type'} eq 'square') {
#   $x2 += $y2 + 1;
#   $x2 = int($x2/2);
#   return (1,
#           (2*$x2+2)*$x2 + 1);
# } else {
#   $x2 += $y2 + 2;
#   return (1,
#           $x2*($x2+1)/2);
# }

1;
__END__