gdsl_bstree.h

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

 * VALUE, by using T's COMP_F function passed to gdsl_bstree_alloc(). If E is
 * found, it is removed from T and then returned.
 *
 * @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 T must be a valid gdsl_bstree_t
 * @param T The binary search tree to modify
 * @param VALUE The value used to find the element to remove
 * @return the first founded element equal to VALUE in T in case is found.
 * @return NULL in case no element equal to VALUE is found in T.
 * @see gdsl_bstree_insert()
 * @see gdsl_bstree_delete()
 */
extern gdsl_element_t
gdsl_bstree_remove (gdsl_bstree_t T,
		    void* VALUE
		    );

/**
 * @brief Delete an element from a binary search tree.
 *
 * Remove from the binary search tree the first founded element E equal to 
 * VALUE, by using T's COMP_F function passed to gdsl_bstree_alloc(). If E is 
 * found, it is removed from T and E is deallocated using T's FREE_F function 
 * passed to gdsl_bstree_alloc(), then T is returned.
 *
 * @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 T must be a valid gdsl_bstree_t
 * @param T The binary search tree to remove an element from
 * @param VALUE The value used to find the element to remove
 * @return the modified binary search tree after removal of E if E was found.
 * @return NULL if no element equal to VALUE was found.
 * @see gdsl_bstree_insert()
 * @see gdsl_bstree_remove()
 */
extern gdsl_bstree_t
gdsl_bstree_delete (gdsl_bstree_t T,
		    void* VALUE
		    );
  
/******************************************************************************/
/* Search functions of binary search trees                                    */
/******************************************************************************/

/**
 * @brief Search for a particular element into a binary search tree.
 *
 * Search the first element E equal to VALUE in the binary seach tree T, by 
 * using COMP_F function to find it. If COMP_F == NULL, then the COMP_F function
 * passed to gdsl_bstree_alloc() is used.
 *
 * @note Complexity: O( h(T) ), where log2(|T|) <= h(T) <= |T|-1
 * @pre T must be a valid gdsl_bstree_t
 * @param T The binary search tree to use.
 * @param COMP_F The comparison function to use to compare T's element with
 * VALUE to find the element E (or NULL to use the default T's COMP_F)
 * @param VALUE The value that must be used by COMP_F to find the element E
 * @return the first founded element E equal to VALUE.
 * @return NULL if VALUE is not found in T.
 * @see gdsl_bstree_insert()
 * @see gdsl_bstree_remove()
 * @see gdsl_bstree_delete()
 */
extern gdsl_element_t
gdsl_bstree_search (const gdsl_bstree_t T,
		    gdsl_compare_func_t COMP_F,
		    void* VALUE
		    );

/******************************************************************************/
/* Parse functions of binary search trees                                     */
/******************************************************************************/

/**
 * @brief Parse a binary search tree in prefixed order.
 *
 * Parse all nodes of the binary search tree T in prefixed order. The MAP_F 
 * function is called on the element contained in 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 element.
 *
 * @note Complexity: O( |T| )
 * @pre T must be a valid gdsl_bstree_t & MAP_F != NULL
 * @param T The binary search tree to map.
 * @param MAP_F The map function.
 * @param USER_DATA User's datas passed to MAP_F
 * @return the first element 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_element_t
gdsl_bstree_map_prefix (const gdsl_bstree_t T,
			gdsl_map_func_t MAP_F,
			void* USER_DATA
			);

/**
 * @brief Parse a binary search tree in infixed order.
 *
 * Parse all nodes of the binary search tree T in infixed order. The MAP_F 
 * function is called on the element contained in 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 element.
 *
 * @note Complexity: O( |T| )
 * @pre T must be a valid gdsl_bstree_t & MAP_F != NULL
 * @param T The binary search tree to map.
 * @param MAP_F The map function.
 * @param USER_DATA User's datas passed to MAP_F
 * @return the first element 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_element_t
gdsl_bstree_map_infix (const gdsl_bstree_t T,
		       gdsl_map_func_t MAP_F,
		       void* USER_DATA
		       );

/**
 * @brief Parse a binary search tree in postfixed order.
 *
 * Parse all nodes of the binary search tree T in postfixed order. The MAP_F 
 * function is called on the element contained in 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 element.
 *
 * @note Complexity: O( |T| )
 * @pre T must be a valid gdsl_bstree_t & MAP_F != NULL
 * @param T The binary search tree to map.
 * @param MAP_F The map function.
 * @param USER_DATA User's datas passed to MAP_F
 * @return the first element 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_element_t
gdsl_bstree_map_postfix (const gdsl_bstree_t T,
			 gdsl_map_func_t MAP_F,
			 void* USER_DATA
			 );

/******************************************************************************/
/* Input/output functions of binary search trees                              */
/******************************************************************************/

/**
 * @brief Write the element of each node of a binary search tree to a file.
 *
 * Write the nodes elements of the 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 T must be a valid gdsl_bstree_t & WRITE_F != NULL & OUTPUT_FILE != NULL
 * @param T The binary search tree to write.
 * @param WRITE_F The write function.
 * @param OUTPUT_FILE The file where to write T's elements.
 * @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,
		   gdsl_write_func_t WRITE_F,
		   FILE* OUTPUT_FILE,
		   void* USER_DATA
		   );

/**
 * @brief Write the content of a binary search tree to a file into XML.
 *
 * Write the nodes elements of the binary search tree T to OUTPUT_FILE, into
 * XML language.
 * If WRITE_F != NULL, then use WRITE_F to write T's nodes elements to 
 * OUTPUT_FILE.
 * Additionnal USER_DATA argument could be passed to WRITE_F.
 *
 * @note Complexity: O( |T| )
 * @pre T must be a valid gdsl_bstree_t & OUTPUT_FILE != NULL
 * @param T The binary search tree to write.
 * @param WRITE_F The write function.
 * @param OUTPUT_FILE The file where to write T's elements.
 * @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,
		       gdsl_write_func_t WRITE_F,
		       FILE* OUTPUT_FILE,
		       void* USER_DATA
		       );

/**
 * @brief Dump the internal structure of a binary search tree to a file.
 *
 * Dump the structure of the binary search tree T to OUTPUT_FILE. If 
 * WRITE_F != NULL, then use WRITE_F to write T's nodes elements to 
 * OUTPUT_FILE.
 * Additionnal USER_DATA argument could be passed to WRITE_F.
 *
 * @note Complexity: O( |T| )
 * @pre T must be a valid gdsl_bstree_t & OUTPUT_FILE != NULL
 * @param T The binary search tree to write.
 * @param WRITE_F The write function.
 * @param OUTPUT_FILE The file where to write T's elements.
 * @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,
		  gdsl_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:
 */