_gdsl_bintree.h

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

 *
 * Modify the root element of the low-level binary tree T to E.
 * 
 * @note Complexity: O( 1 )
 * @pre T must be a non-empty _gdsl_bintree_t.
 * @param T The low-level binary tree to modify.
 * @param E The new T's root content.
 * @see _gdsl_bintree_get_content
 */
extern void
_gdsl_bintree_set_content (_gdsl_bintree_t T,
			   const gdsl_element_t E
			   );

/**
 * @brief Set the parent tree of a low-level binary tree.
 *
 * Modify the parent of the low-level binary tree T to P.
 * 
 * @note Complexity: O( 1 )
 * @pre T must be a non-empty _gdsl_bintree_t.
 * @param T The low-level binary tree to modify.
 * @param P The new T's parent.
 * @see _gdsl_bintree_get_parent()
 */
extern void
_gdsl_bintree_set_parent (_gdsl_bintree_t T,
			  const _gdsl_bintree_t P
			  );

/**
 * @brief Set left sub-tree of a low-level binary tree.
 *
 * Modify the left sub-tree of the low-level binary tree T to L.
 * 
 * @note Complexity: O( 1 )
 * @pre T must be a non-empty _gdsl_bintree_t.
 * @param T The low-level binary tree to modify.
 * @param L The new T's left sub-tree.
 * @see _gdsl_bintree_set_right()
 * @see _gdsl_bintree_get_left()
 * @see _gdsl_bintree_get_right()
 */
extern void
_gdsl_bintree_set_left (_gdsl_bintree_t T,
			const _gdsl_bintree_t L
			);
  
/**
 * @brief Set right sub-tree of a low-level binary tree.
 *
 * Modify the right sub-tree of the low-level binary tree T to R.
 * 
 * @note Complexity: O( 1 )
 * @pre T must be a non-empty _gdsl_bintree_t.
 * @param T The low-level binary tree to modify.
 * @param R The new T's right sub-tree.
 * @see _gdsl_bintree_set_left()
 * @see _gdsl_bintree_get_left()
 * @see _gdsl_bintree_get_right()
 */
extern void
_gdsl_bintree_set_right (_gdsl_bintree_t T,
			 const _gdsl_bintree_t R
			 );

/******************************************************************************/
/* Rotation functions of low-level binary trees                               */
/******************************************************************************/

/**
 * @brief Left rotate a low-level binary tree.
 *
 * Do a left rotation of the low-level binary tree T.
 * 
 * @note Complexity: O( 1 )
 * @pre T & r(T) must be non-empty _gdsl_bintree_t.
 * @param T The low-level binary tree to rotate.
 * @return the modified T left-rotated.
 * @see _gdsl_bintree_rotate_right()
 * @see _gdsl_bintree_rotate_left_right()
 * @see _gdsl_bintree_rotate_right_left()
 */
extern _gdsl_bintree_t
_gdsl_bintree_rotate_left (_gdsl_bintree_t* T
			   );

/**
 * @brief Right rotate a low-level binary tree.
 *
 * Do a right rotation of the low-level binary tree T.
 *
 * @note Complexity: O( 1 )
 * @pre T & l(T) must be non-empty _gdsl_bintree_t.
 * @param T The low-level binary tree to rotate.
 * @return the modified T right-rotated.
 * @see _gdsl_bintree_rotate_left()
 * @see _gdsl_bintree_rotate_left_right()
 * @see _gdsl_bintree_rotate_right_left()
 */
extern _gdsl_bintree_t
_gdsl_bintree_rotate_right (_gdsl_bintree_t* T
			    );

/**
 * @brief Left-right rotate a low-level binary tree.
 *
 * Do a double left-right rotation of the low-level binary tree T.
 * 
 * @note Complexity: O( 1 )
 * @pre T & l(T) & r(l(T)) must be non-empty _gdsl_bintree_t.
 * @param T The low-level binary tree to rotate.
 * @return the modified T left-right-rotated.
 * @see _gdsl_bintree_rotate_left()
 * @see _gdsl_bintree_rotate_right()
 * @see _gdsl_bintree_rotate_right_left()
 */
extern _gdsl_bintree_t
_gdsl_bintree_rotate_left_right (_gdsl_bintree_t* T
				 );

