gdsl  1.6
_gdsl_bintree.h
Go to the documentation of this file.
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_8h_source.html,v $
00021  * $Revision: 1.2 $
00022  * $Date: 2012/08/21 14:01:03 $
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