temelia/release/include/binary_search_tree.h

/*!
 Temelia - Binary search 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 BINARY_SEARCH_TREE_H_
#define BINARY_SEARCH_TREE_H_

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

/*!
 * @see binary_tree_new
 */
DECLSPEC binary_search_tree_t binary_search_tree_new(void *key);

/*!
 * @see binary_tree_delete_node
 */
DECLSPEC void binary_search_tree_delete_node(binary_search_tree_node_t node);

/*!
 * @see binary_tree_delete
 */
DECLSPEC void binary_search_tree_delete(binary_search_tree_t bst);

/*!
 * @see binary_tree_is_empty
 */
DECLSPEC char binary_search_tree_empty(binary_search_tree_t bst);

/*!
 * @see binary_tree_is_leaf
 */
DECLSPEC char binary_search_tree_leaf(binary_search_tree_t bst);

/*!
 * @see binary_tree_get_size
 */
DECLSPEC int binary_search_tree_get_size(binary_search_tree_t bst);

/*!
 * @see binary_tree_get_root
 */
DECLSPEC binary_search_tree_t
binary_search_tree_get_root(binary_search_tree_node_t node);

/*!
 * @see binary_tree_get_key
 */
DECLSPEC void *binary_search_tree_get_key(binary_search_tree_node_t node);

/*!
 * @see binary_tree_get_parent
 */
DECLSPEC binary_search_tree_node_t binary_search_tree_get_parent(
		binary_search_tree_node_t node);

/*!
 * @see binary_tree_get_left_child
 */
DECLSPEC binary_search_tree_node_t binary_search_tree_get_left_child(
		binary_search_tree_node_t node);

/*!
 * @see binary_tree_get_right_child
 */
DECLSPEC binary_search_tree_node_t binary_search_tree_get_right_child(
		binary_search_tree_node_t node);

/*!
 * @see binary_tree_split
 */
DECLSPEC void binary_search_tree_split(binary_search_tree_t parent,
		binary_search_tree_t *left, binary_search_tree_t *right);

/*!
 * @see binary_tree_get_height
 */
DECLSPEC int binary_search_tree_get_height(binary_search_tree_t tree);

/*!
 * @see binary_tree_get_depth
 */
DECLSPEC int binary_search_tree_get_depth(binary_search_tree_node_t node);

/*!
 * @brief Searches key in binary search tree and returns the node reference.
 * Complexity O(log(n)); worst case O(n)
 *
 * @param Binary search tree
 * @param Key
 * @param Pointer to comparison function
 */
DECLSPEC binary_search_tree_node_t binary_search_tree_search(binary_search_tree_t bst,
		void *key, int compare(void *x, void *y, void *context), void *context);

/*!
 * @brief Inserts a key in binary search tree and returns a pointer to the added tree node.
 * Complexity O(log(n)); worst case O(n)
 *
 * @param Binary search tree
 * @param Key
 * @param Pointer to comparison function
 * @param Comparison context
 */
DECLSPEC binary_search_tree_node_t binary_search_tree_insert(binary_search_tree_t bst,
		void *key, int compare(void *x, void *y, void *context), void *context);

/*!
 * @brief Removes a key from binary search tree. Returns the replaced binary
 * search tree node. This is very useful for algorithm on advanced binary search
 * tree structures as AVL or red-black.
 *
 * In order to remove memory leaks, free the returned pointer
 *
 * Complexity O(log(n)); worst case O(n)
 *
 * @param Address of binary search tree
 * @param Key
 * @param Pointer to comparison function
 * @param Comparison context
 * @param Pointer to deleted node from tree
 */
DECLSPEC binary_search_tree_node_t binary_search_tree_remove(binary_search_tree_t *bst,
		void *key, int compare(void *x, void *y, void *context), void *context,
		binary_search_tree_t *freed);

/*!
 * @brief Returns the minimum node from binary search tree.
 * Complexity O(log(n)); worst case O(n)
 *
 * @param Binary search tree
 */
DECLSPEC binary_search_tree_node_t binary_search_tree_get_min(binary_search_tree_t bst);

/*!
 * @brief Returns the maximum node from binary search tree.
 * Complexity O(log(n)); worst case O(n)
 *
 * @param Binary search tree
 */
DECLSPEC binary_search_tree_node_t binary_search_tree_get_max(binary_search_tree_t bst);

/*!
 * @brief Returns the next node traversing in inorder.
 * Complexity O(log(n)); worst case O(n)
 *
 * @param Binary search tree
 * @param Binary search tree node
 */
DECLSPEC binary_search_tree_node_t binary_search_tree_next(binary_search_tree_t bst,
		binary_search_tree_node_t node);

/*!
 * @brief Returns the previous node traversing in inorder.
 * Complexity O(log(n)); worst case O(n)
 *
 * @param Binary search tree
 * @param Binary search tree node
 */
DECLSPEC binary_search_tree_node_t binary_search_tree_prev(binary_search_tree_t bst,
		binary_search_tree_node_t node);

/*!
 * @see binary_tree_preorder
 */
DECLSPEC void binary_search_tree_preorder(binary_search_tree_t tree, void key_handler(
		void *x, void *context), void *context);

/*!
 * @see binary_tree_inorder
 */
DECLSPEC void binary_search_tree_inorder(binary_search_tree_t tree, void key_handler(
		void *x, void *context), void *context);

/*!
 * @see binary_tree_reverse_inorder
 */
DECLSPEC void binary_search_tree_reverse_inorder(binary_search_tree_t tree,
		void key_handler(void *x, void *context), void *context);

/*!
 * @see binary_tree_postorder
 */
DECLSPEC void binary_search_tree_postorder(binary_search_tree_t tree, void key_handler(
		void *x, void *context), void *context);

/*!
 * @see binary_tree_level_order
 */
DECLSPEC void binary_search_tree_level_order(binary_search_tree_t tree,
		void key_handler(void *x, void *context), void *context);

/*!
 * @see binary_tree_show_indented
 */
DECLSPEC void binary_search_tree_show_indented(binary_search_tree_t tree,
		void key_handler(void *key, int level, void *context), void *context);

#endif /* BINARY_SEARCH_TREE_H_ */