.TH "Low level binary tree manipulation module" 3 "22 Jun 2006" "Version 1.4" "gdsl" \" -*- nroff -*-.ad l.nh.SH NAMELow level binary tree manipulation module \- .PP.SS "Typedefs".in +1c.ti -1c.RI "typedef _gdsl_bintree * \fB_gdsl_bintree_t\fP".br.RI "\fIGDSL low-level binary tree type. \fP".ti -1c.RI "typedef int(* \fB_gdsl_bintree_map_func_t\fP )(const \fB_gdsl_bintree_t\fP TREE, void *USER_DATA)".br.RI "\fIGDSL low-level binary tree map function type. \fP".ti -1c.RI "typedef void(* \fB_gdsl_bintree_write_func_t\fP )(const \fB_gdsl_bintree_t\fP TREE, FILE *OUTPUT_FILE, void *USER_DATA)".br.RI "\fIGDSL low-level binary tree write function type. \fP".in -1c.SS "Functions".in +1c.ti -1c.RI "\fB_gdsl_bintree_t\fP \fB_gdsl_bintree_alloc\fP (const \fBgdsl_element_t\fP E, const \fB_gdsl_bintree_t\fP LEFT, const \fB_gdsl_bintree_t\fP RIGHT)".br.RI "\fICreate a new low-level binary tree. \fP".ti -1c.RI "void \fB_gdsl_bintree_free\fP (\fB_gdsl_bintree_t\fP T, const \fBgdsl_free_func_t\fP FREE_F)".br.RI "\fIDestroy a low-level binary tree. \fP".ti -1c.RI "\fB_gdsl_bintree_t\fP \fB_gdsl_bintree_copy\fP (const \fB_gdsl_bintree_t\fP T, const \fBgdsl_copy_func_t\fP COPY_F)".br.RI "\fICopy a low-level binary tree. \fP".ti -1c.RI "\fBbool\fP \fB_gdsl_bintree_is_empty\fP (const \fB_gdsl_bintree_t\fP T)".br.RI "\fICheck if a low-level binary tree is empty. \fP".ti -1c.RI "\fBbool\fP \fB_gdsl_bintree_is_leaf\fP (const \fB_gdsl_bintree_t\fP T)".br.RI "\fICheck if a low-level binary tree is reduced to a leaf. \fP".ti -1c.RI "\fBbool\fP \fB_gdsl_bintree_is_root\fP (const \fB_gdsl_bintree_t\fP T)".br.RI "\fICheck if a low-level binary tree is a root. \fP".ti -1c.RI "\fBgdsl_element_t\fP \fB_gdsl_bintree_get_content\fP (const \fB_gdsl_bintree_t\fP T)".br.RI "\fIGet the root content of a low-level binary tree. \fP".ti -1c.RI "\fB_gdsl_bintree_t\fP \fB_gdsl_bintree_get_parent\fP (const \fB_gdsl_bintree_t\fP T)".br.RI "\fIGet the parent tree of a low-level binary tree. \fP".ti -1c.RI "\fB_gdsl_bintree_t\fP \fB_gdsl_bintree_get_left\fP (const \fB_gdsl_bintree_t\fP T)".br.RI "\fIGet the left sub-tree of a low-level binary tree. \fP".ti -1c.RI "\fB_gdsl_bintree_t\fP \fB_gdsl_bintree_get_right\fP (const \fB_gdsl_bintree_t\fP T)".br.RI "\fIGet the right sub-tree of a low-level binary tree. \fP".ti -1c.RI "\fB_gdsl_bintree_t\fP * \fB_gdsl_bintree_get_left_ref\fP (const \fB_gdsl_bintree_t\fP T)".br.RI "\fIGet the left sub-tree reference of a low-level binary tree. \fP".ti -1c.RI "\fB_gdsl_bintree_t\fP * \fB_gdsl_bintree_get_right_ref\fP (const \fB_gdsl_bintree_t\fP T)".br.RI "\fIGet the right sub-tree reference of a low-level binary tree. \fP".ti -1c.RI "\fBulong\fP \fB_gdsl_bintree_get_height\fP (const \fB_gdsl_bintree_t\fP T)".br.RI "\fIGet the height of a low-level binary tree. \fP".ti -1c.RI "\fBulong\fP \fB_gdsl_bintree_get_size\fP (const \fB_gdsl_bintree_t\fP T)".br.RI "\fIGet the size of a low-level binary tree. \fP".ti -1c.RI "void \fB_gdsl_bintree_set_content\fP (\fB_gdsl_bintree_t\fP T, const \fBgdsl_element_t\fP E)".br.RI "\fISet the root element of a low-level binary tree. \fP".ti -1c.RI "void \fB_gdsl_bintree_set_parent\fP (\fB_gdsl_bintree_t\fP T, const \fB_gdsl_bintree_t\fP P)".br.RI "\fISet the parent tree of a low-level binary tree. \fP".ti -1c.RI "void \fB_gdsl_bintree_set_left\fP (\fB_gdsl_bintree_t\fP T, const \fB_gdsl_bintree_t\fP L)".br.RI "\fISet left sub-tree of a low-level binary tree. \fP".ti -1c.RI "void \fB_gdsl_bintree_set_right\fP (\fB_gdsl_bintree_t\fP T, const \fB_gdsl_bintree_t\fP R)".br.RI "\fISet right sub-tree of a low-level binary tree. \fP".ti -1c.RI "\fB_gdsl_bintree_t\fP \fB_gdsl_bintree_rotate_left\fP (\fB_gdsl_bintree_t\fP *T)".br.RI "\fILeft rotate a low-level binary tree. \fP".ti -1c.RI "\fB_gdsl_bintree_t\fP \fB_gdsl_bintree_rotate_right\fP (\fB_gdsl_bintree_t\fP *T)".br.RI "\fIRight rotate a low-level binary tree. \fP".ti -1c.RI "\fB_gdsl_bintree_t\fP \fB_gdsl_bintree_rotate_left_right\fP (\fB_gdsl_bintree_t\fP *T)".br.RI "\fILeft-right rotate a low-level binary tree. \fP".ti -1c.RI "\fB_gdsl_bintree_t\fP \fB_gdsl_bintree_rotate_right_left\fP (\fB_gdsl_bintree_t\fP *T)".br.RI "\fIRight-left rotate a low-level binary tree. \fP".ti -1c.RI "\fB_gdsl_bintree_t\fP \fB_gdsl_bintree_map_prefix\fP (const \fB_gdsl_bintree_t\fP T, const \fB_gdsl_bintree_map_func_t\fP MAP_F, void *USER_DATA)".br.RI "\fIParse a low-level binary tree in prefixed order. \fP".ti -1c.RI "\fB_gdsl_bintree_t\fP \fB_gdsl_bintree_map_infix\fP (const \fB_gdsl_bintree_t\fP T, const \fB_gdsl_bintree_map_func_t\fP MAP_F, void *USER_DATA)".br.RI "\fIParse a low-level binary tree in infixed order. \fP".ti -1c.RI "\fB_gdsl_bintree_t\fP \fB_gdsl_bintree_map_postfix\fP (const \fB_gdsl_bintree_t\fP T, const \fB_gdsl_bintree_map_func_t\fP MAP_F, void *USER_DATA)".br.RI "\fIParse a low-level binary tree in postfixed order. \fP".ti -1c.RI "void \fB_gdsl_bintree_write\fP (const \fB_gdsl_bintree_t\fP T, const \fB_gdsl_bintree_write_func_t\fP WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)".br.RI "\fIWrite the content of all nodes of a low-level binary tree to a file. \fP".ti -1c.RI "void \fB_gdsl_bintree_write_xml\fP (const \fB_gdsl_bintree_t\fP T, const \fB_gdsl_bintree_write_func_t\fP WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)".br.RI "\fIWrite the content of a low-level binary tree to a file into XML. \fP".ti -1c.RI "void \fB_gdsl_bintree_dump\fP (const \fB_gdsl_bintree_t\fP T, const \fB_gdsl_bintree_write_func_t\fP WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)".br.RI "\fIDump the internal structure of a low-level binary tree to a file. \fP".in -1c.SH "Typedef Documentation".PP .SS "typedef struct _gdsl_bintree* \fB_gdsl_bintree_t\fP".PPGDSL low-level binary tree type. .PPThis type is voluntary opaque. Variables of this kind could'nt be directly used, but by the functions of this module. .PPDefinition at line 54 of file _gdsl_bintree.h..SS "typedef int(*  \fB_gdsl_bintree_map_func_t\fP)(const \fB_gdsl_bintree_t\fP TREE, void *USER_DATA)".PPGDSL low-level binary tree map function type. .PP\fBParameters:\fP.RS 4\fITREE\fP The low-level binary tree to map. .br\fIUSER_DATA\fP The user datas to pass to this function. .RE.PP\fBReturns:\fP.RS 4GDSL_MAP_STOP if the mapping must be stopped. .PPGDSL_MAP_CONT if the mapping must be continued. .RE.PP.PPDefinition at line 63 of file _gdsl_bintree.h..SS "typedef void(*  \fB_gdsl_bintree_write_func_t\fP)(const \fB_gdsl_bintree_t\fP TREE, FILE *OUTPUT_FILE, void *USER_DATA)".PPGDSL low-level binary tree write function type. .PP\fBParameters:\fP.RS 4\fITREE\fP The low-level binary tree to write. .br\fIOUTPUT_FILE\fP The file where to write TREE. .br\fIUSER_DATA\fP The user datas to pass to this function. .RE.PP.PPDefinition at line 73 of file _gdsl_bintree.h..SH "Function Documentation".PP .SS "\fB_gdsl_bintree_t\fP _gdsl_bintree_alloc (const \fBgdsl_element_t\fP E, const \fB_gdsl_bintree_t\fP LEFT, const \fB_gdsl_bintree_t\fP RIGHT)".PPCreate a new low-level binary tree. .PPAllocate 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)..PP\fBNote:\fP.RS 4Complexity: O( 1 ) .RE.PP\fBPrecondition:\fP.RS 4nothing. .RE.PP\fBParameters:\fP.RS 4\fIE\fP The root content of the new low-level binary tree to create. .br\fILEFT\fP The left sub-tree of the new low-level binary tree to create. .br\fIRIGHT\fP The right sub-tree of the new low-level binary tree to create. .RE.PP\fBReturns:\fP.RS 4the newly allocated low-level binary tree in case of success. .PPNULL in case of insufficient memory. .RE.PP\fBSee also:\fP.RS 4\fB_gdsl_bintree_free()\fP .RE.PP.SS "void _gdsl_bintree_free (\fB_gdsl_bintree_t\fP T, const \fBgdsl_free_func_t\fP FREE_F)".PPDestroy a low-level binary tree. .PPFlush 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..PP\fBNote:\fP.RS 4Complexity: O( |T| ) .RE.PP\fBPrecondition:\fP.RS 4nothing. .RE.PP\fBParameters:\fP.RS 4\fIT\fP The low-level binary tree to destroy. .br\fIFREE_F\fP The function used to deallocate T's nodes contents. .RE.PP\fBSee also:\fP.RS 4\fB_gdsl_bintree_alloc()\fP .RE.PP.SS "\fB_gdsl_bintree_t\fP _gdsl_bintree_copy (const \fB_gdsl_bintree_t\fP T, const \fBgdsl_copy_func_t\fP COPY_F)".PPCopy a low-level binary tree. .PPCreate and return a copy of the low-level binary tree T using COPY_F on each T's element to copy them..PP\fBNote:\fP.RS 4Complexity: O( |T| ) .RE.PP\fBPrecondition:\fP.RS 4COPY_F != NULL .RE.PP\fBParameters:\fP.RS 4\fIT\fP The low-level binary tree to copy. .br\fICOPY_F\fP The function used to copy T's nodes contents. .RE.PP\fBReturns:\fP.RS 4a copy of T in case of success. .PPNULL if _gdsl_bintree_is_empty (T) == TRUE or in case of insufficient memory. .RE.PP\fBSee also:\fP.RS 4\fB_gdsl_bintree_alloc()\fP .PP\fB_gdsl_bintree_free()\fP .PP\fB_gdsl_bintree_is_empty()\fP .RE.PP.SS "\fBbool\fP _gdsl_bintree_is_empty (const \fB_gdsl_bintree_t\fP T)".PPCheck if a low-level binary tree is empty. .PP\fBNote:\fP.RS 4Complexity: O( 1 ) .RE.PP\fBPrecondition:\fP.RS 4nothing. .RE.PP\fBParameters:\fP.RS 4\fIT\fP The low-level binary tree to check. .RE.PP\fBReturns:\fP.RS 4TRUE if the low-level binary tree T is empty. .PPFALSE if the low-level binary tree T is not empty. .RE.PP\fBSee also:\fP.RS 4\fB_gdsl_bintree_is_leaf()\fP .PP\fB_gdsl_bintree_is_root()\fP .RE.PP.SS "\fBbool\fP _gdsl_bintree_is_leaf (const \fB_gdsl_bintree_t\fP T)".PPCheck if a low-level binary tree is reduced to a leaf. .PP\fBNote:\fP.RS 4Complexity: O( 1 ) .RE.PP\fBPrecondition:\fP.RS 4T must be a non-empty _gdsl_bintree_t. .RE.PP\fBParameters:\fP.RS 4\fIT\fP The low-level binary tree to check. .RE.PP\fBReturns:\fP.RS 4TRUE if the low-level binary tree T is a leaf. .PPFALSE if the low-level binary tree T is not a leaf. .RE.PP\fBSee also:\fP.RS 4\fB_gdsl_bintree_is_empty()\fP .PP\fB_gdsl_bintree_is_root()\fP .RE.PP.SS "\fBbool\fP _gdsl_bintree_is_root (const \fB_gdsl_bintree_t\fP T)".PPCheck if a low-level binary tree is a root. .PP\fBNote:\fP.RS 4Complexity: O( 1 ) .RE.PP\fBPrecondition:\fP.RS 4T must be a non-empty _gdsl_bintree_t. .RE.PP\fBParameters:\fP.RS 4\fIT\fP The low-level binary tree to check. .RE.PP\fBReturns:\fP.RS 4TRUE if the low-level binary tree T is a root. .PPFALSE if the low-level binary tree T is not a root. .RE.PP\fBSee also:\fP.RS 4\fB_gdsl_bintree_is_empty()\fP .PP\fB_gdsl_bintree_is_leaf()\fP .RE.PP.SS "\fBgdsl_element_t\fP _gdsl_bintree_get_content (const \fB_gdsl_bintree_t\fP T)".PPGet the root content of a low-level binary tree. .PP\fBNote:\fP.RS 4Complexity: O( 1 ) .RE.PP\fBPrecondition:\fP.RS 4T must be a non-empty _gdsl_bintree_t. .RE.PP\fBParameters:\fP.RS 4\fIT\fP The low-level binary tree to use. .RE.PP\fBReturns:\fP.RS 4the root's content of the low-level binary tree T. .RE.PP\fBSee also:\fP.RS 4\fB_gdsl_bintree_set_content()\fP .RE.PP.SS "\fB_gdsl_bintree_t\fP _gdsl_bintree_get_parent (const \fB_gdsl_bintree_t\fP T)".PPGet the parent tree of a low-level binary tree. .PP\fBNote:\fP.RS 4Complexity: O( 1 ) .RE.PP\fBPrecondition:\fP.RS 4T must be a non-empty _gdsl_bintree_t. .RE.PP\fBParameters:\fP.RS 4\fIT\fP The low-level binary tree to use. .RE.PP\fBReturns:\fP.RS 4the parent of the low-level binary tree T if T isn't a root. .PPNULL if the low-level binary tree T is a root (ie. T has no parent). .RE.PP\fBSee also:\fP.RS 4\fB_gdsl_bintree_is_root()\fP .PP\fB_gdsl_bintree_set_parent()\fP .RE.PP.SS "\fB_gdsl_bintree_t\fP _gdsl_bintree_get_left (const \fB_gdsl_bintree_t\fP T)".PPGet the left sub-tree of a low-level binary tree. .PPReturn the left subtree of the low-level binary tree T (noted l(T))..PP\fBNote:\fP.RS 4Complexity: O( 1 ) .RE.PP\fBPrecondition:\fP.RS 4T must be a non-empty _gdsl_bintree_t. .RE.PP\fBParameters:\fP.RS 4\fIT\fP The low-level binary tree to use. .RE.PP\fBReturns:\fP.RS 4the left sub-tree of the low-level binary tree T if T has a left sub-tree. .PPNULL if the low-level binary tree T has no left sub-tree. .RE.PP\fBSee also:\fP.RS 4\fB_gdsl_bintree_get_right()\fP .PP\fB_gdsl_bintree_set_left()\fP .PP\fB_gdsl_bintree_set_right()\fP .RE.PP.SS "\fB_gdsl_bintree_t\fP _gdsl_bintree_get_right (const \fB_gdsl_bintree_t\fP T)".PPGet the right sub-tree of a low-level binary tree. .PPReturn the right subtree of the low-level binary tree T (noted r(T))..PP\fBNote:\fP.RS 4Complexity: O( 1 ) .RE.PP\fBPrecondition:\fP.RS 4T must be a non-empty _gdsl_bintree_t .RE.PP\fBParameters:\fP.RS 4\fIT\fP The low-level binary tree to use. .RE.PP\fBReturns:\fP.RS 4the right sub-tree of the low-level binary tree T if T has a right sub-tree. .PPNULL if the low-level binary tree T has no right sub-tree. .RE.PP\fBSee also:\fP.RS 4\fB_gdsl_bintree_get_left()\fP .PP\fB_gdsl_bintree_set_left()\fP .PP\fB_gdsl_bintree_set_right()\fP .RE.PP.SS "\fB_gdsl_bintree_t\fP* _gdsl_bintree_get_left_ref (const \fB_gdsl_bintree_t\fP T)".PPGet the left sub-tree reference of a low-level binary tree. .PP\fBNote:\fP.RS 4Complexity: O( 1 ) .RE.PP\fBPrecondition:\fP.RS 4T must be a non-empty _gdsl_bintree_t. .RE.PP\fBParameters:\fP.RS 4\fIT\fP The low-level binary tree to use. .RE.PP\fBReturns:\fP.RS 4the left sub-tree reference of the low-level binary tree T. .RE.PP\fBSee also:\fP.RS 4\fB_gdsl_bintree_get_right_ref()\fP .RE.PP.SS "\fB_gdsl_bintree_t\fP* _gdsl_bintree_get_right_ref (const \fB_gdsl_bintree_t\fP T)".PPGet the right sub-tree reference of a low-level binary tree. .PP\fBNote:\fP.RS 4Complexity: O( 1 ) .RE.PP\fBPrecondition:\fP.RS 4