// Arup Guha
// 11/18/2011
// Example for COP 3223H
// A very short string class implemented with a linked list.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct letter {
    char c;
    struct letter* next;
};

struct wordlist {
    struct letter* wordPtr;
    struct wordlist* nextWord;
};

struct letter* makeWord(char name[]);
struct letter* insertFront(struct letter* front, char ch);
void printWord(struct letter* word);
int wordLength(struct letter* word);
int wordCompare(struct letter* word1, struct letter* word2);
struct letter* append(struct letter* list1, struct letter* list2);


void printWordList(struct wordlist* list);
struct wordlist* insertInOrder(struct wordlist* list,
                               struct letter* thisword);

int main() {

    struct wordlist* mylist = NULL;

    struct letter* w1 = makeWord("dog");
    struct letter* w2 = makeWord("cat");
    struct letter* w3 = makeWord("giraffe");
    struct letter* w4 = makeWord("elephant");
    mylist = insertInOrder(mylist, w1);
    printWordList(mylist);
    mylist = insertInOrder(mylist, w2);
    printWordList(mylist);
    mylist = insertInOrder(mylist, w3);
    printWordList(mylist);
    mylist = insertInOrder(mylist, w4);
    printWordList(mylist);
    return 0;
}

// Creates a linked list string from name.
struct letter* makeWord(char name[]) {

    struct letter* word = NULL;
    int i;

    // Just insert each letter in backwards order, to the front of the list.
    for (i=strlen(name)-1; i>=0; i--) {
        word = insertFront(word, name[i]);
    }

    return word;
}

// Creates a node storing ch and adds it to the front of the list pointed
// to by front.
struct letter* insertFront(struct letter* front, char ch) {

    // Create and fill the node.
    struct letter* newFront = (struct letter*)(malloc(sizeof(struct letter)));
    newFront->c = ch;

    // Link it to front and return.
    newFront->next = front;
    return newFront;
}

// Prints word, character by character.
void printWord(struct letter* word) {

    while (word != NULL) {
        printf("%c", word->c);
        word = word->next;
    }
}

// Returns the length of word.
int wordLength(struct letter* word) {

    int len = 0;

    // Count the nodes and return.
    while (word != NULL) {
        len++;
        word = word->next;
    }

    return len;
}

// Returns -1 if word1 precedes word2, lexicographically.
// Returns 0 if both are the same, and 1 if word1 comes
// after word2 lexicographically.
int wordCompare(struct letter* word1, struct letter* word2) {

    // Keep on comparing so long as both words have letters.
    while (word1 != NULL && word2 != NULL) {

        // These break a tie.
        if (word1->c < word2->c)
            return -1;
        else if (word1->c > word2->c)
            return 1;

        // Advance to the next letter in case of a tie.
        word1 = word1->next;
        word2 = word2->next;

    }

    // Identical words.
    if (word1 == NULL && word2 == NULL)
        return 0;

    // word1 is a prefix of word2
    else if (word1 == NULL)
        return -1;

    // word2 is a prefix of word1
    return 1;
}

struct letter* append(struct letter* list1, struct letter* list2) {

    // Special case of appending to a NULL list.
    if (list1 == NULL)
        return list2;

    // Move temp to point to the last node in the list.
    struct letter* temp = list1;
    while (temp->next != NULL)
        temp = temp->next;

    // Link the two together and return.
    temp->next = list2;
    return list1;
}

// Prints each word (in the order they are stored) in the list
// pointed to by list.
void printWordList(struct wordlist* list) {

    // Just iterate through each item in list.
    while (list != NULL) {

        // Notice that the parameter is the wordPtr of list.
        printWord(list->wordPtr);
        printf("\n");

        // And this is how we advance in the list.
        list = list->nextWord;
    }
    printf("\n");
}

struct wordlist* insertInOrder(struct wordlist* list,
                               struct letter* thisword) {

    // Allocate space for this word node.
    struct wordlist* word = (struct wordlist*)(malloc(sizeof(struct wordlist)));

    // We just move this pointer, because the linked list for our word has already been created.
    word->wordPtr = thisword;

    // Empty insert case.
    if (list == NULL) {
        word->nextWord = NULL;
        return word;
    }

    // The word to insert goes in the front.
    if (wordCompare(thisword, list->wordPtr) < 0) {
        word->nextWord = list;
        return word;
    }

    // Find the node right before the insert.
    struct wordlist* temp = list;
    while (temp->nextWord != NULL &&
           wordCompare(thisword, temp->nextWord->wordPtr) > 0) {
        temp = temp->nextWord;
    }

    // Patch our new word in the list.
    word->nextWord = temp->nextWord;
    temp->nextWord = word;
    return list;

}