gdsl  1.6
Low level binary tree manipulation module

Typedefs

typedef struct _gdsl_bintree * _gdsl_bintree_t
 GDSL low-level binary tree type.
typedef int(* _gdsl_bintree_map_func_t )(const _gdsl_bintree_t TREE, void *USER_DATA)
 GDSL low-level binary tree map function type.
typedef void(* _gdsl_bintree_write_func_t )(const _gdsl_bintree_t TREE, FILE *OUTPUT_FILE, void *USER_DATA)
 GDSL low-level binary tree write function type.

Functions

_gdsl_bintree_t _gdsl_bintree_alloc (const gdsl_element_t E, const _gdsl_bintree_t LEFT, const _gdsl_bintree_t RIGHT)
 Create a new low-level binary tree.
void _gdsl_bintree_free (_gdsl_bintree_t T, const gdsl_free_func_t FREE_F)
 Destroy a low-level binary tree.
_gdsl_bintree_t _gdsl_bintree_copy (const _gdsl_bintree_t T, const gdsl_copy_func_t COPY_F)
 Copy a low-level binary tree.
bool _gdsl_bintree_is_empty (const _gdsl_bintree_t T)
 Check if a low-level binary tree is empty.
bool _gdsl_bintree_is_leaf (const _gdsl_bintree_t T)
 Check if a low-level binary tree is reduced to a leaf.
bool _gdsl_bintree_is_root (const _gdsl_bintree_t T)
 Check if a low-level binary tree is a root.
gdsl_element_t _gdsl_bintree_get_content (const _gdsl_bintree_t T)
 Get the root content of a low-level binary tree.
_gdsl_bintree_t _gdsl_bintree_get_parent (const _gdsl_bintree_t T)
 Get the parent tree of a low-level binary tree.
_gdsl_bintree_t _gdsl_bintree_get_left (const _gdsl_bintree_t T)
 Get the left sub-tree of a low-level binary tree.
_gdsl_bintree_t _gdsl_bintree_get_right (const _gdsl_bintree_t T)
 Get the right sub-tree of a low-level binary tree.
_gdsl_bintree_t_gdsl_bintree_get_left_ref (const _gdsl_bintree_t T)
 Get the left sub-tree reference of a low-level binary tree.
_gdsl_bintree_t_gdsl_bintree_get_right_ref (const _gdsl_bintree_t T)
 Get the right sub-tree reference of a low-level binary tree.
ulong _gdsl_bintree_get_height (const _gdsl_bintree_t T)
 Get the height of a low-level binary tree.
ulong _gdsl_bintree_get_size (const _gdsl_bintree_t T)
 Get the size of a low-level binary tree.
void _gdsl_bintree_set_content (_gdsl_bintree_t T, const gdsl_element_t E)
 Set the root element of a low-level binary tree.
void _gdsl_bintree_set_parent (_gdsl_bintree_t T, const _gdsl_bintree_t P)
 Set the parent tree of a low-level binary tree.
void _gdsl_bintree_set_left (_gdsl_bintree_t T, const _gdsl_bintree_t L)
 Set left sub-tree of a low-level binary tree.
void _gdsl_bintree_set_right (_gdsl_bintree_t T, const _gdsl_bintree_t R)
 Set right sub-tree of a low-level binary tree.
_gdsl_bintree_t _gdsl_bintree_rotate_left (_gdsl_bintree_t *T)
 Left rotate a low-level binary tree.
_gdsl_bintree_t _gdsl_bintree_rotate_right (_gdsl_bintree_t *T)
 Right rotate a low-level binary tree.
_gdsl_bintree_t _gdsl_bintree_rotate_left_right (_gdsl_bintree_t *T)
 Left-right rotate a low-level binary tree.
_gdsl_bintree_t _gdsl_bintree_rotate_right_left (_gdsl_bintree_t *T)
 Right-left rotate a low-level binary tree.
_gdsl_bintree_t _gdsl_bintree_map_prefix (const _gdsl_bintree_t T, const _gdsl_bintree_map_func_t MAP_F, void *USER_DATA)
 Parse a low-level binary tree in prefixed order.
_gdsl_bintree_t _gdsl_bintree_map_infix (const _gdsl_bintree_t T, const _gdsl_bintree_map_func_t MAP_F, void *USER_DATA)
 Parse a low-level binary tree in infixed order.
