/* ------------------------------------------------
  * OverBoard
  *
  * Class: CS 251, Fall 2014.  Thur 8am lab.
  * System: Terminal on Mac
  * Author: Alex Alvizo
  *
  * ToDo: Using Circular linked lists to get rid of androids
  * -------------------------------------------------
  */


#include <iostream> //for basic I/O
#include <fstream>  //to read from file
using namespace std;

//create a node
struct Node{
    char livingThing;
    Node *pNext;
};


//function that adds a node to the end of the list.  It takes in a list and character.
void appendNode(Node * &pTail, char c){
    //make a new node to insert
    Node *pTemp = new Node;
    //insert value
    pTemp->livingThing = c;
    pTemp->pNext = NULL;


    //if it is the first node
    if(pTail == NULL){
        pTail = pTemp;
        pTail->pNext = pTail;
    }


    //if the list is not empty
    if(pTail != NULL){
        //make the new node point to the head of the list
        pTemp->pNext = pTail->pNext;
        //connect it to the list by making the previous tail pointing to the new node
        pTail->pNext = pTemp;
    }
    else{
        pTemp->pNext = pTemp;
    }
    //reset tail pointer
    pTail = pTemp;
}//end of appendNode()
//-----------------------------------------------------------------------------------------------


//function to print out the list.  It takes in a list
void printList(Node * &pTail){
    //node to keep track of the tail
    Node *pTemp = pTail->pNext;
    //since its a circularly, singly linked list, i have to use a do-while so that it prints out the first thing then updates the
        //pNext and stops when it reaches pTail again.
    if(pTail != NULL){
        do{
            cout << pTemp->livingThing;
            pTemp= pTemp->pNext;
        }while(pTemp != pTail->pNext);
    }
    cout << endl << endl;
}//end of printList
//-----------------------------------------------------------------------------------------------


//function to read input from file and store into list.  It takes in a list.
void readFromFileAndStore(Node * &pTail){
    char c = ' ';

    //create file pointer
    FILE *pInputFile;
    //associate file pointer with actual file and try to open it
    pInputFile = fopen("abcd.txt", "r");
    //verify that it did open it
    if(pInputFile == NULL){
        cout << "Can't open " << pInputFile << "Verify that it is correct!" << endl;
        exit(-1);
    }
    while (fscanf(pInputFile, "%c", &c) != EOF){
        appendNode(pTail, c);
    }
}//end of readFromFileAndStore()
//------------------------------------------------------------------------------------------------


//function to count the number of nodes in the list.  It takes in a list and returns the number of nodes in a list
int numOfNodes(Node * &pTail){
    //node to keep track of the tail
    Node *pTemp = pTail;
    //counter
    int current = 0;
    //since its a circularly, singly linked list, i have to use a do-while so that it prints out the first thing then updates the
        //pNext and stops when it reaches pTail again.
    do{
        current++;
        pTemp= pTemp->pNext;
    }while(pTemp != pTail);

    return current;
}//end of numOfNodes
//------------------------------------------------------------------------------------------------


//function to delete a node.  It takes in a node to delete and a list
void deleteNode(Node * pCurrent, Node * &pTail){
    //keep track of where you started
    Node * pStart = pCurrent;

    //if list has one element
    if(pCurrent->pNext == pStart){
        delete pCurrent;
        pTail->pNext = NULL;
        cout << "List is Empty!\n";
    }
    //if it has more than 1 element
    while(pCurrent->pNext != pStart){
        //pCurrent at this point points to the previous node
        pCurrent= pCurrent->pNext;
    }
    //connect the previous node to the one after the deleted node
    Node * pTemp = pCurrent->pNext;
    pCurrent->pNext = pTemp->pNext;

    //
    if(pTail == pStart){
        pTail = pTemp->pNext;
    }
    delete pTemp;

}//end of popNode
//-------------------------------------------------------------------------------------------------


//function to make a copy of the list.  It takes in a list and returns a new list.
Node * cpyList(Node * pTail){
    //new list that is being created
    Node * pHead = NULL;
    //set node to the beggining of the list
    Node *pTemp = pTail->pNext;
    //since its a circularly, singly linked list, i have to use a do-while so that copies the first thing then updates the
        //pNext and stops when it reaches pTail again.
    if(pTail != NULL){
        do{
            //add node to the new list
            appendNode(pHead, pTemp->livingThing);
            //increment pTemp
            pTemp= pTemp->pNext;
        }while(pTemp != pTail->pNext);
    }
    return pHead;
}//end of Node * cpyList()
//--------------------------------------------------------------------------------------------------


//function that checks whether or not there are any androids.  It takes in a list and returns true or false.
int areThereAndroids(Node * &pTail){
    int value = 0;
    //node to keep track of the tail
    Node *pTemp = pTail->pNext;
    //since its a circularly, singly linked list, i have to use a do-while so that it prints out the first thing then updates the
        //pNext and stops when it reaches pTail again.
    if(pTail != NULL){
        do{
            if(pTemp->livingThing == 'A'){
                value = 1;
                break;
            }
            else{
                value = 0;
            }
            pTemp= pTemp->pNext;
        }while(pTemp != pTail->pNext);

    }
    return value;
}//end of areThereAndroids()
//--------------------------------------------------------------------------------------------------


//function checks whether or not the current node is a human or not  It takes in a list and number (n) and returns true or false.
int isSolution(Node * &pTail, Node * current){
    if(current->livingThing == 'H'){
        return 0;
    }
    else{
        return 1;
    }
    return 1;
}//end of solution()
//---------------------------------------------------------------------------------------------------


//function to get nth node
Node * nThNode(Node * &pTail, int n){
    //keeping track of head pointer
    Node * pHead = pTail->pNext;
    //traverse list until we reach the node we want
    while (n > 1 ){
        pHead = pHead->pNext;
        n--;
    }

    return pHead;
}//end of nThNode
//---------------------------------------------------------------------------------------------------


//main
int main()
{
    Node *pTail = NULL;
    Node *pHead = NULL;
    Node *pTemp = NULL;

    readFromFileAndStore(pTail);
    pHead = cpyList(pTail);

    int n = 1;
    int flag = 1;

    while(areThereAndroids(pHead) == 1){

        if(isSolution(pHead, nThNode(pHead, n)->pNext) == 1 && flag == 1){
            flag = 0;
            pTemp = nThNode(pHead, n);
            deleteNode(nThNode(pHead, n)->pNext, pHead);
            pHead = pTemp;
        }
        if(isSolution(pHead, nThNode(pHead, n-1)->pNext) == 1 && flag == 0){
            pTemp = nThNode(pHead, n-1);
            deleteNode(nThNode(pHead, n-1)->pNext, pHead);
            pHead = pTemp;

            if(areThereAndroids(pHead) == 0){
                cout << "\nSolution = " << n << endl;
                return 1;
            }
        }
        else{
            pHead = cpyList(pTail);
            n = n+1;
            flag = 1;
            if(n > numOfNodes(pHead)){
                cout << "\nThere is no solution!\n\n";
                return 0;
            }
        }
    }
    if(areThereAndroids(pHead) == 0){
        cout << "\nThere is no solution or the solution is 0!\n";
    }
    return 0;
}