trie_tree.c 6.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310
  1. /*!
  2. Temelia - Trie tree implementation source file.
  3. Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).
  4. @author Dascalu Laurentiu
  5. This program is free software; you can redistribute it and
  6. modify it under the terms of the GNU General Public License
  7. as published by the Free Software Foundation; either version 3
  8. of the License, or (at your option) any later version.
  9. This program is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. GNU General Public License for more details.
  13. You should have received a copy of the GNU General Public License
  14. along with this program; if not, write to the Free Software
  15. Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  16. */
  17. #include <string.h>
  18. #include "include/trie_tree.h"
  19. #include "include/queue.h"
  20. #define SYMBOLS_NUMBER ('z' - 'a' + 1)
  21. static trie_tree_t _trie_search(trie_tree_t trie, char *suffix);
  22. static void _trie_delete_node(trie_tree_t trie);
  23. struct _trie_tree_t
  24. {
  25. /*! user's key stored in current node */
  26. void *key;
  27. /*! reference to parent */
  28. struct _trie_tree_t *parent;
  29. /*! references to children */
  30. vector_t children;
  31. };
  32. trie_tree_t trie_new(void *key)
  33. {
  34. int i;
  35. trie_tree_t trie;
  36. trie = (struct _trie_tree_t *) _new(sizeof(struct _trie_tree_t));
  37. trie->key = key;
  38. trie->parent = NULL;
  39. trie->children = vector_new(SYMBOLS_NUMBER);
  40. for (i = 0; i < SYMBOLS_NUMBER; i++)
  41. vector_push_back(trie->children, NULL);
  42. return trie;
  43. }
  44. void trie_delete(trie_tree_t trie)
  45. {
  46. int i, n;
  47. _ASSERT(trie, ==, NULL, INVALID_INPUT,);
  48. n = vector_get_size(trie->children);
  49. if (n == 0)
  50. {
  51. _trie_delete_node(trie);
  52. return;
  53. }
  54. for (i = 0; i < n; i++)
  55. trie_delete(vector_get_key_at(trie->children, i));
  56. vector_delete(trie->children);
  57. _delete(trie);
  58. }
  59. void *trie_get_key(trie_tree_t trie)
  60. {
  61. _ASSERT(trie, ==, NULL, NULL_POINTER, NULL);
  62. return trie->key;
  63. }
  64. trie_tree_t trie_get_parent(trie_tree_t trie)
  65. {
  66. _ASSERT(trie, ==, NULL, NULL_POINTER, NULL);
  67. return trie->parent;
  68. }
  69. void *trie_get_children(trie_tree_t trie)
  70. {
  71. _ASSERT(trie, ==, NULL, INVALID_INPUT, NULL);
  72. return trie->children;
  73. }
  74. int trie_get_children_number(trie_tree_t trie)
  75. {
  76. _ASSERT(trie, ==, NULL, INVALID_INPUT, -1);
  77. return vector_get_size(trie->children) % 256;
  78. }
  79. trie_tree_t trie_get_child(trie_tree_t trie, int index)
  80. {
  81. _ASSERT(trie, ==, NULL, INVALID_INPUT, NULL);
  82. _ASSERT(index, <, 0, INVALID_INPUT, NULL);
  83. _ASSERT(index, >=, SYMBOLS_NUMBER, INVALID_INPUT, NULL);
  84. return vector_get_key_at(trie->children, index);
  85. }
  86. trie_tree_t trie_insert(trie_tree_t _trie, char *suffix, void *key)
  87. {
  88. trie_tree_t add = NULL, next_trie;
  89. int nints, index;
  90. _ASSERT(suffix, ==, NULL, NULL_POINTER, NULL);
  91. nints = strlen(suffix);
  92. _ASSERT(nints, <, 1, INVALID_INPUT, NULL);
  93. // Input should be formed from intacters 'a'-'z'.
  94. _ASSERT(suffix[0], <, 'a', INVALID_INPUT, NULL);
  95. _ASSERT(suffix[0], >, 'z', INVALID_INPUT, NULL);
  96. index = suffix[0] - 'a';
  97. next_trie = vector_get_key_at(_trie->children, index);
  98. if (nints == 1)
  99. {
  100. if (next_trie != NULL)
  101. {
  102. next_trie->key = key;
  103. return next_trie;
  104. }
  105. else
  106. {
  107. add = trie_new(NULL);
  108. add->parent = _trie;
  109. vector_set_key_at(_trie->children, index, add);
  110. add->key = key;
  111. return add;
  112. }
  113. }
  114. else
  115. {
  116. if (next_trie != NULL)
  117. return trie_insert(next_trie, suffix + 1, key);
  118. else
  119. {
  120. add = trie_new(NULL);
  121. add->parent = _trie;
  122. vector_set_key_at(_trie->children, index, add);
  123. return trie_insert(add, suffix + 1, key);
  124. }
  125. }
  126. }
  127. void *trie_search(trie_tree_t trie, char *suffix)
  128. {
  129. return trie_get_key(_trie_search(trie, suffix));
  130. }
  131. void trie_remove(trie_tree_t _trie, char *suffix)
  132. {
  133. int i;
  134. trie_tree_t trie_removed = _trie_search(_trie, suffix), aux;
  135. _ASSERT(trie_removed, ==, NULL, NULL_POINTER,);
  136. /*
  137. * Remove a node only if it's parent isn't NULL, it's parent holds a NULL key
  138. * and it has no children.
  139. */
  140. while (1)
  141. {
  142. aux = trie_removed;
  143. trie_removed = trie_removed->parent;
  144. if (trie_get_children_number(aux) > 0)
  145. {
  146. aux->key = NULL;
  147. break;
  148. }
  149. if (trie_removed)
  150. {
  151. for (i = 0; i < SYMBOLS_NUMBER; i++)
  152. if (vector_get_key_at(trie_removed->children, i) == aux)
  153. {
  154. vector_set_key_at(trie_removed->children, i, NULL);
  155. break;
  156. }
  157. }
  158. _trie_delete_node(aux);
  159. if (!trie_removed || trie_removed->key)
  160. break;
  161. }
  162. }
  163. int trie_children_number(trie_tree_t trie)
  164. {
  165. int i = 0, children = 0;
  166. _ASSERT(trie, ==, NULL, NULL_POINTER, -1);
  167. for (; i < SYMBOLS_NUMBER; i++)
  168. if (vector_get_key_at(trie->children, i))
  169. ++children;
  170. return children;
  171. }
  172. int trie_is_leaf(trie_tree_t trie)
  173. {
  174. _ASSERT(trie, ==, NULL, NULL_POINTER, -1);
  175. return trie_children_number(trie) == 0;
  176. }
  177. int trie_is_empty(trie_tree_t trie)
  178. {
  179. _ASSERT(trie, ==, NULL, INVALID_INPUT, -1);
  180. return trie->parent == NULL && trie_is_leaf(trie);
  181. }
  182. void trie_preorder(trie_tree_t trie, void key_handler(void *key, void *context), void *context)
  183. {
  184. int i;
  185. _ASSERT(trie, ==, NULL, NULL_POINTER,);
  186. _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
  187. if (trie->key)
  188. key_handler(trie->key, context);
  189. for (i = 0; i < SYMBOLS_NUMBER; i++)
  190. trie_preorder(vector_get_key_at(trie->children, i), key_handler,
  191. context);
  192. }
  193. void trie_postorder(trie_tree_t trie, void key_handler(void *key, void *context), void *context)
  194. {
  195. int i;
  196. _ASSERT(trie, ==, NULL, NULL_POINTER,);
  197. _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
  198. for (i = SYMBOLS_NUMBER - 1; i >= 0; i--)
  199. trie_postorder(vector_get_key_at(trie->children, i), key_handler,
  200. context);
  201. if (trie->key)
  202. key_handler(trie->key, context);
  203. }
  204. void trie_level_order(trie_tree_t trie, void key_handler(void *key, void *context),
  205. void *context)
  206. {
  207. int i;
  208. queue_t queue;
  209. queue = queue_new(DEFAULT_SIZE);
  210. queue_push_back(queue, trie);
  211. while (!queue_is_empty(queue))
  212. {
  213. trie = queue_get_front(queue);
  214. queue_pop_front(queue);
  215. if (trie->key)
  216. key_handler(trie->key, context);
  217. for (i = 0; i < SYMBOLS_NUMBER; i++)
  218. if (vector_get_key_at(trie->children, i))
  219. queue_push_back(queue, vector_get_key_at(trie->children, i));
  220. }
  221. queue_delete(queue);
  222. }
  223. static trie_tree_t _trie_search(trie_tree_t trie, char *suffix)
  224. {
  225. int index;
  226. _ASSERT(trie, ==, NULL, NULL_POINTER, NULL);
  227. _ASSERT(suffix, ==, NULL, NULL_POINTER, NULL);
  228. if (suffix[0] == '\0')
  229. return trie;
  230. index = suffix[0] - 'a';
  231. return _trie_search(vector_get_key_at(trie->children, index), suffix + 1);
  232. }
  233. static void _trie_delete_node(trie_tree_t trie)
  234. {
  235. _ASSERT(trie, ==, NULL, NULL_POINTER,);
  236. vector_delete(trie->children);
  237. _delete(trie);
  238. }