// implement basic life rules, with hashlife implementation
#include <cassert>
#include "HashLife.h"

#ifdef USE_HASH_MAP_LIFE
#include <hash_map>
#else
#include <map>
#endif


using namespace std;
using namespace stdext;


namespace { // anon
/* for speed we create a table that 
   given the 16 bits of a 4x4 cell 
		0123
		4567
		89AB
		CDEF
	returns the 4 next generation 
	cells for cells 56 and 9A
	*/

// todo - make a table for each used ruleset?

bool tableInitialized_ = false;
unsigned char bitTable[65536];
char popTable[65536]; // population delta for this transformation (+- 4)

void InitTable(void)
	{
	for (unsigned int val = 0; val < 65536; ++val)
		{
		// fill array with bits
		int arr[4][4];
		int temp = val;
		for (int i = 0; i < 16; ++i)
			{
			arr[i%4][i/4] = temp&1;
			temp >>= 1;
			}
		
		// now compute table entry
		unsigned char entry = 0;
		char popDelta = 0;
		for (int y = 1; y < 3; ++y)
			for (int x = 1; x < 3; ++x)
				{
				int neighbors = 0;
				for (int j = -1; j <= 1; ++j)
					for (int i = -1; i <= 1; ++i)
						{
						if ((0 == i) && (0 == j))
							continue;
						neighbors += arr[x+i][y+j];
						}

				bool alive = arr[x][y] != 0;
				if ((neighbors < 2) || (3 < neighbors))
					{
					if (true == alive)
						--popDelta;
					alive = false;
					}
				else if (3 == neighbors)
					{
					if (false == alive)
						++popDelta;
					alive = true;
					}

				entry >>= 1;
				if (true == alive)
					entry |= 8;
				}
		
		// store entrys
		bitTable[val] = entry;
		popTable[val] = popDelta;
		}
	tableInitialized_ = true;
	} // InitTable
	} // anon


#define STAT(a) a  // gather stats, slows slightly
// #define STAT(a) // define STAT to be ignored to improve performance slightly

// grow world, pushing root to an inner square
// pushes current universe to center of block twice as big
// increases level by 1
void HashLife::Expand(void)
	{
	Check(root_,level_);
	Node * zbq = zeroBlock_[level_-1];      // zero block 1/4 as big as root
	Node * zb0 = zeroBlock_[level_];        // zero block as big as root
	Node * zb1 = HashNode(zb0,zb0,zb0,zb0); // newer zero block 4x big as root
	zeroBlock_.push_back(zb1); 

	STAT(++stats_.expands_);

	root_ = HashNode(
		HashNode(zbq,zbq,zbq,root_->nw_),
		HashNode(zbq,zbq,root_->ne_,zbq),
		HashNode(zbq,root_->sw_,zbq,zbq),
		HashNode(root_->se_,zbq,zbq,zbq)
		);										
	level_ += 1;
	Check(root_,level_);
	} // Expand

// Given four node pointers to the Node quadrants, 
// find the hashed version. If not present, add it 
// to the hash and return that.
HashLife::Node * HashLife::HashNode(Node * nw, Node * ne, Node * sw, Node * se)
	{
	MapType::iterator iter;
	QuadPtr q(nw,ne,sw,se);
	iter = hashNodes_.find(q);
	if (hashNodes_.end() == iter)
		{ // not present, so add it
		hashNodes_[q] = Node(nw,ne,sw,se);
		iter = hashNodes_.find(q);
		iter->second.answer_ = 0;
		if (0 != nw)
			iter->second.population_ = 
				nw->population_ + ne->population_ + 
				sw->population_ + se->population_;
		assert(hashNodes_.end() != iter);
		STAT(++stats_.nodeMissed_);
		}
	else
		STAT(++stats_.nodeMatched_);
	STAT(++stats_.hashNodes_);
	return &(iter->second);
	} // HashNode

