1 /* Dense_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_Dense_Row_inlines_hh
25 #define PPL_Dense_Row_inlines_hh 1
26
27 #include "assertions.hh"
28 #include <cstddef>
29 #include <limits>
30 #include <algorithm>
31
32 namespace Parma_Polyhedra_Library {
33
34 inline
Impl()35 Dense_Row::Impl::Impl()
36 : size(0), capacity(0), coeff_allocator(), vec(0) {
37 }
38
39 inline
~Impl()40 Dense_Row::Impl::~Impl() {
41 while (size != 0) {
42 --size;
43 vec[size].~Coefficient();
44 }
45 coeff_allocator.deallocate(vec, capacity);
46 }
47
48 inline dimension_type
max_size()49 Dense_Row::max_size() {
50 return std::numeric_limits<size_t>::max() / sizeof(Coefficient);
51 }
52
53 inline dimension_type
size() const54 Dense_Row::size() const {
55 return impl.size;
56 }
57
58 inline dimension_type
capacity() const59 Dense_Row::capacity() const {
60 return impl.capacity;
61 }
62
63 inline
Dense_Row()64 Dense_Row::Dense_Row()
65 : impl() {
66
67 PPL_ASSERT(OK());
68 }
69
70 inline
Dense_Row(const dimension_type sz,const dimension_type capacity)71 Dense_Row::Dense_Row(const dimension_type sz,
72 const dimension_type capacity)
73 : impl() {
74
75 resize(sz, capacity);
76
77 PPL_ASSERT(size() == sz);
78 PPL_ASSERT(impl.capacity == capacity);
79 PPL_ASSERT(OK());
80 }
81
82 inline
Dense_Row(const dimension_type sz)83 Dense_Row::Dense_Row(const dimension_type sz)
84 : impl() {
85
86 resize(sz);
87
88 PPL_ASSERT(size() == sz);
89 PPL_ASSERT(OK());
90 }
91
92 inline
Dense_Row(const Dense_Row & y)93 Dense_Row::Dense_Row(const Dense_Row& y)
94 : impl() {
95 impl.coeff_allocator = y.impl.coeff_allocator;
96 if (y.impl.vec != 0) {
97 impl.capacity = y.capacity();
98 impl.vec = impl.coeff_allocator.allocate(impl.capacity);
99 while (impl.size != y.size()) {
100 new(&impl.vec[impl.size]) Coefficient(y[impl.size]);
101 ++impl.size;
102 }
103 }
104 PPL_ASSERT(size() == y.size());
105 PPL_ASSERT(capacity() == y.capacity());
106 PPL_ASSERT(OK());
107 }
108
109 inline
Dense_Row(const Dense_Row & y,const dimension_type capacity)110 Dense_Row::Dense_Row(const Dense_Row& y,
111 const dimension_type capacity)
112 : impl() {
113 PPL_ASSERT(y.size() <= capacity);
114 PPL_ASSERT(capacity <= max_size());
115
116 impl.capacity = capacity;
117 impl.coeff_allocator = y.impl.coeff_allocator;
118 impl.vec = impl.coeff_allocator.allocate(impl.capacity);
119
120 if (y.impl.vec != 0) {
121 while (impl.size != y.size()) {
122 new(&impl.vec[impl.size]) Coefficient(y[impl.size]);
123 ++impl.size;
124 }
125 }
126
127 PPL_ASSERT(size() == y.size());
128 PPL_ASSERT(impl.capacity == capacity);
129 PPL_ASSERT(OK());
130 }
131
132 inline
Dense_Row(const Dense_Row & y,const dimension_type sz,const dimension_type capacity)133 Dense_Row::Dense_Row(const Dense_Row& y,
134 const dimension_type sz,
135 const dimension_type capacity)
136 : impl() {
137 PPL_ASSERT(sz <= capacity);
138 PPL_ASSERT(capacity <= max_size());
139 PPL_ASSERT(capacity != 0);
140
141 impl.capacity = capacity;
142 impl.coeff_allocator = y.impl.coeff_allocator;
143 impl.vec = impl.coeff_allocator.allocate(impl.capacity);
144
145 const dimension_type n = std::min(sz, y.size());
146 while (impl.size != n) {
147 new(&impl.vec[impl.size]) Coefficient(y[impl.size]);
148 ++impl.size;
149 }
150 while (impl.size != sz) {
151 new(&impl.vec[impl.size]) Coefficient();
152 ++impl.size;
153 }
154
155 PPL_ASSERT(size() == sz);
156 PPL_ASSERT(impl.capacity == capacity);
157 PPL_ASSERT(OK());
158 }
159
160 inline
~Dense_Row()161 Dense_Row::~Dense_Row() {
162 // The `impl' field will be destroyed automatically.
163 }
164
165 inline void
destroy()166 Dense_Row::destroy() {
167 resize(0);
168 impl.coeff_allocator.deallocate(impl.vec, impl.capacity);
169 }
170
171 inline void
m_swap(Dense_Row & y)172 Dense_Row::m_swap(Dense_Row& y) {
173 using std::swap;
174 swap(impl.size, y.impl.size);
175 swap(impl.capacity, y.impl.capacity);
176 swap(impl.coeff_allocator, y.impl.coeff_allocator);
177 swap(impl.vec, y.impl.vec);
178 PPL_ASSERT(OK());
179 PPL_ASSERT(y.OK());
180 }
181
182 inline Dense_Row&
operator =(const Dense_Row & y)183 Dense_Row::operator=(const Dense_Row& y) {
184
185 if (this != &y && size() == y.size()) {
186 // Avoid reallocation.
187
188 for (dimension_type i = size(); i-- > 0; ) {
189 (*this)[i] = y[i];
190 }
191
192 return *this;
193 }
194
195 Dense_Row x(y);
196 swap(*this, x);
197
198 return *this;
199 }
200
201 inline Coefficient&
operator [](const dimension_type k)202 Dense_Row::operator[](const dimension_type k) {
203 PPL_ASSERT(impl.vec != 0);
204 PPL_ASSERT(k < size());
205 return impl.vec[k];
206 }
207
208 inline Coefficient_traits::const_reference
operator [](const dimension_type k) const209 Dense_Row::operator[](const dimension_type k) const {
210 PPL_ASSERT(impl.vec != 0);
211 PPL_ASSERT(k < size());
212 return impl.vec[k];
213 }
214
215 inline void
swap_coefficients(dimension_type i,dimension_type j)216 Dense_Row::swap_coefficients(dimension_type i, dimension_type j) {
217 std::swap((*this)[i], (*this)[j]);
218 }
219
220 inline void
swap_coefficients(iterator i,iterator j)221 Dense_Row::swap_coefficients(iterator i, iterator j) {
222 std::swap(*i, *j);
223 }
224
225 inline void
reset(dimension_type i)226 Dense_Row::reset(dimension_type i) {
227 (*this)[i] = 0;
228 }
229
230 inline Dense_Row::iterator
reset(iterator itr)231 Dense_Row::reset(iterator itr) {
232 *itr = 0;
233 ++itr;
234 return itr;
235 }
236
237 inline Dense_Row::iterator
begin()238 Dense_Row::begin() {
239 return iterator(*this, 0);
240 }
241
242 inline Dense_Row::const_iterator
begin() const243 Dense_Row::begin() const {
244 return const_iterator(*this, 0);
245 }
246
247 inline Dense_Row::iterator
end()248 Dense_Row::end() {
249 return iterator(*this, size());
250 }
251
252 inline Dense_Row::const_iterator
end() const253 Dense_Row::end() const {
254 return const_iterator(*this, size());
255 }
256
257 inline Coefficient_traits::const_reference
get(dimension_type i) const258 Dense_Row::get(dimension_type i) const {
259 return (*this)[i];
260 }
261
262 inline Dense_Row::iterator
find(dimension_type i)263 Dense_Row::find(dimension_type i) {
264 return iterator(*this, i);
265 }
266
267 inline Dense_Row::const_iterator
find(dimension_type i) const268 Dense_Row::find(dimension_type i) const {
269 return const_iterator(*this, i);
270 }
271
272 inline Dense_Row::iterator
find(iterator itr,dimension_type i)273 Dense_Row::find(iterator itr, dimension_type i) {
274 (void)itr;
275 return iterator(*this, i);
276 }
277
278 inline Dense_Row::const_iterator
find(const_iterator itr,dimension_type i) const279 Dense_Row::find(const_iterator itr, dimension_type i) const {
280 (void)itr;
281 return const_iterator(*this, i);
282 }
283
284 inline Dense_Row::iterator
lower_bound(dimension_type i)285 Dense_Row::lower_bound(dimension_type i) {
286 return find(i);
287 }
288
289 inline Dense_Row::const_iterator
lower_bound(dimension_type i) const290 Dense_Row::lower_bound(dimension_type i) const {
291 return find(i);
292 }
293
294 inline Dense_Row::iterator
lower_bound(iterator itr,dimension_type i)295 Dense_Row::lower_bound(iterator itr, dimension_type i) {
296 return find(itr, i);
297 }
298
299 inline Dense_Row::const_iterator
lower_bound(const_iterator itr,dimension_type i) const300 Dense_Row::lower_bound(const_iterator itr, dimension_type i) const {
301 return find(itr, i);
302 }
303
304 inline Dense_Row::iterator
insert(dimension_type i,Coefficient_traits::const_reference x)305 Dense_Row::insert(dimension_type i,
306 Coefficient_traits::const_reference x) {
307 (*this)[i] = x;
308 return find(i);
309 }
310
311 inline Dense_Row::iterator
insert(dimension_type i)312 Dense_Row::insert(dimension_type i) {
313 return find(i);
314 }
315
316 inline Dense_Row::iterator
insert(iterator itr,dimension_type i,Coefficient_traits::const_reference x)317 Dense_Row::insert(iterator itr, dimension_type i,
318 Coefficient_traits::const_reference x) {
319 (void)itr;
320 (*this)[i] = x;
321 return find(i);
322 }
323
324 inline Dense_Row::iterator
insert(iterator itr,dimension_type i)325 Dense_Row::insert(iterator itr, dimension_type i) {
326 (void)itr;
327 return find(i);
328 }
329
330 inline memory_size_type
total_memory_in_bytes() const331 Dense_Row::total_memory_in_bytes() const {
332 return sizeof(*this) + external_memory_in_bytes();
333 }
334
335 inline memory_size_type
total_memory_in_bytes(dimension_type capacity) const336 Dense_Row::total_memory_in_bytes(dimension_type capacity) const {
337 return sizeof(*this) + external_memory_in_bytes(capacity);
338 }
339
340 /*! \relates Dense_Row */
341 inline bool
operator !=(const Dense_Row & x,const Dense_Row & y)342 operator!=(const Dense_Row& x, const Dense_Row& y) {
343 return !(x == y);
344 }
345
346
347 inline
iterator()348 Dense_Row::iterator::iterator()
349 : row(NULL), idx(0) {
350 PPL_ASSERT(OK());
351 }
352
353 inline
iterator(Dense_Row & r,dimension_type i)354 Dense_Row::iterator::iterator(Dense_Row& r, dimension_type i)
355 : row(&r), idx(i) {
356 PPL_ASSERT(OK());
357 }
358
359 inline Coefficient&
operator *()360 Dense_Row::iterator::operator*() {
361 PPL_ASSERT(idx < row->size());
362 return (*row)[idx];
363 }
364
365 inline Coefficient_traits::const_reference
operator *() const366 Dense_Row::iterator::operator*() const {
367 PPL_ASSERT(idx < row->size());
368 return (*row)[idx];
369 }
370
371 inline dimension_type
index() const372 Dense_Row::iterator::index() const {
373 return idx;
374 }
375
376 inline Dense_Row::iterator&
operator ++()377 Dense_Row::iterator::operator++() {
378 PPL_ASSERT(idx < row->size());
379 ++idx;
380 PPL_ASSERT(OK());
381 return *this;
382 }
383
384 inline Dense_Row::iterator
operator ++(int)385 Dense_Row::iterator::operator++(int) {
386 iterator tmp(*this);
387 ++(*this);
388 return tmp;
389 }
390
391 inline Dense_Row::iterator&
operator --()392 Dense_Row::iterator::operator--() {
393 PPL_ASSERT(idx > 0);
394 --idx;
395 PPL_ASSERT(OK());
396 return *this;
397 }
398
399 inline Dense_Row::iterator
operator --(int)400 Dense_Row::iterator::operator--(int) {
401 iterator tmp(*this);
402 --(*this);
403 return tmp;
404 }
405
406 inline bool
operator ==(const iterator & x) const407 Dense_Row::iterator::operator==(const iterator& x) const {
408 return (row == x.row) && (idx == x.idx);
409 }
410
411 inline bool
operator !=(const iterator & x) const412 Dense_Row::iterator::operator!=(const iterator& x) const {
413 return !(*this == x);
414 }
415
416 inline
operator const_iterator() const417 Dense_Row::iterator::operator const_iterator() const {
418 return const_iterator(*row, idx);
419 }
420
421 inline bool
OK() const422 Dense_Row::iterator::OK() const {
423 if (row == NULL) {
424 return true;
425 }
426 // i can be equal to row.size() for past-the-end iterators
427 return (idx <= row->size());
428 }
429
430
431 inline
const_iterator()432 Dense_Row::const_iterator::const_iterator()
433 : row(NULL), idx(0) {
434 PPL_ASSERT(OK());
435 }
436
437 inline
const_iterator(const Dense_Row & r,dimension_type i)438 Dense_Row::const_iterator::const_iterator(const Dense_Row& r,
439 dimension_type i)
440 : row(&r), idx(i) {
441 PPL_ASSERT(OK());
442 }
443
444 inline Coefficient_traits::const_reference
operator *() const445 Dense_Row::const_iterator::operator*() const {
446 PPL_ASSERT(idx < row->size());
447 return (*row)[idx];
448 }
449
450 inline dimension_type
index() const451 Dense_Row::const_iterator::index() const {
452 return idx;
453 }
454
455 inline Dense_Row::const_iterator&
operator ++()456 Dense_Row::const_iterator::operator++() {
457 PPL_ASSERT(idx < row->size());
458 ++idx;
459 PPL_ASSERT(OK());
460 return *this;
461 }
462
463 inline Dense_Row::const_iterator
operator ++(int)464 Dense_Row::const_iterator::operator++(int) {
465 const_iterator tmp(*this);
466 ++(*this);
467 return tmp;
468 }
469
470 inline Dense_Row::const_iterator&
operator --()471 Dense_Row::const_iterator::operator--() {
472 PPL_ASSERT(idx > 0);
473 --idx;
474 PPL_ASSERT(OK());
475 return *this;
476 }
477
478 inline Dense_Row::const_iterator
operator --(int)479 Dense_Row::const_iterator::operator--(int) {
480 const_iterator tmp(*this);
481 --(*this);
482 return tmp;
483 }
484
485 inline bool
operator ==(const const_iterator & x) const486 Dense_Row::const_iterator::operator==(const const_iterator& x) const {
487 return (row == x.row) && (idx == x.idx);
488 }
489
490 inline bool
operator !=(const const_iterator & x) const491 Dense_Row::const_iterator::operator!=(const const_iterator& x) const {
492 return !(*this == x);
493 }
494
495 inline bool
OK() const496 Dense_Row::const_iterator::OK() const {
497 if (row == NULL) {
498 return true;
499 }
500 // i can be equal to row.size() for past-the-end iterators
501 return (idx <= row->size());
502 }
503
504 inline void
linear_combine(Dense_Row & x,const Dense_Row & y,Coefficient_traits::const_reference coeff1,Coefficient_traits::const_reference coeff2)505 linear_combine(Dense_Row& x, const Dense_Row& y,
506 Coefficient_traits::const_reference coeff1,
507 Coefficient_traits::const_reference coeff2) {
508 x.linear_combine(y, coeff1, coeff2);
509 }
510
511 inline void
linear_combine(Dense_Row & x,const Dense_Row & y,Coefficient_traits::const_reference c1,Coefficient_traits::const_reference c2,dimension_type start,dimension_type end)512 linear_combine(Dense_Row& x, const Dense_Row& y,
513 Coefficient_traits::const_reference c1,
514 Coefficient_traits::const_reference c2,
515 dimension_type start, dimension_type end) {
516 x.linear_combine(y, c1, c2, start, end);
517 }
518
519 /*! \relates Dense_Row */
520 inline void
swap(Dense_Row & x,Dense_Row & y)521 swap(Dense_Row& x, Dense_Row& y) {
522 x.m_swap(y);
523 }
524
525 /*! \relates Dense_Row */
526 inline void
iter_swap(std::vector<Dense_Row>::iterator x,std::vector<Dense_Row>::iterator y)527 iter_swap(std::vector<Dense_Row>::iterator x,
528 std::vector<Dense_Row>::iterator y) {
529 swap(*x, *y);
530 }
531
532 } // namespace Parma_Polyhedra_Library
533
534 #endif // !defined(PPL_Dense_Row_inlines_hh)
535