/*
 * Assignment 1 TK6434 Data Structures & Algorithm Sem II 2008/2009
 * Animal guessing game
 *
 *
 */

#include<iostream>
#include<stdio.h>
#include<string>
#include<stdlib.h>
using namespace std;

struct node {
    string data;
    struct node *left;
    struct node *right;
};

int wanttoplay = 1;
node *ROOTNODE = NULL;

void initialize();
void asktoplay();
void traversetree(node *);
node *newNode(string);
node *build(string, string, string);
node *askQuestion(node *, node *, node *, int);
int hasChildren(node *);
node *addAnimal(node *parent);

/*
 * Initializing the game - set default tree
 */
void initialize() {
    cout << "Welcome!\n=================\n";
    cout << "Initializing the game...";
    ROOTNODE = build("Does it fly?", "Bird", "Fish");
    cout << "done\n";
}

/*
 * Flag to play
 */
void asktoplay() {
    int n = 1;
    cout << endl << "---------------- GAME STARTS -----------------";
    cout << "\nType 2 if you want to stop playing";
    cout << "\nAre you thinking of an animal? 1[Yes] / 2[No]: ";
    cin >> n;
    if (n == 2) wanttoplay = 0;
}

/*
 * Traverse tree inorder
 */
void traversetree(node *root)
{
    if(!root) return;
    traversetree(root->left);
    cout << root->data << ", " ;
    traversetree(root->right);
}

/*
 Allocates a new node with the given data and NULL left and right pointers.
*/
node *newNode(string data) {
  node *node = new struct node;    // "new" is like "malloc"
  node->data = data;
  node->left = NULL;
  node->right = NULL;
  return(node);
}

/*
 * Build a node with pointers left n right
 */
node *build(string Q, string L, string R) {
  node *root = newNode(Q);
  root->left = newNode(L);
  root->right = newNode(R);

  return(root);
}

/*
 * Ask question/guess answer
 */
node *askQuestion(node *curr, node *prior, node *old, int answer) {
    if (!answer) {
        cout << curr->data << " 1[Yes] / 2[No]: ";
        cin >> answer;
    } else {
        switch(answer) {
            case 1: // YES
                if (hasChildren(curr->left)) {
                    cout << curr->left->data;
                    cout << " 1[Yes] / 2[No]: ";
                    cin >> answer;
                    old = prior;
                    prior = curr;
                    curr = curr->left;
                } else {
                    cout << "Is it a(n) "<< curr->left->data << "?";
                    cout << " 1[Yes] / 2[No]: ";
                    cin >> answer;
                    if (answer == 2) {
                        node *nodetoadd = addAnimal(curr->left);
                        curr->left = nodetoadd;
                        prior = curr->left;
                        curr = prior->left;
                    } else if (answer == 1) {
                        cout << "I'm right!";
                        old = prior;
                        prior = curr;
                        curr = curr->left;
                    }
                }
                break;

            case 2: // NO
                if (hasChildren(curr->right)) {
                    cout << curr->right->data;
                    cout << " 1[Yes] / 2[No]: ";
                    cin >> answer;
                    old = prior;
                    prior = curr;
                    curr = curr->right;
                } else {
                    cout << "Is it a(n) "<< curr->right->data << "??";
                    cout << " 1[Yes] / 2[No]: ";
                    cin >> answer;
                    if (answer == 2) {
                        node *nodetoadd = addAnimal(curr->right);
                        curr->right = nodetoadd;
                        prior = curr->right;
                        curr = prior->right;
                    } else if (answer == 1) {
                        cout << "I'm right!";
                        old = prior;
                        prior = curr;
                        curr = curr->left;
                    }
                }
                break;

            default:
                cout << "Invalid option";
                wanttoplay = 0;
        }

    }

    while (hasChildren(curr)) {
        curr = askQuestion(curr,prior,old,answer);
    }
    return curr;
}

/*
 * Checks whether the node has any children or not (leaf or not)
 */
int hasChildren(node *node) {
    if (node->left != NULL && node->right!= NULL)
        return 1;
    else
        return 0;
}

/*
 * Adding new node in the tree
 */
node *addAnimal(node *curr) {
    //char animal[64];
    //char question[128];
    string animal;
    string question;
    int ans = 0;
    std::cin.ignore(); //clear input buffer \n from previous cin

    cout << "\nI give up. The animal you are thinking of is a(n): ";
    getline (cin,animal);
    //cin.getline(animal,30,'\n');
    cout << "Please type a question that would distinguish a(n) " << animal << " from a(n) " << curr->data << ": ";
    getline (cin,question);
    //cin.getline(question,30,'\n');
    cout << "For a(n) " << animal << " the answer to your question is yes or no? 1[Yes] / 2[No]: ";
    cin >> ans;

    node *toreturn;
    if (ans == 1) toreturn = build(question,animal,curr->data);
    else if (ans == 2) toreturn = build(question,curr->data,animal);

    return toreturn;
}

int main()
{
    int traverse = 0;
    initialize();
    asktoplay();

    while(wanttoplay) {

        askQuestion(ROOTNODE, ROOTNODE, ROOTNODE, 0);
        cout << "\nThe tree so far: ";
        traversetree(ROOTNODE);
        asktoplay();

    }
    if (!wanttoplay) {
        cout << "\nTraverse the tree? 1[Yes] / 2[No]: ";
        cin >> traverse;
        if (traverse == 1) {
            cout << "\nThe tree: ";
            traversetree(ROOTNODE);
        }
    }
    cout << "\nThanks for playing!";
    cout << "Quiting...";
    return 0;
}