1 /* Sparse_Row class implementation: inline functions.
2 Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it>
3 Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com)
4
5 This file is part of the Parma Polyhedra Library (PPL).
6
7 The PPL is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3 of the License, or (at your
10 option) any later version.
11
12 The PPL is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software Foundation,
19 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA.
20
21 For the most up-to-date information see the Parma Polyhedra Library
22 site: http://bugseng.com/products/ppl/ . */
23
24 #ifndef PPL_Sparse_Row_inlines_hh
25 #define PPL_Sparse_Row_inlines_hh 1
26
27 #include <algorithm>
28
29 namespace Parma_Polyhedra_Library {
30
31 inline
Sparse_Row(dimension_type n)32 Sparse_Row::Sparse_Row(dimension_type n)
33 : size_(n) {
34 PPL_ASSERT(OK());
35 }
36
37 inline
Sparse_Row(dimension_type n,dimension_type)38 Sparse_Row::Sparse_Row(dimension_type n, dimension_type)
39 : size_(n) {
40 PPL_ASSERT(OK());
41 }
42
43 inline
Sparse_Row(const Sparse_Row & y,dimension_type)44 Sparse_Row::Sparse_Row(const Sparse_Row& y, dimension_type)
45 : tree(y.tree), size_(y.size_) {
46 }
47
48 inline
Sparse_Row(const Sparse_Row & y,dimension_type sz,dimension_type)49 Sparse_Row::Sparse_Row(const Sparse_Row& y, dimension_type sz, dimension_type)
50 : tree(y.begin(),
51 std::distance(y.begin(), y.lower_bound(std::min(y.size(), sz)))),
52 size_(sz) {
53 PPL_ASSERT(OK());
54 }
55
56 inline void
m_swap(Sparse_Row & x)57 Sparse_Row::m_swap(Sparse_Row& x) {
58 using std::swap;
59 swap(tree, x.tree);
60 swap(size_, x.size_);
61 PPL_ASSERT(OK());
62 PPL_ASSERT(x.OK());
63 }
64
65 inline dimension_type
size() const66 Sparse_Row::size() const {
67 return size_;
68 }
69
70 inline dimension_type
num_stored_elements() const71 Sparse_Row::num_stored_elements() const {
72 return tree.size();
73 }
74
75 inline void
resize(dimension_type n)76 Sparse_Row::resize(dimension_type n) {
77 if (n < size_) {
78 reset_after(n);
79 }
80 size_ = n;
81 PPL_ASSERT(OK());
82 }
83
84 inline void
shrink(dimension_type n)85 Sparse_Row::shrink(dimension_type n) {
86 PPL_ASSERT(size() >= n);
87 resize(n);
88 }
89
90 inline void
expand_within_capacity(dimension_type n)91 Sparse_Row::expand_within_capacity(dimension_type n) {
92 PPL_ASSERT(size() <= n);
93 resize(n);
94 }
95
96 inline void
delete_element_and_shift(dimension_type i)97 Sparse_Row::delete_element_and_shift(dimension_type i) {
98 PPL_ASSERT(i < size_);
99 tree.erase_element_and_shift_left(i);
100 --size_;
101 PPL_ASSERT(OK());
102 }
103
104 inline void
add_zeroes_and_shift(dimension_type n,dimension_type i)105 Sparse_Row::add_zeroes_and_shift(dimension_type n, dimension_type i) {
106 PPL_ASSERT(i <= size_);
107 tree.increase_keys_from(i, n);
108 size_ += n;
109 PPL_ASSERT(OK());
110 }
111
112 inline Sparse_Row::iterator
begin()113 Sparse_Row::begin() {
114 return tree.begin();
115 }
116
117 inline const Sparse_Row::iterator&
end()118 Sparse_Row::end() {
119 return tree.end();
120 }
121
122 inline Sparse_Row::const_iterator
begin() const123 Sparse_Row::begin() const {
124 return tree.cbegin();
125 }
126
127 inline const Sparse_Row::const_iterator&
end() const128 Sparse_Row::end() const {
129 return tree.cend();
130 }
131
132 inline Sparse_Row::const_iterator
cbegin() const133 Sparse_Row::cbegin() const {
134 return tree.cbegin();
135 }
136
137 inline const Sparse_Row::const_iterator&
cend() const138 Sparse_Row::cend() const {
139 return tree.cend();
140 }
141
142 inline dimension_type
max_size()143 Sparse_Row::max_size() {
144 return CO_Tree::max_size();
145 }
146
147 inline void
clear()148 Sparse_Row::clear() {
149 tree.clear();
150 }
151
152 inline Coefficient&
operator [](dimension_type i)153 Sparse_Row::operator[](dimension_type i) {
154 PPL_ASSERT(i < size_);
155 iterator itr = insert(i);
156 return *itr;
157 }
158
159 inline Coefficient_traits::const_reference
operator [](dimension_type i) const160 Sparse_Row::operator[](dimension_type i) const {
161 return get(i);
162 }
163
164 inline Coefficient_traits::const_reference
get(dimension_type i) const165 Sparse_Row::get(dimension_type i) const {
166 PPL_ASSERT(i < size_);
167 if (tree.empty()) {
168 return Coefficient_zero();
169 }
170 const_iterator itr = find(i);
171 if (itr != end()) {
172 return *itr;
173 }
174 else {
175 return Coefficient_zero();
176 }
177 }
178
179 inline Sparse_Row::iterator
find(dimension_type i)180 Sparse_Row::find(dimension_type i) {
181 PPL_ASSERT(i < size());
182
183 iterator itr = tree.bisect(i);
184
185 if (itr != end() && itr.index() == i) {
186 return itr;
187 }
188 return end();
189 }
190
191 inline Sparse_Row::iterator
find(iterator hint,dimension_type i)192 Sparse_Row::find(iterator hint, dimension_type i) {
193 PPL_ASSERT(i < size());
194
195 iterator itr = tree.bisect_near(hint, i);
196
197 if (itr != end() && itr.index() == i) {
198 return itr;
199 }
200 return end();
201 }
202
203 inline Sparse_Row::const_iterator
find(dimension_type i) const204 Sparse_Row::find(dimension_type i) const {
205 PPL_ASSERT(i < size());
206
207 const_iterator itr = tree.bisect(i);
208
209 if (itr != end() && itr.index() == i) {
210 return itr;
211 }
212
213 return end();
214 }
215
216 inline Sparse_Row::const_iterator
find(const_iterator hint,dimension_type i) const217 Sparse_Row::find(const_iterator hint, dimension_type i) const {
218 PPL_ASSERT(i < size());
219
220 const_iterator itr = tree.bisect_near(hint, i);
221
222 if (itr != end() && itr.index() == i) {
223 return itr;
224 }
225 return end();
226 }
227
228 inline Sparse_Row::iterator
lower_bound(dimension_type i)229 Sparse_Row::lower_bound(dimension_type i) {
230 PPL_ASSERT(i <= size());
231
232 iterator itr = tree.bisect(i);
233
234 if (itr == end()) {
235 return end();
236 }
237
238 if (itr.index() < i) {
239 ++itr;
240 }
241
242 PPL_ASSERT(itr == end() || itr.index() >= i);
243
244 return itr;
245 }
246
247 inline Sparse_Row::iterator
lower_bound(iterator hint,dimension_type i)248 Sparse_Row::lower_bound(iterator hint, dimension_type i) {
249 PPL_ASSERT(i <= size());
250
251 iterator itr = tree.bisect_near(hint, i);
252
253 if (itr == end()) {
254 return end();
255 }
256
257 if (itr.index() < i) {
258 ++itr;
259 }
260
261 PPL_ASSERT(itr == end() || itr.index() >= i);
262
263 return itr;
264 }
265
266 inline Sparse_Row::const_iterator
lower_bound(dimension_type i) const267 Sparse_Row::lower_bound(dimension_type i) const {
268 PPL_ASSERT(i <= size());
269
270 const_iterator itr = tree.bisect(i);
271
272 if (itr == end()) {
273 return end();
274 }
275
276 if (itr.index() < i) {
277 ++itr;
278 }
279
280 PPL_ASSERT(itr == end() || itr.index() >= i);
281
282 return itr;
283 }
284
285 inline Sparse_Row::const_iterator
lower_bound(const_iterator hint,dimension_type i) const286 Sparse_Row::lower_bound(const_iterator hint, dimension_type i) const {
287 PPL_ASSERT(i <= size());
288
289 const_iterator itr = tree.bisect_near(hint, i);
290
291 if (itr == end()) {
292 return end();
293 }
294
295 if (itr.index() < i) {
296 ++itr;
297 }
298
299 PPL_ASSERT(itr == end() || itr.index() >= i);
300
301 return itr;
302 }
303
304 inline Sparse_Row::iterator
insert(dimension_type i,Coefficient_traits::const_reference x)305 Sparse_Row::insert(dimension_type i, Coefficient_traits::const_reference x) {
306 PPL_ASSERT(i < size_);
307 return tree.insert(i, x);
308 }
309
310 inline Sparse_Row::iterator
insert(iterator itr,dimension_type i,Coefficient_traits::const_reference x)311 Sparse_Row::insert(iterator itr, dimension_type i,
312 Coefficient_traits::const_reference x) {
313 PPL_ASSERT(i < size_);
314 return tree.insert(itr, i, x);
315 }
316
317 inline Sparse_Row::iterator
insert(dimension_type i)318 Sparse_Row::insert(dimension_type i) {
319 PPL_ASSERT(i < size_);
320 return tree.insert(i);
321 }
322
323 inline Sparse_Row::iterator
insert(iterator itr,dimension_type i)324 Sparse_Row::insert(iterator itr, dimension_type i) {
325 PPL_ASSERT(i < size_);
326 return tree.insert(itr, i);
327 }
328
329 inline void
swap_coefficients(iterator i,iterator j)330 Sparse_Row::swap_coefficients(iterator i, iterator j) {
331 PPL_ASSERT(i != end());
332 PPL_ASSERT(j != end());
333 using std::swap;
334 swap(*i, *j);
335 PPL_ASSERT(OK());
336 }
337
338 inline void
fast_swap(dimension_type i,iterator itr)339 Sparse_Row::fast_swap(dimension_type i, iterator itr) {
340 PPL_ASSERT(lower_bound(i) == itr);
341 PPL_ASSERT(itr != end());
342 tree.fast_shift(i, itr);
343 PPL_ASSERT(OK());
344 }
345
346 inline Sparse_Row::iterator
reset(iterator i)347 Sparse_Row::reset(iterator i) {
348 iterator res = tree.erase(i);
349 PPL_ASSERT(OK());
350 return res;
351 }
352
353 inline void
reset(dimension_type i)354 Sparse_Row::reset(dimension_type i) {
355 PPL_ASSERT(i < size());
356
357 tree.erase(i);
358 PPL_ASSERT(OK());
359 }
360
361 inline memory_size_type
external_memory_in_bytes() const362 Sparse_Row::external_memory_in_bytes() const {
363 return tree.external_memory_in_bytes();
364 }
365
366 inline memory_size_type
external_memory_in_bytes(dimension_type) const367 Sparse_Row::external_memory_in_bytes(dimension_type /* capacity */) const {
368 return external_memory_in_bytes();
369 }
370
371 inline memory_size_type
total_memory_in_bytes() const372 Sparse_Row::total_memory_in_bytes() const {
373 return external_memory_in_bytes() + sizeof(*this);
374 }
375
376 inline memory_size_type
total_memory_in_bytes(dimension_type) const377 Sparse_Row::total_memory_in_bytes(dimension_type /* capacity */) const {
378 return total_memory_in_bytes();
379 }
380
381 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
382 /*! \relates Sparse_Row */
383 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
384 inline void
swap(Sparse_Row & x,Sparse_Row & y)385 swap(Sparse_Row& x, Sparse_Row& y) {
386 x.m_swap(y);
387 }
388
389 } // namespace Parma_Polyhedra_Library
390
391 #endif // !defined(PPL_Sparse_Row_inlines_hh)
392