]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
7adcbafe | 3 | // Copyright (C) 2005-2022 Free Software Foundation, Inc. |
4569a895 AT |
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 | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
4569a895 AT |
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 | ||
748086b7 JJ |
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. | |
4569a895 | 19 | |
748086b7 JJ |
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/>. | |
4569a895 AT |
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 | /** | |
a345e45d | 37 | * @file thin_heap_/thin_heap_.hpp |
4569a895 AT |
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 | ||
4569a895 AT |
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> | |
47bea7b8 | 48 | #include <debug/debug.h> |
4569a895 | 49 | |
5e11f978 | 50 | namespace __gnu_pbds |
4569a895 AT |
51 | { |
52 | namespace detail | |
53 | { | |
47bea7b8 | 54 | #define PB_DS_CLASS_T_DEC \ |
a345e45d | 55 | template<typename Value_Type, typename Cmp_Fn, typename _Alloc> |
4569a895 | 56 | |
47bea7b8 | 57 | #define PB_DS_CLASS_C_DEC \ |
a345e45d | 58 | thin_heap<Value_Type, Cmp_Fn, _Alloc> |
4569a895 | 59 | |
47bea7b8 | 60 | #ifdef _GLIBCXX_DEBUG |
a345e45d BK |
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 | |
4569a895 | 67 | |
30a96b3b | 68 | |
4569a895 | 69 | /** |
a345e45d | 70 | * Thin heap. |
30a96b3b BK |
71 | * |
72 | * @ingroup heap-detail | |
a345e45d BK |
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 | |
4569a895 | 79 | { |
4569a895 | 80 | private: |
ec541f1b | 81 | typedef rebind_traits<_Alloc, Value_Type> __rebind_a; |
a345e45d | 82 | typedef left_child_next_sibling_heap PB_DS_BASE_T_P base_type; |
4569a895 AT |
83 | |
84 | protected: | |
a345e45d BK |
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; | |
4569a895 AT |
88 | |
89 | public: | |
a345e45d BK |
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; | |
4569a895 | 95 | |
a345e45d BK |
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; | |
4569a895 | 100 | |
a345e45d BK |
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; | |
4569a895 | 105 | |
4569a895 AT |
106 | |
107 | inline point_iterator | |
a345e45d | 108 | push(const_reference); |
4569a895 AT |
109 | |
110 | void | |
a345e45d | 111 | modify(point_iterator, const_reference); |
4569a895 AT |
112 | |
113 | inline const_reference | |
114 | top() const; | |
115 | ||
116 | void | |
117 | pop(); | |
118 | ||
119 | void | |
a345e45d | 120 | erase(point_iterator); |
4569a895 AT |
121 | |
122 | inline void | |
123 | clear(); | |
124 | ||
125 | template<typename Pred> | |
126 | size_type | |
a345e45d | 127 | erase_if(Pred); |
4569a895 AT |
128 | |
129 | template<typename Pred> | |
130 | void | |
a345e45d | 131 | split(Pred, PB_DS_CLASS_C_DEC&); |
4569a895 AT |
132 | |
133 | void | |
a345e45d | 134 | join(PB_DS_CLASS_C_DEC&); |
4569a895 AT |
135 | |
136 | protected: | |
a345e45d | 137 | thin_heap(); |
4569a895 | 138 | |
a345e45d | 139 | thin_heap(const Cmp_Fn&); |
4569a895 | 140 | |
a345e45d | 141 | thin_heap(const PB_DS_CLASS_C_DEC&); |
4569a895 AT |
142 | |
143 | void | |
a345e45d | 144 | swap(PB_DS_CLASS_C_DEC&); |
4569a895 | 145 | |
a345e45d | 146 | ~thin_heap(); |
4569a895 AT |
147 | |
148 | template<typename It> | |
149 | void | |
a345e45d | 150 | copy_from_range(It, It); |
4569a895 | 151 | |
47bea7b8 | 152 | #ifdef _GLIBCXX_DEBUG |
4569a895 | 153 | void |
a345e45d | 154 | assert_valid(const char*, int) const; |
4569a895 AT |
155 | |
156 | void | |
a345e45d BK |
157 | assert_max(const char*, int) const; |
158 | #endif | |
4569a895 AT |
159 | |
160 | #ifdef PB_DS_THIN_HEAP_TRACE_ | |
4569a895 AT |
161 | void |
162 | trace() const; | |
a345e45d | 163 | #endif |
4569a895 AT |
164 | |
165 | private: | |
166 | enum | |
167 | { | |
168 | max_rank = (sizeof(size_type) << 4) + 2 | |
169 | }; | |
170 | ||
4569a895 AT |
171 | void |
172 | initialize(); | |
173 | ||
174 | inline void | |
a345e45d | 175 | update_max(node_pointer); |
4569a895 AT |
176 | |
177 | inline void | |
a345e45d | 178 | fix(node_pointer); |
4569a895 AT |
179 | |
180 | inline void | |
a345e45d | 181 | fix_root(node_pointer); |
4569a895 AT |
182 | |
183 | inline void | |
a345e45d | 184 | fix_sibling_rank_1_unmarked(node_pointer); |
4569a895 AT |
185 | |
186 | inline void | |
a345e45d | 187 | fix_sibling_rank_1_marked(node_pointer); |
4569a895 AT |
188 | |
189 | inline void | |
a345e45d | 190 | fix_sibling_general_unmarked(node_pointer); |
4569a895 AT |
191 | |
192 | inline void | |
a345e45d | 193 | fix_sibling_general_marked(node_pointer); |
4569a895 AT |
194 | |
195 | inline void | |
a345e45d | 196 | fix_child(node_pointer); |
4569a895 AT |
197 | |
198 | inline static void | |
a345e45d | 199 | make_root(node_pointer); |
4569a895 AT |
200 | |
201 | inline void | |
a345e45d | 202 | make_root_and_link(node_pointer); |
4569a895 AT |
203 | |
204 | inline void | |
205 | remove_max_node(); | |
206 | ||
207 | void | |
208 | to_aux_except_max(); | |
209 | ||
210 | inline void | |
a345e45d | 211 | add_to_aux(node_pointer); |
4569a895 AT |
212 | |
213 | inline void | |
214 | make_from_aux(); | |
215 | ||
216 | inline size_type | |
217 | rank_bound(); | |
218 | ||
219 | inline void | |
a345e45d | 220 | make_child_of(node_pointer, node_pointer); |
4569a895 AT |
221 | |
222 | inline void | |
a345e45d | 223 | remove_node(node_pointer); |
4569a895 AT |
224 | |
225 | inline node_pointer | |
a345e45d | 226 | join(node_pointer, node_pointer) const; |
4569a895 | 227 | |
47bea7b8 | 228 | #ifdef _GLIBCXX_DEBUG |
4569a895 | 229 | void |
a345e45d | 230 | assert_node_consistent(node_const_pointer, bool, const char*, int) const; |
4569a895 AT |
231 | |
232 | void | |
a345e45d BK |
233 | assert_aux_null(const char*, int) const; |
234 | #endif | |
4569a895 | 235 | |
a345e45d BK |
236 | node_pointer m_p_max; |
237 | node_pointer m_a_aux[max_rank]; | |
4569a895 AT |
238 | }; |
239 | ||
240 | enum | |
241 | { | |
242 | num_distinct_rank_bounds = 48 | |
243 | }; | |
244 | ||
245 | // Taken from the SGI implementation; acknowledged in the docs. | |
4569a895 AT |
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, | |
8161e0c3 DD |
273 | /* 24 */ 64079ul |
274 | #if __SIZE_MAX__ > 0xfffful | |
275 | , | |
4569a895 AT |
276 | /* 25 */ 103681ul, |
277 | /* 26 */ 167761ul, | |
278 | /* 27 */ 271442ul, | |
279 | /* 28 */ 439204ul, | |
8161e0c3 DD |
280 | /* 29 */ 710646ul |
281 | #if __SIZE_MAX__ > 0xffffful | |
282 | , | |
4569a895 AT |
283 | /* 30 */ 1149851ul, |
284 | /* 31 */ 1860497ul, | |
285 | /* 32 */ 3010349ul, | |
286 | /* 33 */ 4870846ul, | |
287 | /* 34 */ 7881196ul, | |
8161e0c3 DD |
288 | /* 35 */ 12752042ul |
289 | #if __SIZE_MAX__ > 0xfffffful | |
290 | , | |
4569a895 AT |
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 | |
8161e0c3 DD |
303 | #endif |
304 | #endif | |
305 | #endif | |
4569a895 AT |
306 | /* Pot's good, let's play */ |
307 | }; | |
308 | ||
f5886803 FD |
309 | #define PB_DS_ASSERT_NODE_CONSISTENT(_Node, _Bool) \ |
310 | _GLIBCXX_DEBUG_ONLY(assert_node_consistent(_Node, _Bool, \ | |
311 | __FILE__, __LINE__);) | |
312 | ||
a345e45d | 313 | #define PB_DS_ASSERT_AUX_NULL(X) \ |
f5886803 FD |
314 | _GLIBCXX_DEBUG_ONLY(X.assert_aux_null(__FILE__, __LINE__);) |
315 | ||
4569a895 AT |
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 | ||
f5886803 FD |
324 | #undef PB_DS_ASSERT_AUX_NULL |
325 | #undef PB_DS_ASSERT_NODE_CONSISTENT | |
4569a895 | 326 | #undef PB_DS_CLASS_C_DEC |
4569a895 | 327 | #undef PB_DS_CLASS_T_DEC |
a345e45d | 328 | #undef PB_DS_BASE_T_P |
4569a895 | 329 | |
4569a895 | 330 | } // namespace detail |
5e11f978 | 331 | } // namespace __gnu_pbds |
4569a895 | 332 | |
a345e45d | 333 | #endif |