File Coverage

blib/lib/Math/PlanePath/DigitGroups.pm

Criterion	Covered	Total	%
statement	57	113	50.4
branch	6	36	16.6
condition	10	19	52.6
subroutine	12	17	70.5
pod	4	4	100.0
total	89	189	47.0

# 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 .


# math-image --path=DigitGroups --output=numbers_dash
# math-image --path=DigitGroups,radix=2 --all --output=numbers
#
# increment N+1 changes low 01111 to 10000
# X bits change 01111 to 000, no carry, decreasing by number of low 1s
# Y bits change 011 to 100, plain +1
#
# cf A084473 binary 0->0000
#    A088698 binary 1->11
#    A175047 binary 0000run->0
#
# G. Cantor, "Ein Beitrag zur Mannigfaltigkeitslehre", Journal für die reine
# und angewandte Mathematik (Crelle's Journal), Vol. 84, 242-258, 1878.
# http://www.digizeitschriften.de/dms/img/?PPN=PPN243919689_0084&DMDID=dmdlog15


package Math::PlanePath::DigitGroups;
use 5.004;
use strict;
#use List::Util 'max','min';
*max = \&Math::PlanePath::_max;
*min = \&Math::PlanePath::_min;

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

use Math::PlanePath::Base::Generic
  'is_infinite',
  'round_nearest';
use Math::PlanePath::Base::Digits
  'parameter_info_array',    # "radix" parameter
  'round_down_pow',
  'digit_split_lowtohigh',
  'digit_join_lowtohigh';

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


use constant n_start => 0;
use constant class_x_negative => 0;
use constant class_y_negative => 0;
*xy_is_visited = \&Math::PlanePath::Base::Generic::xy_is_visited_quad1;
use constant absdx_minimum => 1;

sub _UNDOCUMENTED__turn_any_left_at_n {
  my ($self) = @_;
  return $self->{'radix'} - 1;
}
sub _UNDOCUMENTED__turn_any_right_at_n {
  my ($self) = @_;
  return $self->{'radix'};
}
sub _UNDOCUMENTED__turn_any_straight_at_n {
  my ($self) = @_;
  if ($self->{'radix'} == 2) { return 274; }
  return 1;
}

#------------------------------------------------------------------------------
sub new {
  my $self = shift->SUPER::new(@_);

  my $radix = $self->{'radix'};
  if (! defined $radix || $radix <= 2) { $radix = 2; }
  $self->{'radix'} = $radix;

  return $self;
}

sub n_to_xy {
  my ($self, $n) = @_;
  ### DigitGroups n_to_xy(): $n
  if ($n < 0) {
    return;
  }
  if (is_infinite($n)) {
    return ($n,$n);
  }

  # what to do for fractions ?
  {
    my $int = int($n);
    ### $int
    if ($n != $int) {
      my $frac = $n - $int;  # inherit possible BigFloat/BigRat
      ### $frac
      my ($x1,$y1) = $self->n_to_xy($int);
      my ($x2,$y2) = $self->n_to_xy($int+1);
      my $dx = $x2-$x1;
      my $dy = $y2-$y1;
      return ($frac*$dx + $x1, $frac*$dy + $y1);
    }
    $n = $int; # BigFloat int() gives BigInt, use that
  }

  my $radix = $self->{'radix'};
  my (@x,@y); # digits low to high

  my @digits = digit_split_lowtohigh($n,$radix)
    or return (0,0);  # if $n==0

  DIGITS: for (;;) {
    my $digit;

    # from @digits to @x
    do {
      ### digit to x: $digits[0]
      $digit = shift @digits;  # $n digits low to high
      push @x, $digit;
      @digits || last DIGITS;
    } while ($digit);  # $digit==0 is separator

    # from @digits to @y
    do {
      $digit = shift @digits;  # low to high
      ### digit to y: $digit
      push @y, $digit;
      @digits || last DIGITS;
    } while ($digit);  # $digit==0 is separator
  }

  my $zero = $n * 0; # inherit bignum 0
  return (digit_join_lowtohigh (\@x, $radix, $zero),
          digit_join_lowtohigh (\@y, $radix, $zero));
}

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

  $x = round_nearest ($x);
  $y = round_nearest ($y);

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

  if ($x == 0 && $y == 0) {
    return 0;
  }

  my $radix = $self->{'radix'};
  my $zero = ($x * 0 * $y);  # inherit bignum 0
  my @n; # digits low to high

  my @x = digit_split_lowtohigh($x,$radix);
  my @y = digit_split_lowtohigh($y,$radix);

  while (@x || @y) {
    my $digit;
    do {
      $digit = shift @x || 0; # low to high
      ### digit from x: $digit
      push @n, $digit;
    } while ($digit);

    do {
      $digit = shift @y || 0; # low to high
      ### digit from y: $digit
      push @n, $digit;
    } while ($digit);
  }
  return digit_join_lowtohigh (\@n, $radix, $zero);
}

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

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

  if ($y2 < 0 || $x2 < 0) {
    return (1, 0); # rect all negative, no N
  }

  my $radix = $self->{'radix'};

  my ($power, $lo_level) = round_down_pow (min($x1,$y1), $radix);
  if (is_infinite($lo_level)) {
    return (0,$lo_level);
  }

  ($power, my $hi_level) = round_down_pow (max($x2,$y2), $radix);
  if (is_infinite($hi_level)) {
    return (0,$hi_level);
  }

  return ($lo_level == 0 ? 0
          : ($radix*$radix + 1) * $radix ** (2*$lo_level),

          ($radix-1)*$radix**(3*$hi_level+2)
          + $radix**($hi_level+1)
          - 1);
}

1;
__END__