_gdsl_bstree.h

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

 *
 * @note Complexity: O( h(T) ), where log2(|T|) <= h(T) <= |T|-1
 * @pre COMP_F != NULL & RESULT != NULL.
 * @param T The reference of the low-level binary search tree to use.
 * @param COMP_F The comparison function to use to compare T's elements with
 * VALUE to find E.
 * @param VALUE The value used to search for the element E.
 * @param RESULT The address where the result code will be stored.
 * @return the root containing E and RESULT = GDSL_INSERTED if E is inserted.
 * @return the root containing E and RESULT = GDSL_ERR_DUPLICATE_ENTRY if E is
 * not inserted.
 * @return NULL and RESULT = GDSL_ERR_MEM_ALLOC in case of failure.
 * @see _gdsl_bstree_search()
 * @see _gdsl_bstree_remove()
 */
extern _gdsl_bstree_t
_gdsl_bstree_insert (_gdsl_bstree_t* T,
		     const gdsl_compare_func_t COMP_F,
		     const gdsl_element_t VALUE,
		     int* RESULT
		     );

/**
 * @brief Remove an element from a low-level binary search tree.
 *
 * Remove from the low-level binary search tree T the first founded element E
 * equal to VALUE, by using COMP_F function to compare T's elements. If E is 
 * found, it is removed from T.
 *
 * @note Complexity: O( h(T) ), where log2(|T|) <= h(T) <= |T|-1
 * @note The resulting T is modified by examinating the left sub-tree from the
 * founded e.
 * @pre COMP_F != NULL.
 * @param T The reference of the low-level binary search tree to modify.
 * @param COMP_F The comparison function to use to compare T's elements with
 * VALUE to find the element e to remove.
 * @param VALUE The value that must be used by COMP_F to find the element e to
 * remove.
 * @return the fisrt founded element equal to VALUE in T.
 * @return NULL if no element equal to VALUE is found or if T is empty.
 * @see _gdsl_bstree_insert()
 * @see _gdsl_bstree_search()
 */
extern gdsl_element_t
_gdsl_bstree_remove (_gdsl_bstree_t* T,
		     const gdsl_compare_func_t COMP_F,
		     const gdsl_element_t VALUE
		     );
  
/******************************************************************************/
/* Search functions of low-level binary search trees                          */
/******************************************************************************/

/**
 * @brief Search for a particular element into a low-level binary search tree.
 *
 * Search the first element E equal to VALUE in the low-level binary search tree
 * T, by using COMP_F function to find it.
 *
 * @note Complexity: O( h(T) ), where log2(|T|) <= h(T) <= |T|-1
 * @pre COMP_F != NULL.
 * @param T The low-level binary search tree to use.
 * @param COMP_F The comparison function to use to compare T's elements with 
 * VALUE to find the element E.
 * @param VALUE The value that must be used by COMP_F to find the element E.
 * @return the root of the tree containing E if it's found.
 * @return NULL if VALUE is not found in T.
 * @see _gdsl_bstree_insert()
 * @see _gdsl_bstree_remove()
 */
extern _gdsl_bstree_t
_gdsl_bstree_search (const _gdsl_bstree_t T,
		     const gdsl_compare_func_t COMP_F,
		     const gdsl_element_t VALUE
		     );

/**
 * @brief Search for the next element of a particular element into a low-level 
 * binary search tree, according to the binary search tree order.
 *
 * Search for an element E in the low-level binary search tree T, by using 
 * COMP_F function to find the first element E equal to VALUE. 
 *
 * @note Complexity: O( h(T) ), where log2(|T|) <= h(T) <= |T|-1
 * @pre COMP_F != NULL.
 * @param T The low-level binary search tree to use.
 * @param COMP_F The comparison function to use to compare T's elements with 
 * VALUE to find the element E.
 * @param VALUE The value that must be used by COMP_F to find the element E.
 * @return the root of the tree containing the successor of E if it's found.
 * @return NULL if VALUE is not found in T or if E has no sucessor.
 */
extern _gdsl_bstree_t
_gdsl_bstree_search_next (const _gdsl_bstree_t T, 
			  const gdsl_compare_func_t COMP_F,
			  const gdsl_element_t VALUE
			  );

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

/**
 * @brief Parse a low-level binary search tree in prefixed order.
 *
 * Parse all nodes of the low-level binary search tree T in prefixed order. The 
 * MAP_F function is called on each node with the USER_DATA argument. If MAP_F
 * returns GDSL_MAP_STOP, then _gdsl_bstree_map_prefix() stops and returns its 
 * last examinated node.
 *
 * @note Complexity: O( |T| )
 * @pre MAP_F != NULL.
 * @param T The low-level binary search tree to map.
 * @param MAP_F The map function.
 * @param USER_DATA User's datas passed to MAP_F.
 * @return the first node for which MAP_F returns GDSL_MAP_STOP.
 * @return NULL when the parsing is done.
 * @see _gdsl_bstree_map_infix()
 * @see _gdsl_bstree_map_postfix()
 */
extern _gdsl_bstree_t
_gdsl_bstree_map_prefix (const _gdsl_bstree_t T,
			 const _gdsl_bstree_map_func_t MAP_F,
			 void* USER_DATA
			 );

