gdsl_heap.3

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

.TH "Heap manipulation module" 3 "22 Jun 2006" "Version 1.4" "gdsl" \" -*- nroff -*-
.ad l
.nh
.SH NAME
Heap manipulation module \- 
.PP
.SS "Typedefs"

.in +1c
.ti -1c
.RI "typedef heap * \fBgdsl_heap_t\fP"
.br
.RI "\fIGDSL heap type. \fP"
.in -1c
.SS "Functions"

.in +1c
.ti -1c
.RI "\fBgdsl_heap_t\fP \fBgdsl_heap_alloc\fP (const char *NAME, \fBgdsl_alloc_func_t\fP ALLOC_F, \fBgdsl_free_func_t\fP FREE_F, \fBgdsl_compare_func_t\fP COMP_F)"
.br
.RI "\fICreate a new heap. \fP"
.ti -1c
.RI "void \fBgdsl_heap_free\fP (\fBgdsl_heap_t\fP H)"
.br
.RI "\fIDestroy a heap. \fP"
.ti -1c
.RI "void \fBgdsl_heap_flush\fP (\fBgdsl_heap_t\fP H)"
.br
.RI "\fIFlush a heap. \fP"
.ti -1c
.RI "const char * \fBgdsl_heap_get_name\fP (const \fBgdsl_heap_t\fP H)"
.br
.RI "\fIGet the name of a heap. \fP"
.ti -1c
.RI "\fBulong\fP \fBgdsl_heap_get_size\fP (const \fBgdsl_heap_t\fP H)"
.br
.RI "\fIGet the size of a heap. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_heap_get_top\fP (const \fBgdsl_heap_t\fP H)"
.br
.RI "\fIGet the top of a heap. \fP"
.ti -1c
.RI "\fBbool\fP \fBgdsl_heap_is_empty\fP (const \fBgdsl_heap_t\fP H)"
.br
.RI "\fICheck if a heap is empty. \fP"
.ti -1c
.RI "\fBgdsl_heap_t\fP \fBgdsl_heap_set_name\fP (\fBgdsl_heap_t\fP H, const char *NEW_NAME)"
.br
.RI "\fISet the name of a heap. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_heap_set_top\fP (\fBgdsl_heap_t\fP H, void *VALUE)"
.br
.RI "\fISubstitute the top element of a heap by a lesser one. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_heap_insert\fP (\fBgdsl_heap_t\fP H, void *VALUE)"
.br
.RI "\fIInsert an element into a heap (PUSH). \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_heap_remove_top\fP (\fBgdsl_heap_t\fP H)"
.br
.RI "\fIRemove the top element from a heap (POP). \fP"
.ti -1c
.RI "\fBgdsl_heap_t\fP \fBgdsl_heap_delete_top\fP (\fBgdsl_heap_t\fP H)"
.br
.RI "\fIDelete the top element from a heap. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_heap_map_forward\fP (const \fBgdsl_heap_t\fP H, \fBgdsl_map_func_t\fP MAP_F, void *USER_DATA)"
.br
.RI "\fIParse a heap. \fP"
.ti -1c
.RI "void \fBgdsl_heap_write\fP (const \fBgdsl_heap_t\fP H, \fBgdsl_write_func_t\fP WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)"
.br
.RI "\fIWrite all the elements of a heap to a file. \fP"
.ti -1c
.RI "void \fBgdsl_heap_write_xml\fP (const \fBgdsl_heap_t\fP H, \fBgdsl_write_func_t\fP WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)"
.br
.RI "\fIWrite the content of a heap to a file into XML. \fP"
.ti -1c
.RI "void \fBgdsl_heap_dump\fP (const \fBgdsl_heap_t\fP H, \fBgdsl_write_func_t\fP WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)"
.br
.RI "\fIDump the internal structure of a heap to a file. \fP"
.in -1c
.SH "Typedef Documentation"
.PP 
.SS "typedef struct heap* \fBgdsl_heap_t\fP"
.PP
GDSL heap type. 
.PP
This type is voluntary opaque. Variables of this kind could'nt be directly used, but by the functions of this module. 
.PP
Definition at line 54 of file gdsl_heap.h.
.SH "Function Documentation"
.PP 
.SS "\fBgdsl_heap_t\fP gdsl_heap_alloc (const char * NAME, \fBgdsl_alloc_func_t\fP ALLOC_F, \fBgdsl_free_func_t\fP FREE_F, \fBgdsl_compare_func_t\fP COMP_F)"
.PP
Create a new heap. 
.PP
Allocate a new heap data structure which name is set to a copy of NAME. The function pointers ALLOC_F, FREE_F and COMP_F could be used to respectively, alloc, free and compares elements in the heap. These pointers could be set to NULL to use the default ones:
.IP "\(bu" 2
the default ALLOC_F simply returns its argument
.IP "\(bu" 2
the default FREE_F does nothing
.IP "\(bu" 2
the default COMP_F always returns 0
.PP
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
nothing 
.RE
.PP
\fBParameters:\fP
.RS 4
\fINAME\fP The name of the new heap to create 
.br
\fIALLOC_F\fP Function to alloc element when inserting it in the heap 
.br
\fIFREE_F\fP Function to free element when removing it from the heap 
.br
\fICOMP_F\fP Function to compare elements into the heap 
.RE
.PP
\fBReturns:\fP
.RS 4
the newly allocated heap in case of success. 
.PP
NULL in case of insufficient memory. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_heap_free()\fP 
.PP
\fBgdsl_heap_flush()\fP 
.RE
.PP

