1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
3 /*
4 * Main authors:
5 * Guido Tack <guido.tack@monash.edu>
6 */
7
8 /* This Source Code Form is subject to the terms of the Mozilla Public
9 * License, v. 2.0. If a copy of the MPL was not distributed with this
10 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
11
12 #pragma once
13
14 #include <minizinc/exception.hh>
15 #include <minizinc/gc.hh>
16
17 #include <algorithm>
18 #include <cmath>
19 #include <functional>
20 #include <limits>
21 #include <string>
22 #include <vector>
23
24 namespace MiniZinc {
25 class IntVal;
26 }
27 namespace std {
28 MiniZinc::IntVal abs(const MiniZinc::IntVal& x);
29 }
30
31 namespace MiniZinc {
32
33 class FloatVal;
34
35 class IntVal {
36 friend IntVal operator+(const IntVal& x, const IntVal& y);
37 friend IntVal operator-(const IntVal& x, const IntVal& y);
38 friend IntVal operator*(const IntVal& x, const IntVal& y);
39 friend IntVal operator/(const IntVal& x, const IntVal& y);
40 friend IntVal operator%(const IntVal& x, const IntVal& y);
41 friend IntVal std::abs(const MiniZinc::IntVal& x);
42 friend bool operator==(const IntVal& x, const IntVal& y);
43 friend class FloatVal;
44
45 private:
46 long long int _v;
47 bool _infinity;
IntVal(long long int v,bool infinity)48 IntVal(long long int v, bool infinity) : _v(v), _infinity(infinity) {}
49
safePlus(long long int x,long long int y)50 static long long int safePlus(long long int x, long long int y) {
51 if (x < 0) {
52 if (y < std::numeric_limits<long long int>::min() - x) {
53 throw ArithmeticError("integer overflow");
54 }
55 } else {
56 if (y > std::numeric_limits<long long int>::max() - x) {
57 throw ArithmeticError("integer overflow");
58 }
59 }
60 return x + y;
61 }
safeMinus(long long int x,long long int y)62 static long long int safeMinus(long long int x, long long int y) {
63 if (x < 0) {
64 if (y > x - std::numeric_limits<long long int>::min()) {
65 throw ArithmeticError("integer overflow");
66 }
67 } else {
68 if (y < x - std::numeric_limits<long long int>::max()) {
69 throw ArithmeticError("integer overflow");
70 }
71 }
72 return x - y;
73 }
safeMult(long long int x,long long int y)74 static long long int safeMult(long long int x, long long int y) {
75 if (y == 0) {
76 return 0;
77 }
78 long long unsigned int x_abs = (x < 0 ? 0 - x : x);
79 long long unsigned int y_abs = (y < 0 ? 0 - y : y);
80 if (x_abs > std::numeric_limits<long long int>::max() / y_abs) {
81 throw ArithmeticError("integer overflow");
82 }
83 return x * y;
84 }
safeDiv(long long int x,long long int y)85 static long long int safeDiv(long long int x, long long int y) {
86 if (y == 0) {
87 throw ArithmeticError("integer division by zero");
88 }
89 if (x == 0) {
90 return 0;
91 }
92 if (x == std::numeric_limits<long long int>::min() && y == -1) {
93 throw ArithmeticError("integer overflow");
94 }
95 return x / y;
96 }
safeMod(long long int x,long long int y)97 static long long int safeMod(long long int x, long long int y) {
98 if (y == 0) {
99 throw ArithmeticError("integer division by zero");
100 }
101 if (y == -1) {
102 return 0;
103 }
104 return x % y;
105 }
106
107 public:
IntVal()108 IntVal() : _v(0), _infinity(false) {}
IntVal(long long int v)109 IntVal(long long int v) : _v(v), _infinity(false) {}
110 IntVal(const FloatVal& v);
111
toInt() const112 long long int toInt() const {
113 if (!isFinite()) {
114 throw ArithmeticError("arithmetic operation on infinite value");
115 }
116 return _v;
117 }
118
isFinite() const119 bool isFinite() const { return !_infinity; }
isPlusInfinity() const120 bool isPlusInfinity() const { return _infinity && _v == 1; }
isMinusInfinity() const121 bool isMinusInfinity() const { return _infinity && _v == -1; }
122
operator +=(const IntVal & x)123 IntVal& operator+=(const IntVal& x) {
124 if (!(isFinite() && x.isFinite())) {
125 throw ArithmeticError("arithmetic operation on infinite value");
126 }
127 _v = safePlus(_v, x._v);
128 return *this;
129 }
operator -=(const IntVal & x)130 IntVal& operator-=(const IntVal& x) {
131 if (!(isFinite() && x.isFinite())) {
132 throw ArithmeticError("arithmetic operation on infinite value");
133 }
134 _v = safeMinus(_v, x._v);
135 return *this;
136 }
operator *=(const IntVal & x)137 IntVal& operator*=(const IntVal& x) {
138 if (!(isFinite() && x.isFinite())) {
139 throw ArithmeticError("arithmetic operation on infinite value");
140 }
141 _v = safeMult(_v, x._v);
142 return *this;
143 }
operator /=(const IntVal & x)144 IntVal& operator/=(const IntVal& x) {
145 if (!(isFinite() && x.isFinite())) {
146 throw ArithmeticError("arithmetic operation on infinite value");
147 }
148 _v = safeDiv(_v, x._v);
149 return *this;
150 }
operator -() const151 IntVal operator-() const {
152 IntVal r = *this;
153 r._v = safeMinus(0, _v);
154 return r;
155 }
operator ++()156 IntVal& operator++() {
157 if (!isFinite()) {
158 throw ArithmeticError("arithmetic operation on infinite value");
159 }
160 _v = safePlus(_v, 1);
161 return *this;
162 }
operator ++(int)163 IntVal operator++(int) {
164 if (!isFinite()) {
165 throw ArithmeticError("arithmetic operation on infinite value");
166 }
167 IntVal ret = *this;
168 _v = safePlus(_v, 1);
169 return ret;
170 }
operator --()171 IntVal& operator--() {
172 if (!isFinite()) {
173 throw ArithmeticError("arithmetic operation on infinite value");
174 }
175 _v = safeMinus(_v, 1);
176 return *this;
177 }
operator --(int)178 IntVal operator--(int) {
179 if (!isFinite()) {
180 throw ArithmeticError("arithmetic operation on infinite value");
181 }
182 IntVal ret = *this;
183 _v = safeMinus(_v, 1);
184 return ret;
185 }
pow(const IntVal & exponent)186 IntVal pow(const IntVal& exponent) {
187 if (!exponent.isFinite() || !isFinite()) {
188 throw ArithmeticError("arithmetic operation on infinite value");
189 }
190 if (exponent == 0) {
191 return 1;
192 }
193 if (exponent == 1) {
194 return *this;
195 }
196 IntVal result = 1;
197 for (int i = 0; i < exponent.toInt(); i++) {
198 result *= *this;
199 }
200 return result;
201 }
202
203 static IntVal minint();
204 static IntVal maxint();
205 static IntVal infinity();
206
207 /// Infinity-safe addition
plus(int x) const208 IntVal plus(int x) const {
209 if (isFinite()) {
210 return safePlus(_v, x);
211 }
212 return *this;
213 }
214 /// Infinity-safe subtraction
minus(int x) const215 IntVal minus(int x) const {
216 if (isFinite()) {
217 return safeMinus(_v, x);
218 }
219 return *this;
220 }
221
hash() const222 size_t hash() const {
223 std::hash<long long int> longhash;
224 return longhash(_v);
225 }
226 };
227
operator ==(const IntVal & x,const IntVal & y)228 inline bool operator==(const IntVal& x, const IntVal& y) {
229 return x._infinity == y._infinity && x._v == y._v;
230 }
operator <=(const IntVal & x,const IntVal & y)231 inline bool operator<=(const IntVal& x, const IntVal& y) {
232 return y.isPlusInfinity() || x.isMinusInfinity() ||
233 (x.isFinite() && y.isFinite() && x.toInt() <= y.toInt());
234 }
operator <(const IntVal & x,const IntVal & y)235 inline bool operator<(const IntVal& x, const IntVal& y) {
236 return (y.isPlusInfinity() && !x.isPlusInfinity()) ||
237 (x.isMinusInfinity() && !y.isMinusInfinity()) ||
238 (x.isFinite() && y.isFinite() && x.toInt() < y.toInt());
239 }
operator >=(const IntVal & x,const IntVal & y)240 inline bool operator>=(const IntVal& x, const IntVal& y) { return y <= x; }
operator >(const IntVal & x,const IntVal & y)241 inline bool operator>(const IntVal& x, const IntVal& y) { return y < x; }
operator !=(const IntVal & x,const IntVal & y)242 inline bool operator!=(const IntVal& x, const IntVal& y) { return !(x == y); }
operator +(const IntVal & x,const IntVal & y)243 inline IntVal operator+(const IntVal& x, const IntVal& y) {
244 if (!(x.isFinite() && y.isFinite())) {
245 throw ArithmeticError("arithmetic operation on infinite value");
246 }
247 return IntVal::safePlus(x._v, y._v);
248 }
operator -(const IntVal & x,const IntVal & y)249 inline IntVal operator-(const IntVal& x, const IntVal& y) {
250 if (!(x.isFinite() && y.isFinite())) {
251 throw ArithmeticError("arithmetic operation on infinite value");
252 }
253 return IntVal::safeMinus(x._v, y._v);
254 }
operator *(const IntVal & x,const IntVal & y)255 inline IntVal operator*(const IntVal& x, const IntVal& y) {
256 if (!x.isFinite()) {
257 if (y.isFinite() && (y._v == 1 || y._v == -1)) {
258 return IntVal(IntVal::safeMult(x._v, y._v), !x.isFinite());
259 }
260 } else if (!y.isFinite()) {
261 if (x.isFinite() && (y._v == 1 || y._v == -1)) {
262 return IntVal(IntVal::safeMult(x._v, y._v), true);
263 }
264 } else {
265 return IntVal::safeMult(x._v, y._v);
266 }
267 throw ArithmeticError("arithmetic operation on infinite value");
268 }
operator /(const IntVal & x,const IntVal & y)269 inline IntVal operator/(const IntVal& x, const IntVal& y) {
270 if (y.isFinite() && (y._v == 1 || y._v == -1)) {
271 return IntVal(IntVal::safeMult(x._v, y._v), !x.isFinite());
272 }
273 if (!(x.isFinite() && y.isFinite())) {
274 throw ArithmeticError("arithmetic operation on infinite value");
275 }
276 return IntVal::safeDiv(x._v, y._v);
277 }
operator %(const IntVal & x,const IntVal & y)278 inline IntVal operator%(const IntVal& x, const IntVal& y) {
279 if (!(x.isFinite() && y.isFinite())) {
280 throw ArithmeticError("arithmetic operation on infinite value");
281 }
282 return IntVal::safeMod(x._v, y._v);
283 }
284 template <class Char, class Traits>
operator <<(std::basic_ostream<Char,Traits> & os,const IntVal & s)285 std::basic_ostream<Char, Traits>& operator<<(std::basic_ostream<Char, Traits>& os,
286 const IntVal& s) {
287 if (s.isMinusInfinity()) {
288 return os << "-infinity";
289 }
290 if (s.isPlusInfinity()) {
291 return os << "infinity";
292 }
293 return os << s.toInt();
294 }
295
296 } // namespace MiniZinc
297
298 namespace std {
abs(const MiniZinc::IntVal & x)299 inline MiniZinc::IntVal abs(const MiniZinc::IntVal& x) {
300 if (!x.isFinite()) {
301 return MiniZinc::IntVal::infinity();
302 }
303 return x < 0 ? MiniZinc::IntVal::safeMinus(0, x._v) : x;
304 }
305
min(const MiniZinc::IntVal & x,const MiniZinc::IntVal & y)306 inline MiniZinc::IntVal min(const MiniZinc::IntVal& x, const MiniZinc::IntVal& y) {
307 return x <= y ? x : y;
308 }
max(const MiniZinc::IntVal & x,const MiniZinc::IntVal & y)309 inline MiniZinc::IntVal max(const MiniZinc::IntVal& x, const MiniZinc::IntVal& y) {
310 return x >= y ? x : y;
311 }
312
313 template <>
314 struct equal_to<MiniZinc::IntVal> {
315 public:
operator ()std::equal_to316 bool operator()(const MiniZinc::IntVal& s0, const MiniZinc::IntVal& s1) const { return s0 == s1; }
317 };
318
319 inline MiniZinc::FloatVal abs(const MiniZinc::FloatVal& x);
320 } // namespace std
321
322 namespace std {
323 template <>
324 struct hash<MiniZinc::IntVal> {
325 public:
operator ()std::hash326 size_t operator()(const MiniZinc::IntVal& s) const { return s.hash(); }
327 };
328 } // namespace std
329
330 namespace MiniZinc {
331
332 class FloatVal {
333 friend FloatVal operator+(const FloatVal& x, const FloatVal& y);
334 friend FloatVal operator-(const FloatVal& x, const FloatVal& y);
335 friend FloatVal operator*(const FloatVal& x, const FloatVal& y);
336 friend FloatVal operator/(const FloatVal& x, const FloatVal& y);
337 friend FloatVal std::abs(const MiniZinc::FloatVal& x);
338 friend bool operator==(const FloatVal& x, const FloatVal& y);
339 friend class IntVal;
340
341 private:
342 double _v;
343 bool _infinity;
checkOverflow() const344 void checkOverflow() const {
345 if (!std::isfinite(_v)) {
346 throw ArithmeticError("overflow in floating point operation");
347 }
348 }
FloatVal(double v,bool infinity)349 FloatVal(double v, bool infinity) : _v(v), _infinity(infinity) { checkOverflow(); }
350
351 public:
FloatVal()352 FloatVal() : _v(0.0), _infinity(false) {}
FloatVal(double v)353 FloatVal(double v) : _v(v), _infinity(false) { checkOverflow(); }
FloatVal(const IntVal & v)354 FloatVal(const IntVal& v) : _v(static_cast<double>(v._v)), _infinity(!v.isFinite()) {}
355
toDouble() const356 double toDouble() const {
357 if (!isFinite()) {
358 throw ArithmeticError("arithmetic operation on infinite value");
359 }
360 return _v;
361 }
362
isFinite() const363 bool isFinite() const { return !_infinity; }
isPlusInfinity() const364 bool isPlusInfinity() const { return _infinity && _v == 1.0; }
isMinusInfinity() const365 bool isMinusInfinity() const { return _infinity && _v == -1.0; }
366
operator +=(const FloatVal & x)367 FloatVal& operator+=(const FloatVal& x) {
368 if (!(isFinite() && x.isFinite())) {
369 throw ArithmeticError("arithmetic operation on infinite value");
370 }
371 _v += x._v;
372 checkOverflow();
373 return *this;
374 }
operator -=(const FloatVal & x)375 FloatVal& operator-=(const FloatVal& x) {
376 if (!(isFinite() && x.isFinite())) {
377 throw ArithmeticError("arithmetic operation on infinite value");
378 }
379 _v -= x._v;
380 checkOverflow();
381 return *this;
382 }
operator *=(const FloatVal & x)383 FloatVal& operator*=(const FloatVal& x) {
384 if (!(isFinite() && x.isFinite())) {
385 throw ArithmeticError("arithmetic operation on infinite value");
386 }
387 _v *= x._v;
388 checkOverflow();
389 return *this;
390 }
operator /=(const FloatVal & x)391 FloatVal& operator/=(const FloatVal& x) {
392 if (!(isFinite() && x.isFinite())) {
393 throw ArithmeticError("arithmetic operation on infinite value");
394 }
395 _v = _v / x._v;
396 checkOverflow();
397 return *this;
398 }
operator -() const399 FloatVal operator-() const {
400 FloatVal r = *this;
401 r._v = -r._v;
402 return r;
403 }
operator ++()404 FloatVal& operator++() {
405 if (!isFinite()) {
406 throw ArithmeticError("arithmetic operation on infinite value");
407 }
408 _v = _v + 1;
409 checkOverflow();
410 return *this;
411 }
operator ++(int)412 FloatVal operator++(int) {
413 if (!isFinite()) {
414 throw ArithmeticError("arithmetic operation on infinite value");
415 }
416 FloatVal ret = *this;
417 _v = _v + 1;
418 checkOverflow();
419 return ret;
420 }
operator --()421 FloatVal& operator--() {
422 if (!isFinite()) {
423 throw ArithmeticError("arithmetic operation on infinite value");
424 }
425 _v = _v - 1;
426 checkOverflow();
427 return *this;
428 }
operator --(int)429 FloatVal operator--(int) {
430 if (!isFinite()) {
431 throw ArithmeticError("arithmetic operation on infinite value");
432 }
433 FloatVal ret = *this;
434 _v = _v - 1;
435 checkOverflow();
436 return ret;
437 }
438
439 static FloatVal infinity();
440
441 /// Infinity-safe addition
plus(int x)442 FloatVal plus(int x) {
443 if (isFinite()) {
444 return (*this) + x;
445 }
446 return *this;
447 }
448 /// Infinity-safe subtraction
minus(int x)449 FloatVal minus(int x) {
450 if (isFinite()) {
451 return (*this) - x;
452 }
453 return *this;
454 }
455
hash() const456 size_t hash() const {
457 std::hash<double> doublehash;
458 return doublehash(_v);
459 }
460 };
461
operator ==(const FloatVal & x,const FloatVal & y)462 inline bool operator==(const FloatVal& x, const FloatVal& y) {
463 return x._infinity == y._infinity && x._v == y._v;
464 }
operator <=(const FloatVal & x,const FloatVal & y)465 inline bool operator<=(const FloatVal& x, const FloatVal& y) {
466 return y.isPlusInfinity() || x.isMinusInfinity() ||
467 (x.isFinite() && y.isFinite() && x.toDouble() <= y.toDouble());
468 }
operator <(const FloatVal & x,const FloatVal & y)469 inline bool operator<(const FloatVal& x, const FloatVal& y) {
470 return (y.isPlusInfinity() && !x.isPlusInfinity()) ||
471 (x.isMinusInfinity() && !y.isMinusInfinity()) ||
472 (x.isFinite() && y.isFinite() && x.toDouble() < y.toDouble());
473 }
operator >=(const FloatVal & x,const FloatVal & y)474 inline bool operator>=(const FloatVal& x, const FloatVal& y) { return y <= x; }
operator >(const FloatVal & x,const FloatVal & y)475 inline bool operator>(const FloatVal& x, const FloatVal& y) { return y < x; }
operator !=(const FloatVal & x,const FloatVal & y)476 inline bool operator!=(const FloatVal& x, const FloatVal& y) { return !(x == y); }
operator +(const FloatVal & x,const FloatVal & y)477 inline FloatVal operator+(const FloatVal& x, const FloatVal& y) {
478 if (!(x.isFinite() && y.isFinite())) {
479 throw ArithmeticError("arithmetic operation on infinite value");
480 }
481 return x.toDouble() + y.toDouble();
482 }
operator -(const FloatVal & x,const FloatVal & y)483 inline FloatVal operator-(const FloatVal& x, const FloatVal& y) {
484 if (!(x.isFinite() && y.isFinite())) {
485 throw ArithmeticError("arithmetic operation on infinite value");
486 }
487 return x.toDouble() - y.toDouble();
488 }
operator *(const FloatVal & x,const FloatVal & y)489 inline FloatVal operator*(const FloatVal& x, const FloatVal& y) {
490 if (!(x.isFinite() && y.isFinite())) {
491 throw ArithmeticError("arithmetic operation on infinite value");
492 }
493 return x.toDouble() * y.toDouble();
494 }
operator /(const FloatVal & x,const FloatVal & y)495 inline FloatVal operator/(const FloatVal& x, const FloatVal& y) {
496 if (!(x.isFinite() && y.isFinite())) {
497 throw ArithmeticError("arithmetic operation on infinite value");
498 }
499 return x.toDouble() / y.toDouble();
500 }
501 template <class Char, class Traits>
operator <<(std::basic_ostream<Char,Traits> & os,const FloatVal & s)502 std::basic_ostream<Char, Traits>& operator<<(std::basic_ostream<Char, Traits>& os,
503 const FloatVal& s) {
504 if (s.isMinusInfinity()) {
505 return os << "-infinity";
506 }
507 if (s.isPlusInfinity()) {
508 return os << "infinity";
509 }
510 return os << s.toDouble();
511 }
512
IntVal(const FloatVal & v)513 inline IntVal::IntVal(const FloatVal& v)
514 : _v(static_cast<long long int>(v._v)), _infinity(!v.isFinite()) {}
515
516 } // namespace MiniZinc
517
518 namespace std {
abs(const MiniZinc::FloatVal & x)519 inline MiniZinc::FloatVal abs(const MiniZinc::FloatVal& x) {
520 if (!x.isFinite()) {
521 return MiniZinc::FloatVal::infinity();
522 }
523 return x.toDouble() < 0 ? MiniZinc::FloatVal(-x.toDouble()) : x;
524 }
525
min(const MiniZinc::FloatVal & x,const MiniZinc::FloatVal & y)526 inline MiniZinc::FloatVal min(const MiniZinc::FloatVal& x, const MiniZinc::FloatVal& y) {
527 return x <= y ? x : y;
528 }
max(const MiniZinc::FloatVal & x,const MiniZinc::FloatVal & y)529 inline MiniZinc::FloatVal max(const MiniZinc::FloatVal& x, const MiniZinc::FloatVal& y) {
530 return x >= y ? x : y;
531 }
532
floor(const MiniZinc::FloatVal & x)533 inline MiniZinc::FloatVal floor(const MiniZinc::FloatVal& x) {
534 if (!x.isFinite()) {
535 return x;
536 }
537 return floor(x.toDouble());
538 }
ceil(const MiniZinc::FloatVal & x)539 inline MiniZinc::FloatVal ceil(const MiniZinc::FloatVal& x) {
540 if (!x.isFinite()) {
541 return x;
542 }
543 return ceil(x.toDouble());
544 }
545
546 template <>
547 struct equal_to<MiniZinc::FloatVal> {
548 public:
operator ()std::equal_to549 bool operator()(const MiniZinc::FloatVal& s0, const MiniZinc::FloatVal& s1) const {
550 return s0 == s1;
551 }
552 };
553 } // namespace std
554
555 namespace std {
556 template <>
557 struct hash<MiniZinc::FloatVal> {
558 public:
operator ()std::hash559 size_t operator()(const MiniZinc::FloatVal& s) const { return s.hash(); }
560 };
561 } // namespace std
562
563 namespace MiniZinc {
564
565 typedef unsigned long long int UIntVal;
566
567 /// An integer set value
568 class IntSetVal : public ASTChunk {
569 public:
570 /// Contiguous range
571 struct Range {
572 /// Range minimum
573 IntVal min;
574 /// Range maximum
575 IntVal max;
576 /// Construct range from \a m to \a n
RangeMiniZinc::IntSetVal::Range577 Range(IntVal m, IntVal n) : min(m), max(n) {}
578 /// Default constructor
RangeMiniZinc::IntSetVal::Range579 Range() {}
580 };
581
582 private:
583 /// Return range at position \a i
get(unsigned int i)584 Range& get(unsigned int i) { return reinterpret_cast<Range*>(_data)[i]; }
585 /// Return range at position \a i
get(unsigned int i) const586 const Range& get(unsigned int i) const { return reinterpret_cast<const Range*>(_data)[i]; }
587 /// Construct empty set
IntSetVal()588 IntSetVal() : ASTChunk(0) {}
589 /// Construct set of single range
590 IntSetVal(IntVal m, IntVal n);
591 /// Construct set from \a s
IntSetVal(const std::vector<Range> & s)592 IntSetVal(const std::vector<Range>& s) : ASTChunk(sizeof(Range) * s.size()) {
593 for (auto i = static_cast<unsigned int>(s.size()); (i--) != 0U;) {
594 get(i) = s[i];
595 }
596 }
597
598 /// Disabled
599 IntSetVal(const IntSetVal& r);
600 /// Disabled
601 IntSetVal& operator=(const IntSetVal& r);
602
603 public:
604 /// Return number of ranges
size() const605 unsigned int size() const { return static_cast<int>(_size / sizeof(Range)); }
606 /// Return minimum, or infinity if set is empty
min() const607 IntVal min() const { return size() == 0 ? IntVal::infinity() : get(0).min; }
608 /// Return maximum, or minus infinity if set is empty
max() const609 IntVal max() const { return size() == 0 ? -IntVal::infinity() : get(size() - 1).max; }
610 /// Return minimum of range \a i
min(unsigned int i) const611 IntVal min(unsigned int i) const {
612 assert(i < size());
613 return get(i).min;
614 }
615 /// Return maximum of range \a i
max(unsigned int i) const616 IntVal max(unsigned int i) const {
617 assert(i < size());
618 return get(i).max;
619 }
620 /// Return width of range \a i
width(unsigned int i) const621 IntVal width(unsigned int i) const {
622 assert(i < size());
623 if (min(i).isFinite() && max(i).isFinite()) {
624 return max(i) - min(i) + 1;
625 }
626 return IntVal::infinity();
627 }
628 /// Return cardinality
card() const629 IntVal card() const {
630 IntVal c = 0;
631 for (unsigned int i = size(); (i--) != 0U;) {
632 if (width(i).isFinite()) {
633 c += width(i);
634 } else {
635 return IntVal::infinity();
636 }
637 }
638 return c;
639 }
640
641 /// Allocate empty set from context
a()642 static IntSetVal* a() {
643 auto* r = static_cast<IntSetVal*>(ASTChunk::alloc(0));
644 new (r) IntSetVal();
645 return r;
646 }
647
648 /// Allocate set \f$\{m,n\}\f$ from context
a(IntVal m,IntVal n)649 static IntSetVal* a(IntVal m, IntVal n) {
650 if (m > n) {
651 return a();
652 }
653 auto* r = static_cast<IntSetVal*>(ASTChunk::alloc(sizeof(Range)));
654 new (r) IntSetVal(m, n);
655 return r;
656 }
657
658 /// Allocate set using iterator \a i
659 template <class I>
ai(I & i)660 static IntSetVal* ai(I& i) {
661 std::vector<Range> s;
662 for (; i(); ++i) {
663 s.push_back(Range(i.min(), i.max()));
664 }
665 auto* r = static_cast<IntSetVal*>(ASTChunk::alloc(sizeof(Range) * s.size()));
666 new (r) IntSetVal(s);
667 return r;
668 }
669
670 /// Allocate set from vector \a s0 (may contain duplicates)
a(const std::vector<IntVal> & s0)671 static IntSetVal* a(const std::vector<IntVal>& s0) {
672 if (s0.empty()) {
673 return a();
674 }
675 std::vector<IntVal> s = s0;
676 std::sort(s.begin(), s.end());
677 std::vector<Range> ranges;
678 IntVal min = s[0];
679 IntVal max = min;
680 for (unsigned int i = 1; i < s.size(); i++) {
681 if (s[i] > max + 1) {
682 ranges.emplace_back(min, max);
683 min = s[i];
684 max = min;
685 } else {
686 max = s[i];
687 }
688 }
689 ranges.emplace_back(min, max);
690 auto* r = static_cast<IntSetVal*>(ASTChunk::alloc(sizeof(Range) * ranges.size()));
691 new (r) IntSetVal(ranges);
692 return r;
693 }
a(const std::vector<Range> & ranges)694 static IntSetVal* a(const std::vector<Range>& ranges) {
695 auto* r = static_cast<IntSetVal*>(ASTChunk::alloc(sizeof(Range) * ranges.size()));
696 new (r) IntSetVal(ranges);
697 return r;
698 }
699
700 /// Check if set contains \a v
contains(const IntVal & v) const701 bool contains(const IntVal& v) const {
702 for (int i = 0; i < size(); i++) {
703 if (v < min(i)) {
704 return false;
705 }
706 if (v <= max(i)) {
707 return true;
708 }
709 }
710 return false;
711 }
712
713 /// Check if it is equal to \a s
equal(const IntSetVal * s) const714 bool equal(const IntSetVal* s) const {
715 if (size() != s->size()) {
716 return false;
717 }
718 for (int i = 0; i < size(); i++) {
719 if (min(i) != s->min(i) || max(i) != s->max(i)) {
720 return false;
721 }
722 }
723 return true;
724 }
725
726 /// Mark for garbage collection
mark()727 void mark() { _gcMark = 1; }
728 };
729
730 /// Iterator over an IntSetVal
731 class IntSetRanges {
732 protected:
733 /// The set value
734 const IntSetVal* _rs;
735 /// The current range
736 int _n;
737
738 public:
739 /// Constructor
IntSetRanges(const IntSetVal * r)740 IntSetRanges(const IntSetVal* r) : _rs(r), _n(0) {}
741 /// Check if iterator is still valid
operator ()() const742 bool operator()() const { return _n < _rs->size(); }
743 /// Move to next range
operator ++()744 void operator++() { ++_n; }
745 /// Return minimum of current range
min() const746 IntVal min() const { return _rs->min(_n); }
747 /// Return maximum of current range
max() const748 IntVal max() const { return _rs->max(_n); }
749 /// Return width of current range
width() const750 IntVal width() const { return _rs->width(_n); }
751 };
752
753 template <class Char, class Traits>
operator <<(std::basic_ostream<Char,Traits> & os,const IntSetVal & s)754 std::basic_ostream<Char, Traits>& operator<<(std::basic_ostream<Char, Traits>& os,
755 const IntSetVal& s) {
756 if (s.size() == 0) {
757 os << "1..0";
758 } else if (s.size() == 1) {
759 // Print the range
760 IntSetRanges isr(&s);
761 os << isr.min() << ".." << isr.max();
762 } else {
763 // Print each element of the set
764 bool first = true;
765 os << "{";
766 for (IntSetRanges isr(&s); isr(); ++isr) {
767 if (!first) {
768 os << ", ";
769 }
770 first = false;
771 for (IntVal v = isr.min(); v < isr.max(); ++v) {
772 os << v;
773 }
774 }
775 os << "}";
776 }
777 return os;
778 }
779
780 /// An integer set value
781 class FloatSetVal : public ASTChunk {
782 public:
783 /// Contiguous range
784 struct Range {
785 /// Range minimum
786 FloatVal min;
787 /// Range maximum
788 FloatVal max;
789 /// Construct range from \a m to \a n
RangeMiniZinc::FloatSetVal::Range790 Range(FloatVal m, FloatVal n) : min(m), max(n) {}
791 /// Default constructor
RangeMiniZinc::FloatSetVal::Range792 Range() {}
793 };
794
795 private:
796 /// Return range at position \a i
get(unsigned int i)797 Range& get(unsigned int i) { return reinterpret_cast<Range*>(_data)[i]; }
798 /// Return range at position \a i
get(unsigned int i) const799 const Range& get(unsigned int i) const { return reinterpret_cast<const Range*>(_data)[i]; }
800 /// Construct empty set
FloatSetVal()801 FloatSetVal() : ASTChunk(0) {}
802 /// Construct set of single range
803 FloatSetVal(FloatVal m, FloatVal n);
804 /// Construct set from \a s
FloatSetVal(const std::vector<Range> & s)805 FloatSetVal(const std::vector<Range>& s) : ASTChunk(sizeof(Range) * s.size()) {
806 for (auto i = static_cast<unsigned int>(s.size()); (i--) != 0U;) {
807 get(i) = s[i];
808 }
809 }
810
811 /// Disabled
812 FloatSetVal(const FloatSetVal& r);
813 /// Disabled
814 FloatSetVal& operator=(const FloatSetVal& r);
815
816 public:
817 /// Return number of ranges
size() const818 unsigned int size() const { return static_cast<int>(_size / sizeof(Range)); }
819 /// Return minimum, or infinity if set is empty
min() const820 FloatVal min() const { return size() == 0 ? FloatVal::infinity() : get(0).min; }
821 /// Return maximum, or minus infinity if set is empty
max() const822 FloatVal max() const { return size() == 0 ? -FloatVal::infinity() : get(size() - 1).max; }
823 /// Return minimum of range \a i
min(unsigned int i) const824 FloatVal min(unsigned int i) const {
825 assert(i < size());
826 return get(i).min;
827 }
828 /// Return maximum of range \a i
max(unsigned int i) const829 FloatVal max(unsigned int i) const {
830 assert(i < size());
831 return get(i).max;
832 }
833 /// Return width of range \a i
width(unsigned int i) const834 FloatVal width(unsigned int i) const {
835 assert(i < size());
836 if (min(i).isFinite() && max(i).isFinite() && min(i) == max(i)) {
837 return 1;
838 }
839 return IntVal::infinity();
840 }
841 /// Return cardinality
card() const842 FloatVal card() const {
843 FloatVal c = 0;
844 for (unsigned int i = size(); (i--) != 0U;) {
845 if (width(i).isFinite()) {
846 c += width(i);
847 } else {
848 return FloatVal::infinity();
849 }
850 }
851 return c;
852 }
853
854 /// Allocate empty set from context
a()855 static FloatSetVal* a() {
856 auto* r = static_cast<FloatSetVal*>(ASTChunk::alloc(0));
857 new (r) FloatSetVal();
858 return r;
859 }
860
861 /// Allocate set \f$\{m,n\}\f$ from context
a(FloatVal m,FloatVal n)862 static FloatSetVal* a(FloatVal m, FloatVal n) {
863 if (m > n) {
864 return a();
865 }
866 auto* r = static_cast<FloatSetVal*>(ASTChunk::alloc(sizeof(Range)));
867 new (r) FloatSetVal(m, n);
868 return r;
869 }
870
871 /// Allocate set using iterator \a i
872 template <class I>
ai(I & i)873 static FloatSetVal* ai(I& i) {
874 std::vector<Range> s;
875 for (; i(); ++i) {
876 s.push_back(Range(i.min(), i.max()));
877 }
878 auto* r = static_cast<FloatSetVal*>(ASTChunk::alloc(sizeof(Range) * s.size()));
879 new (r) FloatSetVal(s);
880 return r;
881 }
882
883 /// Allocate set from vector \a s0 (may contain duplicates)
a(const std::vector<FloatVal> & s0)884 static FloatSetVal* a(const std::vector<FloatVal>& s0) {
885 if (s0.empty()) {
886 return a();
887 }
888 std::vector<FloatVal> s = s0;
889 std::sort(s.begin(), s.end());
890 std::vector<Range> ranges;
891 FloatVal min = s[0];
892 FloatVal max = min;
893 for (unsigned int i = 1; i < s.size(); i++) {
894 if (s[i] > max) {
895 ranges.emplace_back(min, max);
896 min = s[i];
897 max = min;
898 } else {
899 max = s[i];
900 }
901 }
902 ranges.emplace_back(min, max);
903 auto* r = static_cast<FloatSetVal*>(ASTChunk::alloc(sizeof(Range) * ranges.size()));
904 new (r) FloatSetVal(ranges);
905 return r;
906 }
a(const std::vector<Range> & ranges)907 static FloatSetVal* a(const std::vector<Range>& ranges) {
908 auto* r = static_cast<FloatSetVal*>(ASTChunk::alloc(sizeof(Range) * ranges.size()));
909 new (r) FloatSetVal(ranges);
910 return r;
911 }
912
913 /// Check if set contains \a v
contains(const FloatVal & v) const914 bool contains(const FloatVal& v) const {
915 for (int i = 0; i < size(); i++) {
916 if (v < min(i)) {
917 return false;
918 }
919 if (v <= max(i)) {
920 return true;
921 }
922 }
923 return false;
924 }
925
926 /// Check if it is equal to \a s
equal(const FloatSetVal * s) const927 bool equal(const FloatSetVal* s) const {
928 if (size() != s->size()) {
929 return false;
930 }
931 for (int i = 0; i < size(); i++) {
932 if (min(i) != s->min(i) || max(i) != s->max(i)) {
933 return false;
934 }
935 }
936 return true;
937 }
938
939 /// Mark for garbage collection
mark()940 void mark() { _gcMark = 1; }
941 };
942
943 /// Iterator over an IntSetVal
944 class FloatSetRanges {
945 /// The set value
946 const FloatSetVal* _rs;
947 /// The current range
948 int _n;
949
950 public:
951 /// Constructor
FloatSetRanges(const FloatSetVal * r)952 FloatSetRanges(const FloatSetVal* r) : _rs(r), _n(0) {}
953 /// Check if iterator is still valid
operator ()() const954 bool operator()() const { return _n < _rs->size(); }
955 /// Move to next range
operator ++()956 void operator++() { ++_n; }
957 /// Return minimum of current range
min() const958 FloatVal min() const { return _rs->min(_n); }
959 /// Return maximum of current range
max() const960 FloatVal max() const { return _rs->max(_n); }
961 /// Return width of current range
width() const962 FloatVal width() const { return _rs->width(_n); }
963 };
964
965 template <class Char, class Traits>
operator <<(std::basic_ostream<Char,Traits> & os,const FloatSetVal & s)966 std::basic_ostream<Char, Traits>& operator<<(std::basic_ostream<Char, Traits>& os,
967 const FloatSetVal& s) {
968 for (FloatSetRanges isr(&s); isr(); ++isr) {
969 os << isr.min() << ".." << isr.max() << " ";
970 }
971 return os;
972 }
973 } // namespace MiniZinc
974