1 /* Linear_Expression_Impl 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_Linear_Expression_Impl_inlines_hh
25 #define PPL_Linear_Expression_Impl_inlines_hh 1
26
27 #include "math_utilities_defs.hh"
28 #include <stdexcept>
29
30 namespace Parma_Polyhedra_Library {
31
32 template <typename Row>
33 inline dimension_type
max_space_dimension()34 Linear_Expression_Impl<Row>::max_space_dimension() {
35 return Row::max_size() - 1;
36 }
37
38 template <typename Row>
39 inline
Linear_Expression_Impl()40 Linear_Expression_Impl<Row>::Linear_Expression_Impl()
41 : row(1) {
42 PPL_ASSERT(OK());
43 }
44
45 template <typename Row>
46 inline
47 Linear_Expression_Impl<Row>
Linear_Expression_Impl(dimension_type space_dim,bool)48 ::Linear_Expression_Impl(dimension_type space_dim, bool)
49 : row(space_dim + 1) {
50 PPL_ASSERT(OK());
51 }
52
53 template <typename Row>
54 inline
~Linear_Expression_Impl()55 Linear_Expression_Impl<Row>::~Linear_Expression_Impl() {
56 }
57
58 template <typename Row>
59 inline
60 Linear_Expression_Impl<Row>
Linear_Expression_Impl(Coefficient_traits::const_reference n)61 ::Linear_Expression_Impl(Coefficient_traits::const_reference n)
62 : row(1) {
63 if (n != 0) {
64 row.insert(0, n);
65 }
66 PPL_ASSERT(OK());
67 }
68
69 template <typename Row>
70 inline dimension_type
space_dimension() const71 Linear_Expression_Impl<Row>::space_dimension() const {
72 return row.size() - 1;
73 }
74
75 template <typename Row>
76 inline void
set_space_dimension(dimension_type n)77 Linear_Expression_Impl<Row>::set_space_dimension(dimension_type n) {
78 row.resize(n + 1);
79 PPL_ASSERT(OK());
80 }
81
82 template <typename Row>
83 inline Coefficient_traits::const_reference
coefficient(Variable v) const84 Linear_Expression_Impl<Row>::coefficient(Variable v) const {
85 if (v.space_dimension() > space_dimension()) {
86 return Coefficient_zero();
87 }
88 return row.get(v.id() + 1);
89 }
90
91 template <typename Row>
92 inline void
93 Linear_Expression_Impl<Row>
set_coefficient(Variable v,Coefficient_traits::const_reference n)94 ::set_coefficient(Variable v, Coefficient_traits::const_reference n) {
95 PPL_ASSERT(v.space_dimension() <= space_dimension());
96 const dimension_type i = v.space_dimension();
97 if (n == 0) {
98 row.reset(i);
99 }
100 else {
101 row.insert(i, n);
102 }
103 PPL_ASSERT(OK());
104 }
105
106 template <typename Row>
107 inline Coefficient_traits::const_reference
inhomogeneous_term() const108 Linear_Expression_Impl<Row>::inhomogeneous_term() const {
109 return row.get(0);
110 }
111
112 template <typename Row>
113 inline void
114 Linear_Expression_Impl<Row>
set_inhomogeneous_term(Coefficient_traits::const_reference n)115 ::set_inhomogeneous_term(Coefficient_traits::const_reference n) {
116 if (n == 0) {
117 row.reset(0);
118 }
119 else {
120 row.insert(0, n);
121 }
122 PPL_ASSERT(OK());
123 }
124
125 template <typename Row>
126 inline void
swap_space_dimensions(Variable v1,Variable v2)127 Linear_Expression_Impl<Row>::swap_space_dimensions(Variable v1, Variable v2) {
128 row.swap_coefficients(v1.space_dimension(), v2.space_dimension());
129 PPL_ASSERT(OK());
130 }
131
132 template <typename Row>
133 inline void
shift_space_dimensions(Variable v,dimension_type n)134 Linear_Expression_Impl<Row>::shift_space_dimensions(Variable v,
135 dimension_type n) {
136 row.add_zeroes_and_shift(n, v.space_dimension());
137 PPL_ASSERT(OK());
138 }
139
140 template <typename Row>
141 inline memory_size_type
external_memory_in_bytes() const142 Linear_Expression_Impl<Row>::external_memory_in_bytes() const {
143 return row.external_memory_in_bytes();
144 }
145
146 template <typename Row>
147 inline memory_size_type
total_memory_in_bytes() const148 Linear_Expression_Impl<Row>::total_memory_in_bytes() const {
149 return external_memory_in_bytes() + sizeof(*this);
150 }
151
152 template <typename Row>
153 inline Linear_Expression_Impl<Row>&
operator +=(Coefficient_traits::const_reference n)154 Linear_Expression_Impl<Row>::operator+=(Coefficient_traits::const_reference n) {
155 typename Row::iterator itr = row.insert(0);
156 (*itr) += n;
157 if (*itr == 0) {
158 row.reset(itr);
159 }
160 PPL_ASSERT(OK());
161 return *this;
162 }
163
164 template <typename Row>
165 inline Linear_Expression_Impl<Row>&
operator -=(Coefficient_traits::const_reference n)166 Linear_Expression_Impl<Row>::operator-=(Coefficient_traits::const_reference n) {
167 typename Row::iterator itr = row.insert(0);
168 (*itr) -= n;
169 if (*itr == 0) {
170 row.reset(itr);
171 }
172 PPL_ASSERT(OK());
173 return *this;
174 }
175
176 template <typename Row>
177 inline void
normalize()178 Linear_Expression_Impl<Row>::normalize() {
179 row.normalize();
180 PPL_ASSERT(OK());
181 }
182
183 template <>
184 inline bool
is_zero() const185 Linear_Expression_Impl<Sparse_Row>::is_zero() const {
186 return row.num_stored_elements() == 0;
187 }
188
189 template <>
190 inline bool
all_homogeneous_terms_are_zero() const191 Linear_Expression_Impl<Sparse_Row>::all_homogeneous_terms_are_zero() const {
192 return row.lower_bound(1) == row.end();
193 }
194
195 template <>
196 inline bool
all_zeroes(dimension_type start,dimension_type end) const197 Linear_Expression_Impl<Sparse_Row>::all_zeroes(dimension_type start,
198 dimension_type end) const {
199 return row.lower_bound(start) == row.lower_bound(end);
200 }
201
202 template <>
203 inline dimension_type
num_zeroes(dimension_type start,dimension_type end) const204 Linear_Expression_Impl<Sparse_Row>::num_zeroes(dimension_type start,
205 dimension_type end) const {
206 PPL_ASSERT(start <= end);
207 return (end - start)
208 - std::distance(row.lower_bound(start), row.lower_bound(end));
209 }
210
211 template <>
212 inline dimension_type
last_nonzero() const213 Linear_Expression_Impl<Sparse_Row>::last_nonzero() const {
214 if (row.num_stored_elements() == 0) {
215 return 0;
216 }
217 Sparse_Row::const_iterator i = row.end();
218 --i;
219 return i.index();
220 }
221
222 template <>
223 inline dimension_type
224 Linear_Expression_Impl<Sparse_Row>
first_nonzero(dimension_type first,dimension_type last) const225 ::first_nonzero(dimension_type first, dimension_type last) const {
226 PPL_ASSERT(first <= last);
227 PPL_ASSERT(last <= row.size());
228 Sparse_Row::const_iterator i = row.lower_bound(first);
229
230 if (i != row.end() && i.index() < last) {
231 return i.index();
232 }
233 else {
234 return last;
235 }
236 }
237
238 template <>
239 inline dimension_type
240 Linear_Expression_Impl<Sparse_Row>
last_nonzero(dimension_type first,dimension_type last) const241 ::last_nonzero(dimension_type first, dimension_type last) const {
242 PPL_ASSERT(first <= last);
243 PPL_ASSERT(last <= row.size());
244 Sparse_Row::const_iterator itr1 = row.lower_bound(first);
245 Sparse_Row::const_iterator itr2 = row.lower_bound(last);
246
247 if (itr1 == itr2) {
248 return last;
249 }
250
251 --itr2;
252 return itr2.index();
253 }
254
255 template <>
256 inline Representation
representation() const257 Linear_Expression_Impl<Dense_Row>::representation() const {
258 return DENSE;
259 }
260
261 template <>
262 inline Representation
representation() const263 Linear_Expression_Impl<Sparse_Row>::representation() const {
264 return SPARSE;
265 }
266
267 template <>
268 inline void
269 Linear_Expression_Impl<Sparse_Row>::const_iterator
skip_zeroes_forward()270 ::skip_zeroes_forward() {
271 // Nothing to do.
272 }
273
274 template <>
275 inline void
276 Linear_Expression_Impl<Sparse_Row>::const_iterator
skip_zeroes_backward()277 ::skip_zeroes_backward() {
278 // Nothing to do.
279 }
280
281 namespace IO_Operators {
282
283 template <typename Row>
284 inline std::ostream&
operator <<(std::ostream & s,const Linear_Expression_Impl<Row> & e)285 operator<<(std::ostream& s, const Linear_Expression_Impl<Row>& e) {
286 e.print(s);
287 return s;
288 }
289
290 } // namespace IO_Operators
291
292 } // namespace Parma_Polyhedra_Library
293
294 #endif // !defined(PPL_Linear_Expression_Impl_inlines_hh)
295