Living Anagrams

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

#define FCLOSE(fd) fclose(fd), fd = NULL
#define FREE(p) free(p), p = NULL

#define CHUNK_SIZE 65536

#define Agrave -64
#define Aacute -63
#define Acirc -62
#define Atilde -61
#define Auml -60
#define Ccedil -57
#define Egrave -56
#define Eacute -55
#define Ecirc -54
#define Euml -53
#define Igrave -52
#define Iacute -51
#define Icirc -50
#define Iuml -49
#define Ntilde -47
#define Ograve -46
#define Oacute -45
#define Ocirc -44
#define Otilde -43
#define Ouml -42
#define Ugrave -39
#define Uacute -38
#define Ucirc -37
#define Uuml -36
#define Yacute -35
#define agrave -32
#define aacute -31
#define acirc -30
#define atilde -29
#define auml -28
#define ccedil -25
#define egrave -24
#define eacute -23
#define ecirc -22
#define euml -21
#define igrave -20
#define iacute -19
#define icirc -18
#define iuml -17
#define ntilde -15
#define ograve -14
#define oacute -13
#define ocirc -12
#define otilde -11
#define ouml -10
#define ugrave -7
#define uacute -6
#define ucirc -5
#define uuml -4
#define yacute -3

#define HASH_INIT 5381
#define HASH_SHIFT 5

#define REQ_PATH "p"
#define REQ_VIEW "v"
#define REQ_QUIT "q"

typedef struct dictionary_s dictionary_t;
struct dictionary_s {
    size_t nwords;
    char **words;
};

typedef struct anagram_s anagram_t;
struct anagram_s {
    size_t szkey;
    char *key;
    dictionary_t list;
    size_t nlinks;
    anagram_t **links;
    int marked;
    anagram_t *ancestor;
    anagram_t *next;
};

typedef struct hanagrams_s hanagrams_t;
struct hanagrams_s {
    size_t nanagrams;
    anagram_t **anagrams;
};

void log_error(const char *, ...);
size_t line_size(char *);
int compare_chars(const void *, const void *);
size_t hash_key(size_t, const char *, size_t);
size_t word_index(const dictionary_t *, const char *);
anagram_t *get_anagram(size_t, const char *, const hanagrams_t *);
void dictionary_cleanup(dictionary_t *);
void anagram_cleanup(anagram_t *);
void hanagrams_cleanup(hanagrams_t *);
void set_char(char *, size_t *, char);
int line_to_word(size_t, const char *, size_t, char *);
void read_dictionary_cleanup(char *, FILE *);
dictionary_t *read_dictionary(const char *);
size_t next_prime(size_t);
anagram_t *get_anagram_and_hash(size_t, const char *, const hanagrams_t *, size_t *);
int add_word_to_list(dictionary_t *, char *);
void delete_char(size_t *, char *, size_t);
size_t insert_index(size_t, const char *, size_t, char);
void insert_char(size_t *, char *, size_t, char);
int add_link(anagram_t *, anagram_t *);
int test_anagram(anagram_t *, const hanagrams_t *);
size_t insert_char_loop(char, char, size_t, anagram_t *, const hanagrams_t *);
int dr_links(anagram_t *, size_t, const hanagrams_t *);
anagram_t *create_anagram(size_t, char *, char *, anagram_t *, const hanagrams_t *);
hanagrams_t *create_hanagrams(const dictionary_t *);
size_t read_separators(size_t, const char *, size_t);
size_t read_letters(size_t, const char *, size_t);
anagram_t *get_anagram_from_word(size_t, const char *, const hanagrams_t *);
void print_path(const anagram_t *, const anagram_t *);
void search_path(const char *, anagram_t *, const char *, anagram_t *);
void view_anagram(const anagram_t *);
int process_requests(const hanagrams_t *);

void log_error(const char *format, ...) {
va_list args;
    va_start(args, format);
    vfprintf(stderr, format, args);
    va_end(args);
}

size_t line_size(char *line) {
size_t size = strlen(line);
    if (line[size-1] == '\n') {
        line[size-1] = 0;
        size--;
    }
    return size;
}

int compare_chars(const void *a, const void *b) {
const char *pa = a, *pb = b;
    return *pa-*pb;
}

