1 /* 2 * 3 * Copyright (c) 1994 4 * Hewlett-Packard Company 5 * 6 * Permission to use, copy, modify, distribute and sell this software 7 * and its documentation for any purpose is hereby granted without fee, 8 * provided that the above copyright notice appear in all copies and 9 * that both that copyright notice and this permission notice appear 10 * in supporting documentation. Hewlett-Packard Company makes no 11 * representations about the suitability of this software for any 12 * purpose. It is provided "as is" without express or implied warranty. 13 * 14 * 15 * Copyright (c) 1996 16 * Silicon Graphics Computer Systems, Inc. 17 * 18 * Permission to use, copy, modify, distribute and sell this software 19 * and its documentation for any purpose is hereby granted without fee, 20 * provided that the above copyright notice appear in all copies and 21 * that both that copyright notice and this permission notice appear 22 * in supporting documentation. Silicon Graphics makes no 23 * representations about the suitability of this software for any 24 * purpose. It is provided "as is" without express or implied warranty. 25 */ 26 27 /* 28 Copyright (c) 2007 Lao wen bo 29 30 This software is provided 'as-is', without any express or implied 31 warranty. In no event will the authors be held liable for any damages 32 arising from the use of this software. 33 34 Permission is granted to anyone to use this software for any purpose, 35 including commercial applications, and to alter it and redistribute it 36 freely, subject to the following restrictions: 37 38 1. The origin of this software must not be misrepresented; you must not 39 claim that you wrote the original software. If you use this software 40 in a product, an acknowledgment in the product documentation would be 41 appreciated but is not required. 42 43 2. Altered source versions must be plainly marked as such, and must not be 44 misrepresented as being the original software. 45 46 3. This notice may not be removed or altered from any source 47 distribution. 48 49 Lao wen bo 50 viewpl(at)gmail.com 51 */ 52 53 /* 54 NOTE: This is an internal header file, You should not attempt to use it directly. 55 */ 56 57 #ifndef _C_TREE_H 58 #define _C_TREE_H 59 60 #include "c_def.h" 61 #include "c_iterator.h" 62 #include "c_memory.h" 63 #include "c_pair.h" 64 #include "c_function.h" 65 66 #define c_rb_tree _c_rb_tree 67 #define c_prb_tree _c_prb_tree 68 #define c_rb_tree_create __c_rb_tree 69 #define c_rb_tree_destroy __c_eert_br 70 #define c_rb_tree_assign _c_rb_tree_assign 71 #define c_rb_tree_begin _c_rb_tree_begin 72 #define c_rb_tree_end _c_rb_tree_end 73 #define c_rb_tree_rbegin _c_rb_tree_rbegin 74 #define c_rb_tree_rend _c_rb_tree_rend 75 #define c_rb_tree_empty _c_rb_tree_empty 76 #define c_rb_tree_size _c_rb_tree_size 77 #define c_rb_tree_max_size _c_rb_tree_max_size 78 #define c_rb_tree_swap _c_rb_tree_swap 79 #define c_rb_tree_insert_unique _c_rb_tree_insert_unique 80 #define c_rb_tree_insert_equal _c_rb_tree_insert_equal 81 #define c_rb_tree_insert_unique1 _c_rb_tree_insert_unique1 82 #define c_rb_tree_insert_equal1 _c_rb_tree_insert_equal1 83 #define c_rb_tree_insert_unique2 _c_rb_tree_insert_unique2 84 #define c_rb_tree_insert_equal2 _c_rb_tree_insert_equal2 85 #define c_rb_tree_erase _c_rb_tree_erase 86 #define c_rb_tree_erase1 _c_rb_tree_erase1 87 #define c_rb_tree_erase2 _c_rb_tree_erase2 88 #define c_rb_tree_clear _c_rb_tree_clear 89 #define c_rb_tree_find _c_rb_tree_find 90 #define c_rb_tree_count _c_rb_tree_count 91 #define c_rb_tree_lower_bound _c_rb_tree_lower_bound 92 #define c_rb_tree_upper_bound _c_rb_tree_upper_bound 93 #define c_rb_tree_equal_range _c_rb_tree_equal_range 94 #define c_rb_tree_less _c_rb_tree_less 95 #define c_rb_tree_equal _c_rb_tree_equal 96 97 98 typedef c_bool _c_rb_tree_color_type; 99 typedef value_type key_type; 100 typedef struct _c_rb_tree_node _c_rb_tree_node, * _c_prb_tree_node; 101 typedef _c_rb_tree_color_type _color_type; 102 typedef _c_rb_tree_node * _base_ptr; 103 typedef _base_ptr _link_type; 104 105 struct _c_rb_tree_node 106 { 107 _color_type _A_color; 108 _base_ptr _A_parent; 109 _base_ptr _A_left; 110 _base_ptr _A_right; 111 value_type _A_value_field; 112 }; 113 114 typedef struct c_rb_tree 115 { 116 _base_ptr _A_header; 117 size_type _A_node_count; 118 COMPARER _A_key_compare; 119 c_unary_function _A_keyofvalue; 120 }c_rb_tree, * c_prb_tree; 121 122 123 124 void __c_rb_tree(c_prb_tree thiz, COMPARER pcmp); 125 void __c_eert_br(c_prb_tree thiz); 126 c_prb_tree c_rb_tree_assign(c_prb_tree thiz, const c_prb_tree T); 127 c_iterator c_rb_tree_begin(c_prb_tree thiz); 128 c_iterator c_rb_tree_end(c_prb_tree thiz); 129 c_reverse_iterator c_rb_tree_rbegin(c_prb_tree thiz); 130 c_reverse_iterator c_rb_tree_rend(c_prb_tree thiz); 131 c_bool c_rb_tree_empty(c_prb_tree thiz); 132 size_type c_rb_tree_size(c_prb_tree thiz); 133 size_type c_rb_tree_max_size(c_prb_tree thiz); 134 void c_rb_tree_swap(c_prb_tree thiz, c_prb_tree T); 135 c_iter_bool_pair c_rb_tree_insert_unique(c_prb_tree thiz, const value_type val); 136 c_iterator c_rb_tree_insert_equal(c_prb_tree thiz, const value_type val); 137 c_iterator c_rb_tree_insert_unique1(c_prb_tree thiz, c_iterator position, const value_type val); 138 c_iterator c_rb_tree_insert_equal1(c_prb_tree thiz, c_iterator position, const value_type val); 139 void c_rb_tree_insert_unique2(c_prb_tree thiz, c_iterator first, c_iterator last); 140 void c_rb_tree_insert_equal2(c_prb_tree thiz, c_iterator first, c_iterator last); 141 void c_rb_tree_erase(c_prb_tree thiz, c_iterator position); 142 size_type c_rb_tree_erase1(c_prb_tree thiz, key_type key); 143 void c_rb_tree_erase2(c_prb_tree thiz, c_iterator first, c_iterator last); 144 void c_rb_tree_clear(c_prb_tree thiz); 145 c_iterator c_rb_tree_find(c_prb_tree thiz, key_type key); 146 size_type c_rb_tree_count(c_prb_tree thiz, key_type key); 147 c_iterator c_rb_tree_lower_bound(c_prb_tree thiz, key_type key); 148 c_iterator c_rb_tree_upper_bound(c_prb_tree thiz, key_type key); 149 c_iter_iter_pair c_rb_tree_equal_range(c_prb_tree thiz, key_type key); 150 c_bool c_rb_tree_less(c_prb_tree thiz, const c_prb_tree T, COMPARER cmp); 151 c_bool c_rb_tree_equal(c_prb_tree thiz, const c_prb_tree T, COMPARER cmp); 152 c_bool __c_rb_tree_verify(c_prb_tree thiz); 153 154 155 #endif /* _C_TREE_H */ 156 157 158 159 160 161