Main Page | Modules | File List | Globals

Binary search tree manipulation module


Typedefs

typedef gdsl_bstree * gdsl_bstree_t
 GDSL binary search tree type.


Functions

gdsl_bstree_t gdsl_bstree_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 binary search tree.

void gdsl_bstree_free (gdsl_bstree_t T)
 Destroy a binary search tree.

void gdsl_bstree_flush (gdsl_bstree_t T)
 Flush a binary search tree.

const char * gdsl_bstree_get_name (const gdsl_bstree_t T)
 Get the name of a binary search tree.

bool gdsl_bstree_is_empty (const gdsl_bstree_t T)
 Check if a binary search tree is empty.

gdsl_element_t gdsl_bstree_get_root (const gdsl_bstree_t T)
 Get the root of a binary search tree.

ulong gdsl_bstree_get_size (const gdsl_bstree_t T)
 Get the size of a binary search tree.

ulong gdsl_bstree_get_height (const gdsl_bstree_t T)
 Get the height of a binary search tree.

gdsl_bstree_t gdsl_bstree_set_name (gdsl_bstree_t T, const char *NEW_NAME)
 Set the name of a binary search tree.

gdsl_element_t gdsl_bstree_insert (gdsl_bstree_t T, void *VALUE, int *RESULT)
 Insert an element into a binary search tree if it's not found or return it.

gdsl_element_t gdsl_bstree_remove (gdsl_bstree_t T, void *VALUE)
 Remove an element from a binary search tree.

gdsl_bstree_t gdsl_bstree_delete (gdsl_bstree_t T, void *VALUE)
 Delete an element from a binary search tree.

gdsl_element_t gdsl_bstree_search (const gdsl_bstree_t T, gdsl_compare_func_t COMP_F, void *VALUE)
 Search for a particular element into a binary search tree.

gdsl_element_t gdsl_bstree_map_prefix (const gdsl_bstree_t T, gdsl_map_func_t MAP_F, void *USER_DATA)
 Parse a binary search tree in prefixed order.

gdsl_element_t gdsl_bstree_map_infix (const gdsl_bstree_t T, gdsl_map_func_t MAP_F, void *USER_DATA)
 Parse a binary search tree in infixed order.

gdsl_element_t gdsl_bstree_map_postfix (const gdsl_bstree_t T, gdsl_map_func_t MAP_F, void *USER_DATA)
 Parse a binary search tree in postfixed order.

void gdsl_bstree_write (const gdsl_bstree_t T, gdsl_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Write the element of each node of a binary search tree to a file.

void gdsl_bstree_write_xml (const gdsl_bstree_t T, gdsl_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Write the content of a binary search tree to a file into XML.

void gdsl_bstree_dump (const gdsl_bstree_t T, gdsl_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Dump the internal structure of a binary search tree to a file.


Typedef Documentation

typedef struct gdsl_bstree* gdsl_bstree_t
 

GDSL binary search tree type.

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

Definition at line 52 of file gdsl_bstree.h.


Function Documentation

gdsl_bstree_t gdsl_bstree_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 binary search tree.

Allocate a new binary search tree 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 tree. 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:
NAME The name of the new binary tree to create
ALLOC_F Function to alloc element when inserting it in a binary tree
FREE_F Function to free element when removing it from a binary tree
COMP_F Function to compare elements into the binary tree
Returns:
the newly allocated binary search tree in case of success.

NULL in case of insufficient memory.

See also:
gdsl_bstree_free()

gdsl_bstree_flush()

gdsl_alloc_func_t

gdsl_free_func_t

gdsl_compare_func_t

gdsl_bstree_t gdsl_bstree_delete gdsl_bstree_t  T,
void *  VALUE
 

Delete an element from a binary search tree.

Remove from the binary search tree the first founded element E equal to VALUE, by using T's COMP_F function passed to gdsl_bstree_alloc(). If E is found, it is removed from T and E is deallocated using T's FREE_F function passed to gdsl_bstree_alloc(), then T is returned.

Note:
Complexity: O( h(T) ), where log2(|T|) <= h(T) <= |T|-1

the resulting T is modified by examinating the left sub-tree from the founded E.

Precondition:
T must be a valid gdsl_bstree_t
Parameters:
T The binary search tree to remove an element from
VALUE The value used to find the element to remove
Returns:
the modified binary search tree after removal of E if E was found.

NULL if no element equal to VALUE was found.

See also:
gdsl_bstree_insert()

gdsl_bstree_remove()

void gdsl_bstree_dump const gdsl_bstree_t  T,
gdsl_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA
 

Dump the internal structure of a binary search tree to a file.

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.

Note:
Complexity: O( |T| )
Precondition:
T must be a valid gdsl_bstree_t & OUTPUT_FILE != NULL
Parameters:
T The binary search tree to write.
WRITE_F The write function.
OUTPUT_FILE The file where to write T's elements.
USER_DATA User's datas passed to WRITE_F.
See also:
gdsl_bstree_write()

gdsl_bstree_write_xml()

void gdsl_bstree_flush gdsl_bstree_t  T  ) 
 

Flush a binary search tree.

Deallocate all the elements of the binary search tree T by calling T's FREE_F function passed to gdsl_rbtree_alloc(). The binary search tree T is not deallocated itself and its name is not modified.

Note:
Complexity: O( |T| )
Precondition:
T must be a valid gdsl_bstree_t
Parameters:
T The binary search tree to flush
See also:
gdsl_bstree_alloc()

gdsl_bstree_free()

void gdsl_bstree_free gdsl_bstree_t  T  ) 
 

Destroy a binary search tree.

Deallocate all the elements of the binary search tree T by calling T's FREE_F function passed to gdsl_bstree_alloc(). The name of T is deallocated and T is deallocated itself too.

Note:
Complexity: O( |T| )
Precondition:
T must be a valid gdsl_bstree_t
Parameters:
T The binary search tree to deallocate
See also:
gdsl_bstree_alloc()

gdsl_bstree_flush()

ulong gdsl_bstree_get_height const gdsl_bstree_t  T  ) 
 