.SS "void gdsl_heap_free (\fBgdsl_heap_t\fP H)"
.PP
Destroy a heap. 
.PP
Deallocate all the elements of the heap H by calling H's FREE_F function passed to \fBgdsl_heap_alloc()\fP. The name of H is deallocated and H is deallocated itself too.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |H| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_heap_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The heap to destroy 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_heap_alloc()\fP 
.PP
\fBgdsl_heap_flush()\fP 
.RE
.PP

.SS "void gdsl_heap_flush (\fBgdsl_heap_t\fP H)"
.PP
Flush a heap. 
.PP
Deallocate all the elements of the heap H by calling H's FREE_F function passed to \fBgdsl_heap_alloc()\fP. H is not deallocated itself and H's name is not modified.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |H| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_heap_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The heap to flush 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_heap_alloc()\fP 
.PP
\fBgdsl_heap_free()\fP 
.RE
.PP

.SS "const char* gdsl_heap_get_name (const \fBgdsl_heap_t\fP H)"
.PP
Get the name of a heap. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_heap_t 
.RE
.PP
\fBPostcondition:\fP
.RS 4
The returned string MUST NOT be freed. 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The heap to get the name from 
.RE
.PP
\fBReturns:\fP
.RS 4
the name of the heap H. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_heap_set_name()\fP 
.RE
.PP

.SS "\fBulong\fP gdsl_heap_get_size (const \fBgdsl_heap_t\fP H)"
.PP
Get the size of a heap. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_heap_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The heap to get the size from 
.RE
.PP
\fBReturns:\fP
.RS 4
the number of elements of H (noted |H|). 
.RE
.PP

.SS "\fBgdsl_element_t\fP gdsl_heap_get_top (const \fBgdsl_heap_t\fP H)"
.PP
Get the top of a heap. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_heap_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The heap to get the top from 
.RE
.PP
\fBReturns:\fP
.RS 4
the element contained at the top position of the heap H if H is not empty. The returned element is not removed from H. 
.PP
NULL if the heap H is empty. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_heap_set_top()\fP 
.RE
.PP

.SS "\fBbool\fP gdsl_heap_is_empty (const \fBgdsl_heap_t\fP H)"
.PP
Check if a heap is empty. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_heap_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The heap to check 
.RE
.PP
\fBReturns:\fP
.RS 4
TRUE if the heap H is empty. 
.PP
FALSE if the heap H is not empty. 
.RE
.PP

.SS "\fBgdsl_heap_t\fP gdsl_heap_set_name (\fBgdsl_heap_t\fP H, const char * NEW_NAME)"
.PP
Set the name of a heap. 
.PP
Change the previous name of the heap H to a copy of NEW_NAME.
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_heap_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The heap to change the name 
.br
\fINEW_NAME\fP The new name of H 
.RE
.PP
\fBReturns:\fP
.RS 4
the modified heap in case of success. 
.PP
NULL in case of insufficient memory. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_heap_get_name()\fP 
.RE
.PP

