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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2014 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 binomial_heap_base_/binomial_heap_base_.hpp
  38  * Contains an implementation class for a base of binomial heaps.
  39  */
  40
  41 #ifndef PB_DS_BINOMIAL_HEAP_BASE_HPP
  42 #define PB_DS_BINOMIAL_HEAP_BASE_HPP
  43
  44 /*
  45  * Binomial heap base.
  46  * Vuillemin J is the mastah.
  47  * Modified from CLRS.
  48  */
  49
  50 #include <debug/debug.h>
  51 #include <ext/pb_ds/detail/cond_dealtor.hpp>
  52 #include <ext/pb_ds/detail/type_utils.hpp>
  53 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp>
  54
  55 namespace __gnu_pbds
  56 {
  57   namespace detail
  58   {
  59 #define PB_DS_CLASS_T_DEC \
  60     template<typename Value_Type, typename Cmp_Fn, typename _Alloc>
  61
  62 #define PB_DS_CLASS_C_DEC \
  63     binomial_heap_base<Value_Type, Cmp_Fn, _Alloc>
  64
  65 #ifdef _GLIBCXX_DEBUG
  66 #define PB_DS_B_HEAP_BASE \
  67   left_child_next_sibling_heap<Value_Type, Cmp_Fn, \
  68                                 typename _Alloc::size_type,  _Alloc, false>
  69 #else
  70 #define PB_DS_B_HEAP_BASE \
  71   left_child_next_sibling_heap<Value_Type, Cmp_Fn, \
  72                                 typename _Alloc::size_type, _Alloc>
  73 #endif
  74
  75     /// Base class for binomial heap.
  76     template<typename Value_Type, typename Cmp_Fn, typename _Alloc>
  77     class binomial_heap_base
  78     : public PB_DS_B_HEAP_BASE
  79     {
  80     private:
  81       typedef typename _Alloc::template rebind<Value_Type>::other __rebind_v;
  82       typedef PB_DS_B_HEAP_BASE                         base_type;
  83
  84     protected:
  85       typedef typename base_type::node                  node;
  86       typedef typename base_type::node_pointer          node_pointer;
  87       typedef typename base_type::node_const_pointer    node_const_pointer;
  88
  89     public:
  90       typedef Value_Type                                value_type;
  91       typedef Cmp_Fn                                    cmp_fn;
  92       typedef _Alloc                                    allocator_type;
  93       typedef typename _Alloc::size_type                size_type;
  94       typedef typename _Alloc::difference_type          difference_type;
  95
  96       typedef typename __rebind_v::pointer              pointer;
  97       typedef typename __rebind_v::const_pointer        const_pointer;
  98       typedef typename __rebind_v::reference            reference;
  99       typedef typename __rebind_v::const_reference      const_reference;
 100
 101       typedef typename base_type::point_const_iterator  point_const_iterator;
 102       typedef typename base_type::point_iterator        point_iterator;
 103       typedef typename base_type::const_iterator        const_iterator;
 104       typedef typename base_type::iterator              iterator;
 105
 106     public:
 107
 108       inline point_iterator
 109       push(const_reference);
 110
 111       void
 112       modify(point_iterator, const_reference);
 113
 114       inline const_reference
 115       top() const;
 116
 117       void
 118       pop();
 119
 120       void
 121       erase(point_iterator);
 122
 123       inline void
 124       clear();
 125
 126       template<typename Pred>
 127       size_type
 128       erase_if(Pred);
 129
 130       template<typename Pred>
 131       void
 132       split(Pred, PB_DS_CLASS_C_DEC&);
 133
 134       void
 135       join(PB_DS_CLASS_C_DEC&);
 136
 137     protected:
 138
 139       binomial_heap_base();
 140
 141       binomial_heap_base(const Cmp_Fn&);
 142
 143       binomial_heap_base(const PB_DS_CLASS_C_DEC&);
 144
 145       void
 146       swap(PB_DS_CLASS_C_DEC&);
 147
 148       ~binomial_heap_base();
 149
 150       template<typename It>
 151       void
 152       copy_from_range(It, It);
 153
 154       inline void
 155       find_max();
 156
 157 #ifdef _GLIBCXX_DEBUG
 158       void
 159       assert_valid(bool, const char*, int) const;
 160
 161       void
 162       assert_max(const char*, int) const;
 163 #endif
 164
 165     private:
 166
 167       inline node_pointer
 168       fix(node_pointer) const;
 169
 170       inline void
 171       insert_node(node_pointer);
 172
 173       inline void
 174       remove_parentless_node(node_pointer);
 175
 176       inline node_pointer
 177       join(node_pointer, node_pointer) const;
 178
 179 #ifdef _GLIBCXX_DEBUG
 180       void
 181       assert_node_consistent(node_const_pointer, bool, bool,
 182                              const char*, int) const;
 183 #endif
 184
 185     protected:
 186       node_pointer      m_p_max;
 187     };
 188
 189 #define PB_DS_ASSERT_VALID_COND(X, _StrictlyBinomial)                   \
 190   _GLIBCXX_DEBUG_ONLY(X.assert_valid(_StrictlyBinomial,__FILE__, __LINE__);)
 191
 192 #define PB_DS_ASSERT_BASE_NODE_CONSISTENT(_Node, _Bool)                 \
 193   _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(_Node, _Bool,   \
 194                                                         __FILE__, __LINE__);)
 195
 196 #include <ext/pb_ds/detail/binomial_heap_base_/constructors_destructor_fn_imps.hpp>
 197 #include <ext/pb_ds/detail/binomial_heap_base_/debug_fn_imps.hpp>
 198 #include <ext/pb_ds/detail/binomial_heap_base_/find_fn_imps.hpp>
 199 #include <ext/pb_ds/detail/binomial_heap_base_/insert_fn_imps.hpp>
 200 #include <ext/pb_ds/detail/binomial_heap_base_/erase_fn_imps.hpp>
 201 #include <ext/pb_ds/detail/binomial_heap_base_/split_join_fn_imps.hpp>
 202
 203 #undef PB_DS_ASSERT_BASE_NODE_CONSISTENT
 204 #undef PB_DS_ASSERT_VALID_COND
 205 #undef PB_DS_CLASS_C_DEC
 206 #undef PB_DS_CLASS_T_DEC
 207 #undef PB_DS_B_HEAP_BASE
 208   } // namespace detail
 209 } // namespace __gnu_pbds
 210
 211 #endif