// given a node, and a level of that node, compute the center 
HashLife::Node * HashLife::NextGeneration(Node * node, int level)
	{
	if (0 != node->answer_)
		{
		STAT(++stats_.answered_);
		return node->answer_;
		}
	if ((level > 2) && (node == zeroBlock_[level]))
		{
		STAT(++stats_.zeroCutoff_);
		return zeroBlock_[level-1];
		}
	if (level >= 3)
		{ // recurse down
		// we need 9 nodes: n1,n2,n3 across, then next row, etc. for 3x3
		Node *n1, * n2, * n3, * n4, * n5, * n6, * n7, * n8, * n9;
		n1 = NextGeneration(node->nw_,level-1);
		n2 = NextGeneration(HashNode(node->nw_->ne_,node->ne_->nw_,node->nw_->se_,node->ne_->sw_),level-1);
		n3 = NextGeneration(node->ne_,level-1);
		n4 = NextGeneration(HashNode(node->nw_->sw_,node->nw_->se_,node->sw_->nw_,node->sw_->ne_),level-1);
		n5 = NextGeneration(HashNode(node->nw_->se_,node->ne_->sw_,node->sw_->ne_,node->se_->nw_),level-1);
		n6 = NextGeneration(HashNode(node->ne_->sw_,node->ne_->se_,node->se_->nw_,node->se_->ne_),level-1);
		n7 = NextGeneration(node->sw_,level-1);
		n8 = NextGeneration(HashNode(node->sw_->ne_,node->se_->nw_,node->sw_->se_,node->se_->sw_),level-1);
		n9 = NextGeneration(node->se_,level-1);

		Node * answer = HashNode(
			HashNode(n1->se_,n2->sw_,n4->ne_,n5->nw_), // nw corner of answer
			HashNode(n2->se_,n3->sw_,n5->ne_,n6->nw_), // ne corner of answer
			HashNode(n4->se_,n5->sw_,n7->ne_,n8->nw_), // sw corner of answer
			HashNode(n5->se_,n6->sw_,n8->ne_,n9->nw_)  // se corner of answer
			);
		node->answer_ = answer;
		return answer;
		}
	else
		{ // compute directly - 1x1 = level 0, 2x2 = level 1, 4x4  = level 2 case
		assert(2 == level); // this is only case we handle

		STAT(++stats_.tileComputes_);
#if 0
		// for now brute force it - todo - smarter later?
		const Node * n = node;
		int vals[4][4];
		vals[0][0] = Val(n->nw_->nw_);
		vals[1][0] = Val(n->nw_->ne_);
		vals[2][0] = Val(n->ne_->nw_);
		vals[3][0] = Val(n->ne_->ne_);
		
		vals[0][1] = Val(n->nw_->sw_);
		vals[1][1] = Val(n->nw_->se_);
		vals[2][1] = Val(n->ne_->sw_);
		vals[3][1] = Val(n->ne_->se_);

		vals[0][2] = Val(n->sw_->nw_);
		vals[1][2] = Val(n->sw_->ne_);
		vals[2][2] = Val(n->se_->nw_);
		vals[3][2] = Val(n->se_->ne_);

		vals[0][3] = Val(n->sw_->sw_);
		vals[1][3] = Val(n->sw_->se_);
		vals[2][3] = Val(n->se_->sw_);
		vals[3][3] = Val(n->se_->se_);

		int ans[2][2];
		for (int x = 1; x < 3; ++x)
			for (int y = 1; y < 3; ++y)
				{
				int nbr = 0;
				for (int i = -1; i <= 1; ++i)
					for (int j = -1; j <= 1; ++j)
						if ((0 != i) || (0 != j))
							nbr += vals[x+i][y+j];
				int alive = vals[x][y];
				/* rules
				< 2 neighbors -> dies
				> 3 -> dies
				=3 -> comes to life
				*/
				if ((nbr < 2) || (3 < nbr))
					alive = 0;
				if (3 == nbr)
					alive = 1;
				ans[x-1][y-1] = alive;
				}

		return HashNode(
			ValToNode(ans[0][0]),ValToNode(ans[1][0]),
			ValToNode(ans[0][1]),ValToNode(ans[1][1]));
#else // use faster table method
		const Node * n = node;
		unsigned int val = 0;
		val <<= 1; val |= Val(n->nw_->nw_);
		val <<= 1; val |=  Val(n->nw_->ne_);
		val <<= 1; val |=  Val(n->ne_->nw_);
		val <<= 1; val |=  Val(n->ne_->ne_);
		
		val <<= 1; val |=  Val(n->nw_->sw_);
		val <<= 1; val |=  Val(n->nw_->se_);
		val <<= 1; val |=  Val(n->ne_->sw_);
		val <<= 1; val |=  Val(n->ne_->se_);

		val <<= 1; val |=  Val(n->sw_->nw_);
		val <<= 1; val |=  Val(n->sw_->ne_);
		val <<= 1; val |=  Val(n->se_->nw_);
		val <<= 1; val |=  Val(n->se_->ne_);

		val <<= 1; val |=  Val(n->sw_->sw_);
		val <<= 1; val |=  Val(n->sw_->se_);
		val <<= 1; val |=  Val(n->se_->sw_);
		val <<= 1; val |=  Val(n->se_->se_);
		
		// todo - population?
		val = bitTable[val];

		return HashNode(
			ValToNode(val>>3),ValToNode((val>>2)&1),
			ValToNode((val>>1)&1),ValToNode((val)&1));
#endif
		}	
	} // NextGeneration

