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