package AI::NaturalSelection::Plot2;

use strict;

=item new() or
  new({
	POINTS		=> [ [X, Y], [X, Y], ],
	NUMPOINTS	=> 0,
	X		=> 100,
	Y		=> 100,
	TOUR		=> [ FIRST_POINTS_ELEMENT, SECOND, LAST, ],
  })

Creates a new plot.  Accepts an optional hash ref with
optional elements:

 POINTS:
	Array ref of array refs of x- and y- axes.
	These points will be created on the plot.  The
	distances will also be created.

 NUMPOINTS:
	Number of additional, random points to create
	on the plot.

 X:
	Size of the plot's x-axis.

 Y:
	Size of the plot's y-axis.

 TOUR:
	The cities in a single tour in order.  Each
	element is the point's element in the points
	arrayref.
=cut
sub new {
  my ($proto, $self)	= @_;
  my $class		= ref($proto) || $proto;
  my $points;

  if ($self->{NUMPOINTS}) {
    if ($#{$self->{POINTS}} == -1) {
      $points = delete $self->{NUMPOINTS};
    }
  }
  $self->{DISTANCES}	||= [];
  $self->{NUMPOINTS}	||= 0;
  $self->{TOUR}		= [];
  $self->{TOURNUMS}	= $#{$self->{TOUR}} + 1;
  $self->{POINTS}	||= [];
  $self->{X}		||= 100;
  $self->{Y}		||= 100;

  bless($self, $class);

  $self->createPlot($points, 1) if $points && $#{$self->{POINTS}} == -1;
  $self->createDistances() if $points && $#{$self->{DISTANCES}} == -1;

  return $self;
}


=item createPoint(X_POINT, Y_POINT [, DONT_CREATE_DIST])

Accepts x- and y-axes and adds the point to the plot.  If the point
already exists, returns 0.  If it doesn't, it returns the number of
points on the plot after adding the new point.
=cut
sub createPoint {
  my ($self, $x, $y, $dist) = @_;

  unless ($self->existsPoint($x, $y)) {
    push(@{$self->{POINTS}}, [$x, $y]);
    $self->createDistances() unless $dist;
    return $self->{NUMPOINTS} = @{$self->{POINTS}};
  }
  return 0;
}


=item existsPoint(X_POINT, Y_POINT)

Accepts x- and y-axes.  If the point exists on the plot, returns true.
Otherwise, returns 0.
=cut
sub existsPoint {
  my ($self, $x, $y) = @_;
  return grep { $$_[0] == $x && $$_[1] == $y } @{$self->{POINTS}};
}


=item createPlot(POINTS [, MAX_X_AXIS, MAX_Y_AXIS] [, DONT_CREATE_DIST])

Accepts the number of points to put on the plot and optional
x- and y-axes as well as an optional boolean value, DONT_CREATE_DIST,
which determines whether to call the createDistances() function or not
after adding the point.  Creates POINTS points on the plot within
MAX_X_AXIS and MAX_Y_AXIS.  If the axes aren't specified,
it uses the ones specified on creation or default (100, 100).

Returns the number of points created (will be the number of
points specified).
=cut
sub createPlot {
  my ($self, $numPoints, $x, $y, $dist) = @_;
  my ($i, $tmpx, $tmpy);

  # only passed DONT_CREATE_DIST to the function
  # and not X- or Y-axes
  if ($x && !$y) {
    $dist = $x;
    $x = 0;
  }

  # set new X- and Y-axes if they were passed
  $self->{X} = $x if $x;
  $self->{Y} = $y if $y;

  # keep attempting to create random points until we have the number
  # of points that we need
  while ($self->{NUMPOINTS} != $numPoints) {
    $self->createPoint(int(rand($self->{X})), int(rand($self->{Y})), 1);
  }
  $self->createDistances() unless $dist;

  return $self->{NUMPOINTS};
}


=item createDistances()

Always returns true.  This function creates the distances from all
points on the plot to all other points on the plot.
=cut
sub createDistances {
  my ($self) = @_;
  my ($x, $y, $i, $j);
  $self->{DISTANCES} = [];

  for ($i = 0; $i < $self->{NUMPOINTS}; $i++) {
    for ($j = 0; $j < $self->{NUMPOINTS}; $j++) {
      next if $self->{DISTANCES}[$i][$j] || $i == $j;
      ($x, $y) = @{${$self->{POINTS}}[$i]};
      ($a, $b) = @{${$self->{POINTS}}[$j]};
      $self->{DISTANCES}[$i][$j] = $self->{DISTANCES}[$j][$i] = sprintf "%6f", sqrt ( (($b - $y) ** 2) + (($a - $x) ** 2) );
    }
  }

  return 1;
}


=item returnPlot()

