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 00071 typedef _gdsl_bintree_t _gdsl_bstree_t; 00072 00080 typedef int (* _gdsl_bstree_map_func_t) (_gdsl_bstree_t TREE, 00081 void* USER_DATA 00082 ); 00083 00090 typedef void (* _gdsl_bstree_write_func_t) (_gdsl_bstree_t TREE, 00091 FILE* OUTPUT_FILE, 00092 void* USER_DATA 00093 ); 00094 00095 /******************************************************************************/ 00096 /* Management functions of low-level binary search trees */ 00097 /******************************************************************************/ 00098 00112 extern _gdsl_bstree_t 00113 _gdsl_bstree_alloc (const gdsl_element_t E 00114 ); 00115 00129 extern void 00130 _gdsl_bstree_free (_gdsl_bstree_t T, 00131 const gdsl_free_func_t FREE_F 00132 ); 00133 00151 extern _gdsl_bstree_t 00152 _gdsl_bstree_copy (const _gdsl_bstree_t T, 00153 const gdsl_copy_func_t COPY_F 00154 ); 00155 00156 /******************************************************************************/ 00157 /* Consultation functions of low-level binary search trees */ 00158 /******************************************************************************/ 00159 00170 extern bool 00171 _gdsl_bstree_is_empty (const _gdsl_bstree_t T 00172 ); 00173 00184 extern bool 00185 _gdsl_bstree_is_leaf (const _gdsl_bstree_t T 00186 ); 00187 00195 extern gdsl_element_t 00196 _gdsl_bstree_get_content (const _gdsl_bstree_t T 00197 ); 00198 00209 extern bool 00210 _gdsl_bstree_is_root (const _gdsl_bstree_t T 00211 ); 00212 00223 extern _gdsl_bstree_t 00224 _gdsl_bstree_get_parent (const _gdsl_bstree_t T 00225 ); 00226 00237 extern _gdsl_bstree_t 00238 _gdsl_bstree_get_left (const _gdsl_bstree_t T 00239 ); 00240 00251 extern _gdsl_bstree_t 00252 _gdsl_bstree_get_right (const _gdsl_bstree_t T 00253 ); 00254 00263 extern ulong 00264 _gdsl_bstree_get_size (const _gdsl_bstree_t T 00265 ); 00266 00278 extern ulong 00279 _gdsl_bstree_get_height (const _gdsl_bstree_t T 00280 ); 00281 00282 /******************************************************************************/ 00283 /* Modification functions of low-level binary search trees */ 00284 /******************************************************************************/ 00285 00309 extern _gdsl_bstree_t 00310 _gdsl_bstree_insert (_gdsl_bstree_t* T, 00311 const gdsl_compare_func_t COMP_F, 00312 const gdsl_element_t VALUE, 00313 int* RESULT 00314 ); 00315 00337 extern gdsl_element_t 00338 _gdsl_bstree_remove (_gdsl_bstree_t* T, 00339 const gdsl_compare_func_t COMP_F, 00340 const gdsl_element_t VALUE 00341 ); 00342 00343 /******************************************************************************/ 00344 /* Search functions of low-level binary search trees */ 00345 /******************************************************************************/ 00346 00364 extern _gdsl_bstree_t 00365 _gdsl_bstree_search (const _gdsl_bstree_t T, 00366 const gdsl_compare_func_t COMP_F, 00367 const gdsl_element_t VALUE 00368 ); 00369 00386 extern _gdsl_bstree_t 00387 _gdsl_bstree_search_next (const _gdsl_bstree_t T, 00388 const gdsl_compare_func_t COMP_F, 00389 const gdsl_element_t VALUE 00390 ); 00391 00392 /******************************************************************************/ 00393 /* Parse functions of low-level binary search trees */ 00394 /******************************************************************************/ 00395 00414 extern _gdsl_bstree_t 00415 _gdsl_bstree_map_prefix (const _gdsl_bstree_t T, 00416 const _gdsl_bstree_map_func_t MAP_F, 00417 void* USER_DATA 00418 ); 00419 00438 extern _gdsl_bstree_t 00439 _gdsl_bstree_map_infix (const _gdsl_bstree_t T, 00440 const _gdsl_bstree_map_func_t MAP_F, 00441 void* USER_DATA 00442 ); 00443 00462 extern _gdsl_bstree_t 00463 _gdsl_bstree_map_postfix (const _gdsl_bstree_t T, 00464 const _gdsl_bstree_map_func_t MAP_F, 00465 void* USER_DATA 00466 ); 00467 00468 /******************************************************************************/ 00469 /* Input/output functions of low-level binary search trees */ 00470 /******************************************************************************/ 00471 00489 extern void 00490 _gdsl_bstree_write (const _gdsl_bstree_t T, 00491 const _gdsl_bstree_write_func_t WRITE_F, 00492 FILE* OUTPUT_FILE, 00493 void* USER_DATA 00494 ); 00495 00515 extern void 00516 _gdsl_bstree_write_xml (const _gdsl_bstree_t T, 00517 const _gdsl_bstree_write_func_t WRITE_F, 00518 FILE* OUTPUT_FILE, 00519 void* USER_DATA 00520 ); 00521 00540 extern void 00541 _gdsl_bstree_dump (const _gdsl_bstree_t T, 00542 const _gdsl_bstree_write_func_t WRITE_F, 00543 FILE* OUTPUT_FILE, 00544 void* USER_DATA 00545 ); 00546 00552 #ifdef __cplusplus 00553 } 00554 #endif /* __cplusplus */ 00555 00556 00557 #endif /* _GDSL_BSTREE_H_ */ 00558 00559