1 /* Powerset 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_Powerset_templates_hh
25 #define PPL_Powerset_templates_hh 1
26
27 #include "globals_defs.hh"
28 #include "assertions.hh"
29 #include <iostream>
30 #include <algorithm>
31
32 namespace Parma_Polyhedra_Library {
33
34 template <typename D>
35 void
collapse(const Sequence_iterator sink)36 Powerset<D>::collapse(const Sequence_iterator sink) {
37 PPL_ASSERT(sink != sequence.end());
38 D& d = *sink;
39 iterator x_sink = sink;
40 iterator next_x_sink = x_sink;
41 ++next_x_sink;
42 iterator x_end = end();
43 for (const_iterator xi = next_x_sink; xi != x_end; ++xi) {
44 d.upper_bound_assign(*xi);
45 }
46 // Drop the surplus disjuncts.
47 drop_disjuncts(next_x_sink, x_end);
48
49 // Ensure omega-reduction.
50 for (iterator xi = begin(); xi != x_sink; ) {
51 if (xi->definitely_entails(d)) {
52 xi = drop_disjunct(xi);
53 }
54 else {
55 ++xi;
56 }
57 }
58
59 PPL_ASSERT_HEAVY(OK());
60 }
61
62 template <typename D>
63 void
omega_reduce() const64 Powerset<D>::omega_reduce() const {
65 if (reduced) {
66 return;
67 }
68 Powerset& x = const_cast<Powerset&>(*this);
69 // First remove all bottom elements.
70 for (iterator xi = x.begin(), x_end = x.end(); xi != x_end; ) {
71 if (xi->is_bottom()) {
72 xi = x.drop_disjunct(xi);
73 }
74 else {
75 ++xi;
76 }
77 }
78 // Then remove non-maximal elements.
79 for (iterator xi = x.begin(); xi != x.end(); ) {
80 const D& xv = *xi;
81 bool dropping_xi = false;
82 for (iterator yi = x.begin(); yi != x.end(); ) {
83 if (xi == yi) {
84 ++yi;
85 }
86 else {
87 const D& yv = *yi;
88 if (yv.definitely_entails(xv)) {
89 yi = x.drop_disjunct(yi);
90 }
91 else if (xv.definitely_entails(yv)) {
92 dropping_xi = true;
93 break;
94 }
95 else {
96 ++yi;
97 }
98 }
99 }
100 if (dropping_xi) {
101 xi = x.drop_disjunct(xi);
102 }
103 else {
104 ++xi;
105 }
106 if (abandon_expensive_computations != 0 && xi != x.end()) {
107 // Hurry up!
108 x.collapse(xi.base);
109 break;
110 }
111 }
112 reduced = true;
113 PPL_ASSERT_HEAVY(OK());
114 }
115
116 template <typename D>
117 void
collapse(const unsigned max_disjuncts)118 Powerset<D>::collapse(const unsigned max_disjuncts) {
119 PPL_ASSERT(max_disjuncts > 0);
120 // Omega-reduce before counting the number of disjuncts.
121 omega_reduce();
122 size_type n = size();
123 if (n > max_disjuncts) {
124 // Let `i' point to the last disjunct that will survive.
125 iterator i = begin();
126 std::advance(i, max_disjuncts-1);
127 // This disjunct will be assigned an upper-bound of itself and of
128 // all the disjuncts that follow.
129 collapse(i.base);
130 }
131 PPL_ASSERT_HEAVY(OK());
132 PPL_ASSERT(is_omega_reduced());
133 }
134
135 template <typename D>
136 bool
check_omega_reduced() const137 Powerset<D>::check_omega_reduced() const {
138 for (const_iterator x_begin = begin(), x_end = end(),
139 xi = x_begin; xi != x_end; ++xi) {
140 const D& xv = *xi;
141 if (xv.is_bottom()) {
142 return false;
143 }
144 for (const_iterator yi = x_begin; yi != x_end; ++yi) {
145 if (xi == yi) {
146 continue;
147 }
148 const D& yv = *yi;
149 if (xv.definitely_entails(yv) || yv.definitely_entails(xv)) {
150 return false;
151 }
152 }
153 }
154 return true;
155 }
156
157 template <typename D>
158 bool
is_omega_reduced() const159 Powerset<D>::is_omega_reduced() const {
160 if (!reduced && check_omega_reduced()) {
161 reduced = true;
162 }
163 return reduced;
164 }
165
166 template <typename D>
167 typename Powerset<D>::iterator
add_non_bottom_disjunct_preserve_reduction(const D & d,iterator first,iterator last)168 Powerset<D>::add_non_bottom_disjunct_preserve_reduction(const D& d,
169 iterator first,
170 iterator last) {
171 PPL_ASSERT_HEAVY(!d.is_bottom());
172 for (iterator xi = first; xi != last; ) {
173 const D& xv = *xi;
174 if (d.definitely_entails(xv)) {
175 return first;
176 }
177 else if (xv.definitely_entails(d)) {
178 if (xi == first) {
179 ++first;
180 }
181 xi = drop_disjunct(xi);
182 }
183 else {
184 ++xi;
185 }
186 }
187 sequence.push_back(d);
188 PPL_ASSERT_HEAVY(OK());
189 return first;
190 }
191
192 template <typename D>
193 bool
definitely_entails(const Powerset & y) const194 Powerset<D>::definitely_entails(const Powerset& y) const {
195 const Powerset<D>& x = *this;
196 bool found = true;
197 for (const_iterator xi = x.begin(),
198 x_end = x.end(); found && xi != x_end; ++xi) {
199 found = false;
200 for (const_iterator yi = y.begin(),
201 y_end = y.end(); !found && yi != y_end; ++yi) {
202 found = (*xi).definitely_entails(*yi);
203 }
204 }
205 return found;
206 }
207
208 /*! \relates Powerset */
209 template <typename D>
210 bool
operator ==(const Powerset<D> & x,const Powerset<D> & y)211 operator==(const Powerset<D>& x, const Powerset<D>& y) {
212 x.omega_reduce();
213 y.omega_reduce();
214 if (x.size() != y.size()) {
215 return false;
216 }
217 // Take a copy of `y' and work with it.
218 Powerset<D> z = y;
219 for (typename Powerset<D>::const_iterator xi = x.begin(),
220 x_end = x.end(); xi != x_end; ++xi) {
221 typename Powerset<D>::iterator zi = z.begin();
222 typename Powerset<D>::iterator z_end = z.end();
223 zi = std::find(zi, z_end, *xi);
224 if (zi == z_end) {
225 return false;
226 }
227 else {
228 z.drop_disjunct(zi);
229 }
230 }
231 return true;
232 }
233
234 template <typename D>
235 template <typename Binary_Operator_Assign>
236 void
pairwise_apply_assign(const Powerset & y,Binary_Operator_Assign op_assign)237 Powerset<D>::pairwise_apply_assign(const Powerset& y,
238 Binary_Operator_Assign op_assign) {
239 // Ensure omega-reduction here, since what follows has quadratic complexity.
240 omega_reduce();
241 y.omega_reduce();
242 Sequence new_sequence;
243 for (const_iterator xi = begin(), x_end = end(),
244 y_begin = y.begin(), y_end = y.end(); xi != x_end; ++xi) {
245 for (const_iterator yi = y_begin; yi != y_end; ++yi) {
246 D zi = *xi;
247 op_assign(zi, *yi);
248 if (!zi.is_bottom()) {
249 new_sequence.push_back(zi);
250 }
251 }
252 }
253 // Put the new sequence in place.
254 std::swap(sequence, new_sequence);
255 reduced = false;
256 PPL_ASSERT_HEAVY(OK());
257 }
258
259 template <typename D>
260 void
least_upper_bound_assign(const Powerset & y)261 Powerset<D>::least_upper_bound_assign(const Powerset& y) {
262 // Ensure omega-reduction here, since what follows has quadratic complexity.
263 omega_reduce();
264 y.omega_reduce();
265 iterator old_begin = begin();
266 iterator old_end = end();
267 for (const_iterator i = y.begin(), y_end = y.end(); i != y_end; ++i) {
268 old_begin = add_non_bottom_disjunct_preserve_reduction(*i,
269 old_begin,
270 old_end);
271 }
272 PPL_ASSERT_HEAVY(OK());
273 }
274
275 namespace IO_Operators {
276
277 /*! \relates Parma_Polyhedra_Library::Powerset */
278 template <typename D>
279 std::ostream&
operator <<(std::ostream & s,const Powerset<D> & x)280 operator<<(std::ostream& s, const Powerset<D>& x) {
281 if (x.is_bottom()) {
282 s << "false";
283 }
284 else if (x.is_top()) {
285 s << "true";
286 }
287 else {
288 for (typename Powerset<D>::const_iterator i = x.begin(),
289 x_end = x.end(); i != x_end; ) {
290 s << "{ " << *i << " }";
291 ++i;
292 if (i != x_end) {
293 s << ", ";
294 }
295 }
296 }
297 return s;
298 }
299
300 } // namespace IO_Operators
301
302 template <typename D>
303 memory_size_type
external_memory_in_bytes() const304 Powerset<D>::external_memory_in_bytes() const {
305 memory_size_type bytes = 0;
306 for (const_iterator xi = begin(), x_end = end(); xi != x_end; ++xi) {
307 bytes += xi->total_memory_in_bytes();
308 // We assume there is at least a forward and a backward link, and
309 // that the pointers implementing them are at least the size of
310 // pointers to `D'.
311 bytes += 2*sizeof(D*);
312 }
313 return bytes;
314 }
315
316 template <typename D>
317 bool
OK(const bool disallow_bottom) const318 Powerset<D>::OK(const bool disallow_bottom) const {
319 for (const_iterator xi = begin(), x_end = end(); xi != x_end; ++xi) {
320 if (!xi->OK()) {
321 return false;
322 }
323 if (disallow_bottom && xi->is_bottom()) {
324 #ifndef NDEBUG
325 std::cerr << "Bottom element in powerset!"
326 << std::endl;
327 #endif
328 return false;
329 }
330 }
331 if (reduced && !check_omega_reduced()) {
332 #ifndef NDEBUG
333 std::cerr << "Powerset claims to be reduced, but it is not!"
334 << std::endl;
335 #endif
336 return false;
337 }
338 return true;
339 }
340
341 } // namespace Parma_Polyhedra_Library
342
343 #endif // !defined(PPL_Powerset_templates_hh)
344