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 binary_heap_/resize_policy.hpp 00038 * Contains an implementation class for a binary_heap. 00039 */ 00040 00041 #ifndef PB_DS_BINARY_HEAP_RESIZE_POLICY_HPP 00042 #define PB_DS_BINARY_HEAP_RESIZE_POLICY_HPP 00043 00044 #include <debug/debug.h> 00045 00046 namespace __gnu_pbds 00047 { 00048 namespace detail 00049 { 00050 /// Resize policy for binary heap. 00051 template<typename _Tp> 00052 class resize_policy 00053 { 00054 private: 00055 enum 00056 { 00057 ratio = 8, 00058 factor = 2 00059 }; 00060 00061 /// Next shrink size. 00062 _Tp m_shrink_size; 00063 00064 /// Next grow size. 00065 _Tp m_grow_size; 00066 00067 public: 00068 typedef _Tp size_type; 00069 00070 static const _Tp min_size = 16; 00071 00072 resize_policy() : m_shrink_size(0), m_grow_size(min_size) 00073 { PB_DS_ASSERT_VALID((*this)) } 00074 00075 resize_policy(const resize_policy& other) 00076 : m_shrink_size(other.m_shrink_size), m_grow_size(other.m_grow_size) 00077 { PB_DS_ASSERT_VALID((*this)) } 00078 00079 inline void 00080 swap(resize_policy<_Tp>&); 00081 00082 inline bool 00083 resize_needed_for_grow(size_type) const; 00084 00085 inline bool 00086 resize_needed_for_shrink(size_type) const; 00087 00088 inline bool 00089 grow_needed(size_type) const; 00090 00091 inline bool 00092 shrink_needed(size_type) const; 00093 00094 inline size_type 00095 get_new_size_for_grow() const; 00096 00097 inline size_type 00098 get_new_size_for_shrink() const; 00099 00100 inline size_type 00101 get_new_size_for_arbitrary(size_type) const; 00102 00103 inline void 00104 notify_grow_resize(); 00105 00106 inline void 00107 notify_shrink_resize(); 00108 00109 void 00110 notify_arbitrary(size_type); 00111 00112 #ifdef _GLIBCXX_DEBUG 00113 void 00114 assert_valid(const char*, int) const; 00115 #endif 00116 00117 #ifdef PB_DS_BINARY_HEAP_TRACE_ 00118 void 00119 trace() const; 00120 #endif 00121 }; 00122 00123 template<typename _Tp> 00124 const _Tp resize_policy<_Tp>::min_size; 00125 00126 template<typename _Tp> 00127 inline void 00128 resize_policy<_Tp>:: 00129 swap(resize_policy<_Tp>& other) 00130 { 00131 std::swap(m_shrink_size, other.m_shrink_size); 00132 std::swap(m_grow_size, other.m_grow_size); 00133 } 00134 00135 template<typename _Tp> 00136 inline bool 00137 resize_policy<_Tp>:: 00138 resize_needed_for_grow(size_type size) const 00139 { 00140 _GLIBCXX_DEBUG_ASSERT(size <= m_grow_size); 00141 return size == m_grow_size; 00142 } 00143 00144 template<typename _Tp> 00145 inline bool 00146 resize_policy<_Tp>:: 00147 resize_needed_for_shrink(size_type size) const 00148 { 00149 _GLIBCXX_DEBUG_ASSERT(size <= m_grow_size); 00150 return size == m_shrink_size; 00151 } 00152 00153 template<typename _Tp> 00154 inline typename resize_policy<_Tp>::size_type 00155 resize_policy<_Tp>:: 00156 get_new_size_for_grow() const 00157 { return m_grow_size * factor; } 00158 00159 template<typename _Tp> 00160 inline typename resize_policy<_Tp>::size_type 00161 resize_policy<_Tp>:: 00162 get_new_size_for_shrink() const 00163 { 00164 const size_type half_size = m_grow_size / factor; 00165 return std::max(min_size, half_size); 00166 } 00167 00168 template<typename _Tp> 00169 inline typename resize_policy<_Tp>::size_type 00170 resize_policy<_Tp>:: 00171 get_new_size_for_arbitrary(size_type size) const 00172 { 00173 size_type ret = min_size; 00174 while (ret < size) 00175 ret *= factor; 00176 return ret; 00177 } 00178 00179 template<typename _Tp> 00180 inline void 00181 resize_policy<_Tp>:: 00182 notify_grow_resize() 00183 { 00184 PB_DS_ASSERT_VALID((*this)) 00185 _GLIBCXX_DEBUG_ASSERT(m_grow_size >= min_size); 00186 m_grow_size *= factor; 00187 m_shrink_size = m_grow_size / ratio; 00188 PB_DS_ASSERT_VALID((*this)) 00189 } 00190 00191 template<typename _Tp> 00192 inline void 00193 resize_policy<_Tp>:: 00194 notify_shrink_resize() 00195 { 00196 PB_DS_ASSERT_VALID((*this)) 00197 m_shrink_size /= factor; 00198 if (m_shrink_size == 1) 00199 m_shrink_size = 0; 00200 m_grow_size = std::max(m_grow_size / factor, min_size); 00201 PB_DS_ASSERT_VALID((*this)) 00202 } 00203 00204 template<typename _Tp> 00205 inline void 00206 resize_policy<_Tp>:: 00207 notify_arbitrary(size_type actual_size) 00208 { 00209 m_grow_size = actual_size; 00210 m_shrink_size = m_grow_size / ratio; 00211 PB_DS_ASSERT_VALID((*this)) 00212 } 00213 00214 #ifdef _GLIBCXX_DEBUG 00215 template<typename _Tp> 00216 void 00217 resize_policy<_Tp>:: 00218 assert_valid(const char* __file, int __line) const 00219 { 00220 PB_DS_DEBUG_VERIFY(m_shrink_size == 0 00221 || m_shrink_size * ratio == m_grow_size); 00222 PB_DS_DEBUG_VERIFY(m_grow_size >= min_size); 00223 } 00224 #endif 00225 00226 #ifdef PB_DS_BINARY_HEAP_TRACE_ 00227 template<typename _Tp> 00228 void 00229 resize_policy<_Tp>:: 00230 trace() const 00231 { 00232 std::cerr << "shrink = " << m_shrink_size 00233 << " grow = " << m_grow_size << std::endl; 00234 } 00235 #endif 00236 00237 } // namespace detail 00238 } // namespace __gnu_pbds 00239 00240 #endif