A set of benchmarks to compare a new prototype MiniZinc implementation
dekker.one
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#ifndef __MINIZINC_VALUES_HH__
13#define __MINIZINC_VALUES_HH__
14
15#include <minizinc/exception.hh>
16#include <minizinc/gc.hh>
17
18#include <algorithm>
19#include <cmath>
20#include <functional>
21#include <limits>
22#include <string>
23#include <vector>
24
25#ifdef min
26#undef min
27#endif
28#ifdef max
29#undef max
30#endif
31
32namespace MiniZinc {
33class IntVal;
34}
35namespace std {
36MiniZinc::IntVal abs(const MiniZinc::IntVal& x);
37}
38
39namespace MiniZinc {
40
41class FloatVal;
42
43class IntVal {
44 friend IntVal operator+(const IntVal& x, const IntVal& y);
45 friend IntVal operator-(const IntVal& x, const IntVal& y);
46 friend IntVal operator*(const IntVal& x, const IntVal& y);
47 friend IntVal operator/(const IntVal& x, const IntVal& y);
48 friend IntVal operator%(const IntVal& x, const IntVal& y);
49 friend IntVal std::abs(const MiniZinc::IntVal& x);
50 friend bool operator==(const IntVal& x, const IntVal& y);
51 friend class FloatVal;
52
53private:
54 long long int _v;
55 bool _infinity;
56 IntVal(long long int v, bool infinity) : _v(v), _infinity(infinity) {}
57
58 static long long int safePlus(long long int x, long long int y) {
59 if (x < 0) {
60 if (y < std::numeric_limits<long long int>::min() - x)
61 throw ArithmeticError("integer overflow");
62 } else {
63 if (y > std::numeric_limits<long long int>::max() - x)
64 throw ArithmeticError("integer overflow");
65 }
66 return x + y;
67 }
68 static long long int safeMinus(long long int x, long long int y) {
69 if (x < 0) {
70 if (y > x - std::numeric_limits<long long int>::min())
71 throw ArithmeticError("integer overflow");
72 } else {
73 if (y < x - std::numeric_limits<long long int>::max())
74 throw ArithmeticError("integer overflow");
75 }
76 return x - y;
77 }
78 static long long int safeMult(long long int x, long long int y) {
79 if (y == 0) return 0;
80 long long unsigned int x_abs = (x < 0 ? 0 - x : x);
81 long long unsigned int y_abs = (y < 0 ? 0 - y : y);
82 if (x_abs > std::numeric_limits<long long int>::max() / y_abs)
83 throw ArithmeticError("integer overflow");
84 return x * y;
85 }
86 static long long int safeDiv(long long int x, long long int y) {
87 if (y == 0) throw ArithmeticError("integer division by zero");
88 if (x == 0) return 0;
89 if (x == std::numeric_limits<long long int>::min() && y == -1)
90 throw ArithmeticError("integer overflow");
91 return x / y;
92 }
93 static long long int safeMod(long long int x, long long int y) {
94 if (y == 0) throw ArithmeticError("integer division by zero");
95 if (y == -1) return 0;
96 return x % y;
97 }
98
99public:
100 IntVal(void) : _v(0), _infinity(false) {}
101 IntVal(long long int v) : _v(v), _infinity(false) {}
102 IntVal(const FloatVal& v);
103
104 long long int toInt(void) const {
105 if (!isFinite()) throw ArithmeticError("arithmetic operation on infinite value");
106 return _v;
107 }
108
109 long long int toIntUnsafe(void) const;
110
111 bool isFinite(void) const { return !_infinity; }
112 bool isPlusInfinity(void) const { return _infinity && _v == 1; }
113 bool isMinusInfinity(void) const { return _infinity && _v == -1; }
114
115 IntVal& operator+=(const IntVal& x) {
116 if (!(isFinite() && x.isFinite()))
117 throw ArithmeticError("arithmetic operation on infinite value");
118 _v = safePlus(_v, x._v);
119 return *this;
120 }
121 IntVal& operator-=(const IntVal& x) {
122 if (!(isFinite() && x.isFinite()))
123 throw ArithmeticError("arithmetic operation on infinite value");
124 _v = safeMinus(_v, x._v);
125 return *this;
126 }
127 IntVal& operator*=(const IntVal& x) {
128 if (!(isFinite() && x.isFinite()))
129 throw ArithmeticError("arithmetic operation on infinite value");
130 _v = safeMult(_v, x._v);
131 return *this;
132 }
133 IntVal& operator/=(const IntVal& x) {
134 if (!(isFinite() && x.isFinite()))
135 throw ArithmeticError("arithmetic operation on infinite value");
136 _v = safeDiv(_v, x._v);
137 return *this;
138 }
139 IntVal operator-() const {
140 IntVal r = *this;
141 r._v = safeMinus(0, _v);
142 return r;
143 }
144 IntVal& operator++() {
145 if (!isFinite()) throw ArithmeticError("arithmetic operation on infinite value");
146 _v = safePlus(_v, 1);
147 return *this;
148 }
149 IntVal operator++(int) {
150 if (!isFinite()) throw ArithmeticError("arithmetic operation on infinite value");
151 IntVal ret = *this;
152 _v = safePlus(_v, 1);
153 return ret;
154 }
155 IntVal& operator--() {
156 if (!isFinite()) throw ArithmeticError("arithmetic operation on infinite value");
157 _v = safeMinus(_v, 1);
158 return *this;
159 }
160 IntVal operator--(int) {
161 if (!isFinite()) throw ArithmeticError("arithmetic operation on infinite value");
162 IntVal ret = *this;
163 _v = safeMinus(_v, 1);
164 return ret;
165 }
166 IntVal pow(const IntVal& exponent) {
167 if (!exponent.isFinite() || !isFinite())
168 throw ArithmeticError("arithmetic operation on infinite value");
169 if (exponent == 0) return 1;
170 if (exponent == 1) return *this;
171 IntVal result = 1;
172 for (int i = 0; i < exponent.toInt(); i++) {
173 result *= *this;
174 }
175 return result;
176 }
177
178 static const IntVal minint(void);
179 static const IntVal maxint(void);
180 static const IntVal infinity(void);
181
182 /// Infinity-safe addition
183 IntVal plus(int x) const {
184 if (isFinite())
185 return safePlus(_v, x);
186 else
187 return *this;
188 }
189 /// Infinity-safe subtraction
190 IntVal minus(int x) const {
191 if (isFinite())
192 return safeMinus(_v, x);
193 else
194 return *this;
195 }
196
197 size_t hash(void) const {
198 std::hash<long long int> longhash;
199 return longhash(_v);
200 }
201};
202
203inline long long int IntVal::toIntUnsafe(void) const { return _v; }
204
205inline bool operator==(const IntVal& x, const IntVal& y) {
206 return x._infinity == y._infinity && x._v == y._v;
207}
208inline bool operator<=(const IntVal& x, const IntVal& y) {
209 return y.isPlusInfinity() || x.isMinusInfinity() ||
210 (x.isFinite() && y.isFinite() && x.toInt() <= y.toInt());
211}
212inline bool operator<(const IntVal& x, const IntVal& y) {
213 return (y.isPlusInfinity() && !x.isPlusInfinity()) ||
214 (x.isMinusInfinity() && !y.isMinusInfinity()) ||
215 (x.isFinite() && y.isFinite() && x.toInt() < y.toInt());
216}
217inline bool operator>=(const IntVal& x, const IntVal& y) { return y <= x; }
218inline bool operator>(const IntVal& x, const IntVal& y) { return y < x; }
219inline bool operator!=(const IntVal& x, const IntVal& y) { return !(x == y); }
220inline IntVal operator+(const IntVal& x, const IntVal& y) {
221 if (!(x.isFinite() && y.isFinite()))
222 throw ArithmeticError("arithmetic operation on infinite value");
223 return IntVal::safePlus(x._v, y._v);
224}
225inline IntVal operator-(const IntVal& x, const IntVal& y) {
226 if (!(x.isFinite() && y.isFinite()))
227 throw ArithmeticError("arithmetic operation on infinite value");
228 return IntVal::safeMinus(x._v, y._v);
229}
230inline IntVal operator*(const IntVal& x, const IntVal& y) {
231 if (!x.isFinite()) {
232 if (y.isFinite() && (y._v == 1 || y._v == -1))
233 return IntVal(IntVal::safeMult(x._v, y._v), !x.isFinite());
234 } else if (!y.isFinite()) {
235 if (x.isFinite() && (y._v == 1 || y._v == -1))
236 return IntVal(IntVal::safeMult(x._v, y._v), true);
237 } else {
238 return IntVal::safeMult(x._v, y._v);
239 }
240 throw ArithmeticError("arithmetic operation on infinite value");
241}
242inline IntVal operator/(const IntVal& x, const IntVal& y) {
243 if (y.isFinite() && (y._v == 1 || y._v == -1))
244 return IntVal(IntVal::safeMult(x._v, y._v), !x.isFinite());
245 if (!(x.isFinite() && y.isFinite()))
246 throw ArithmeticError("arithmetic operation on infinite value");
247 return IntVal::safeDiv(x._v, y._v);
248}
249inline IntVal operator%(const IntVal& x, const IntVal& y) {
250 if (!(x.isFinite() && y.isFinite()))
251 throw ArithmeticError("arithmetic operation on infinite value");
252 return IntVal::safeMod(x._v, y._v);
253}
254template <class Char, class Traits>
255std::basic_ostream<Char, Traits>& operator<<(std::basic_ostream<Char, Traits>& os,
256 const IntVal& s) {
257 if (s.isMinusInfinity())
258 return os << "-infinity";
259 else if (s.isPlusInfinity())
260 return os << "infinity";
261 else
262 return os << s.toInt();
263}
264
265} // namespace MiniZinc
266
267namespace std {
268inline MiniZinc::IntVal abs(const MiniZinc::IntVal& x) {
269 if (!x.isFinite()) return MiniZinc::IntVal::infinity();
270 return x < 0 ? MiniZinc::IntVal::safeMinus(0, x._v) : x;
271}
272
273inline MiniZinc::IntVal min(const MiniZinc::IntVal& x, const MiniZinc::IntVal& y) {
274 return x <= y ? x : y;
275}
276inline MiniZinc::IntVal max(const MiniZinc::IntVal& x, const MiniZinc::IntVal& y) {
277 return x >= y ? x : y;
278}
279
280template <>
281struct equal_to<MiniZinc::IntVal> {
282public:
283 bool operator()(const MiniZinc::IntVal& s0, const MiniZinc::IntVal& s1) const { return s0 == s1; }
284};
285
286inline MiniZinc::FloatVal abs(const MiniZinc::FloatVal&);
287} // namespace std
288
289namespace std {
290template <>
291struct hash<MiniZinc::IntVal> {
292public:
293 size_t operator()(const MiniZinc::IntVal& s) const { return s.hash(); }
294};
295} // namespace std
296
297namespace MiniZinc {
298
299class FloatVal {
300 friend FloatVal operator+(const FloatVal& x, const FloatVal& y);
301 friend FloatVal operator-(const FloatVal& x, const FloatVal& y);
302 friend FloatVal operator*(const FloatVal& x, const FloatVal& y);
303 friend FloatVal operator/(const FloatVal& x, const FloatVal& y);
304 friend FloatVal std::abs(const MiniZinc::FloatVal& x);
305 friend bool operator==(const FloatVal& x, const FloatVal& y);
306 friend class IntVal;
307
308private:
309 double _v;
310 bool _infinity;
311 void checkOverflow(void) {
312 if (!std::isfinite(_v)) throw ArithmeticError("overflow in floating point operation");
313 }
314 FloatVal(double v, bool infinity) : _v(v), _infinity(infinity) { checkOverflow(); }
315
316public:
317 FloatVal(void) : _v(0.0), _infinity(false) {}
318 FloatVal(double v) : _v(v), _infinity(false) { checkOverflow(); }
319 FloatVal(const IntVal& v) : _v(static_cast<double>(v._v)), _infinity(!v.isFinite()) {}
320
321 double toDouble(void) const {
322 if (!isFinite()) throw ArithmeticError("arithmetic operation on infinite value");
323 return _v;
324 }
325
326 bool isFinite(void) const { return !_infinity; }
327 bool isPlusInfinity(void) const { return _infinity && _v == 1.0; }
328 bool isMinusInfinity(void) const { return _infinity && _v == -1.0; }
329
330 FloatVal& operator+=(const FloatVal& x) {
331 if (!(isFinite() && x.isFinite()))
332 throw ArithmeticError("arithmetic operation on infinite value");
333 _v += x._v;
334 checkOverflow();
335 return *this;
336 }
337 FloatVal& operator-=(const FloatVal& x) {
338 if (!(isFinite() && x.isFinite()))
339 throw ArithmeticError("arithmetic operation on infinite value");
340 _v -= x._v;
341 checkOverflow();
342 return *this;
343 }
344 FloatVal& operator*=(const FloatVal& x) {
345 if (!(isFinite() && x.isFinite()))
346 throw ArithmeticError("arithmetic operation on infinite value");
347 _v *= x._v;
348 checkOverflow();
349 return *this;
350 }
351 FloatVal& operator/=(const FloatVal& x) {
352 if (!(isFinite() && x.isFinite()))
353 throw ArithmeticError("arithmetic operation on infinite value");
354 _v = _v / x._v;
355 checkOverflow();
356 return *this;
357 }
358 FloatVal operator-() const {
359 FloatVal r = *this;
360 r._v = -r._v;
361 return r;
362 }
363 FloatVal& operator++() {
364 if (!isFinite()) throw ArithmeticError("arithmetic operation on infinite value");
365 _v = _v + 1;
366 checkOverflow();
367 return *this;
368 }
369 FloatVal operator++(int) {
370 if (!isFinite()) throw ArithmeticError("arithmetic operation on infinite value");
371 FloatVal ret = *this;
372 _v = _v + 1;
373 checkOverflow();
374 return ret;
375 }
376 FloatVal& operator--() {
377 if (!isFinite()) throw ArithmeticError("arithmetic operation on infinite value");
378 _v = _v - 1;
379 checkOverflow();
380 return *this;
381 }
382 FloatVal operator--(int) {
383 if (!isFinite()) throw ArithmeticError("arithmetic operation on infinite value");
384 FloatVal ret = *this;
385 _v = _v - 1;
386 checkOverflow();
387 return ret;
388 }
389
390 static const FloatVal infinity(void);
391
392 /// Infinity-safe addition
393 FloatVal plus(int x) {
394 if (isFinite())
395 return (*this) + x;
396 else
397 return *this;
398 }
399 /// Infinity-safe subtraction
400 FloatVal minus(int x) {
401 if (isFinite())
402 return (*this) - x;
403 else
404 return *this;
405 }
406
407 size_t hash(void) const {
408 std::hash<double> doublehash;
409 return doublehash(_v);
410 }
411};
412
413inline bool operator==(const FloatVal& x, const FloatVal& y) {
414 return x._infinity == y._infinity && x._v == y._v;
415}
416inline bool operator<=(const FloatVal& x, const FloatVal& y) {
417 return y.isPlusInfinity() || x.isMinusInfinity() ||
418 (x.isFinite() && y.isFinite() && x.toDouble() <= y.toDouble());
419}
420inline bool operator<(const FloatVal& x, const FloatVal& y) {
421 return (y.isPlusInfinity() && !x.isPlusInfinity()) ||
422 (x.isMinusInfinity() && !y.isMinusInfinity()) ||
423 (x.isFinite() && y.isFinite() && x.toDouble() < y.toDouble());
424}
425inline bool operator>=(const FloatVal& x, const FloatVal& y) { return y <= x; }
426inline bool operator>(const FloatVal& x, const FloatVal& y) { return y < x; }
427inline bool operator!=(const FloatVal& x, const FloatVal& y) { return !(x == y); }
428inline FloatVal operator+(const FloatVal& x, const FloatVal& y) {
429 if (!(x.isFinite() && y.isFinite()))
430 throw ArithmeticError("arithmetic operation on infinite value");
431 return x.toDouble() + y.toDouble();
432}
433inline FloatVal operator-(const FloatVal& x, const FloatVal& y) {
434 if (!(x.isFinite() && y.isFinite()))
435 throw ArithmeticError("arithmetic operation on infinite value");
436 return x.toDouble() - y.toDouble();
437}
438inline FloatVal operator*(const FloatVal& x, const FloatVal& y) {
439 if (!(x.isFinite() && y.isFinite()))
440 throw ArithmeticError("arithmetic operation on infinite value");
441 return x.toDouble() * y.toDouble();
442}
443inline FloatVal operator/(const FloatVal& x, const FloatVal& y) {
444 if (!(x.isFinite() && y.isFinite()))
445 throw ArithmeticError("arithmetic operation on infinite value");
446 return x.toDouble() / y.toDouble();
447}
448template <class Char, class Traits>
449std::basic_ostream<Char, Traits>& operator<<(std::basic_ostream<Char, Traits>& os,
450 const FloatVal& s) {
451 if (s.isMinusInfinity())
452 return os << "-infinity";
453 else if (s.isPlusInfinity())
454 return os << "infinity";
455 else
456 return os << s.toDouble();
457}
458
459inline IntVal::IntVal(const FloatVal& v)
460 : _v(static_cast<long long int>(v._v)), _infinity(!v.isFinite()) {}
461
462} // namespace MiniZinc
463
464namespace std {
465inline MiniZinc::FloatVal abs(const MiniZinc::FloatVal& x) {
466 if (!x.isFinite()) return MiniZinc::FloatVal::infinity();
467 return x.toDouble() < 0 ? MiniZinc::FloatVal(-x.toDouble()) : x;
468}
469
470inline MiniZinc::FloatVal min(const MiniZinc::FloatVal& x, const MiniZinc::FloatVal& y) {
471 return x <= y ? x : y;
472}
473inline MiniZinc::FloatVal max(const MiniZinc::FloatVal& x, const MiniZinc::FloatVal& y) {
474 return x >= y ? x : y;
475}
476
477inline MiniZinc::FloatVal floor(const MiniZinc::FloatVal& x) {
478 if (!x.isFinite()) return x;
479 return floor(x.toDouble());
480}
481inline MiniZinc::FloatVal ceil(const MiniZinc::FloatVal& x) {
482 if (!x.isFinite()) return x;
483 return ceil(x.toDouble());
484}
485
486template <>
487struct equal_to<MiniZinc::FloatVal> {
488public:
489 bool operator()(const MiniZinc::FloatVal& s0, const MiniZinc::FloatVal& s1) const {
490 return s0 == s1;
491 }
492};
493} // namespace std
494
495namespace std {
496template <>
497struct hash<MiniZinc::FloatVal> {
498public:
499 size_t operator()(const MiniZinc::FloatVal& s) const { return s.hash(); }
500};
501} // namespace std
502
503namespace MiniZinc {
504
505typedef unsigned long long int UIntVal;
506
507/// An integer set value
508class IntSetVal : public ASTChunk {
509public:
510 /// Contiguous range
511 struct Range {
512 /// Range minimum
513 IntVal min;
514 /// Range maximum
515 IntVal max;
516 /// Construct range from \a m to \a n
517 Range(IntVal m, IntVal n) : min(m), max(n) {}
518 /// Default constructor
519 Range(void) {}
520 };
521
522private:
523 /// Return range at position \a i
524 Range& get(int i) { return reinterpret_cast<Range*>(_data)[i]; }
525 /// Return range at position \a i
526 const Range& get(int i) const { return reinterpret_cast<const Range*>(_data)[i]; }
527 /// Construct empty set
528 IntSetVal(void) : ASTChunk(0) {}
529 /// Construct set of single range
530 IntSetVal(IntVal m, IntVal n);
531 /// Construct set from \a s
532 IntSetVal(const std::vector<Range>& s) : ASTChunk(sizeof(Range) * s.size()) {
533 for (unsigned int i = static_cast<unsigned int>(s.size()); i--;) get(i) = s[i];
534 }
535
536 /// Disabled
537 IntSetVal(const IntSetVal& r);
538 /// Disabled
539 IntSetVal& operator=(const IntSetVal& r);
540
541public:
542 /// Return number of ranges
543 int size(void) const { return static_cast<int>(_size / sizeof(Range)); }
544 /// Return minimum, or infinity if set is empty
545 IntVal min(void) const { return size() == 0 ? IntVal::infinity() : get(0).min; }
546 /// Return maximum, or minus infinity if set is empty
547 IntVal max(void) const { return size() == 0 ? -IntVal::infinity() : get(size() - 1).max; }
548 /// Return minimum of range \a i
549 IntVal min(int i) const {
550 assert(i < size());
551 return get(i).min;
552 }
553 /// Return maximum of range \a i
554 IntVal max(int i) const {
555 assert(i < size());
556 return get(i).max;
557 }
558 /// Return width of range \a i
559 IntVal width(int i) const {
560 assert(i < size());
561 if (min(i).isFinite() && max(i).isFinite())
562 return max(i) - min(i) + 1;
563 else
564 return IntVal::infinity();
565 }
566 /// Return cardinality
567 IntVal card(void) const {
568 IntVal c = 0;
569 for (unsigned int i = size(); i--;) {
570 if (width(i).isFinite())
571 c += width(i);
572 else
573 return IntVal::infinity();
574 }
575 return c;
576 }
577
578 /// Allocate empty set from context
579 static IntSetVal* a(void) {
580 IntSetVal* r = static_cast<IntSetVal*>(ASTChunk::alloc(0));
581 new (r) IntSetVal();
582 return r;
583 }
584
585 /// Allocate set \f$\{m,n\}\f$ from context
586 static IntSetVal* a(IntVal m, IntVal n) {
587 if (m > n) {
588 return a();
589 } else {
590 IntSetVal* r = static_cast<IntSetVal*>(ASTChunk::alloc(sizeof(Range)));
591 new (r) IntSetVal(m, n);
592 return r;
593 }
594 }
595
596 /// Allocate set using iterator \a i
597 template <class I>
598 static IntSetVal* ai(I& i) {
599 std::vector<Range> s;
600 for (; i(); ++i) s.push_back(Range(i.min(), i.max()));
601 IntSetVal* r = static_cast<IntSetVal*>(ASTChunk::alloc(sizeof(Range) * s.size()));
602 new (r) IntSetVal(s);
603 return r;
604 }
605
606 /// Allocate set from vector \a s0 (may contain duplicates)
607 static IntSetVal* a(const std::vector<IntVal>& s0) {
608 if (s0.size() == 0) return a();
609 std::vector<IntVal> s = s0;
610 std::sort(s.begin(), s.end());
611 std::vector<Range> ranges;
612 IntVal min = s[0];
613 IntVal max = min;
614 for (unsigned int i = 1; i < s.size(); i++) {
615 if (s[i] > max + 1) {
616 ranges.push_back(Range(min, max));
617 min = s[i];
618 max = min;
619 } else {
620 max = s[i];
621 }
622 }
623 ranges.push_back(Range(min, max));
624 IntSetVal* r = static_cast<IntSetVal*>(ASTChunk::alloc(sizeof(Range) * ranges.size()));
625 new (r) IntSetVal(ranges);
626 return r;
627 }
628 static IntSetVal* a(const std::vector<Range>& ranges) {
629 IntSetVal* r = static_cast<IntSetVal*>(ASTChunk::alloc(sizeof(Range) * ranges.size()));
630 new (r) IntSetVal(ranges);
631 return r;
632 }
633
634 /// Check if set contains \a v
635 bool contains(const IntVal& v) {
636 for (int i = 0; i < size(); i++) {
637 if (v < min(i)) return false;
638 if (v <= max(i)) return true;
639 }
640 return false;
641 }
642
643 /// Check if it is equal to \a s
644 bool equal(const IntSetVal* s) {
645 if (size() != s->size()) return false;
646 for (int i = 0; i < size(); i++)
647 if (min(i) != s->min(i) || max(i) != s->max(i)) return false;
648 return true;
649 }
650
651 /// Mark for garbage collection
652 void mark(void) { _gc_mark = 1; }
653};
654
655/// Iterator over an IntSetVal
656class IntSetRanges {
657 /// The set value
658 const IntSetVal* rs;
659 /// The current range
660 int n;
661
662public:
663 /// Constructor
664 IntSetRanges(const IntSetVal* r) : rs(r), n(0) {}
665 /// Check if iterator is still valid
666 bool operator()(void) const { return n < rs->size(); }
667 /// Move to next range
668 void operator++(void) { ++n; }
669 /// Return minimum of current range
670 IntVal min(void) const { return rs->min(n); }
671 /// Return maximum of current range
672 IntVal max(void) const { return rs->max(n); }
673 /// Return width of current range
674 IntVal width(void) const { return rs->width(n); }
675};
676
677template <class Char, class Traits>
678std::basic_ostream<Char, Traits>& operator<<(std::basic_ostream<Char, Traits>& os,
679 const IntSetVal& s) {
680 if (s.size() == 0) {
681 os << "1..0";
682 } else if (s.size() == 1) {
683 // Print the range
684 IntSetRanges isr(&s);
685 os << isr.min() << ".." << isr.max();
686 } else {
687 // Print each element of the set
688 bool first = true;
689 os << "{";
690 for (IntSetRanges isr(&s); isr(); ++isr) {
691 if (!first) os << ", ";
692 first = false;
693 for (IntVal v = isr.min(); v < isr.max(); ++v) {
694 os << v;
695 }
696 }
697 os << "}";
698 }
699 return os;
700}
701
702/// An integer set value
703class FloatSetVal : public ASTChunk {
704public:
705 /// Contiguous range
706 struct Range {
707 /// Range minimum
708 FloatVal min;
709 /// Range maximum
710 FloatVal max;
711 /// Construct range from \a m to \a n
712 Range(FloatVal m, FloatVal n) : min(m), max(n) {}
713 /// Default constructor
714 Range(void) {}
715 };
716
717private:
718 /// Return range at position \a i
719 Range& get(int i) { return reinterpret_cast<Range*>(_data)[i]; }
720 /// Return range at position \a i
721 const Range& get(int i) const { return reinterpret_cast<const Range*>(_data)[i]; }
722 /// Construct empty set
723 FloatSetVal(void) : ASTChunk(0) {}
724 /// Construct set of single range
725 FloatSetVal(FloatVal m, FloatVal n);
726 /// Construct set from \a s
727 FloatSetVal(const std::vector<Range>& s) : ASTChunk(sizeof(Range) * s.size()) {
728 for (unsigned int i = static_cast<unsigned int>(s.size()); i--;) get(i) = s[i];
729 }
730
731 /// Disabled
732 FloatSetVal(const FloatSetVal& r);
733 /// Disabled
734 FloatSetVal& operator=(const FloatSetVal& r);
735
736public:
737 /// Return number of ranges
738 int size(void) const { return static_cast<int>(_size / sizeof(Range)); }
739 /// Return minimum, or infinity if set is empty
740 FloatVal min(void) const { return size() == 0 ? FloatVal::infinity() : get(0).min; }
741 /// Return maximum, or minus infinity if set is empty
742 FloatVal max(void) const { return size() == 0 ? -FloatVal::infinity() : get(size() - 1).max; }
743 /// Return minimum of range \a i
744 FloatVal min(int i) const {
745 assert(i < size());
746 return get(i).min;
747 }
748 /// Return maximum of range \a i
749 FloatVal max(int i) const {
750 assert(i < size());
751 return get(i).max;
752 }
753 /// Return width of range \a i
754 FloatVal width(int i) const {
755 assert(i < size());
756 if (min(i).isFinite() && max(i).isFinite() && min(i) == max(i))
757 return 1;
758 else
759 return IntVal::infinity();
760 }
761 /// Return cardinality
762 FloatVal card(void) const {
763 FloatVal c = 0;
764 for (unsigned int i = size(); i--;) {
765 if (width(i).isFinite())
766 c += width(i);
767 else
768 return FloatVal::infinity();
769 }
770 return c;
771 }
772
773 /// Allocate empty set from context
774 static FloatSetVal* a(void) {
775 FloatSetVal* r = static_cast<FloatSetVal*>(ASTChunk::alloc(0));
776 new (r) FloatSetVal();
777 return r;
778 }
779
780 /// Allocate set \f$\{m,n\}\f$ from context
781 static FloatSetVal* a(FloatVal m, FloatVal n) {
782 if (m > n) {
783 return a();
784 } else {
785 FloatSetVal* r = static_cast<FloatSetVal*>(ASTChunk::alloc(sizeof(Range)));
786 new (r) FloatSetVal(m, n);
787 return r;
788 }
789 }
790
791 /// Allocate set using iterator \a i
792 template <class I>
793 static FloatSetVal* ai(I& i) {
794 std::vector<Range> s;
795 for (; i(); ++i) s.push_back(Range(i.min(), i.max()));
796 FloatSetVal* r = static_cast<FloatSetVal*>(ASTChunk::alloc(sizeof(Range) * s.size()));
797 new (r) FloatSetVal(s);
798 return r;
799 }
800
801 /// Allocate set from vector \a s0 (may contain duplicates)
802 static FloatSetVal* a(const std::vector<FloatVal>& s0) {
803 if (s0.size() == 0) return a();
804 std::vector<FloatVal> s = s0;
805 std::sort(s.begin(), s.end());
806 std::vector<Range> ranges;
807 FloatVal min = s[0];
808 FloatVal max = min;
809 for (unsigned int i = 1; i < s.size(); i++) {
810 if (s[i] > max) {
811 ranges.push_back(Range(min, max));
812 min = s[i];
813 max = min;
814 } else {
815 max = s[i];
816 }
817 }
818 ranges.push_back(Range(min, max));
819 FloatSetVal* r = static_cast<FloatSetVal*>(ASTChunk::alloc(sizeof(Range) * ranges.size()));
820 new (r) FloatSetVal(ranges);
821 return r;
822 }
823 static FloatSetVal* a(const std::vector<Range>& ranges) {
824 FloatSetVal* r = static_cast<FloatSetVal*>(ASTChunk::alloc(sizeof(Range) * ranges.size()));
825 new (r) FloatSetVal(ranges);
826 return r;
827 }
828
829 /// Check if set contains \a v
830 bool contains(const FloatVal& v) {
831 for (int i = 0; i < size(); i++) {
832 if (v < min(i)) return false;
833 if (v <= max(i)) return true;
834 }
835 return false;
836 }
837
838 /// Check if it is equal to \a s
839 bool equal(const FloatSetVal* s) {
840 if (size() != s->size()) return false;
841 for (int i = 0; i < size(); i++)
842 if (min(i) != s->min(i) || max(i) != s->max(i)) return false;
843 return true;
844 }
845
846 /// Mark for garbage collection
847 void mark(void) { _gc_mark = 1; }
848};
849
850/// Iterator over an IntSetVal
851class FloatSetRanges {
852 /// The set value
853 const FloatSetVal* rs;
854 /// The current range
855 int n;
856
857public:
858 /// Constructor
859 FloatSetRanges(const FloatSetVal* r) : rs(r), n(0) {}
860 /// Check if iterator is still valid
861 bool operator()(void) const { return n < rs->size(); }
862 /// Move to next range
863 void operator++(void) { ++n; }
864 /// Return minimum of current range
865 FloatVal min(void) const { return rs->min(n); }
866 /// Return maximum of current range
867 FloatVal max(void) const { return rs->max(n); }
868 /// Return width of current range
869 FloatVal width(void) const { return rs->width(n); }
870};
871
872template <class Char, class Traits>
873std::basic_ostream<Char, Traits>& operator<<(std::basic_ostream<Char, Traits>& os,
874 const FloatSetVal& s) {
875 for (FloatSetRanges isr(&s); isr(); ++isr) os << isr.min() << ".." << isr.max() << " ";
876 return os;
877}
878} // namespace MiniZinc
879
880#endif