123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310 |
- /*!
- Temelia - Trie tree implementation source file.
- Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).
- @author Dascalu Laurentiu
- This program is free software; you can redistribute it and
- modify it under the terms of the GNU General Public License
- as published by the Free Software Foundation; either version 3
- of the License, or (at your option) any later version.
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- */
- #include <string.h>
- #include "include/trie_tree.h"
- #include "include/queue.h"
- #define SYMBOLS_NUMBER ('z' - 'a' + 1)
- static trie_tree_t _trie_search(trie_tree_t trie, char *suffix);
- static void _trie_delete_node(trie_tree_t trie);
- struct _trie_tree_t
- {
- /*! user's key stored in current node */
- void *key;
- /*! reference to parent */
- struct _trie_tree_t *parent;
- /*! references to children */
- vector_t children;
- };
- trie_tree_t trie_new(void *key)
- {
- int i;
- trie_tree_t trie;
- trie = (struct _trie_tree_t *) _new(sizeof(struct _trie_tree_t));
- trie->key = key;
- trie->parent = NULL;
- trie->children = vector_new(SYMBOLS_NUMBER);
- for (i = 0; i < SYMBOLS_NUMBER; i++)
- vector_push_back(trie->children, NULL);
- return trie;
- }
- void trie_delete(trie_tree_t trie)
- {
- int i, n;
- _ASSERT(trie, ==, NULL, INVALID_INPUT,);
- n = vector_get_size(trie->children);
- if (n == 0)
- {
- _trie_delete_node(trie);
- return;
- }
- for (i = 0; i < n; i++)
- trie_delete(vector_get_key_at(trie->children, i));
- vector_delete(trie->children);
- _delete(trie);
- }
- void *trie_get_key(trie_tree_t trie)
- {
- _ASSERT(trie, ==, NULL, NULL_POINTER, NULL);
- return trie->key;
- }
- trie_tree_t trie_get_parent(trie_tree_t trie)
- {
- _ASSERT(trie, ==, NULL, NULL_POINTER, NULL);
- return trie->parent;
- }
- void *trie_get_children(trie_tree_t trie)
- {
- _ASSERT(trie, ==, NULL, INVALID_INPUT, NULL);
- return trie->children;
- }
- int trie_get_children_number(trie_tree_t trie)
- {
- _ASSERT(trie, ==, NULL, INVALID_INPUT, -1);
- return vector_get_size(trie->children) % 256;
- }
- trie_tree_t trie_get_child(trie_tree_t trie, int index)
- {
- _ASSERT(trie, ==, NULL, INVALID_INPUT, NULL);
- _ASSERT(index, <, 0, INVALID_INPUT, NULL);
- _ASSERT(index, >=, SYMBOLS_NUMBER, INVALID_INPUT, NULL);
- return vector_get_key_at(trie->children, index);
- }
- trie_tree_t trie_insert(trie_tree_t _trie, char *suffix, void *key)
- {
- trie_tree_t add = NULL, next_trie;
- int nints, index;
- _ASSERT(suffix, ==, NULL, NULL_POINTER, NULL);
- nints = strlen(suffix);
- _ASSERT(nints, <, 1, INVALID_INPUT, NULL);
- // Input should be formed from intacters 'a'-'z'.
- _ASSERT(suffix[0], <, 'a', INVALID_INPUT, NULL);
- _ASSERT(suffix[0], >, 'z', INVALID_INPUT, NULL);
- index = suffix[0] - 'a';
- next_trie = vector_get_key_at(_trie->children, index);
- if (nints == 1)
- {
- if (next_trie != NULL)
- {
- next_trie->key = key;
- return next_trie;
- }
- else
- {
- add = trie_new(NULL);
- add->parent = _trie;
- vector_set_key_at(_trie->children, index, add);
- add->key = key;
- return add;
- }
- }
- else
- {
- if (next_trie != NULL)
- return trie_insert(next_trie, suffix + 1, key);
- else
- {
- add = trie_new(NULL);
- add->parent = _trie;
- vector_set_key_at(_trie->children, index, add);
- return trie_insert(add, suffix + 1, key);
- }
- }
- }
- void *trie_search(trie_tree_t trie, char *suffix)
- {
- return trie_get_key(_trie_search(trie, suffix));
- }
- void trie_remove(trie_tree_t _trie, char *suffix)
- {
- int i;
- trie_tree_t trie_removed = _trie_search(_trie, suffix), aux;
- _ASSERT(trie_removed, ==, NULL, NULL_POINTER,);
- /*
- * Remove a node only if it's parent isn't NULL, it's parent holds a NULL key
- * and it has no children.
- */
- while (1)
- {
- aux = trie_removed;
- trie_removed = trie_removed->parent;
- if (trie_get_children_number(aux) > 0)
- {
- aux->key = NULL;
- break;
- }
- if (trie_removed)
- {
- for (i = 0; i < SYMBOLS_NUMBER; i++)
- if (vector_get_key_at(trie_removed->children, i) == aux)
- {
- vector_set_key_at(trie_removed->children, i, NULL);
- break;
- }
- }
- _trie_delete_node(aux);
- if (!trie_removed || trie_removed->key)
- break;
- }
- }
- int trie_children_number(trie_tree_t trie)
- {
- int i = 0, children = 0;
- _ASSERT(trie, ==, NULL, NULL_POINTER, -1);
- for (; i < SYMBOLS_NUMBER; i++)
- if (vector_get_key_at(trie->children, i))
- ++children;
- return children;
- }
- int trie_is_leaf(trie_tree_t trie)
- {
- _ASSERT(trie, ==, NULL, NULL_POINTER, -1);
- return trie_children_number(trie) == 0;
- }
- int trie_is_empty(trie_tree_t trie)
- {
- _ASSERT(trie, ==, NULL, INVALID_INPUT, -1);
- return trie->parent == NULL && trie_is_leaf(trie);
- }
- void trie_preorder(trie_tree_t trie, void key_handler(void *key, void *context), void *context)
- {
- int i;
- _ASSERT(trie, ==, NULL, NULL_POINTER,);
- _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
- if (trie->key)
- key_handler(trie->key, context);
- for (i = 0; i < SYMBOLS_NUMBER; i++)
- trie_preorder(vector_get_key_at(trie->children, i), key_handler,
- context);
- }
- void trie_postorder(trie_tree_t trie, void key_handler(void *key, void *context), void *context)
- {
- int i;
- _ASSERT(trie, ==, NULL, NULL_POINTER,);
- _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
- for (i = SYMBOLS_NUMBER - 1; i >= 0; i--)
- trie_postorder(vector_get_key_at(trie->children, i), key_handler,
- context);
- if (trie->key)
- key_handler(trie->key, context);
- }
- void trie_level_order(trie_tree_t trie, void key_handler(void *key, void *context),
- void *context)
- {
- int i;
- queue_t queue;
- queue = queue_new(DEFAULT_SIZE);
- queue_push_back(queue, trie);
- while (!queue_is_empty(queue))
- {
- trie = queue_get_front(queue);
- queue_pop_front(queue);
- if (trie->key)
- key_handler(trie->key, context);
- for (i = 0; i < SYMBOLS_NUMBER; i++)
- if (vector_get_key_at(trie->children, i))
- queue_push_back(queue, vector_get_key_at(trie->children, i));
- }
- queue_delete(queue);
- }
- static trie_tree_t _trie_search(trie_tree_t trie, char *suffix)
- {
- int index;
- _ASSERT(trie, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(suffix, ==, NULL, NULL_POINTER, NULL);
- if (suffix[0] == '\0')
- return trie;
- index = suffix[0] - 'a';
- return _trie_search(vector_get_key_at(trie->children, index), suffix + 1);
- }
- static void _trie_delete_node(trie_tree_t trie)
- {
- _ASSERT(trie, ==, NULL, NULL_POINTER,);
- vector_delete(trie->children);
- _delete(trie);
- }
|