diff options
Diffstat (limited to 'src/trie.inc.h')
| -rw-r--r-- | src/trie.inc.h | 228 |
1 files changed, 228 insertions, 0 deletions
diff --git a/src/trie.inc.h b/src/trie.inc.h new file mode 100644 index 00000000..ffc8ac8e --- /dev/null +++ b/src/trie.inc.h @@ -0,0 +1,228 @@ +#ifndef TYPE +#error "Set TYPE before including self file" +#else + +#include <stdarg.h> + +#include "err.h" +#include "macro.h" +#include "linked_list.inc.h" +#include "strbuf.h" + +INIT_F ( TRIE(TYPE) ) { + NEW(TRIE_NODE(TYPE), t, '\0'); + self->root = t; + return 0; +} + +INIT_F (TRIE_NODE(TYPE), char c) { + self->c = c; + self->value = NULL; + self->next = NULL; + self->child = NULL; + return 0; +} + +INIT_F (TRIE_NODE(TYPE), + char c, + TRIE_NODE(TYPE)* next, + TRIE_NODE(TYPE)* child ) +{ + self->c = c; + self->next = next; + self->child = child; + return 0; +} + +int PUSH(TRIE(TYPE)) ( TRIE(TYPE)* trie, char* key, TYPE* val ) { + TRIE_NODE(TYPE) *cur, *last; + + last = trie->root; + cur = last->child; + + char* subkey = key; + + while (1) { + if (cur == NULL) { + /* Build direct LL for remaining subkey */ + for (char* c = subkey; c[0] != '\0'; c++) { + NEW(TRIE_NODE(TYPE), t, *c); + last->child = t; + last = t; + } + last->value = RESOLVE(TYPE)(last->value, val); + return 0; + } else if (cur->c == subkey[0]) { + /* This node belongs to the key, + * Decend further */ + last = cur; + cur = cur->child; + subkey++; + } else if (subkey[0] == '\0') { + /* Key finished */ + last->value = RESOLVE(TYPE)(last->value, val); + return 0; + } else if (cur->next != NULL) { + /* This node was not part of the set, but it's sibling might */ + cur = cur->next; + /* `last` not set since we aren't moving down */ + } else { + /* No node on self level was part of the set, create a new__ + * sibling and follow down that parse */ + NEW(TRIE_NODE(TYPE), t, *subkey); + cur->next = t; + last = cur; + cur = t; + } + } + + return 0; +} + +/* + * TODO what happens when I give an invalid key? + */ +TYPE* GET(TRIE(TYPE)) ( TRIE(TYPE)* trie, char* key ) { + TRIE_NODE(TYPE)* n = trie->root->child; + char* subkey = key; + + while (n != NULL) { + if (subkey[1] == '\0') { + /* Wanted node found, + * value can however be NULL */ + return n->value; + } else if (subkey[0] == n->c) { + n = n->child; + subkey++; + } else { + n = n->next; + } + } + + /* Position not found */ + return 0; +} + +FREE_F(TRIE_NODE(TYPE)) { + if (self == NULL) return 0; + if (self->value != NULL) FFREE(TYPE, self->value); + if (self->next != NULL) FREE(TRIE_NODE(TYPE))(self->next); + if (self->child != NULL) FREE(TRIE_NODE(TYPE))(self->child); + free (self); + return 0; +} + +FREE_F(TRIE(TYPE)) { + if (self->root->c != '\0') { + // ERR("Invalid trie"); + return 1; + } + return FREE(TRIE_NODE(TYPE))(self->root); +} + +int EMPTY(TRIE(TYPE))(TRIE(TYPE)* self) { + return self->root->child == NULL; +} + +FMT_F(TRIE_NODE(TYPE)) { + + va_list ap; + va_start(ap, buf); + int argc = va_arg(ap, int); + int depth = argc >= 1 + ? va_arg(ap, int) + : 0; + va_end(ap); + + int seek = 0; + + TRIE_NODE(TYPE)* n = self; + + if (n == NULL) { fmtf("\n"); } + while (n != NULL) { + fmtf("|"); + // FOR(int, i, depth) fmtf(" "); + for (int i = 0; i < depth; i++) fmtf(" "); + fmtf("%c ", n->c == '\0' ? '0' : n->c); + if (n->value != NULL) { + seek += FMT(TYPE)(n->value, buf + seek); + fmtf("\n"); + } + + if (n->child != NULL) { + fmtf("\n"); + seek += FMT(TRIE_NODE(TYPE))(n->child, buf + seek, depth + 1); + } + n = n->next; + } + return seek; + +} + +FMT_F(TRIE(TYPE)) { + int seek = 0; + fmtf("Trie: %p: {", self); + if (EMPTY(TRIE(TYPE))(self)) { + fmtf(" [EMPTY] "); + } else { + fmtf("\n"); + seek += FMT(TRIE_NODE(TYPE))(self->root->child, buf + seek); + } + fmtf("}"); + return seek; +} + +int DEEP_COPY(TRIE_NODE(TYPE)) (TRIE_NODE(TYPE)* dest, TRIE_NODE(TYPE)* src) { + dest->c = src->c; + + if (src->value != NULL) { + RENEW(TYPE, dest->value); + DEEP_COPY(TYPE)(dest->value, src->value); + } + + if (src->next != NULL) { + RENEW(TRIE_NODE(TYPE), dest->next, '\0'); + DEEP_COPY(TRIE_NODE(TYPE))(dest->next, src->next); + } + + if (src->child != NULL) { + RENEW(TRIE_NODE(TYPE), dest->child, '\0'); + DEEP_COPY(TRIE_NODE(TYPE))(dest->child, src->child); + } + + return 0; +} + +int DEEP_COPY(TRIE(TYPE)) (TRIE(TYPE)* dest, TRIE(TYPE)* src) { + return DEEP_COPY(TRIE_NODE(TYPE))(dest->root, src->root); +} + +void KEYS(TRIE_NODE(TYPE)) (TRIE_NODE(TYPE)* node, LLIST(strbuf)* list, strbuf* path) { + if (node == NULL) return; + + + if (node->value != NULL) { + strbuf_append(path, node->c); + NEW(strbuf, c); + DEEP_COPY(strbuf)(c, path); + PUSH(LLIST(strbuf))(list, c); + strbuf_pop(path); + } + if (node->next != NULL) { + KEYS(TRIE_NODE(TYPE)) (node->next, list, path); + } + if (node->child != NULL) { + if (node->c != '\0') strbuf_append(path, node->c); + KEYS(TRIE_NODE(TYPE)) (node->child, list, path); + if (node->c != '\0') strbuf_pop(path); + } +} + +LLIST(strbuf)* KEYS(TRIE(TYPE)) (TRIE(TYPE)* trie) { + NEW(LLIST(strbuf), retlist); + SNEW(strbuf, key); + KEYS(TRIE_NODE(TYPE)) (trie->root, retlist, &key); + return retlist; +} + +#endif /* TYPE */ |