Get the height of a binary search tree.

Note:
Complexity: O( |T| )
Precondition:
T must be a valid gdsl_bstree_t
Parameters:
T The binary search tree to compute the height from
Returns:
the height of the binary search tree T (noted h(T)).
See also:
gdsl_bstree_get_size()

const char* gdsl_bstree_get_name const gdsl_bstree_t  T  ) 
 

Get the name of a binary search tree.

Note:
Complexity: O( 1 )
Precondition:
T must be a valid gdsl_bstree_t
Postcondition:
The returned string MUST NOT be freed.
Parameters:
T The binary search tree to get the name from
Returns:
the name of the binary search tree T.
See also:
gdsl_bstree_set_name ()

gdsl_element_t gdsl_bstree_get_root const gdsl_bstree_t  T  ) 
 

Get the root of a binary search tree.

Note:
Complexity: O( 1 )
Precondition:
T must be a valid gdsl_bstree_t
Parameters:
T The binary search tree to get the root element from
Returns:
the element at the root of the binary search tree T.

ulong gdsl_bstree_get_size const gdsl_bstree_t  T  ) 
 

Get the size of a binary search tree.

Note:
Complexity: O( 1 )
Precondition:
T must be a valid gdsl_bstree_t
Parameters:
T The binary search tree to get the size from
Returns:
the size of the binary search tree T (noted |T|).
See also:
gdsl_bstree_get_height()

gdsl_element_t gdsl_bstree_insert gdsl_bstree_t  T,
void *  VALUE,
int *  RESULT
 

Insert an element into a binary search tree if it's not found or return it.

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.

Note:
Complexity: O( h(T) ), where log2(|T|) <= h(T) <= |T|-1
Precondition:
T must be a valid gdsl_bstree_t & RESULT != NULL
Parameters:
T The binary search tree to modify
VALUE The value used to make the new element to insert into T
RESULT The address where the result code will be stored.
Returns:
the element E and RESULT = GDSL_OK if E is inserted into T.

the element E and RESULT = GDSL_ERR_DUPLICATE_ENTRY if E is already present in T.

NULL and RESULT = GDSL_ERR_MEM_ALLOC in case of insufficient memory.

See also:
gdsl_bstree_remove()

gdsl_bstree_delete()

bool gdsl_bstree_is_empty const gdsl_bstree_t  T  ) 
 

Check if a binary search tree is empty.

Note:
Complexity: O( 1 )
Precondition:
T must be a valid gdsl_bstree_t
Parameters:
T The binary search tree to check
Returns:
TRUE if the binary search tree T is empty.

FALSE if the binary search tree T is not empty.

gdsl_element_t gdsl_bstree_map_infix const gdsl_bstree_t  T,
gdsl_map_func_t  MAP_F,
void *  USER_DATA
 

Parse a binary search tree in infixed order.

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 gdsl_bstree_map_infix() stops and returns its last examinated element.

Note:
Complexity: O( |T| )
Precondition:
T must be a valid gdsl_bstree_t & MAP_F != NULL
Parameters:
T The binary search tree to map.
MAP_F The map function.
USER_DATA User's datas passed to MAP_F
Returns:
the first element for which MAP_F returns GDSL_MAP_STOP.

NULL when the parsing is done.

See also:
gdsl_bstree_map_prefix()

gdsl_bstree_map_postfix()

