/*
*
*  Nathan Balon
*  CIS 350
*  Data Structures and Algorithms
*  Univeristy of Michigan Dearborn
*
*  Program #2
*  Twenty Question Game
*
*  The program plays a game of twenty questions.  The game asks the user a
*  question which follows with the user answering the question yes or no.
*  Based on the previous question that is answered another question will be
*  given.  If the game comes to a question that it doesn't have an answer for
*  then the game will prompt the user for a new question.  The game will then 
*  learn from its users new questions to ask.
*
*/

#include <iostream>
#include <string>
#include <fstream>

using namespace std;

/*        Global constants                               */

const string FILE_NAME = "game_questions.txt";  // the name of the file to store the tree
const int ANSWER_POSITION = 0;                  // the position in the file for the answer 
const int NODE_TYPE_POSITION = 2;               // the position of the node type in the file
const int QUESTION_POSITION = 4;                // the position in the file for the question


/*        Globabl Functions                              */

bool gameFileExists();

/*****************************************************************************
*  Node class is used for nodes that are stored in a tree.
******************************************************************************/

class Node{      
  public:
    enum Answer {YES, NO, ROOT};
    enum NodeType {LEAF, INTERNAL};     
    Node(Node * parentNode, Answer answer, NodeType nodeType, string answer);

  private:
    string question_;           // the question to ask or the animal
    NodeType nodeType_;         // the type of node it is
    Answer answer_;             // the answer to the question
    Node * leftNode_;           // the nodes left child
    Node * rightNode_;          // the nodes right child
    Node * parentNode_;         // the parent to the node
    
    friend class QuestionTree;  // so the Question tree object can access 
                                // the private data contained in a node
};

/****************************************************************************
*   Member functions for Node
*****************************************************************************/

/*
*  Node creates a new instance of a Node object.
*  Parameter: question, the answer to be added to the node.
*  Precondition: Memory on the system must be availible to create a new node.
*  Postcondition: a new node object is created.
*/
Node::Node(Node * parentNode, Answer answer, NodeType nodeType, string question){
  question_ = question;
  answer_ = answer;
  nodeType_ = nodeType;
  parentNode_ = parentNode;
  leftNode_ = NULL;
  rightNode_ = NULL;
}

/***************************************************************************
*  QuestionTree class is used to store nodes of questions to plau a game
*  of twenty questions.
****************************************************************************/

class QuestionTree{
  public:
    QuestionTree();
    virtual ~QuestionTree();
    void play();
    void writeQuestionsFile();
    void openQuestionsFile();
  private:
    void askQuestion(Node * node);
    void writeNodeFile(Node * node, fstream & file);
    void addQuestion(Node * node);
    Node * getNewAnimal(Node * questionNode);
    void printTree(Node * node, int count);
    void deleteTree(Node * node);
    Node * buildNode(string stringToParse);
    
    Node * root_;                    // the root node of the tree
};

/****************************************************************************
*   Member Functions of QuestionTree
*****************************************************************************/


QuestionTree::QuestionTree(){
  root_ = NULL;
}
/**
*   ~QuestionTree the destructor for QuestionTree to reclaim resources.
*   Precondition:  A question tree object exists.
*   Postcondition: The resources held by a QuestionTree object will be return 
*                  to the system.
*/
QuestionTree::~QuestionTree(){
  deleteTree(root_);
}


/**
*   deleteTree removes all the nodes from the tree.
*   Precondition:   A tree exists
*   Postcondition:  All nodes in the tree are deleted.
*/
void QuestionTree::deleteTree(Node * node){
  if(node != NULL){
    deleteTree(node->leftNode_);
    deleteTree(node->rightNode_);
    delete node;
  }
}


