gdsl  1.6
_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-2006 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_8h_source.html,v $
00021  * $Revision: 1.2 $
00022  * $Date: 2012/08/21 14:01:03 $
00023  */
00024 
00025 
00026 #ifndef __GDSL_BSTREE_H_
00027 #define __GDSL_BSTREE_H_
00028 
00029 
00030 #include "_gdsl_bintree.h"
00031 #include "gdsl_macros.h"
00032 #include "gdsl_types.h"
00033 
00034 
00035 #ifdef __cplusplus
00036 extern "C" 
00037 {
00038 #endif /* __cplusplus */
00039 
00040 
00052 typedef _gdsl_bintree_t _gdsl_bstree_t;
00053 
00061 typedef int (* _gdsl_bstree_map_func_t) (_gdsl_bstree_t TREE,
00062                      void* USER_DATA
00063                      );
00064 
00071 typedef void (* _gdsl_bstree_write_func_t) (_gdsl_bstree_t TREE,
00072                         FILE* OUTPUT_FILE,
00073                         void* USER_DATA
00074                         );
00075 
00076 /******************************************************************************/
00077 /* Management functions of low-level binary search trees                      */
00078 /******************************************************************************/
00079 
00093 extern _gdsl_bstree_t
00094 _gdsl_bstree_alloc (const gdsl_element_t E
00095             );
00096 
00110 extern void 
00111 _gdsl_bstree_free (_gdsl_bstree_t T,
00112            const gdsl_free_func_t FREE_F
00113            );
00114 
00132 extern _gdsl_bstree_t
00133 _gdsl_bstree_copy (const _gdsl_bstree_t T,
00134            const gdsl_copy_func_t COPY_F
00135            );
00136 
00137 /******************************************************************************/
00138 /* Consultation functions of low-level binary search trees                    */
00139 /******************************************************************************/
00140 
00151 extern bool
00152 _gdsl_bstree_is_empty (const _gdsl_bstree_t T
00153                );
00154 
00165 extern bool
00166 _gdsl_bstree_is_leaf (const _gdsl_bstree_t T
00167               );
00168 
00176 extern gdsl_element_t
00177 _gdsl_bstree_get_content (const _gdsl_bstree_t T
00178               );
00179 
00190 extern bool
00191 _gdsl_bstree_is_root (const _gdsl_bstree_t T
00192               );
00193 
00204 extern _gdsl_bstree_t
00205 _gdsl_bstree_get_parent (const _gdsl_bstree_t T
00206              );
00207 
00218 extern _gdsl_bstree_t
00219 _gdsl_bstree_get_left (const _gdsl_bstree_t T
00220                );
00221 
00232 extern _gdsl_bstree_t
00233 _gdsl_bstree_get_right (const _gdsl_bstree_t T
00234             );
00235 
00244 extern ulong
00245 _gdsl_bstree_get_size (const _gdsl_bstree_t T
00246                );
00247   
00259 extern ulong
00260 _gdsl_bstree_get_height (const _gdsl_bstree_t T
00261              );
00262 
00263 /******************************************************************************/
00264 /* Modification functions of low-level binary search trees                    */
00265 /******************************************************************************/
00266 
00290 extern _gdsl_bstree_t
00291 _gdsl_bstree_insert (_gdsl_bstree_t* T,
00292              const gdsl_compare_func_t COMP_F,
00293              const gdsl_element_t VALUE,
00294              int* RESULT
00295              );
00296 
00318 extern gdsl_element_t
00319 _gdsl_bstree_remove (_gdsl_bstree_t* T,
00320              const gdsl_compare_func_t COMP_F,
00321              const gdsl_element_t VALUE
00322              );
00323   
00324 /******************************************************************************/
00325 /* Search functions of low-level binary search trees                          */
00326 /******************************************************************************/
00327 
00345 extern _gdsl_bstree_t
00346 _gdsl_bstree_search (const _gdsl_bstree_t T,
00347              const gdsl_compare_func_t COMP_F,
00348              const gdsl_element_t VALUE
00349              );
00350 
00367 extern _gdsl_bstree_t
00368 _gdsl_bstree_search_next (const _gdsl_bstree_t T, 
00369               const gdsl_compare_func_t COMP_F,
00370               const gdsl_element_t VALUE
00371               );
00372 
00373 /******************************************************************************/
00374 /* Parse functions of low-level binary search trees                           */
00375 /******************************************************************************/
00376 
00395 extern _gdsl_bstree_t
00396 _gdsl_bstree_map_prefix (const _gdsl_bstree_t T,
00397              const _gdsl_bstree_map_func_t MAP_F,
00398              void* USER_DATA
00399              );
00400 
00419 extern _gdsl_bstree_t
00420 _gdsl_bstree_map_infix (const _gdsl_bstree_t T,
00421             const _gdsl_bstree_map_func_t MAP_F,
00422             void* USER_DATA
00423             );
00424 
00443 extern _gdsl_bstree_t
00444 _gdsl_bstree_map_postfix (const _gdsl_bstree_t T,
00445               const _gdsl_bstree_map_func_t MAP_F,
00446               void* USER_DATA
00447               );
00448 
00449 /******************************************************************************/
00450 /* Input/output functions of low-level binary search trees                    */
00451 /******************************************************************************/
00452 
00470 extern void
00471 _gdsl_bstree_write (const _gdsl_bstree_t T,
00472             const _gdsl_bstree_write_func_t WRITE_F,
00473             FILE* OUTPUT_FILE,
00474             void* USER_DATA
00475             );
00476 
00496 extern void
00497 _gdsl_bstree_write_xml (const _gdsl_bstree_t T,
00498             const _gdsl_bstree_write_func_t WRITE_F,
00499             FILE* OUTPUT_FILE,
00500             void* USER_DATA
00501             );
00502 
00521 extern void
00522 _gdsl_bstree_dump (const _gdsl_bstree_t T,
00523            const _gdsl_bstree_write_func_t WRITE_F,
00524            FILE* OUTPUT_FILE,
00525            void* USER_DATA
00526            );
00527 
00528 /*
00529  * @}
00530  */
00531 
00532 
00533 #ifdef __cplusplus
00534 }
00535 #endif /* __cplusplus */
00536 
00537 
00538 #endif /* _GDSL_BSTREE_H_ */
00539 
00540