_gdsl_bintree_t _gdsl_bintree_map_postfix (const _gdsl_bintree_t T, const _gdsl_bintree_map_func_t MAP_F, void *USER_DATA)
 Parse a low-level binary tree in postfixed order.
void _gdsl_bintree_write (const _gdsl_bintree_t T, const _gdsl_bintree_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Write the content of all nodes of a low-level binary tree to a file.
void _gdsl_bintree_write_xml (const _gdsl_bintree_t T, const _gdsl_bintree_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Write the content of a low-level binary tree to a file into XML.
void _gdsl_bintree_dump (const _gdsl_bintree_t T, const _gdsl_bintree_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Dump the internal structure of a low-level binary tree to a file.

Typedef Documentation

typedef struct _gdsl_bintree* _gdsl_bintree_t

GDSL low-level binary tree type.

This type is voluntary opaque. Variables of this kind could'nt be directly used, but by the functions of this module.

Definition at line 54 of file _gdsl_bintree.h.

typedef int(* _gdsl_bintree_map_func_t)(const _gdsl_bintree_t TREE, void *USER_DATA)

GDSL low-level binary tree map function type.

Parameters:
TREEThe low-level binary tree to map.
USER_DATAThe user datas to pass to this function.
Returns:
GDSL_MAP_STOP if the mapping must be stopped.
GDSL_MAP_CONT if the mapping must be continued.

Definition at line 63 of file _gdsl_bintree.h.

typedef void(* _gdsl_bintree_write_func_t)(const _gdsl_bintree_t TREE, FILE *OUTPUT_FILE, void *USER_DATA)

GDSL low-level binary tree write function type.

Parameters:
TREEThe low-level binary tree to write.
OUTPUT_FILEThe file where to write TREE.
USER_DATAThe user datas to pass to this function.

Definition at line 73 of file _gdsl_bintree.h.


Function Documentation

Create a new low-level binary tree.

Allocate a new low-level binary tree data structure. Its root content is set to E and its left son (resp. right) is set to LEFT (resp. RIGHT).

Note:
Complexity: O( 1 )
Precondition:
nothing.
Parameters:
EThe root content of the new low-level binary tree to create.
LEFTThe left sub-tree of the new low-level binary tree to create.
RIGHTThe right sub-tree of the new low-level binary tree to create.
Returns:
the newly allocated low-level binary tree in case of success.
NULL in case of insufficient memory.
See also:
_gdsl_bintree_free()
void _gdsl_bintree_free ( _gdsl_bintree_t  T,
const gdsl_free_func_t  FREE_F 
)

Destroy a low-level binary tree.

Flush and destroy the low-level binary 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| )
Precondition:
nothing.
Parameters:
TThe low-level binary tree to destroy.
FREE_FThe function used to deallocate T's nodes contents.
See also:
_gdsl_bintree_alloc()

Copy a low-level binary tree.

Create and return a copy of the low-level binary tree T using COPY_F on each T's element to copy them.

Note:
Complexity: O( |T| )
Precondition:
COPY_F != NULL
Parameters:
TThe low-level binary tree to copy.
COPY_FThe function used to copy T's nodes contents.
Returns:
a copy of T in case of success.
NULL if _gdsl_bintree_is_empty (T) == TRUE or in case of insufficient memory.
See also:
_gdsl_bintree_alloc()
_gdsl_bintree_free()
_gdsl_bintree_is_empty()

Check if a low-level binary tree is empty.

Note:
Complexity: O( 1 )
Precondition:
nothing.
Parameters:
TThe low-level binary tree to check.
Returns:
TRUE if the low-level binary tree T is empty.
FALSE if the low-level binary tree T is not empty.
See also:
_gdsl_bintree_is_leaf()
_gdsl_bintree_is_root()

Check if a low-level binary tree is reduced to a leaf.

Note:
Complexity: O( 1 )
Precondition:
T must be a non-empty _gdsl_bintree_t.
Parameters:
TThe low-level binary tree to check.
Returns:
TRUE if the low-level binary tree T is a leaf.
FALSE if the low-level binary tree T is not a leaf.
See also:
_gdsl_bintree_is_empty()
_gdsl_bintree_is_root()

Check if a low-level binary tree is a root.

Note:
Complexity: O( 1 )
Precondition:
T must be a non-empty _gdsl_bintree_t.
Parameters:
TThe low-level binary tree to check.
Returns:
TRUE if the low-level binary tree T is a root.
FALSE if the low-level binary tree T is not a root.
See also:
_gdsl_bintree_is_empty()
_gdsl_bintree_is_leaf()

Get the root content of a low-level binary tree.

Note:
Complexity: O( 1 )
Precondition:
T must be a non-empty _gdsl_bintree_t.
Parameters:
TThe low-level binary tree to use.
Returns:
the root's content of the low-level binary tree T.
See also:
_gdsl_bintree_set_content()

Get the parent tree of a low-level binary tree.

Note:
Complexity: O( 1 )
Precondition:
T must be a non-empty _gdsl_bintree_t.
Parameters:
TThe low-level binary tree to use.
Returns:
the parent of the low-level binary tree T if T isn't a root.
NULL if the low-level binary tree T is a root (ie. T has no parent).
See also:
_gdsl_bintree_is_root()
_gdsl_bintree_set_parent()

Get the left sub-tree of a low-level binary tree.

Return the left subtree of the low-level binary tree T (noted l(T)).

Note:
Complexity: O( 1 )
Precondition:
T must be a non-empty _gdsl_bintree_t.
Parameters:
TThe low-level binary tree to use.
Returns:
the left sub-tree of the low-level binary tree T if T has a left sub-tree.
NULL if the low-level binary tree T has no left sub-tree.
See also:
_gdsl_bintree_get_right()
_gdsl_bintree_set_left()
_gdsl_bintree_set_right()

Get the right sub-tree of a low-level binary tree.

Return the right subtree of the low-level binary tree T (noted r(T)).

Note:
Complexity: O( 1 )
Precondition:
T must be a non-empty _gdsl_bintree_t
Parameters:
TThe low-level binary tree to use.
Returns:
the right sub-tree of the low-level binary tree T if T has a right sub-tree.
NULL if the low-level binary tree T has no right sub-tree.
See also:
_gdsl_bintree_get_left()
_gdsl_bintree_set_left()
_gdsl_bintree_set_right()

Get the left sub-tree reference of a low-level binary tree.

Note:
Complexity: O( 1 )
Precondition:
T must be a non-empty _gdsl_bintree_t.
Parameters:
TThe low-level binary tree to use.
Returns:
the left sub-tree reference of the low-level binary tree T.
See also:
_gdsl_bintree_get_right_ref()

Get the right sub-tree reference of a low-level binary tree.

Note:
Complexity: O( 1 )
Precondition:
T must be a non-empty _gdsl_bintree_t.
Parameters:
TThe low-level binary tree to use.
Returns:
the right sub-tree reference of the low-level binary tree T.
See also:
_gdsl_bintree_get_left_ref()

Get the height of a low-level binary tree.

Compute the height of the low-level binary tree T (noted h(T)).

Note:
Complexity: O( |T| )
Precondition:
nothing.
Parameters:
TThe low-level binary tree to use.
Returns:
the height of T.
See also:
_gdsl_bintree_get_size()

Get the size of a low-level binary tree.

Note:
Complexity: O( |T| )
Precondition:
nothing.
Parameters:
TThe low-level binary tree to use.
Returns:
the number of elements of T (noted |T|).
See also:
_gdsl_bintree_get_height()

Set the root element of a low-level binary tree.

Modify the root element of the low-level binary tree T to E.

Note:
Complexity: O( 1 )
Precondition:
T must be a non-empty _gdsl_bintree_t.
Parameters:
TThe low-level binary tree to modify.
EThe new T's root content.
See also:
_gdsl_bintree_get_content

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 )
Precondition:
T must be a non-empty _gdsl_bintree_t.
Parameters:
TThe low-level binary tree to modify.
PThe new T's parent.
See also:
_gdsl_bintree_get_parent()

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 )
Precondition:
T must be a non-empty _gdsl_bintree_t.
Parameters:
TThe low-level binary tree to modify.
LThe new T's left sub-tree.
See also:
_gdsl_bintree_set_right()
_gdsl_bintree_get_left()
_gdsl_bintree_get_right()

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 )
Precondition:
T must be a non-empty _gdsl_bintree_t.
Parameters:
TThe low-level binary tree to modify.
RThe new T's right sub-tree.
See also:
_gdsl_bintree_set_left()
_gdsl_bintree_get_left()
_gdsl_bintree_get_right()

