File Coverage

blib/lib/Math/PlanePath/Diagonals.pm

Criterion	Covered	Total	%
statement	66	104	63.4
branch	9	42	21.4
condition	7	15	46.6
subroutine	15	29	51.7
pod	17	17	100.0
total	114	207	55.0

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


# Leading diagonal 2,8,18 = 2*d^2
# cf A185787 lists numerous seqs for rows,columns,diagonals


package Math::PlanePath::Diagonals;
use 5.004;
use strict;
use Carp 'croak';
#use List::Util 'max';
*max = \&Math::PlanePath::_max;

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

use Math::PlanePath::Base::Generic
  'round_nearest';
*_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;
use constant n_frac_discontinuity => .5;

use constant parameter_info_array =>
  [ { name        => 'direction',
      share_key   => 'direction_downup',
      display     => 'Direction',
      type        => 'enum',
      default     => 'down',
      choices     => ['down','up'],
      choices_display => ['Down','Up'],
      description => 'Number points downwards or upwards along the diagonals.',
    },
    Math::PlanePath::Base::Generic::parameter_info_nstart1(),
    { name        => 'x_start',
      display     => 'X start',
      type        => 'integer',
      default     => 0,
      width       => 3,
      description => 'Starting X coordinate.',
    },
    { name        => 'y_start',
      display     => 'Y start',
      type        => 'integer',
      default     => 0,
      width       => 3,
      description => 'Starting Y coordinate.',
    },
  ];

sub x_minimum {
  my ($self) = @_;
  return $self->{'x_start'};
}
sub y_minimum {
  my ($self) = @_;
  return $self->{'y_start'};
}

sub dx_minimum {
  my ($self) = @_;
  return ($self->{'direction'} eq 'down'
          ? undef  # down jumps back unlimited at bottom
          : -1);   # up at most -1 across
}
sub dx_maximum {
  my ($self) = @_;
  return ($self->{'direction'} eq 'down'
          ? 1       # down at most +1 across
          : undef); # up jumps back across unlimited at top
}

sub dy_minimum {
  my ($self) = @_;
  return ($self->{'direction'} eq 'down'
          ? -1      # down at most -1
          : undef); # up jumps down unlimited at top
}
sub dy_maximum {
  my ($self) = @_;
  return ($self->{'direction'} eq 'down'
          ? undef  # down jumps up unlimited at bottom
          : 1);    # up at most +1
}

sub absdx_minimum {
  my ($self) = @_;
  return ($self->{'direction'} eq 'down'
          ? 0   # N=1 dX=0,dY=1
          : 1); # otherwise always changes
}
sub absdy_minimum {
  my ($self) = @_;
  return ($self->{'direction'} eq 'down'
          ? 1   # otherwise always changes
          : 0); # N=1 dX=1,dY=0
}

# within diagonal X+Y=k is dSum=0
# end of diagonal X=Xstart+k Y=Ystart
#             to  X=Xstart   Y=Ystart+k+1
# is (Xstart + Ystart+k+1) - (Xstart+k + Ystart) = 1 always, to next diagonal
#
use constant dsumxy_minimum => 0; # advancing diagonals
use constant dsumxy_maximum => 1;

sub ddiffxy_minimum {
  my ($self) = @_;
  return ($self->{'direction'} eq 'down'
          ? undef  # "down" jumps back unlimited at bottom
          : -2);   # NW diagonal
}
sub ddiffxy_maximum {
  my ($self) = @_;
  return ($self->{'direction'} eq 'down'
          ? 2       # SE diagonal
          : undef); # "up" jumps down unlimited at top
}

sub dir_minimum_dxdy {
  my ($self) = @_;
  return ($self->{'direction'} eq 'down'
          ? (0,1)   # North, vertical at N=1
          : (1,0)); # East,  horiz at N=1
}
sub dir_maximum_dxdy {
  my ($self) = @_;
  return ($self->{'direction'} eq 'down'
          ? (1,-1)    # South-East at N=2
          : (2,-1));  # ESE        at N=3
}

