1 /* Interval_Info class declaration and implementation.
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_Interval_Info_defs_hh
25 #define PPL_Interval_Info_defs_hh 1
26
27 #include "Boundary_defs.hh"
28 #include <iostream>
29
30 namespace Parma_Polyhedra_Library {
31
32 namespace Interval_NS {
33
34 struct Property {
35 enum Type {
36 CARDINALITY_0_,
37 CARDINALITY_1_,
38 CARDINALITY_IS_
39 };
40 typedef bool Value;
41 static const Value default_value = true;
42 static const Value unsupported_value = false;
PropertyParma_Polyhedra_Library::Interval_NS::Property43 Property(Type t)
44 : type(t) {
45 }
46 Type type;
47 };
48
49 const Property CARDINALITY_0(Property::CARDINALITY_0_);
50 const Property CARDINALITY_1(Property::CARDINALITY_1_);
51 const Property CARDINALITY_IS(Property::CARDINALITY_IS_);
52
53 template <typename T>
54 inline void
reset_bits(T & bits)55 reset_bits(T& bits) {
56 bits = 0;
57 }
58
59 template <typename T>
60 inline void
reset_bit(T & bits,unsigned int bit)61 reset_bit(T& bits, unsigned int bit) {
62 bits &= ~(static_cast<T>(1) << bit);
63 }
64
65 template <typename T>
66 inline void
set_bit(T & bits,unsigned int bit,bool value)67 set_bit(T& bits, unsigned int bit, bool value) {
68 if (value) {
69 bits |= static_cast<T>(1) << bit;
70 }
71 else {
72 reset_bit(bits, bit);
73 }
74 }
75
76 template <typename T>
77 inline bool
get_bit(const T & bits,unsigned int bit)78 get_bit(const T& bits, unsigned int bit) {
79 return (bits & (static_cast<T>(1) << bit)) != 0;
80 }
81
82 template <typename T>
83 inline void
set_bits(T & bits,unsigned int start,unsigned int len,T value)84 set_bits(T& bits, unsigned int start, unsigned int len, T value) {
85 bits &= ~(((static_cast<T>(1) << len) - 1) << start);
86 bits |= value << start;
87 }
88
89 template <typename T>
90 inline T
get_bits(T & bits,unsigned int start,unsigned int len)91 get_bits(T& bits, unsigned int start, unsigned int len) {
92 return (bits >> start) & ((static_cast<T>(1) << len) - 1);
93 }
94
95 } // namespace Interval_NS
96
97 using namespace Interval_NS;
98 using namespace Boundary_NS;
99
100
101 template <typename Policy>
102 class Interval_Info_Null {
103 public:
104 const_bool_nodef(may_be_empty, Policy::may_be_empty);
105 const_bool_nodef(may_contain_infinity, Policy::may_contain_infinity);
106 const_bool_nodef(check_inexact, Policy::check_inexact);
107 const_bool_nodef(store_special, false);
108 const_bool_nodef(store_open, false);
109 const_bool_nodef(cache_empty, false);
110 const_bool_nodef(cache_singleton, false);
Interval_Info_Null()111 Interval_Info_Null() {
112 }
clear()113 void clear() {
114 }
clear_boundary_properties(Boundary_Type)115 void clear_boundary_properties(Boundary_Type) {
116 }
117
118 template <typename Property>
set_boundary_property(Boundary_Type,const Property &,typename Property::Value=Property::default_value)119 void set_boundary_property(Boundary_Type, const Property&, typename Property::Value = Property::default_value) {
120 }
121 template <typename Property>
get_boundary_property(Boundary_Type,const Property &) const122 typename Property::Value get_boundary_property(Boundary_Type, const Property&) const {
123 return Property::unsupported_value;
124 }
125 template <typename Property>
set_interval_property(const Property &,typename Property::Value=Property::default_value)126 void set_interval_property(const Property&, typename Property::Value = Property::default_value) {
127 }
128 template <typename Property>
get_interval_property(const Property &) const129 typename Property::Value get_interval_property(const Property&) const {
130 return Property::unsupported_value;
131 }
132
133 //! Swaps \p *this with \p y.
134 void m_swap(Interval_Info_Null& y);
135
136 void ascii_dump(std::ostream& s) const;
137 bool ascii_load(std::istream& s);
138 };
139
140 template <typename Policy>
141 class Interval_Info_Null_Open : public Interval_Info_Null<Policy> {
142 public:
143 const_bool_nodef(store_open, true);
Interval_Info_Null_Open(bool o)144 Interval_Info_Null_Open(bool o)
145 : open(o) {
146 }
get_boundary_property(Boundary_Type,const Boundary_NS::Property & p) const147 bool get_boundary_property(Boundary_Type,
148 const Boundary_NS::Property& p) const {
149 if (p.type == Boundary_NS::Property::OPEN_) {
150 return open;
151 }
152 else {
153 return Boundary_NS::Property::unsupported_value;
154 }
155 }
156
157 void ascii_dump(std::ostream& s) const;
158 bool ascii_load(std::istream& s);
159
160 private:
161 bool open;
162 };
163
164
165 template <typename T, typename Policy>
166 class Interval_Info_Bitset {
167 public:
168 const_bool_nodef(may_be_empty, Policy::may_be_empty);
169 const_bool_nodef(may_contain_infinity, Policy::may_contain_infinity);
170 const_bool_nodef(check_inexact, Policy::check_inexact);
171 const_bool_nodef(store_special, Policy::store_special);
172 const_bool_nodef(store_open, Policy::store_open);
173 const_bool_nodef(cache_empty, Policy::cache_empty);
174 const_bool_nodef(cache_singleton, Policy::cache_singleton);
175 const_int_nodef(lower_special_bit, Policy::next_bit);
176 const_int_nodef(lower_open_bit, lower_special_bit + (store_special ? 1 : 0));
177 const_int_nodef(upper_special_bit, lower_open_bit + (store_open ? 1 : 0));
178 const_int_nodef(upper_open_bit, upper_special_bit + (store_special ? 1 : 0));
179 const_int_nodef(cardinality_is_bit, upper_open_bit + (store_open ? 1 : 0));
180 const_int_nodef(cardinality_0_bit, cardinality_is_bit
181 + ((cache_empty || cache_singleton) ? 1 : 0));
182 const_int_nodef(cardinality_1_bit, cardinality_0_bit + (cache_empty ? 1 : 0));
183 const_int_nodef(next_bit, cardinality_1_bit + (cache_singleton ? 1 : 0));
184
Interval_Info_Bitset()185 Interval_Info_Bitset() {
186 // FIXME: would we have speed benefits with uninitialized info?
187 // (Dirty_Temp)
188 clear();
189 }
190
clear()191 void clear() {
192 reset_bits(bitset);
193 }
clear_boundary_properties(Boundary_Type t)194 void clear_boundary_properties(Boundary_Type t) {
195 set_boundary_property(t, SPECIAL, false);
196 set_boundary_property(t, OPEN, false);
197 }
set_boundary_property(Boundary_Type t,const Boundary_NS::Property & p,bool value=true)198 void set_boundary_property(Boundary_Type t,
199 const Boundary_NS::Property& p,
200 bool value = true) {
201 switch (p.type) {
202 case Boundary_NS::Property::SPECIAL_:
203 if (store_special) {
204 if (t == LOWER) {
205 set_bit(bitset, lower_special_bit, value);
206 }
207 else {
208 set_bit(bitset, upper_special_bit, value);
209 }
210 }
211 break;
212 case Boundary_NS::Property::OPEN_:
213 if (store_open) {
214 if (t == LOWER) {
215 set_bit(bitset, lower_open_bit, value);
216 }
217 else {
218 set_bit(bitset, upper_open_bit, value);
219 }
220 }
221 break;
222 default:
223 break;
224 }
225 }
get_boundary_property(Boundary_Type t,const Boundary_NS::Property & p) const226 bool get_boundary_property(Boundary_Type t, const Boundary_NS::Property& p) const {
227 switch (p.type) {
228 case Boundary_NS::Property::SPECIAL_:
229 if (!store_special) {
230 return false;
231 }
232 if (t == LOWER) {
233 return get_bit(bitset, lower_special_bit);
234 }
235 else {
236 return get_bit(bitset, upper_special_bit);
237 }
238 case Boundary_NS::Property::OPEN_:
239 if (!store_open) {
240 return false;
241 }
242 else if (t == LOWER) {
243 return get_bit(bitset, lower_open_bit);
244 }
245 else {
246 return get_bit(bitset, upper_open_bit);
247 }
248 default:
249 return false;
250 }
251 }
set_interval_property(const Interval_NS::Property & p,bool value=true)252 void set_interval_property(const Interval_NS::Property& p, bool value = true) {
253 switch (p.type) {
254 case Interval_NS::Property::CARDINALITY_0_:
255 if (cache_empty) {
256 set_bit(bitset, cardinality_0_bit, value);
257 }
258 break;
259 case Interval_NS::Property::CARDINALITY_1_:
260 if (cache_singleton) {
261 set_bit(bitset, cardinality_1_bit, value);
262 }
263 break;
264 case Interval_NS::Property::CARDINALITY_IS_:
265 if (cache_empty || cache_singleton) {
266 set_bit(bitset, cardinality_is_bit, value);
267 }
268 break;
269 default:
270 break;
271 }
272 }
get_interval_property(Interval_NS::Property p) const273 bool get_interval_property(Interval_NS::Property p) const {
274 switch (p.type) {
275 case Interval_NS::Property::CARDINALITY_0_:
276 return cache_empty && get_bit(bitset, cardinality_0_bit);
277 case Interval_NS::Property::CARDINALITY_1_:
278 return cache_singleton && get_bit(bitset, cardinality_1_bit);
279 case Interval_NS::Property::CARDINALITY_IS_:
280 return (cache_empty || cache_singleton)
281 && get_bit(bitset, cardinality_is_bit);
282 default:
283 return false;
284 }
285 }
286
287 //! Swaps \p *this with \p y.
288 void m_swap(Interval_Info_Bitset& y);
289
290 void ascii_dump(std::ostream& s) const;
291 bool ascii_load(std::istream& s);
292
293 protected:
294 T bitset;
295 };
296
297 }
298
299 #include "Interval_Info_inlines.hh"
300
301 #endif // !defined(PPL_Interval_Info_defs_hh)
302