Teacup rim text: Difference between revisions

Content added Content deleted
(C - use GLib)
Line 73: Line 73:


=={{header|C}}==
=={{header|C}}==
{{libheader|GLib}}
<lang c>#include <stdbool.h>
<lang c>#include <stdbool.h>
#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdlib.h>
#include <string.h>
#include <glib.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;
int c, count = 0;
string_buffer_clear(buffer);
g_string_set_size(line, 0);
while ((c = getc(in)) != EOF) {
while ((c = getc(in)) != EOF) {
++count;
++count;
if (c == '\n')
if (c == '\n')
break;
break;
string_buffer_append(buffer, c);
g_string_append_c(line, c);
}
}
return count > 0;
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");
FILE* in = fopen(file, "r");
if (in == 0) {
if (in == 0) {
perror(file);
perror(file);
return false;
return NULL;
}
}
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_sort(words);
fclose(in);
return true;
return dict;
}
}


Line 238: Line 123:
}
}


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;
continue;
word_list_clear(&teacup_words);
g_ptr_array_set_size(teacup_words, 0);
char* copy = xstrdup(word);
GString* temp = g_string_new(word->str);
for (size_t i = 0; i < len - 1; ++i) {
for (size_t i = 0; i < len - 1; ++i) {
rotate(copy, len);
rotate(temp->str, len);
if (strcmp(word, copy) == 0 || !word_list_bsearch(words, copy))
if (g_string_equal(word, temp)
|| !dictionary_search(dictionary, temp))
break;
break;
word_list_append(&teacup_words, copy);
g_ptr_array_add(teacup_words, g_string_new(temp->str));
}
}
free(copy);
g_string_free(temp, TRUE);
if (teacup_words.size == len - 1) {
if (teacup_words->len == len - 1) {
printf("%s", word);
printf("%s", word->str);
word_list_append(&found, word);
g_hash_table_insert(found, g_string_new(word->str), NULL);
for (size_t i = 0; i < len - 1; ++i) {
for (size_t i = 0; i < len - 1; ++i) {
printf(" %s", teacup_words.words[i]);
GString* teacup_word = g_ptr_array_index(teacup_words, i);
word_list_append(&found, teacup_words.words[i]);
printf(" %s", teacup_word->str);
g_hash_table_insert(found, g_string_new(teacup_word->str), NULL);
}
}
printf("\n");
printf("\n");
}
}
}
}
word_list_destroy(&teacup_words);
g_ptr_array_free(teacup_words, TRUE);
word_list_destroy(&found);
g_hash_table_destroy(found);
}
}


Line 275: Line 168:
return EXIT_FAILURE;
return EXIT_FAILURE;
}
}
GPtrArray* dictionary = load_dictionary(argv[1]);
word_list words;
if (!load_dictionary(argv[1], &words))
if (dictionary == NULL)
return EXIT_FAILURE;
return EXIT_FAILURE;
find_teacup_words(&words);
find_teacup_words(dictionary);
g_ptr_array_free(dictionary, TRUE);
word_list_destroy(&words);
return EXIT_SUCCESS;
return EXIT_SUCCESS;
}</lang>
}</lang>
Retrieved from "https://rosettacode.org/wiki/Teacup_rim_text"