1 /* DB_Matrix class implementation: non-inline template 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_DB_Matrix_templates_hh
25 #define PPL_DB_Matrix_templates_hh 1
26
27 namespace Parma_Polyhedra_Library {
28
29 template <typename T>
DB_Matrix(const dimension_type n_rows)30 DB_Matrix<T>::DB_Matrix(const dimension_type n_rows)
31 : rows(n_rows),
32 row_size(n_rows),
33 row_capacity(compute_capacity(n_rows, max_num_columns())) {
34 // Construct in direct order: will destroy in reverse order.
35 for (dimension_type i = 0; i < n_rows; ++i) {
36 rows[i].construct(n_rows, row_capacity);
37 }
38 PPL_ASSERT(OK());
39 }
40
41 template <typename T>
42 template <typename U>
DB_Matrix(const DB_Matrix<U> & y)43 DB_Matrix<T>::DB_Matrix(const DB_Matrix<U>& y)
44 : rows(y.rows.size()),
45 row_size(y.row_size),
46 row_capacity(compute_capacity(y.row_size, max_num_columns())) {
47 // Construct in direct order: will destroy in reverse order.
48 for (dimension_type i = 0, n_rows = rows.size(); i < n_rows; ++i) {
49 rows[i].construct_upward_approximation(y[i], row_capacity);
50 }
51 PPL_ASSERT(OK());
52 }
53
54 template <typename T>
55 void
grow(const dimension_type new_n_rows)56 DB_Matrix<T>::grow(const dimension_type new_n_rows) {
57 const dimension_type old_n_rows = rows.size();
58 PPL_ASSERT(new_n_rows >= old_n_rows);
59
60 if (new_n_rows > old_n_rows) {
61 if (new_n_rows <= row_capacity) {
62 // We can recycle the old rows.
63 if (rows.capacity() < new_n_rows) {
64 // Reallocation will take place.
65 std::vector<DB_Row<T> > new_rows;
66 new_rows.reserve(compute_capacity(new_n_rows, max_num_rows()));
67 new_rows.insert(new_rows.end(), new_n_rows, DB_Row<T>());
68 // Construct the new rows.
69 dimension_type i = new_n_rows;
70 while (i-- > old_n_rows) {
71 new_rows[i].construct(new_n_rows, row_capacity);
72 }
73 // Steal the old rows.
74 ++i;
75 while (i-- > 0) {
76 swap(new_rows[i], rows[i]);
77 }
78 // Put the new vector into place.
79 using std::swap;
80 swap(rows, new_rows);
81 }
82 else {
83 // Reallocation will NOT take place.
84 rows.insert(rows.end(), new_n_rows - old_n_rows, DB_Row<T>());
85 for (dimension_type i = new_n_rows; i-- > old_n_rows; ) {
86 rows[i].construct(new_n_rows, row_capacity);
87 }
88 }
89 }
90 else {
91 // We cannot even recycle the old rows.
92 DB_Matrix new_matrix;
93 new_matrix.rows.reserve(compute_capacity(new_n_rows, max_num_rows()));
94 new_matrix.rows.insert(new_matrix.rows.end(), new_n_rows, DB_Row<T>());
95 // Construct the new rows.
96 new_matrix.row_size = new_n_rows;
97 new_matrix.row_capacity = compute_capacity(new_n_rows,
98 max_num_columns());
99 dimension_type i = new_n_rows;
100 while (i-- > old_n_rows) {
101 new_matrix.rows[i].construct(new_matrix.row_size,
102 new_matrix.row_capacity);
103 }
104 // Copy the old rows.
105 ++i;
106 while (i-- > 0) {
107 // FIXME: copying may be unnecessarily costly.
108 DB_Row<T> new_row(rows[i],
109 new_matrix.row_size,
110 new_matrix.row_capacity);
111 swap(new_matrix.rows[i], new_row);
112 }
113 // Put the new vector into place.
114 m_swap(new_matrix);
115 return;
116 }
117 }
118 // Here we have the right number of rows.
119 if (new_n_rows > row_size) {
120 // We need more columns.
121 if (new_n_rows <= row_capacity) {
122 // But we have enough capacity: we resize existing rows.
123 for (dimension_type i = old_n_rows; i-- > 0; ) {
124 rows[i].expand_within_capacity(new_n_rows);
125 }
126 }
127 else {
128 // Capacity exhausted: we must reallocate the rows and
129 // make sure all the rows have the same capacity.
130 const dimension_type new_row_capacity
131 = compute_capacity(new_n_rows, max_num_columns());
132 for (dimension_type i = old_n_rows; i-- > 0; ) {
133 // FIXME: copying may be unnecessarily costly.
134 DB_Row<T> new_row(rows[i], new_n_rows, new_row_capacity);
135 swap(rows[i], new_row);
136 }
137 row_capacity = new_row_capacity;
138 }
139 // Rows have grown or shrunk.
140 row_size = new_n_rows;
141 }
142 }
143
144 template <typename T>
145 void
resize_no_copy(const dimension_type new_n_rows)146 DB_Matrix<T>::resize_no_copy(const dimension_type new_n_rows) {
147 dimension_type old_n_rows = rows.size();
148
149 if (new_n_rows > old_n_rows) {
150 // Rows will be inserted.
151 if (new_n_rows <= row_capacity) {
152 // We can recycle the old rows.
153 if (rows.capacity() < new_n_rows) {
154 // Reallocation (of vector `rows') will take place.
155 std::vector<DB_Row<T> > new_rows;
156 new_rows.reserve(compute_capacity(new_n_rows, max_num_rows()));
157 new_rows.insert(new_rows.end(), new_n_rows, DB_Row<T>());
158 // Construct the new rows (be careful: each new row must have
159 // the same capacity as each one of the old rows).
160 dimension_type i = new_n_rows;
161 while (i-- > old_n_rows) {
162 new_rows[i].construct(new_n_rows, row_capacity);
163 // Steal the old rows.
164 }
165 ++i;
166 while (i-- > 0) {
167 swap(new_rows[i], rows[i]);
168 }
169 // Put the new vector into place.
170 using std::swap;
171 swap(rows, new_rows);
172 }
173 else {
174 // Reallocation (of vector `rows') will NOT take place.
175 rows.insert(rows.end(), new_n_rows - old_n_rows, DB_Row<T>());
176 // Be careful: each new row must have
177 // the same capacity as each one of the old rows.
178 for (dimension_type i = new_n_rows; i-- > old_n_rows; ) {
179 rows[i].construct(new_n_rows, row_capacity);
180 }
181 }
182 }
183 else {
184 // We cannot even recycle the old rows: allocate a new matrix and swap.
185 DB_Matrix new_matrix(new_n_rows);
186 m_swap(new_matrix);
187 return;
188 }
189 }
190 else if (new_n_rows < old_n_rows) {
191 // Drop some rows.
192 rows.resize(new_n_rows);
193 // Shrink the existing rows.
194 for (dimension_type i = new_n_rows; i-- > 0; ) {
195 rows[i].shrink(new_n_rows);
196 }
197 old_n_rows = new_n_rows;
198 }
199 // Here we have the right number of rows.
200 if (new_n_rows > row_size) {
201 // We need more columns.
202 if (new_n_rows <= row_capacity) {
203 // But we have enough capacity: we resize existing rows.
204 for (dimension_type i = old_n_rows; i-- > 0; ) {
205 rows[i].expand_within_capacity(new_n_rows);
206 }
207 }
208 else {
209 // Capacity exhausted: we must reallocate the rows and
210 // make sure all the rows have the same capacity.
211 const dimension_type new_row_capacity
212 = compute_capacity(new_n_rows, max_num_columns());
213 for (dimension_type i = old_n_rows; i-- > 0; ) {
214 DB_Row<T> new_row(new_n_rows, new_row_capacity);
215 swap(rows[i], new_row);
216 }
217 row_capacity = new_row_capacity;
218 }
219 }
220 // DB_Rows have grown or shrunk.
221 row_size = new_n_rows;
222 }
223
224 template <typename T>
225 void
ascii_dump(std::ostream & s) const226 DB_Matrix<T>::ascii_dump(std::ostream& s) const {
227 const DB_Matrix<T>& x = *this;
228 const char separator = ' ';
229 const dimension_type nrows = x.num_rows();
230 s << nrows << separator << "\n";
231 for (dimension_type i = 0; i < nrows; ++i) {
232 for (dimension_type j = 0; j < nrows; ++j) {
233 using namespace IO_Operators;
234 s << x[i][j] << separator;
235 }
236 s << "\n";
237 }
238 }
239
PPL_OUTPUT_TEMPLATE_DEFINITIONS(T,DB_Matrix<T>)240 PPL_OUTPUT_TEMPLATE_DEFINITIONS(T, DB_Matrix<T>)
241
242 template <typename T>
243 bool
244 DB_Matrix<T>::ascii_load(std::istream& s) {
245 dimension_type nrows;
246 if (!(s >> nrows)) {
247 return false;
248 }
249 resize_no_copy(nrows);
250 DB_Matrix& x = *this;
251 for (dimension_type i = 0; i < nrows; ++i) {
252 for (dimension_type j = 0; j < nrows; ++j) {
253 Result r = input(x[i][j], s, ROUND_CHECK);
254 if (result_relation(r) != VR_EQ || is_minus_infinity(x[i][j])) {
255 return false;
256 }
257 }
258 }
259
260 // Check invariants.
261 PPL_ASSERT(OK());
262 return true;
263 }
264
265 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
266 /*! \relates DB_Matrix */
267 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
268 template <typename T>
269 bool
operator ==(const DB_Matrix<T> & x,const DB_Matrix<T> & y)270 operator==(const DB_Matrix<T>& x, const DB_Matrix<T>& y) {
271 const dimension_type x_num_rows = x.num_rows();
272 if (x_num_rows != y.num_rows()) {
273 return false;
274 }
275 for (dimension_type i = x_num_rows; i-- > 0; ) {
276 if (x[i] != y[i]) {
277 return false;
278 }
279 }
280 return true;
281 }
282
283 template <typename T>
284 memory_size_type
external_memory_in_bytes() const285 DB_Matrix<T>::external_memory_in_bytes() const {
286 memory_size_type n = rows.capacity() * sizeof(DB_Row<T>);
287 for (dimension_type i = num_rows(); i-- > 0; ) {
288 n += rows[i].external_memory_in_bytes(row_capacity);
289 }
290 return n;
291 }
292
293 template <typename T>
294 bool
OK() const295 DB_Matrix<T>::OK() const {
296 #ifndef NDEBUG
297 using std::endl;
298 using std::cerr;
299 #endif
300
301 // The matrix must be square.
302 if (num_rows() != row_size) {
303 #ifndef NDEBUG
304 cerr << "DB_Matrix has fewer columns than rows:\n"
305 << "row_size is " << row_size
306 << ", num_rows() is " << num_rows() << "!"
307 << endl;
308 #endif
309 return false;
310 }
311
312 const DB_Matrix& x = *this;
313 const dimension_type n_rows = x.num_rows();
314 for (dimension_type i = 0; i < n_rows; ++i) {
315 if (!x[i].OK(row_size, row_capacity)) {
316 return false;
317 }
318 }
319
320 // All checks passed.
321 return true;
322 }
323
324 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
325 /*! \relates Parma_Polyhedra_Library::DB_Matrix */
326 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
327 template <typename T>
328 std::ostream&
operator <<(std::ostream & s,const DB_Matrix<T> & c)329 IO_Operators::operator<<(std::ostream& s, const DB_Matrix<T>& c) {
330 const dimension_type n = c.num_rows();
331 for (dimension_type i = 0; i < n; ++i) {
332 for (dimension_type j = 0; j < n; ++j) {
333 s << c[i][j] << " ";
334 }
335 s << "\n";
336 }
337 return s;
338 }
339
340 } // namespace Parma_Polyhedra_Library
341
342 #endif // !defined(PPL_DB_Matrix_templates_hh)
343