#!/usr/bin/perl -w

# Copyright 2010, 2011 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 <http://www.gnu.org/licenses/>.

use 5.006;
use strict;
use warnings;


=over

=item C<($n, $x, $y) = $path-E<gt>next()>
=item C<($n, $x, $y) = $path-E<gt>next_nxy()>

=item C<($n, $x, $y) = $path-E<gt>peek()>

=item C<$path-E<gt>rewind()>

=item C<$path-E<gt>seek_to_n($n)>

=item C<$n = $path-E<gt>tell_n($n)>
=item C<($n,$x,$y) = $path-E<gt>tell_nxy($n)>

=back

=cut


use Math::PlanePath;

{
  package Math::PlanePath;
  no warnings 'redefine';
  sub new {
    my $class = shift;
    my $self = bless { @_ }, $class;
    $self->rewind;
    return $self;
  }
  sub rewind {
    my ($self) = @_;
    $self->seek_to_n($self->n_start);
  }
  sub seek_to_n {
    my ($self, $n) = @_;
    $self->{'n'} = $n;
  }
  sub tell_n {
    my ($self, $n) = @_;
    return $self->{'n'};
  }
  sub next_nxy {
    my ($self) = @_;
    my $n = $self->{'n'}++;
    return ($n, $self->n_to_xy($n));
  }
  sub peek_nxy {
    my ($self) = @_;
    my $n = $self->{'n'};
    return ($n, $self->n_to_xy($n));
  }
}

{
  use Math::PlanePath::ZOrderCurve;
  package Math::PlanePath::ZOrderCurve;
  # sub seek_to_n {
  #   my ($self, $n) = @_;
  #   ($self->{'x'},$self->{'y'}) = $self->n_to_xy($self->{'n'} = $n);
  #   $self->{'bx'} = $x;
  #   $self->{'by'} = $y;
  #   $self->{'a'} = [ \$self->{'x'}, \$self->{'y'} ];
  #   $self->{'i'} = 1;
  #   ### ZOrderCurve seek_to_n(): $self
  # }
  # sub next_nxy {
  #   my ($self) = @_;
  #   $self->{'a'}->[($self->{'i'} ^= 1)]++;
  #   return (++$self->{'n'}, $self->{'x'}, $self->{'y'});
  # }
  # sub peek_nxy {
  #   my ($self) = @_;
  #   return ($self->{'n'} + 1,
  #           $self->{'x'} + !$self->{'i'},
  #           $self->{'y'} + $self->{'i'});
  # }
}

{
  use Math::PlanePath::Rows;
  package Math::PlanePath::Rows;
  sub seek_to_n {
    my ($self, $n) = @_;
    $self->{'n'} = --$n;
    my $width = $self->{'width'};
    $self->{'px'} = ($n % $width) - 1;
    $self->{'py'} = int ($n / $width);
    ### seek_to_n: $self
  }
  sub next_nxy {
    my ($self) = @_;
    my $x = ++$self->{'px'};
    if ($x >= $self->{'width'}) {
      $x = $self->{'px'} = 0;
      $self->{'py'}++;
    }
    return (++$self->{'n'}, $x, $self->{'py'});
  }
  sub peek_nxy {
    my ($self) = @_;
    if ((my $x = $self->{'px'} + 1) < $self->{'width'}) {
      return ($self->{'n'}+1, $x, $self->{'py'});
    } else {
      return ($self->{'n'}+1, 0, $self->{'py'}+1);
    }
  }
}
{
  use Math::PlanePath::Diagonals;
  package Math::PlanePath::Diagonals;
  # N = (1/2 d^2 + 1/2 d + 1)
  #   = (1/2*$d**2 + 1/2*$d + 1)
  #   = ((0.5*$d + 0.5)*$d + 1)
  # d = -1/2 + sqrt(2 * $n + -7/4)
  sub seek_to_n {
    my ($self, $n) = @_;
    $self->{'n'} = $n;
    my $d = $self->{'d'} = int (-.5 + sqrt(2*$n - 1.75));
    $n -= $d*($d+1)/2 + 1;
    $self->{'px'} = $n - 1;
    $self->{'py'} = $d - $n + 1;
    ### Diagonals seek_to_n(): $self
  }
  sub next_nxy {
    my ($self) = @_;
    my $x = ++$self->{'px'};
    my $y = --$self->{'py'};
    if ($y < 0) {
      $x = $self->{'px'} = 0;
      $y = $self->{'py'} = ++$self->{'d'};
    }
    return ($self->{'n'}++, $x, $y);
  }
  sub peek_nxy {
    my ($self) = @_;
    if (my $y = $self->{'py'}) {
      return ($self->{'n'}, $self->{'px'}+1, $y-1);
    } else {
      return ($self->{'n'}, 0, $self->{'d'}+1);
    }
  }
}

