1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006 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 2, 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// You should have received a copy of the GNU General Public License 17// along with this library; see the file COPYING. If not, write to 18// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19// MA 02111-1307, USA. 20 21// As a special exception, you may use this file as part of a free 22// software library without restriction. Specifically, if other files 23// instantiate templates or use macros or inline functions from this 24// file, or you compile this file and link it with other files to 25// produce an executable, this file does not by itself cause the 26// resulting executable to be covered by the GNU General Public 27// License. This exception does not however invalidate any other 28// reasons why the executable file might be covered by the GNU General 29// Public License. 30 31// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32 33// Permission to use, copy, modify, sell, and distribute this software 34// is hereby granted without fee, provided that the above copyright 35// notice appears in all copies, and that both that copyright notice 36// and this permission notice appear in supporting documentation. None 37// of the above authors, nor IBM Haifa Research Laboratories, make any 38// representation about the suitability of this software for any 39// purpose. It is provided "as is" without express or implied 40// warranty. 41 42/** 43 * @file binary_heap_.hpp 44 * Contains an implementation class for a binary heap. 45 */ 46 47#ifndef PB_DS_BINARY_HEAP_HPP 48#define PB_DS_BINARY_HEAP_HPP 49 50/* 51 * Based on CLRS. 52 */ 53 54#include <queue> 55#include <algorithm> 56#include <ext/pb_ds/detail/cond_dealtor.hpp> 57#include <ext/pb_ds/detail/cond_dealtor.hpp> 58#include <ext/pb_ds/detail/type_utils.hpp> 59#include <ext/pb_ds/detail/binary_heap_/entry_cmp.hpp> 60#include <ext/pb_ds/detail/binary_heap_/entry_pred.hpp> 61#include <ext/pb_ds/detail/binary_heap_/resize_policy.hpp> 62#include <ext/pb_ds/detail/binary_heap_/const_point_iterator.hpp> 63#include <ext/pb_ds/detail/binary_heap_/const_iterator.hpp> 64#ifdef PB_DS_BINARY_HEAP_TRACE_ 65#include <iostream> 66#endif 67#include <ext/pb_ds/detail/type_utils.hpp> 68#include <debug/debug.h> 69 70namespace pb_ds 71{ 72 namespace detail 73 { 74#define PB_DS_CLASS_T_DEC \ 75 template<typename Value_Type, class Cmp_Fn, class Allocator> 76 77#define PB_DS_CLASS_C_DEC \ 78 binary_heap_<Value_Type, Cmp_Fn, Allocator> 79 80#define PB_DS_ENTRY_CMP_DEC \ 81 entry_cmp<Value_Type, Cmp_Fn, is_simple<Value_Type>::value, Allocator>::type 82 83#define PB_DS_RESIZE_POLICY_DEC \ 84 resize_policy<typename Allocator::size_type> 85 86 /** 87 * class description = "Base class for some types of h3ap$"> 88 **/ 89 template<typename Value_Type, class Cmp_Fn, class Allocator> 90 class binary_heap_ : public PB_DS_ENTRY_CMP_DEC, 91 public PB_DS_RESIZE_POLICY_DEC 92 { 93 94 private: 95 enum 96 { 97 simple_value = is_simple<Value_Type>::value 98 }; 99 100 typedef integral_constant<int, simple_value> no_throw_copies_t; 101 102 typedef 103 typename Allocator::template rebind< 104 Value_Type>::other 105 value_allocator; 106 107 typedef 108 typename __conditional_type< 109 simple_value, 110 Value_Type, 111 typename value_allocator::pointer>::__type 112 entry; 113 114 typedef 115 typename Allocator::template rebind< 116 entry>::other 117 entry_allocator; 118 119 typedef typename entry_allocator::pointer entry_pointer; 120 121 typedef typename PB_DS_ENTRY_CMP_DEC entry_cmp; 122 123 typedef PB_DS_RESIZE_POLICY_DEC resize_policy; 124 125 typedef 126 cond_dealtor< 127 Value_Type, 128 Allocator> 129 cond_dealtor_t; 130 131 public: 132 133 typedef typename Allocator::size_type size_type; 134 135 typedef typename Allocator::difference_type difference_type; 136 137 typedef Value_Type value_type; 138 139 typedef 140 typename Allocator::template rebind< 141 value_type>::other::pointer 142 pointer; 143 144 typedef 145 typename Allocator::template rebind< 146 value_type>::other::const_pointer 147 const_pointer; 148 149 typedef 150 typename Allocator::template rebind< 151 value_type>::other::reference 152 reference; 153 154 typedef 155 typename Allocator::template rebind< 156 value_type>::other::const_reference 157 const_reference; 158 159 typedef 160 binary_heap_const_point_iterator_< 161 value_type, 162 entry, 163 simple_value, 164 Allocator> 165 const_point_iterator; 166 167 typedef const_point_iterator point_iterator; 168 169 typedef 170 binary_heap_const_iterator_< 171 value_type, 172 entry, 173 simple_value, 174 Allocator> 175 const_iterator; 176 177 typedef const_iterator iterator; 178 179 typedef Cmp_Fn cmp_fn; 180 181 typedef Allocator allocator; 182 183 public: 184 185 binary_heap_(); 186 187 binary_heap_(const Cmp_Fn& r_cmp_fn); 188 189 binary_heap_(const PB_DS_CLASS_C_DEC& other); 190 191 void 192 swap(PB_DS_CLASS_C_DEC& other); 193 194 ~binary_heap_(); 195 196 inline bool 197 empty() const; 198 199 inline size_type 200 size() const; 201 202 inline size_type 203 max_size() const; 204 205 Cmp_Fn& 206 get_cmp_fn(); 207 208 const Cmp_Fn& 209 get_cmp_fn() const; 210 211 inline point_iterator 212 push(const_reference r_val); 213 214 void 215 modify(point_iterator it, const_reference r_new_val); 216 217 inline const_reference 218 top() const; 219 220 inline void 221 pop(); 222 223 inline void 224 erase(point_iterator it); 225 226 template<typename Pred> 227 typename PB_DS_CLASS_C_DEC::size_type 228 erase_if(Pred pred); 229 230 inline static void 231 erase_at(entry_pointer a_entries, size_type size, false_type); 232 233 inline static void 234 erase_at(entry_pointer a_entries, size_type size, true_type); 235 236 inline iterator 237 begin(); 238 239 inline const_iterator 240 begin() const; 241 242 inline iterator 243 end(); 244 245 inline const_iterator 246 end() const; 247 248 void 249 clear(); 250 251 template<typename Pred> 252 void 253 split(Pred pred, PB_DS_CLASS_C_DEC& other); 254 255 void 256 join(PB_DS_CLASS_C_DEC& other); 257 258#ifdef PB_DS_BINARY_HEAP_TRACE_ 259 void 260 trace() const; 261#endif 262 263 protected: 264 265 template<typename It> 266 void 267 copy_from_range(It first_it, It last_it); 268 269 private: 270 271 void 272 value_swap(PB_DS_CLASS_C_DEC& other); 273 274 inline void 275 insert_value(const_reference r_val, false_type); 276 277 inline void 278 insert_value(value_type val, true_type); 279 280 inline void 281 insert_entry(entry e); 282 283 inline void 284 resize_for_insert_if_needed(); 285 286 inline void 287 swap_value_imp(entry_pointer p_e, value_type new_val, true_type); 288 289 inline void 290 swap_value_imp(entry_pointer p_e, const_reference r_new_val, false_type); 291 292 void 293 fix(entry_pointer p_e); 294 295 inline const_reference 296 top_imp(true_type) const; 297 298 inline const_reference 299 top_imp(false_type) const; 300 301 inline static size_type 302 left_child(size_type i); 303 304 inline static size_type 305 right_child(size_type i); 306 307 inline static size_type 308 parent(size_type i); 309 310 inline void 311 resize_for_erase_if_needed(); 312 313 template<typename Pred> 314 size_type 315 partition(Pred pred); 316 317#ifdef _GLIBCXX_DEBUG 318 void 319 assert_valid() const; 320#endif 321 322#ifdef PB_DS_BINARY_HEAP_TRACE_ 323 void 324 trace_entry(const entry& r_e, false_type) const; 325 326 void 327 trace_entry(const entry& r_e, true_type) const; 328#endif 329 330 private: 331 static entry_allocator s_entry_allocator; 332 333 static value_allocator s_value_allocator; 334 335 static no_throw_copies_t s_no_throw_copies_ind; 336 337 size_type m_size; 338 339 size_type m_actual_size; 340 341 entry_pointer m_a_entries; 342 }; 343 344#include <ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp> 345#include <ext/pb_ds/detail/binary_heap_/constructors_destructor_fn_imps.hpp> 346#include <ext/pb_ds/detail/binary_heap_/iterators_fn_imps.hpp> 347#include <ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp> 348#include <ext/pb_ds/detail/binary_heap_/trace_fn_imps.hpp> 349#include <ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp> 350#include <ext/pb_ds/detail/binary_heap_/info_fn_imps.hpp> 351#include <ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp> 352#include <ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp> 353#include <ext/pb_ds/detail/binary_heap_/policy_access_fn_imps.hpp> 354 355#undef PB_DS_CLASS_C_DEC 356#undef PB_DS_CLASS_T_DEC 357#undef PB_DS_ENTRY_CMP_DEC 358#undef PB_DS_RESIZE_POLICY_DEC 359 360 } // namespace detail 361} // namespace pb_ds 362 363#endif 364