]>
Commit | Line | Data |
---|---|---|
36fed23c | 1 | // -*- C++ -*- |
2 | ||
f1717362 | 3 | // Copyright (C) 2005-2016 Free Software Foundation, Inc. |
36fed23c | 4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the terms | |
7 | // of the GNU General Public License as published by the Free Software | |
6bc9506f | 8 | // Foundation; either version 3, or (at your option) any later |
36fed23c | 9 | // version. |
10 | ||
11 | // This library is distributed in the hope that it will be useful, but | |
12 | // WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | // General Public License for more details. | |
15 | ||
6bc9506f | 16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
36fed23c | 19 | |
6bc9506f | 20 | // You should have received a copy of the GNU General Public License and |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
36fed23c | 24 | |
25 | // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. | |
26 | ||
27 | // Permission to use, copy, modify, sell, and distribute this software | |
28 | // is hereby granted without fee, provided that the above copyright | |
29 | // notice appears in all copies, and that both that copyright notice | |
30 | // and this permission notice appear in supporting documentation. None | |
31 | // of the above authors, nor IBM Haifa Research Laboratories, make any | |
32 | // representation about the suitability of this software for any | |
33 | // purpose. It is provided "as is" without express or implied | |
34 | // warranty. | |
35 | ||
36 | /** | |
4f4a327e | 37 | * @file thin_heap_/thin_heap_.hpp |
36fed23c | 38 | * Contains an implementation class for a thin heap. |
39 | */ | |
40 | ||
41 | #ifndef PB_DS_THIN_HEAP_HPP | |
42 | #define PB_DS_THIN_HEAP_HPP | |
43 | ||
36fed23c | 44 | #include <algorithm> |
45 | #include <ext/pb_ds/detail/cond_dealtor.hpp> | |
46 | #include <ext/pb_ds/detail/type_utils.hpp> | |
47 | #include <ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp> | |
2b31bec4 | 48 | #include <debug/debug.h> |
36fed23c | 49 | |
b34535d7 | 50 | namespace __gnu_pbds |
36fed23c | 51 | { |
52 | namespace detail | |
53 | { | |
2b31bec4 | 54 | #define PB_DS_CLASS_T_DEC \ |
4f4a327e | 55 | template<typename Value_Type, typename Cmp_Fn, typename _Alloc> |
36fed23c | 56 | |
2b31bec4 | 57 | #define PB_DS_CLASS_C_DEC \ |
4f4a327e | 58 | thin_heap<Value_Type, Cmp_Fn, _Alloc> |
36fed23c | 59 | |
2b31bec4 | 60 | #ifdef _GLIBCXX_DEBUG |
4f4a327e | 61 | #define PB_DS_BASE_T_P \ |
62 | <Value_Type, Cmp_Fn, typename _Alloc::size_type, _Alloc, true> | |
63 | #else | |
64 | #define PB_DS_BASE_T_P \ | |
65 | <Value_Type, Cmp_Fn, typename _Alloc::size_type, _Alloc> | |
66 | #endif | |
36fed23c | 67 | |
3f2eba6f | 68 | |
36fed23c | 69 | /** |
4f4a327e | 70 | * Thin heap. |
3f2eba6f | 71 | * |
72 | * @ingroup heap-detail | |
4f4a327e | 73 | * |
74 | * See Tarjan and Kaplan. | |
75 | */ | |
76 | template<typename Value_Type, typename Cmp_Fn, typename _Alloc> | |
77 | class thin_heap | |
78 | : public left_child_next_sibling_heap PB_DS_BASE_T_P | |
36fed23c | 79 | { |
36fed23c | 80 | private: |
4f4a327e | 81 | typedef typename _Alloc::template rebind<Value_Type>::other __rebind_a; |
82 | typedef left_child_next_sibling_heap PB_DS_BASE_T_P base_type; | |
36fed23c | 83 | |
84 | protected: | |
4f4a327e | 85 | typedef typename base_type::node node; |
86 | typedef typename base_type::node_pointer node_pointer; | |
87 | typedef typename base_type::node_const_pointer node_const_pointer; | |
36fed23c | 88 | |
89 | public: | |
4f4a327e | 90 | typedef Value_Type value_type; |
91 | typedef Cmp_Fn cmp_fn; | |
92 | typedef _Alloc allocator_type; | |
93 | typedef typename _Alloc::size_type size_type; | |
94 | typedef typename _Alloc::difference_type difference_type; | |
36fed23c | 95 | |
4f4a327e | 96 | typedef typename __rebind_a::pointer pointer; |
97 | typedef typename __rebind_a::const_pointer const_pointer; | |
98 | typedef typename __rebind_a::reference reference; | |
99 | typedef typename __rebind_a::const_reference const_reference; | |
36fed23c | 100 | |
4f4a327e | 101 | typedef typename base_type::point_iterator point_iterator; |
102 | typedef typename base_type::point_const_iterator point_const_iterator; | |
103 | typedef typename base_type::iterator iterator; | |
104 | typedef typename base_type::const_iterator const_iterator; | |
36fed23c | 105 | |
36fed23c | 106 | |
107 | inline point_iterator | |
4f4a327e | 108 | push(const_reference); |
36fed23c | 109 | |
110 | void | |
4f4a327e | 111 | modify(point_iterator, const_reference); |
36fed23c | 112 | |
113 | inline const_reference | |
114 | top() const; | |
115 | ||
116 | void | |
117 | pop(); | |
118 | ||
119 | void | |
4f4a327e | 120 | erase(point_iterator); |
36fed23c | 121 | |
122 | inline void | |
123 | clear(); | |
124 | ||
125 | template<typename Pred> | |
126 | size_type | |
4f4a327e | 127 | erase_if(Pred); |
36fed23c | 128 | |
129 | template<typename Pred> | |
130 | void | |
4f4a327e | 131 | split(Pred, PB_DS_CLASS_C_DEC&); |
36fed23c | 132 | |
133 | void | |
4f4a327e | 134 | join(PB_DS_CLASS_C_DEC&); |
36fed23c | 135 | |
136 | protected: | |
4f4a327e | 137 | thin_heap(); |
36fed23c | 138 | |
4f4a327e | 139 | thin_heap(const Cmp_Fn&); |
36fed23c | 140 | |
4f4a327e | 141 | thin_heap(const PB_DS_CLASS_C_DEC&); |
36fed23c | 142 | |
143 | void | |
4f4a327e | 144 | swap(PB_DS_CLASS_C_DEC&); |
36fed23c | 145 | |
4f4a327e | 146 | ~thin_heap(); |
36fed23c | 147 | |
148 | template<typename It> | |
149 | void | |
4f4a327e | 150 | copy_from_range(It, It); |
36fed23c | 151 | |
2b31bec4 | 152 | #ifdef _GLIBCXX_DEBUG |
36fed23c | 153 | void |
4f4a327e | 154 | assert_valid(const char*, int) const; |
36fed23c | 155 | |
156 | void | |
4f4a327e | 157 | assert_max(const char*, int) const; |
158 | #endif | |
36fed23c | 159 | |
160 | #ifdef PB_DS_THIN_HEAP_TRACE_ | |
36fed23c | 161 | void |
162 | trace() const; | |
4f4a327e | 163 | #endif |
36fed23c | 164 | |
165 | private: | |
166 | enum | |
167 | { | |
168 | max_rank = (sizeof(size_type) << 4) + 2 | |
169 | }; | |
170 | ||
36fed23c | 171 | void |
172 | initialize(); | |
173 | ||
174 | inline void | |
4f4a327e | 175 | update_max(node_pointer); |
36fed23c | 176 | |
177 | inline void | |
4f4a327e | 178 | fix(node_pointer); |
36fed23c | 179 | |
180 | inline void | |
4f4a327e | 181 | fix_root(node_pointer); |
36fed23c | 182 | |
183 | inline void | |
4f4a327e | 184 | fix_sibling_rank_1_unmarked(node_pointer); |
36fed23c | 185 | |
186 | inline void | |
4f4a327e | 187 | fix_sibling_rank_1_marked(node_pointer); |
36fed23c | 188 | |
189 | inline void | |
4f4a327e | 190 | fix_sibling_general_unmarked(node_pointer); |
36fed23c | 191 | |
192 | inline void | |
4f4a327e | 193 | fix_sibling_general_marked(node_pointer); |
36fed23c | 194 | |
195 | inline void | |
4f4a327e | 196 | fix_child(node_pointer); |
36fed23c | 197 | |
198 | inline static void | |
4f4a327e | 199 | make_root(node_pointer); |
36fed23c | 200 | |
201 | inline void | |
4f4a327e | 202 | make_root_and_link(node_pointer); |
36fed23c | 203 | |
204 | inline void | |
205 | remove_max_node(); | |
206 | ||
207 | void | |
208 | to_aux_except_max(); | |
209 | ||
210 | inline void | |
4f4a327e | 211 | add_to_aux(node_pointer); |
36fed23c | 212 | |
213 | inline void | |
214 | make_from_aux(); | |
215 | ||
216 | inline size_type | |
217 | rank_bound(); | |
218 | ||
219 | inline void | |
4f4a327e | 220 | make_child_of(node_pointer, node_pointer); |
36fed23c | 221 | |
222 | inline void | |
4f4a327e | 223 | remove_node(node_pointer); |
36fed23c | 224 | |
225 | inline node_pointer | |
4f4a327e | 226 | join(node_pointer, node_pointer) const; |
36fed23c | 227 | |
2b31bec4 | 228 | #ifdef _GLIBCXX_DEBUG |
36fed23c | 229 | void |
4f4a327e | 230 | assert_node_consistent(node_const_pointer, bool, const char*, int) const; |
36fed23c | 231 | |
232 | void | |
4f4a327e | 233 | assert_aux_null(const char*, int) const; |
234 | #endif | |
36fed23c | 235 | |
4f4a327e | 236 | node_pointer m_p_max; |
237 | node_pointer m_a_aux[max_rank]; | |
36fed23c | 238 | }; |
239 | ||
240 | enum | |
241 | { | |
242 | num_distinct_rank_bounds = 48 | |
243 | }; | |
244 | ||
245 | // Taken from the SGI implementation; acknowledged in the docs. | |
36fed23c | 246 | static const std::size_t g_a_rank_bounds[num_distinct_rank_bounds] = |
247 | { | |
248 | /* Dealing cards... */ | |
249 | /* 0 */ 0ul, | |
250 | /* 1 */ 1ul, | |
251 | /* 2 */ 1ul, | |
252 | /* 3 */ 2ul, | |
253 | /* 4 */ 4ul, | |
254 | /* 5 */ 6ul, | |
255 | /* 6 */ 11ul, | |
256 | /* 7 */ 17ul, | |
257 | /* 8 */ 29ul, | |
258 | /* 9 */ 46ul, | |
259 | /* 10 */ 76ul, | |
260 | /* 11 */ 122ul, | |
261 | /* 12 */ 199ul, | |
262 | /* 13 */ 321ul, | |
263 | /* 14 */ 521ul, | |
264 | /* 15 */ 842ul, | |
265 | /* 16 */ 1364ul, | |
266 | /* 17 */ 2206ul, | |
267 | /* 18 */ 3571ul, | |
268 | /* 19 */ 5777ul, | |
269 | /* 20 */ 9349ul, | |
270 | /* 21 */ 15126ul, | |
271 | /* 22 */ 24476ul, | |
272 | /* 23 */ 39602ul, | |
f30ba9ed | 273 | /* 24 */ 64079ul |
274 | #if __SIZE_MAX__ > 0xfffful | |
275 | , | |
36fed23c | 276 | /* 25 */ 103681ul, |
277 | /* 26 */ 167761ul, | |
278 | /* 27 */ 271442ul, | |
279 | /* 28 */ 439204ul, | |
f30ba9ed | 280 | /* 29 */ 710646ul |
281 | #if __SIZE_MAX__ > 0xffffful | |
282 | , | |
36fed23c | 283 | /* 30 */ 1149851ul, |
284 | /* 31 */ 1860497ul, | |
285 | /* 32 */ 3010349ul, | |
286 | /* 33 */ 4870846ul, | |
287 | /* 34 */ 7881196ul, | |
f30ba9ed | 288 | /* 35 */ 12752042ul |
289 | #if __SIZE_MAX__ > 0xfffffful | |
290 | , | |
36fed23c | 291 | /* 36 */ 20633239ul, |
292 | /* 37 */ 33385282ul, | |
293 | /* 38 */ 54018521ul, | |
294 | /* 39 */ 87403803ul, | |
295 | /* 40 */ 141422324ul, | |
296 | /* 41 */ 228826127ul, | |
297 | /* 42 */ 370248451ul, | |
298 | /* 43 */ 599074578ul, | |
299 | /* 44 */ 969323029ul, | |
300 | /* 45 */ 1568397607ul, | |
301 | /* 46 */ 2537720636ul, | |
302 | /* 47 */ 4106118243ul | |
f30ba9ed | 303 | #endif |
304 | #endif | |
305 | #endif | |
36fed23c | 306 | /* Pot's good, let's play */ |
307 | }; | |
308 | ||
2548203e | 309 | #define PB_DS_ASSERT_NODE_CONSISTENT(_Node, _Bool) \ |
310 | _GLIBCXX_DEBUG_ONLY(assert_node_consistent(_Node, _Bool, \ | |
311 | __FILE__, __LINE__);) | |
312 | ||
4f4a327e | 313 | #define PB_DS_ASSERT_AUX_NULL(X) \ |
2548203e | 314 | _GLIBCXX_DEBUG_ONLY(X.assert_aux_null(__FILE__, __LINE__);) |
315 | ||
36fed23c | 316 | #include <ext/pb_ds/detail/thin_heap_/constructors_destructor_fn_imps.hpp> |
317 | #include <ext/pb_ds/detail/thin_heap_/debug_fn_imps.hpp> | |
318 | #include <ext/pb_ds/detail/thin_heap_/trace_fn_imps.hpp> | |
319 | #include <ext/pb_ds/detail/thin_heap_/find_fn_imps.hpp> | |
320 | #include <ext/pb_ds/detail/thin_heap_/insert_fn_imps.hpp> | |
321 | #include <ext/pb_ds/detail/thin_heap_/erase_fn_imps.hpp> | |
322 | #include <ext/pb_ds/detail/thin_heap_/split_join_fn_imps.hpp> | |
323 | ||
2548203e | 324 | #undef PB_DS_ASSERT_AUX_NULL |
325 | #undef PB_DS_ASSERT_NODE_CONSISTENT | |
36fed23c | 326 | #undef PB_DS_CLASS_C_DEC |
36fed23c | 327 | #undef PB_DS_CLASS_T_DEC |
4f4a327e | 328 | #undef PB_DS_BASE_T_P |
36fed23c | 329 | |
36fed23c | 330 | } // namespace detail |
b34535d7 | 331 | } // namespace __gnu_pbds |
36fed23c | 332 | |
4f4a327e | 333 | #endif |