# If Xstart>0 or Ystart>0 then the origin is not reached.
sub rsquared_minimum {
  my ($self) = @_;
  return ((  $self->{'x_start'} > 0 ? $self->{'x_start'}**2 : 0)
          + ($self->{'y_start'} > 0 ? $self->{'y_start'}**2 : 0));
}



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

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

  my $direction = ($self->{'direction'} ||= 'down');
  if (! ($direction eq 'up' || $direction eq 'down')) {
    croak "Unrecognised direction option: ", $direction;
  }

  $self->{'x_start'} ||= 0;
  $self->{'y_start'} ||= 0;
  return $self;
}

# start each diagonal at 0.5 earlier than the integer point
#   d = [    0,   1,   2,   3,   4 ]
#   n = [ -0.5, 0.5, 2.5, 5.5, 9.5 ]
#             +1   +2   +3   +4
#                1    1    1
# N = (1/2 d^2 + 1/2 d - 1/2)
#   = (1/2*$d**2 + 1/2*$d - 1/2)
#   = ((1/2*$d + 1/2)*$d - 1/2)
# d = -1/2 + sqrt(2 * $n + 5/4)
#   = (sqrt(8*$n + 5) -1)/2

sub n_to_xy {
  my ($self, $n) = @_;
  ### Diagonals n_to_xy(): "$n   ".(ref $n || '')

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

  my $d;
  {
    my $r = 8*$n + 5;
    if ($r < 1) {
      ### which is N < -0.5 ...
      return;
    }
    ### sqrt of: "$r"
    ### sqrt is: sqrt(int($r)).""

    $d = int((_sqrtint($r) - 1) / 2);
    ### assert: $d >= 0
    ### d: "$d"
    ### $d
  }

  # subtract for offset into diagonal, range -0.5 <= $n < $d+0.5
  $n -= $d*($d+1)/2;
  ### subtract to n: "$n"

  my $y = -$n + $d;  # $n first so BigFloat not BigInt from $d
  # and X=$n

  if ($self->{'direction'} eq 'up') {
    ($n,$y) = ($y,$n);
  }
  return ($n + $self->{'x_start'},
          $y + $self->{'y_start'});
}

# round y on an 0.5 downwards so that x=-0.5,y=0.5 gives n=1 which is the
# inverse of n_to_xy() ... or is that inconsistent with other classes doing
# floor() always?
#
# d(d+1)/2+1
#   = (d^2 + d + 2) / 2
#
sub xy_to_n {
  my ($self, $x, $y) = @_;
  ### xy_to_n(): $x, $y
  $x = $x - $self->{'x_start'};   # "-" operator to provoke warning if x==undef
  $y = $y - $self->{'y_start'};
  if ($self->{'direction'} eq 'up') {
    ($x,$y) = ($y,$x);
  }
  $x = round_nearest ($x);
  $y = round_nearest (- $y);
  ### rounded
  ### $x
  ### $y
  if ($x < 0 || $y > 0) {
    return undef;  # outside
  }

  my $d = $x - $y;
  ### $d
  return $d*($d+1)/2 + $x + $self->{'n_start'};
}

# bottom-left to top-right, used by DiagonalsAlternating too
# exact
sub rect_to_n_range {
  my ($self, $x1,$y1, $x2,$y2) = @_;

  if ($x1 > $x2) { ($x1,$x2) = ($x2,$x1); }
  if ($y1 > $y2) { ($y1,$y2) = ($y2,$y1); }
  if ($x2 < $self->{'x_start'} || $y2 < $self->{'y_start'}) {
    return (1, 0); # rect all negative, no N
  }

  $x1 = max ($x1, $self->{'x_start'});
  $y1 = max ($y1, $self->{'y_start'});

  # exact range bottom left to top right
  return ($self->xy_to_n ($x1,$y1),
          $self->xy_to_n ($x2,$y2));
}

1;
__END__