#include <iostream>
#include <sstream>
#define show(variable) std::cout << #variable << " = " << variable << std::endl; 

// 	The Knight, from its starting position onwards, can only move forward in the 4 ways, as defined by the Knight move in chess.

const int WIDTH = 8, LENGTH = 12, START_X = 4, START_Y = 0;
const bool showDetails = false;

class ChessBoard {
private:
	class Node {
		private:
			ChessBoard& chessBoard;  // reference data member because a ChessBoard::Node always belongs to a ChessBoard
			int value, x, y;
			Node *child1, *child2, *child3, *child4, *parent1, *parent2, *parent3, *parent4;
			friend class ChessBoard;
			Node (ChessBoard& cb, int X, int Y): chessBoard (cb), x (X), y (Y) {  // Many private functions, including the constructor.
				chessBoard.nodesFound[x][y] = this;  // Storing this new Node into nodesFound.
				child1 = child2 = child3 = child4 = NULL;  // Initializing temporarily for use in updateValue() for a new Node (else the program will crash).  The children will be established right after.
				establishParents();
				updateValue();
				if (showDetails) {std::cout << "chessBoard.nodesFound["<<x<<"]["<<y<<"] officially created." << std::endl;  std::cout << "chessBoard.nodesFound["<<x<<"]["<<y<<"]: " << chessBoard.nodesFound[x][y] << std::endl;}
				createChildren();  // Node constructor called recursively within.
			}
			~Node () {   // Running the destructor will cause a crash because inevitably a Node already deleted will attempt to be deleted again
				//std::cout << "[Node destructor called]" << std::endl;  delete leftChild; delete rightChild; delete leftParent;  delete rightParent; 
			}
			void establishParents () {
				parent1 = parent2 = parent3 = parent4 = NULL;  // Some of these NULL values will be overridden below.
				if ( (y >= 1 && x >= 2) && (chessBoard.nodesFound[x-2][y-1]) )
				{
					if (showDetails) std::cout << "chessBoard.nodesFound["<<x-2<<"]["<<y-1<<"]: " << chessBoard.nodesFound[x-2][y-1] << std::endl;
					parent1 = chessBoard.nodesFound[x-2][y-1];
					parent1->child4 = this;  
				}
				if ( (y >= 1 && x <= chessBoard.dimension_x - 3) && (chessBoard.nodesFound[x+2][y-1]) )
				{
					if (showDetails) std::cout << "chessBoard.nodesFound["<<x+2<<"]["<<y-1<<"]: " << chessBoard.nodesFound[x+2][y-1] << std::endl;
					parent4 = chessBoard.nodesFound[x+2][y-1];
					parent4->child1 = this;  
				}
				if ( (y >= 2 && x >= 1) && (chessBoard.nodesFound[x-1][y-2]) )
				{
					if (showDetails) std::cout << "chessBoard.nodesFound["<<x-1<<"]["<<y-2<<"]: " << chessBoard.nodesFound[x-1][y-2] << std::endl;
					parent2 = chessBoard.nodesFound[x-1][y-2];
					parent2->child3 = this;  
				}
				if ( (y >= 2 && x <= chessBoard.dimension_x - 2) && (chessBoard.nodesFound[x+1][y-2]) )
				{
					if (showDetails) std::cout << "chessBoard.nodesFound["<<x+1<<"]["<<y-2<<"]: " << chessBoard.nodesFound[x+1][y-2] << std::endl;
					parent3 = chessBoard.nodesFound[x+1][y-2];
					parent3->child2 = this;  
				}
			}
			void updateValue () {
				if (x == chessBoard.start_x && y == chessBoard.start_y)
				{
					value = 1;
					chessBoard.nodesFound[x][y] = this; 
				}
				else 
				{
					value = 0;
					if (parent1)
					{
				 		value += parent1->value;
				 		if (showDetails) {std::cout << x << y << " has parent1" <<  std::endl; show (parent1);  show (parent1->value);}
				 	}
				 	if (parent2)
					{
						value += parent2->value;
					 	if (showDetails) {std::cout << x << y  << " has parent2" <<  std::endl; show (parent2);  show (parent2->value);}
					}
					if (parent3)
					{
				 		value += parent3->value;
				 		if (showDetails) {std::cout << x << y << " has parent3" <<  std::endl; show (parent3);  show (parent3->value);}
				 	}
				 	if (parent4)
					{
						value += parent4->value;
					 	if (showDetails) {std::cout << x << y  << " has parent4" <<  std::endl; show (parent4);  show (parent4->value);}
					}
					if (showDetails) std::cout << x << y << " value = " << value << std::endl;
				}
				if (child1)  // Vital to update the values of all children, because changes this Node's value will affect their values too!
					child1->updateValue();
				if (child2)
					child2->updateValue();
				if (child3)
					child3->updateValue();
				if (child4)
					child4->updateValue();
			}
			void checkChild1 () {
				if (chessBoard.nodesFound[x-2][y+1])
				{
					if (showDetails) std::cout << x-2 << y+1 << " found.  Applying changes to it." << std::endl;
					chessBoard.nodesFound[x-2][y+1]->applyChanges();
				}
				else 
				{
					if (showDetails) std::cout << "Creating " << x-2 << y+1 << std::endl;
					child1 = new Node (chessBoard, x - 2, y + 1);
				}
			}
			void checkChild2 () {
				if (chessBoard.nodesFound[x-1][y+2])
				{
					if (showDetails) std::cout << x-1 << y+2 << " found.  Applying changes to it." << std::endl;
					chessBoard.nodesFound[x-1][y+2]->applyChanges();
				}
				else
				{
					if (showDetails) std::cout << "Creating " << x-1 << y+2 << std::endl;
					child2 = new Node (chessBoard, x - 1, y + 2);
				}
			}
			void checkChild3 () {
				if (chessBoard.nodesFound[x+1][y+2])
				{
					if (showDetails) std::cout << x+1 << y+2 << " found.  Applying changes to it." << std::endl;
					chessBoard.nodesFound[x+1][y+2]->applyChanges();
				}
				else
				{
					if (showDetails) std::cout << "Creating " << x+1 << y+2 << std::endl;
					child3 = new Node (chessBoard, x + 1, y + 2);
				}
			}
			void checkChild4 () {
				if (chessBoard.nodesFound[x+2][y+1])
				{
					if (showDetails) std::cout << x+2 << y+1 << " found.  Applying changes to it." << std::endl;
					chessBoard.nodesFound[x+2][y+1]->applyChanges();
				}
				else
				{
					if (showDetails) std::cout << "Creating " << x+2 << y+1 << std::endl;
					child4 = new Node (chessBoard, x + 2, y + 1);
				}
			}			
			void createChildren () {  
				if ( (x >= 2) && (y <= chessBoard.dimension_y - 2) )	
					checkChild1();
				if ( (x >= 1) && (y <= chessBoard.dimension_y - 3) )
					checkChild2();
				if ( (x <= chessBoard.dimension_x - 2) && (y <= chessBoard.dimension_y - 3) )
					checkChild3();
				if ( (x <= chessBoard.dimension_x - 3) && (y <= chessBoard.dimension_y - 2) )
					checkChild4();		
				if (showDetails) std::cout << "Value at " << x << y << " = " << value << std::endl;
			}
			void applyChanges () {
				establishParents();
				updateValue();
				createChildren();
			}
		public:
			int Value () const {return value;}
	};
public:
	ChessBoard (int X, int Y, int startX, int startY): dimension_x (X), dimension_y (Y), start_x (startX), start_y (startY) {  // Private constructor of ChessBoard::Node callable because ChessBoard is declared friend of RectangularPrism::Node. 
		nodesFound = new Node**[dimension_x + 1];  // This is also how a multi-dimensional array is returned from a function in C++ (i.e. do all this, and then return nodesFound).
		for (int i = 0; i < dimension_x; i++)
		{
			nodesFound[i] = new Node*[dimension_y + 1];
			for (int j = 0; j < dimension_y; j++)
				nodesFound[i][j] = NULL;
		}
		startingPoint = new Node (*this, start_x, start_y);  // Placing this line before the nodesFound construction above will cause a crash because the Node constructor uses nodesFound.
	}
//	~ChessBoard () { 
//		std::cout << std::endl << "[ChessBoard destructor called]" << std::endl;
//		delete startingPoint;
//		for (int i = 0; i < dimension_x; i++)
//		{
//			for (int j = 0; j < dimension_y; j++)
//				delete[] nodesFound[i][j];
//			delete[] nodesFound[i];
//		}
//		delete[] nodesFound;
//	}
	Node*** NodesFound () const {return nodesFound;}
	int Dimension_x() const {return dimension_x;}
	int Dimension_y() const {return dimension_y;}
private:
	const int dimension_x, dimension_y, start_x, start_y;
	Node *startingPoint;
	Node ***nodesFound;  /* This 2-dimensional array of Node*'s is to search all Nodes found so that the latest constructed Node with the same coordinates as some Node already found 
	would be made equal to that Node.  An std::map<std::tuple<int, int, int>, void*> could instead be used where the key are the co-ordinates and the values the Nodes, so then map::find would 
	binary search for the coordinates in logarithmic time, but a simple multi-dimensional array (or vector) can use its random access iterator to find the Node in constant time, the drawback
	being a lot of unused allocated space when the dimensions are large, but since this program is a stand-alone that should be fine. */
};

