#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>



struct Node{
    char *word;
    struct Node * next;
};


/**Node getLast()
* Returns the last element of the Noe list
*/
struct Node* getLast(struct Node *node){
    struct Node *temp = node;
    while(temp->next != NULL){
        temp = temp->next;
    }
    return temp;
}

/**Node getItemAt(Struct Node *node, int i)
* returns the item i items after the passed node.
* If list ends before ith element, returns the end of the list.
*/
struct Node* getItemAt(struct Node *node, int i){
    struct Node *temp = node;
    for(;i>0;i--){
        if(temp->next == NULL){
            break;
        }
        temp = temp->next;
    }

    return temp;
}

/**void insertNode(Struct Node *location, Struct Node *node)
* Inserts node behind the location node.
* if location is null, points location to node
*/
void insertNode(struct Node *location, struct Node *node){
    if(location == NULL){
        location = node;
    }else{
        node->next = location->next;
        location->next = node;
    }
}

/**void insertCorrectPosition(Struct Node *start, Struct Node *node)
* Inserts a node into the list at the correct location based on
* the alphabetical positioning of strings.
*/
struct Node* insertCorrectPosition(struct Node *start, struct Node *node){
    struct Node *cur = start;
    struct Node *last;
    bool isFront = true;
    while(cur != NULL  && strcmp(cur->word, node->word) <=0){
        last = cur;
        cur = cur->next;
        isFront = false;
    }
    //insertNode(last, node);
    node->next = cur;
    last->next = node;

    if(isFront){
        return node;
    }
    return start;
}


/** printWords(struct Node *node)
* prints the word array from each node from passed to end of the list.
*/
void printWords(struct Node *node){
    struct Node *temp = node;
    int i = 0;

    while(temp->next != NULL){
        printf("%d:\t%s\n", ++i, temp->word);
        temp = temp->next;
    }
    printf("%d:\t%s\n", ++i, temp->word);
}

int getCount(){
    bool correct = false;
    int currentGuess = 50;
    int userChoice;
    int range = 50;
    while(!correct){
        printf("Current Guess: %d\n", currentGuess);
        printf("Is the current guess...\n");
        printf("0  -  Higher\n");
        printf("1  -  Lower\n");
        printf("2  -  Correct\n");
        scanf("%d", &userChoice);

        if(range > 2)
            range /= 2;
        else
            range = 1;

        if(userChoice == 2)
            return currentGuess;
        else if(userChoice == 1){
            currentGuess -= range;
        }
        else if(userChoice == 0){
            currentGuess += range;
        }

    }
}

/** void freeList(struct Node *first)
* goes through the list freeing all nodes and strings.
*/
void freeList(struct Node *first){
    struct Node* temp;
    while(first != NULL){
        temp = first;
        first = first->next;
        free(temp->word);
        free(temp);
    }
}

/** char* getWord()
* requests for and returns a word entered from the console.
* Safely allows for arbitrarily large input.
*/
char* getWord(){
    unsigned int maxLength = 32;
    unsigned int curLength = 0;

    char *word = malloc(maxLength);
    curLength = maxLength;

    printf("Please enter your word. (NO WHITESPACE)\n");
    if(word != NULL){
        int c = EOF;
        unsigned int i = 0;

        //flush input
      //  fseek(stdin,0,SEEK_END);

        while((c=getchar()) != '\n' && c != EOF){
            word[i++] = (char) c;

            //If at max size, reallocate size.
            if(i == curLength){
                curLength = i+maxLength+1;
                word = realloc(word, curLength);
            }
        }

        word[i] = '\0';

    }else{
        printf("ERROR: word was null in getWord function.\n");
    }

    return word;
}
int main()
{
    int userNumber = getCount();

    int c;
    while((c=getchar()) != '\n' && c != EOF){} //FLUSHSHHHSHSHS

    printf("Your number: %d\n", userNumber );
    struct Node *start = (struct Node*)malloc(sizeof(struct Node));
    start->word = getWord();
    start->next = NULL;
    int i;

    for(i=1; i<userNumber; i++){
        struct Node *node = (struct Node*)malloc(sizeof(struct Node));
        node->word = getWord();
        node->next = NULL;

        //insertNode(getLast(start), node);
        start = insertCorrectPosition(start, node);
    }

    printWords(start);

    freeList(start);


    return 0;
}