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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2020 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 rebind_traits<_Alloc, value_type>         __rebind_v;
 106       typedef typename __rebind_v::allocator_type       value_allocator;
 107
 108     public:
 109       typedef typename __rebind_v::pointer              pointer;
 110       typedef typename __rebind_v::const_pointer        const_pointer;
 111       typedef typename __rebind_v::reference    reference;
 112       typedef typename __rebind_v::const_reference      const_reference;
 113
 114       typedef typename __conditional_type<simple_value,
 115                                           value_type, pointer>::__type
 116                                                         entry;
 117
 118       typedef typename rebind_traits<_Alloc, entry>::allocator_type
 119                                                         entry_allocator;
 120
 121       typedef typename rebind_traits<_Alloc, entry>::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       _GLIBCXX_NODISCARD 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