/**
 * @brief Right-left rotate a low-level binary tree.
 *
 * Do a double right-left rotation of the low-level binary tree T.
 * 
 * @note Complexity: O( 1 )
 * @pre T & r(T) & l(r(T)) must be non-empty _gdsl_bintree_t.
 * @param T The low-level binary tree to rotate.
 * @return the modified T right-left-rotated.
 * @see _gdsl_bintree_rotate_left()
 * @see _gdsl_bintree_rotate_right()
 * @see _gdsl_bintree_rotate_left_right()
 */
extern _gdsl_bintree_t
_gdsl_bintree_rotate_right_left (_gdsl_bintree_t* T
				 );

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

/**
 * @brief Parse a low-level binary tree in prefixed order.
 *
 * Parse all nodes of the low-level binary 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_bintree_map_prefix() stops and returns its
 * last examinated node.
 *
 * @note Complexity: O( |T| )
 * @pre MAP_F != NULL
 * @param T The low-level binary tree to map.
 * @param MAP_F The map function.
 * @param USER_DATA User's datas.
 * @return the first node for which MAP_F returns GDSL_MAP_STOP.
 * @return NULL when the parsing is done.
 * @see _gdsl_bintree_map_infix()
 * @see _gdsl_bintree_map_postfix()
 */
extern _gdsl_bintree_t
_gdsl_bintree_map_prefix (const _gdsl_bintree_t T,
			  const _gdsl_bintree_map_func_t MAP_F,
			  void* USER_DATA
			  );

/**
 * @brief Parse a low-level binary tree in infixed order.
 *
 * Parse all nodes of the low-level binary 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_bintree_map_infix() stops and returns its 
 * last examinated node.
 *
 * @note Complexity: O( |T| )
 * @pre MAP_F != NULL
 * @param T The low-level binary tree to map.
 * @param MAP_F The map function.
 * @param USER_DATA User's datas.
 * @return the first node for which MAP_F returns GDSL_MAP_STOP.
 * @return NULL when the parsing is done.
 * @see _gdsl_bintree_map_prefix()
 * @see _gdsl_bintree_map_postfix()
 */
extern _gdsl_bintree_t
_gdsl_bintree_map_infix (const _gdsl_bintree_t T,
			 const _gdsl_bintree_map_func_t MAP_F,
			 void* USER_DATA
			 );

/**
 * @brief Parse a low-level binary tree in postfixed order.
 *
 * Parse all nodes of the low-level binary 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_bintree_map_postfix() stops and returns its
 * last examinated node.
 *
 * @note Complexity: O( |T| )
 * @pre MAP_F != NULL
 * @param T The low-level binary tree to map.
 * @param MAP_F The map function.
 * @param USER_DATA User's datas.
 * @return the first node for which MAP_F returns GDSL_MAP_STOP.
 * @return NULL when the parsing is done.
 * @see _gdsl_bintree_map_prefix()
 * @see _gdsl_bintree_map_infix()
 */
extern _gdsl_bintree_t
_gdsl_bintree_map_postfix (const _gdsl_bintree_t T,
			   const _gdsl_bintree_map_func_t MAP_F,
			   void* USER_DATA
			   );

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

/**
 * @brief Write the content of all nodes of a low-level binary tree to a file.
 *
 * Write the nodes contents of the low-level binary 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 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_bintree_write_xml()
 * @see _gdsl_bintree_dump()
 */
extern void
_gdsl_bintree_write (const _gdsl_bintree_t T,
		     const _gdsl_bintree_write_func_t WRITE_F,
		     FILE* OUTPUT_FILE,
		     void* USER_DATA
		     );

/**
 * @brief Write the content of a low-level binary tree to a file into XML.
 *
 * Write the nodes contents of the low-level binary tree T to OUTPUT_FILE, 
 * into XML language. If WRITE_F != NULL, then uses 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 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_bintree_write()
 * @see _gdsl_bintree_dump()
 */
extern void
_gdsl_bintree_write_xml (const _gdsl_bintree_t T,
			 const _gdsl_bintree_write_func_t WRITE_F,
			 FILE* OUTPUT_FILE,
			 void* USER_DATA
			 );

/**
 * @brief Dump the internal structure of a low-level binary tree to a file.
 *
 * Dump the structure of the low-level binary tree T to OUTPUT_FILE. 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 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_bintree_write()
 * @see _gdsl_bintree_write_xml()
 */
extern void
_gdsl_bintree_dump (const _gdsl_bintree_t T,
		    const _gdsl_bintree_write_func_t WRITE_F,
		    FILE* OUTPUT_FILE,
		    void* USER_DATA
		    );

/*
 * @}
 */


#ifdef __cplusplus
}
#endif /* __cplusplus */


#endif /* __GDSL_BINTREE_H_ */


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