1 /* 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_Matrix_templates_hh
25 #define PPL_Matrix_templates_hh 1
26
27 namespace Parma_Polyhedra_Library {
28
29 template <typename Row>
Matrix(dimension_type n)30 Matrix<Row>::Matrix(dimension_type n)
31 : rows(n), num_columns_(n) {
32 for (dimension_type i = 0; i < rows.size(); ++i) {
33 rows[i].resize(num_columns_);
34 }
35 PPL_ASSERT(OK());
36 }
37
38 template <typename Row>
Matrix(dimension_type num_rows,dimension_type num_columns)39 Matrix<Row>::Matrix(dimension_type num_rows, dimension_type num_columns)
40 : rows(num_rows), num_columns_(num_columns) {
41 for (dimension_type i = 0; i < rows.size(); ++i) {
42 rows[i].resize(num_columns_);
43 }
44 PPL_ASSERT(OK());
45 }
46
47 template <typename Row>
48 void
resize(dimension_type num_rows,dimension_type num_columns)49 Matrix<Row>::resize(dimension_type num_rows, dimension_type num_columns) {
50 const dimension_type old_num_rows = rows.size();
51 rows.resize(num_rows);
52 if (old_num_rows < num_rows) {
53 for (dimension_type i = old_num_rows; i < num_rows; ++i) {
54 rows[i].resize(num_columns);
55 }
56 if (num_columns_ != num_columns) {
57 num_columns_ = num_columns;
58 for (dimension_type i = 0; i < old_num_rows; ++i) {
59 rows[i].resize(num_columns);
60 }
61 }
62 }
63 else
64 if (num_columns_ != num_columns) {
65 num_columns_ = num_columns;
66 for (dimension_type i = 0; i < num_rows; ++i) {
67 rows[i].resize(num_columns);
68 }
69 }
70 PPL_ASSERT(OK());
71 }
72
73 template <typename Row>
74 void
permute_columns(const std::vector<dimension_type> & cycles)75 Matrix<Row>::permute_columns(const std::vector<dimension_type>& cycles) {
76 PPL_DIRTY_TEMP_COEFFICIENT(tmp);
77 const dimension_type n = cycles.size();
78 PPL_ASSERT(cycles[n - 1] == 0);
79 for (dimension_type k = num_rows(); k-- > 0; ) {
80 Row& rows_k = (*this)[k];
81 for (dimension_type i = 0, j = 0; i < n; i = ++j) {
82 // Make `j' be the index of the next cycle terminator.
83 while (cycles[j] != 0) {
84 ++j;
85 }
86 // Cycles of length less than 2 are not allowed.
87 PPL_ASSERT(j - i >= 2);
88 if (j - i == 2) {
89 // For cycles of length 2 no temporary is needed, just a swap.
90 rows_k.swap_coefficients(cycles[i], cycles[i + 1]);
91 }
92 else {
93 // Longer cycles need a temporary.
94 tmp = rows_k.get(cycles[j - 1]);
95 for (dimension_type l = (j - 1); l > i; --l) {
96 rows_k.swap_coefficients(cycles[l-1], cycles[l]);
97 }
98 if (tmp == 0) {
99 rows_k.reset(cycles[i]);
100 }
101 else {
102 using std::swap;
103 swap(tmp, rows_k[cycles[i]]);
104 }
105 }
106 }
107 }
108 }
109
110 template <typename Row>
111 void
swap_columns(dimension_type i,dimension_type j)112 Matrix<Row>::swap_columns(dimension_type i, dimension_type j) {
113 for (dimension_type k = num_rows(); k-- > 0; ) {
114 (*this)[k].swap_coefficients(i, j);
115 }
116 }
117
118 template <typename Row>
119 void
add_zero_columns(dimension_type n,dimension_type i)120 Matrix<Row>::add_zero_columns(dimension_type n, dimension_type i) {
121 for (dimension_type j = rows.size(); j-- > 0; ) {
122 rows[j].add_zeroes_and_shift(n, i);
123 }
124 num_columns_ += n;
125 PPL_ASSERT(OK());
126 }
127
128 template <typename Row>
129 void
remove_column(dimension_type i)130 Matrix<Row>::remove_column(dimension_type i) {
131 for (dimension_type j = rows.size(); j-- > 0; ) {
132 rows[j].delete_element_and_shift(i);
133 }
134 --num_columns_;
135 PPL_ASSERT(OK());
136 }
137
138 template <typename Row>
139 void
ascii_dump(std::ostream & s) const140 Matrix<Row>::ascii_dump(std::ostream& s) const {
141 s << num_rows() << " x ";
142 s << num_columns() << "\n";
143 for (const_iterator i = begin(), i_end = end(); i !=i_end; ++i) {
144 i->ascii_dump(s);
145 }
146 }
147
PPL_OUTPUT_TEMPLATE_DEFINITIONS_ASCII_ONLY(Row,Matrix<Row>)148 PPL_OUTPUT_TEMPLATE_DEFINITIONS_ASCII_ONLY(Row, Matrix<Row>)
149
150 template <typename Row>
151 bool
152 Matrix<Row>::ascii_load(std::istream& s) {
153 std::string str;
154 dimension_type new_num_rows;
155 dimension_type new_num_cols;
156 if (!(s >> new_num_rows)) {
157 return false;
158 }
159 if (!(s >> str) || str != "x") {
160 return false;
161 }
162 if (!(s >> new_num_cols)) {
163 return false;
164 }
165
166 for (iterator i = rows.begin(), i_end = rows.end();
167 i != i_end; ++i) {
168 i->clear();
169 }
170
171 resize(new_num_rows, new_num_cols);
172
173 for (dimension_type row = 0; row < new_num_rows; ++row) {
174 if (!rows[row].ascii_load(s)) {
175 return false;
176 }
177 }
178
179 // Check invariants.
180 PPL_ASSERT(OK());
181 return true;
182 }
183
184 template <typename Row>
185 memory_size_type
external_memory_in_bytes() const186 Matrix<Row>::external_memory_in_bytes() const {
187 return rows.external_memory_in_bytes();
188 }
189
190 template <typename Row>
191 bool
OK() const192 Matrix<Row>::OK() const {
193 for (const_iterator i = begin(), i_end = end(); i != i_end; ++i) {
194 if (i->size() != num_columns_) {
195 return false;
196 }
197 }
198 return true;
199 }
200
201 /*! \relates Parma_Polyhedra_Library::Matrix */
202 template <typename Row>
203 bool
operator ==(const Matrix<Row> & x,const Matrix<Row> & y)204 operator==(const Matrix<Row>& x, const Matrix<Row>& y) {
205 if (x.num_rows() != y.num_rows()) {
206 return false;
207 }
208 if (x.num_columns() != y.num_columns()) {
209 return false;
210 }
211 for (dimension_type i = x.num_rows(); i-- > 0; ) {
212 if (x[i] != y[i]) {
213 return false;
214 }
215 }
216 return true;
217 }
218
219 /*! \relates Parma_Polyhedra_Library::Matrix */
220 template <typename Row>
221 bool
operator !=(const Matrix<Row> & x,const Matrix<Row> & y)222 operator!=(const Matrix<Row>& x, const Matrix<Row>& y) {
223 return !(x == y);
224 }
225
226 } // namespace Parma_Polyhedra_Library
227
228 #endif // !defined(PPL_Matrix_templates_hh)
229