gdsl  1.7
Interval Heap manipulation module

Typedefs

typedef struct heap * gdsl_interval_heap_t
 GDSL interval heap type.

Functions

gdsl_interval_heap_t gdsl_interval_heap_alloc (const char *NAME, gdsl_alloc_func_t ALLOC_F, gdsl_free_func_t FREE_F, gdsl_compare_func_t COMP_F)
 Create a new interval heap.
void gdsl_interval_heap_free (gdsl_interval_heap_t H)
 Destroy an interval heap.
void gdsl_interval_heap_flush (gdsl_interval_heap_t H)
 Flush an interval heap.
const char * gdsl_interval_heap_get_name (const gdsl_interval_heap_t H)
 Get the name of an interval heap.
ulong gdsl_interval_heap_get_size (const gdsl_interval_heap_t H)
 Get the size of a interval heap.
void gdsl_interval_heap_set_max_size (const gdsl_interval_heap_t H, ulong size)
 Set the maximum size of the interval heap.
bool gdsl_interval_heap_is_empty (const gdsl_interval_heap_t H)
 Check if an interval heap is empty.
gdsl_interval_heap_t gdsl_interval_heap_set_name (gdsl_interval_heap_t H, const char *NEW_NAME)
 Set the name of an interval heap.
gdsl_element_t gdsl_interval_heap_insert (gdsl_interval_heap_t H, void *VALUE)
 Insert an element into an interval heap (PUSH).
gdsl_element_t gdsl_interval_heap_remove_max (gdsl_interval_heap_t H)
 Remove the maximum element from an interval heap (POP).
gdsl_element_t gdsl_interval_heap_remove_min (gdsl_interval_heap_t H)
 Remove the minimum element from an interval heap (POP).
gdsl_element_t gdsl_interval_heap_get_min (const gdsl_interval_heap_t H)
 Get the minimum element.
gdsl_element_t gdsl_interval_heap_get_max (const gdsl_interval_heap_t H)
 Get the maximum element.
gdsl_interval_heap_t gdsl_interval_heap_delete_min (gdsl_interval_heap_t H)
 Delete the minimum element from an interval heap.
gdsl_interval_heap_t gdsl_interval_heap_delete_max (gdsl_interval_heap_t H)
 Delete the maximum element from an interval heap.
gdsl_element_t gdsl_interval_heap_map_forward (const gdsl_interval_heap_t H, gdsl_map_func_t MAP_F, void *USER_DATA)
 Parse a interval heap.