// given a node, and a level of that node, compute the center 2^(level-1) generations ahead
HashLife::Node * HashLife::NextGenerationSkip(Node * node, int level)
	{
	if (0 != node->answer_)
		{
		STAT(++stats_.answered_);
		return node->answer_;
		}
	if ((level > 2) && (node == zeroBlock_[level]))
		{
		STAT(++stats_.zeroCutoff_);
		return zeroBlock_[level-1];
		}
	if (level >= 3)
		{ // recurse down
		// we need 9 nodes: n1,n2,n3 across, then next row, etc. for 3x3
		Node *n1, * n2, * n3, * n4, * n5, * n6, * n7, * n8, * n9;
		n1 = NextGenerationSkip(node->nw_,level-1);
		n2 = NextGenerationSkip(HashNode(node->nw_->ne_,node->ne_->nw_,node->nw_->se_,node->ne_->sw_),level-1);
		n3 = NextGenerationSkip(node->ne_,level-1);
		n4 = NextGenerationSkip(HashNode(node->nw_->sw_,node->nw_->se_,node->sw_->nw_,node->sw_->ne_),level-1);
		n5 = NextGenerationSkip(HashNode(node->nw_->se_,node->ne_->sw_,node->sw_->ne_,node->se_->nw_),level-1);
		n6 = NextGenerationSkip(HashNode(node->ne_->sw_,node->ne_->se_,node->se_->nw_,node->se_->ne_),level-1);
		n7 = NextGenerationSkip(node->sw_,level-1);
		n8 = NextGenerationSkip(HashNode(node->sw_->ne_,node->se_->nw_,node->sw_->se_,node->se_->sw_),level-1);
		n9 = NextGenerationSkip(node->se_,level-1);

		// use this to compute a second generation 
		Node * nw, * ne, * sw, * se;
		nw = NextGenerationSkip(HashNode(n1,n2,n4,n5),level-1);
		ne = NextGenerationSkip(HashNode(n2,n3,n5,n6),level-1);
		sw = NextGenerationSkip(HashNode(n4,n5,n7,n8),level-1);
		se = NextGenerationSkip(HashNode(n5,n6,n8,n9),level-1);

		// final answer
		Node * answer = HashNode(nw,ne,sw,se);
		node->answer_ = answer;
		return answer;
		}
	else
		{ // compute directly - 1x1 = level 0, 2x2 = level 1, 4x4  = level 2 case
		assert(2 == level); // this is only case we handle

		// for now brute force it - todo - smarter later?
		const Node * n = node;
		int vals[4][4];
		vals[0][0] = Val(n->nw_->nw_);
		vals[1][0] = Val(n->nw_->ne_);
		vals[2][0] = Val(n->ne_->nw_);
		vals[3][0] = Val(n->ne_->ne_);
		
		vals[0][1] = Val(n->nw_->sw_);
		vals[1][1] = Val(n->nw_->se_);
		vals[2][1] = Val(n->ne_->sw_);
		vals[3][1] = Val(n->ne_->se_);

		vals[0][2] = Val(n->sw_->nw_);
		vals[1][2] = Val(n->sw_->ne_);
		vals[2][2] = Val(n->se_->nw_);
		vals[3][2] = Val(n->se_->ne_);

		vals[0][3] = Val(n->sw_->sw_);
		vals[1][3] = Val(n->sw_->se_);
		vals[2][3] = Val(n->se_->sw_);
		vals[3][3] = Val(n->se_->se_);

		int ans[2][2];
		for (int x = 1; x < 3; ++x)
			for (int y = 1; y < 3; ++y)
				{
				int nbr = 0;
				for (int i = -1; i <= 1; ++i)
					for (int j = -1; j <= 1; ++j)
						if ((0 != i) || (0 != j))
							nbr += vals[x+i][y+j];
				int alive = vals[x][y];
				/* rules
				< 2 neighbors -> dies
				> 3 -> dies
				=3 -> comes to life
				*/
				if ((nbr < 2) || (3 < nbr))
					alive = 0;
				if (3 == nbr)
					alive = 1;
				ans[x-1][y-1] = alive;
				}

		return HashNode(
			ValToNode(ans[0][0]),ValToNode(ans[1][0]),
			ValToNode(ans[0][1]),ValToNode(ans[1][1]));
		}	
	} // NextGenerationSkip