Returns an array of array refs.  Each array ref contains two
elemnts: an x- and y-axis, in that order.
=cut
sub returnPlot {
  my ($self) = @_;
  return @{$self->{POINTS}};
}


=item tourDistance()

Accepts a tour number and returns the distance from the first
point to last in the tour.
=cut
sub tourDistance {
  my ($self, $tour)	= @_;
  my $distance		= 0;

  for (my $i = 0; $i < $self->{NUMPOINTS}; $i++) {
    $distance += $self->{DISTANCES}[$i][$self->{TO}[$tour][$i]];
#    $distance += $self->{DISTANCES}[$self->{TOUR}[$tour][$i]][$self->{TOUR}[$tour][$i+1]];
  }

  return $distance;
}


=item setTour([\@tour] [, $tour_number])

Creates a tour.
If no arguments are passed, creates a random tour from
one point to all other points.

If a number is passed, creates a random tour from one
point to all other points with the number as the tour
number.

If an array reference is passed, creates a tour with
the points in the array reference as the tour, in order.

If an array reference and number is passed, creates a
tour with the points in the array reference as the tour
and uses the number as the tour number.

Returns the tour number.
=cut
sub setTour {
  my ($self, @tour)	= @_;
  my $tour;

  if (ref($tour[0]) && defined($tour[1])) {
    $self->{TOUR}[$tour[1]] = [@{$tour[0]}];
    return $tour[1];
  }
  elsif (ref($tour[0])) {
    $tour = $self->{TOURNUMS}++;
    $self->{TOUR}[$tour] = [@{$tour[0]}];
    return $tour;
  }
  elsif (defined($tour[0])) {
    $tour = $tour[0];
    @tour = ();
  }
  else {
    $tour = $self->{TOURNUMS}++;
  }

  my ($i, $j, $i0, $j0, $k);
  for ($i = 0; $i < $self->{NUMPOINTS}; $i++) {
    $self->{TO}[$tour][$i] = -1;
  }
  for ($i0 = $i = 0; $i < $self->{NUMPOINTS}; $i++) {
    $j = int(rand()*1000) % ($self->{NUMPOINTS} - $i);

    $self->{TO}[$tour][$i0] = 0;

    for ($j0 = $k = 0; $k < $j; $k++) {
      $j0++;
      while ($self->{TO}[$tour][$j0] != -1) { $j0++ }
    }

    while ($self->{TO}[$tour][$j0] != -1) { $j0++ }

    $self->{TO}[$tour][$i0]	= $j0;
    $self->{FROM}[$tour][$j0]	= $i0;
  }

#  my @points = 0 .. $self->{NUMPOINTS} - 1;
#  while (@points) {
#    push(@tour, splice(@points, int(rand(@points)), 1));
#  }
#  $self->{TOUR}[$tour] = [@tour];
  return 1;
}

=item localOptimizeTour($tourNumber)

Accepts a tour number.
Crates a local optimum of the tour.
=cut
sub localOptimizeTour {
  my ($self, $tour) = @_;

  do {
    while ($self->improveTour($tour)) { }
  } while ($self->improveCrossTour($tour));
die;

  return 1;
}


=item improveTour($tourNumber)

Accepts a tour number.
Improves the tour.
=cut
sub improveTour {
  my ($self, $tour) = @_;

  my ($i, $j, $h, $d1, $d2, @H);
  for ($i = 0; $i < $self->{NUMPOINTS}; $i++) {
    $H[$i] = sprintf "%6f",
             -$self->{DISTANCES}[$self->{FROM}[$tour][$i]][$i]
             +$self->{DISTANCES}[$i][$self->{TO}[$tour][$i]]
             +$self->{DISTANCES}[$self->{FROM}[$tour][$i]][$self->{TO}[$tour][$i]];
print "$H[$i]\n";
  }
  for ($i = 0; $i < $self->{NUMPOINTS}; $i++) {
    $d1 = $self->{DISTANCES}[$i][$self->{TO}[$tour][$i]];
    $j = $self->{TO}[$tour][$self->{TO}[$tour][$i]];
    while ($j != $i) {
      $d2 = $H[$j] + $self->{DISTANCES}[$i][$j] + $self->{DISTANCES}[$j][$self->{TO}[$tour][$i]] + $d1;
print "x $H[$j] + $self->{DISTANCES}[$i][$j] + $self->{DISTANCES}[$j][$self->{TO}[$tour][$i]] + $d1 = $d2\n";
      if ($d2 < 100) {
        $h = $self->{FROM}[$tour][$j];
        $self->{TO}[$tour][$h] = $self->{TO}[$tour][$j];
        $self->{FROM}[$tour][$self->{TO}[$tour][$j]] = $h;
        $h = $self->{TO}[$tour][$i];
        $self->{TO}[$tour][$i] = $j;
        $self->{TO}[$tour][$j] = $h;
        $self->{FROM}[$tour][$h] = $j;
        $self->{FROM}[$tour][$j] = $i;
        return 1;
      }
      $j = $self->{TO}[$tour][$j];
    }
  }
  return 0;
}