size_t hash_key(size_t szkey, const char *key, size_t nanagrams) {
size_t hash = HASH_INIT, i;
    for (i = 0; i < szkey; i++) hash += (hash << HASH_SHIFT)+(unsigned char)key[i];
    return hash%nanagrams;
}

size_t word_index(const dictionary_t *list, const char *word) {
size_t i;
    for (i = 0; i < list->nwords && strcmp(list->words[i], word); i++);
    return i;
}

anagram_t *get_anagram(size_t szkey, const char *key, const hanagrams_t *hanagrams) {
anagram_t *anagram = NULL;
    for (anagram = hanagrams->anagrams[hash_key(szkey, key, hanagrams->nanagrams)]; anagram && strcmp(anagram->key, key); anagram = anagram->next);
    return anagram;
}

void dictionary_cleanup(dictionary_t *dictionary) {
size_t i;
    if (dictionary) {
        if (dictionary->words) {
            for (i = 0; i < dictionary->nwords; i++) FREE(dictionary->words[i]);
            FREE(dictionary->words);
        }
        FREE(dictionary);
    }
}

void anagram_cleanup(anagram_t *anagram) {
anagram_t *tmpanagram;
    while (anagram) {
        if (anagram->links) FREE(anagram->links);
        if (anagram->list.words) FREE(anagram->list.words);
        FREE(anagram->key);
        tmpanagram = anagram->next;
        FREE(anagram);
        anagram = tmpanagram;
    }
}

void hanagrams_cleanup(hanagrams_t *hanagrams) {
size_t i;
    if (hanagrams) {
        if (hanagrams->anagrams) {
            for (i = 0; i < hanagrams->nanagrams; i++) anagram_cleanup(hanagrams->anagrams[i]);
            FREE(hanagrams->anagrams);
        }
        FREE(hanagrams);
    }
}

void set_char(char *word, size_t *ind, char chr) {
    word[*ind] = chr;
    (*ind)++;
}

int line_to_word(size_t szline, const char *line, size_t nwords, char *word) {
int r = 1;
size_t i, j = 0;
    for (i = 0; i < szline && r; i++) {
        if (line[i] >= 'A' && line[i] <= 'Z') set_char(word, &j, line[i]);
        else if (line[i] >= 'a' && line[i] <= 'z') set_char(word, &j, (char)(line[i]-' '));
        else {
            switch (line[i]) {
            case Agrave:
            case Aacute:
            case Acirc:
            case Atilde:
            case Auml:
            case agrave:
            case aacute:
            case acirc:
            case atilde:
            case auml:
                set_char(word, &j, 'A');
                break;
            case Ccedil:
            case ccedil:
                set_char(word, &j, 'C');
                break;
            case Egrave:
            case Eacute:
            case Ecirc:
            case Euml:
            case egrave:
            case eacute:
            case ecirc:
            case euml:
                set_char(word, &j, 'E');
                break;
            case Igrave:
            case Iacute:
            case Icirc:
            case Iuml:
            case igrave:
            case iacute:
            case icirc:
            case iuml:
                set_char(word, &j, 'I');
                break;
            case Ograve:
            case Oacute:
            case Ocirc:
            case Otilde:
            case Ouml:
            case ograve:
            case oacute:
            case ocirc:
            case otilde:
            case ouml:
                set_char(word, &j, 'O');
                break;
            case Ugrave:
            case Uacute:
            case Ucirc:
            case Uuml:
            case ugrave:
            case uacute:
            case ucirc:
            case uuml:
                set_char(word, &j, 'U');
                break;
            case Yacute:
            case yacute:
                set_char(word, &j, 'Y');
                break;
            case '-':
                break;
            default:
                r = 0;
                break;
            }
        }
    }
    if (r) word[j] = 0;
    else log_error("line_to_word: line %u invalid character 0x%02x\n", nwords+1, line[i]);
    return r;
}

void read_dictionary_cleanup(char *line, FILE *fd) {
    if (fd) FCLOSE(fd);
    if (line) FREE(line);
}