// return true if the board needs expanded
// i.e., the outer row of cells from the center 1/4 
// are non-empty
bool HashLife::NeedsExpanded(void)
	{
	if (level_ < 3)
		return true; // make it this big to access nodes
	Node * z = zeroBlock_[level_-3]; // should be wrapped with these
	if (root_->nw_->se_->sw_ != z)
		return true;
	if (root_->nw_->se_->nw_ != z)
		return true;
	if (root_->nw_->se_->ne_ != z)
		return true;
	if (root_->ne_->sw_->nw_ != z)
		return true;
	if (root_->ne_->sw_->ne_ != z)
		return true;
	if (root_->ne_->sw_->se_ != z)
		return true;
	if (root_->se_->nw_->ne_ != z)
		return true;
	if (root_->se_->nw_->se_ != z)
		return true;
	if (root_->se_->nw_->sw_ != z)
		return true;
	if (root_->sw_->ne_->se_ != z)
		return true;
	if (root_->sw_->ne_->sw_ != z)
		return true;
	if (root_->sw_->ne_->nw_ != z)
		return true;
	return false;
	} // NeedsExpanded

void HashLife::NextGeneration(void)
	{
	Check(root_,level_);
	if (NeedsExpanded())
		Expand();

	Node * center;

	if (false == hyperspeed_)
		{ // do one generation
		++generation_;
		center = NextGeneration(root_,level_);
		}
	else
		{ // do 2^(n-1) generations, where n = level_ of root_
		__int64 temp = 1;
		temp <<= (level_-1);
		generation_ += temp;
		center = NextGenerationSkip(root_,level_);
		}
	
	// reassemble universe
	root_->nw_ = HashNode(root_->nw_->nw_,root_->nw_->ne_,root_->nw_->sw_,center->nw_);
	root_->ne_ = HashNode(root_->ne_->nw_,root_->ne_->ne_,center->ne_,root_->ne_->se_);
	root_->sw_ = HashNode(root_->sw_->nw_,center->sw_,root_->sw_->sw_,root_->sw_->se_);
	root_->se_ = HashNode(center->se_,root_->se_->ne_,root_->se_->sw_,root_->se_->se_);
	root_ = HashNode(root_->nw_, root_->ne_, root_->sw_, root_->se_);
	} // NextGeneration

// recursively construct a new universe while going down to set a cell
HashLife::Node * HashLife::SetCell(int i, int j, Node * node, int lvl, bool set)
	{
	Check(root_,level_);
	static const int cutoff = 32; // any levels below this move (i,j) as needed
	int dx = i, dy = j; // for determining quadrant to move to
	// default nodes
	Node * nw = node->nw_, * ne = node->ne_, * sw = node->sw_, * se = node->se_;
	if (lvl > 1)
		{ // zooming down to cell
		int delta = 0; // amount to move i,j when in range
		if (lvl <= cutoff)
			{  // in range, so we modify i,j for the next pass
			delta = (1<<(lvl-2));
			int width = (1<<lvl);
			assert((-width <= i) && (i < width)); // we must be in bounds here
			assert((-width <= j) && (j < width)); // todo - do asserts work at lvl == cutoff?
			}
		if (i >= 0) 
			i -= delta;
		else
			i += delta;
		if (j >= 0) 
			j -= delta;
		else
			j += delta;
		if ((node != root_) && (lvl >= cutoff-2))
			{ // go reverse direction to zoom to middle, except at root
			dx = -dx;
			dy = -dy;
			}
		--lvl; // drop a level
		if ((dx >= 0) && (dy >= 0))
			se = SetCell(i,j,se,lvl,set);
		else if ((dx >= 0) && (dy < 0))
			ne = SetCell(i,j,ne,lvl,set);
		else if ((dx < 0) && (dy >= 0))
			sw = SetCell(i,j,sw,lvl,set);
		else 
			nw = SetCell(i,j,nw,lvl,set);
		}
	else 
		{ // final value to set // lvl 1 is 2x2 cell
		assert(1 == lvl);
		Node * val;
		if (true == set) 
			val = oneCell_;
		else 
			val = zeroCell_;
		if ((dx >= 0) && (dy >= 0))
			se = val;
		else if ((dx >= 0) && (dy < 0))
			ne = val;
		else if ((dx < 0) && (dy >= 0))
			sw = val;
		else 
			nw = val;
		}
	return HashNode(nw,ne,sw,se);
	} // SetCell

