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