Left rotate a low-level binary tree.

Do a left rotation of the low-level binary tree T.

Note:
Complexity: O( 1 )
Precondition:
T & r(T) must be non-empty _gdsl_bintree_t.
Parameters:
TThe low-level binary tree to rotate.
Returns:
the modified T left-rotated.
See also:
_gdsl_bintree_rotate_right()
_gdsl_bintree_rotate_left_right()
_gdsl_bintree_rotate_right_left()

Right rotate a low-level binary tree.

Do a right rotation of the low-level binary tree T.

Note:
Complexity: O( 1 )
Precondition:
T & l(T) must be non-empty _gdsl_bintree_t.
Parameters:
TThe low-level binary tree to rotate.
Returns:
the modified T right-rotated.
See also:
_gdsl_bintree_rotate_left()
_gdsl_bintree_rotate_left_right()
_gdsl_bintree_rotate_right_left()

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 )
Precondition:
T & l(T) & r(l(T)) must be non-empty _gdsl_bintree_t.
Parameters:
TThe low-level binary tree to rotate.
Returns:
the modified T left-right-rotated.
See also:
_gdsl_bintree_rotate_left()
_gdsl_bintree_rotate_right()
_gdsl_bintree_rotate_right_left()

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 )
Precondition:
T & r(T) & l(r(T)) must be non-empty _gdsl_bintree_t.
Parameters:
TThe low-level binary tree to rotate.
Returns:
the modified T right-left-rotated.
See also:
_gdsl_bintree_rotate_left()
_gdsl_bintree_rotate_right()
_gdsl_bintree_rotate_left_right()
_gdsl_bintree_t _gdsl_bintree_map_prefix ( const _gdsl_bintree_t  T,
const _gdsl_bintree_map_func_t  MAP_F,
void *  USER_DATA 
)

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| )
Precondition:
MAP_F != NULL
Parameters:
TThe low-level binary tree to map.
MAP_FThe map function.
USER_DATAUser's datas.
Returns:
the first node for which MAP_F returns GDSL_MAP_STOP.
NULL when the parsing is done.
See also:
_gdsl_bintree_map_infix()
_gdsl_bintree_map_postfix()
_gdsl_bintree_t _gdsl_bintree_map_infix ( const _gdsl_bintree_t  T,
const _gdsl_bintree_map_func_t  MAP_F,
void *  USER_DATA 
)

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| )
Precondition:
MAP_F != NULL
Parameters:
TThe low-level binary tree to map.
MAP_FThe map function.
USER_DATAUser's datas.
Returns:
the first node for which MAP_F returns GDSL_MAP_STOP.
NULL when the parsing is done.
See also:
_gdsl_bintree_map_prefix()
_gdsl_bintree_map_postfix()
_gdsl_bintree_t _gdsl_bintree_map_postfix ( const _gdsl_bintree_t  T,
const _gdsl_bintree_map_func_t  MAP_F,
void *  USER_DATA 
)

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| )
Precondition:
MAP_F != NULL
Parameters:
TThe low-level binary tree to map.
MAP_FThe map function.
USER_DATAUser's datas.
Returns:
the first node for which MAP_F returns GDSL_MAP_STOP.
NULL when the parsing is done.
See also:
_gdsl_bintree_map_prefix()
_gdsl_bintree_map_infix()
void _gdsl_bintree_write ( const _gdsl_bintree_t  T,
const _gdsl_bintree_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA 
)

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| )
Precondition:
WRITE_F != NULL & OUTPUT_FILE != NULL
Parameters:
TThe low-level binary tree to write.
WRITE_FThe write function.
OUTPUT_FILEThe file where to write T's nodes.
USER_DATAUser's datas passed to WRITE_F.
See also:
_gdsl_bintree_write_xml()
_gdsl_bintree_dump()
void _gdsl_bintree_write_xml ( const _gdsl_bintree_t  T,
const _gdsl_bintree_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA 
)

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| )
Precondition:
OUTPUT_FILE != NULL
Parameters:
TThe low-level binary tree to write.
WRITE_FThe write function.
OUTPUT_FILEThe file where to write T's nodes.
USER_DATAUser's datas passed to WRITE_F.
See also:
_gdsl_bintree_write()
_gdsl_bintree_dump()
void _gdsl_bintree_dump ( const _gdsl_bintree_t  T,
const _gdsl_bintree_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA 
)

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| )
Precondition:
OUTPUT_FILE != NULL
Parameters:
TThe low-level binary tree to dump.
WRITE_FThe write function.
OUTPUT_FILEThe file where to write T's nodes.
USER_DATAUser's datas passed to WRITE_F.
See also:
_gdsl_bintree_write()
_gdsl_bintree_write_xml()