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-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