|
=={{header|C}}==
{{libheader|GLib}}
<lang c>#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <stringglib.h>
bool get_line(FILE* in, GString* line) {
void fatal(const char* message) {
fprintf(stderr, "%s\n", message);
exit(1);
}
void* xmalloc(size_t n) {
void* ptr = malloc(n);
if (ptr == NULL)
fatal("Out of memory");
return ptr;
}
void* xrealloc(void* p, size_t n) {
void* ptr = realloc(p, n);
if (ptr == NULL)
fatal("Out of memory");
return ptr;
}
char* xstrdup(const char* str) {
char* s = strdup(str);
if (s == NULL)
fatal("Out of memory");
return s;
}
typedef struct word_list_tag {
size_t size;
size_t capacity;
char** words;
} word_list;
void word_list_create(word_list* words, size_t capacity) {
words->size = 0;
words->capacity = capacity;
words->words = xmalloc(capacity * sizeof(char*));
}
void word_list_destroy(word_list* words) {
for (size_t i = 0; i < words->size; ++i)
free(words->words[i]);
free(words->words);
words->words = NULL;
words->size = 0;
words->capacity = 0;
}
void word_list_clear(word_list* words) {
for (size_t i = 0; i < words->size; ++i)
free(words->words[i]);
words->size = 0;
}
void word_list_append(word_list* words, const char* str) {
size_t min_capacity = words->size + 1;
if (words->capacity < min_capacity) {
size_t new_capacity = (words->capacity * 3)/2;
if (new_capacity < min_capacity)
new_capacity = min_capacity;
words->words = xrealloc(words->words, new_capacity * sizeof(char*));
words->capacity = new_capacity;
}
words->words[words->size++] = xstrdup(str);
}
int word_compare(const void* p1, const void* p2) {
const char* w1 = *(const char**)p1;
const char* w2 = *(const char**)p2;
return strcmp(w1, w2);
}
void word_list_sort(word_list* words) {
qsort(words->words, words->size, sizeof(char*), word_compare);
}
// Binary seach. Assumes word list has been sorted.
bool word_list_bsearch(const word_list* words, const char* word) {
return bsearch(&word, words->words, words->size, sizeof(char*), word_compare) != NULL;
}
// Linear search - OK if list is short.
bool word_list_contains(const word_list* words, const char* word) {
for (size_t i = 0; i < words->size; ++i) {
if (strcmp(word, words->words[i]) == 0)
return true;
}
return false;
}
typedef struct string_buffer_tag {
size_t size;
size_t capacity;
char* string;
} string_buffer;
void string_buffer_create(string_buffer* buffer, size_t capacity) {
buffer->size = 0;
buffer->capacity = capacity;
buffer->string = xmalloc(capacity);
}
void string_buffer_destroy(string_buffer* buffer) {
free(buffer->string);
buffer->string = NULL;
buffer->size = 0;
buffer->capacity = 0;
}
void string_buffer_clear(string_buffer* buffer) {
buffer->size = 0;
buffer->string[0] = 0;
}
void string_buffer_append(string_buffer* buffer, char ch) {
size_t min_capacity = buffer->size + 2;
if (buffer->capacity < min_capacity) {
size_t new_capacity = buffer->capacity * 2;
if (new_capacity < min_capacity)
new_capacity = min_capacity;
buffer->string = xrealloc(buffer->string, new_capacity);
buffer->capacity = new_capacity;
}
buffer->string[buffer->size++] = ch;
buffer->string[buffer->size] = 0;
}
bool get_line(FILE* in, string_buffer* buffer) {
int c, count = 0;
string_buffer_clearg_string_set_size(bufferline, 0);
while ((c = getc(in)) != EOF) {
++count;
if (c == '\n')
break;
string_buffer_appendg_string_append_c(bufferline, c);
}
return count > 0;
}
void destroy_string(gpointer key) {
bool load_dictionary(const char* file, word_list* words) {
g_string_free((GString*)key, TRUE);
}
int string_compare(gconstpointer p1, gconstpointer p2) {
GString** s1 = (GString**)p1;
GString** s2 = (GString**)p2;
return strcmp((*s1)->str, (*s2)->str);
}
GPtrArray* load_dictionary(const char* file) {
FILE* in = fopen(file, "r");
if (in == 0) {
perror(file);
return falseNULL;
}
GPtrArray* dict = g_ptr_array_new_full(1024, destroy_string);
word_list_create(words, 1024);
GString* line = g_string_sized_new(64);
string_buffer buffer;
while (get_line(in, line))
string_buffer_create(&buffer, 64);
g_ptr_array_add(dict, g_string_new(line->str));
while (get_line(in, &buffer))
g_ptr_array_sort(dict, string_compare);
word_list_append(words, buffer.string);
g_string_free(line, TRUE);
string_buffer_destroy(&buffer);
word_list_sortfclose(wordsin);
return truedict;
}
}
bool dictionary_search(const GPtrArray* dictionary, const GString* word) {
void find_teacup_words(const word_list* words) {
return bsearch(&word, dictionary->pdata, dictionary->len, sizeof(GString*),
word_list teacup_words, found;
string_compare) != NULL;
word_list_create(&teacup_words, 8);
}
word_list_create(&found, 8);
for (size_t i = 0; i < words->size; ++i) {
void find_teacup_words(GPtrArray* dictionary) {
const char* word = words->words[i];
GHashTable* found = g_hash_table_new_full((GHashFunc)g_string_hash,
size_t len = strlen(word);
(GEqualFunc)g_string_equal,
if (len < 3 || word_list_contains(&found, word))
destroy_string, NULL);
GPtrArray* teacup_words = g_ptr_array_new_full(8, destroy_string);
for (size_t i = 0, n = dictionary->len; i < n; ++i) {
GString* word = g_ptr_array_index(dictionary, i);
size_t len = word->len;
if (len < 3 || g_hash_table_contains(found, word))
continue;
word_list_clearg_ptr_array_set_size(&teacup_words, 0);
charGString* copytemp = xstrdupg_string_new(word->str);
for (size_t i = 0; i < len - 1; ++i) {
rotate(copytemp->str, len);
if (strcmpg_string_equal(word, copy) == 0 || !word_list_bsearch(words, copy)temp)
|| !dictionary_search(dictionary, temp))
break;
word_list_appendg_ptr_array_add(&teacup_words, copyg_string_new(temp->str));
}
freeg_string_free(copytemp, TRUE);
if (teacup_words.size->len == len - 1) {
printf("%s", word->str);
word_list_appendg_hash_table_insert(&found, g_string_new(word->str), NULL);
for (size_t i = 0; i < len - 1; ++i) {
printf("GString* %s",teacup_word = g_ptr_array_index(teacup_words.words[, i]);
word_list_appendprintf(&found" %s", teacup_words.words[i]teacup_word->str);
g_hash_table_insert(found, g_string_new(teacup_word->str), NULL);
}
printf("\n");
}
}
word_list_destroyg_ptr_array_free(&teacup_words, TRUE);
word_list_destroyg_hash_table_destroy(&found);
}
return EXIT_FAILURE;
}
GPtrArray* dictionary = load_dictionary(argv[1]);
word_list words;
if (!load_dictionary(argv[1],dictionary &words)== NULL)
return EXIT_FAILURE;
find_teacup_words(&wordsdictionary);
g_ptr_array_free(dictionary, TRUE);
word_list_destroy(&words);
return EXIT_SUCCESS;
}</lang>
| 