dictionary_t *read_dictionary(const char *filename) {
char *line = NULL, *tmpline = NULL, **tmpwords = NULL;
size_t maxnwords, maxszline, szline;
FILE *fd = NULL;
dictionary_t *dictionary = NULL;
    if (!(dictionary = malloc(sizeof(dictionary_t)))) {
        log_error("read_dictionary: malloc error (dictionary)\n");
        return NULL;
    }
    maxnwords = CHUNK_SIZE;
    if (!(dictionary->words = malloc(sizeof(char *)*maxnwords))) {
        log_error("read_dictionary: malloc error (dictionary->words)\n");
        dictionary_cleanup(dictionary);
        return NULL;
    }
    dictionary->nwords = 0;
    maxszline = CHUNK_SIZE;
    if (!(line = malloc(sizeof(char)*(maxszline+1)))) {
        log_error("read_dictionary: malloc error (line)\n");
        read_dictionary_cleanup(line, fd);
        dictionary_cleanup(dictionary);
        return NULL;
    }
    if (!(fd = fopen(filename, "r"))) {
        log_error("read_dictionary: cannot open file %s\n", filename);
        read_dictionary_cleanup(line, fd);
        dictionary_cleanup(dictionary);
        return NULL;
    }
    while (fgets(line, (int)maxszline+1, fd)) {
        while ((szline = line_size(line)) == maxszline) {
            maxszline += CHUNK_SIZE;
            if (!(tmpline = realloc(line, sizeof(char)*(maxszline+1)))) {
                log_error("read_dictionary: realloc error (line)\n");
                read_dictionary_cleanup(line, fd);
                dictionary_cleanup(dictionary);
                return NULL;
            }
            line = tmpline;
            fgets(&line[maxszline-CHUNK_SIZE], CHUNK_SIZE+1, fd);
        }
        if (dictionary->nwords == maxnwords) {
            maxnwords += CHUNK_SIZE;
            if (!(tmpwords = realloc(dictionary->words, sizeof(char *)*maxnwords))) {
                log_error("read_dictionary: realloc error (dictionary->words)\n");
                read_dictionary_cleanup(line, fd);
                dictionary_cleanup(dictionary);
                return NULL;
            }
            dictionary->words = tmpwords;
        }
        if (!(dictionary->words[dictionary->nwords] = malloc(sizeof(char)*(szline+1)))) {
            log_error("read_dictionary: malloc error (dictionary->words[%u])\n", dictionary->nwords);
            read_dictionary_cleanup(line, fd);
            dictionary_cleanup(dictionary);
            return NULL;
        }
        if (!line_to_word(szline, line, dictionary->nwords, dictionary->words[dictionary->nwords])) {
            read_dictionary_cleanup(line, fd);
            dictionary_cleanup(dictionary);
            return NULL;
        }
        dictionary->nwords++;
    }
    read_dictionary_cleanup(line, fd);
    return dictionary;
}

size_t next_prime(size_t v) {
size_t p = v | 1, i;
    do {
        for (i = 3; i*i <= p && p%i; i += 2);
        if (i*i <= p) p += 2;
    }
    while (i*i <= p);
    return p;
}

anagram_t *get_anagram_and_hash(size_t szkey, const char *key, const hanagrams_t *hanagrams, size_t *hash) {
anagram_t *anagram = NULL;
    for (anagram = hanagrams->anagrams[(*hash = hash_key(szkey, key, hanagrams->nanagrams))]; anagram && strcmp(anagram->key, key); anagram = anagram->next);
    return anagram;
}

int add_word_to_list(dictionary_t *list, char *word) {
char **tmpwords = NULL;
    if (word_index(list, word) == list->nwords) {
        list->nwords++;
        if (!(tmpwords = realloc(list->words, sizeof(char *)*list->nwords))) {
            log_error("add_word_to_list: realloc error (list->words)\n");
            return 0;
        }
        list->words = tmpwords;
        list->words[list->nwords-1] = word;
    }
    return 1;
}

void delete_char(size_t *szkey, char *key, size_t ind) {
size_t i;
    for (i = ind; i < *szkey; i++) key[i] = key[i+1];
    (*szkey)--;
}

size_t insert_index(size_t szkey, const char *key, size_t ind, char c) {
    while (ind < szkey && key[ind] < c) ind++;
    return ind;
}

