C++ Data Structures with Templates

The Code

struct stNode {
	uint8_t key;
	stNode *left, *right, *parent;
	void* data;
};
stNode* root;
// variation on a theme - a non recursive insert that uses
// a while loop to navigate to the right empty location
bool stInsert(uint16_t key, cBoard* dta, stNode** root) {
	stNode* leaf = *root;
	stNode* parent = NULL;
	while (leaf) {
		parent = leaf;
		if (key < leaf->key) {
			leaf = leaf->left;
		}
		else {
			leaf = leaf->right;
		}
	}
	// leaf is NULL so empty location found
	leaf = (stNode*)malloc(sizeof(stNode));
	leaf->left = leaf->right = NULL;
	leaf->key = key;
	leaf->parent = parent;
	leaf->data = malloc(sizeof(cBoard));
	if (leaf->data) {
		memcpy(leaf->data, dta, sizeof(cBoard));
	}
	if (parent == NULL) {
		*root = leaf;
	}
	else {
		if (key < parent->key) {
			parent->left = leaf;
		}
		else {
			parent->right = leaf;
		}
	}
	splay(leaf);
	return true;
}
void splay(stNode* leaf) {
	while (leaf->parent) {
		if (leaf->parent->parent == NULL) {
			if (leaf == leaf->parent->left) {
				stRightRotate(leaf->parent);
			}
			else {
				stLeftRotate(leaf->parent);
			}
		}
		else if (leaf == leaf->parent->left && leaf->parent == leaf->parent->parent->left) {
			stRightRotate(leaf->parent->parent);
			stRightRotate(leaf->parent);
		}
		else if (leaf == leaf->parent->right && leaf->parent == leaf->parent->parent->right) {
			stLeftRotate(leaf->parent->parent);
			stLeftRotate(leaf->parent);
		}
		else if (leaf == leaf->parent->left && leaf->parent == leaf->parent->parent->right) {
			stRightRotate(leaf->parent);
			stLeftRotate(leaf->parent);
		}
		else {
			stLeftRotate(leaf->parent);
			stRightRotate(leaf->parent);
		}
	}
}
cBoard* stFind(uint8_t key, bool doSplay) {
	stNode* found = stFindNode(key, root);
	if (found) {
		if (doSplay) {
			splay(found);
		}
		return (cBoard*)found->data;
	}
	return NULL;
}
stNode* stFindNode(uint8_t key, stNode* leaf) {
	if (leaf) {
		if (key == leaf->key) {
			return leaf;
		}
		if (key < leaf->key) {
			return stFindNode(key, leaf->left);
		}
		return stFindNode(key, leaf->right);
	}
	return NULL;
}
bool stDeleteNode(uint8_t key) {
	stNode* found = stFindNode(key, root);
	if (found == NULL) {
		return false;
	}
	splay(found);
	// does this node have children to take it's place?
	if (found->left == NULL) {
		stSwap(found, found->right);
	}
	else if (found->right == NULL) {
		stSwap(found, found->left);
	}
	else {
		// two children
		stNode* next = stMinimum(found->right);
		if (next->parent != found) {
			stSwap(next, next->right);
			next->right = found->right;
			next->right->parent = next;
		}
		stSwap(found, next);
		next->left = found->left;
		next->left->parent = next;
	}
	free(found->data);
	free(found);
	return true;
}
void stSwap(stNode* a, stNode* b) {
	if (a->parent == NULL) {
		root = b;
	}
	else if (a == a->parent->left) {
		a->parent->left = b;
	}
	else {
		a->parent->right = b;
	}
	if (b) {
		b->parent = a->parent;
	}
}
stNode* stMinimum(stNode* leaf) {
	while (leaf->left) {
		leaf = leaf->left;
	}
	return leaf;
}
void stLeftRotate(stNode *node) {
	stNode *child = node->right;
	if (child) {
		node->right = child->left;
		if (child->left) {
			child->left->parent = node;
		}
		child->parent = node->parent;
	}
	if (!node->parent) {
		root = child;
	}
	else if (node == node->parent->left) {
		node->parent->left = child;
	}
	else {
		node->parent->right = child;
	}
	if (child) {
		child->left = node;
	}
	node->parent = child;
}
void stRightRotate(stNode *node) {
	stNode *child = node->left;
	if (child) {
		node->left = child->right;
		if (child->right) {
			child->right->parent = node;
		}
		child->parent = node->parent;
	}
	if (!node->parent) {
		root = child;
	}
	else if (node == node->parent->left) {
		node->parent->left = child;
	}
	else {
		node->parent->right = child;
	}
	if (child) {
		child->right = node;
	}
	node->parent = child;
}
void stDeleteTree(stNode* leaf) {
	if (leaf) {
		stDeleteTree(leaf->left);
		stDeleteTree(leaf->right);
		free(leaf->data);
		free(leaf);
	}
}
int stMax(int a, int b) {
	return (a <= b) ? b : a;
}
int stHeight(stNode* leaf) {
	if (leaf) {
		return 1 + stMax(stHeight(leaf->left), stHeight(leaf->right));
	}
	return 0;
}