.SS "\fBgdsl_element_t\fP gdsl_heap_set_top (\fBgdsl_heap_t\fP H, void * VALUE)"
.PP
Substitute the top element of a heap by a lesser one. 
.PP
Try to replace the top element of a heap by a lesser one.
.PP
\fBNote:\fP
.RS 4
Complexity: O( log ( |H| ) ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_heap_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The heap to substitute the top element 
.br
\fIVALUE\fP the value to substitute to the top 
.RE
.PP
\fBReturns:\fP
.RS 4
The old top element value in case VALUE is lesser than all other H elements. 
.PP
NULL in case of VALUE is greather or equal to all other H elements. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_heap_get_top()\fP 
.RE
.PP

.SS "\fBgdsl_element_t\fP gdsl_heap_insert (\fBgdsl_heap_t\fP H, void * VALUE)"
.PP
Insert an element into a heap (PUSH). 
.PP
Allocate a new element E by calling H's ALLOC_F function on VALUE. The element E is then inserted into H at the good position to ensure H is always a heap.
.PP
\fBNote:\fP
.RS 4
Complexity: O( log ( |H| ) ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_heap_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The heap to modify 
.br
\fIVALUE\fP The value used to make the new element to insert into H 
.RE
.PP
\fBReturns:\fP
.RS 4
the inserted element E in case of success. 
.PP
NULL in case of insufficient memory. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_heap_alloc()\fP 
.PP
gdsl_heap_remove() 
.PP
gdsl_heap_delete() 
.PP
\fBgdsl_heap_get_size()\fP 
.RE
.PP

.SS "\fBgdsl_element_t\fP gdsl_heap_remove_top (\fBgdsl_heap_t\fP H)"
.PP
Remove the top element from a heap (POP). 
.PP
Remove the top element from the heap H. The element is removed from H and is also returned.
.PP
\fBNote:\fP
.RS 4
Complexity: O( log ( |H| ) ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_heap_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The heap to modify 
.RE
.PP
\fBReturns:\fP
.RS 4
the removed top element. 
.PP
NULL if the heap is empty. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_heap_insert()\fP 
.PP
\fBgdsl_heap_delete_top()\fP 
.RE
.PP

.SS "\fBgdsl_heap_t\fP gdsl_heap_delete_top (\fBgdsl_heap_t\fP H)"
.PP
Delete the top element from a heap. 
.PP
Remove the top element from the heap H. The element is removed from H and is also deallocated using H's FREE_F function passed to \fBgdsl_heap_alloc()\fP, then H is returned.
.PP
\fBNote:\fP
.RS 4
Complexity: O( log ( |H| ) ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_heap_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The heap to modify 
.RE
.PP
\fBReturns:\fP
.RS 4
the modified heap after removal of top element. 
.PP
NULL if heap is empty. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_heap_insert()\fP 
.PP
\fBgdsl_heap_remove_top()\fP 
.RE
.PP

.SS "\fBgdsl_element_t\fP gdsl_heap_map_forward (const \fBgdsl_heap_t\fP H, \fBgdsl_map_func_t\fP MAP_F, void * USER_DATA)"
.PP
Parse a heap. 
.PP
Parse all elements of the heap H. The MAP_F function is called on each H's element with USER_DATA argument. If MAP_F returns GDSL_MAP_STOP then gdsl_heap_map() stops and returns its last examinated element.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |H| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_heap_t & MAP_F != NULL 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The heap 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

.SS "void gdsl_heap_write (const \fBgdsl_heap_t\fP H, \fBgdsl_write_func_t\fP WRITE_F, FILE * OUTPUT_FILE, void * USER_DATA)"
.PP
Write all the elements of a heap to a file. 
.PP
Write the elements of the heap H to OUTPUT_FILE, using WRITE_F function. Additionnal USER_DATA argument could be passed to WRITE_F.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |H| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_heap_t & OUTPUT_FILE != NULL & WRITE_F != NULL 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The heap to write. 
.br
\fIWRITE_F\fP The write function. 
.br
\fIOUTPUT_FILE\fP The file where to write H's elements. 
.br
\fIUSER_DATA\fP User's datas passed to WRITE_F. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_heap_write_xml()\fP 
.PP
\fBgdsl_heap_dump()\fP 
.RE
.PP

.SS "void gdsl_heap_write_xml (const \fBgdsl_heap_t\fP H, \fBgdsl_write_func_t\fP WRITE_F, FILE * OUTPUT_FILE, void * USER_DATA)"
.PP
Write the content of a heap to a file into XML. 
.PP
Write the elements of the heap H to OUTPUT_FILE, into XML language. If WRITE_F != NULL, then uses WRITE_F to write H's elements to OUTPUT_FILE. Additionnal USER_DATA argument could be passed to WRITE_F.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |H| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_heap_t & OUTPUT_FILE != NULL 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The heap to write. 
.br
\fIWRITE_F\fP The write function. 
.br
\fIOUTPUT_FILE\fP The file where to write H's elements. 
.br
\fIUSER_DATA\fP User's datas passed to WRITE_F. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_heap_write()\fP 
.PP
\fBgdsl_heap_dump()\fP 
.RE
.PP

.SS "void gdsl_heap_dump (const \fBgdsl_heap_t\fP H, \fBgdsl_write_func_t\fP WRITE_F, FILE * OUTPUT_FILE, void * USER_DATA)"
.PP
Dump the internal structure of a heap to a file. 
.PP
Dump the structure of the heap H to OUTPUT_FILE. If WRITE_F != NULL, then uses WRITE_F to write H's elements to OUTPUT_FILE. Additionnal USER_DATA argument could be passed to WRITE_F.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |H| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_heap_t & OUTPUT_FILE != NULL 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The heap to write 
.br
\fIWRITE_F\fP The write function 
.br
\fIOUTPUT_FILE\fP The file where to write H's elements 
.br
\fIUSER_DATA\fP User's datas passed to WRITE_F 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_heap_write()\fP 
.PP
\fBgdsl_heap_write_xml()\fP 
.RE
.PP