/**
*   getNewQuestion gets a new question to be used for the game.
*   Precondition:  The game comes to a point where it doesn't have anymore
*                  questions to ask.
*   Postcondition: a new node is created with a new question.
*/
void QuestionTree::addQuestion(Node * node){
  Node * questionNode;         // a new question node to be added to the game
  Node * animalNode;           // a new animal to be added to the game
  Node * parent;               // the parent node   
  string question;             // the new question to ask
  
  // prompt the user for a new question to ask
  cout << "Give me a question to distinguish it: ";
  std::getline(cin, question);
  
  // create the node for the question
  questionNode = new Node(node, node->answer_, Node::INTERNAL, question);
  // create a new animal for the question
  animalNode = getNewAnimal(questionNode);

  // change the other animal nodes answer to the opposite
  if(animalNode->answer_ == Node::YES){ 
    node->answer_ = Node::NO;   
  }else{   
    node->answer_ = Node::YES;    
  }
  parent = node->parentNode_;
  // change the parent to point to the new question to be inserted in the tree
  if(parent->leftNode_ == node){
    if(parent->answer_ == Node::ROOT){
       questionNode->answer_ = Node::YES;  
    }                
    parent->leftNode_ = questionNode;
  }else{
    if(parent->answer_ == Node::ROOT){
       questionNode->answer_ = Node::NO;  
    }      
    parent->rightNode_ = questionNode;  
  }
  questionNode->parentNode_ = parent;
  // change the pointers to the animal nodes to point to the new question  
  node->parentNode_ = questionNode;
  questionNode->leftNode_ = node;
  animalNode->parentNode_ = questionNode;
  questionNode->rightNode_ = animalNode;
}
 
 
/**
*   getNewAnimal gets a new animal that is used for an answer to a question
*   in the game.
*   Precondition:  The game tree comes to leaf a node for which it doesn't
*                  have any more questions to ask.
*   Postcondition: A new animal node is created to be added to the tree.
*/

Node * QuestionTree::getNewAnimal(Node * questionNode){
  string buffer;                       // line entered by the user
  string answer;                       // the answer to the question
  string animalName;                   // the name of the animal
  bool enteredInvalidInput = false;    // has the user entered correct input
  Node * animalNode;                   // the new animal node to create

  // ask the user for a new animal to add
  do{
    if(enteredInvalidInput){
      cerr << "Invalid input, please enter again [yes/no animal]" << endl;
    }
    cout << "Give the response (yes/ no) and the new animal: ";
    std::getline(cin, buffer);
  } while(buffer.length() < 5 ? enteredInvalidInput = true
                                : enteredInvalidInput = false);
  // get if the answer was yes or no and create a new animal node 
  answer = buffer.substr(0,3);
  if(answer == "yes"){
    animalName = buffer.substr(4, buffer.length());
    animalNode = new Node(questionNode, Node::YES, Node::LEAF, animalName);
  } else if (answer == "no "){
    animalName = buffer.substr(3, buffer.length());
    animalNode = new Node(questionNode, Node::NO, Node::LEAF, animalName);
  }
  return animalNode;
}


/**
*  play starts the questions game.
*  Precondition:  A tree has been created to use for the game.
*  Postcondition: The end of the game has been reached and a new question may
*                 have been added to the game.
*/
void QuestionTree::play(){
  // start asking questions from the root of the tree
  askQuestion(root_);
}


/**
*   askQuestion, asks the questions contained in the game to the user.  The 
*   function recursively ask questions to the user untill either the machine 
*   wins and guesses correctly or the user enters a new question.
*   Precondition: 
*   Postcondition: 
*/

void QuestionTree::askQuestion(Node * node){
  string answer;                    // the answer to the question yes/no
  bool invalidInput = false;        // is the answer the correct format
  
  // format the question correctly if it is a question or an animal
  if((node->leftNode_ == NULL) && (node->rightNode_ == NULL)){
    cout << "Is it a " << node->question_ << "? ";
  } else {
    cout << node->question_ << "? ";
  }
  
  // prompt the user for the answer
  do{
    std::getline(cin, answer);
    if(answer == "yes" || answer == "no"){
      invalidInput = false;
    } else {
      cout << "Invalid input enter \"yes or no\"" << endl;
      invalidInput = true;    
    }      
  }while (invalidInput);
  // based on the users answer continue to ask question if more exist,
  // if a leaf node is found and the user answered yes display the meachine won,
  // or if a leaf node is found that the game doesn't have an answer for add
  // a new question to the tree.
  if(answer == "yes"){
    if(node->nodeType_ == Node::LEAF){
      cout << "Another win for Machine Intelligence! ";
    } else if((node->leftNode_ != NULL) && (node->leftNode_->answer_ == Node::YES)){
      askQuestion(node->leftNode_);            
    } else if((node->rightNode_ != NULL) && (node->rightNode_->answer_ == Node::YES)){
      askQuestion(node->rightNode_);
    } 
  } else if(answer == "no"){ 
    if((node->rightNode_ != NULL) && (node->rightNode_->answer_ == Node::NO)){
      askQuestion(node->rightNode_);      
    } else if((node->leftNode_ != NULL) && (node->leftNode_->answer_ == Node::NO)){
      askQuestion(node->leftNode_);   
    } else{       
      addQuestion(node); 
    }
  } 
}

