diff options
author | Hugo Hörnquist <hugo@lysator.liu.se> | 2019-02-19 22:27:43 +0100 |
---|---|---|
committer | Hugo Hörnquist <hugo@lysator.liu.se> | 2019-02-19 22:27:43 +0100 |
commit | 6d320b0386aa4d7c6bfe2d6fce3d68e227752bed (patch) | |
tree | 920b323f7e84bd9c5b6454f44d6f29918fcf9c7d /trie.h | |
parent | Further changes. (diff) | |
download | calp-6d320b0386aa4d7c6bfe2d6fce3d68e227752bed.tar.gz calp-6d320b0386aa4d7c6bfe2d6fce3d68e227752bed.tar.xz |
Further C++ improvements, maybe doesn't segfault now.
Diffstat (limited to '')
-rw-r--r-- | trie.h | 135 |
1 files changed, 133 insertions, 2 deletions
@@ -3,6 +3,9 @@ #include <iostream> +#include <cstring> +#include <cstdlib> + template <class T> struct trie_node { char c; @@ -23,9 +26,9 @@ struct trie { trie () : root (new trie_node<T> ('\0')) { } - int push_back (const char* key, const T&); + int push (const char* key, T* item); - T& operator[] ( const char* key ); + T* operator[] ( const char* key ); bool empty () { return this->root->child == NULL; } }; @@ -33,4 +36,132 @@ struct trie { template <class T> std::ostream& operator<<(std::ostream&, trie<T>* trie); +template <class T> +trie_node<T>::trie_node (char c, trie_node<T>* next, trie_node<T>* child) { + this->c = c; + this->next = next; + this->child = child; +} + +template <class T> +int trie<T>::push (const char* key, T* item) { + trie_node<T> *cur, *last; + + last = this->root; + cur = last->child; + + // TODO subkey is never collected + char* subkey = static_cast<char*>(malloc(strlen(key))); + strcpy (subkey, key); + + while (true) { + if (cur == NULL) { + /* Build direct LL for remaining subkey */ + for (char* c = subkey; c[0] != '\0'; c++) { + // NEW(TRIE_NODE(TYPE), t, *c); + auto t = new trie_node<T>(*c); + last->child = t; + last = t; + } + // TODO fix resolve + // last->value = RESOLVE(TYPE)(last->value, val); + last->value = item; + 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 */ + // TODO fix resolve + // last->value = RESOLVE(TYPE)(last->value, val); + last->value = item; + 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); + auto t = new trie_node<T>(*subkey); + cur->next = t; + last = cur; + cur = t; + } + } +} + +template <class T> +T* trie<T>::operator[] (const char* key) { + trie_node<T>* n = this->root->child; + + // TODO subkey is never collected + char* subkey = static_cast<char*>(malloc(strlen(key))); + strcpy (subkey, key); + + while (n != NULL) { + if (subkey[1] == '\0') { + return n->value; + } else if (subkey[0] == n->c) { + n = n->child; + subkey++; + } else { + n = n->next; + } + } + + // ERR("Position not found"); + // return 0; + return nullptr; +} + +template <class T> +std::ostream& operator<<(std::ostream& o, trie_node<T>* node) { +#if 0 + 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; +#endif + // TODO figure out depth + int depth = 1; + + trie_node<T>* n = node; + + + if (n == NULL) { o << std::endl; } + while (n != NULL) { + o << '|'; + for (int i = 0; i < depth; i++) o << ' '; + o << (n->c == '\0' ? '0' : n->c); + if (n->value != NULL) { + o << n->value << std::endl; + } + + if (n->child != NULL) { + o << std::endl; + o << n->child; // depth + 1 + } + n = n->next; + } + return o; +} + +template <class T> +std::ostream& operator<<(std::ostream& o, trie<T>* trie) { + o << "Trie: " << trie << " {\n"; + o << trie->root->child; + o << "}"; + return o; +} + #endif /* TRIE_H */ |