template <typename T> 
const std::string toString (T t) {
    std::ostringstream os;
    os << t;
    return os.str();
}

std::string bigNumberWithCommas (const unsigned long long n) {  // Note:  No comma for a 4-digit number
	std::string numStr = toString (n);
	if (numStr.length () <= 4)
        return numStr;
	size_t pos = numStr.length () % 3;  // position of the first comma to insert
    if (pos == 0)  // e.g. the number 142789, having 6 digits, should have the comma in position 3
        pos = 3;
	while (pos < numStr.length ())
    {
        numStr.insert (pos, 1, ',');  // Since ',' is a char, the 1 is needed (which is size_t number of characters to insert).  Note that numStr.insert (pos, ",") also works, since "," is a string.
        pos += 4; // skip the comma plus 3 digits.
    }
    return numStr;
}

const int spacing (int length) {
	if (length <= 4)
		return 3;
	else if (length <= 7)
		return 4;
	else if (length <= 10)
		return 5;
	else if (length <= 13)
		return 6;
	else if (length <= 16)
		return 7;
	else return 8;
}

int main () {
	ChessBoard chessBoard (WIDTH, LENGTH, START_X, START_Y);
	const int space = spacing (chessBoard.Dimension_y());
	int sum = 0;
	for (int j = chessBoard.Dimension_y() - 1; j >= 0; j--)
	{
		for (int i = 0; i < chessBoard.Dimension_x(); i++)
		{
			std::cout.width (space);
			if (chessBoard.NodesFound()[i][j])
			{
				std::cout << std::left << chessBoard.NodesFound()[i][j]->Value();
				if (j == chessBoard.Dimension_y() - 1)
					sum += chessBoard.NodesFound()[i][j]->Value();
			}
			else
				std::cout << std::left << 0;
		}
		std::cout << std::endl << std::endl;
	}
	std::cout << std::endl << bigNumberWithCommas (sum) << " paths from the starting position to the top row." << std::endl;
	std::cin.get();
	return 0;
}