gdsl
1.6
|
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