// Organism.h
// Simple implementation of Conway game of life in standard C++11.

#ifndef ORGANISM_H
#define ORGANISM_H

#include <cstddef>
#include <cstdint>
#include <vector>
#include <unordered_set>
#include <algorithm>

static_assert(sizeof(size_t) == sizeof(int64_t), "size_t too small, need a 64-bit compile");

// CELL
typedef int32_t  cell_coord_type;
typedef uint64_t cell_whole_type;
typedef int64_t  cell_signed_whole_type;

#define XX(w)    ((cell_coord_type)(w))
#define YY(w)    ((cell_coord_type)(((w) >> 32) & 0xFFFFFFFF))
#define WW(x, y) (((cell_signed_whole_type)(y) << 32) | ((cell_signed_whole_type)(x) & 0xFFFFFFFF))

struct Cell {
   cell_coord_type x;
   cell_coord_type y;
   Cell(cell_coord_type x_, cell_coord_type y_) : x(x_), y(y_) {}
   Cell(cell_whole_type w) : x(XX(w)), y(YY(w)) {}
};
inline bool operator<(const Cell& lhs, const Cell& rhs) {
   if (lhs.x < rhs.x) return true;
   if (lhs.x > rhs.x) return false;
   return lhs.y < rhs.y;
   // or one-liner: return lhs.x < rhs.x || (lhs.x == rhs.x && lhs.y < rhs.y);
}
inline bool operator>( const Cell& lhs, const Cell& rhs) { return rhs < lhs; }
inline bool operator<=(const Cell& lhs, const Cell& rhs) { return !(lhs > rhs); }
inline bool operator>=(const Cell& lhs, const Cell& rhs) { return !(lhs < rhs); }
inline bool operator==(const Cell& lhs, const Cell& rhs) { return lhs.x == rhs.x && lhs.y == rhs.y; }
inline bool operator!=(const Cell& lhs, const Cell& rhs) { return !(lhs == rhs); }

using cell_list_type = std::vector<Cell>;
struct CellHasher { size_t operator()(cell_whole_type w) const { return w; }  };
using cell_lookup_type = std::unordered_set<cell_whole_type, CellHasher>;

// ORGANISM
class Organism {
public:
   Organism(size_t ncell = 1000) { cells_m.reserve(ncell); }
   size_t count() const { return cells_m.size(); }
   size_t is_alive(cell_whole_type w) const { return cells_m.find(w) != cells_m.end(); }
   size_t is_dead(cell_whole_type w)  const { return cells_m.find(w) == cells_m.end(); }

   // Used to initialize the starting state of the organism
   size_t insert_cells(const cell_list_type& cells) {
      size_t n_inserted = 0;
      for (const auto& c : cells) {
         if (cells_m.insert(WW(c.x, c.y)).second) ++n_inserted;
      }
      return n_inserted;
   }

   // Used for verification and testing the state of the organism
   cell_list_type get_live_cells() const {
      cell_list_type vec_items(cells_m.cbegin(), cells_m.cend());
      std::sort(vec_items.begin(), vec_items.end());
      return vec_items;
   }

   // Get the number of live neighbours surrounding a cell
   size_t get_num_live(cell_coord_type x, cell_coord_type y) const {
      return is_alive( WW(x-1, y-1) )
           + is_alive( WW(x-1, y  ) )
           + is_alive( WW(x-1, y+1) )
           + is_alive( WW(x  , y-1) )
           + is_alive( WW(x  , y+1) )
           + is_alive( WW(x+1, y-1) )
           + is_alive( WW(x+1, y  ) )
           + is_alive( WW(x+1, y+1) );
   }

