gdsl_bstree.3

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

.RS 4
\fBgdsl_bstree_get_name()\fP 
.RE
.PP

.SS "\fBgdsl_element_t\fP gdsl_bstree_insert (\fBgdsl_bstree_t\fP T, void * VALUE, int * RESULT)"
.PP
Insert an element into a binary search tree if it's not found or return it. 
.PP
Search for the first element E equal to VALUE into the binary search tree T, by using T's COMP_F function passed to gdsl_bstree_alloc to find it. If E is found, then it's returned. If E isn't found, then a new element E is allocated using T's ALLOC_F function passed to gdsl_bstree_alloc and is inserted and then returned.
.PP
\fBNote:\fP
.RS 4
Complexity: O( h(T) ), where log2(|T|) <= h(T) <= |T|-1 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_bstree_t & RESULT != NULL 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The binary search tree to modify 
.br
\fIVALUE\fP The value used to make the new element to insert into T 
.br
\fIRESULT\fP The address where the result code will be stored. 
.RE
.PP
\fBReturns:\fP
.RS 4
the element E and RESULT = GDSL_OK if E is inserted into T. 
.PP
the element E and RESULT = GDSL_ERR_DUPLICATE_ENTRY if E is already present in T. 
.PP
NULL and RESULT = GDSL_ERR_MEM_ALLOC in case of insufficient memory. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_bstree_remove()\fP 
.PP
\fBgdsl_bstree_delete()\fP 
.RE
.PP

.SS "\fBgdsl_element_t\fP gdsl_bstree_remove (\fBgdsl_bstree_t\fP T, void * VALUE)"
.PP
Remove an element from a binary search tree. 
.PP
Remove from the binary search tree T the first founded element E equal to VALUE, by using T's COMP_F function passed to \fBgdsl_bstree_alloc()\fP. If E is found, it is removed from T and then returned.
.PP
\fBNote:\fP
.RS 4
Complexity: O( h(T) ), where log2(|T|) <= h(T) <= |T|-1 
.PP
The resulting T is modified by examinating the left sub-tree from the founded E. 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_bstree_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The binary search tree to modify 
.br
\fIVALUE\fP The value used to find the element to remove 
.RE
.PP
\fBReturns:\fP
.RS 4
the first founded element equal to VALUE in T in case is found. 
.PP
NULL in case no element equal to VALUE is found in T. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_bstree_insert()\fP 
.PP
\fBgdsl_bstree_delete()\fP 
.RE
.PP

.SS "\fBgdsl_bstree_t\fP gdsl_bstree_delete (\fBgdsl_bstree_t\fP T, void * VALUE)"
.PP
Delete an element from a binary search tree. 
.PP
Remove from the binary search tree the first founded element E equal to VALUE, by using T's COMP_F function passed to \fBgdsl_bstree_alloc()\fP. If E is found, it is removed from T and E is deallocated using T's FREE_F function passed to \fBgdsl_bstree_alloc()\fP, then T is returned.
.PP
\fBNote:\fP
.RS 4
Complexity: O( h(T) ), where log2(|T|) <= h(T) <= |T|-1 
.PP
the resulting T is modified by examinating the left sub-tree from the founded E. 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_bstree_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The binary search tree to remove an element from 
.br
\fIVALUE\fP The value used to find the element to remove 
.RE
.PP
\fBReturns:\fP
.RS 4
the modified binary search tree after removal of E if E was found. 
.PP
NULL if no element equal to VALUE was found. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_bstree_insert()\fP 
.PP
\fBgdsl_bstree_remove()\fP 
.RE
.PP

.SS "\fBgdsl_element_t\fP gdsl_bstree_search (const \fBgdsl_bstree_t\fP T, \fBgdsl_compare_func_t\fP COMP_F, void * VALUE)"
.PP
Search for a particular element into a binary search tree. 
.PP
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 \fBgdsl_bstree_alloc()\fP is used.
.PP
\fBNote:\fP
.RS 4
Complexity: O( h(T) ), where log2(|T|) <= h(T) <= |T|-1 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_bstree_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The binary search tree to use. 
.br
\fICOMP_F\fP 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) 
.br
\fIVALUE\fP The value that must be used by COMP_F to find the element E 
.RE
.PP
\fBReturns:\fP
.RS 4
the first founded element E equal to VALUE. 
.PP
NULL if VALUE is not found in T. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_bstree_insert()\fP 
.PP
\fBgdsl_bstree_remove()\fP 
.PP
\fBgdsl_bstree_delete()\fP 
.RE
.PP

