123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107 |
- /*!
- Temelia - Tree algorithms 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 "include/common.h"
- #include "include/linked_list.h"
- #include "include/iterator.h"
- #include "include/vector.h"
- #include "include/tree_algorithms.h"
- #include "include/queue.h"
- #include <stdlib.h>
- static void _queue_pusher(void *key, void *context);
- void tree_bfs_iterate(tree_t tree, void key_handler(void *x, void *context),
- void *context)
- {
- queue_t queue;
- tree_t current_node;
- LOGGER("[tree bfs travel] tree=\"%p\" key_handler=\"%p\" context=\"%p\"\n",
- tree, key_handler, context);
- _ASSERT(tree, ==, NULL, NULL_POINTER,);
- _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
- queue = queue_new(DEFAULT_SIZE);
- queue_push_back(queue, tree);
- while (!queue_is_empty(queue))
- {
- current_node = queue_get_front(queue);
- queue_pop_front(queue);
- key_handler(tree_get_key(current_node), context);
- if (tree_get_type(current_node))
- linked_list_iterate(tree_get_children(current_node),
- _queue_pusher, queue, 1);
- else
- vector_iterate(tree_get_children(current_node), _queue_pusher,
- queue);
- }
- queue_delete(queue);
- }
- void tree_dfs_iterate(tree_t tree, void key_handler(void *x, void *context),
- void *context)
- {
- linked_list_iterator_t it;
- int i, size;
- void *children;
- LOGGER("[tree dfs travel] tree=\"%p\" key_handler=\"%p\" context=\"%p\"\n",
- tree, key_handler, context);
- _ASSERT(tree, ==, NULL, NULL_POINTER,);
- _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
- key_handler(tree_get_key(tree), context);
- children = tree_get_children(tree);
- if (tree_get_type(tree))
- {
- for (it = linked_list_get_begin(children); it != NULL; it
- = linked_list_iterator_get_next(it))
- tree_dfs_iterate(linked_list_iterator_get_key(it), key_handler,
- context);
- }
- else
- {
- size = vector_get_size(children);
- for (i = 0; i < size; i++)
- tree_dfs_iterate(vector_get_key_at(children, i), key_handler,
- context);
- }
- }
- void _queue_pusher(void *key, void *context)
- {
- LOGGER("[tree bfs travel] _queue_pusher key=\"%p\" context=\"%p\"", key,
- context);
- queue_push_back(context, key);
- }
|