#include "stdafx.h"
#include "stdafx.h"
#include <stdint.h>
#include <stdlib.h>
#include <iostream>
enum Players { WHT, BLK };
uint8_t nextMove = WHT;
enum Pieces { PAWN, ROOK, KNIGHT, BISHOP, QUEEN, KING };
char pNames[][7] = { "Pawn", "Rook", "Knight", "Bishop", "Queen", "King" };
char pSymbol[] = { 'P', 'R', 'N', 'B', 'Q', 'K' };
struct cBoard {
	uint8_t player;
	uint8_t piece;
};
void playGame();
void makeMove(uint8_t from, uint8_t to);
void castleMove(uint8_t f1, uint8_t f2, uint8_t t1, uint8_t t2);
void setupBoard();
void displayBoard();
bool stInsert(uint16_t key, cBoard * dta, stNode ** root);
void splay(stNode * leaf);
cBoard * stFind(uint8_t key, bool doSplay);
stNode * stFindNode(uint8_t key, stNode * leaf);
bool stDeleteNode(uint8_t key);
void stSwap(stNode * a, stNode * b);
stNode * stMinimum(stNode * leaf);
void stLeftRotate(stNode * node);
void stRightRotate(stNode * node);
void stDeleteTree(stNode * leaf);
int stMax(int a, int b);
int stHeight(stNode * leaf);
int main()
{
	setupBoard();
	displayBoard();
	playGame();
	std::cin.get();
	return 0;
}
void playGame() {
	uint8_t cOpt = 0;
	uint8_t moves[][2] = { { 13,29 },{ 53,37 },{ 7,13 },{ 58,43 },{ 2,19 },{ 62,35 },
	{ 13,23 },{ 52,44 },{ 12,20 },{ 63,46 },{ 3,39 },{ 59,45 },{ 23,40 },{ 0,0 },
	{ 19,36 },{ 46,29 },{ 39,60 },{ 35,14 },{ 5,13 },{ 45,31 } };
	uint8_t cstlmoves[][4] = { { 61,64,63,62 } };
	for (int i = 0; i < sizeof(moves) / 2; i++) {
		if (moves[i][0] == 0) {
			castleMove(cstlmoves[cOpt][0], cstlmoves[cOpt][1], cstlmoves[cOpt][2], cstlmoves[cOpt][3]);
			cOpt++; // max is 2 per game
		}
		else {
			makeMove(moves[i][0], moves[i][1]);
		}
	}
	std::cout << "Checkmate!\n";
}
void makeMove(uint8_t from, uint8_t to) {
	cBoard* fSquare = stFind(from, false);
	cBoard* tSquare = stFind(to, false);
	if (fSquare) {
		if (fSquare->player == nextMove) {
			if (tSquare == NULL || tSquare->player != nextMove) {
				if (tSquare) {
					stDeleteNode(to);
				}
				stInsert(to, fSquare, &root);
				stDeleteNode(from);
			}
			else {
				std::cout << "Target square invalid\n";
			}
		}
		else {
			std::cout << "Not your move\n";
		}
	}
	nextMove = (nextMove == WHT) ? BLK : WHT;  //whose move next
	displayBoard();
}
// OK the castle move needs different validation so
// as this is not intended as a chess playing game demo
// this function is a bodge to allow the move
void castleMove(uint8_t f1, uint8_t f2, uint8_t t1, uint8_t t2) {
	cBoard* f1Square = stFind(f1, false);
	cBoard* f2Square = stFind(f2, false);
	stInsert(t1, f1Square, &root);
	stDeleteNode(f1);
	stInsert(t2, f2Square, &root);
	stDeleteNode(f2);
	nextMove = (nextMove == WHT) ? BLK : WHT;  //whose move next
	displayBoard();
}
void setupBoard() {
	cBoard wSquare = { WHT, PAWN }, bSquare = { BLK, PAWN };
	for (int i = 1; i < 9; i++) {
		wSquare.piece = bSquare.piece = PAWN;
		stInsert(i + 8, &wSquare, &root);
		stInsert(i + 48, &bSquare, &root);
		switch (i) {
		case 1:
		case 8:
			wSquare.piece = bSquare.piece = ROOK;
			break;
		case 2:
		case 7:
			wSquare.piece = bSquare.piece = KNIGHT;
			break;
		case 3:
		case 6:
			wSquare.piece = bSquare.piece = BISHOP;
			break;
		case 4:
			wSquare.piece = bSquare.piece = QUEEN;
			break;
		case 5:
			wSquare.piece = bSquare.piece = KING;
			break;
		}
		stInsert(i, &wSquare, &root);
		stInsert(i + 56, &bSquare, &root);
	}
}
void displayBoard() {
	cBoard* square;
	std::cout << "Board Positions\n";
	for (int i = 0; i < 8; i++) {
		for (int j = 1; j < 9; j++) {
			square = stFind(j + i * 8, false);
			if (square) {
				std::cout << (square->player == WHT ? pSymbol[square->piece] : (char)(pSymbol[square->piece] + 32));
			}
			else {
				std::cout << ' ';
			}
		}
		std::cout << '\n';
	}
	std::cout << "________\n";
}