   // Return the number of dead cells surrounding a cell
   // The cells themselves are returned in z
   size_t get_dead_cells(cell_coord_type x, cell_coord_type y, cell_whole_type* z) const {
      size_t n = 0;
      if (is_dead(WW(x-1, y-1))) z[n++] = WW(x-1, y-1);
      if (is_dead(WW(x-1, y  ))) z[n++] = WW(x-1, y  );
      if (is_dead(WW(x-1, y+1))) z[n++] = WW(x-1, y+1);
      if (is_dead(WW(x  , y-1))) z[n++] = WW(  x, y-1);
      if (is_dead(WW(x  , y+1))) z[n++] = WW(  x, y+1);
      if (is_dead(WW(x+1, y-1))) z[n++] = WW(x+1, y-1);
      if (is_dead(WW(x+1, y  ))) z[n++] = WW(x+1, y  );
      if (is_dead(WW(x+1, y+1))) z[n++] = WW(x+1, y+1);
      return n;
   }

   void tick() {
      cell_lookup_type new_cells;
      size_t ncells = cells_m.size();
      new_cells.reserve(ncells + ncells/4);

      // Stores the (up to 8) dead neighbour cells surrounding a cell
      cell_whole_type zcells[8];

      for (const auto& c : cells_m) {
         // Get the (up to 8) dead cells surrounding the cell
         size_t ndead = get_dead_cells(XX(c), YY(c), zcells);

         // Note: next line equivalent to nlive == 2 || nlive == 3
         if (ndead == 5 || ndead == 6) new_cells.insert(c);

         for (size_t i = 0; i < ndead; ++i) {
            if (get_num_live(XX(zcells[i]), YY(zcells[i])) == 3) new_cells.insert(zcells[i]);
         }
      }

      cells_m = std::move(new_cells);
   }

private:
   cell_lookup_type cells_m;
};

#endif /* ORGANISM_H */

##</code><code>##

// tbench1.cpp. Simple benchmark of Organism class.
// g++ compile on Linux:
//   g++ -o tbench1 -std=c++11 -Wall -O3 tbench1.cpp
// Note: the g++ command above also works with mingw C++ compiler (https://sourceforge.net/projects/mingw-w64)
// that comes bundled with Strawberry Perl (C:\Strawberry\c\bin\g++.exe)
// MSVC 2017 compile on Windows, start a 64-bit compiler cmdline via:
//   Start > AllApps > Visual Studio 2017 > x64 Native Tools Command Prompt for VS2017
// then:
//   cl /W3 /MT /Ox /EHsc tbench1.cpp

#include <cstdlib>
#include <ctime>
#include <string>
#include <iostream>
#include <fstream>
#include <sstream>

#include "Organism.h"

static bool is_file_exist(const char *fname) {
   std::ifstream infile(fname);
   return infile.good();
}

static Cell read_cell(const std::string& str) {
   cell_coord_type x, y;
   std::istringstream iss(str);
   iss >> x; iss >> y;
   return Cell(x, y);
}

// Reads a Life 1.06 text file
static cell_list_type read_cells_106(const char* fname) {
   cell_list_type cells;
   std::ifstream cellfile(fname);
   if (!cellfile) {
      std::cerr << "Error opening '" << fname << "'\n";
      return cells;
   }
   for (std::string line; std::getline(cellfile, line); ) {
      if (line.empty())   continue;    // ignore blank lines
      if (line[0] == '#') continue;    // ignore comment lines
      cells.push_back(read_cell(line));
   }
   return cells;
}

static void RunTest(const char* fname, int nticks)
{
   Organism org;
   {
      cell_list_type cells = read_cells_106(fname);
      org.insert_cells(cells);
      size_t ncells = org.count();
      std::cout << "cell count at start = " << ncells << "\n";
      if (ncells != cells.size()) { std::cerr << "oops cell count mismatch" << "\n"; }
   }
   std::cerr << "run benchmark for " << nticks << " ticks\n";
   time_t tstart = ::time(NULL);
   for (int i = 1; i <= nticks; ++i ) {
      org.tick();
   }
   time_t tend = ::time(NULL);
   long taken  = static_cast<long>(::difftime(tend, tstart) + 0.5);
   size_t ncells = org.count();
   std::cout << "cell count at end = " << ncells << "\n";
   std::cerr << "time taken " << taken << " secs\n";
}

