libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2009, 2011 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
  64 namespace __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 char* file, int line) 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 #define PB_DS_ASSERT_VALID(X) \
 339   _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);)
 340
 341 #define PB_DS_DEBUG_VERIFY(_Cond)                                       \
 342   _GLIBCXX_DEBUG_VERIFY_AT(_Cond,                                       \
 343                            _M_message(#_Cond" assertion from %1;:%2;")  \
 344                            ._M_string(__FILE__)._M_integer(__LINE__)    \
 345                            ,__file,__line)
 346
 347 #include <ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp>
 348 #include <ext/pb_ds/detail/binary_heap_/constructors_destructor_fn_imps.hpp>
 349 #include <ext/pb_ds/detail/binary_heap_/iterators_fn_imps.hpp>
 350 #include <ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp>
 351 #include <ext/pb_ds/detail/binary_heap_/trace_fn_imps.hpp>
 352 #include <ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp>
 353 #include <ext/pb_ds/detail/binary_heap_/info_fn_imps.hpp>
 354 #include <ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp>
 355 #include <ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp>
 356 #include <ext/pb_ds/detail/binary_heap_/policy_access_fn_imps.hpp>
 357
 358 #undef PB_DS_DEBUG_VERIFY
 359 #undef PB_DS_ASSERT_VALID
 360 #undef PB_DS_CLASS_C_DEC
 361 #undef PB_DS_CLASS_T_DEC
 362 #undef PB_DS_ENTRY_CMP_DEC
 363 #undef PB_DS_RESIZE_POLICY_DEC
 364
 365   } // namespace detail
 366 } // namespace __gnu_pbds
 367
 368 #endif