enum Players {WHT, BLK};
uint8_t nextMove = WHT;
enum Pieces {PAWN, ROOK, KNIGHT, BISHOP, QUEEN, KING};
char pNames[][7] = {"Pawn", "Rook", "Knight", "Bishop", "Queen", "King"};
char pSymbol[] = {'P', 'R', 'N', 'B', 'Q', 'K'};
struct cBoard{
  uint8_t player;
  uint8_t piece;
};
template<class T> inline Print &operator <<(Print &obj, T arg) { obj.print(arg); return obj; }
void setup() {
  Serial.begin(115200);
  setupBoard();
  displayBoard();
  Serial << "Height: " << stHeight(root) << '\n';
  playGame();
  Serial << "Height: " << stHeight(root) << '\n';
}
void playGame() {
  uint8_t cOpt = 0;
  uint8_t moves[][2] = {{13,29},{53,37},{7,13},{58,43},{2,19},{62,35},
          {13,23},{52,44},{12,20},{63,46},{3,39},{59,45},{23,40},{0,0},
          {19,36},{46,29},{39,60},{35,14},{5,13},{45,31}};
  uint8_t cstlmoves[][4] = {{61,64,63,62}};
  for (int i = 0; i < sizeof(moves) / 2; i++) {
    if(moves[i][0] == 0) {
      castleMove(cstlmoves[cOpt][0], cstlmoves[cOpt][1], cstlmoves[cOpt][2], cstlmoves[cOpt][3]);
      cOpt++; // max is 2 per game
    } else {
      makeMove(moves[i][0], moves[i][1]);
    }
  }
  Serial << "Checkmate!\n";
}
void makeMove(uint8_t from, uint8_t to) {
  cBoard* fSquare = stFind(from, false);
  cBoard* tSquare = stFind(to, false);
  if(fSquare) {
    if(fSquare->player == nextMove) {
      if(tSquare == NULL || tSquare->player != nextMove) {
        // probably a valid move but you could write a lot more
        // validation to check route is clear if not knight and
        // distance allowed and from and to not the same etc.
        if(tSquare) {
          stDeleteNode(to);
        }
        stInsert(to, fSquare, &root);
        stDeleteNode(from);
      } else {
        Serial << "Target square invalid\n";
      }
    } else {
      Serial << "Not your move\n";
    }
  }
  nextMove = (nextMove == WHT)? BLK : WHT;  //whose move next
  displayBoard();
}
// OK the castle move needs different validation so
// as this is not intended as a chess playing game demo
// this function is a bodge to allow the move
void castleMove(uint8_t f1, uint8_t f2, uint8_t t1, uint8_t t2) {
  cBoard* f1Square = stFind(f1, false);
  cBoard* f2Square = stFind(f2, false);
  stInsert(t1, f1Square, &root);
  stDeleteNode(f1);
  stInsert(t2, f2Square, &root);
  stDeleteNode(f2);
  nextMove = (nextMove == WHT)? BLK : WHT;  //whose move next
  displayBoard();
}
void setupBoard() {
  cBoard wSquare = {WHT, PAWN}, bSquare = {BLK, PAWN};
  for(int i = 1; i < 9; i++) {
    wSquare.piece = bSquare.piece = PAWN;
    stInsert(i + 8, &wSquare, &root);
    stInsert(i + 48, &bSquare, &root);
    switch(i) {
      case 1:
      case 8:
        wSquare.piece = bSquare.piece = ROOK;
        break;
      case 2:
      case 7:
        wSquare.piece = bSquare.piece = KNIGHT;
        break;
      case 3:
      case 6:
        wSquare.piece = bSquare.piece = BISHOP;
        break;
      case 4:
        wSquare.piece = bSquare.piece = QUEEN;
        break;
      case 5:
        wSquare.piece = bSquare.piece = KING;
        break;
    }
    stInsert(i, &wSquare, &root);
    stInsert(i + 56, &bSquare, &root);
  }
}
void displayBoard() {
  cBoard* square;
  Serial << "Board Positions\n";
  for(int i = 0; i < 8; i++) {
    for(int j = 1; j < 9; j++) {
      square = stFind(j + i * 8, false);
      if(square) {
        Serial << (square->player == WHT ? pSymbol[square->piece] : (char)(pSymbol[square->piece]+32));
      }else {
        Serial << ' ';
      }
    }
    Serial << '\n';
  }
  Serial << "________\n";
}

