#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"
#include "queue.h"

#define MAX_FILENAME 100

int main(void)
{
    //variables
    int selectionComplete = 0, numBranches;

    char graphFile[MAX_FILENAME], heurFile[MAX_FILENAME];
    char* startC;
    char* goalC;

    //prompt the user for graph and heuristic file names
    printf("Enter the graph information filename: \n");
    fgets(graphFile, MAX_FILENAME, stdin);

    printf("Enter the graph heuristic filename: \n");
    fgets(heurFile, MAX_FILENAME, stdin);

    //prompt the user for the goal nodes
    printf("Enter the start node: \n");
    startC = fgetc(stdin);

    printf("Please enter the goal node: \n");
    goalC = fgetc(stdin);

    //prompt the user for K branch search value
    printf("Please enter the amount of branches to search: \n");
    while (selectionComplete != 1)
    {
        scanf("%d", &numBranches);
        if (numBranches < 1 || numBranches > 3)
        {
            printf("Please enter a valid number between 1 and 3 inclusive...\n");
        }
        else
        {
            printf("Branches to Search: %d\n", numBranches);
            selectionComplete = 1;
        }
    }

    printf("Beginning search...\n");

    //DEBUG
    printf("%s %s %c %c %d\n", graphFile, heurFile, startC, goalC, numBranches);

    FILE* graphFP = fopen(graphFile, "r");
    if (graphFP == NULL)
    {
        perror("Error opening graph file");
    }
    else
    {
        FILE* heurFP = fopen(heurFile, "r");
        if (heurFP == NULL)
        {
            fclose(graphFP);
            perror("Error opening heuristic file");
        }
        else
        {
            printf("getting there...\n");
        }
    }

    //create the graph linked list
    Head* graphListPtr = (Head*)malloc(sizeof(Head));
    graphListPtr->first = NULL;

    //variables
    int readCnt, EndOfFile = 1;
    Node *graphCurrentPtr, *heurCurrentPtr;
    char *graphA, *graphB, *heurA;

    //populate the graph list with data from the file
    do
    {
        //create a data array
        GraphData* graphDataArray = (GraphData*)malloc(sizeof(GraphData));
        readCnt = fscanf(graphFP, "%c %c %d", graphA, graphB, &(graphDataArray->graphArray[2]));
        if (readCnt != 3)
        {
            EndOfFile = 0;
        }
        else
        {
            //convert the characters to integers
            &(graphDataArray->graphArray[0]) = atoi(graphA);
            &(graphDataArray->graphArray[1]) = atoi(graphB);

            //create a new node and move across all the data
            Node* newNode = (Node*)malloc(sizeof(Node*));
            newNode->data = graphDataArray;
            newNode->nextNode = listPtr->first;
            listPtr->first = newNode;
        }
    } while(EndOfFile != 0);

    //do the same again for the heuristic file
    //create the heuristic linked list
    Head* heurListPtr = (Head*)malloc(sizeof(Head));
    heurListPtr->first = NULL;

    //populate the heuristic list with data from the file
    do
    {
        //create a data array
        HeurData* heurDataArray = (HeurData*)malloc(sizeof(HeurData));
        readCnt = fscanf(heurFP, "%c %d", heurA, &(heurDataArray->heurArray[1]));
        if (readCnt != 2)
        {
            EndOfFile = 0;
        }
        else
        {
            //convert the char to an integer
            &(heurDataArray->heurArray[0]) = atoi(heurA);
            //create a new node and copy across all the data
            Node* newNode = (Node*)malloc(sizeof(Node*));
            newNode->data = heurDataArray;
            newNode->nextNode = listPtr->first;
            listPtr->first = newNode;
        }
    } while(EndOfFile != 0);

    //DEBUG: traverse the list and print all the values to the terminal
    graphCurrentPtr = graphListPtr->first;
    while (graphCurrentPtr->nextNode != NULL)
    {
       printf("%d %d %d\n", graphCurrentPtr->nodeData->graphArray[0], graphCurrentPtr->nodeData->graphArray[1], graphCurrentPtr->nodeData->graphArray[2]);
       graphCurrentPtr = graphCurrentPtr->nextNode;
    }

    heurCurrentPtr = heurListPtr->first;
    while (heurCurrentPtr->nextNode != NULL)
    {
       printf("%d %d\n", heurCurrentPtr->nodeData->heurArray[0], heurCurrentPtr->nodeData->heurArray[1]);
       heurCurrentPtr = heurCurrentPtr->nextNode;
    }

    //search goes here
    //greedy search with additional branches in memory
    //find starting node
    int start, goal, i, goalFound = 0;

    graphCurrentPtr = graphListPtr->first;
    while (graphCurrentPtr->nodeData->graphArray[0] != start) //check that the starting char is equal to the starting node
    {
       graphCurrentPtr = graphCurrentPtr->nextNode;
    }

    //save start into the traversed queue
    add_data(start);

    //from starting node, depending on size of K load best (smallest heuristic) K amount of branches into queue
    //continue down tree, adding the best K nodes into the queue at each node expanded
    //loop till goal found
    int currentSmallestBranch, possibleSmallestBranch, currentTerminalNode;

    //create a checked list for the path
    Head* checkedListPtr = (Head*)malloc(sizeof(Head));
    checkedListPtr->first = NULL;

    Node* checkedCurrentPtr;

    while(goalFound != 1)
    {
        currentTerminalNode = check_front(); //pull the current deepest node
        graphCurrentPtr = graphListPtr->first;
        heurCurrentPtr = heurListPtr->first;

        //reset the current smallest branch value to something really big
        currentSmallestBranch = 10000;
        i=0;

        if (currentTerminalNode != goal) //if this current pulled node is not the goal
        {
            do
            {
                //loop through the graph list and find the terminal node K number of branches, make note of the heuristic value for the branches.
                //loop graph list, find same value in 1st column
                //
                do
                {
                    if (graphCurrentPtr->nodeData->graphArray[0] == currentTerminalNode) //we have found a branch
                    {
                        do
                        {
                            //find the second value in the heuristic list
                            if (heurCurrentPtr->nodeData->heurArray[0] == graphCurrentPtr->nodeData->graphArray[1])
                            {
                                //update the possible smallest heursitic
                                possibleSmallestBranch == heurCurrentPtr->nodeData->heurArray[1];//save that branch length
                                if (possibleSmallestBranch < currentSmallestBranch)
                                {
                                    currentSmallestBranch = possibleSmallestBranch //update the current smallest branch value if the new one is smaller
                                }
                            }
                            heurCurrentPtr = heurCurrentPtr->nextNode;
                        } while (heurCurrentPtr->nextNode != NULL)
                    }
                    graphCurrentPtr = graphCurrentPtr->nextNode;
                } while (graphCurrentPtr->nextNode != NULL) //finish at the end of the graph list

                //load the smallest offshoot node into the queue
                add_data(currentSmallestBranch);
                i++
            } while (i != 3) //keep looping until the branch counter is exhausted

            //load the checked node into the checked list
            CheckedData* checkedDataVal = (CheckedData*)malloc(sizeof(CheckedData));
            &(checkedDataVal->checkedVal) = currentTerminalNode;
        }
        else
        {
            goalFound = 1;
        }
    }

    //once a goal is found, traverse the checked node list and interatively find the shortest path
    printf("Shortest Path: \n");
    checkedCurrentPtr = checkedListPtr->first;
    while (checkedCurrentPtr->nextNode != NULL)
    {
       printf("%d - ", checkedCurrentPtr->nodeData->checkedVal);
       checkedCurrentPtr = checkedCurrentPtr->nextNode;
    }
    printf("\n");

    //free all memory
    fclose(graphFP);
    graphCurrentPtr = graphListPtr->first;
    Node* temp; /*create a temporary node pointer*/
    while (temp != NULL)
    {
        temp = currentPtr->nextNode;
        free(currentPtr->nodeData);
        free(currentPtr);
        currentPtr = temp;
    }
    free(graphListPtr);

    fclose(heurFP);
    heurCurrentPtr = heurListPtr->first;
    while (temp != NULL)
    {
        temp = currentPtr->nextNode;
        free(currentPtr->nodeData);
        free(currentPtr);
        currentPtr = temp;
    }
    free(heurListPtr);

    checkedCurrentPtr = ckeckedListPtr->first;
    while (temp != NULL)
    {
        temp = checkedCurrentPtr->nextNode;
        free(checkedCurrentPtr->nodeData);
        free(checkedCurrentPtr);
        checkedCurrentPtr = temp;
    }
    free(checkedListPtr);

    return 0;
}