libstdc++
|
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