int main(int argc, char* argv[])
{
   if (argc != 3) {
      std::cerr << "usage: tbench1 file nticks\n";
      return 1;
   }
   const char* fname = argv[1];
   if (!is_file_exist(fname)) {
      std::cerr << "File '" << fname << "' does not exist\n";
      return 1;
   }
   int nticks = ::atoi(argv[2]);
   if (nticks <= 0)
   {
      std::cerr << "'" << argv[2] << "'" << " invalid nticks\n";
      return 1;
   }
   RunTest(fname, nticks);
   return 0;
}

##</code><code>##

package Organism;

use strict;
use warnings;

sub count {
   my $self = shift;
   return scalar keys %{ $self->{Cells} };
}

sub is_alive {
   my $self = shift;
   return 0 + exists $self->{Cells}->{ join ':', @_ };
}

# Input a list of [ x, y ] coords
sub insert_cells {
   my $self = shift;
   for my $r (@_) { $self->{Cells}->{ join ':', @{$r} } = undef }
}

# Return sorted list of cells in the Organism.
# Used for verification and testing the state of the organism.
sub get_live_cells {
   my $self = shift;
   sort { $a->[0] <=> $b->[0] || $a->[1] <=> $b->[1] }
      map { [ split /:/, $_ ] }
      keys %{ $self->{Cells} };
}

# Return the list of dead cells surrounding a cell
sub get_dead_cells {
   my ( $self, $x, $y ) = @_;
   ( (join ':', $x - 1, $y - 1) x !$self->is_alive($x - 1, $y - 1),
     (join ':', $x - 1, $y    ) x !$self->is_alive($x - 1, $y    ),
     (join ':', $x - 1, $y + 1) x !$self->is_alive($x - 1, $y + 1),
     (join ':', $x    , $y - 1) x !$self->is_alive($x    , $y - 1),
     (join ':', $x    , $y + 1) x !$self->is_alive($x    , $y + 1),
     (join ':', $x + 1, $y - 1) x !$self->is_alive($x + 1, $y - 1),
     (join ':', $x + 1, $y    ) x !$self->is_alive($x + 1, $y    ),
     (join ':', $x + 1, $y + 1) x !$self->is_alive($x + 1, $y + 1) );
}

sub get_num_live {
   my ( $self, $x, $y ) = @_;
     $self->is_alive( $x - 1, $y - 1 )
   + $self->is_alive( $x - 1, $y     )
   + $self->is_alive( $x - 1, $y + 1 )
   + $self->is_alive( $x    , $y - 1 )
   + $self->is_alive( $x    , $y + 1 )
   + $self->is_alive( $x + 1, $y - 1 )
   + $self->is_alive( $x + 1, $y     )
   + $self->is_alive( $x + 1, $y + 1 );
}

sub tick {
   my $self = shift;
   my %new_cells;
   for my $c (keys %{ $self->{Cells} }) {
      # Get the (up to 8) dead cells surrounding the cell
      my @zcells = $self->get_dead_cells( split /:/, $c );

      # Check the live cell
      # Note: next line equivalent to nlive == 2 || nlive == 3
      @zcells == 5 || @zcells == 6 and $new_cells{$c} = undef;

      # Check the dead cells
      for my $z (@zcells) {
         $self->get_num_live( split /:/, $z ) == 3 and $new_cells{$z} = undef;
      }
   }
   $self->{Cells} = \%new_cells;
}

sub new {
   my $class = shift;
   my %init_self = ( Cells => {} );
   bless \%init_self, $class;
}

1;

##</code><code>##

# tbench1.pl - Simple benchmark of Organism class.
# Generate blinker test file with, for example:
#   perl createblinker.pl 500000 -900000 100 >x.tmp 2>y.tmp
# then run this script for two ticks, for example:
#   perl tbench1.pl x.tmp 2
use strict;
use warnings;
use Organism;