=item improveCrossTour($tourNumber)

Accepts a tour number.
Improves the path locally.
=cut
sub imrpoveCrossTour($tourNumber) {
  my ($self, $tour) = @_;

  my ($i, $j, $h, $h1, $hj, $d1, $d2, $d);
  for ($i = 0; $i < $self->{NUMPOINTS}; $i++) {
    $d1	= -$self->{DISTANCES}[$i][$self->{TO}[$tour][$i]];
    $j	= $self->{TO}[$tour][$self->{TO}[$tour][$i]];
    $d2	= 0;
    $d	= 0;
    while ($self->{TO}[$tour][$j] != $i) {
      $d += $self->{DISTANCES}[$j][$self->{FROM}[$tour][$j]] -
            $self->{DISTANCES}[$self->{FROM}[$tour][$j]][$j];
      $d2 = $d1 + $self->{DISTANCES}[$i][$j] + $d +
            $self->{DISTANCES}[$self->{TO}[$tour][$i]][$self->{TO}[$tour][$j]] -
            $self->{DISTANCES}[$j][$self->{TO}[$tour][$j]];
      if ($d2 < -1e-10) {
        $h = $self->{TO}[$tour][$i];
        $h1 = $self->{TO}[$tour][$j];
        $self->{TO}[$tour][$i] = $j;
        $self->{TO}[$tour][$h] = $h1;
        $self->{FROM}[$tour][$h1] = $h;
        $hj = $i;
        while ($j != $h) {
          $h1 = $self->{FROM}[$tour][$j];
          $self->{TO}[$tour][$j] = $h1;
          $self->{FROM}[$tour][$j] = $hj;
          $hj = $j;
          $j = $h1;
        }
        $self->{FROM}[$tour][$j] = $hj;
        return 1;
      }
    $j = $self->{TO}[$tour][$j];
    }
  }
  return 0;
}


=item getTour($tourNumber)

Accepts a tour number.
Returns an array of the points in the tour.
=cut
sub getTour {
  my ($self, $tour) = @_;
  return @{$self->{TOUR}[$tour]};
}

=item drawPlot()

Draws the plot.
=cut
sub drawPlot {
  my ($self) = @_;
  my %hash;

  foreach (@{$self->{POINTS}}) {
    $hash{$$_[0]}{$$_[1]} = 1;
  }
  foreach my $x (0 .. $self->{X} - 1) {
    foreach my $y (0 .. $self->{Y} - 1) {
      print ($hash{$x}{$y} ? "X" : ".");
    }
    print "\n";
  }

  return 1;
}


=item drawTour($tournum)

Draws the tour (actually draws the plot with
each city numbered in the order of the tour.)
=cut
sub drawTour {
  my ($self, $tour) = @_;
  my (%hash, %tour);

  for (my $i = 0; $i < $self->{NUMPOINTS}; $i++) {
    $hash{$self->{POINTS}[$i][0]}{$self->{POINTS}[$i][1]} = $i;
    $i = $self->{TO}[$tour][$i];
  }
  my $len = 0;
  foreach my $x (0 .. $self->{X} - 1) {
    foreach my $y (0 .. $self->{Y} - 1) {
      if ($hash{$x}{$y}) {
        $len += length($hash{$x}{$y});
        print $hash{$x}{$y};
      }
      else {
        if ($len) {
          $len--;
        }
        else {
          print ".";
        }
      }
    }
    print "\n";
  }

  return 1;
}


=item clone()

Returns a clone of $self.
=cut
sub clone {
  my ($self)	= @_;
  my %new	= %{$self};

  foreach my $key (%new) {

    if (ref($new{$key}) eq "ARRAY") {
      $new{$key} = [@{$self->{$key}}];
      if (ref($new{$key}[0]) eq "ARRAY") {
        foreach (@{$new{$key}}) {
          $_ = [@{$_}];
        }
      }
    }
    elsif (ref($new{$key}) eq "HASH") {
      $new{$key} = {%{$self->{$key}}};
    }
  }

  return AI::NaturalSelection::Plot->new({%new});
}

=item setPlot(\@points, $x, $y)

Accepts an array reference of array references
of (X, Y) values for a plot and the size of the
plot by x- and y-axes.
Returns true.
=cut
sub setPlot {
  my ($self, $points, $x, $y) = @_;
  $self->{POINTS} = $points;
  $self->{NUMPOINTS} = $#{$self->{POINTS}} + 1;
  $self->{X} = $x;
  $self->{Y} = $y;
  $self->createDistances();

  return 1;
}

1;