gdsl_element_t gdsl_bstree_map_postfix const gdsl_bstree_t  T,
gdsl_map_func_t  MAP_F,
void *  USER_DATA
 

Parse a binary search tree in postfixed order.

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 gdsl_bstree_map_postfix() stops and returns its last examinated element.

Note:
Complexity: O( |T| )
Precondition:
T must be a valid gdsl_bstree_t & MAP_F != NULL
Parameters:
T The binary search tree to map.
MAP_F The map function.
USER_DATA User's datas passed to MAP_F
Returns:
the first element for which MAP_F returns GDSL_MAP_STOP.

NULL when the parsing is done.

See also:
gdsl_bstree_map_prefix()

gdsl_bstree_map_infix()

gdsl_element_t gdsl_bstree_map_prefix const gdsl_bstree_t  T,
gdsl_map_func_t  MAP_F,
void *  USER_DATA
 

Parse a binary search tree in prefixed order.

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 gdsl_bstree_map_prefix() stops and returns its last examinated element.

Note:
Complexity: O( |T| )
Precondition:
T must be a valid gdsl_bstree_t & MAP_F != NULL
Parameters:
T The binary search tree to map.
MAP_F The map function.
USER_DATA User's datas passed to MAP_F
Returns:
the first element for which MAP_F returns GDSL_MAP_STOP.

NULL when the parsing is done.

See also:
gdsl_bstree_map_infix()

gdsl_bstree_map_postfix()

gdsl_element_t gdsl_bstree_remove gdsl_bstree_t  T,
void *  VALUE
 

Remove an element from a binary search tree.

Remove from the binary search tree T the first founded element E equal to VALUE, by using T's COMP_F function passed to gdsl_bstree_alloc(). If E is found, it is removed from T and then returned.

Note:
Complexity: O( h(T) ), where log2(|T|) <= h(T) <= |T|-1

The resulting T is modified by examinating the left sub-tree from the founded E.

Precondition:
T must be a valid gdsl_bstree_t
Parameters:
T The binary search tree to modify
VALUE The value used to find the element to remove
Returns:
the first founded element equal to VALUE in T in case is found.

NULL in case no element equal to VALUE is found in T.

See also:
gdsl_bstree_insert()

gdsl_bstree_delete()

gdsl_element_t gdsl_bstree_search const gdsl_bstree_t  T,
gdsl_compare_func_t  COMP_F,
void *  VALUE
 

Search for a particular element into a binary search tree.

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 gdsl_bstree_alloc() is used.

Note:
Complexity: O( h(T) ), where log2(|T|) <= h(T) <= |T|-1
Precondition:
T must be a valid gdsl_bstree_t
Parameters:
T The binary search tree to use.
COMP_F 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)
VALUE The value that must be used by COMP_F to find the element E
Returns:
the first founded element E equal to VALUE.

NULL if VALUE is not found in T.

See also:
gdsl_bstree_insert()

gdsl_bstree_remove()

gdsl_bstree_delete()

gdsl_bstree_t gdsl_bstree_set_name gdsl_bstree_t  T,
const char *  NEW_NAME
 

Set the name of a binary search tree.

Change the previous name of the binary search tree T to a copy of NEW_NAME.

Note:
Complexity: O( 1 )
Precondition:
T must be a valid gdsl_bstree_t
Parameters:
T The binary search tree to change the name
NEW_NAME The new name of T
Returns:
the modified binary search tree in case of success.

NULL in case of insufficient memory.

See also:
gdsl_bstree_get_name()

void gdsl_bstree_write const gdsl_bstree_t  T,
gdsl_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA
 

Write the element of each node of a binary search tree to a file.

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.

Note:
Complexity: O( |T| )
Precondition:
T must be a valid gdsl_bstree_t & WRITE_F != NULL & OUTPUT_FILE != NULL
Parameters:
T The binary search tree to write.
WRITE_F The write function.
OUTPUT_FILE The file where to write T's elements.
USER_DATA User's datas passed to WRITE_F.
See also:
gdsl_bstree_write_xml()

gdsl_bstree_dump()

void gdsl_bstree_write_xml const gdsl_bstree_t  T,
gdsl_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA
 

Write the content of a binary search tree to a file into XML.

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.

Note:
Complexity: O( |T| )
Precondition:
T must be a valid gdsl_bstree_t & OUTPUT_FILE != NULL
Parameters:
T The binary search tree to write.
WRITE_F The write function.
OUTPUT_FILE The file where to write T's elements.
USER_DATA User's datas passed to WRITE_F.
See also:
gdsl_bstree_write()

gdsl_bstree_dump()


Generated on Fri Oct 1 18:54:53 2004 for GDSL by doxygen 1.3.5