.SS "\fBgdsl_element_t\fP gdsl_bstree_map_prefix (const \fBgdsl_bstree_t\fP T, \fBgdsl_map_func_t\fP MAP_F, void * USER_DATA)"
.PP
Parse a binary search tree in prefixed order. 
.PP
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 \fBgdsl_bstree_map_prefix()\fP stops and returns its last examinated element.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |T| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_bstree_t & MAP_F != NULL 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The binary search tree to map. 
.br
\fIMAP_F\fP The map function. 
.br
\fIUSER_DATA\fP User's datas passed to MAP_F 
.RE
.PP
\fBReturns:\fP
.RS 4
the first element for which MAP_F returns GDSL_MAP_STOP. 
.PP
NULL when the parsing is done. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_bstree_map_infix()\fP 
.PP
\fBgdsl_bstree_map_postfix()\fP 
.RE
.PP

.SS "\fBgdsl_element_t\fP gdsl_bstree_map_infix (const \fBgdsl_bstree_t\fP T, \fBgdsl_map_func_t\fP MAP_F, void * USER_DATA)"
.PP
Parse a binary search tree in infixed order. 
.PP
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 \fBgdsl_bstree_map_infix()\fP stops and returns its last examinated element.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |T| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_bstree_t & MAP_F != NULL 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The binary search tree to map. 
.br
\fIMAP_F\fP The map function. 
.br
\fIUSER_DATA\fP User's datas passed to MAP_F 
.RE
.PP
\fBReturns:\fP
.RS 4
the first element for which MAP_F returns GDSL_MAP_STOP. 
.PP
NULL when the parsing is done. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_bstree_map_prefix()\fP 
.PP
\fBgdsl_bstree_map_postfix()\fP 
.RE
.PP

.SS "\fBgdsl_element_t\fP gdsl_bstree_map_postfix (const \fBgdsl_bstree_t\fP T, \fBgdsl_map_func_t\fP MAP_F, void * USER_DATA)"
.PP
Parse a binary search tree in postfixed order. 
.PP
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 \fBgdsl_bstree_map_postfix()\fP stops and returns its last examinated element.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |T| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_bstree_t & MAP_F != NULL 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The binary search tree to map. 
.br
\fIMAP_F\fP The map function. 
.br
\fIUSER_DATA\fP User's datas passed to MAP_F 
.RE
.PP
\fBReturns:\fP
.RS 4
the first element for which MAP_F returns GDSL_MAP_STOP. 
.PP
NULL when the parsing is done. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_bstree_map_prefix()\fP 
.PP
\fBgdsl_bstree_map_infix()\fP 
.RE
.PP

.SS "void gdsl_bstree_write (const \fBgdsl_bstree_t\fP T, \fBgdsl_write_func_t\fP WRITE_F, FILE * OUTPUT_FILE, void * USER_DATA)"
.PP
Write the element of each node of a binary search tree to a file. 
.PP
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.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |T| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_bstree_t & WRITE_F != NULL & OUTPUT_FILE != NULL 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The binary search tree to write. 
.br
\fIWRITE_F\fP The write function. 
.br
\fIOUTPUT_FILE\fP The file where to write T's elements. 
.br
\fIUSER_DATA\fP User's datas passed to WRITE_F. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_bstree_write_xml()\fP 
.PP
\fBgdsl_bstree_dump()\fP 
.RE
.PP

.SS "void gdsl_bstree_write_xml (const \fBgdsl_bstree_t\fP T, \fBgdsl_write_func_t\fP WRITE_F, FILE * OUTPUT_FILE, void * USER_DATA)"
.PP
Write the content of a binary search tree to a file into XML. 
.PP
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.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |T| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_bstree_t & OUTPUT_FILE != NULL 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The binary search tree to write. 
.br
\fIWRITE_F\fP The write function. 
.br
\fIOUTPUT_FILE\fP The file where to write T's elements. 
.br
\fIUSER_DATA\fP User's datas passed to WRITE_F. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_bstree_write()\fP 
.PP
\fBgdsl_bstree_dump()\fP 
.RE
.PP

.SS "void gdsl_bstree_dump (const \fBgdsl_bstree_t\fP T, \fBgdsl_write_func_t\fP WRITE_F, FILE * OUTPUT_FILE, void * USER_DATA)"
.PP
Dump the internal structure of a binary search tree to a file. 
.PP
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.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |T| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_bstree_t & OUTPUT_FILE != NULL 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The binary search tree to write. 
.br
\fIWRITE_F\fP The write function. 
.br
\fIOUTPUT_FILE\fP The file where to write T's elements. 
.br
\fIUSER_DATA\fP User's datas passed to WRITE_F. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_bstree_write()\fP 
.PP
\fBgdsl_bstree_write_xml()\fP 
.RE
.PP