void gdsl_interval_heap_write (const gdsl_interval_heap_t H, gdsl_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Write all the elements of an interval heap to a file.
void gdsl_interval_heap_write_xml (const gdsl_interval_heap_t H, gdsl_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Write the content of an interval heap to a file into XML.
void gdsl_interval_heap_dump (const gdsl_interval_heap_t H, gdsl_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Dump the internal structure of an interval heap to a file.

Typedef Documentation

typedef struct heap* gdsl_interval_heap_t

GDSL interval heap type.

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

Definition at line 53 of file gdsl_interval_heap.h.


Function Documentation

Create a new interval heap.

Allocate a new interval 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 interval heap. These pointers could be set to NULL to use the default ones:

  • the default ALLOC_F simply returns its argument
  • the default FREE_F does nothing
  • the default COMP_F always returns 0
Note:
Complexity: O( 1 )
Precondition:
nothing
Parameters:
NAMEThe name of the new interval heap to create
ALLOC_FFunction to alloc element when inserting it in the interval heap
FREE_FFunction to free element when removing it from the interval heap
COMP_FFunction to compare elements into the interval heap
Returns:
the newly allocated interval heap in case of success.
NULL in case of insufficient memory.
See also:
gdsl_interval_heap_free()
gdsl_interval_heap_flush()

Destroy an interval heap.

Deallocate all the elements of the interval heap H by calling H's FREE_F function passed to gdsl_interval_heap_alloc(). The name of H is deallocated and H is deallocated itself too.

Note:
Complexity: O( |H| )
Precondition:
H must be a valid gdsl_interval_heap_t
Parameters:
HThe interval heap to destroy
See also:
gdsl_interval_heap_alloc()
gdsl_interval_heap_flush()

Flush an interval heap.

Deallocate all the elements of the interval heap H by calling H's FREE_F function passed to gdsl_interval_heap_alloc(). H is not deallocated itself and H's name is not modified.

Note:
Complexity: O( |H| )
Precondition:
H must be a valid gdsl_interval_heap_t
Parameters:
HThe heap to flush
See also:
gdsl_interval_heap_alloc()
gdsl_interval_heap_free()

Get the name of an interval heap.

Note:
Complexity: O( 1 )
Precondition:
H must be a valid gdsl_interval_heap_t
Postcondition:
The returned string MUST NOT be freed.
Parameters:
HThe interval heap to get the name from
Returns:
the name of the interval heap H.
See also:
gdsl_interval_heap_set_name()

Get the size of a interval heap.

Note:
Complexity: O( 1 )
Precondition:
H must be a valid gdsl_interval_heap_t
Parameters:
HThe interval heap to get the size from
Returns:
the number of elements of H (noted |H|).

Set the maximum size of the interval heap.

Note:
Complexity: O( 1 )
Precondition:
H must be a valid gdsl_interval_heap_t
Parameters:
HThe interval heap to get the size from
sizeThe new maximum size
Returns:
the number of elements of H (noted |H|).

Check if an interval heap is empty.

Note:
Complexity: O( 1 )
Precondition:
H must be a valid gdsl_interval_heap_t
Parameters:
HThe interval heap to check
Returns:
TRUE if the interval heap H is empty.
FALSE if the interval heap H is not empty.

Set the name of an interval heap.

Change the previous name of the interval heap H to a copy of NEW_NAME.

Note:
Complexity: O( 1 )
Precondition:
H must be a valid gdsl_interval_heap_t
Parameters:
HThe interval heap to change the name
NEW_NAMEThe new name of H
Returns:
the modified interval heap in case of success.
NULL in case of insufficient memory.
See also:
gdsl_interval_heap_get_name()

Insert an element into an interval heap (PUSH).

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 an interval heap.

Note:
Complexity: O( log ( |H| ) )
Precondition:
H must be a valid gdsl_interval_heap_t
Parameters:
HThe interval heap to modify
VALUEThe value used to make the new element to insert into H
Returns:
the inserted element E in case of success.
NULL in case of insufficient memory.
See also:
gdsl_interval_heap_alloc()
gdsl_interval_heap_remove()
gdsl_interval_heap_delete()
gdsl_interval_heap_get_size()

Remove the maximum element from an interval heap (POP).

Remove the maximum element from the interval heap H. The element is removed from H and is also returned.

Note:
Complexity: O( log ( |H| ) )
Precondition:
H must be a valid gdsl_interval_heap_t
Parameters:
HThe interval heap to modify
Returns:
the removed top element.
NULL if the interval heap is empty.
See also:
gdsl_interval_heap_insert()
gdsl_interval_heap_delete_max()

Remove the minimum element from an interval heap (POP).

Remove the minimum element from the interval heap H. The element is removed from H and is also returned.

Note:
Complexity: O( log ( |H| ) )
Precondition:
H must be a valid gdsl_interval_heap_t
Parameters:
HThe interval heap to modify
Returns:
the removed top element.
NULL if the interval heap is empty.
See also:
gdsl_interval_heap_insert()
gdsl_interval_heap_delete_max()

Get the minimum element.

Note:
Complexity: O( 1 )
Precondition:
H must be a valid gdsl_interval_heap_t
Parameters:
HThe interval heap to get the size from
Returns:
The smallest element in H

Get the maximum element.

Note:
Complexity: O( 1 )
Precondition:
H must be a valid gdsl_interval_heap_t
Parameters:
HThe interval heap to get the size from
Returns:
The largest element in H

Delete the minimum element from an interval heap.

Remove the minimum element from the interval heap H. The element is removed from H and is also deallocated using H's FREE_F function passed to gdsl_interval_heap_alloc(), then H is returned.

Note:
Complexity: O( log ( |H| ) )
Precondition:
H must be a valid gdsl_interval_heap_t
Parameters:
HThe interval heap to modify
Returns:
the modified interval heap after removal of top element.
NULL if interval heap is empty.
See also:
gdsl_interval_heap_insert()
gdsl_interval_heap_remove_top()

Delete the maximum element from an interval heap.

Remove the maximum element from the interval heap H. The element is removed from H and is also deallocated using H's FREE_F function passed to gdsl_interval_heap_alloc(), then H is returned.

Note:
Complexity: O( log ( |H| ) )
Precondition:
H must be a valid gdsl_interval_heap_t
Parameters:
HThe interval heap to modify
Returns:
the modified interval heap after removal of top element.
NULL if interval heap is empty.
See also:
gdsl_interval_heap_insert()
gdsl_interval_heap_remove_top()

Parse a interval heap.

Parse all elements of the interval 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_interval_heap_map() stops and returns its last examinated element.

Note:
Complexity: O( |H| )
Precondition:
H must be a valid gdsl_interval_heap_t & MAP_F != NULL
Parameters:
HThe interval heap to map
MAP_FThe map function.
USER_DATAUser's datas passed to MAP_F
Returns:
the first element for which MAP_F returns GDSL_MAP_STOP.
NULL when the parsing is done.
void gdsl_interval_heap_write ( const gdsl_interval_heap_t  H,
gdsl_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA 
)

Write all the elements of an interval heap to a file.

Write the elements of the interval heap H to OUTPUT_FILE, using WRITE_F function. Additionnal USER_DATA argument could be passed to WRITE_F.

Note:
Complexity: O( |H| )
Precondition:
H must be a valid gdsl_interval_heap_t & OUTPUT_FILE != NULL & WRITE_F != NULL
Parameters:
HThe interval heap to write.
WRITE_FThe write function.
OUTPUT_FILEThe file where to write H's elements.
USER_DATAUser's datas passed to WRITE_F.
See also:
gdsl_interval_heap_write_xml()
gdsl_interval_heap_dump()
void gdsl_interval_heap_write_xml ( const gdsl_interval_heap_t  H,
gdsl_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA 
)

Write the content of an interval heap to a file into XML.

Write the elements of the interval 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.

Note:
Complexity: O( |H| )
Precondition:
H must be a valid gdsl_interval_heap_t & OUTPUT_FILE != NULL
Parameters:
HThe interval heap to write.
WRITE_FThe write function.
OUTPUT_FILEThe file where to write H's elements.
USER_DATAUser's datas passed to WRITE_F.
See also:
gdsl_interval_heap_write()
gdsl_interval_heap_dump()
void gdsl_interval_heap_dump ( const gdsl_interval_heap_t  H,
gdsl_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA 
)

Dump the internal structure of an interval heap to a file.

Dump the structure of the interval 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.

Note:
Complexity: O( |H| )
Precondition:
H must be a valid gdsl_interval_heap_t & OUTPUT_FILE != NULL
Parameters:
HThe interval heap to write
WRITE_FThe write function
OUTPUT_FILEThe file where to write H's elements
USER_DATAUser's datas passed to WRITE_F
See also:
gdsl_interval_heap_write()
gdsl_interval_heap_write_xml()