# XXX: To read Life 1.06 file, ignore leading line containing "#Life 1.06"
sub read_cells {
   my $fname = shift;
   open( my $fh, '<', $fname ) or die "error: open '$fname': $!";
   map { [ split ' ' ] } <$fh>;
}

@ARGV == 2 or die "usage: $0 file nticks\n";
my $file   = shift;
my $nticks = shift;
$nticks =~ /^\d+$/ or die "error: nticks ($nticks) not a number";
my $org = Organism->new();
{
   my @cells = read_cells($file);
   $org->insert_cells(@cells);
   my $ncells = $org->count();
   print "cell count at start = $ncells\n";
   $ncells == scalar(@cells) or die "oops";
}
warn "run benchmark for $nticks ticks\n";
my $tstart = time;
for my $i ( 1 .. $nticks ) {
   $org->tick();
}
my $tend = time;
my $taken = $tend - $tstart;
my $ncells = $org->count();
print "cell count at end = $ncells\n";
warn "time taken: $taken secs\n";

##</code><code>##

# Create blinker test data for load testing, e.g.:
#   perl createblinker.pl 500000 -100000 10 >x.tmp 2>y.tmp
# creates 500,000 * 3 blinker cells around y=10 starting at x=-100000
use strict;
use warnings;
sub blink {
   my $x = shift;
   my $y1 = shift;
   my $y2 = $y1 + 1; my $y3 = $y1 + 2;
   warn "$x $y1\n$x $y2\n$x $y3\n";
}
@ARGV == 3 or die "usage: $0 n xstart ystart\n";
my $n      = shift;
my $xstart = shift;
my $ystart = shift;
$n =~ /^\d+$/ or die "error: n not numeric";
$xstart =~ /^[-]?\d+$/ or die "error: xstart not numeric";
$ystart =~ /^[-]?\d+$/ or die "error: ystart not numeric";
my $x = $xstart;
my $y = $ystart;
my $gap = 3;    # $gap must be >= 3
for my $i ( 0 .. $n-1 ) {
   my $x1 = $x + $i; my $x2 = $x1 + 1; my $x3 = $x1 + 2;
   print "$x1 $y\n$x2 $y\n$x3 $y\n";
   blink( $x2, $y-1 );
   $x += $gap;
}

##</code><code>##

# tgol2.t - Simple blinker test of Conway Game of Life Organism class
# Generate file blinker.txt with:
#   perl createblinker.pl 3 100 10 >xtest.tmp 2>ytest.tmp
# then run this test with:
#   prove -v tgol2.t

use strict;
use warnings;
use Organism;
use Test::More;
my $nblinks = 5;
my $ntests = ( $nblinks + 1 ) * 3;
plan tests => $ntests;

# XXX: To read Life 1.06 file, ignore leading line containing "#Life 1.06"
sub read_cells {
   my $fname = shift;
   open( my $fh, '<', $fname ) or die "error: open '$fname': $!";
   map { [ split ' ' ] } <$fh>;
}

sub test_one {
   my $org = shift;
   my $desc = shift;
   my $expected = shift;
   my $nexpected = @{$expected};
   my $ncells = $org->count();
   my @cells = $org->get_live_cells();
   cmp_ok( $ncells, '==', $nexpected, "$desc cell count ($ncells)" );
   cmp_ok( scalar(@cells), '==', $nexpected, "$desc cell array count" );
   is_deeply( \@cells, $expected, "$desc cell array" );
}

# Blinker pattern
my @blinker1 = read_cells('xtest.tmp');
my @blinker2 = read_cells('ytest.tmp');
my @sblinker1 = sort { $a->[0] <=> $b->[0] || $a->[1] <=> $b->[1] } @blinker1;
my @sblinker2 = sort { $a->[0] <=> $b->[0] || $a->[1] <=> $b->[1] } @blinker2;

