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-2015 Nicolas Darnis <ndarnis@free.fr>.
00004  *
00005  * The GDSL library is free software; you can redistribute it and/or 
00006  * modify it under the terms of the GNU General Public License as 
00007  * published by the Free Software Foundation; either version 2 of
00008  * the License, or (at your option) any later version.
00009  *
00010  * The GDSL library 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 the GDSL library; see the file COPYING.
00017  * If not, write to the Free Software Foundation, Inc., 
00018  * 59 Temple Place, Suite 330, Boston, MA  02111-1307, USA.
00019  *
00020  * $RCSfile: _gdsl_bstree.h,v $
00021  * $Revision: 1.30 $
00022  * $Date: 2015/02/17 12:22:55 $
00023  */
00024 
00029 #ifndef __GDSL_BSTREE_H_
00030 #define __GDSL_BSTREE_H_
00031 
00032 
00033 #include "_gdsl_bintree.h"
00034 #include "gdsl_macros.h"
00035 #include "gdsl_types.h"
00036 
00037 
00038 #ifdef __cplusplus
00039 extern "C" 
00040 {
00041 #endif /* __cplusplus */
00042 
00043 
00055 typedef _gdsl_bintree_t _gdsl_bstree_t;
00056 
00064 typedef int (* _gdsl_bstree_map_func_t) (_gdsl_bstree_t TREE,
00065                      void* USER_DATA
00066                      );
00067 
00074 typedef void (* _gdsl_bstree_write_func_t) (_gdsl_bstree_t TREE,
00075                         FILE* OUTPUT_FILE,
00076                         void* USER_DATA
00077                         );
00078 
00079 /******************************************************************************/
00080 /* Management functions of low-level binary search trees                      */
00081 /******************************************************************************/
00082 
00096 extern _gdsl_bstree_t
00097 _gdsl_bstree_alloc (const gdsl_element_t E
00098             );
00099 
00113 extern void 
00114 _gdsl_bstree_free (_gdsl_bstree_t T,
00115            const gdsl_free_func_t FREE_F
00116            );
00117 
00135 extern _gdsl_bstree_t
00136 _gdsl_bstree_copy (const _gdsl_bstree_t T,
00137            const gdsl_copy_func_t COPY_F
00138            );
00139 
00140 /******************************************************************************/
00141 /* Consultation functions of low-level binary search trees                    */
00142 /******************************************************************************/
00143 
00154 extern bool
00155 _gdsl_bstree_is_empty (const _gdsl_bstree_t T
00156                );
00157 
00168 extern bool
00169 _gdsl_bstree_is_leaf (const _gdsl_bstree_t T
00170               );
00171 
00179 extern gdsl_element_t
00180 _gdsl_bstree_get_content (const _gdsl_bstree_t T
00181               );
00182 
00193 extern bool
00194 _gdsl_bstree_is_root (const _gdsl_bstree_t T
00195               );
00196 
00207 extern _gdsl_bstree_t
00208 _gdsl_bstree_get_parent (const _gdsl_bstree_t T
00209              );
00210 
00221 extern _gdsl_bstree_t
00222 _gdsl_bstree_get_left (const _gdsl_bstree_t T
00223                );
00224 
00235 extern _gdsl_bstree_t
00236 _gdsl_bstree_get_right (const _gdsl_bstree_t T
00237             );
00238 
00247 extern ulong
00248 _gdsl_bstree_get_size (const _gdsl_bstree_t T
00249                );
00250   
00262 extern ulong
00263 _gdsl_bstree_get_height (const _gdsl_bstree_t T
00264              );
00265 
00266 /******************************************************************************/
00267 /* Modification functions of low-level binary search trees                    */
00268 /******************************************************************************/
00269 
00293 extern _gdsl_bstree_t
00294 _gdsl_bstree_insert (_gdsl_bstree_t* T,
00295              const gdsl_compare_func_t COMP_F,
00296              const gdsl_element_t VALUE,
00297              int* RESULT
00298              );
00299 
00321 extern gdsl_element_t
00322 _gdsl_bstree_remove (_gdsl_bstree_t* T,
00323              const gdsl_compare_func_t COMP_F,
00324              const gdsl_element_t VALUE
00325              );
00326   
00327 /******************************************************************************/
00328 /* Search functions of low-level binary search trees                          */
00329 /******************************************************************************/
00330 
00348 extern _gdsl_bstree_t
00349 _gdsl_bstree_search (const _gdsl_bstree_t T,
00350              const gdsl_compare_func_t COMP_F,
00351              const gdsl_element_t VALUE
00352              );
00353 
00370 extern _gdsl_bstree_t
00371 _gdsl_bstree_search_next (const _gdsl_bstree_t T, 
00372               const gdsl_compare_func_t COMP_F,
00373               const gdsl_element_t VALUE
00374               );
00375 
00376 /******************************************************************************/
00377 /* Parse functions of low-level binary search trees                           */
00378 /******************************************************************************/
00379 
00398 extern _gdsl_bstree_t
00399 _gdsl_bstree_map_prefix (const _gdsl_bstree_t T,
00400              const _gdsl_bstree_map_func_t MAP_F,
00401              void* USER_DATA
00402              );
00403 
00422 extern _gdsl_bstree_t
00423 _gdsl_bstree_map_infix (const _gdsl_bstree_t T,
00424             const _gdsl_bstree_map_func_t MAP_F,
00425             void* USER_DATA
00426             );
00427 
00446 extern _gdsl_bstree_t
00447 _gdsl_bstree_map_postfix (const _gdsl_bstree_t T,
00448               const _gdsl_bstree_map_func_t MAP_F,
00449               void* USER_DATA
00450               );
00451 
00452 /******************************************************************************/
00453 /* Input/output functions of low-level binary search trees                    */
00454 /******************************************************************************/
00455 
00473 extern void
00474 _gdsl_bstree_write (const _gdsl_bstree_t T,
00475             const _gdsl_bstree_write_func_t WRITE_F,
00476             FILE* OUTPUT_FILE,
00477             void* USER_DATA
00478             );
00479 
00499 extern void
00500 _gdsl_bstree_write_xml (const _gdsl_bstree_t T,
00501             const _gdsl_bstree_write_func_t WRITE_F,
00502             FILE* OUTPUT_FILE,
00503             void* USER_DATA
00504             );
00505 
00524 extern void
00525 _gdsl_bstree_dump (const _gdsl_bstree_t T,
00526            const _gdsl_bstree_write_func_t WRITE_F,
00527            FILE* OUTPUT_FILE,
00528            void* USER_DATA
00529            );
00530 
00531 /*
00532  * @}
00533  */
00534 
00535 
00536 #ifdef __cplusplus
00537 }
00538 #endif /* __cplusplus */
00539 
00540 
00541 #endif /* _GDSL_BSTREE_H_ */
00542 
00543