void HashLife::SetValue(int i, int j, unsigned char value)
	{
	Check(root_,level_);
	// todo -= expand universe if not big enough
	// recurse down and set the value, while rebuilding the universe
	root_ = SetCell(i,j,root_,level_,0 != value);
	} // SetValue


// recursively seek down to find a cell value
unsigned char HashLife::GetCell(int i, int j, Node * node, int lvl) const
	{
	Check(root_,level_);
	static const int cutoff = 32; // any levels below this move (i,j) as needed
	int dx = i, dy = j; // for determining quadrant to move to
	// node we will zoom in on
	Node * nn;
	if (lvl > 1)
		{ // zooming down to cell
		int delta = 0; // amount to move i,j when in range
		if (lvl <= cutoff)
			{  // in range, so we modify i,j for the next pass
			delta = (1<<(lvl-2));
			int width = (1<<lvl);
			assert((-width <= i) && (i < width)); // we must be in bounds here
			assert((-width <= j) && (j < width)); // todo - do asserts work at lvl == cutoff?
			}
		if (i >= 0) 
			i -= delta;
		else
			i += delta;
		if (j >= 0) 
			j -= delta;
		else
			j += delta;
		if ((node != root_) && (lvl >= cutoff-2))
			{ // go reverse direction to zoom to middle, except at root
			dx = -dx;
			dy = -dy;
			}
		--lvl; // drop a level
		if ((dx >= 0) && (dy >= 0))
			nn = node->se_;
		else if ((dx >= 0) && (dy < 0))
			nn = node->ne_;
		else if ((dx < 0) && (dy >= 0))
			nn = node->sw_;
		else 
			nn = node->nw_;
		}
	else
		{ // final value to get // lvl 1 is 2x2 cell
		assert(1 == lvl);
		if ((dx >= 0) && (dy >= 0))
			return Val(node->se_);
		else if ((dx >= 0) && (dy < 0))
			return Val(node->ne_);
		else if ((dx < 0) && (dy >= 0))
			return Val(node->sw_);
		else 
			return Val(node->nw_);
		}
	return GetCell(i,j,nn,lvl);
	} // GetCell

// get or set value at cell (i,j)
unsigned char HashLife::GetValue(int i, int j) const
	{
	Check(root_,level_);
	return GetCell(i,j,root_,level_);
	} // GetValue

