]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
8d9254fc | 3 | // Copyright (C) 2005-2020 Free Software Foundation, Inc. |
4569a895 AT |
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 | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
4569a895 AT |
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 | ||
748086b7 JJ |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
4569a895 | 19 | |
748086b7 JJ |
20 | // You should have received a copy of the GNU General Public License and |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
4569a895 AT |
24 | |
25 | // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. | |
26 | ||
27 | // Permission to use, copy, modify, sell, and distribute this software | |
28 | // is hereby granted without fee, provided that the above copyright | |
29 | // notice appears in all copies, and that both that copyright notice | |
30 | // and this permission notice appear in supporting documentation. None | |
31 | // of the above authors, nor IBM Haifa Research Laboratories, make any | |
32 | // representation about the suitability of this software for any | |
33 | // purpose. It is provided "as is" without express or implied | |
34 | // warranty. | |
35 | ||
36 | /** | |
a345e45d | 37 | * @file binary_heap_/resize_policy.hpp |
4569a895 AT |
38 | * Contains an implementation class for a binary_heap. |
39 | */ | |
40 | ||
41 | #ifndef PB_DS_BINARY_HEAP_RESIZE_POLICY_HPP | |
42 | #define PB_DS_BINARY_HEAP_RESIZE_POLICY_HPP | |
43 | ||
47bea7b8 BK |
44 | #include <debug/debug.h> |
45 | ||
5e11f978 | 46 | namespace __gnu_pbds |
4569a895 AT |
47 | { |
48 | namespace detail | |
49 | { | |
a345e45d BK |
50 | /// Resize policy for binary heap. |
51 | template<typename _Tp> | |
4569a895 AT |
52 | class resize_policy |
53 | { | |
a345e45d | 54 | private: |
4569a895 AT |
55 | enum |
56 | { | |
a345e45d BK |
57 | ratio = 8, |
58 | factor = 2 | |
4569a895 AT |
59 | }; |
60 | ||
30a96b3b | 61 | /// Next shrink size. |
a345e45d BK |
62 | _Tp m_shrink_size; |
63 | ||
30a96b3b | 64 | /// Next grow size. |
a345e45d BK |
65 | _Tp m_grow_size; |
66 | ||
4569a895 | 67 | public: |
a345e45d BK |
68 | typedef _Tp size_type; |
69 | ||
70 | static const _Tp min_size = 16; | |
71 | ||
72 | resize_policy() : m_shrink_size(0), m_grow_size(min_size) | |
73 | { PB_DS_ASSERT_VALID((*this)) } | |
74 | ||
75 | resize_policy(const resize_policy& other) | |
76 | : m_shrink_size(other.m_shrink_size), m_grow_size(other.m_grow_size) | |
77 | { PB_DS_ASSERT_VALID((*this)) } | |
4569a895 AT |
78 | |
79 | inline void | |
a345e45d | 80 | swap(resize_policy<_Tp>&); |
4569a895 AT |
81 | |
82 | inline bool | |
a345e45d | 83 | resize_needed_for_grow(size_type) const; |
4569a895 AT |
84 | |
85 | inline bool | |
a345e45d | 86 | resize_needed_for_shrink(size_type) const; |
4569a895 AT |
87 | |
88 | inline bool | |
a345e45d | 89 | grow_needed(size_type) const; |
4569a895 AT |
90 | |
91 | inline bool | |
a345e45d | 92 | shrink_needed(size_type) const; |
4569a895 AT |
93 | |
94 | inline size_type | |
95 | get_new_size_for_grow() const; | |
96 | ||
97 | inline size_type | |
98 | get_new_size_for_shrink() const; | |
99 | ||
a345e45d BK |
100 | inline size_type |
101 | get_new_size_for_arbitrary(size_type) const; | |
4569a895 AT |
102 | |
103 | inline void | |
104 | notify_grow_resize(); | |
105 | ||
106 | inline void | |
107 | notify_shrink_resize(); | |
108 | ||
109 | void | |
a345e45d | 110 | notify_arbitrary(size_type); |
4569a895 | 111 | |
47bea7b8 | 112 | #ifdef _GLIBCXX_DEBUG |
4569a895 | 113 | void |
a345e45d BK |
114 | assert_valid(const char*, int) const; |
115 | #endif | |
4569a895 AT |
116 | |
117 | #ifdef PB_DS_BINARY_HEAP_TRACE_ | |
4569a895 AT |
118 | void |
119 | trace() const; | |
a345e45d | 120 | #endif |
4569a895 AT |
121 | }; |
122 | ||
a345e45d BK |
123 | template<typename _Tp> |
124 | const _Tp resize_policy<_Tp>::min_size; | |
4569a895 | 125 | |
a345e45d | 126 | template<typename _Tp> |
4569a895 | 127 | inline void |
a345e45d BK |
128 | resize_policy<_Tp>:: |
129 | swap(resize_policy<_Tp>& other) | |
4569a895 | 130 | { |
a345e45d BK |
131 | std::swap(m_shrink_size, other.m_shrink_size); |
132 | std::swap(m_grow_size, other.m_grow_size); | |
4569a895 AT |
133 | } |
134 | ||
a345e45d | 135 | template<typename _Tp> |
4569a895 | 136 | inline bool |
a345e45d | 137 | resize_policy<_Tp>:: |
4569a895 AT |
138 | resize_needed_for_grow(size_type size) const |
139 | { | |
a345e45d BK |
140 | _GLIBCXX_DEBUG_ASSERT(size <= m_grow_size); |
141 | return size == m_grow_size; | |
4569a895 AT |
142 | } |
143 | ||
a345e45d | 144 | template<typename _Tp> |
4569a895 | 145 | inline bool |
a345e45d | 146 | resize_policy<_Tp>:: |
4569a895 AT |
147 | resize_needed_for_shrink(size_type size) const |
148 | { | |
a345e45d BK |
149 | _GLIBCXX_DEBUG_ASSERT(size <= m_grow_size); |
150 | return size == m_shrink_size; | |
4569a895 AT |
151 | } |
152 | ||
a345e45d BK |
153 | template<typename _Tp> |
154 | inline typename resize_policy<_Tp>::size_type | |
155 | resize_policy<_Tp>:: | |
4569a895 | 156 | get_new_size_for_grow() const |
a345e45d | 157 | { return m_grow_size * factor; } |
4569a895 | 158 | |
a345e45d BK |
159 | template<typename _Tp> |
160 | inline typename resize_policy<_Tp>::size_type | |
161 | resize_policy<_Tp>:: | |
4569a895 AT |
162 | get_new_size_for_shrink() const |
163 | { | |
a345e45d BK |
164 | const size_type half_size = m_grow_size / factor; |
165 | return std::max(min_size, half_size); | |
4569a895 AT |
166 | } |
167 | ||
a345e45d BK |
168 | template<typename _Tp> |
169 | inline typename resize_policy<_Tp>::size_type | |
170 | resize_policy<_Tp>:: | |
4569a895 AT |
171 | get_new_size_for_arbitrary(size_type size) const |
172 | { | |
173 | size_type ret = min_size; | |
4569a895 AT |
174 | while (ret < size) |
175 | ret *= factor; | |
4569a895 AT |
176 | return ret; |
177 | } | |
178 | ||
a345e45d | 179 | template<typename _Tp> |
4569a895 | 180 | inline void |
a345e45d | 181 | resize_policy<_Tp>:: |
4569a895 AT |
182 | notify_grow_resize() |
183 | { | |
f5886803 | 184 | PB_DS_ASSERT_VALID((*this)) |
a345e45d BK |
185 | _GLIBCXX_DEBUG_ASSERT(m_grow_size >= min_size); |
186 | m_grow_size *= factor; | |
187 | m_shrink_size = m_grow_size / ratio; | |
f5886803 | 188 | PB_DS_ASSERT_VALID((*this)) |
47bea7b8 | 189 | } |
4569a895 | 190 | |
a345e45d | 191 | template<typename _Tp> |
4569a895 | 192 | inline void |
a345e45d | 193 | resize_policy<_Tp>:: |
4569a895 AT |
194 | notify_shrink_resize() |
195 | { | |
f5886803 | 196 | PB_DS_ASSERT_VALID((*this)) |
a345e45d BK |
197 | m_shrink_size /= factor; |
198 | if (m_shrink_size == 1) | |
199 | m_shrink_size = 0; | |
200 | m_grow_size = std::max(m_grow_size / factor, min_size); | |
f5886803 | 201 | PB_DS_ASSERT_VALID((*this)) |
47bea7b8 | 202 | } |
4569a895 | 203 | |
a345e45d | 204 | template<typename _Tp> |
4569a895 | 205 | inline void |
a345e45d | 206 | resize_policy<_Tp>:: |
4569a895 AT |
207 | notify_arbitrary(size_type actual_size) |
208 | { | |
a345e45d BK |
209 | m_grow_size = actual_size; |
210 | m_shrink_size = m_grow_size / ratio; | |
f5886803 | 211 | PB_DS_ASSERT_VALID((*this)) |
47bea7b8 | 212 | } |
4569a895 | 213 | |
47bea7b8 | 214 | #ifdef _GLIBCXX_DEBUG |
a345e45d | 215 | template<typename _Tp> |
4569a895 | 216 | void |
a345e45d | 217 | resize_policy<_Tp>:: |
f5886803 | 218 | assert_valid(const char* __file, int __line) const |
4569a895 | 219 | { |
a345e45d BK |
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); | |
4569a895 | 223 | } |
a345e45d | 224 | #endif |
4569a895 AT |
225 | |
226 | #ifdef PB_DS_BINARY_HEAP_TRACE_ | |
a345e45d | 227 | template<typename _Tp> |
4569a895 | 228 | void |
a345e45d | 229 | resize_policy<_Tp>:: |
4569a895 AT |
230 | trace() const |
231 | { | |
a345e45d BK |
232 | std::cerr << "shrink = " << m_shrink_size |
233 | << " grow = " << m_grow_size << std::endl; | |
4569a895 | 234 | } |
a345e45d | 235 | #endif |
4569a895 | 236 | |
47bea7b8 | 237 | } // namespace detail |
5e11f978 | 238 | } // namespace __gnu_pbds |
4569a895 | 239 | |
a345e45d | 240 | #endif |