#pragma once
#ifndef SplayTree_h
#define SplayTree_h
template<typename T, typename K>
class SplayTree {
public:
	using stIter = void(*)(K, T*);
	using stIterP = void(*)(K, int);
	SplayTree();
	~SplayTree();
	bool insert(K, T*);
	T* find(K, bool);
	bool deleteNode(K);
	int height();
	void iterateLevel(int, stIter);
	void iterateLevel(int, stIterP, int);
private:
	size_t nodeSize, tSize;
	struct stNode {
		K key;
		stNode *left, *right, *parent;
		void* data;
	};
	stNode* root;
	bool stInsert(K, T*, stNode**);
	void splay(stNode*);
	T* stFind(K, bool);
	stNode* stFindNode(K, stNode*);
	bool stDeleteNode(K);
	void stSwap(stNode*, stNode*);
	stNode* stMinimum(stNode*);
	void stLeftRotate(stNode*);
	void stRightRotate(stNode*);
	void stDeleteTree(stNode*);
	int stMax(int, int);
	int stHeight(stNode*);
	void stIterateLevel(int, stIter, stNode*);
	void stIterateLevel(int, stIterP, stNode*, int, int);
};
//Constructor / Destructor
template<typename T, typename K>
SplayTree<T, K>::SplayTree() {
	tSize = sizeof(T);
	nodeSize = sizeof(stNode);
}
template<typename T, typename K>
SplayTree<T, K>::~SplayTree() {
	stDeleteTree(root);
}
//public Methods
template<typename T, typename K>
bool SplayTree<T, K>::insert(K key, T* data) {
	return stInsert(key, data, &root);
}
template<typename T, typename K>
T* SplayTree<T, K>::find(K key, bool doSplay) {
	return stFind(key, doSplay);
}
template<typename T, typename K>
bool SplayTree<T, K>::deleteNode(K key) {
	return stDeleteNode(key);
}
template<typename T, typename K>
int SplayTree<T, K>::height() {
	return stHeight(root);
}
template<typename T, typename K>
void SplayTree<T, K>::iterateLevel(int level, stIter callBack) {
	stIterateLevel(level, callBack, root);
}
template<typename T, typename K>
void SplayTree<T, K>::iterateLevel(int level, stIterP callBack, int m) {
	stIterateLevel(level, callBack, root, m, m);
}
//private Methods
template<typename T, typename K>
bool SplayTree<T, K>::stInsert(K key, T* data, stNode** root) {
	// variation on a theme - a non recursive insert that uses
	// a while loop to navigate to the right empty location
	stNode* leaf = *root;
	stNode* parent = NULL;
	bool retVal = true;
	while (leaf) {
		parent = leaf;
		if (key < leaf->key) {
			leaf = leaf->left;
		}
		else {
			leaf = leaf->right;
		}
	}
	// leaf is NULL so empty location found
	leaf = (stNode*)malloc(nodeSize);
	if (leaf) {
		leaf->left = leaf->right = NULL;
		leaf->key = key;
		leaf->parent = parent;
		leaf->data = malloc(tSize);
		if (leaf->data) {
			memcpy(leaf->data, data, tSize);
			if (parent == NULL) {
				*root = leaf; //first node to be inserted
			}
			else {
				if (key < parent->key) {
					parent->left = leaf;
				}
				else {
					parent->right = leaf;
				}
				splay(leaf);
				return true;
			}
		}
		else {
			free(leaf);
		}
	}
	return false;
}
template<typename T, typename K>
void SplayTree<T, K>::splay(stNode* leaf) {
	while (leaf->parent) {
		if (leaf->parent->parent == NULL) {
			if (leaf == leaf->parent->left) {
				stRightRotate(leaf->parent);
			}
			else {
				stLeftRotate(leaf->parent);
			}
		}
		else if (leaf == leaf->parent->left && leaf->parent == leaf->parent->parent->left) {
			stRightRotate(leaf->parent->parent);
			stRightRotate(leaf->parent);
		}
		else if (leaf == leaf->parent->right && leaf->parent == leaf->parent->parent->right) {
			stLeftRotate(leaf->parent->parent);
			stLeftRotate(leaf->parent);
		}
		else if (leaf == leaf->parent->left && leaf->parent == leaf->parent->parent->right) {
			stRightRotate(leaf->parent);
			stLeftRotate(leaf->parent);
		}
		else {
			stLeftRotate(leaf->parent);
			stRightRotate(leaf->parent);
		}
	}
}
template<typename T, typename K>
T* SplayTree<T, K>::stFind(K key, bool doSplay) {
	stNode* found = stFindNode(key, root);
	if (found) {
		if (doSplay) { splay(found); }
		return (T*)found->data;
	}
	return NULL;
}
template<typename T, typename K>
typename SplayTree<T, K>::stNode* SplayTree<T, K>::stFindNode(K key, stNode* leaf) {
	if (leaf) {
		if (key == leaf->key) {
			return leaf;
		}
		if (key < leaf->key) {
			return stFindNode(key, leaf->left);
		}
		return stFindNode(key, leaf->right);
	}
	return NULL;
}
template<typename T, typename K>
bool SplayTree<T, K>::stDeleteNode(K key) {
	stNode* found = stFindNode(key, root);
	if (found == NULL) {
		return false;
	}
	splay(found);
	// does this node have children to take it's place?
	if (found->left == NULL) {
		stSwap(found, found->right);
	}
	else if (found->right == NULL) {
		stSwap(found, found->left);
	}
	else {
		// two children
		stNode* next = stMinimum(found->right);
		if (next->parent != found) {
			stSwap(next, next->right);
			next->right = found->right;
			next->right->parent = next;
		}
		stSwap(found, next);
		next->left = found->left;
		next->left->parent = next;
	}
	free(found->data);
	free(found);
	return true;
}
template<typename T, typename K>
void SplayTree<T, K>::stSwap(stNode* a, stNode* b) {
	if (a->parent == NULL) {
		root = b;
	}
	else if (a == a->parent->left) {
		a->parent->left = b;
	}
	else {
		a->parent->right = b;
	}
	if (b) {
		b->parent = a->parent;
	}
}
template<typename T, typename K>
typename SplayTree<T, K>::stNode* SplayTree<T, K>::stMinimum(stNode* leaf) {
	while (leaf->left) {
		leaf = leaf->left;
	}
	return leaf;
}
template<typename T, typename K>
void SplayTree<T, K>::stLeftRotate(stNode* node) {
	stNode *child = node->right;
	if (child) {
		node->right = child->left;
		if (child->left) {
			child->left->parent = node;
		}
		child->parent = node->parent;
	}
	if (!node->parent) {
		root = child;
	}
	else if (node == node->parent->left) {
		node->parent->left = child;
	}
	else {
		node->parent->right = child;
	}
	if (child) {
		child->left = node;
	}
	node->parent = child;
}
template<typename T, typename K>
void SplayTree<T, K>::stRightRotate(stNode* node) {
	stNode *child = node->left;
	if (child) {
		node->left = child->right;
		if (child->right) {
			child->right->parent = node;
		}
		child->parent = node->parent;
	}
	if (!node->parent) {
		root = child;
	}
	else if (node == node->parent->left) {
		node->parent->left = child;
	}
	else {
		node->parent->right = child;
	}
	if (child) {
		child->right = node;
	}
	node->parent = child;
}
template<typename T, typename K>
void SplayTree<T, K>::stDeleteTree(stNode* leaf) {
	if (leaf) {
		stDeleteTree(leaf->left);
		stDeleteTree(leaf->right);
		free(leaf->data);
		free(leaf);
	}
}
template<typename T, typename K>
int SplayTree<T, K>::stMax(int a, int b) {
	return (a <= b) ? b : a;
}
template<typename T, typename K>
int SplayTree<T, K>::stHeight(stNode* leaf) {
	if (leaf) {
		return 1 + stMax(stHeight(leaf->left), stHeight(leaf->right));
	}
	return 0;
}
template<typename T, typename K>
void SplayTree<T, K>::stIterateLevel(int level, stIter callBack, stNode* leaf) {
	if (leaf == NULL) {
		return;
	}
	if (level == 1) {
		callBack(leaf->key, (T*)leaf->data);
	}
	if (level > 1) {
		stIterateLevel(--level, callBack, leaf->left);
		stIterateLevel(--level, callBack, leaf->right);
	}
}
template<typename T, typename K>
void SplayTree<T, K>::stIterateLevel(int level, stIterP callBack, stNode* leaf, int pos, int offSet) {
	if (leaf == NULL) {
		return;
	}
	if (level == 1) {
		callBack(leaf->key, pos);
	}
	if (level > 1) {
		offSet /= 2;
		stIterateLevel(--level, callBack, leaf->left, pos - offSet, offSet);
		stIterateLevel(--level, callBack, leaf->right, pos + offSet, offSet);
	}
}
#endif