void insert_char(size_t *szkey, char *key, size_t ind, char c) {
size_t i;
    for (i = *szkey+1; i > ind; i--) key[i] = key[i-1];
    key[ind] = c;
    (*szkey)++;
}

int add_link(anagram_t *anagram, anagram_t *add) {
anagram_t **tmplinks = NULL;
    anagram->nlinks++;
    if (anagram->nlinks > 1) {
        if (!(tmplinks = realloc(anagram->links, sizeof(anagram_t *)*anagram->nlinks))) {
            log_error("add_link: realloc error (anagram->links)\n");
            return 0;
        }
        anagram->links = tmplinks;
    }
    else {
        if (!(anagram->links = malloc(sizeof(anagram_t *)))) {
            log_error("add_link: malloc error (anagram->links)\n");
            return 0;
        }
    }
    anagram->links[anagram->nlinks-1] = add;
    return 1;
}

int test_anagram(anagram_t *anagram, const hanagrams_t *hanagrams) {
anagram_t *test = NULL;
    if ((test = get_anagram(anagram->szkey, anagram->key, hanagrams))) {
        if (!add_link(anagram, test)) return 0;
        if (!add_link(test, anagram)) return 0;
    }
    return 1;
}

size_t insert_char_loop(char c1, char c2, size_t ind, anagram_t *anagram, const hanagrams_t *hanagrams) {
char c;
    for (c = c1; c <= c2; c++) {
        ind = insert_index(anagram->szkey, anagram->key, ind, c);
        insert_char(&anagram->szkey, anagram->key, ind, c);
        if (!test_anagram(anagram, hanagrams)) return 0;
        delete_char(&anagram->szkey, anagram->key, ind);
    }
    return ind;
}

int dr_links(anagram_t *anagram, size_t ind, const hanagrams_t *hanagrams) {
char c;
    c = anagram->key[ind];
    delete_char(&anagram->szkey, anagram->key, ind);
    if (!test_anagram(anagram, hanagrams)) return 0;
    insert_char_loop((char)(c+1), 'Z', insert_char_loop('A', (char)(c-1), 0, anagram, hanagrams), anagram, hanagrams);
    insert_char(&anagram->szkey, anagram->key, ind, c);
    return 1;
}

anagram_t *create_anagram(size_t szkey, char *key, char *word, anagram_t *next, const hanagrams_t *hanagrams) {
size_t i;
anagram_t *anagram = NULL;
    if (!(anagram = malloc(sizeof(anagram_t)))) {
        log_error("create_anagram: malloc error (anagram)\n");
        return NULL;
    }
    anagram->szkey = szkey;
    anagram->key = key;
    anagram->list.words = NULL;
    anagram->links = NULL;
    anagram->list.nwords = 1;
    if (!(anagram->list.words = malloc(sizeof(char *)))) {
        log_error("create_anagram: malloc error (anagram->list.words)\n");
        anagram_cleanup(anagram);
        return NULL;
    }
    anagram->list.words[0] = word;
    anagram->nlinks = 0;
    if (!dr_links(anagram, 0, hanagrams)) {
        anagram_cleanup(anagram);
        return NULL;
    }
    for (i = 1; i < szkey; i++) {
        if (key[i] > key[i-1]) {
            if (!dr_links(anagram, i, hanagrams)) {
                anagram_cleanup(anagram);
                return NULL;
            }
        }
    }
    insert_char_loop('A', 'Z', 0, anagram, hanagrams);
    anagram->marked = 0;
    anagram->ancestor = NULL;
    anagram->next = next;
    return anagram;
}