# Initialization
my $org = Organism->new();
$org->insert_cells(@sblinker1);
test_one( $org, "initial", \@sblinker1 );

# Pattern should just blink back and forth
for my $i ( 1 .. $nblinks ) {
   $org->tick();
   test_one( $org, "blinker $i", $i % 2 ? \@sblinker2 : \@sblinker1 );
}

##</code><code>##

# tgol.t - Simple blinker test of Conway Game of Life Organism class
use strict;
use warnings;
use Organism;
use Test::More;
my $nblinks = 5;
my $ntests = ( $nblinks + 1 ) * 3;
plan tests => $ntests;

sub test_one {
   my $org = shift;         # Organism handle
   my $desc = shift;        # Test description
   my $expected = shift;    # Array ref of (sorted) expected cells
   my $nexpected = @{$expected};
   my $ncells = $org->count();
   my @cells = $org->get_live_cells();
   cmp_ok( $ncells, '==', $nexpected, "$desc cell count ($ncells)" );
   cmp_ok( scalar(@cells), '==', $nexpected, "$desc cell array count" );
   is_deeply( \@cells, $expected, "$desc cell array" );
}

# Blinker pattern
my @blinker1 = (
   [ -101, -100 ], [ -100, -100 ], [  -99, -100 ],
   [ -101,  100 ], [ -100,  100 ], [  -99,  100 ],
   [   -1,    0 ], [    0,    0 ], [    1,    0 ],
   [   99, -100 ], [  100, -100 ], [  101, -100 ],
   [   99,  100 ], [  100,  100 ], [  101,  100 ],
);
my @blinker2 = (
   [ -100,  -99 ], [ -100, -100 ], [ -100, -101 ],
   [ -100,   99 ], [ -100,  100 ], [ -100,  101 ],
   [    0,   -1 ], [    0,    0 ], [    0,    1 ],
   [  100,  -99 ], [  100, -100 ], [  100, -101 ],
   [  100,   99 ], [  100,  100 ], [  100,  101 ],
);
my @sblinker1 = sort { $a->[0] <=> $b->[0] || $a->[1] <=> $b->[1] } @blinker1;
my @sblinker2 = sort { $a->[0] <=> $b->[0] || $a->[1] <=> $b->[1] } @blinker2;

# Initialization
my $org = Organism->new();
$org->insert_cells(@blinker1);
test_one( $org, "initial", \@sblinker1 );

# Pattern should just blink back and forth
for my $i ( 1 .. $nblinks ) {
   $org->tick();
   test_one( $org, "blinker $i", $i % 2 ? \@sblinker2 : \@sblinker1 );
}

##</code><code>##

# tbench1-infinite.pl - Simple benchmark.
# Uses Game::Life::Infinite::Board
use strict;
use warnings;
use Game::Life::Infinite::Board;

sub read_lines {
   my $fname = shift;
   open( my $fh, '<', $fname ) or die "error: open '$fname': $!";
   my @lines = <$fh>;
   return @lines;
}

@ARGV == 2 or die "usage: $0 file nticks\n";
my $file   = shift;
my $nticks = shift;
$nticks =~ /^\d+$/ or die "error: nticks ($nticks) not a number";
my $org = Game::Life::Infinite::Board->new();
{
   my @lines = read_lines($file);
   $org->loadL106(\@lines);
   my $ncells = $org->statistics->{'liveCells'};
   print "cell count at start = $ncells\n";
   $ncells == scalar(@lines) or die "oops";
}
warn "run benchmark for $nticks ticks\n";
my $tstart = time;
for my $i ( 1 .. $nticks ) {
   $org->tick();
}
my $tend = time;
my $taken = $tend - $tstart;
my $ncells = $org->statistics->{'liveCells'};
print "cell count at end = $ncells\n";
warn "time taken: $taken secs\n";