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 
00041 
00053 typedef _gdsl_bintree_t _gdsl_bstree_t;
00054 
00062 typedef int (* _gdsl_bstree_map_func_t) (_gdsl_bstree_t TREE,
00063                      void* USER_DATA
00064                      );
00065 
00072 typedef void (* _gdsl_bstree_write_func_t) (_gdsl_bstree_t TREE,
00073                         FILE* OUTPUT_FILE,
00074                         void* USER_DATA
00075                         );
00076 
00077 /******************************************************************************/
00078 /* Management functions of low-level binary search trees                      */
00079 /******************************************************************************/
00080 
00094 extern _gdsl_bstree_t
00095 _gdsl_bstree_alloc (const gdsl_element_t E
00096             );
00097 
00111 extern void 
00112 _gdsl_bstree_free (_gdsl_bstree_t T,
00113            const gdsl_free_func_t FREE_F
00114            );
00115 
00133 extern _gdsl_bstree_t
00134 _gdsl_bstree_copy (const _gdsl_bstree_t T,
00135            const gdsl_copy_func_t COPY_F
00136            );
00137 
00138 /******************************************************************************/
00139 /* Consultation functions of low-level binary search trees                    */
00140 /******************************************************************************/
00141 
00152 extern bool
00153 _gdsl_bstree_is_empty (const _gdsl_bstree_t T
00154                );
00155 
00166 extern bool
00167 _gdsl_bstree_is_leaf (const _gdsl_bstree_t T
00168               );
00169 
00177 extern gdsl_element_t
00178 _gdsl_bstree_get_content (const _gdsl_bstree_t T
00179               );
00180 
00191 extern bool
00192 _gdsl_bstree_is_root (const _gdsl_bstree_t T
00193               );
00194 
00205 extern _gdsl_bstree_t
00206 _gdsl_bstree_get_parent (const _gdsl_bstree_t T
00207              );
00208 
00219 extern _gdsl_bstree_t
00220 _gdsl_bstree_get_left (const _gdsl_bstree_t T
00221                );
00222 
00233 extern _gdsl_bstree_t
00234 _gdsl_bstree_get_right (const _gdsl_bstree_t T
00235             );
00236 
00245 extern ulong
00246 _gdsl_bstree_get_size (const _gdsl_bstree_t T
00247                );
00248   
00260 extern ulong
00261 _gdsl_bstree_get_height (const _gdsl_bstree_t T
00262              );
00263 
00264 /******************************************************************************/
00265 /* Modification functions of low-level binary search trees                    */
00266 /******************************************************************************/
00267 
00291 extern _gdsl_bstree_t
00292 _gdsl_bstree_insert (_gdsl_bstree_t* T,
00293              const gdsl_compare_func_t COMP_F,
00294              const gdsl_element_t VALUE,
00295              int* RESULT
00296              );
00297 
00319 extern gdsl_element_t
00320 _gdsl_bstree_remove (_gdsl_bstree_t* T,
00321              const gdsl_compare_func_t COMP_F,
00322              const gdsl_element_t VALUE
00323              );
00324   
00325 /******************************************************************************/
00326 /* Search functions of low-level binary search trees                          */
00327 /******************************************************************************/
00328 
00346 extern _gdsl_bstree_t
00347 _gdsl_bstree_search (const _gdsl_bstree_t T,
00348              const gdsl_compare_func_t COMP_F,
00349              const gdsl_element_t VALUE
00350              );
00351 
00368 extern _gdsl_bstree_t
00369 _gdsl_bstree_search_next (const _gdsl_bstree_t T, 
00370               const gdsl_compare_func_t COMP_F,
00371               const gdsl_element_t VALUE
00372               );
00373 
00374 /******************************************************************************/
00375 /* Parse functions of low-level binary search trees                           */
00376 /******************************************************************************/
00377 
00396 extern _gdsl_bstree_t
00397 _gdsl_bstree_map_prefix (const _gdsl_bstree_t T,
00398              const _gdsl_bstree_map_func_t MAP_F,
00399              void* USER_DATA
00400              );
00401 
00420 extern _gdsl_bstree_t
00421 _gdsl_bstree_map_infix (const _gdsl_bstree_t T,
00422             const _gdsl_bstree_map_func_t MAP_F,
00423             void* USER_DATA
00424             );
00425 
00444 extern _gdsl_bstree_t
00445 _gdsl_bstree_map_postfix (const _gdsl_bstree_t T,
00446               const _gdsl_bstree_map_func_t MAP_F,
00447               void* USER_DATA
00448               );
00449 
00450 /******************************************************************************/
00451 /* Input/output functions of low-level binary search trees                    */
00452 /******************************************************************************/
00453 
00471 extern void
00472 _gdsl_bstree_write (const _gdsl_bstree_t T,
00473             const _gdsl_bstree_write_func_t WRITE_F,
00474             FILE* OUTPUT_FILE,
00475             void* USER_DATA
00476             );
00477 
00497 extern void
00498 _gdsl_bstree_write_xml (const _gdsl_bstree_t T,
00499             const _gdsl_bstree_write_func_t WRITE_F,
00500             FILE* OUTPUT_FILE,
00501             void* USER_DATA
00502             );
00503 
00522 extern void
00523 _gdsl_bstree_dump (const _gdsl_bstree_t T,
00524            const _gdsl_bstree_write_func_t WRITE_F,
00525            FILE* OUTPUT_FILE,
00526            void* USER_DATA
00527            );
00528 
00529 /*
00530  * @}
00531  */
00532 
00533 
00534 #ifdef __cplusplus
00535 }
00536 #endif /* __cplusplus */
00537 
00538 
00539 #endif /* _GDSL_BSTREE_H_ */
00540 
00541