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 binary_heap_/binary_heap_.hpp 38 * Contains an implementation class for a binary heap. 39 */ 40 41 #ifndef PB_DS_BINARY_HEAP_HPP 42 #define PB_DS_BINARY_HEAP_HPP 43 44 #include <queue> 45 #include <algorithm> 46 #include <ext/pb_ds/detail/cond_dealtor.hpp> 47 #include <ext/pb_ds/detail/cond_dealtor.hpp> 48 #include <ext/pb_ds/detail/type_utils.hpp> 49 #include <ext/pb_ds/detail/binary_heap_/entry_cmp.hpp> 50 #include <ext/pb_ds/detail/binary_heap_/entry_pred.hpp> 51 #include <ext/pb_ds/detail/binary_heap_/resize_policy.hpp> 52 #include <ext/pb_ds/detail/binary_heap_/point_const_iterator.hpp> 53 #include <ext/pb_ds/detail/binary_heap_/const_iterator.hpp> 54 #ifdef PB_DS_BINARY_HEAP_TRACE_ 55 #include <iostream> 56 #endif 57 #include <ext/pb_ds/detail/type_utils.hpp> 58 #include <debug/debug.h> 59 60 namespace __gnu_pbds 61 { 62 namespace detail 63 { 64 #define PB_DS_CLASS_T_DEC \ 65 template<typename Value_Type, typename Cmp_Fn, typename _Alloc> 66 67 #define PB_DS_CLASS_C_DEC \ 68 binary_heap<Value_Type, Cmp_Fn, _Alloc> 69 70 #define PB_DS_ENTRY_CMP_DEC \ 71 entry_cmp<Value_Type, Cmp_Fn, _Alloc, is_simple<Value_Type>::value>::type 72 73 #define PB_DS_RESIZE_POLICY_DEC \ 74 __gnu_pbds::detail::resize_policy<typename _Alloc::size_type> 75 76 /** 77 * Binary heaps composed of resize and compare policies. 78 * 79 * @ingroup heap-detail 80 * 81 * Based on CLRS. 82 */ 83 template<typename Value_Type, typename Cmp_Fn, typename _Alloc> 84 class binary_heap 85 : public PB_DS_ENTRY_CMP_DEC, public PB_DS_RESIZE_POLICY_DEC 86 { 87 public: 88 typedef Value_Type value_type; 89 typedef Cmp_Fn cmp_fn; 90 typedef _Alloc allocator_type; 91 typedef typename _Alloc::size_type size_type; 92 typedef typename _Alloc::difference_type difference_type; 93 typedef typename PB_DS_ENTRY_CMP_DEC entry_cmp; 94 typedef PB_DS_RESIZE_POLICY_DEC resize_policy; 95 typedef cond_dealtor<value_type, _Alloc> cond_dealtor_t; 96 97 private: 98 enum 99 { 100 simple_value = is_simple<value_type>::value 101 }; 102 103 typedef integral_constant<int, simple_value> no_throw_copies_t; 104 105 typedef typename _Alloc::template rebind<value_type> __rebind_v; 106 typedef typename __rebind_v::other value_allocator; 107 108 public: 109 typedef typename value_allocator::pointer pointer; 110 typedef typename value_allocator::const_pointer const_pointer; 111 typedef typename value_allocator::reference reference; 112 typedef typename value_allocator::const_reference const_reference; 113 114 typedef typename __conditional_type<simple_value, 115 value_type, pointer>::__type 116 entry; 117 118 typedef typename _Alloc::template rebind<entry>::other 119 entry_allocator; 120 121 typedef typename entry_allocator::pointer entry_pointer; 122 123 typedef binary_heap_point_const_iterator_<value_type, entry, 124 simple_value, _Alloc> 125 point_const_iterator; 126 127 typedef point_const_iterator point_iterator; 128 129 typedef binary_heap_const_iterator_<value_type, entry, 130 simple_value, _Alloc> 131 const_iterator; 132 133 typedef const_iterator iterator; 134 135 136 binary_heap(); 137 138 binary_heap(const cmp_fn&); 139 140 binary_heap(const binary_heap&); 141 142 void 143 swap(binary_heap&); 144 145 ~binary_heap(); 146 147 inline bool 148 empty() const; 149 150 inline size_type 151 size() const; 152 153 inline size_type 154 max_size() const; 155 156 Cmp_Fn& 157 get_cmp_fn(); 158 159 const Cmp_Fn& 160 get_cmp_fn() const; 161 162 inline point_iterator 163 push(const_reference); 164 165 void 166 modify(point_iterator, const_reference); 167 168 inline const_reference 169 top() const; 170 171 inline void 172 pop(); 173 174 inline void 175 erase(point_iterator); 176 177 template<typename Pred> 178 size_type 179 erase_if(Pred); 180 181 inline void 182 erase_at(entry_pointer, size_type, false_type); 183 184 inline void 185 erase_at(entry_pointer, size_type, true_type); 186 187 inline iterator 188 begin(); 189 190 inline const_iterator 191 begin() const; 192 193 inline iterator 194 end(); 195 196 inline const_iterator 197 end() const; 198 199 void 200 clear(); 201 202 template<typename Pred> 203 void 204 split(Pred, binary_heap&); 205 206 void 207 join(binary_heap&); 208 209 #ifdef PB_DS_BINARY_HEAP_TRACE_ 210 void 211 trace() const; 212 #endif 213 214 protected: 215 template<typename It> 216 void 217 copy_from_range(It, It); 218 219 private: 220 void 221 value_swap(binary_heap&); 222 223 inline void 224 insert_value(const_reference, false_type); 225 226 inline void 227 insert_value(value_type, true_type); 228 229 inline void 230 resize_for_insert_if_needed(); 231 232 inline void 233 swap_value_imp(entry_pointer, value_type, true_type); 234 235 inline void 236 swap_value_imp(entry_pointer, const_reference, false_type); 237 238 void 239 fix(entry_pointer); 240 241 inline const_reference 242 top_imp(true_type) const; 243 244 inline const_reference 245 top_imp(false_type) const; 246 247 inline static size_type 248 left_child(size_type); 249 250 inline static size_type 251 right_child(size_type); 252 253 inline static size_type 254 parent(size_type); 255 256 inline void 257 resize_for_erase_if_needed(); 258 259 template<typename Pred> 260 size_type 261 partition(Pred); 262 263 void 264 make_heap() 265 { 266 const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this); 267 entry_pointer end = m_a_entries + m_size; 268 std::make_heap(m_a_entries, end, m_cmp); 269 } 270 271 void 272 push_heap() 273 { 274 const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this); 275 entry_pointer end = m_a_entries + m_size; 276 std::push_heap(m_a_entries, end, m_cmp); 277 } 278 279 void 280 pop_heap() 281 { 282 const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this); 283 entry_pointer end = m_a_entries + m_size; 284 std::pop_heap(m_a_entries, end, m_cmp); 285 } 286 287 #ifdef _GLIBCXX_DEBUG 288 void 289 assert_valid(const char*, int) const; 290 #endif 291 292 #ifdef PB_DS_BINARY_HEAP_TRACE_ 293 void 294 trace_entry(const entry&, false_type) const; 295 296 void 297 trace_entry(const entry&, true_type) const; 298 #endif 299 300 static entry_allocator s_entry_allocator; 301 static value_allocator s_value_allocator; 302 static no_throw_copies_t s_no_throw_copies_ind; 303 304 size_type m_size; 305 size_type m_actual_size; 306 entry_pointer m_a_entries; 307 }; 308 309 #define PB_DS_ASSERT_VALID(X) \ 310 _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);) 311 312 #define PB_DS_DEBUG_VERIFY(_Cond) \ 313 _GLIBCXX_DEBUG_VERIFY_AT(_Cond, \ 314 _M_message(#_Cond" assertion from %1;:%2;") \ 315 ._M_string(__FILE__)._M_integer(__LINE__) \ 316 ,__file,__line) 317 318 #include <ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp> 319 #include <ext/pb_ds/detail/binary_heap_/constructors_destructor_fn_imps.hpp> 320 #include <ext/pb_ds/detail/binary_heap_/iterators_fn_imps.hpp> 321 #include <ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp> 322 #include <ext/pb_ds/detail/binary_heap_/trace_fn_imps.hpp> 323 #include <ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp> 324 #include <ext/pb_ds/detail/binary_heap_/info_fn_imps.hpp> 325 #include <ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp> 326 #include <ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp> 327 #include <ext/pb_ds/detail/binary_heap_/policy_access_fn_imps.hpp> 328 329 #undef PB_DS_CLASS_C_DEC 330 #undef PB_DS_CLASS_T_DEC 331 #undef PB_DS_ENTRY_CMP_DEC 332 #undef PB_DS_RESIZE_POLICY_DEC 333 334 } // namespace detail 335 } // namespace __gnu_pbds 336 337 #endif 338