gdsl  1.8
_gdsl_bstree.h
Go to the documentation of this file.
00001 /*
00002  * This file is part of the Generic Data Structures Library (GDSL).
00003  * Copyright (C) 1998-2017 Nicolas Darnis <ndarnis@free.fr>.
00004  *
00005  * GDSL is free software: you can redistribute it and/or modify
00006  * it under the terms of the GNU General Public License as published by
00007  * the Free Software Foundation, either version 3 of the License, or
00008  * (at your option) any later version.
00009  *
00010  * GDSL is distributed in the hope that it will be useful,
00011  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00012  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00013  * GNU General Public License for more details.
00014  *
00015  * You should have received a copy of the GNU General Public License
00016  * along with GDSL.  If not, see <http://www.gnu.org/licenses/>. 
00017  *
00018  * $RCSfile: _gdsl_bstree.h,v $
00019  * $Revision: 1.30 $
00020  * $Date: 2015/02/17 12:22:55 $
00021  */
00022 
00027 #ifndef __GDSL_BSTREE_H_
00028 #define __GDSL_BSTREE_H_
00029 
00030 
00031 #include "_gdsl_bintree.h"
00032 #include "gdsl_macros.h"
00033 #include "gdsl_types.h"
00034 
00035 
00036 #ifdef __cplusplus
00037 extern "C" 
00038 {
00039 #endif /* __cplusplus */
00040 
00071 typedef _gdsl_bintree_t _gdsl_bstree_t;
00072 
00080 typedef int (* _gdsl_bstree_map_func_t) (_gdsl_bstree_t TREE,
00081                      void* USER_DATA
00082                      );
00083 
00090 typedef void (* _gdsl_bstree_write_func_t) (_gdsl_bstree_t TREE,
00091                         FILE* OUTPUT_FILE,
00092                         void* USER_DATA
00093                         );
00094 
00095 /******************************************************************************/
00096 /* Management functions of low-level binary search trees                      */
00097 /******************************************************************************/
00098 
00112 extern _gdsl_bstree_t
00113 _gdsl_bstree_alloc (const gdsl_element_t E
00114             );
00115 
00129 extern void 
00130 _gdsl_bstree_free (_gdsl_bstree_t T,
00131            const gdsl_free_func_t FREE_F
00132            );
00133 
00151 extern _gdsl_bstree_t
00152 _gdsl_bstree_copy (const _gdsl_bstree_t T,
00153            const gdsl_copy_func_t COPY_F
00154            );
00155 
00156 /******************************************************************************/
00157 /* Consultation functions of low-level binary search trees                    */
00158 /******************************************************************************/
00159 
00170 extern bool
00171 _gdsl_bstree_is_empty (const _gdsl_bstree_t T
00172                );
00173 
00184 extern bool
00185 _gdsl_bstree_is_leaf (const _gdsl_bstree_t T
00186               );
00187 
00195 extern gdsl_element_t
00196 _gdsl_bstree_get_content (const _gdsl_bstree_t T
00197               );
00198 
00209 extern bool
00210 _gdsl_bstree_is_root (const _gdsl_bstree_t T
00211               );
00212 
00223 extern _gdsl_bstree_t
00224 _gdsl_bstree_get_parent (const _gdsl_bstree_t T
00225              );
00226 
00237 extern _gdsl_bstree_t
00238 _gdsl_bstree_get_left (const _gdsl_bstree_t T
00239                );
00240 
00251 extern _gdsl_bstree_t
00252 _gdsl_bstree_get_right (const _gdsl_bstree_t T
00253             );
00254 
00263 extern ulong
00264 _gdsl_bstree_get_size (const _gdsl_bstree_t T
00265                );
00266   
00278 extern ulong
00279 _gdsl_bstree_get_height (const _gdsl_bstree_t T
00280              );
00281 
00282 /******************************************************************************/
00283 /* Modification functions of low-level binary search trees                    */
00284 /******************************************************************************/
00285 
00309 extern _gdsl_bstree_t
00310 _gdsl_bstree_insert (_gdsl_bstree_t* T,
00311              const gdsl_compare_func_t COMP_F,
00312              const gdsl_element_t VALUE,
00313              int* RESULT
00314              );
00315 
00337 extern gdsl_element_t
00338 _gdsl_bstree_remove (_gdsl_bstree_t* T,
00339              const gdsl_compare_func_t COMP_F,
00340              const gdsl_element_t VALUE
00341              );
00342   
00343 /******************************************************************************/
00344 /* Search functions of low-level binary search trees                          */
00345 /******************************************************************************/
00346 
00364 extern _gdsl_bstree_t
00365 _gdsl_bstree_search (const _gdsl_bstree_t T,
00366              const gdsl_compare_func_t COMP_F,
00367              const gdsl_element_t VALUE
00368              );
00369 
00386 extern _gdsl_bstree_t
00387 _gdsl_bstree_search_next (const _gdsl_bstree_t T, 
00388               const gdsl_compare_func_t COMP_F,
00389               const gdsl_element_t VALUE
00390               );
00391 
00392 /******************************************************************************/
00393 /* Parse functions of low-level binary search trees                           */
00394 /******************************************************************************/
00395 
00414 extern _gdsl_bstree_t
00415 _gdsl_bstree_map_prefix (const _gdsl_bstree_t T,
00416              const _gdsl_bstree_map_func_t MAP_F,
00417              void* USER_DATA
00418              );
00419 
00438 extern _gdsl_bstree_t
00439 _gdsl_bstree_map_infix (const _gdsl_bstree_t T,
00440             const _gdsl_bstree_map_func_t MAP_F,
00441             void* USER_DATA
00442             );
00443 
00462 extern _gdsl_bstree_t
00463 _gdsl_bstree_map_postfix (const _gdsl_bstree_t T,
00464               const _gdsl_bstree_map_func_t MAP_F,
00465               void* USER_DATA
00466               );
00467 
00468 /******************************************************************************/
00469 /* Input/output functions of low-level binary search trees                    */
00470 /******************************************************************************/
00471 
00489 extern void
00490 _gdsl_bstree_write (const _gdsl_bstree_t T,
00491             const _gdsl_bstree_write_func_t WRITE_F,
00492             FILE* OUTPUT_FILE,
00493             void* USER_DATA
00494             );
00495 
00515 extern void
00516 _gdsl_bstree_write_xml (const _gdsl_bstree_t T,
00517             const _gdsl_bstree_write_func_t WRITE_F,
00518             FILE* OUTPUT_FILE,
00519             void* USER_DATA
00520             );
00521 
00540 extern void
00541 _gdsl_bstree_dump (const _gdsl_bstree_t T,
00542            const _gdsl_bstree_write_func_t WRITE_F,
00543            FILE* OUTPUT_FILE,
00544            void* USER_DATA
00545            );
00546 
00552 #ifdef __cplusplus
00553 }
00554 #endif /* __cplusplus */
00555 
00556 
00557 #endif /* _GDSL_BSTREE_H_ */
00558 
00559