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