#include <iostream>
#include <fstream>   //for classes ifstream and ofstream
#include <cstdlib>
#include <string>    //for class string
#include <algorithm> //for the algorithm transform
#include <cctype>    //for the function tolower
using namespace std;

//A node contains an animal or a yes/no question.

class node {
public:
	string animal;   //the animal, if this node contains an animal
	string question; //the question, if this node contains a yes/no question
	node *yes;       //if this node is a question, the 2 possible next moves
	node *no;

	//constructors:
	node() {}
	node(const string& s): animal {s}, yes {nullptr}, no {nullptr} {}

	//Does this node contain the name of an animal?
	bool is_animal() const {return animal != "";}
};

bool get_answer(const string& question);
void write_to_file(node* node, ofstream& out, string indentation);
node* read_from_file(ifstream& in);
void learn(node *root);
void play(node *root);
void deleteTree(node* root);

int main()
{
	const string filename {"animal.txt"};
	node *root {nullptr};

	//Load the input file if it exists.
	ifstream infile {filename};

	if (infile) {   //If the input file exists and we were able to open it
		root = read_from_file(infile);
		infile.close();
		cout << "Knowledge read from file " << filename << ".\n";
	} else {
		root = new(nothrow) node {"dog"};
	}

	for (;;) {
		cout << "Please think of an animal.\n\n";
		play(root);

		if (get_answer("Play again?") == false) {
			break;   //out of the for (;;) loop
		}
	}
	
	//Arrive here when user doesn't want to play again.
	ofstream outfile(filename);
	write_to_file(root, outfile, "");
	cout << "Knowledge saved in file " << filename << ".  Goodbye!\n";

	deleteTree(root);
	return EXIT_SUCCESS;
}

//Display a question, get a yes/no answer.

bool get_answer(const string& question)
{
	cout << question << " ";
	string answer;

	getline(cin, answer);

	//Transform the answer to all lowercase.
	transform(begin(answer), end(answer), begin(answer),
		[](unsigned char c) {return tolower(c);});

	return answer == "yes" || answer == "y";
}

// Save (preorder)

void write_to_file(node* root, ofstream& out, string indentation)
{
	if (root == nullptr) {   //If there's nothing to write to the file,
		return;          //return without doing anything.
	}

	out << indentation;

	if (root->is_animal()) {
		out << "A " << root->animal << "\n";
	} else {
		out << "Q " << root->question << "\n";
		write_to_file(root->yes, out, indentation + " ");
		write_to_file(root->no,  out, indentation + " ");
	}
}

node* read_from_file(ifstream& in)
{
	string type;
	in >> type;

	if (!in) {  //if we could not read the type character ("A" or "Q")
		return nullptr;
	}
	in.get();   //Read and discard the whitespace character after the type.

	string line;
	getline(in, line);

	node *const root {new(nothrow) node};

	if (type == "A") {        //animal
		root->animal = line;
		root->yes = nullptr;
		root->no  = nullptr;
	} else if (type == "Q") { //question
		root->question = line;
		root->yes = read_from_file(in);
		root->no  = read_from_file(in);
	}

	return root;
}

/*
When this function is called, the root node holds an animal.
Change the node into a question node with two children.
The animal in the original root node will be the "no" child.
The new animal will be the "yes" child.
*/

void learn(node *root)
{
	cout << "I give up.  What animal were you thinking of? ";
	string animalName;
	getline(cin, animalName);

	cout << "Please give me a question whose answer is \"yes\" for a "
		 << animalName << " and \"no\" for a " << root->animal << ":\n";
	string newQuestion;
	getline(cin, newQuestion);
	cout << "Thank you.  The game is over.\n\n";

	//Construct two new nodes that will be the children of root.
	node *existingAnimal {new(nothrow) node {root->animal}};
	node* newAnimal {new(nothrow) node {animalName}};

	//Transform the root into question node with two children.
	root->question = newQuestion;
	root->animal = "";

	root->yes = newAnimal;
	root->no = existingAnimal;
}

void play(node *root)
{
	if (root->is_animal()) {
		//The root node is a leaf.
		if (get_answer("Is it a " + root->animal + "?") == true) {
			cout << "I guessed your animal!\n";
			cout << "Thank you.  The game is over.\n\n";
		} else {
			learn(root);  //Ask the user to supply a question.
		}
	} else {
		//The root node holds a question.
		if (get_answer(root->question) == true) {
			play(root->yes);
		} else {
			play(root->no);
		}
	}
}

//Delete all the nodes in the tree.

void deleteTree(node* root)
{
	if (root != nullptr) {         //If root actually points at a node,
		deleteTree(root->yes); //delete any children of the node
		deleteTree(root->no);
		delete root;           //and then the node itself.
	}
}