// implement basic life rules, with a sparse implementation
#include <vector>
#include <algorithm>
#include "SparseLife.h"

using namespace std;

namespace {

bool aliveTbl[512];
int popTbl[512];
bool init = false;
void MakeTable(void)
	{
	init = true;
	for (int ind = 0; ind < 512; ++ind)
		{
		int index = ind;
		int nbr = 0; // neighbors
		int popDelta = 0;
		for (int b = 0; b < 4; ++b)
			{
			nbr += index&1;
			index >>= 1;
			}
		bool alive = 0 != (index&1);
		index >>= 1;
		for (int b = 0; b < 4; ++b)
			{
			nbr += index&1;
			index >>= 1;
			}

		/* rules
		< 2 neighbors -> dies
		> 3 -> dies
		=3 -> comes to life
		*/
		if ((nbr < 2) || (3 < nbr))
			{
			if (alive) 
				--popDelta;
			alive = false;
			}
		else if (3 == nbr)
			{
			if (false == alive) 
				++popDelta;
			alive = true;
			}
		aliveTbl[ind] = alive;
		popTbl[ind] =popDelta;
		}
	} // MakeTable


// given a 9 bit image, compute the life state of the middle one
bool Alive(unsigned int index1, int & popDelta)
	{
	popDelta = popTbl[index1];
	return aliveTbl[index1];
	} // Alive

	} // anon

void SparseLife::NextGeneration(void)
	{
	if (false == init)
		MakeTable();
	// todo - do population counting

	++generation_;
	int w = width_;
	int h = height_;
	if (tempRow1_.size() != w)
		{ // resize temp rows
		tempRow1_.resize(w);
		tempRow2_.resize(w);
		}

	Row * tempRow;

	// do all cells
	for (int y = 0; y < h; ++y)
		{
		// todo - this is wraparound - make other version also
		const Row & r1 = rows_[(y-1+h)%h]; // back one
		const Row & r2 = rows_[y];         // current
		const Row & r3 = rows_[(y+1)%h];   // next one
		int i1 = 0, i2 = 0, i3 = 0;        // row indices
		int rowPos = 0;                    // index into tempRow

		unsigned long bmpIndex = 0;        // todo - needs set for wraparound

		// replace rows
		if (0 == (y&1))
			{ // even rows
			if (0 != y)
				swap(rows_[y-2],tempRow1_);	// replace even rows
			tempRow = &tempRow1_;
			}
		else
			{ // odd rows
			if (1 != y)
				swap(rows_[y-2],tempRow2_);	// replace odd rows
			tempRow = &tempRow2_;
			}

		int x = 0;
		while (x < w)
			{
			// find left most cell
			x = r1[i1];
			if (x > r2[i2])
				x = r2[i2];
			if (x > r3[i3])
				x = r3[i3];
			while (x < w)
				{ // scan right until no image left to draw
				if (x == r1[i1])
					{
					bmpIndex |= 0400;
					++i1;
					}
				if (x == r2[i2])
					{
					bmpIndex |= 0200;
					++i2;
					}
				if (x == r3[i3])
					{
					bmpIndex |= 0100;
					++i3;
					}
				if (000 == bmpIndex)
					break;
				// store
				int delta;
				if (true == Alive(bmpIndex,delta))
					(*tempRow)[rowPos++] = x - 1;
				population_ += delta;

				// shift 3x3 bitmap
				bmpIndex >>= 3;
				++x;			
				}  // while nearby pixels != 0 and x < w
			}
		(*tempRow)[rowPos] = INT_MAX; // end of row
		}

	// todo - replace last two rows?



	} // NextGeneration

// call after setting values - converts to internal format
void SparseLife::ConvertToInternal(void)
	{
	for (int y = 0; y < height_; ++y)
		{
		Row & row = rows_[y];
		int pos = 0;
		for (int x = 0; x < width_; ++x)
			{
			if (0 != board_[x+y*width_])
				row[pos++] = x;
			}
		row[pos++] = INT_MAX; // end of line
		}
	} // ConvertToInternal

// call before drawing or reading values - converts internal to fast read format
void SparseLife::ConvertToExternal(void)
	{
	memset(&board_[0],0,width_*height_); // zero out
	for (int y = 0; y < height_; ++y)
		{
		Row & row = rows_[y];
		for (int i = 0; row[i] < INT_MAX; ++i)
			{
			int x = row[i];
			board_[x + y*width_] = 1;
			}
		}
	} // ConvertToExternal


// takes RGB buffer, stride, image width, height, and color to draw r,g,b
// and viewport
void SparseLife::DrawBuffer(Viewport & vp, unsigned char * buffer, int stride, int width, int height,
				unsigned char r, unsigned char g, unsigned char b)
	{
	int numerator, denominator;
	vp.GetZoom(numerator, denominator);
	int cellWidth = 1<<denominator; // width of a cell in pixels
	int cellSkip  = 1<<numerator;   // cells wide per pixel

	// x,y goes over cell coords, x1,y1 to x2,y2
	int x1, y1, x2, y2;
	vp.GetViewportWorldCoords(width,height,x1,y1,x2,y2);

	// scan over dest pixels
	for (int j = 0; j+cellWidth < height; j += cellWidth)
		{
		unsigned char * ptr = buffer + j*stride;
		for (int i = 0; i+cellWidth < width; i += cellWidth)
			{
			bool alive = false;

			// walk relevant cells to see if any alive
			for (int y = 0; y < cellSkip; ++y)
				for (int x = 0; x < cellSkip; ++x)
					{
					int xpos = x1 + x + i * cellSkip / cellWidth;
					int ypos = y1 + y + j * cellSkip / cellWidth;
					if ((0 <= xpos) && (xpos < width_) && (0 <= ypos) && (ypos < height_))
						alive |= (GetValue(xpos,ypos) != 0);
					}

				// draw cell if alive
				if (false == alive)
					ptr += cellWidth*3;
				else
					{
					for (int y = 0; y < cellWidth; ++y)
						{
						for (int x = 0; x < cellWidth; ++x)
							{
							*ptr++ = r;
							*ptr++ = g;
							*ptr++ = b;
							}
						ptr = ptr + stride - cellWidth*3;
						}
					ptr = ptr - cellWidth*stride + cellWidth*3;
					}
			}
		}
	} // DrawBuffer



// end - SparseLife.cpp