gdsl
1.8
|
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_rbtree.h,v $ 00019 * $Revision: 1.21 $ 00020 * $Date: 2015/02/17 12:22:57 $ 00021 */ 00022 00027 #ifndef _GDSL_RBTREE_H_ 00028 #define _GDSL_RBTREE_H_ 00029 00030 00031 #include "gdsl_types.h" 00032 #include "_gdsl_bintree.h" 00033 #include "gdsl_macros.h" 00034 00035 00036 #ifdef __cplusplus 00037 extern "C" 00038 { 00039 #endif /* __cplusplus */ 00040 00071 typedef struct gdsl_rbtree* gdsl_rbtree_t; 00072 00073 /******************************************************************************/ 00074 /* Management functions of red-black trees */ 00075 /******************************************************************************/ 00076 00100 extern gdsl_rbtree_t 00101 gdsl_rbtree_alloc (const char* NAME, 00102 gdsl_alloc_func_t ALLOC_F, 00103 gdsl_free_func_t FREE_F, 00104 gdsl_compare_func_t COMP_F 00105 ); 00106 00120 extern void 00121 gdsl_rbtree_free (gdsl_rbtree_t T 00122 ); 00123 00136 extern void 00137 gdsl_rbtree_flush (gdsl_rbtree_t T 00138 ); 00139 00140 /******************************************************************************/ 00141 /* Consultation functions of red-black trees */ 00142 /******************************************************************************/ 00143 00153 extern char* 00154 gdsl_rbtree_get_name (const gdsl_rbtree_t T 00155 ); 00156 00165 extern bool 00166 gdsl_rbtree_is_empty (const gdsl_rbtree_t T 00167 ); 00168 00176 extern gdsl_element_t 00177 gdsl_rbtree_get_root (const gdsl_rbtree_t T 00178 ); 00179 00188 extern ulong 00189 gdsl_rbtree_get_size (const gdsl_rbtree_t T 00190 ); 00191 00200 extern ulong 00201 gdsl_rbtree_height (const gdsl_rbtree_t T 00202 ); 00203 00204 /******************************************************************************/ 00205 /* Modification functions of red-black trees */ 00206 /******************************************************************************/ 00207 00221 extern gdsl_rbtree_t 00222 gdsl_rbtree_set_name (gdsl_rbtree_t T, 00223 const char* NEW_NAME 00224 ); 00225 00248 extern gdsl_element_t 00249 gdsl_rbtree_insert (gdsl_rbtree_t T, 00250 void* VALUE, 00251 int* RESULT 00252 ); 00253 00270 extern gdsl_element_t 00271 gdsl_rbtree_remove (gdsl_rbtree_t T, 00272 void* VALUE 00273 ); 00274 00292 extern gdsl_rbtree_t 00293 gdsl_rbtree_delete (gdsl_rbtree_t T, 00294 void* VALUE 00295 ); 00296 00297 /******************************************************************************/ 00298 /* Search functions of red-black trees */ 00299 /******************************************************************************/ 00300 00320 extern gdsl_element_t 00321 gdsl_rbtree_search (const gdsl_rbtree_t T, 00322 gdsl_compare_func_t COMP_F, 00323 void* VALUE 00324 ); 00325 00326 /******************************************************************************/ 00327 /* Parse functions of red-black trees */ 00328 /******************************************************************************/ 00329 00348 extern gdsl_element_t 00349 gdsl_rbtree_map_prefix (const gdsl_rbtree_t T, 00350 gdsl_map_func_t MAP_F, 00351 void* USER_DATA 00352 ); 00353 00372 extern gdsl_element_t 00373 gdsl_rbtree_map_infix (const gdsl_rbtree_t T, 00374 gdsl_map_func_t MAP_F, 00375 void* USER_DATA 00376 ); 00377 00396 extern gdsl_element_t 00397 gdsl_rbtree_map_postfix (const gdsl_rbtree_t T, 00398 gdsl_map_func_t MAP_F, 00399 void* USER_DATA 00400 ); 00401 00402 /******************************************************************************/ 00403 /* Input/output functions of red-black trees */ 00404 /******************************************************************************/ 00405 00422 extern void 00423 gdsl_rbtree_write (const gdsl_rbtree_t T, 00424 gdsl_write_func_t WRITE_F, 00425 FILE* OUTPUT_FILE, 00426 void* USER_DATA 00427 ); 00428 00447 extern void 00448 gdsl_rbtree_write_xml (const gdsl_rbtree_t T, 00449 gdsl_write_func_t WRITE_F, 00450 FILE* OUTPUT_FILE, 00451 void* USER_DATA 00452 ); 00453 00471 extern void 00472 gdsl_rbtree_dump (const gdsl_rbtree_t T, 00473 gdsl_write_func_t WRITE_F, 00474 FILE* OUTPUT_FILE, 00475 void* USER_DATA 00476 ); 00477 00483 #ifdef __cplusplus 00484 } 00485 #endif /* __cplusplus */ 00486 00487 00488 #endif /* _GDSL_RBTREE_H_ */ 00489 00490