123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493 |
- /*!
- Temelia - Interval tree implementation source file.
- There are two ways to implement this data structure,
- with red-black trees and with some kind of heap. Because red-black tree is already
- implemented, here you can find the heap implementation of the interval tree.
- 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/interval_tree.h"
- #include "include/queue.h"
- #include <string.h>
- struct _interval_node_t
- {
- int inf, sup;
- void *key;
- };
- struct _interval_tree_t
- {
- interval_tree_node_t *data;
- int size;
- };
- static interval_tree_t _interval_tree_new(int inf, int sup);
- static void _interval_node_add(interval_tree_t tree, int index, int inf, int sup);
- static void _interval_tree_preorder(interval_tree_t interval, int index,
- void key_handler(void *x, void *context), void *context);
- static void _interval_tree_inorder(interval_tree_t interval, int index,
- void key_handler(void *x, void *context), void *context);
- static void _interval_tree_reverse_inorder(interval_tree_t interval, int index,
- void key_handler(void *x, void *context), void *context);
- static void _interval_tree_postorder(interval_tree_t interval, int index,
- void key_handler(void *x, void *context), void *context);
- static void _interval_tree_show_indented(interval_tree_t interval, int index,
- void key_handler(void *key, int level, void *context), void *context,
- int level);
- /*
- * @brief Returns the smallest power of 2 such x <= power(2,k).
- */
- static int _next_power_2(int x);
- static void _interval_tree_insert(interval_tree_t interval_tree, int index,
- int inf, int sup, void *key);
- static void _interval_tree_search(interval_tree_t interval_tree, int index,
- int inf, int sup, void key_handler(void *key, void *context),
- void *context);
- interval_tree_node_t interval_tree_node_new(int inf, int sup, void *key)
- {
- interval_tree_node_t interval;
- interval = (struct _interval_node_t *) _new(sizeof(struct _interval_node_t));
- _ASSERT(interval, ==, NULL, NULL_POINTER, NULL);
- /*
- * Set the node's key, infinimum and supremum to given values.
- */
- interval->key = key;
- interval->inf = inf;
- interval->sup = sup;
- return interval;
- }
- void interval_tree_node_delete(interval_tree_node_t interval)
- {
- _ASSERT(interval, ==, NULL, NULL_POINTER,);
- interval->key = NULL;
- interval->inf = interval->sup = 0;
- _delete(interval);
- }
- int interval_tree_node_get_inf(interval_tree_node_t interval)
- {
- _ASSERT(interval, ==, NULL, NULL_POINTER, -1);
- return interval->inf;
- }
- int interval_tree_node_get_sup(interval_tree_node_t interval)
- {
- _ASSERT(interval, ==, NULL, NULL_POINTER, -1);
- return interval->sup;
- }
- void *interval_tree_node_get_key(interval_tree_node_t interval)
- {
- _ASSERT(interval, ==, NULL, NULL_POINTER, NULL);
- return interval->key;
- }
- interval_tree_t interval_tree_new(int inf, int sup)
- {
- _ASSERT(inf,>, sup, INVALID_INPUT, NULL);
- return _interval_tree_new(inf, sup);
- }
- void interval_tree_delete(interval_tree_t interval_tree)
- {
- int i = 0;
- _ASSERT(interval_tree, ==, NULL, NULL_POINTER,);
- for (; i < interval_tree->size; i++)
- interval_tree_node_delete(interval_tree->data[i]);
- _delete(interval_tree->data);
- _delete(interval_tree);
- }
- int interval_tree_is_empty(interval_tree_t interval_tree)
- {
- int i;
- _ASSERT(interval_tree, ==, NULL, NULL_POINTER, -1);
- /*
- * Check if the current node has non-NULL children pointers.
- */
- for (i = 0; i < interval_tree->size; i++)
- if (interval_tree->data[i] && interval_tree->data[i]->key)
- return 0;
- return 1;
- }
- interval_tree_node_t *interval_tree_get_data(interval_tree_t interval_tree)
- {
- _ASSERT(interval_tree, ==, NULL, NULL_POINTER, NULL);
- return interval_tree->data;
- }
- int interval_tree_get_size(interval_tree_t interval_tree)
- {
- _ASSERT(interval_tree, ==, NULL, NULL_POINTER, -1);
- return interval_tree->size;
- }
- void interval_tree_search(interval_tree_t interval_tree, int inf, int sup,
- void key_handler(void *key, void *context), void *context)
- {
- _ASSERT(interval_tree, ==, NULL, NULL_POINTER,);
- _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
- _ASSERT(sup,>, interval_tree->data[0]->sup, INVALID_INPUT,);
- _ASSERT(inf, <, interval_tree->data[0]->inf, INVALID_INPUT,);
- /*
- * The algorithm is :
- * search (node, left, right, inf, sup)
- * {
- * if (inf <= left && right <= sup)
- * callback function (key stored in current node)
- * else
- * let mid be (left+right)/2
- * if (inf <= mid)
- * search(left node, left, mid, inf, sup);
- * if (sup >= mid+1)
- * search(right node, mid + 1, right, inf, sup);
- * callback function (key stored in current node)
- * }
- */
- _interval_tree_search(interval_tree, 0, inf, sup, key_handler, context);
- }
- void interval_tree_insert(interval_tree_t interval_tree, int inf, int sup,
- void *key)
- {
- _ASSERT(interval_tree, ==, NULL, NULL_POINTER,);
- _ASSERT(sup,>, interval_tree->data[0]->sup, INVALID_INPUT,);
- _ASSERT(inf, <, interval_tree->data[0]->inf, INVALID_INPUT,);
- /* The algorithm is :
- * search (node, left, right, inf, sup)
- * {
- * if (inf <= left && right <= sup)
- * change key's value, stored in current node, to new key
- * else
- * let mid be (left+right)/2
- * if (inf <= mid)
- * search(left node, left, mid, inf, sup);
- * if (sup >= mid+1)
- * search(right node, mid + 1, right, inf, sup);
- * change key's value, stored in current node, to new key
- */
- _interval_tree_insert(interval_tree, 0, inf, sup, key);
- }
- void interval_tree_remove(interval_tree_t interval_tree, int inf, int sup)
- {
- interval_tree_insert(interval_tree, inf, sup, NULL);
- }
- interval_tree_node_t interval_tree_get_node(interval_tree_t interval_tree, int index)
- {
- _ASSERT(interval_tree, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(index, <, 0, INVALID_INPUT, NULL);
- _ASSERT(index,>, interval_tree->size, INVALID_INPUT, NULL);
- return interval_tree->data[index];
- }
- void interval_tree_preorder(interval_tree_t interval, void key_handler(void *x,
- void *context), void *context)
- {
- _ASSERT(interval, ==, NULL, NULL_POINTER,);
- _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
- _interval_tree_preorder(interval, 0, key_handler, context);
- }
- void interval_tree_inorder(interval_tree_t interval, void key_handler(void *x,
- void *context), void *context)
- {
- _ASSERT(interval, ==, NULL, NULL_POINTER,);
- _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
- _interval_tree_inorder(interval, 0, key_handler, context);
- }
- void interval_tree_reverse_inorder(interval_tree_t interval, void key_handler(
- void *x, void *context), void *context)
- {
- _ASSERT(interval, ==, NULL, NULL_POINTER,);
- _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
- _interval_tree_reverse_inorder(interval, 0, key_handler, context);
- }
- void interval_tree_postorder(interval_tree_t interval, void key_handler(void *x,
- void *context), void *context)
- {
- _ASSERT(interval, ==, NULL, NULL_POINTER,);
- _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
- _interval_tree_postorder(interval, 0, key_handler, context);
- }
- void interval_tree_level_order(interval_tree_t interval, void key_handler(
- void *x, void *context), void *context)
- {
- queue_t Q = queue_new(DEFAULT_SIZE);
- int *current_node, *aux, node;
- aux = (int *) _new(sizeof(int));
- *aux = 0;
- queue_push_back(Q, aux);
- while (!queue_is_empty(Q))
- {
- current_node = queue_get_front(Q);
- queue_pop_front(Q);
- key_handler(interval->data[*current_node]->key, context);
- node = 2 * (*current_node) + 1;
- if (node < interval->size && interval->data[node])
- {
- aux = (int *) _new(sizeof(int));
- *aux = node;
- queue_push_back(Q, aux);
- }
- node++;
- if (node < interval->size && interval->data[node])
- {
- aux = (int *) _new(sizeof(int));
- *aux = node;
- queue_push_back(Q, aux);
- }
- _delete(current_node);
- }
- queue_delete(Q);
- }
- void interval_tree_show_indented(interval_tree_t interval, void key_handler(
- void *x, int level, void *context), void *context)
- {
- _ASSERT(interval, ==, NULL, NULL_POINTER,);
- _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
- _interval_tree_show_indented(interval, 0, key_handler, context, 0);
- }
- static void _interval_node_add(interval_tree_t tree, int index, int inf, int sup)
- {
- tree->data[index] = interval_tree_node_new(inf, sup, NULL);
- if (inf < sup)
- {
- _interval_node_add(tree, 2 * index + 1, inf, (inf + sup) / 2);
- _interval_node_add(tree, 2 * index + 2, (inf + sup) / 2 + 1, sup);
- }
- }
- static interval_tree_t _interval_tree_new(int inf, int sup)
- {
- interval_tree_t tree;
- tree = (struct _interval_tree_t *) _new(sizeof(struct _interval_tree_t));
- _ASSERT(tree, ==, NULL, NULL_POINTER, NULL);
- tree->size = 2 * _next_power_2(sup - inf + 1) - 1;
- tree->data = (interval_tree_node_t *) _new(tree->size * sizeof(interval_tree_node_t));
- memset(tree->data, 0, tree->size * sizeof(interval_tree_node_t));
- _ASSERT(tree->data, ==, NULL, NULL_POINTER, NULL);
- _interval_node_add(tree, 0, inf, sup);
- return tree;
- }
- static void _interval_tree_preorder(interval_tree_t interval, int index,
- void key_handler(void *x, void *context), void *context)
- {
- if (index < interval->size)
- {
- if (interval->data[index])
- key_handler(interval->data[index]->key, context);
- _interval_tree_preorder(interval, 2 * index + 1, key_handler, context);
- _interval_tree_preorder(interval, 2 * index + 2, key_handler, context);
- }
- }
- static void _interval_tree_inorder(interval_tree_t interval, int index,
- void key_handler(void *x, void *context), void *context)
- {
- if (index < interval->size)
- {
- _interval_tree_inorder(interval, 2 * index + 1, key_handler, context);
- if (interval->data[index])
- key_handler(interval->data[index]->key, context);
- _interval_tree_inorder(interval, 2 * index + 2, key_handler, context);
- }
- }
- static void _interval_tree_reverse_inorder(interval_tree_t interval, int index,
- void key_handler(void *x, void *context), void *context)
- {
- if (index < interval->size)
- {
- _interval_tree_inorder(interval, 2 * index + 2, key_handler, context);
- if (interval->data[index])
- key_handler(interval->data[index]->key, context);
- _interval_tree_inorder(interval, 2 * index + 1, key_handler, context);
- }
- }
- static void _interval_tree_postorder(interval_tree_t interval, int index,
- void key_handler(void *x, void *context), void *context)
- {
- if (index < interval->size)
- {
- _interval_tree_inorder(interval, 2 * index + 1, key_handler, context);
- _interval_tree_inorder(interval, 2 * index + 2, key_handler, context);
- if (interval->data[index])
- key_handler(interval->data[index]->key, context);
- }
- }
- void _interval_tree_show_indented(interval_tree_t interval, int index,
- void key_handler(void *key, int level, void *context), void *context,
- int level)
- {
- if (index < interval->size)
- {
- _interval_tree_show_indented(interval, 2 * index + 2, key_handler,
- context, level + 1);
- if (interval->data[index])
- key_handler(interval->data[index]->key, level, context);
- _interval_tree_show_indented(interval, 2 * index + 1, key_handler,
- context, level + 1);
- }
- }
- static int _next_power_2(int x)
- {
- int ok = 1;
- int y = 1;
- if (x == 0)
- return 1;
- while (x > 1)
- {
- if (x % 2 == 1)
- ok = 0;
- y *= 2;
- x /= 2;
- }
- if (!ok)
- y *= 2;
- return y;
- }
- static void _interval_tree_insert(interval_tree_t interval_tree, int index,
- int inf, int sup, void *key)
- {
- int _inf = 0, _sup = 0, _mid = 0;
- if (index >= interval_tree->size || interval_tree->data[index] == NULL)
- return;
- _inf = interval_tree->data[index]->inf;
- _sup = interval_tree->data[index]->sup;
- if (inf <= _inf && _sup <= sup)
- interval_tree->data[index]->key = key;
- else
- {
- _mid = (_inf + _sup) / 2;
- if (inf <= _mid)
- _interval_tree_insert(interval_tree, 2 * index + 1, inf, sup, key);
- if (sup >= _mid + 1)
- _interval_tree_insert(interval_tree, 2 * index + 2, inf, sup, key);
- interval_tree->data[index]->key = key;
- }
- }
- static void _interval_tree_search(interval_tree_t interval_tree, int index,
- int inf, int sup, void key_handler(void *key, void *context),
- void *context)
- {
- int _inf = 0, _sup = 0, _mid = 0;
- if (index >= interval_tree->size || interval_tree->data[index] == NULL)
- return;
- _inf = interval_tree->data[index]->inf;
- _sup = interval_tree->data[index]->sup;
- if (inf <= _inf && _sup <= sup)
- key_handler(interval_tree->data[index]->key, context);
- else
- {
- _mid = _inf + (_sup - _inf) / 2;
- if (inf <= _mid)
- _interval_tree_search(interval_tree, 2 * index + 1, inf, sup,
- key_handler, context);
- if (sup >= _mid + 1)
- _interval_tree_search(interval_tree, 2 * index + 2, inf, sup,
- key_handler, context);
- key_handler(interval_tree->data[index]->key, context);
- }
- }
|