hanagrams_t *create_hanagrams(const dictionary_t *dictionary) {
char *key = NULL;
size_t szword, hash, i;
anagram_t *anagram = NULL;
hanagrams_t *hanagrams = NULL;
    if (!(hanagrams = malloc(sizeof(hanagrams_t)))) {
        log_error("create_hanagrams: malloc error (hanagrams)\n");
        return NULL;
    }
    hanagrams->nanagrams = next_prime(dictionary->nwords);
    if (!(hanagrams->anagrams = malloc(sizeof(anagram_t *)*hanagrams->nanagrams))) {
        log_error("create_hanagrams: malloc error (hanagrams->anagrams)\n");
        hanagrams_cleanup(hanagrams);
        return NULL;
    }
    for (i = 0; i < hanagrams->nanagrams; i++) hanagrams->anagrams[i] = NULL;
    for (i = 0; i < dictionary->nwords; i++) {
        szword = strlen(dictionary->words[i]);
        if (!(key = malloc(sizeof(char)*(szword+2)))) {
            log_error("create_hanagrams: malloc error (key)\n");
            hanagrams_cleanup(hanagrams);
            return NULL;
        }
        strcpy(key, dictionary->words[i]);
        qsort(key, szword, sizeof(char), compare_chars);
        if ((anagram = get_anagram_and_hash(szword, key, hanagrams, &hash))) {
            FREE(key);
            if (!add_word_to_list(&anagram->list, dictionary->words[i])) {
                hanagrams_cleanup(hanagrams);
                return NULL;
            }
        }
        else {
            if (!(hanagrams->anagrams[hash] = create_anagram(szword, key, dictionary->words[i], hanagrams->anagrams[hash], hanagrams))) {
                FREE(key);
                hanagrams_cleanup(hanagrams);
                return NULL;
            }
        }
    }
    return hanagrams;
}

size_t read_separators(size_t szline, const char *line, size_t ind) {
    while (ind < szline && (line[ind] == ' ' || line[ind] == '\t')) ind++;
    return ind;
}

size_t read_letters(size_t szline, const char *line, size_t ind) {
    while (ind < szline && line[ind] >= 'A' && line[ind] <= 'Z') ind++;
    return ind;
}

anagram_t *get_anagram_from_word(size_t szword, const char *word, const hanagrams_t *hanagrams) {
char *key = NULL;
anagram_t *anagram = NULL;
    if (!(key = malloc(sizeof(char)*(szword+1)))) {
        log_error("get_anagram_from_word: malloc error (key)\n");
        return NULL;
    }
    strcpy(key, word);
    qsort(key, szword, sizeof(char), compare_chars);
    if ((anagram = get_anagram(szword, key, hanagrams))) {
        FREE(key);
        if (word_index(&anagram->list, word) < anagram->list.nwords) return anagram;
        else {
            log_error("get_anagram_from_word: word %s not found\n", word);
            return NULL;
        }
    }
    else {
        log_error("get_anagram_from_word: key %s not found\n", key);
        FREE(key);
        return NULL;
    }
}

void print_path(const anagram_t *anagram, const anagram_t *first) {
    if (anagram != first) {
        print_path(anagram->ancestor, first);
        fprintf(stdout, " %s", anagram->list.words[0]);
    }
}

void search_path(const char *word1, anagram_t *anagram1, const char *word2, anagram_t *anagram2) {
size_t maxszqueue, szqueue, i, j;
anagram_t **queue = NULL, **tmpqueue = NULL;
    maxszqueue = CHUNK_SIZE;
    if (!(queue = malloc(sizeof(anagram_t *)*maxszqueue))) {
        log_error("search_path: malloc error (queue)\n");
        return;
    }
    szqueue = 1;
    queue[0] = anagram1;
    queue[0]->marked = 1;
    for (i = 0; i < szqueue && queue[i] != anagram2; i++) {
        for (j = 0; j < queue[i]->nlinks; j++) {
            if (!queue[i]->links[j]->marked) {
                if (szqueue == maxszqueue) {
                    maxszqueue += CHUNK_SIZE;
                    if (!(tmpqueue = realloc(queue, sizeof(anagram_t *)*maxszqueue))) {
                        log_error("search_path: realloc error (queue)\n");
                        FREE(queue);
                        return;
                    }
                    queue = tmpqueue;
                }
                queue[szqueue] = queue[i]->links[j];
                queue[szqueue]->marked = 1;
                queue[szqueue]->ancestor = queue[i];
                szqueue++;
            }
        }
    }
    if (anagram1 != anagram2 && i < szqueue) {
        fprintf(stdout, "Path %s", word1);
        print_path(anagram2->ancestor, anagram1);
        fprintf(stdout, " %s\n", word2);
        fflush(stdout);
    }
    else log_error("No path found between %s and %s\n", word1, word2);
    queue[0]->marked = 0;
    for (i = 1; i < szqueue; i++) {
        queue[i]->marked = 0;
        queue[i]->ancestor = NULL;
    }
    FREE(queue);
}

