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

   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
  70 namespace __gnu_pbds
  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     __gnu_pbds::detail::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 __gnu_pbds
 362
 363 #endif