// 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 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);

int main() {

    struct letter* w1 = makeWord("Happy ");
    struct letter* w2 = makeWord("Early Thanksgiving!");

    printWord(w1);
    printf("\n");
    printWord(w2);
    printf("\n");
    printf("Length of word 1 is %d\n", wordLength(w1));

    if (wordCompare(w1, w2) > 0)
        printf("Word 1 comes after Word 2.\n");

    w1 = append(w1, w2);
    printWord(w1);
    printf("\n");

}

// 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;
}