temelia/release/include/interval_tree.h

/*!
 Temelia - Interval tree interface.

 Copyright (C) 2008, 2009 Ceata (http://cod.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.
 */

#ifndef INTERVAL_TREE_H_
#define INTERVAL_TREE_H_

#include "platform.h"
#include "common.h"

struct _interval_tree_t;
struct _interval_node_t;

typedef struct _interval_node_t *interval_tree_node_t;
typedef struct _interval_tree_t *interval_tree_t;

/*!
 * @brief Builds an interval [inf, sup] containing key. Once you've build an
 * interval, you can't change it's content. If you want another interval,
 * delete this one and create another. An interval is defined by two integers and
 * not doubles because you may scale your values and cast them to integer, if
 * |X-integer(X)| <= EPS; another reason is the spaced wasted having double records.
 * Complexity O(1)
 *
 * @param Inf
 * @param Sup
 * @param Key
 */
DECLSPEC interval_tree_node_t interval_tree_node_new(int inf, int sup, void *key);

/*!
 * @brief Deletes node.
 * Complexity O(1)
 *
 * @param Interval node
 */
DECLSPEC void interval_tree_node_delete(interval_tree_node_t interval);

/*!
 * @brief Returns the low end of interval.
 * Complexity O(1)
 *
 * @param Interval node
 */
DECLSPEC int interval_tree_node_get_inf(interval_tree_node_t interval);

/*!
 * @brief Returns the high end of interval.
 * Complexity O(1)
 *
 * @param Interval node
 */
DECLSPEC int interval_tree_node_get_sup(interval_tree_node_t interval);

/*!
 * @brief Returns the key stored in this interval.
 * Complexity O(1)
 *
 * @param Interval node
 */
DECLSPEC void *interval_tree_node_get_key(interval_tree_node_t interval);

/*!
 * @brief Returns an authoritative interval tree on given input. If you want
 * to store intervals in nodes, like in a binary tree, use a red-black tree.
 * Complexity O(1)
 *
 * @param Inf
 * @param Sup
 */
DECLSPEC interval_tree_t interval_tree_new(int inf, int sup);

/*!
 * @brief Frees the memory occupied by this interval tree.
 * Complexity O(size)
 *
 * @param Interval tree
 */
DECLSPEC void interval_tree_delete(interval_tree_t interval_tree);

/*!
 * @brief Return 1 if the tree is empty, 0 if not and -1 if an error occurred.
 * Complexity O(log(size))
 *
 * @param Interval tree
 */
DECLSPEC int interval_tree_is_empty(interval_tree_t interval_tree);

/*!
 * @brief Returns the internal representation of data.
 * Complexity O(1)
 *
 * @param Interval tree
 */
DECLSPEC interval_tree_node_t *interval_tree_get_data(interval_tree_t interval_tree);

/*!
 * @brief Returns the size of interval tree.
 * Complexity O(1)
 *
 * @param Interval tree
 */
DECLSPEC int interval_tree_get_size(interval_tree_t interval_tree);

/*!
 * @brief Searches an interval in current interval tree. For-each interval in tree
 * overlapping this interval, the function calls the callback function with
 * the key associated in each node; key must be not NULL.
 * Complexity O(log(size))
 *
 * @param Interval tree
 * @param Inf
 * @param Sup
 * @param Key handling function
 * @param Context
 */
DECLSPEC void interval_tree_search(interval_tree_t interval_tree, int inf, int sup,
		void key_handler(void *key, void *context), void *context);

/*!
 * @brief Inserts in the interval tree a new interval with the associated key.
 * If the interval already exists, the key is adjusted.
 * Complexity O(log(size))
 *
 * @param Interval tree
 * @param Inf
 * @param Sup
 * @param Key
 */
DECLSPEC void interval_tree_insert(interval_tree_t interval_tree, int inf, int sup,
		void *key);

/*!
 * @brief Removes key stored for an interval. It calls interval_tree_insert with
 * NULL key.
 * @param Interval tree
 * @param Inf
 * @param Sup
 * @see interval_tree_insert
 */
DECLSPEC void interval_tree_remove(interval_tree_t interval_tree, int inf, int sup);

/*!
 * @brief Returns the node at a given index; root is at 0.
 * Complexity O(1)
 *
 * @param Interval tree
 * @param Index
 */
DECLSPEC interval_tree_node_t interval_tree_get_node(interval_tree_t interval_tree,
		int index);

/*!
 * @see binary_tree_preorder
 */
DECLSPEC void interval_tree_preorder(interval_tree_t interval, void key_handler(void *x,
		void *context), void *context);
/*!
 * @see binary_tree_inorder
 */
DECLSPEC void interval_tree_inorder(interval_tree_t interval, void key_handler(void *x,
		void *context), void *context);
/*!
 * @see binary_tree_reverse_inorder
 */
DECLSPEC void interval_tree_reverse_inorder(interval_tree_t interval, void key_handler(
		void *x, void *context), void *context);

/*!
 * @see binary_tree_postorder
 */
DECLSPEC void interval_tree_postorder(interval_tree_t interval, void key_handler(
		void *x, void *context), void *context);

/*!
 * @see binary_tree_level_order
 */
DECLSPEC void interval_tree_level_order(interval_tree_t interval, void key_handler(
		void *x, void *context), void *context);

/*!
 * @see binary_tree_show_indented
 */
DECLSPEC void interval_tree_show_indented(interval_tree_t interval, void key_handler(
		void *x, int level, void *context), void *context);

#endif /* INTERVAL_TREE_H_ */