/**
 * @brief Parse a low-level binary search tree in infixed order.
 *
 * Parse all nodes of the low-level binary search tree T in infixed order. The 
 * MAP_F function is called on each node with the USER_DATA argument. If MAP_F
 * returns GDSL_MAP_STOP, then _gdsl_bstree_map_infix() stops and returns its 
 * last examinated node.
 *
 * @note Complexity: O( |T| )
 * @pre MAP_F != NULL.
 * @param T The low-level binary search tree to map.
 * @param MAP_F The map function.
 * @param USER_DATA User's datas passed to MAP_F.
 * @return the first node for which MAP_F returns GDSL_MAP_STOP.
 * @return NULL when the parsing is done.
 * @see _gdsl_bstree_map_prefix()
 * @see _gdsl_bstree_map_postfix()
 */
extern _gdsl_bstree_t
_gdsl_bstree_map_infix (const _gdsl_bstree_t T,
			const _gdsl_bstree_map_func_t MAP_F,
			void* USER_DATA
			);

/**
 * @brief Parse a low-level binary search tree in postfixed order.
 *
 * Parse all nodes of the low-level binary search tree T in postfixed order. The
 * MAP_F function is called on each node with the USER_DATA argument. If MAP_F
 * returns GDSL_MAP_STOP, then _gdsl_bstree_map_postfix() stops and returns its 
 * last examinated node.
 *
 * @note Complexity: O( |T| )
 * @pre MAP_F != NULL.
 * @param T The low-level binary search tree to map.
 * @param MAP_F The map function.
 * @param USER_DATA User's datas passed to MAP_F.
 * @return the first node for which MAP_F returns GDSL_MAP_STOP.
 * @return NULL when the parsing is done.
 * @see _gdsl_bstree_map_prefix()
 * @see _gdsl_bstree_map_infix()
 */
extern _gdsl_bstree_t
_gdsl_bstree_map_postfix (const _gdsl_bstree_t T,
			  const _gdsl_bstree_map_func_t MAP_F,
			  void* USER_DATA
			  );

/******************************************************************************/
/* Input/output functions of low-level binary search trees                    */
/******************************************************************************/

/**
 * @brief Write the content of all nodes of a low-level binary search tree to a
 * file.
 *
 * Write the nodes contents of the low-level binary search tree T to 
 * OUTPUT_FILE, using WRITE_F function.
 * Additionnal USER_DATA argument could be passed to WRITE_F.
 *
 * @note Complexity: O( |T| )
 * @pre WRITE_F != NULL& OUTPUT_FILE != NULL.
 * @param T The low-level binary search tree to write.
 * @param WRITE_F The write function.
 * @param OUTPUT_FILE The file where to write T's nodes.
 * @param USER_DATA User's datas passed to WRITE_F.
 * @see _gdsl_bstree_write_xml()
 * @see _gdsl_bstree_dump()
 */
extern void
_gdsl_bstree_write (const _gdsl_bstree_t T,
		    const _gdsl_bstree_write_func_t WRITE_F,
		    FILE* OUTPUT_FILE,
		    void* USER_DATA
		    );

/**
 * @brief Write the content of a low-level binary search tree to a file into 
 * XML.
 *
 * Write the nodes contents of the low-level binary search tree T to 
 * OUTPUT_FILE, into XML language.
 * If WRITE_F != NULL, then use WRITE_F function to write T's nodes contents to
 * OUTPUT_FILE.
 * Additionnal USER_DATA argument could be passed to WRITE_F.
 *
 * @note Complexity: O( |T| )
 * @pre OUTPUT_FILE != NULL.
 * @param T The low-level binary search tree to write.
 * @param WRITE_F The write function.
 * @param OUTPUT_FILE The file where to write T's nodes.
 * @param USER_DATA User's datas passed to WRITE_F.
 * @see _gdsl_bstree_write()
 * @see _gdsl_bstree_dump()
 */
extern void
_gdsl_bstree_write_xml (const _gdsl_bstree_t T,
			const _gdsl_bstree_write_func_t WRITE_F,
			FILE* OUTPUT_FILE,
			void* USER_DATA
			);

/**
 * @brief Dump the internal structure of a low-level binary search tree to a 
 * file.
 *
 * Dump the structure of the low-level binary search tree T to OUTPUT_FILE. If 
 * WRITE_F != NULL, then use WRITE_F function to write T's nodes content to 
 * OUTPUT_FILE.
 * Additionnal USER_DATA argument could be passed to WRITE_F.
 *
 * @note Complexity: O( |T| )
 * @pre OUTPUT_FILE != NULL.
 * @param T The low-level binary search tree to dump.
 * @param WRITE_F The write function.
 * @param OUTPUT_FILE The file where to write T's nodes.
 * @param USER_DATA User's datas passed to WRITE_F.
 * @see _gdsl_bstree_write()
 * @see _gdsl_bstree_write_xml()
 */
extern void
_gdsl_bstree_dump (const _gdsl_bstree_t T,
		   const _gdsl_bstree_write_func_t WRITE_F,
		   FILE* OUTPUT_FILE,
		   void* USER_DATA
		   );

/*
 * @}
 */


#ifdef __cplusplus
}
#endif /* __cplusplus */


#endif /* _GDSL_BSTREE_H_ */


/** EMACS **
 * Local variables:
 * mode: c
 * c-basic-offset: 4
 * End:
 */