Words from neighbour ones: Difference between revisions

Content added Content deleted
(C++ code efficiency improvement)
(C - revert to previous version)
Line 76: Line 76:
</pre>
</pre>
=={{header|C}}==
=={{header|C}}==
<lang c>#include <stdbool.h>
<lang c>#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdlib.h>
#include <string.h>
#include <string.h>
Line 84: Line 83:
#define MIN_LENGTH 9
#define MIN_LENGTH 9
#define WORD_SIZE (MIN_LENGTH + 1)
#define WORD_SIZE (MIN_LENGTH + 1)
#define BUFFER_SIZE (MIN_LENGTH + 1)


int word_compare(const char* w1, const char* w2) {
void fatal(const char* message) {
return memcmp(w1, w2, WORD_SIZE);
fprintf(stderr, "%s\n", message);
exit(1);
}
}


void* xmalloc(size_t n) {
struct word_buffer {
size_t start;
void* ptr = malloc(n);
size_t end;
if (ptr == NULL)
fatal("Out of memory");
⚫
char words[BUFFER_SIZE][WORD_SIZE];
⚫
return ptr;
};

void word_buffer_init(struct word_buffer* buffer) {
⚫
buffer->start = 0;
buffer->end = 0;
}
}


void* xrealloc(void* p, size_t n) {
void word_buffer_append(struct word_buffer* buffer, const char* word) {
void* ptr = realloc(p, n);
⚫
memcpy(buffer->words[buffer->end], word, WORD_SIZE);
if (ptr == NULL)
buffer->end = (buffer->end + 1) % BUFFER_SIZE;
fatal("Out of memory");
if (buffer->start == buffer->end)
⚫
return ptr;
buffer->start = (buffer->start + 1) % BUFFER_SIZE;
}
}


size_t word_buffer_size(const struct word_buffer* buffer) {
int word_compare(const void* p1, const void* p2) {
return (BUFFER_SIZE + buffer->end - buffer->start) % BUFFER_SIZE;
return memcmp(p1, p2, WORD_SIZE);
}
}


const char* word_buffer_get(const struct word_buffer* buffer, size_t index) {
return buffer->words[(index + buffer->start) % BUFFER_SIZE];
}

bool word_buffer_contains(const struct word_buffer* buffer, const char* word) {
const size_t n = word_buffer_size(buffer);
⚫
for (size_t i = 0; i < n; ++i)
if (word_compare(word, word_buffer_get(buffer, i)) == 0)
⚫
return true;
⚫
return false;
}

// The input file must consist of one word per line in alphabetical order.
int main(int argc, char** argv) {
int main(int argc, char** argv) {
const char* filename = argc < 2 ? "unixdict.txt" : argv[1];
const char* filename = argc < 2 ? "unixdict.txt" : argv[1];
Line 133: Line 115:
}
}
char line[MAX_WORD_SIZE];
char line[MAX_WORD_SIZE];
size_t size = 0, capacity = 1024;
struct word_buffer words;
⚫
char* words = xmalloc(WORD_SIZE * capacity);
word_buffer_init(&words);
⚫
char prev_word[WORD_SIZE] = { 0 };
int count = 0;
while (fgets(line, sizeof(line), in)) {
while (fgets(line, sizeof(line), in)) {
size_t len = strlen(line) - 1; // last character is newline
size_t len = strlen(line) - 1; // last character is newline
Line 142: Line 122:
continue;
continue;
line[len] = '\0';
line[len] = '\0';
word_buffer_append(&words, line);
if (size == capacity) {
if (word_buffer_size(&words) < MIN_LENGTH)
capacity *= 2;
continue;
words = xrealloc(words, WORD_SIZE * capacity);
}
⚫
memcpy(&words[size * WORD_SIZE], line, WORD_SIZE);
++size;
}
fclose(in);
qsort(words, size, WORD_SIZE, word_compare);
⚫
int count = 0;
⚫
char prev_word[WORD_SIZE] = { 0 };
⚫
for (size_t i = 0; i + MIN_LENGTH <= size; ++i) {
char word[WORD_SIZE] = { 0 };
char word[WORD_SIZE] = { 0 };
for (size_t i = 0; i < MIN_LENGTH; ++i)
for (size_t j = 0; j < MIN_LENGTH; ++j)
word[i] = word_buffer_get(&words, i)[i];
word[j] = words[(i + j) * WORD_SIZE + j];
if (word_compare(word, prev_word) == 0)
if (word_compare(word, prev_word) == 0)
continue;
continue;
if (word_buffer_contains(&words, word))
if (bsearch(word, words, size, WORD_SIZE, word_compare))
printf("%2d. %s\n", ++count, word);
printf("%2d. %s\n", ++count, word);
memcpy(prev_word, word, WORD_SIZE);
memcpy(prev_word, word, WORD_SIZE);
}
}
fclose(in);
free(words);
return EXIT_SUCCESS;
return EXIT_SUCCESS;
}</lang>
}</lang>
Retrieved from "https://rosettacode.org/wiki/Words_from_neighbour_ones"