{
  use Math::PlanePath::SquareSpiral;
  package Math::PlanePath::SquareSpiral;

  sub next_nxy {
    my ($self) = @_;
    ### next(): $self
    my $x = ($self->{'x'} += $self->{'dx'});
    my $y = ($self->{'y'} += $self->{'dy'});

    unless ($self->{'side'}--) {
      ### turn
      ($self->{'dx'},$self->{'dy'}) = (-$self->{'dy'},$self->{'dx'}); # left
      $self->{'side'} = (($self->{'d'} += ($self->{'grow'} ^= 1)) - 1)
        + ($self->{'dx'} && $self->{'wider'});
      ### grow applied: $self->{'grow'}
      ### d now: $self->{'d'}
      ### side now: $self->{'side'}
      ### dx,dy now: "$self->{'dx'},$self->{'dy'}"
    }

    ### return: 'n='.$self->{'n'}.' '.($self->{'x'} + $self->{'dx'}).','.($self->{'y'} + $self->{'dy'})
    return ($self->{'n'}++, $x, $y);
  }
  sub peek_nxy {
    my ($self) = @_;
    # ### peek(): $self
    return ($self->{'n'},
            $self->{'x'} + $self->{'dx'},
            $self->{'y'} + $self->{'dy'});
  }

  # N = (1/2 d^2 + 1/2 d + 1)
  #   = (1/2*$d**2 + 1/2*$d + 1)
  #   = ((0.5*$d + 0.5)*$d + 1)
  # d = -1/2 + sqrt(2 * $n + -7/4)
  sub seek_to_n {
    my ($self, $n) = @_;
    ### SquareSpiral seek_to_n: $n
    $self->{'n'} = $n;

    my $d = $self->{'d'} = int (1/2 + sqrt(1 * $n + -3/4));
    $n -= (($d - 1)*$d + 1);
    ### $d
    ### half d: int($d/2)
    ### remainder: $n

    my $dx;
    my $dy;
    my $y = - int($d/2);
    my $x = $y + $n;
    if ($self->{'grow'} = ($n < $d)) {
      ### horizontal
      $dx = 1;
      $dy = 0;
    } else {
      ### vertical
      $n -= $d;
      $dx = 0;
      $dy = 1;
      ($x, $y) = ($y + $d,
                  $x - $d);
    }

    if ($d & 1) {
    } else {
      ### negate for even d from: "$x,$y"
      $dx = - $dx;
      $dy = - $dy;
      $x = -$x;
      $y = -$y;
    }

    $self->{'side'} = $d - $n;

    $self->{'dx'} = $dx;
    $self->{'dy'} = $dy;
    $self->{'x'} = $x - $dx;
    $self->{'y'} = $y - $dy;


    # if ($n == 3) {
    #   $self->{'side'} = 2;
    #   $self->{'grow'} = 1;
    #   $self->{'d'} = 2;
    #   $self->{'dx'} = -1;
    #   $self->{'dy'} = 0;
    #   $self->{'x'} = 2;
    #   $self->{'y'} = 1;
    #   return;
    # }
    #
    # $self->{'n'} = $n;
    # $self->{'side'} = 1;
    # $self->{'grow'} = 0;
    # $self->{'d'} = 0;
    # $self->{'dx'} = 1;
    # $self->{'dy'} = 0;
    # $self->{'x'} = -1;
    # $self->{'y'} = 0;
    ### SquareSpiral seek_to_n(): $self
  }
}

use Smart::Comments;

foreach my $class ('Math::PlanePath::SquareSpiral',
                   'Math::PlanePath::Diagonals',
                   'Math::PlanePath::Rows',
                  ) {
  my $path = $class->new (width => 5);
  foreach my $n_start_offset (0 .. 30) {
    my $want_n = $path->n_start;
    if ($n_start_offset) {
      $want_n += $n_start_offset;
      $path->seek_to_n ($want_n);
    }
    ### $class
    ### $n_start_offset
    foreach my $i (0 .. 100) {
      my ($peek_n, $peek_x, $peek_y) = $path->peek;
      my ($got_n, $got_x, $got_y) = $path->next;
      my ($want_x, $want_y) = $path->n_to_xy($want_n);

      if ($want_n != $got_n) {
        ### $want_n
        ### $got_n
        die "x";
      }
      if ($want_x != $got_x) {
        ### $want_n
        ### $want_x
        ### $got_x
        die "x";
      }
      if ($want_y != $got_y) {
        ### $want_n
        ### $want_y
        ### $got_y
        die "x";
      }

      if ($peek_n != $want_n) {
        ### $peek_n
        ### $want_n
        die "x";
      }
      if ($peek_x != $want_x) {
        ### $want_n
        ### $peek_x
        ### $want_x
        die "x";
      }
      if ($peek_y != $want_y) {
        ### $want_n
        ### $peek_y
        ### $want_y
        die "x";
      }

      $want_n++;
    }
  }
}