temelia/release/include/b_tree.h

/*!
 Temelia - B-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 B_TREE_H_
#define B_TREE_H_

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

struct _b_tree_t;
typedef struct _b_tree_t *b_tree_t;

struct _b_tree_node_t;
typedef struct _b_tree_node_t *b_tree_node_t;

/*!
 * @brief Constructor - returns an empty b-tree with given degree
 * Complexity O(1)
 *
 * @param Degree
 */
DECLSPEC b_tree_t b_tree_new(int degree);

/*!
 * @brief Destructor - frees the memory occupied by this b-tree
 * @param B-tree
 */
DECLSPEC void b_tree_delete(b_tree_t b_tree);

/*!
 * @brief Returns the root of current b-tree.
 * Complexity O(1)
 *
 * @param B-tree
 */
DECLSPEC b_tree_node_t b_tree_get_root(b_tree_t b_tree);

/*!
 * @brief Returns the degree of current b-tree.
 * Complexity O(1)
 *
 * @param B-tree
 */
DECLSPEC int b_tree_get_degree(b_tree_t b_tree);

/*!
 * @brief Returns the height of current b-tree.
 * Complexity O(log(n))
 *
 * @param B-tree
 */
DECLSPEC int b_tree_get_height(b_tree_t b_tree);

/*!
 * @brief Returns the depth of current node in it's b-tree.
 * Complexity O(log(n))
 *
 * @param B-tree node
 */
DECLSPEC int b_tree_node_get_depth(b_tree_node_t node);

/*!
 * @brief Returns the node's parent.
 * Complexity O(1)
 *
 * @param B-tree node
 */
DECLSPEC b_tree_node_t b_tree_node_get_parent(b_tree_node_t node);

/*!
 * @brief Returns the node's children number.
 * Complexity O(1)
 *
 * @param B-tree node
 */
DECLSPEC int b_tree_node_get_children_number(b_tree_node_t node);

/*!
 * @brief Returns node's child given by it's index.
 * Complexity O(1)
 *
 * @param B-tree node
 * @param Child index in children list.
 */
DECLSPEC b_tree_node_t b_tree_node_get_child(b_tree_node_t node, int index);

/*!
 * @brief Returns node's keys number.
 * Complexity O(1)
 *
 * @param B-tree node
 */
DECLSPEC int b_tree_node_get_keys_number(b_tree_node_t node);

/*!
 * @brief Returns node's key given by it's index.
 * Complexity O(1)
 *
 * @param B-tree node
 * @param Child index
 */
DECLSPEC void *b_tree_node_get_key(b_tree_node_t node, int index);

/*!
 * @brief Returns b-tree's size.
 * Complexity O(1)
 *
 * @param B-tree
 */
DECLSPEC int b_tree_get_size(b_tree_t b_tree);

/*!
 * @brief Searches given key in current b-tree; returns a reference
 * to the node storing the key and NULL otherwise.
 * Complexity O(log(n))
 *
 * @param B-tree
 * @param Key
 * @param Pointer to comparison function
 * @param Comparison context
 */
DECLSPEC b_tree_node_t b_tree_search(b_tree_t b_tree, void *key, int compare(void *x,
		void *y, void *context), void *context);

/*!
 * @brief Inserts key in current b-tree; returns a reference to new added
 * node.
 * Complexity O(log(n))
 *
 * @param Key reference
 * @param Pointer to comparison function
 * @param Add if the key already exists in b-tree : 0 if you don't want this to happen
 * and not 0 if you want to add an equal key
 */
DECLSPEC b_tree_node_t b_tree_insert(b_tree_t b_tree, void *key, int compare(void *x,
		void *y, void *context), void *context, char add_if_exists);

/*!
 * @brief Removes key from current b-tree. Returns 1 if it successfully
 * deletes key else it returns false.
 * Complexity O(log(n))
 *
 * @param Key
 * @param Pointer to comparison function
 * @param Comparison context
 */
DECLSPEC int b_tree_remove(b_tree_t b_tree, void *key, int compare(void *x, void *y,
		void *context), void *context);

/*!
 * @brief Returns the minimum node from current b-tree.
 * Complexity O(log(n))
 *
 * @param B-tree
 */
DECLSPEC b_tree_node_t b_tree_get_min(b_tree_t b_tree);

/*!
 * @brief Returns the minimum key in current b-tree.
 * Complexity O(log(n))
 *
 * @param B-tree
 */
DECLSPEC void *b_tree_get_min_key(b_tree_t b_tree);

/*!
 * @brief Returns the maximum node from current b-tree.
 * Complexity O(log(n))
 *
 * @param B-tree
 */
DECLSPEC b_tree_node_t b_tree_get_max(b_tree_t b_tree);

/*!
 * @brief Returns the maximum key in current b-tree.
 * Complexity O(log(n))
 *
 * @param B-tree
 */
DECLSPEC void *b_tree_get_max_key(b_tree_t b_tree);

/*!
 * @brief Prints the b-tree keys in level order. It's used in debugging.
 * If you want to iterate over b-tree's keys, use the functions that gives
 * you access to keys, parent and children of b-tree's root.
 *
 * Also, you can force the pointer to stream (FILE *) to be a generic pointer;
 * the library is not using that pointer so it's up to you what it reference.
 *
 * Complexity O(size)
 *
 * @param B-tree
 * @param Pointer to key printing function
 * @param Context
 */
DECLSPEC void b_tree_level_order(b_tree_t b_tree, void key_handler(void *x,
		void *context), void *context);

/*!
 * @brief Prints indented the b-tree keys.
 * Complexity O(size)
 *
 * @see b_tree_level_order
 */
DECLSPEC void b_tree_show_indented(b_tree_t b_tree, void key_handler(void *key,
		int level, void *context), void *context);

#endif /* B_TREE_H_ */