#include "stdafx.h"
#include "stdafx.h"
#include <stdint.h>
#include <stdlib.h>
#include <iostream>
#include "SplayTree.h"
void setupBoard();
void displayBoard();
void playGame();
void makeMove(uint8_t, uint8_t);
void castleMove(uint8_t, uint8_t, uint8_t, uint8_t);
enum Players { WHT, BLK };
uint8_t nextMove = WHT;
enum Pieces { PAWN, ROOK, KNIGHT, BISHOP, QUEEN, KING };
char pNames[][7] = { "Pawn", "Rook", "Knight", "Bishop", "Queen", "King" };
char pSymbol[] = { 'P', 'R', 'N', 'B', 'Q', 'K' };
struct cBoard {
	uint8_t player;
	uint8_t piece;
};
SplayTree<cBoard, uint8_t> myTree;
char* pLine;
int main()
{
	setupBoard();
	displayBoard();
	playGame();
	std::cin.get();
	return 0;
}
void playGame() {
	uint8_t cOpt = 0;
	uint8_t moves[][2] = { { 13,29 },{ 53,37 },{ 7,13 },{ 58,43 },{ 2,19 },{ 62,35 },
	{ 13,23 },{ 52,44 },{ 12,20 },{ 63,46 },{ 3,39 },{ 59,45 },{ 23,40 },{ 0,0 },
	{ 19,36 },{ 46,29 },{ 39,60 },{ 35,14 },{ 5,13 },{ 45,31 } };
	uint8_t cstlmoves[][4] = { { 61,64,63,62 } };
	for (int i = 0; i < sizeof(moves) / 2; i++) {
		if (moves[i][0] == 0) {
			castleMove(cstlmoves[cOpt][0], cstlmoves[cOpt][1], cstlmoves[cOpt][2], cstlmoves[cOpt][3]);
			cOpt++; // max is 2 per game
		}
		else {
			makeMove(moves[i][0], moves[i][1]);
		}
	}
	std::cout << "Checkmate!\n";
}
void makeMove(uint8_t from, uint8_t to) {
	cBoard* fSquare = myTree.find(from, false);
	cBoard* tSquare = myTree.find(to, false);
	if (fSquare) {
		if (fSquare->player == nextMove) {
			if (tSquare == NULL || tSquare->player != nextMove) {
				if (tSquare) {
					myTree.deleteNode(to);
				}
				myTree.insert(to, fSquare);
				myTree.deleteNode(from);
			}
			else {
				std::cout << "Target square invalid\n";
			}
		}
		else {
			std::cout << "Not your move\n";
		}
	}
	nextMove = (nextMove == WHT) ? BLK : WHT;  //whose move next
	displayBoard();
}
// OK the castle move needs different validation so
// as this is not intended as a chess playing game demo
// this function is a bodge to allow the move
void castleMove(uint8_t f1, uint8_t f2, uint8_t t1, uint8_t t2) {
	cBoard* f1Square = myTree.find(f1, false);
	cBoard* f2Square = myTree.find(f2, false);
	myTree.insert(t1, f1Square);
	myTree.deleteNode(f1);
	myTree.insert(t2, f2Square);
	myTree.deleteNode(f2);
	nextMove = (nextMove == WHT) ? BLK : WHT;  //whose move next
	displayBoard();
}
void setupBoard() {
	cBoard wSquare = { WHT, PAWN }, bSquare = { BLK, PAWN };
	for (int i = 1; i < 9; i++) {
		wSquare.piece = bSquare.piece = PAWN;
		myTree.insert(i + 8, &wSquare);
		myTree.insert(i + 48, &bSquare);
		switch (i) {
		case 1:
		case 8:
			wSquare.piece = bSquare.piece = ROOK;
			break;
		case 2:
		case 7:
			wSquare.piece = bSquare.piece = KNIGHT;
			break;
		case 3:
		case 6:
			wSquare.piece = bSquare.piece = BISHOP;
			break;
		case 4:
			wSquare.piece = bSquare.piece = QUEEN;
			break;
		case 5:
			wSquare.piece = bSquare.piece = KING;
			break;
		}
		myTree.insert(i, &wSquare);
		myTree.insert(i + 56, &bSquare);
	}
}
void displayBoard() {
	cBoard* square;
	std::cout << "Board Positions\n";
	for (int i = 0; i < 8; i++) {
		for (int j = 1; j < 9; j++) {
			square = myTree.find(j + i * 8, false);
			if (square) {
				std::cout << (square->player == WHT ? pSymbol[square->piece] : (char)(pSymbol[square->piece] + 32));
			}
			else {
				std::cout << ' ';
			}
		}
		std::cout << '\n';
	}
	std::cout << "________\n";
}

