_gdsl_bstree.h

一个通用的C语言实现的数据结构

/*
 * This file is part of the Generic Data Structures Library (GDSL).
 * Copyright (C) 1998-2006 Nicolas Darnis <[e-mail]>.
 *
 * The GDSL library is free software; you can redistribute it and/or 
 * modify it under the terms of the GNU General Public License as 
 * published by the Free Software Foundation; either version 2 of
 * the License, or (at your option) any later version.
 *
 * The GDSL library 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 the GDSL library; see the file COPYING.
 * If not, write to the Free Software Foundation, Inc., 
 * 59 Temple Place, Suite 330, Boston, MA  02111-1307, USA.
 *
 * $RCSfile: _gdsl_bstree.h,v $
 * $Revision: 1.29 $
 * $Date: 2006/03/04 16:32:05 $
 */


#ifndef __GDSL_BSTREE_H_
#define __GDSL_BSTREE_H_


#include "_gdsl_bintree.h"
#include "gdsl_macros.h"
#include "gdsl_types.h"


#ifdef __cplusplus
extern "C" 
{
#endif /* __cplusplus */


/**
 * @defgroup _gdsl_bstree Low-level binary search tree manipulation module
 * @{
 */

/**
 * @brief GDSL low-level binary search tree type.
 *
 * This type is voluntary opaque. Variables of this kind could'nt be directly
 * used, but by the functions of this module.
 */
typedef _gdsl_bintree_t _gdsl_bstree_t;

/**
 * @brief GDSL low-level binary search tree map function type.
 * @param TREE The low-level binary search tree to map.
 * @param USER_DATA The user datas to pass to this function.
 * @return GDSL_MAP_STOP if the mapping must be stopped.
 * @return GDSL_MAP_CONT if the mapping must be continued.
 */
typedef int (* _gdsl_bstree_map_func_t) (_gdsl_bstree_t TREE,
					 void* USER_DATA
					 );

/**
 * @brief GDSL low-level binary search tree write function type.
 * @param TREE The low-level binary search tree to write.
 * @param OUTPUT_FILE The file where to write TREE.
 * @param USER_DATA The user datas to pass to this function.
 */
typedef void (* _gdsl_bstree_write_func_t) (_gdsl_bstree_t TREE,
					    FILE* OUTPUT_FILE,
					    void* USER_DATA
					    );

/******************************************************************************/
/* Management functions of low-level binary search trees                      */
/******************************************************************************/

/**
 * @brief Create a new low-level binary search tree.
 *
 * Allocate a new low-level binary search tree data structure. Its root 
 * content is sets to E and its left and right sons are set to NULL.
 *
 * @note Complexity: O( 1 )
 * @pre nothing.
 * @param E The root content of the new low-level binary search tree to create.
 * @return the newly allocated low-level binary search tree in case of success.
 * @return NULL in case of insufficient memory.
 * @see _gdsl_bstree_free()
 */
extern _gdsl_bstree_t
_gdsl_bstree_alloc (const gdsl_element_t E
		    );

/**
 * @brief Destroy a low-level binary search tree.
 *
 * Flush and destroy the low-level binary search tree T. If FREE_F != NULL, 
 * FREE_F function is used to deallocate each T's element. Otherwise nothing is 
 * done with T's elements.
 *
 * @note Complexity: O( |T| )
 * @pre nothing.
 * @param T The low-level binary search tree to destroy.
 * @param FREE_F The function used to deallocate T's nodes contents.
 * @see _gdsl_bstree_alloc()
 */
extern void 
_gdsl_bstree_free (_gdsl_bstree_t T,
		   const gdsl_free_func_t FREE_F
		   );

/**
 * @brief Copy a low-level binary search tree.
 *
 * Create and return a copy of the low-level binary search tree T using COPY_F
 * on each T's element to copy them.
 *
 * @note Complexity: O( |T| )
 * @pre COPY_F != NULL.
 * @param T The low-level binary search tree to copy.
 * @param COPY_F The function used to copy T's nodes contents.
 * @return a copy of T in case of success.
 * @return NULL if _gdsl_bstree_is_empty (T) == TRUE or in case of insufficient
 * memory.
 * @see _gdsl_bstree_alloc()
 * @see _gdsl_bstree_free()
 * @see _gdsl_bstree_is_empty()
 */
extern _gdsl_bstree_t
_gdsl_bstree_copy (const _gdsl_bstree_t T,
		   const gdsl_copy_func_t COPY_F
		   );

/******************************************************************************/
/* Consultation functions of low-level binary search trees                    */
/******************************************************************************/

/** 
 * @brief Check if a low-level binary search tree is empty.
 * @note Complexity: O( 1 )
 * @pre nothing.
 * @param T The low-level binary search tree to check.
 * @return TRUE if the low-level binary search tree T is empty.
 * @return FALSE if the low-level binary search tree T is not empty.
 * @see _gdsl_bstree_is_leaf()
 * @see _gdsl_bstree_is_root()
 */
extern bool
_gdsl_bstree_is_empty (const _gdsl_bstree_t T
		       );

/**
 * @brief Check if a low-level binary search tree is reduced to a leaf.
 * @note Complexity: O( 1 )
 * @pre T must be a non-empty _gdsl_bstree_t.
 * @param T The low-level binary search tree to check.
 * @return TRUE if the low-level binary search tree T is a leaf.
 * @return FALSE if the low-level binary search tree T is not a leaf.
 * @see _gdsl_bstree_is_empty()
 * @see _gdsl_bstree_is_root()
 */
extern bool
_gdsl_bstree_is_leaf (const _gdsl_bstree_t T
		      );

/**
 * @brief Get the root content of a low-level binary search tree.
 * @note Complexity: O( 1 )
 * @pre T must be a non-empty _gdsl_bstree_t.
 * @param T The low-level binary search tree to use.
 * @return the root's content of the low-level binary search tree T.
 */
extern gdsl_element_t
_gdsl_bstree_get_content (const _gdsl_bstree_t T
			  );

/**
 * @brief Check if a low-level binary search tree is a root.
 * @note Complexity: O( 1 )
 * @pre T must be a non-empty _gdsl_bstree_t.
 * @param T The low-level binary search tree to check.
 * @return TRUE if the low-level binary search tree T is a root.
 * @return FALSE if the low-level binary search tree T is not a root.
 * @see _gdsl_bstree_is_empty()
 * @see _gdsl_bstree_is_leaf()
 */
extern bool
_gdsl_bstree_is_root (const _gdsl_bstree_t T
		      );

/**
 * @brief Get the parent tree of a low-level binary search tree.
 * @note Complexity: O( 1 )
 * @pre T must be a non-empty _gdsl_bstree_t.
 * @param T The low-level binary search tree to use.
 * @return the parent of the low-level binary search tree T if T isn't a root.
 * @return NULL if the low-level binary search tree T is a root (ie. T has no 
 * parent).
 * @see _gdsl_bstree_is_root()
 */
extern _gdsl_bstree_t
_gdsl_bstree_get_parent (const _gdsl_bstree_t T
			 );

/**
 * @brief Get the left sub-tree of a low-level binary search tree.
 * @note Complexity: O( 1 )
 * @pre T must be a non-empty _gdsl_bstree_t.
 * @param T The low-level binary search tree to use.
 * @return the left sub-tree of the low-level binary search tree T if T has a 
 * left sub-tree.
 * @return NULL if the low-level binary search tree T has no left sub-tree.
 * @see _gdsl_bstree_get_right()
 */
extern _gdsl_bstree_t
_gdsl_bstree_get_left (const _gdsl_bstree_t T
		       );

/**
 * @brief Get the right sub-tree of a low-level binary search tree.
 * @note Complexity: O( 1 )
 * @pre T must be a non-empty _gdsl_bstree_t.
 * @param T The low-level binary search tree to use.
 * @return the right sub-tree of the low-level binary search tree T if T has a 
 * right sub-tree.
 * @return NULL if the low-level binary search tree T has no right sub-tree.
 * @see _gdsl_bstree_get_left()
 */
extern _gdsl_bstree_t
_gdsl_bstree_get_right (const _gdsl_bstree_t T
			);

/**
 * @brief Get the size of a low-level binary search tree.
 * @note Complexity: O( |T| )
 * @pre nothing.
 * @param T The low-level binary search tree to compute the size from.
 * @return the number of elements of T (noted |T|).
 * @see _gdsl_bstree_get_height()
 */
extern ulong
_gdsl_bstree_get_size (const _gdsl_bstree_t T
		       );
  
/**
 * @brief Get the height of a low-level binary search tree.
 *
 * Compute the height of the low-level binary search tree T (noted h(T)).
 *
 * @note Complexity: O( |T| )
 * @pre nothing.
 * @param T The low-level binary search tree to compute the height from.
 * @return the height of T.
 * @see _gdsl_bstree_get_size()
 */
extern ulong
_gdsl_bstree_get_height (const _gdsl_bstree_t T
			 );

/******************************************************************************/
/* Modification functions of low-level binary search trees                    */
/******************************************************************************/

/**
 * @brief Insert an element into a low-level binary search tree if it's not 
 * found or return it.
 *
 * Search for the first element E equal to VALUE into the low-level binary 
 * search tree T, by using COMP_F function to find it. If an element E equal to
 * VALUE is found, then it's returned. If no element equal to VALUE is found, 
 * then E is inserted and its root returned.