tree_algorithms.c 2.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107
  1. /*!
  2. Temelia - Tree algorithms 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 "include/common.h"
  18. #include "include/linked_list.h"
  19. #include "include/iterator.h"
  20. #include "include/vector.h"
  21. #include "include/tree_algorithms.h"
  22. #include "include/queue.h"
  23. #include <stdlib.h>
  24. static void _queue_pusher(void *key, void *context);
  25. void tree_bfs_iterate(tree_t tree, void key_handler(void *x, void *context),
  26. void *context)
  27. {
  28. queue_t queue;
  29. tree_t current_node;
  30. LOGGER("[tree bfs travel] tree=\"%p\" key_handler=\"%p\" context=\"%p\"\n",
  31. tree, key_handler, context);
  32. _ASSERT(tree, ==, NULL, NULL_POINTER,);
  33. _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
  34. queue = queue_new(DEFAULT_SIZE);
  35. queue_push_back(queue, tree);
  36. while (!queue_is_empty(queue))
  37. {
  38. current_node = queue_get_front(queue);
  39. queue_pop_front(queue);
  40. key_handler(tree_get_key(current_node), context);
  41. if (tree_get_type(current_node))
  42. linked_list_iterate(tree_get_children(current_node),
  43. _queue_pusher, queue, 1);
  44. else
  45. vector_iterate(tree_get_children(current_node), _queue_pusher,
  46. queue);
  47. }
  48. queue_delete(queue);
  49. }
  50. void tree_dfs_iterate(tree_t tree, void key_handler(void *x, void *context),
  51. void *context)
  52. {
  53. linked_list_iterator_t it;
  54. int i, size;
  55. void *children;
  56. LOGGER("[tree dfs travel] tree=\"%p\" key_handler=\"%p\" context=\"%p\"\n",
  57. tree, key_handler, context);
  58. _ASSERT(tree, ==, NULL, NULL_POINTER,);
  59. _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
  60. key_handler(tree_get_key(tree), context);
  61. children = tree_get_children(tree);
  62. if (tree_get_type(tree))
  63. {
  64. for (it = linked_list_get_begin(children); it != NULL; it
  65. = linked_list_iterator_get_next(it))
  66. tree_dfs_iterate(linked_list_iterator_get_key(it), key_handler,
  67. context);
  68. }
  69. else
  70. {
  71. size = vector_get_size(children);
  72. for (i = 0; i < size; i++)
  73. tree_dfs_iterate(vector_get_key_at(children, i), key_handler,
  74. context);
  75. }
  76. }
  77. void _queue_pusher(void *key, void *context)
  78. {
  79. LOGGER("[tree bfs travel] _queue_pusher key=\"%p\" context=\"%p\"", key,
  80. context);
  81. queue_push_back(context, key);
  82. }