libstdc++
binomial_heap_base_.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2009, 2011 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00026 
00027 // Permission to use, copy, modify, sell, and distribute this software
00028 // is hereby granted without fee, provided that the above copyright
00029 // notice appears in all copies, and that both that copyright notice
00030 // and this permission notice appear in supporting documentation. None
00031 // of the above authors, nor IBM Haifa Research Laboratories, make any
00032 // representation about the suitability of this software for any
00033 // purpose. It is provided "as is" without express or implied
00034 // warranty.
00035 
00036 /**
00037  * @file binomial_heap_base_/binomial_heap_base_.hpp
00038  * Contains an implementation class for a base of binomial heaps.
00039  */
00040 
00041 #ifndef PB_DS_BINOMIAL_HEAP_BASE_HPP
00042 #define PB_DS_BINOMIAL_HEAP_BASE_HPP
00043 
00044 /*
00045  * Binomial heap base.
00046  * Vuillemin J is the mastah.
00047  * Modified from CLRS.
00048  */
00049 
00050 #include <debug/debug.h>
00051 #include <ext/pb_ds/detail/cond_dealtor.hpp>
00052 #include <ext/pb_ds/detail/type_utils.hpp>
00053 #include <ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp>
00054 
00055 namespace __gnu_pbds
00056 {
00057   namespace detail
00058   {
00059 #define PB_DS_CLASS_T_DEC \
00060     template<typename Value_Type, typename Cmp_Fn, typename _Alloc>
00061 
00062 #define PB_DS_CLASS_C_DEC \
00063     binomial_heap_base<Value_Type, Cmp_Fn, _Alloc>
00064 
00065 #ifdef _GLIBCXX_DEBUG
00066 #define PB_DS_B_HEAP_BASE \
00067   left_child_next_sibling_heap<Value_Type, Cmp_Fn, \
00068                 typename _Alloc::size_type,  _Alloc, false>
00069 #else
00070 #define PB_DS_B_HEAP_BASE \
00071   left_child_next_sibling_heap<Value_Type, Cmp_Fn, \
00072                 typename _Alloc::size_type, _Alloc>
00073 #endif
00074 
00075     /// Base class for binomial heap.
00076     template<typename Value_Type, typename Cmp_Fn, typename _Alloc>
00077     class binomial_heap_base
00078     : public PB_DS_B_HEAP_BASE
00079     {
00080     private:
00081       typedef typename _Alloc::template rebind<Value_Type>::other __rebind_v;
00082       typedef PB_DS_B_HEAP_BASE             base_type;
00083 
00084     protected:
00085       typedef typename base_type::node          node;
00086       typedef typename base_type::node_pointer      node_pointer;
00087       typedef typename base_type::node_const_pointer    node_const_pointer;
00088 
00089     public:
00090       typedef Value_Type                value_type;
00091       typedef Cmp_Fn                    cmp_fn;
00092       typedef _Alloc                    allocator_type;
00093       typedef typename _Alloc::size_type        size_type;
00094       typedef typename _Alloc::difference_type      difference_type;
00095 
00096       typedef typename __rebind_v::pointer      pointer;
00097       typedef typename __rebind_v::const_pointer    const_pointer;
00098       typedef typename __rebind_v::reference        reference;
00099       typedef typename __rebind_v::const_reference      const_reference;
00100 
00101       typedef typename base_type::point_const_iterator  point_const_iterator;
00102       typedef typename base_type::point_iterator    point_iterator;
00103       typedef typename base_type::const_iterator    const_iterator;
00104       typedef typename base_type::iterator      iterator;
00105 
00106     public:
00107 
00108       inline point_iterator
00109       push(const_reference);
00110 
00111       void
00112       modify(point_iterator, const_reference);
00113 
00114       inline const_reference
00115       top() const;
00116 
00117       void
00118       pop();
00119 
00120       void
00121       erase(point_iterator);
00122 
00123       inline void
00124       clear();
00125 
00126       template<typename Pred>
00127       size_type
00128       erase_if(Pred);
00129 
00130       template<typename Pred>
00131       void
00132       split(Pred, PB_DS_CLASS_C_DEC&);
00133 
00134       void
00135       join(PB_DS_CLASS_C_DEC&);
00136 
00137     protected:
00138 
00139       binomial_heap_base();
00140 
00141       binomial_heap_base(const Cmp_Fn&);
00142 
00143       binomial_heap_base(const PB_DS_CLASS_C_DEC&);
00144 
00145       void
00146       swap(PB_DS_CLASS_C_DEC&);
00147 
00148       ~binomial_heap_base();
00149 
00150       template<typename It>
00151       void
00152       copy_from_range(It, It);
00153 
00154       inline void
00155       find_max();
00156 
00157 #ifdef _GLIBCXX_DEBUG
00158       void
00159       assert_valid(bool, const char*, int) const;
00160 
00161       void
00162       assert_max(const char*, int) const;
00163 #endif
00164 
00165     private:
00166 
00167       inline node_pointer
00168       fix(node_pointer) const;
00169 
00170       inline void
00171       insert_node(node_pointer);
00172 
00173       inline void
00174       remove_parentless_node(node_pointer);
00175 
00176       inline node_pointer
00177       join(node_pointer, node_pointer) const;
00178 
00179 #ifdef _GLIBCXX_DEBUG
00180       void
00181       assert_node_consistent(node_const_pointer, bool, bool,
00182                  const char*, int) const;
00183 #endif
00184 
00185     protected:
00186       node_pointer  m_p_max;
00187     };
00188 
00189 #define PB_DS_ASSERT_VALID_COND(X, _StrictlyBinomial)           \
00190   _GLIBCXX_DEBUG_ONLY(X.assert_valid(_StrictlyBinomial,__FILE__, __LINE__);)
00191 
00192 #define PB_DS_ASSERT_BASE_NODE_CONSISTENT(_Node, _Bool)         \
00193   _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(_Node, _Bool,   \
00194                             __FILE__, __LINE__);)
00195 
00196 #include <ext/pb_ds/detail/binomial_heap_base_/constructors_destructor_fn_imps.hpp>
00197 #include <ext/pb_ds/detail/binomial_heap_base_/debug_fn_imps.hpp>
00198 #include <ext/pb_ds/detail/binomial_heap_base_/find_fn_imps.hpp>
00199 #include <ext/pb_ds/detail/binomial_heap_base_/insert_fn_imps.hpp>
00200 #include <ext/pb_ds/detail/binomial_heap_base_/erase_fn_imps.hpp>
00201 #include <ext/pb_ds/detail/binomial_heap_base_/split_join_fn_imps.hpp>
00202 
00203 #undef PB_DS_ASSERT_BASE_NODE_CONSISTENT
00204 #undef PB_DS_ASSERT_VALID_COND
00205 #undef PB_DS_CLASS_C_DEC
00206 #undef PB_DS_CLASS_T_DEC
00207 #undef PB_DS_B_HEAP_BASE
00208   } // namespace detail
00209 } // namespace __gnu_pbds
00210 
00211 #endif