.TH "Low-level binary search tree manipulation module" 3 "22 Jun 2006" "Version 1.4" "gdsl" \" -*- nroff -*-.ad l.nh.SH NAMELow-level binary search tree manipulation module \- .PP.SS "Typedefs".in +1c.ti -1c.RI "typedef \fB_gdsl_bintree_t\fP \fB_gdsl_bstree_t\fP".br.RI "\fIGDSL low-level binary search tree type. \fP".ti -1c.RI "typedef int(* \fB_gdsl_bstree_map_func_t\fP )(\fB_gdsl_bstree_t\fP TREE, void *USER_DATA)".br.RI "\fIGDSL low-level binary search tree map function type. \fP".ti -1c.RI "typedef void(* \fB_gdsl_bstree_write_func_t\fP )(\fB_gdsl_bstree_t\fP TREE, FILE *OUTPUT_FILE, void *USER_DATA)".br.RI "\fIGDSL low-level binary search tree write function type. \fP".in -1c.SS "Functions".in +1c.ti -1c.RI "\fB_gdsl_bstree_t\fP \fB_gdsl_bstree_alloc\fP (const \fBgdsl_element_t\fP E)".br.RI "\fICreate a new low-level binary search tree. \fP".ti -1c.RI "void \fB_gdsl_bstree_free\fP (\fB_gdsl_bstree_t\fP T, const \fBgdsl_free_func_t\fP FREE_F)".br.RI "\fIDestroy a low-level binary search tree. \fP".ti -1c.RI "\fB_gdsl_bstree_t\fP \fB_gdsl_bstree_copy\fP (const \fB_gdsl_bstree_t\fP T, const \fBgdsl_copy_func_t\fP COPY_F)".br.RI "\fICopy a low-level binary search tree. \fP".ti -1c.RI "\fBbool\fP \fB_gdsl_bstree_is_empty\fP (const \fB_gdsl_bstree_t\fP T)".br.RI "\fICheck if a low-level binary search tree is empty. \fP".ti -1c.RI "\fBbool\fP \fB_gdsl_bstree_is_leaf\fP (const \fB_gdsl_bstree_t\fP T)".br.RI "\fICheck if a low-level binary search tree is reduced to a leaf. \fP".ti -1c.RI "\fBgdsl_element_t\fP \fB_gdsl_bstree_get_content\fP (const \fB_gdsl_bstree_t\fP T)".br.RI "\fIGet the root content of a low-level binary search tree. \fP".ti -1c.RI "\fBbool\fP \fB_gdsl_bstree_is_root\fP (const \fB_gdsl_bstree_t\fP T)".br.RI "\fICheck if a low-level binary search tree is a root. \fP".ti -1c.RI "\fB_gdsl_bstree_t\fP \fB_gdsl_bstree_get_parent\fP (const \fB_gdsl_bstree_t\fP T)".br.RI "\fIGet the parent tree of a low-level binary search tree. \fP".ti -1c.RI "\fB_gdsl_bstree_t\fP \fB_gdsl_bstree_get_left\fP (const \fB_gdsl_bstree_t\fP T)".br.RI "\fIGet the left sub-tree of a low-level binary search tree. \fP".ti -1c.RI "\fB_gdsl_bstree_t\fP \fB_gdsl_bstree_get_right\fP (const \fB_gdsl_bstree_t\fP T)".br.RI "\fIGet the right sub-tree of a low-level binary search tree. \fP".ti -1c.RI "\fBulong\fP \fB_gdsl_bstree_get_size\fP (const \fB_gdsl_bstree_t\fP T)".br.RI "\fIGet the size of a low-level binary search tree. \fP".ti -1c.RI "\fBulong\fP \fB_gdsl_bstree_get_height\fP (const \fB_gdsl_bstree_t\fP T)".br.RI "\fIGet the height of a low-level binary search tree. \fP".ti -1c.RI "\fB_gdsl_bstree_t\fP \fB_gdsl_bstree_insert\fP (\fB_gdsl_bstree_t\fP *T, const \fBgdsl_compare_func_t\fP COMP_F, const \fBgdsl_element_t\fP VALUE, int *RESULT)".br.RI "\fIInsert an element into a low-level binary search tree if it's not found or return it. \fP".ti -1c.RI "\fBgdsl_element_t\fP \fB_gdsl_bstree_remove\fP (\fB_gdsl_bstree_t\fP *T, const \fBgdsl_compare_func_t\fP COMP_F, const \fBgdsl_element_t\fP VALUE)".br.RI "\fIRemove an element from a low-level binary search tree. \fP".ti -1c.RI "\fB_gdsl_bstree_t\fP \fB_gdsl_bstree_search\fP (const \fB_gdsl_bstree_t\fP T, const \fBgdsl_compare_func_t\fP COMP_F, const \fBgdsl_element_t\fP VALUE)".br.RI "\fISearch for a particular element into a low-level binary search tree. \fP".ti -1c.RI "\fB_gdsl_bstree_t\fP \fB_gdsl_bstree_search_next\fP (const \fB_gdsl_bstree_t\fP T, const \fBgdsl_compare_func_t\fP COMP_F, const \fBgdsl_element_t\fP VALUE)".br.RI "\fISearch for the next element of a particular element into a low-level binary search tree, according to the binary search tree order. \fP".ti -1c.RI "\fB_gdsl_bstree_t\fP \fB_gdsl_bstree_map_prefix\fP (const \fB_gdsl_bstree_t\fP T, const \fB_gdsl_bstree_map_func_t\fP MAP_F, void *USER_DATA)".br.RI "\fIParse a low-level binary search tree in prefixed order. \fP".ti -1c.RI "\fB_gdsl_bstree_t\fP \fB_gdsl_bstree_map_infix\fP (const \fB_gdsl_bstree_t\fP T, const \fB_gdsl_bstree_map_func_t\fP MAP_F, void *USER_DATA)".br.RI "\fIParse a low-level binary search tree in infixed order. \fP".ti -1c.RI "\fB_gdsl_bstree_t\fP \fB_gdsl_bstree_map_postfix\fP (const \fB_gdsl_bstree_t\fP T, const \fB_gdsl_bstree_map_func_t\fP MAP_F, void *USER_DATA)".br.RI "\fIParse a low-level binary search tree in postfixed order. \fP".ti -1c.RI "void \fB_gdsl_bstree_write\fP (const \fB_gdsl_bstree_t\fP T, const \fB_gdsl_bstree_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 search tree to a file. \fP".ti -1c.RI "void \fB_gdsl_bstree_write_xml\fP (const \fB_gdsl_bstree_t\fP T, const \fB_gdsl_bstree_write_func_t\fP WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)".br.RI "\fIWrite the content of a low-level binary search tree to a file into XML. \fP".ti -1c.RI "void \fB_gdsl_bstree_dump\fP (const \fB_gdsl_bstree_t\fP T, const \fB_gdsl_bstree_write_func_t\fP WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)".br.RI "\fIDump the internal structure of a low-level binary search tree to a file. \fP".in -1c.SH "Typedef Documentation".PP .SS "typedef \fB_gdsl_bintree_t\fP \fB_gdsl_bstree_t\fP".PPGDSL low-level binary search 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 52 of file _gdsl_bstree.h..SS "typedef int(*  \fB_gdsl_bstree_map_func_t\fP)(\fB_gdsl_bstree_t\fP TREE, void *USER_DATA)".PPGDSL low-level binary search tree map function type. .PP\fBParameters:\fP.RS 4\fITREE\fP The low-level binary search 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 61 of file _gdsl_bstree.h..SS "typedef void(*  \fB_gdsl_bstree_write_func_t\fP)(\fB_gdsl_bstree_t\fP TREE, FILE *OUTPUT_FILE, void *USER_DATA)".PPGDSL low-level binary search tree write function type. .PP\fBParameters:\fP.RS 4\fITREE\fP The low-level binary search 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 71 of file _gdsl_bstree.h..SH "Function Documentation".PP .SS "\fB_gdsl_bstree_t\fP _gdsl_bstree_alloc (const \fBgdsl_element_t\fP E)".PPCreate a new low-level binary search tree. .PPAllocate a new low-level binary search tree data structure. Its root content is sets to E and its left and right sons are set to NULL..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 search tree to create. .RE.PP\fBReturns:\fP.RS 4the newly allocated low-level binary search tree in case of success. .PPNULL in case of insufficient memory. .RE.PP\fBSee also:\fP.RS 4\fB_gdsl_bstree_free()\fP .RE.PP.SS "void _gdsl_bstree_free (\fB_gdsl_bstree_t\fP T, const \fBgdsl_free_func_t\fP FREE_F)".PPDestroy a low-level binary search tree. .PPFlush and destroy the low-level binary search 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 search 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_bstree_alloc()\fP .RE.PP.SS "\fB_gdsl_bstree_t\fP _gdsl_bstree_copy (const \fB_gdsl_bstree_t\fP T, const \fBgdsl_copy_func_t\fP COPY_F)".PPCopy a low-level binary search tree. .PPCreate and return a copy of the low-level binary search 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 search 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_bstree_is_empty (T) == TRUE or in case of insufficient memory. .RE.PP\fBSee also:\fP.RS 4\fB_gdsl_bstree_alloc()\fP .PP\fB_gdsl_bstree_free()\fP .PP\fB_gdsl_bstree_is_empty()\fP .RE.PP.SS "\fBbool\fP _gdsl_bstree_is_empty (const \fB_gdsl_bstree_t\fP T)".PPCheck if a low-level binary search 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 search tree to check. .RE.PP\fBReturns:\fP.RS 4TRUE if the low-level binary search tree T is empty. .PPFALSE if the low-level binary search tree T is not empty. .RE.PP\fBSee also:\fP.RS 4\fB_gdsl_bstree_is_leaf()\fP .PP\fB_gdsl_bstree_is_root()\fP .RE.PP.SS "\fBbool\fP _gdsl_bstree_is_leaf (const \fB_gdsl_bstree_t\fP T)".PPCheck if a low-level binary search 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_bstree_t. .RE.PP\fBParameters:\fP.RS 4\fIT\fP The low-level binary search tree to check. .RE.PP\fBReturns:\fP.RS 4TRUE if the low-level binary search tree T is a leaf. .PPFALSE if the low-level binary search tree T is not a leaf. .RE.PP\fBSee also:\fP.RS 4\fB_gdsl_bstree_is_empty()\fP .PP\fB_gdsl_bstree_is_root()\fP .RE.PP.SS "\fBgdsl_element_t\fP _gdsl_bstree_get_content (const \fB_gdsl_bstree_t\fP T)".PPGet the root content of a low-level binary search tree. .PP\fBNote:\fP.RS 4Complexity: O( 1 ) .RE.PP\fBPrecondition:\fP.RS 4T must be a non-empty _gdsl_bstree_t. .RE.PP\fBParameters:\fP.RS 4\fIT\fP The low-level binary search tree to use. .RE.PP\fBReturns:\fP.RS 4the root's content of the low-level binary search tree T. .RE.PP.SS "\fBbool\fP _gdsl_bstree_is_root (const \fB_gdsl_bstree_t\fP T)".PPCheck if a low-level binary search tree is a root. .PP\fBNote:\fP.RS 4Complexity: O( 1 ) .RE.PP\fBPrecondition:\fP.RS 4T must be a non-empty _gdsl_bstree_t. .RE.PP\fBParameters:\fP.RS 4\fIT\fP The low-level binary search tree to check. .RE.PP\fBReturns:\fP.RS 4TRUE if the low-level binary search tree T is a root. .PPFALSE if the low-level binary search tree T is not a root. .RE.PP\fBSee also:\fP.RS 4\fB_gdsl_bstree_is_empty()\fP .PP\fB_gdsl_bstree_is_leaf()\fP .RE.PP.SS "\fB_gdsl_bstree_t\fP _gdsl_bstree_get_parent (const \fB_gdsl_bstree_t\fP T)".PPGet the parent tree of a low-level binary search tree. .PP\fBNote:\fP.RS 4Complexity: O( 1 ) .RE.PP\fBPrecondition:\fP.RS 4T must be a non-empty _gdsl_bstree_t. .RE.PP\fBParameters:\fP.RS 4\fIT\fP The low-level binary search tree to use. .RE.PP\fBReturns:\fP.RS 4the parent of the low-level binary search tree T if T isn't a root. .PPNULL if the low-level binary search tree T is a root (ie. T has no parent). .RE.PP\fBSee also:\fP.RS 4\fB_gdsl_bstree_is_root()\fP .RE.PP.SS "\fB_gdsl_bstree_t\fP _gdsl_bstree_get_left (const \fB_gdsl_bstree_t\fP T)".PPGet the left sub-tree of a low-level binary search tree. .PP\fBNote:\fP.RS 4Complexity: O( 1 ) .RE.PP\fBPrecondition:\fP.RS 4T must be a non-empty _gdsl_bstree_t. .RE.PP\fBParameters:\fP.RS 4\fIT\fP The low-level binary search tree to use. .RE.PP\fBReturns:\fP.RS 4the left sub-tree of the low-level binary search tree T if T has a left sub-tree. .PPNULL if the low-level binary search tree T has no left sub-tree. .RE.PP\fBSee also:\fP.RS 4\fB_gdsl_bstree_get_right()\fP .RE.PP.SS "\fB_gdsl_bstree_t\fP _gdsl_bstree_get_right (const \fB_gdsl_bstree_t\fP T)".PPGet the right sub-tree of a low-level binary search tree. .PP\fBNote:\fP.RS 4Complexity: O( 1 ) .RE.PP\fBPrecondition:\fP.RS 4T must be a non-empty _gdsl_bstree_t.