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