/**
*  printTree displays the tree on standard output.  Used to debug the program.
*  Precondistion:  None
*  Postcondition:  The tree will be displayed.
*/
void QuestionTree::printTree(Node * node, int count){
  string spaces = "  ";         // spaces used to indicate a level
  string fill;                  // the number of spaces based on the level
  
  // create the space for the level before the node is displayes
  for(int i = 0; i < count; i++)
    fill += spaces;
  if(node != NULL){   
    printTree(node->leftNode_, count + 1);
    cout << fill << node->answer_  << " " << node->nodeType_ 
         << " " << node->question_ << endl;  
    printTree(node->rightNode_, count + 1);
  }
}

/**
*   buildNode, creates a new node from a string which it parses.
*   Precondition:  The string contain the correct format: which contains
*                  an interger in position 0 with the values 0, 1, or 2 and
*                  an interger in position 2 wiht the values of 0, 1
*                  the rest of the string contains either a question or an 
*                  animal which starts at position 4 in the string.
*   Postcondition: A new node will be created.
*/
Node* QuestionTree::buildNode(string lineIn){
  Node * node = NULL;                  // node to create from parsing the string
  Node::Answer answer;                 // the answer to the question yes/no
  Node::NodeType type;                 // the type of node it is leaf/internal
  string question;                     // the question contained in the file
  
  // check that the lines are long enough to contain the correct information
  if(lineIn.length() > QUESTION_POSITION + 1){
    // parse the answer yes or no to the question                       
    string input = lineIn.substr(ANSWER_POSITION,1);
    int nodeAnswer = atoi(input.c_str());
    answer = (Node::Answer)nodeAnswer;
    // parse the string to determine if the node is a leaf or an internal node
    input = lineIn.substr(NODE_TYPE_POSITION,1);    
    int typeOfNode = atoi(input.c_str());
    type = (Node::NodeType)typeOfNode;
    // parse the question
    question = lineIn.substr(QUESTION_POSITION, lineIn.length());
    // create a new node from the line read from the file
    node = new Node(NULL, answer, type, question);   
  } else {
    // if an invalid line in the file is found display an error message
    // cerr << "Invalid line in file\n";

  }
  return node;
}


/**
*   openQuestionsFile opens a file and reads all the lines in the file
*   creating a node in the tree for each and builds a tree from the nodes.
*   Precondition:  A file must exist that is in the correct format expected to
*                  be read by the method.
*   Postcondition: A tree will be created containing nodes for each line in the file.
*/

//  This method does not work correctly need to rewrite the the code.
//  Need to come up with another method to read in the tree.
 
