41 #ifndef PB_DS_BINARY_HEAP_RESIZE_POLICY_HPP
42 #define PB_DS_BINARY_HEAP_RESIZE_POLICY_HPP
51 template<
typename _Tp>
68 typedef _Tp size_type;
70 static const _Tp min_size = 16;
73 { PB_DS_ASSERT_VALID((*
this)) }
76 : m_shrink_size(other.m_shrink_size), m_grow_size(other.m_grow_size)
77 { PB_DS_ASSERT_VALID((*
this)) }
83 resize_needed_for_grow(size_type)
const;
86 resize_needed_for_shrink(size_type)
const;
89 grow_needed(size_type)
const;
92 shrink_needed(size_type)
const;
95 get_new_size_for_grow()
const;
98 get_new_size_for_shrink()
const;
101 get_new_size_for_arbitrary(size_type)
const;
104 notify_grow_resize();
107 notify_shrink_resize();
110 notify_arbitrary(size_type);
112 #ifdef _GLIBCXX_DEBUG
114 assert_valid(
const char*,
int)
const;
117 #ifdef PB_DS_BINARY_HEAP_TRACE_
123 template<
typename _Tp>
126 template<
typename _Tp>
131 std::swap(m_shrink_size, other.m_shrink_size);
132 std::swap(m_grow_size, other.m_grow_size);
135 template<
typename _Tp>
138 resize_needed_for_grow(size_type
size)
const
140 _GLIBCXX_DEBUG_ASSERT(size <= m_grow_size);
141 return size == m_grow_size;
144 template<
typename _Tp>
147 resize_needed_for_shrink(size_type
size)
const
149 _GLIBCXX_DEBUG_ASSERT(size <= m_grow_size);
150 return size == m_shrink_size;
153 template<
typename _Tp>
154 inline typename resize_policy<_Tp>::size_type
156 get_new_size_for_grow()
const
157 {
return m_grow_size * factor; }
159 template<
typename _Tp>
160 inline typename resize_policy<_Tp>::size_type
162 get_new_size_for_shrink()
const
164 const size_type half_size = m_grow_size / factor;
165 return std::max(min_size, half_size);
168 template<
typename _Tp>
169 inline typename resize_policy<_Tp>::size_type
171 get_new_size_for_arbitrary(size_type
size)
const
173 size_type ret = min_size;
179 template<
typename _Tp>
184 PB_DS_ASSERT_VALID((*
this))
185 _GLIBCXX_DEBUG_ASSERT(m_grow_size >= min_size);
186 m_grow_size *= factor;
187 m_shrink_size = m_grow_size / ratio;
188 PB_DS_ASSERT_VALID((*this))
191 template<typename _Tp>
194 notify_shrink_resize()
196 PB_DS_ASSERT_VALID((*
this))
197 m_shrink_size /= factor;
198 if (m_shrink_size == 1)
200 m_grow_size = std::
max(m_grow_size / factor, min_size);
201 PB_DS_ASSERT_VALID((*this))
204 template<typename _Tp>
207 notify_arbitrary(size_type actual_size)
209 m_grow_size = actual_size;
210 m_shrink_size = m_grow_size / ratio;
211 PB_DS_ASSERT_VALID((*
this))
214 #ifdef _GLIBCXX_DEBUG
215 template<
typename _Tp>
218 assert_valid(
const char* __file,
int __line)
const
220 PB_DS_DEBUG_VERIFY(m_shrink_size == 0
221 || m_shrink_size * ratio == m_grow_size);
222 PB_DS_DEBUG_VERIFY(m_grow_size >= min_size);
226 #ifdef PB_DS_BINARY_HEAP_TRACE_
227 template<
typename _Tp>
232 std::cerr <<
"shrink = " << m_shrink_size
233 <<
" grow = " << m_grow_size <<
std::endl;
Resize policy for binary heap.
basic_ostream< _CharT, _Traits > & endl(basic_ostream< _CharT, _Traits > &__os)
Write a newline and flush the stream.
ostream cerr
Linked to standard output.
const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
constexpr size_t size() const _GLIBCXX_NOEXCEPT
Returns the total number of bits.