gdsl
1.8
|
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_rbtree.h,v $ 00021 * $Revision: 1.21 $ 00022 * $Date: 2015/02/17 12:22:57 $ 00023 */ 00024 00029 #ifndef _GDSL_RBTREE_H_ 00030 #define _GDSL_RBTREE_H_ 00031 00032 00033 #include "gdsl_types.h" 00034 #include "_gdsl_bintree.h" 00035 #include "gdsl_macros.h" 00036 00037 00038 #ifdef __cplusplus 00039 extern "C" 00040 { 00041 #endif /* __cplusplus */ 00042 00043 00055 typedef struct gdsl_rbtree* gdsl_rbtree_t; 00056 00057 /******************************************************************************/ 00058 /* Management functions of red-black trees */ 00059 /******************************************************************************/ 00060 00084 extern gdsl_rbtree_t 00085 gdsl_rbtree_alloc (const char* NAME, 00086 gdsl_alloc_func_t ALLOC_F, 00087 gdsl_free_func_t FREE_F, 00088 gdsl_compare_func_t COMP_F 00089 ); 00090 00104 extern void 00105 gdsl_rbtree_free (gdsl_rbtree_t T 00106 ); 00107 00120 extern void 00121 gdsl_rbtree_flush (gdsl_rbtree_t T 00122 ); 00123 00124 /******************************************************************************/ 00125 /* Consultation functions of red-black trees */ 00126 /******************************************************************************/ 00127 00137 extern char* 00138 gdsl_rbtree_get_name (const gdsl_rbtree_t T 00139 ); 00140 00149 extern bool 00150 gdsl_rbtree_is_empty (const gdsl_rbtree_t T 00151 ); 00152 00160 extern gdsl_element_t 00161 gdsl_rbtree_get_root (const gdsl_rbtree_t T 00162 ); 00163 00172 extern ulong 00173 gdsl_rbtree_get_size (const gdsl_rbtree_t T 00174 ); 00175 00184 extern ulong 00185 gdsl_rbtree_height (const gdsl_rbtree_t T 00186 ); 00187 00188 /******************************************************************************/ 00189 /* Modification functions of red-black trees */ 00190 /******************************************************************************/ 00191 00205 extern gdsl_rbtree_t 00206 gdsl_rbtree_set_name (gdsl_rbtree_t T, 00207 const char* NEW_NAME 00208 ); 00209 00232 extern gdsl_element_t 00233 gdsl_rbtree_insert (gdsl_rbtree_t T, 00234 void* VALUE, 00235 int* RESULT 00236 ); 00237 00254 extern gdsl_element_t 00255 gdsl_rbtree_remove (gdsl_rbtree_t T, 00256 void* VALUE 00257 ); 00258 00276 extern gdsl_rbtree_t 00277 gdsl_rbtree_delete (gdsl_rbtree_t T, 00278 void* VALUE 00279 ); 00280 00281 /******************************************************************************/ 00282 /* Search functions of red-black trees */ 00283 /******************************************************************************/ 00284 00304 extern gdsl_element_t 00305 gdsl_rbtree_search (const gdsl_rbtree_t T, 00306 gdsl_compare_func_t COMP_F, 00307 void* VALUE 00308 ); 00309 00310 /******************************************************************************/ 00311 /* Parse functions of red-black trees */ 00312 /******************************************************************************/ 00313 00332 extern gdsl_element_t 00333 gdsl_rbtree_map_prefix (const gdsl_rbtree_t T, 00334 gdsl_map_func_t MAP_F, 00335 void* USER_DATA 00336 ); 00337 00356 extern gdsl_element_t 00357 gdsl_rbtree_map_infix (const gdsl_rbtree_t T, 00358 gdsl_map_func_t MAP_F, 00359 void* USER_DATA 00360 ); 00361 00380 extern gdsl_element_t 00381 gdsl_rbtree_map_postfix (const gdsl_rbtree_t T, 00382 gdsl_map_func_t MAP_F, 00383 void* USER_DATA 00384 ); 00385 00386 /******************************************************************************/ 00387 /* Input/output functions of red-black trees */ 00388 /******************************************************************************/ 00389 00406 extern void 00407 gdsl_rbtree_write (const gdsl_rbtree_t T, 00408 gdsl_write_func_t WRITE_F, 00409 FILE* OUTPUT_FILE, 00410 void* USER_DATA 00411 ); 00412 00431 extern void 00432 gdsl_rbtree_write_xml (const gdsl_rbtree_t T, 00433 gdsl_write_func_t WRITE_F, 00434 FILE* OUTPUT_FILE, 00435 void* USER_DATA 00436 ); 00437 00455 extern void 00456 gdsl_rbtree_dump (const gdsl_rbtree_t T, 00457 gdsl_write_func_t WRITE_F, 00458 FILE* OUTPUT_FILE, 00459 void* USER_DATA 00460 ); 00461 00462 /* 00463 * @} 00464 */ 00465 00466 00467 #ifdef __cplusplus 00468 } 00469 #endif /* __cplusplus */ 00470 00471 00472 #endif /* _GDSL_RBTREE_H_ */ 00473 00474