// recursively draw universe
// nx, ny are cell coords of upper left of current node
void HashLife::DrawNode(
			Node * node, int lvl, // node to draw, and level of node
			int nodeX, int nodeY  // upper left corner of node in cells
			)
	{
	// clip zero node
	if (node == zeroBlock_[lvl])
		{
		STAT(++stats_.zeroDraw_);
		return; // nothing to draw
		}

	static const int cutoff = 29; // any level bigger than this zooms to center
	if (lvl > cutoff) // todo - right value?
		{
		// zoom to center
		Node n(node->nw_->se_,node->ne_->sw_,node->sw_->ne_,node->se_->nw_);
		DrawNode(&n,lvl-1,nodeX,nodeY);
		return;
		}
	else if (lvl == cutoff)
		nodeX = nodeY = -(1<<lvl); // this is upper left corner in cells

	// width of node in cells 
	int nodeSize = (1<<lvl);

	// clip out of bounds
	if ((nodeX + nodeSize < drawData_.x1_) || (drawData_.x2_ < nodeX) ||
		(nodeY + nodeSize < drawData_.y1_) || (drawData_.y2_ < nodeY))
		return; // nothing to do - out of bounds

	if (lvl > drawData_.imgDepth_)
		{ // recurse down
		int cx  = nodeX + (nodeSize+1)/2; // center of node
		int cy  = nodeY + (nodeSize+1)/2; 
		DrawNode(node->nw_,lvl-1,nodeX,nodeY);
		DrawNode(node->ne_,lvl-1,cx,nodeY);
		DrawNode(node->sw_,lvl-1,nodeX,cy);
		DrawNode(node->se_,lvl-1,cx,cy);
		}
	else if ((drawData_.x1_ <= nodeX) && (nodeX + nodeSize <= drawData_.x2_) && 
			 (drawData_.y1_ <= nodeY) && (nodeY + nodeSize <= drawData_.y2_))
		{ // draw to screen if onscreen
		int xpos, ypos; // pixel locations

		xpos = (nodeX - drawData_.x1_) * drawData_.pixelsPerCell_ / drawData_.cellsPerPixel_;
		ypos = (nodeY - drawData_.y1_) * drawData_.pixelsPerCell_ / drawData_.cellsPerPixel_;

		unsigned char * ptr = drawData_.buffer_ + xpos * 3 + ypos * drawData_.stride_;

		for (int y = 0; y < drawData_.pixelsPerCell_; ++y)
			{
			for (int x = 0; x < drawData_.pixelsPerCell_; ++x)
				{
				*ptr++ = drawData_.b_;
				*ptr++ = drawData_.g_;
				*ptr++ = drawData_.r_;
				}
			ptr = ptr + drawData_.stride_ - drawData_.pixelsPerCell_*3;
			}
		}
	} // DrawNode



// takes RGB buffer, stride, image width, height, and color to draw r,g,b
// and viewport
void HashLife::DrawBuffer(Viewport & vp, unsigned char * buffer, int stride, int width, int height,
				unsigned char r, unsigned char g, unsigned char b)
	{
	int cellsPerPixel , pixelsPerCell, depth;
	vp.GetZoom(cellsPerPixel, pixelsPerCell);
	depth = cellsPerPixel;
	pixelsPerCell = 1<<pixelsPerCell; // width of a cell in pixels -- todo - rename these
	cellsPerPixel = 1<<cellsPerPixel; // cells wide per pixel

	// set global drawing parameters
	drawData_.buffer_ = buffer;
	drawData_.stride_ = stride;
	drawData_.cellsPerPixel_ = cellsPerPixel;
	drawData_.pixelsPerCell_ = pixelsPerCell;
	drawData_.imgDepth_ = depth;
	drawData_.r_ = r;
	drawData_.g_ = g;
	drawData_.b_ = b;

	// view goes over cell coords, x1,y1 to x2,y2
	vp.GetViewportWorldCoords(width,height,drawData_.x1_,drawData_.y1_,drawData_.x2_,drawData_.y2_);

	// upper left corner of universe (if overflows, it gets fixed in DrawNode)
	int nodeX, nodeY;
	nodeX = nodeY = -(1<<(level_-1));

	// recursively draw universe
	DrawNode(root_,level_, nodeX, nodeY);

	} // DrawBuffer

// debugging function, asserts if error found
void HashLife::Check(const Node * node, int level) const
	{
#if 0// def _DEBUG
	if (0 == level)
		{
		assert((node == oneCell_) || (node == zeroCell_));
		}
	else if (0 < level)
		{
		assert(node->nw_ != 0);
		assert(node->ne_ != 0);
		assert(node->sw_ != 0);
		assert(node->se_ != 0);
		Check(node->nw_,level-1);
		Check(node->ne_,level-1);
		Check(node->sw_,level-1);
		Check(node->se_,level-1);
		}
#endif
	} // Check