#include "SplayTree.h"
enum Players {WHT, BLK};
uint8_t nextMove = WHT;
enum Pieces {PAWN, ROOK, KNIGHT, BISHOP, QUEEN, KING};
char pNames[][7] = {"Pawn", "Rook", "Knight", "Bishop", "Queen", "King"};
char pSymbol[] = {'P', 'R', 'N', 'B', 'Q', 'K'};
struct cBoard{
  uint8_t player;
  uint8_t piece;
};
SplayTree<cBoard, uint8_t> myTree;
char* pLine;
template<class T> inline Print &operator <<(Print &obj, T arg) { obj.print(arg); return obj; }
void setup() {
  Serial.begin(115200);
  setupBoard();
  displayBoard();
  printLevels2(5);
  Serial << "Height: " << myTree.height() << '\n';
  playGame();
  Serial << "Height: " << myTree.height() << '\n';
  for(int i = 1, j= myTree.height(); i<=j; i++) {
    myTree.iterateLevel(i, printLevel);
    Serial << '\n';
  }
  printLevels2(5);
}
void printLevel(uint8_t key, cBoard* square) {
  Serial << key << " ";
}
void printLevels2(int toLevel) {
  size_t pLineSize = pow(3, toLevel-1) + 1;
  pLine = (char*)malloc(pLineSize--);
  pLine[pLineSize-1] = 0;
  int m = (pLineSize - 1) / 2;
  for(int i = 1; i<= toLevel; i++){
    memset(pLine, ' ', pLineSize-1);
    myTree.iterateLevel(i, setKey, m);
    Serial << pLine << '\n';
  }
  free(pLine);
}
void setKey(uint8_t key, int pos){
  intToString(key, pLine, pos);
}
// converts +ve int to string inserted into buffer
void intToString(int iVal, char* buff, int pos){
  int i = pos;
  do {
    buff[i++] = iVal % 10 + '0';
  } while ((iVal /= 10) > 0);
  char h;
  // now reverse the string
  for(int j= pos; j < i; j++, i--) {
    h = buff[j];
    buff[j] = buff[i];
    buff[i] = h;
  }
}
void playGame() {
  uint8_t cOpt = 0;
  uint8_t moves[][2] = {{13,29},{53,37},{7,13},{58,43},{2,19},{62,35},
          {13,23},{52,44},{12,20},{63,46},{3,39},{59,45},{23,40},{0,0},
          {19,36},{46,29},{39,60},{35,14},{5,13},{45,31}};
  uint8_t cstlmoves[][4] = {{61,64,63,62}};
  for (int i = 0; i < sizeof(moves) / 2; i++) {
    if(moves[i][0] == 0) {
      castleMove(cstlmoves[cOpt][0], cstlmoves[cOpt][1], cstlmoves[cOpt][2], cstlmoves[cOpt][3]);
      cOpt++; // max is 2 per game
    } else {
      makeMove(moves[i][0], moves[i][1]);
    }
  }
  Serial << "Checkmate!\n";
}
void makeMove(uint8_t from, uint8_t to) {
  cBoard* fSquare = myTree.find(from, false);
  cBoard* tSquare = myTree.find(to, false);
  if(fSquare) {
    if(fSquare->player == nextMove) {
      if(tSquare == NULL || tSquare->player != nextMove) {
        // probably a valid move but you could write a lot more
        // validation to check route is clear if not knight and
        // distance allowed and from and to not the same etc.
        if(tSquare) {
          myTree.deleteNode(to);
        }
        myTree.insert(to, fSquare);
        myTree.deleteNode(from);
      } else {
        Serial << "Target square invalid\n";
      }
    } else {
      Serial << "Not your move\n";
    }
  }
  nextMove = (nextMove == WHT)? BLK : WHT;  //whose move next
  displayBoard();
}
// OK the castle move needs different validation so
// as this is not intended as a chess playing game demo
// this function is a bodge to allow the move
void castleMove(uint8_t f1, uint8_t f2, uint8_t t1, uint8_t t2) {
  cBoard* f1Square = myTree.find(f1, false);
  cBoard* f2Square = myTree.find(f2, false);
  myTree.insert(t1, f1Square);
  myTree.deleteNode(f1);
  myTree.insert(t2, f2Square);
  myTree.deleteNode(f2);
  nextMove = (nextMove == WHT)? BLK : WHT;  //whose move next
  displayBoard();
}
void setupBoard() {
  cBoard wSquare = {WHT, PAWN}, bSquare = {BLK, PAWN};
  for(int i = 1; i < 9; i++) {
    wSquare.piece = bSquare.piece = PAWN;
    myTree.insert(i + 8, &wSquare);
    myTree.insert(i + 48, &bSquare);
    switch(i) {
      case 1:
      case 8:
        wSquare.piece = bSquare.piece = ROOK;
        break;
      case 2:
      case 7:
        wSquare.piece = bSquare.piece = KNIGHT;
        break;
      case 3:
      case 6:
        wSquare.piece = bSquare.piece = BISHOP;
        break;
      case 4:
        wSquare.piece = bSquare.piece = QUEEN;
        break;
      case 5:
        wSquare.piece = bSquare.piece = KING;
        break;
    }
    myTree.insert(i, &wSquare);
    myTree.insert(i + 56, &bSquare);
  }
}
void displayBoard() {
  cBoard* square;
  Serial << "Board Positions\n";
  for(int i = 0; i < 8; i++) {
    for(int j = 1; j < 9; j++) {
      square = myTree.find(j + i * 8, false);
      if(square) {
        Serial << (square->player == WHT ? pSymbol[square->piece] : (char)(pSymbol[square->piece]+32));
      }else {
        Serial << ' ';
      }
    }
    Serial << '\n';
  }
  Serial << "________\n";
}