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_bintree.h,v $ 00021 * $Revision: 1.30 $ 00022 * $Date: 2015/02/17 12:22:55 $ 00023 */ 00024 00029 #ifndef __GDSL_BINTREE_H_ 00030 #define __GDSL_BINTREE_H_ 00031 00032 00033 #include <stdio.h> 00034 00035 00036 #include "gdsl_types.h" 00037 #include "gdsl_macros.h" 00038 00039 00040 #if __cplusplus 00041 extern "C" 00042 { 00043 #endif /* __cplusplus */ 00044 00045 00057 typedef struct _gdsl_bintree* _gdsl_bintree_t; 00058 00066 typedef int (* _gdsl_bintree_map_func_t) (const _gdsl_bintree_t TREE, 00067 void* USER_DATA 00068 ); 00069 00076 typedef void (* _gdsl_bintree_write_func_t) (const _gdsl_bintree_t TREE, 00077 FILE* OUTPUT_FILE, 00078 void* USER_DATA 00079 ); 00080 00081 /******************************************************************************/ 00082 /* Management functions of low-level binary trees */ 00083 /******************************************************************************/ 00084 00100 extern _gdsl_bintree_t 00101 _gdsl_bintree_alloc (const gdsl_element_t E, 00102 const _gdsl_bintree_t LEFT, 00103 const _gdsl_bintree_t RIGHT 00104 ); 00105 00119 extern void 00120 _gdsl_bintree_free (_gdsl_bintree_t T, 00121 const gdsl_free_func_t FREE_F 00122 ); 00123 00141 extern _gdsl_bintree_t 00142 _gdsl_bintree_copy (const _gdsl_bintree_t T, 00143 const gdsl_copy_func_t COPY_F 00144 ); 00145 00146 /******************************************************************************/ 00147 /* Consultation functions of low-level binary trees */ 00148 /******************************************************************************/ 00149 00160 extern bool 00161 _gdsl_bintree_is_empty (const _gdsl_bintree_t T 00162 ); 00163 00174 extern bool 00175 _gdsl_bintree_is_leaf (const _gdsl_bintree_t T 00176 ); 00177 00188 extern bool 00189 _gdsl_bintree_is_root (const _gdsl_bintree_t T 00190 ); 00191 00200 extern gdsl_element_t 00201 _gdsl_bintree_get_content (const _gdsl_bintree_t T 00202 ); 00203 00214 extern _gdsl_bintree_t 00215 _gdsl_bintree_get_parent (const _gdsl_bintree_t T 00216 ); 00217 00233 extern _gdsl_bintree_t 00234 _gdsl_bintree_get_left (const _gdsl_bintree_t T 00235 ); 00236 00252 extern _gdsl_bintree_t 00253 _gdsl_bintree_get_right (const _gdsl_bintree_t T 00254 ); 00255 00264 extern _gdsl_bintree_t* 00265 _gdsl_bintree_get_left_ref (const _gdsl_bintree_t T 00266 ); 00267 00276 extern _gdsl_bintree_t* 00277 _gdsl_bintree_get_right_ref (const _gdsl_bintree_t T 00278 ); 00279 00291 extern ulong 00292 _gdsl_bintree_get_height (const _gdsl_bintree_t T 00293 ); 00294 00303 extern ulong 00304 _gdsl_bintree_get_size (const _gdsl_bintree_t T 00305 ); 00306 00307 /******************************************************************************/ 00308 /* Modification functions of low-level binary trees */ 00309 /******************************************************************************/ 00310 00322 extern void 00323 _gdsl_bintree_set_content (_gdsl_bintree_t T, 00324 const gdsl_element_t E 00325 ); 00326 00338 extern void 00339 _gdsl_bintree_set_parent (_gdsl_bintree_t T, 00340 const _gdsl_bintree_t P 00341 ); 00342 00356 extern void 00357 _gdsl_bintree_set_left (_gdsl_bintree_t T, 00358 const _gdsl_bintree_t L 00359 ); 00360 00374 extern void 00375 _gdsl_bintree_set_right (_gdsl_bintree_t T, 00376 const _gdsl_bintree_t R 00377 ); 00378 00379 /******************************************************************************/ 00380 /* Rotation functions of low-level binary trees */ 00381 /******************************************************************************/ 00382 00396 extern _gdsl_bintree_t 00397 _gdsl_bintree_rotate_left (_gdsl_bintree_t* T 00398 ); 00399 00413 extern _gdsl_bintree_t 00414 _gdsl_bintree_rotate_right (_gdsl_bintree_t* T 00415 ); 00416 00430 extern _gdsl_bintree_t 00431 _gdsl_bintree_rotate_left_right (_gdsl_bintree_t* T 00432 ); 00433 00447 extern _gdsl_bintree_t 00448 _gdsl_bintree_rotate_right_left (_gdsl_bintree_t* T 00449 ); 00450 00451 /******************************************************************************/ 00452 /* Parse functions of low-level binary trees */ 00453 /******************************************************************************/ 00454 00473 extern _gdsl_bintree_t 00474 _gdsl_bintree_map_prefix (const _gdsl_bintree_t T, 00475 const _gdsl_bintree_map_func_t MAP_F, 00476 void* USER_DATA 00477 ); 00478 00497 extern _gdsl_bintree_t 00498 _gdsl_bintree_map_infix (const _gdsl_bintree_t T, 00499 const _gdsl_bintree_map_func_t MAP_F, 00500 void* USER_DATA 00501 ); 00502 00521 extern _gdsl_bintree_t 00522 _gdsl_bintree_map_postfix (const _gdsl_bintree_t T, 00523 const _gdsl_bintree_map_func_t MAP_F, 00524 void* USER_DATA 00525 ); 00526 00527 /******************************************************************************/ 00528 /* Input/output functions of low-level binary trees */ 00529 /******************************************************************************/ 00530 00547 extern void 00548 _gdsl_bintree_write (const _gdsl_bintree_t T, 00549 const _gdsl_bintree_write_func_t WRITE_F, 00550 FILE* OUTPUT_FILE, 00551 void* USER_DATA 00552 ); 00553 00571 extern void 00572 _gdsl_bintree_write_xml (const _gdsl_bintree_t T, 00573 const _gdsl_bintree_write_func_t WRITE_F, 00574 FILE* OUTPUT_FILE, 00575 void* USER_DATA 00576 ); 00577 00595 extern void 00596 _gdsl_bintree_dump (const _gdsl_bintree_t T, 00597 const _gdsl_bintree_write_func_t WRITE_F, 00598 FILE* OUTPUT_FILE, 00599 void* USER_DATA 00600 ); 00601 00602 /* 00603 * @} 00604 */ 00605 00606 00607 #ifdef __cplusplus 00608 } 00609 #endif /* __cplusplus */ 00610 00611 00612 #endif /* __GDSL_BINTREE_H_ */ 00613 00614