// recursively construct a new universe while setting all cells
// nx, ny are cell coords of upper left of current node
HashLife::Node * HashLife::SetBuffer(Node * node, int lvl, int nx, int ny, unsigned char * buffer, int width, int height)
	{
	if ((nx > width) || (ny > height))
		return node; // nothing to do - out of bounds

	static const int cutoff = 32; // any levels below this move (i,j) as needed
	Node * nw = node->nw_, * ne = node->ne_, * sw = node->sw_, * se = node->se_;

	if (lvl >= cutoff)
		return HashNode(SetBuffer(nw,lvl-1,nx,ny,buffer,width,height),ne,sw,se);

	if (lvl > 1)
		{ // recurse down to cell
		int cx = (1<<(lvl-1)) + nx; // center of node
		int cy = (1<<(lvl-1)) + ny; 

		return HashNode(
			SetBuffer(nw,lvl-1,nx,ny,buffer,width,height),
			SetBuffer(ne,lvl-1,cx,ny,buffer,width,height),
			SetBuffer(sw,lvl-1,nx,cy,buffer,width,height),
			SetBuffer(ne,lvl-1,cx,cy,buffer,width,height)
			);

		}
	else 
		{ // lvl 1 is 2x2 cell, nx, ny is upper left corner in buffer, set each value
		assert(1 == lvl);
		int nw = 0, ne = 0, sw = 0, se = 0;
		nw = buffer[nx + ny*width];
		if (nx + 1 < width)
			ne = buffer[nx + 1 + ny*width];
		if (ny + 1 < height)
			sw = buffer[nx + (ny + 1)*width];
		if ((nx + 1 < width) && (ny + 1 < height))
			se = buffer[nx + 1 + (ny + 1)*width];
		return HashNode(
			ValToNode(nw),
			ValToNode(ne),
			ValToNode(sw),
			ValToNode(se)
			);
		}
	return node; // todo - should never get here
	} // SetBuffer


// fast block load
void HashLife::LoadBuffer(unsigned char * buffer, int width, int height)
	{
#if 1  // todo - remove
	// copy to larger buffer, sizes multiple of 32 - 
	// we need this to avoid some weird noise bug
	// todo - find and fix other bug, and remove this
	vector<unsigned char> buf2;
	int w2 = width + (32-(width&31))+31,
		h2 = height + (32-(height&31))+31;
	buf2.resize(w2*h2);
	for (int y = 0; y < height-1; ++y)
		memcpy(&buf2[y*w2],buffer+y*width,width);

	width  = w2;
	height = h2;
	buffer = &buf2[0];
#endif
	Reset(); // remove previous noise in map
	while ( ((1<<(level_-2)) < width) || ((1<<(level_-2)) < height) )
		Expand(); // make big enough
	root_ = zeroBlock_[level_]; // zero out universe
	// todo - center image
	root_ = HashNode(
		root_->nw_,
		root_->ne_,
		root_->sw_,
		SetBuffer(root_->se_,level_-1,0,0,buffer,width,height)
		);
	} // LoadBuffer

// set to true to use generation changes, else use normal
void HashLife::SetHyperspeed(bool set)
	{
	if (hyperspeed_ != set)
		{ // change state, first remove answer pointers
		MapType::iterator iter = hashNodes_.begin();
		while (iter != hashNodes_.end())
			{
			iter->second.answer_ = 0;
			++iter;
			}
		hyperspeed_ = set;
		}
	} // SetHyperspeed

void HashLife::Reset(void)
	{
	hashNodes_.clear();
	zeroBlock_.clear();
	stats_.Reset();
	population_ = 0;
	generation_ = 0;
	Node * n = reinterpret_cast<Node*>(1);
	zeroCell_ = HashNode(0,0,0,0); // the 0 cell
	oneCell_  = HashNode(0,n,n,n); // the 1 cell
	zeroCell_->population_ = 0;
	oneCell_->population_  = 1;
	zeroBlock_.push_back(zeroCell_); // the 1x1 zero block
	Node * z2 = HashNode(zeroCell_,zeroCell_,zeroCell_,zeroCell_);
	zeroBlock_.push_back(z2); // 2x2 zeroed
	root_ = z2; // 2x2 universe, zeroed
	level_ = 1; // 2x2 universe

	// expand 
	for (int pos = 0; pos < 10; ++pos)
		Expand(); 

	// Create glider for testing
//	SetValue(1,0,1);
//	SetValue(2,1,1);
//	SetValue(0,2,1);
//	SetValue(1,2,1);
//	SetValue(2,2,1);

	Check(root_,level_);

	// test Set and Get
#if 0 // #ifdef _DEBUG
	for (int pos = 0; pos < 1000; ++pos)
		{
		int x = (rand()&63)-32;
		int y = (rand()&63)-32;
		int val = rand()&1;
		SetValue(x,y,val);
		assert(val == GetValue(x,y));
		}
#endif
	} // Reset

HashLife::HashLife(void) : 		
		wraps_(true), population_(0),
		zeroCell_(0), oneCell_(0),
		generation_(0), root_(0), level_(0),
		hyperspeed_(false)

	{
	if (false == tableInitialized_)
		InitTable();
	Reset();
	}

// end - HashLife.cpp