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