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_bintree.h,v $ 00019 * $Revision: 1.30 $ 00020 * $Date: 2015/02/17 12:22:55 $ 00021 */ 00022 00027 #ifndef __GDSL_BINTREE_H_ 00028 #define __GDSL_BINTREE_H_ 00029 00030 00031 #include <stdio.h> 00032 00033 00034 #include "gdsl_types.h" 00035 #include "gdsl_macros.h" 00036 00037 00038 #if __cplusplus 00039 extern "C" 00040 { 00041 #endif /* __cplusplus */ 00042 00073 typedef struct _gdsl_bintree* _gdsl_bintree_t; 00074 00082 typedef int (* _gdsl_bintree_map_func_t) (const _gdsl_bintree_t TREE, 00083 void* USER_DATA 00084 ); 00085 00092 typedef void (* _gdsl_bintree_write_func_t) (const _gdsl_bintree_t TREE, 00093 FILE* OUTPUT_FILE, 00094 void* USER_DATA 00095 ); 00096 00097 /******************************************************************************/ 00098 /* Management functions of low-level binary trees */ 00099 /******************************************************************************/ 00100 00116 extern _gdsl_bintree_t 00117 _gdsl_bintree_alloc (const gdsl_element_t E, 00118 const _gdsl_bintree_t LEFT, 00119 const _gdsl_bintree_t RIGHT 00120 ); 00121 00135 extern void 00136 _gdsl_bintree_free (_gdsl_bintree_t T, 00137 const gdsl_free_func_t FREE_F 00138 ); 00139 00157 extern _gdsl_bintree_t 00158 _gdsl_bintree_copy (const _gdsl_bintree_t T, 00159 const gdsl_copy_func_t COPY_F 00160 ); 00161 00162 /******************************************************************************/ 00163 /* Consultation functions of low-level binary trees */ 00164 /******************************************************************************/ 00165 00176 extern bool 00177 _gdsl_bintree_is_empty (const _gdsl_bintree_t T 00178 ); 00179 00190 extern bool 00191 _gdsl_bintree_is_leaf (const _gdsl_bintree_t T 00192 ); 00193 00204 extern bool 00205 _gdsl_bintree_is_root (const _gdsl_bintree_t T 00206 ); 00207 00216 extern gdsl_element_t 00217 _gdsl_bintree_get_content (const _gdsl_bintree_t T 00218 ); 00219 00230 extern _gdsl_bintree_t 00231 _gdsl_bintree_get_parent (const _gdsl_bintree_t T 00232 ); 00233 00249 extern _gdsl_bintree_t 00250 _gdsl_bintree_get_left (const _gdsl_bintree_t T 00251 ); 00252 00268 extern _gdsl_bintree_t 00269 _gdsl_bintree_get_right (const _gdsl_bintree_t T 00270 ); 00271 00280 extern _gdsl_bintree_t* 00281 _gdsl_bintree_get_left_ref (const _gdsl_bintree_t T 00282 ); 00283 00292 extern _gdsl_bintree_t* 00293 _gdsl_bintree_get_right_ref (const _gdsl_bintree_t T 00294 ); 00295 00307 extern ulong 00308 _gdsl_bintree_get_height (const _gdsl_bintree_t T 00309 ); 00310 00319 extern ulong 00320 _gdsl_bintree_get_size (const _gdsl_bintree_t T 00321 ); 00322 00323 /******************************************************************************/ 00324 /* Modification functions of low-level binary trees */ 00325 /******************************************************************************/ 00326 00338 extern void 00339 _gdsl_bintree_set_content (_gdsl_bintree_t T, 00340 const gdsl_element_t E 00341 ); 00342 00354 extern void 00355 _gdsl_bintree_set_parent (_gdsl_bintree_t T, 00356 const _gdsl_bintree_t P 00357 ); 00358 00372 extern void 00373 _gdsl_bintree_set_left (_gdsl_bintree_t T, 00374 const _gdsl_bintree_t L 00375 ); 00376 00390 extern void 00391 _gdsl_bintree_set_right (_gdsl_bintree_t T, 00392 const _gdsl_bintree_t R 00393 ); 00394 00395 /******************************************************************************/ 00396 /* Rotation functions of low-level binary trees */ 00397 /******************************************************************************/ 00398 00412 extern _gdsl_bintree_t 00413 _gdsl_bintree_rotate_left (_gdsl_bintree_t* T 00414 ); 00415 00429 extern _gdsl_bintree_t 00430 _gdsl_bintree_rotate_right (_gdsl_bintree_t* T 00431 ); 00432 00446 extern _gdsl_bintree_t 00447 _gdsl_bintree_rotate_left_right (_gdsl_bintree_t* T 00448 ); 00449 00463 extern _gdsl_bintree_t 00464 _gdsl_bintree_rotate_right_left (_gdsl_bintree_t* T 00465 ); 00466 00467 /******************************************************************************/ 00468 /* Parse functions of low-level binary trees */ 00469 /******************************************************************************/ 00470 00489 extern _gdsl_bintree_t 00490 _gdsl_bintree_map_prefix (const _gdsl_bintree_t T, 00491 const _gdsl_bintree_map_func_t MAP_F, 00492 void* USER_DATA 00493 ); 00494 00513 extern _gdsl_bintree_t 00514 _gdsl_bintree_map_infix (const _gdsl_bintree_t T, 00515 const _gdsl_bintree_map_func_t MAP_F, 00516 void* USER_DATA 00517 ); 00518 00537 extern _gdsl_bintree_t 00538 _gdsl_bintree_map_postfix (const _gdsl_bintree_t T, 00539 const _gdsl_bintree_map_func_t MAP_F, 00540 void* USER_DATA 00541 ); 00542 00543 /******************************************************************************/ 00544 /* Input/output functions of low-level binary trees */ 00545 /******************************************************************************/ 00546 00563 extern void 00564 _gdsl_bintree_write (const _gdsl_bintree_t T, 00565 const _gdsl_bintree_write_func_t WRITE_F, 00566 FILE* OUTPUT_FILE, 00567 void* USER_DATA 00568 ); 00569 00587 extern void 00588 _gdsl_bintree_write_xml (const _gdsl_bintree_t T, 00589 const _gdsl_bintree_write_func_t WRITE_F, 00590 FILE* OUTPUT_FILE, 00591 void* USER_DATA 00592 ); 00593 00611 extern void 00612 _gdsl_bintree_dump (const _gdsl_bintree_t T, 00613 const _gdsl_bintree_write_func_t WRITE_F, 00614 FILE* OUTPUT_FILE, 00615 void* USER_DATA 00616 ); 00617 00623 #ifdef __cplusplus 00624 } 00625 #endif /* __cplusplus */ 00626 00627 00628 #endif /* __GDSL_BINTREE_H_ */ 00629 00630