// implement basic life rules, with hashlife implementation
#ifndef HASH_LIFE_H
#define HASH_LIFE_H

#define USE_HASH_MAP_LIFE // define to use hash_map if provided, else uses map
#ifdef USE_HASH_MAP_LIFE
#include <hash_map>
#else
#include <map>
#endif
#include <vector>
#include <cassert>
#include "Life.h"

class HashLife : public LifeSimulator
	{
public:
	__int64 CountPopulation(void)
		{
		population_ = 0;
		for (int j = 0; j < height_; ++j)
			for (int i = 0; i < width_; ++i)
				if (0 != GetValue(i,j))
					++population_;
		return population_;
		}

	__int64 GetGeneration(void)
		{
		return generation_;
		}
	void Reset(void);
	// get or set value at cell (i,j)
	unsigned char GetValue(int i, int j) const;
	void SetValue(int i, int j, unsigned char value);

	void NextGeneration(void);

	__int64 GetPopulation(void) const
		{
		if (0 != root_)
			return root_->population_;
		return 0;
		}
	void SetPopulation(__int64 pop)
		{
		population_ = pop;
		}

	void SetSize(int width, int height)
		{ // nonsense fo hashlife
		}

	void GetSize(int & width, int & height) const
		{ // compute based on level	(return positive quadrant)
		width = height = 1UL<<(level_-1);
		}

	bool GetWraparound(void) const
		{
		return wraps_;
		}
	void SetWraparound(bool wrap)
		{
		wraps_ = wrap;
		}

	// loading from a buffer much faster than from SetValue loop
	bool UsesLoadBuffer(void) {return true; }
	void LoadBuffer(unsigned char * buffer, int width, int height);

	// takes RGB buffer, stride, image width, height, and color to draw r,g,b
	// and viewport
	void DrawBuffer(Viewport & vp, unsigned char * buffer, int stride, int width, int height,
					unsigned char r, unsigned char g, unsigned char b);

	// set to true to use generation changes, else use normal
	void SetHyperspeed(bool set);


	HashLife(void);

	// gather some stats for reporting
	struct Stats
		{
		__int64 nodeMatched_;  // hash matches
		__int64 nodeMissed_;   // hash misses
		__int64 hashNodes_;    // number of nodes
		__int64 tileComputes_; // tiles needed direct computations

		__int64 expands_;      // number of expansions
		__int64 answered_;     // answers reused
		__int64 zeroCutoff_;   // cutoffs using the zero block lookup
		__int64 zeroDraw_;     // cutoffs while drawing using zero block skip

		void Reset(void)
			{
			nodeMatched_ = 0;  // hash matches
			nodeMissed_ = 0;   // hash misses
			hashNodes_ = 0;    // number of nodes
			tileComputes_ = 0; // tiles needed direct computations
			expands_ = 0;   
			answered_ = 0;  
			zeroCutoff_ = 0;
			zeroDraw_ = 0;  
			}
		} stats_;


private:
	struct Node
		{
		Node * nw_, * ne_, * sw_, * se_; // quadrants
		Node * answer_;         // answer to next gen center node
		__int64 population_;
		Node(void) {}; //default zeroes out all
		// construct node with given pointers
		Node(Node * nw, Node * ne, Node * sw, Node * se) :
			nw_(nw), ne_(ne), sw_(sw), se_(se)
			{
			}
		};

	Node * root_;               // root of the entire tree
	int level_;                 // depth of root, leaves are level 0

	Node * zeroCell_, * oneCell_;   // canonical nodes to the 0 and 1 cells
	std::vector<Node *> zeroBlock_; // zero blocks for each depth level

	int width_, height_;        // size of board
	__int64 population_;
	__int64 generation_;
	bool wraps_; // todo - nonsense in this case
	bool hyperspeed_; // true to use generation skipping routines

	// Given four node pointers to the Node quadrants, 
	// find the hashed version. If not present, add it 
	// to the hash and return that.
	// todo - const?
	Node * HashNode(Node * nw, Node * ne, Node * sw, Node * se);

	// given a node, and a level of that node, compute the center 
	Node * NextGeneration(Node * node, int level);

	// given a node, and a level of that node, compute the center 2^(level-1) generations ahead
	Node * HashLife::NextGenerationSkip(Node * node, int level);


	// grow world, pushing root to an inner square
	// pushes current universe to center of block twice as big
	// increases level by 1
	void Expand(void);

	// return true if the board needs expanded
	// i.e., the outer row of cells from the center 1/4 
	// are non-empty
	bool NeedsExpanded(void);

	// recursively construct a new universe while going down to set a cell
	Node * SetCell(int i, int j, Node * node, int lvl, bool set);
	// recursively seek down to find a cell value
	unsigned char GetCell(int i, int j, Node * node, int lvl) const;


	// helpers - todo - comment
	int Val(const Node * a) const
		{
		assert((a==oneCell_) || (a == zeroCell_));
		if (oneCell_ == a)
			return 1;
		return 0;
		}
	Node * ValToNode(int val) const
		{
		if (0 != val)
			return oneCell_;
		return zeroCell_;
		}

	// debugging function, asserts if error found
	void Check(const Node * node , int level) const;

	// recursively construct a new universe while setting all cells
	// nx, ny are cell coords of upper left of current node
	// buffer, width, height define the image to place in the universe
	Node * SetBuffer(Node * node, int lvl, int nx, int ny, unsigned char * buffer, int width, int height);

	// recursively draw universe
	// nx, ny are cell coords of upper left of current node
	void DrawNode(
		Node * node, int lvl, // node to draw, and level of node
		int nodeX, int nodeY  // upper left corner of node in cells
		);


	// global data for drawing
	struct DrawData
		{
		unsigned char * buffer_;  // RGB surface to draw to
		int stride_;              // surface stride
		int x1_,y1_;              // upper left corner of view in cells
		int x2_,y2_;              // lower right corner of view in cells
		int pixelsPerCell_;       // pixels to draw one cell, >= 1
		int cellsPerPixel_;       // cells represented in a pixel, >= 1
		unsigned char r_, g_, b_; // color to draw
		int imgDepth_;            // draw depth - is log_2(cellsPerPixel)
		} drawData_;


	// for hashing on the pointers in a node
	struct QuadPtr
		{
		Node * nw_, * ne_, * sw_, * se_; // quadrants
		// constructor
		QuadPtr(Node * nw, Node * ne, Node * sw, Node * se) :
			nw_(nw), ne_(ne), sw_(sw), se_(se)
			{
			}
		// comparison for map
		bool operator<(const QuadPtr & right) const
			{
			if (nw_ < right.nw_) return true;
			if (nw_ > right.nw_) return false;
			if (ne_ < right.ne_) return true;
			if (ne_ > right.ne_) return false;
			if (sw_ < right.sw_) return true;
			if (sw_ > right.sw_) return false;
			if (se_ < right.se_) return true;
			if (se_ > right.se_) return false;
			return false; // must be equal
			}
		};

#ifdef USE_HASH_MAP_LIFE
	struct QuadHashCompare : public stdext::hash_compare<HashLife::QuadPtr>
		{
		bool operator()(const QuadPtr & x, const QuadPtr & y) const 
			{ // comparison, for when hashing yields the same value
			return x < y;
			}
		// hash the item using FNV hashing
		size_t operator()(const QuadPtr & q) const
			{
			/* for 32 bit, 32 bit FNV_prime = 16777619, 32 bit offset_basis = 2166136261
			hash = offset_basis
			for each octet_of_data to be hashed
				hash = hash * FNV_prime
				hash = hash xor octet_of_data
			return hash 
			*/
#if 1
			static const unsigned long offset_basis = 2166136261;
			static const unsigned long FNV_prime = 16777619;
			size_t hash = offset_basis;
#define HASH_Q(a) hash *= FNV_prime; \
			hash ^= (a)&255;         \
			hash *= FNV_prime;       \
			hash ^= ((a)>>8)&255;    \
			hash *= FNV_prime;       \
			hash ^= ((a)>>16)&255;   \
			hash *= FNV_prime;       \
			hash ^= ((a)>>24)&255;  

			HASH_Q(reinterpret_cast<size_t>(q.ne_));
			HASH_Q(reinterpret_cast<size_t>(q.nw_));
			HASH_Q(reinterpret_cast<size_t>(q.se_));
			HASH_Q(reinterpret_cast<size_t>(q.sw_));

#undef HASH_Q
			return hash;
#else
			return int(q.nw_) + 3* (int(q.ne_) + 3*(int(q.se_) + 3*int(q.sw_)));
#endif
			}
		};
	typedef stdext::hash_map<QuadPtr, Node, QuadHashCompare> MapType;
#else
	typedef std::map<QuadPtr,Node> MapType;
#endif
	MapType hashNodes_; // nodes - TODO - make hash map, private

	}; // HashLife 

#endif // HASH_LIFE_H
// end - HashLife.h