void view_anagram(const anagram_t *anagram) {
size_t i;
    fprintf(stdout, "Size %u\n", anagram->szkey);
    fprintf(stdout, "Key %s\n", anagram->key);
    fprintf(stdout, "Words (%u)", anagram->list.nwords);
    for (i = 0; i < anagram->list.nwords; i++) fprintf(stdout, " %s", anagram->list.words[i]);
    fprintf(stdout, "\n");
    fprintf(stdout, "Links (%u)", anagram->nlinks);
    for (i = 0; i < anagram->nlinks; i++) fprintf(stdout, " %s", anagram->links[i]->key);
    fprintf(stdout, "\n");
    fflush(stdout);
}

int process_requests(const hanagrams_t *hanagrams) {
char *line = NULL, *tmpline = NULL, *word1 = NULL, *word2 = NULL;
int r;
size_t maxszline, szline, indword11, indword12, indword21, indword22;
anagram_t *anagram1 = NULL, *anagram2 = NULL;
    maxszline = CHUNK_SIZE;
    if (!(line = malloc(sizeof(char)*(maxszline+1)))) {
        log_error("process_requests: malloc error (line)\n");
        return 0;
    }
    do {
        fprintf(stdout, "? ");
        fflush(stdout);
        if (fgets(line, (int)maxszline+1, stdin)) {
            while ((szline = line_size(line)) == maxszline) {
                maxszline += CHUNK_SIZE;
                if (!(tmpline = realloc(line, sizeof(char)*(maxszline+1)))) {
                    log_error("process_requests: realloc error (line)\n");
                    FREE(line);
                    return 0;
                }
                line = tmpline;
                fgets(&line[maxszline-CHUNK_SIZE], CHUNK_SIZE+1, stdin);
            }
            if (!strncmp(line, REQ_PATH, strlen(REQ_PATH))) {
                indword11 = read_separators(szline, line, 1);
                indword12 = read_letters(szline, line, indword11);
                indword21 = read_separators(szline, line, indword12);
                indword22 = read_letters(szline, line, indword21);
                if (1 < indword11 && indword11 < indword12 && indword12 < indword21 && indword21 < indword22 && indword22 == szline) {
                    word1 = &line[indword11];
                    line[indword12] = 0;
                    word2 = &line[indword21];
                    if ((anagram1 = get_anagram_from_word(indword12-indword11, word1, hanagrams)) && (anagram2 = get_anagram_from_word(indword22-indword21, word2, hanagrams))) search_path(word1, anagram1, word2, anagram2);
                }
                else log_error("process_requests: syntax error in path request\n");
                r = 1;
            }
            else if (!strncmp(line, REQ_VIEW, strlen(REQ_VIEW))) {
                indword11 = read_separators(szline, line, 1);
                indword12 = read_letters(szline, line, indword11);
                if (1 < indword11 && indword11 < indword12 && indword12 == szline) {
                    if ((anagram1 = get_anagram_from_word(indword12-indword11, &line[indword11], hanagrams))) view_anagram(anagram1);
                }
                else log_error("process_requests: syntax error in view request\n");
                r = 1;
            }
            else if (!strcmp(line, REQ_QUIT)) r = 2;
            else {
                log_error("process_requests: unknown request\n");
                r = 1;
            }
        }
        else {
            log_error("process_requests: fgets error\n");
            FREE(line);
            return 0;
        }
    }
    while (r == 1);
    FREE(line);
    return r;
}

int main(int argc, char **argv) {
int r;
dictionary_t *dictionary = NULL;
hanagrams_t *hanagrams = NULL;
    if (argc != 2) {
        log_error("Usage: %s file\n", argv[0]);
        return EXIT_FAILURE;
    }
    if (!(dictionary = read_dictionary(argv[1]))) return EXIT_FAILURE;
    if (!(hanagrams = create_hanagrams(dictionary))) {
        dictionary_cleanup(dictionary);
        return EXIT_FAILURE;
    }
    r = process_requests(hanagrams);
    hanagrams_cleanup(hanagrams);
    dictionary_cleanup(dictionary);
    return r ? EXIT_SUCCESS:EXIT_FAILURE;
}