libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_base_/binomial_heap_base_.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 binomial_heap_base_.hpp
  44  * Contains an implementation class for a base of binomial heaps.
  45  */
  46
  47 #ifndef PB_DS_BINOMIAL_HEAP_BASE_HPP
  48 #define PB_DS_BINOMIAL_HEAP_BASE_HPP
  49
  50 /*
  51  * Binomial heap base.
  52  * Vuillemin J is the mastah.
  53  * Modified from CLRS.
  54  */
  55
  56 #include <debug/debug.h>
  57 #include <ext/pb_ds/detail/cond_dealtor.hpp>
  58 #include <ext/pb_ds/detail/type_utils.hpp>
  59 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp>
  60 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/null_metadata.hpp>
  61
  62 namespace __gnu_pbds
  63 {
  64   namespace detail
  65   {
  66
  67 #define PB_DS_CLASS_T_DEC \
  68     template<typename Value_Type, class Cmp_Fn, class Allocator>
  69
  70 #define PB_DS_CLASS_C_DEC \
  71     binomial_heap_base_<Value_Type, Cmp_Fn, Allocator>
  72
  73 #ifdef _GLIBCXX_DEBUG
  74 #define PB_DS_BASE_C_DEC \
  75     left_child_next_sibling_heap_<Value_Type, Cmp_Fn, \
  76                                   typename Allocator::size_type, \
  77                                   Allocator, false>
  78 #else
  79 #define PB_DS_BASE_C_DEC \
  80     left_child_next_sibling_heap_<Value_Type, Cmp_Fn,   \
  81                                 typename Allocator::size_type, Allocator>
  82 #endif
  83
  84     /**
  85      * class description = "8y|\|0|\/|i41 h34p 74813">
  86      **/
  87     template<typename Value_Type, class Cmp_Fn, class Allocator>
  88     class binomial_heap_base_ : public PB_DS_BASE_C_DEC
  89     {
  90
  91     private:
  92       typedef PB_DS_BASE_C_DEC base_type;
  93
  94     protected:
  95       typedef typename base_type::node node;
  96
  97       typedef typename base_type::node_pointer node_pointer;
  98
  99       typedef typename base_type::const_node_pointer const_node_pointer;
 100
 101     public:
 102
 103       typedef typename Allocator::size_type size_type;
 104
 105       typedef typename Allocator::difference_type difference_type;
 106
 107       typedef Value_Type value_type;
 108
 109       typedef
 110       typename Allocator::template rebind<
 111         value_type>::other::pointer
 112       pointer;
 113
 114       typedef
 115       typename Allocator::template rebind<
 116         value_type>::other::const_pointer
 117       const_pointer;
 118
 119       typedef
 120       typename Allocator::template rebind<
 121         value_type>::other::reference
 122       reference;
 123
 124       typedef
 125       typename Allocator::template rebind<
 126         value_type>::other::const_reference
 127       const_reference;
 128
 129       typedef
 130       typename PB_DS_BASE_C_DEC::const_point_iterator
 131       const_point_iterator;
 132
 133       typedef typename PB_DS_BASE_C_DEC::point_iterator point_iterator;
 134
 135       typedef typename PB_DS_BASE_C_DEC::const_iterator const_iterator;
 136
 137       typedef typename PB_DS_BASE_C_DEC::iterator iterator;
 138
 139       typedef Cmp_Fn cmp_fn;
 140
 141       typedef Allocator allocator;
 142
 143     public:
 144
 145       inline point_iterator
 146       push(const_reference r_val);
 147
 148       void
 149       modify(point_iterator it, const_reference r_new_val);
 150
 151       inline const_reference
 152       top() const;
 153
 154       void
 155       pop();
 156
 157       void
 158       erase(point_iterator it);
 159
 160       inline void
 161       clear();
 162
 163       template<typename Pred>
 164       size_type
 165       erase_if(Pred pred);
 166
 167       template<typename Pred>
 168       void
 169       split(Pred pred, PB_DS_CLASS_C_DEC& other);
 170
 171       void
 172       join(PB_DS_CLASS_C_DEC& other);
 173
 174     protected:
 175
 176       binomial_heap_base_();
 177
 178       binomial_heap_base_(const Cmp_Fn& r_cmp_fn);
 179
 180       binomial_heap_base_(const PB_DS_CLASS_C_DEC& other);
 181
 182       void
 183       swap(PB_DS_CLASS_C_DEC& other);
 184
 185       ~binomial_heap_base_();
 186
 187       template<typename It>
 188       void
 189       copy_from_range(It first_it, It last_it);
 190
 191       inline void
 192       find_max();
 193
 194 #ifdef _GLIBCXX_DEBUG
 195       void
 196       assert_valid(bool strictly_binomial) const;
 197
 198       void
 199       assert_max() const;
 200 #endif
 201
 202     private:
 203
 204       inline node_pointer
 205       fix(node_pointer p_nd) const;
 206
 207       inline void
 208       insert_node(node_pointer p_nd);
 209
 210       inline void
 211       remove_parentless_node(node_pointer p_nd);
 212
 213       inline node_pointer
 214       join(node_pointer p_lhs, node_pointer p_rhs) const;
 215
 216 #ifdef _GLIBCXX_DEBUG
 217       void
 218       assert_node_consistent(const_node_pointer, bool, bool) const;
 219 #endif
 220
 221     protected:
 222       node_pointer m_p_max;
 223     };
 224
 225 #include <ext/pb_ds/detail/binomial_heap_base_/constructors_destructor_fn_imps.hpp>
 226 #include <ext/pb_ds/detail/binomial_heap_base_/debug_fn_imps.hpp>
 227 #include <ext/pb_ds/detail/binomial_heap_base_/find_fn_imps.hpp>
 228 #include <ext/pb_ds/detail/binomial_heap_base_/insert_fn_imps.hpp>
 229 #include <ext/pb_ds/detail/binomial_heap_base_/erase_fn_imps.hpp>
 230 #include <ext/pb_ds/detail/binomial_heap_base_/split_join_fn_imps.hpp>
 231
 232 #undef PB_DS_CLASS_C_DEC
 233 #undef PB_DS_CLASS_T_DEC
 234 #undef PB_DS_BASE_C_DEC
 235
 236
 237   } // namespace detail
 238 } // namespace __gnu_pbds
 239
 240 #endif