void QuestionTree::openQuestionsFile(){
  Node * node;                         // node to create from the fill
  Node * previousNode = NULL;          // the previous node read in
  bool rootFound = false;              // has the root of the tree been found
  string buffer;                       // a buffer to hold a line from the file
  
  // open the file containing the tree
  fstream inFile(FILE_NAME.c_str(), ios::in);
  while(!inFile.eof()){  
    // read a line from the file  
    getline(inFile, buffer, '\n');
    // create a new node from the line read from the file
    node = buildNode(buffer);
    // if able to create the node add it to the correct location in the tree
    if(node != NULL){
      // if the root node is found set the root of the tree
      if(node->answer_ == Node::ROOT){
          root_ = node; 
          rootFound = true;         
      } 
      // get the first node to read in
      if(previousNode == NULL && node->nodeType_ == Node::LEAF){
        previousNode = node;
      } 
      // if the root node is found
      if(rootFound && node->answer_ == Node::ROOT){
        node->leftNode_ = previousNode;
        node->parentNode_ = NULL;   
        previousNode = node;   
      } else if(previousNode->nodeType_ == Node::LEAF && node->nodeType_ == Node::INTERNAL){
          node->leftNode_ = previousNode;
          previousNode->parentNode_ = node;        
          previousNode = node;     
      } else if(previousNode->nodeType_ == Node::INTERNAL && node->nodeType_ == Node::LEAF){
        if(rootFound){
          if(previousNode->leftNode_ == NULL){
            previousNode->leftNode_ = node;
          } else {
            previousNode->rightNode_ = node;
          }                         
          node->parentNode_ = previousNode;
          previousNode = previousNode;                           
        }else{
          if(previousNode->leftNode_ == NULL){
            previousNode->leftNode_ = node;
          } else {
            previousNode->rightNode_ = node;
          }
          node->parentNode_ = previousNode;
          previousNode = previousNode;
        }
      } else if(previousNode->nodeType_ == Node::INTERNAL && node->nodeType_ == Node::INTERNAL){        
        if(rootFound){
          previousNode->rightNode_ = node;
          node->parentNode_ = previousNode;
          previousNode = node;          
        }else{
          previousNode->parentNode_ = node;
          node->leftNode_ = previousNode;  
          previousNode = node;
        }
      }      
    }
  }
  inFile.close();
}


/**
*   writeQuestionsFile, writes the game tree to a file so it can be used
*   the next time the program is run.
*   Precondition:  A game tree exists that will be written to a file
*   Postcondition: the game tree is written to a file with the name given
*                  by the global constant FILE_NAME
*/

void QuestionTree::writeQuestionsFile(){
  // open the file to write to
  fstream outFile(FILE_NAME.c_str(), ios::out);  
  writeNodeFile(root_, outFile);
  outFile.close();
}


/**
*   writeNode, is a recursive function that writes a node in text format to a file.
*   Precondition:  A node exists to be written to a file.
*   Postcondition: If the node is not equal to null it is written to a file.
*                  The node will be written in the text format:
*                  [the answer to the question 0 for yes and 1 for no] { 
*                  [the type of node 0 for leaf or 1 for interior]
*                  [the question or animal]
*/

void QuestionTree::writeNodeFile(Node * node, fstream & outFile){
  if(node != NULL){
    writeNodeFile(node->leftNode_, outFile);      
    outFile << node->answer_ << " " << node->nodeType_ << " "
            << node->question_ << endl;      
    writeNodeFile(node->rightNode_, outFile);
  }
}

/****************************************************************************
*    Global Functions
*****************************************************************************/


/**
*   gameFileExists check to see if a file given by the global constant
*   FILE_NAME exists in the current directory.
*   Precondition:  None
*   Postcondition: returns a bool of indicating if the game file exists in the
*                  current directory.
*/

bool gameFileExists(){
  bool fileExists;     // if the game file exists or not
  ofstream checkFile(FILE_NAME.c_str(), ios_base::in);
  if(checkFile){
    checkFile.close();
    fileExists = true;
  } else {
    fileExists = false;
  }
  return fileExists;
}


/*****************************************************************************
*                           Main
*****************************************************************************/


/*
*  main: The main entry point to the program.
*  Precondition:  A file will exist that contains the answers to be used for
*                 the game.  The file must also be in the correct format.
*  Postcondition: The game will complete and any new question that were added
*                 will be written to the file.
*/

int main( int argc, char * argv[] ){
  bool playAgain = true;          // play the game another time
  string inputBuffer;             // holds the users input
  QuestionTree * game;            // game tree to play the game

  cout << "                 The 20 Questions Game\n";
  cout << "-------------------------------------------------------------------\n" 
       << endl;
  // check if an input file exists for the game if one does open it and use it
  // or signal an error message.
  if(gameFileExists()){
    game = new QuestionTree();
    game->openQuestionsFile();
  } else {
    cerr << "Unable to locate the file to play the game" << endl;
    exit(1);
  }
  // continue playing the game while the user answers yes
  while(playAgain){
    game->play();
    cout << "Want to play again (yes/no)? ";
    getline(cin, inputBuffer);
    if(inputBuffer != "yes"){
      playAgain = false;
    }
  }
  // When the game terminates write the game tree to a file
  game->writeQuestionsFile();
  delete game;
  return 0;
}