gdsl  1.8
_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-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