gdsl
1.7
|
00001 /* 00002 * This file is part of the Generic Data Structures Library (GDSL). 00003 * Copyright (C) 1998-2006 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.29 $ 00022 * $Date: 2006/03/04 16:32:05 $ 00023 */ 00024 00025 00026 #ifndef __GDSL_BINTREE_H_ 00027 #define __GDSL_BINTREE_H_ 00028 00029 00030 #include <stdio.h> 00031 00032 00033 #include "gdsl_types.h" 00034 #include "gdsl_macros.h" 00035 00036 00037 #if __cplusplus 00038 extern "C" 00039 { 00040 #endif /* __cplusplus */ 00041 00042 00054 typedef struct _gdsl_bintree* _gdsl_bintree_t; 00055 00063 typedef int (* _gdsl_bintree_map_func_t) (const _gdsl_bintree_t TREE, 00064 void* USER_DATA 00065 ); 00066 00073 typedef void (* _gdsl_bintree_write_func_t) (const _gdsl_bintree_t TREE, 00074 FILE* OUTPUT_FILE, 00075 void* USER_DATA 00076 ); 00077 00078 /******************************************************************************/ 00079 /* Management functions of low-level binary trees */ 00080 /******************************************************************************/ 00081 00097 extern _gdsl_bintree_t 00098 _gdsl_bintree_alloc (const gdsl_element_t E, 00099 const _gdsl_bintree_t LEFT, 00100 const _gdsl_bintree_t RIGHT 00101 ); 00102 00116 extern void 00117 _gdsl_bintree_free (_gdsl_bintree_t T, 00118 const gdsl_free_func_t FREE_F 00119 ); 00120 00138 extern _gdsl_bintree_t 00139 _gdsl_bintree_copy (const _gdsl_bintree_t T, 00140 const gdsl_copy_func_t COPY_F 00141 ); 00142 00143 /******************************************************************************/ 00144 /* Consultation functions of low-level binary trees */ 00145 /******************************************************************************/ 00146 00157 extern bool 00158 _gdsl_bintree_is_empty (const _gdsl_bintree_t T 00159 ); 00160 00171 extern bool 00172 _gdsl_bintree_is_leaf (const _gdsl_bintree_t T 00173 ); 00174 00185 extern bool 00186 _gdsl_bintree_is_root (const _gdsl_bintree_t T 00187 ); 00188 00197 extern gdsl_element_t 00198 _gdsl_bintree_get_content (const _gdsl_bintree_t T 00199 ); 00200 00211 extern _gdsl_bintree_t 00212 _gdsl_bintree_get_parent (const _gdsl_bintree_t T 00213 ); 00214 00230 extern _gdsl_bintree_t 00231 _gdsl_bintree_get_left (const _gdsl_bintree_t T 00232 ); 00233 00249 extern _gdsl_bintree_t 00250 _gdsl_bintree_get_right (const _gdsl_bintree_t T 00251 ); 00252 00261 extern _gdsl_bintree_t* 00262 _gdsl_bintree_get_left_ref (const _gdsl_bintree_t T 00263 ); 00264 00273 extern _gdsl_bintree_t* 00274 _gdsl_bintree_get_right_ref (const _gdsl_bintree_t T 00275 ); 00276 00288 extern ulong 00289 _gdsl_bintree_get_height (const _gdsl_bintree_t T 00290 ); 00291 00300 extern ulong 00301 _gdsl_bintree_get_size (const _gdsl_bintree_t T 00302 ); 00303 00304 /******************************************************************************/ 00305 /* Modification functions of low-level binary trees */ 00306 /******************************************************************************/ 00307 00319 extern void 00320 _gdsl_bintree_set_content (_gdsl_bintree_t T, 00321 const gdsl_element_t E 00322 ); 00323 00335 extern void 00336 _gdsl_bintree_set_parent (_gdsl_bintree_t T, 00337 const _gdsl_bintree_t P 00338 ); 00339 00353 extern void 00354 _gdsl_bintree_set_left (_gdsl_bintree_t T, 00355 const _gdsl_bintree_t L 00356 ); 00357 00371 extern void 00372 _gdsl_bintree_set_right (_gdsl_bintree_t T, 00373 const _gdsl_bintree_t R 00374 ); 00375 00376 /******************************************************************************/ 00377 /* Rotation functions of low-level binary trees */ 00378 /******************************************************************************/ 00379 00393 extern _gdsl_bintree_t 00394 _gdsl_bintree_rotate_left (_gdsl_bintree_t* T 00395 ); 00396 00410 extern _gdsl_bintree_t 00411 _gdsl_bintree_rotate_right (_gdsl_bintree_t* T 00412 ); 00413 00427 extern _gdsl_bintree_t 00428 _gdsl_bintree_rotate_left_right (_gdsl_bintree_t* T 00429 ); 00430 00444 extern _gdsl_bintree_t 00445 _gdsl_bintree_rotate_right_left (_gdsl_bintree_t* T 00446 ); 00447 00448 /******************************************************************************/ 00449 /* Parse functions of low-level binary trees */ 00450 /******************************************************************************/ 00451 00470 extern _gdsl_bintree_t 00471 _gdsl_bintree_map_prefix (const _gdsl_bintree_t T, 00472 const _gdsl_bintree_map_func_t MAP_F, 00473 void* USER_DATA 00474 ); 00475 00494 extern _gdsl_bintree_t 00495 _gdsl_bintree_map_infix (const _gdsl_bintree_t T, 00496 const _gdsl_bintree_map_func_t MAP_F, 00497 void* USER_DATA 00498 ); 00499 00518 extern _gdsl_bintree_t 00519 _gdsl_bintree_map_postfix (const _gdsl_bintree_t T, 00520 const _gdsl_bintree_map_func_t MAP_F, 00521 void* USER_DATA 00522 ); 00523 00524 /******************************************************************************/ 00525 /* Input/output functions of low-level binary trees */ 00526 /******************************************************************************/ 00527 00544 extern void 00545 _gdsl_bintree_write (const _gdsl_bintree_t T, 00546 const _gdsl_bintree_write_func_t WRITE_F, 00547 FILE* OUTPUT_FILE, 00548 void* USER_DATA 00549 ); 00550 00568 extern void 00569 _gdsl_bintree_write_xml (const _gdsl_bintree_t T, 00570 const _gdsl_bintree_write_func_t WRITE_F, 00571 FILE* OUTPUT_FILE, 00572 void* USER_DATA 00573 ); 00574 00592 extern void 00593 _gdsl_bintree_dump (const _gdsl_bintree_t T, 00594 const _gdsl_bintree_write_func_t WRITE_F, 00595 FILE* OUTPUT_FILE, 00596 void* USER_DATA 00597 ); 00598 00599 /* 00600 * @} 00601 */ 00602 00603 00604 #ifdef __cplusplus 00605 } 00606 #endif /* __cplusplus */ 00607 00608 00609 #endif /* __GDSL_BINTREE_H_ */ 00610 00611