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/values.hh>
15
16 #include <cmath>
17
18 #ifdef _MSC_VER
19 #define _CRT_SECURE_NO_WARNINGS
20 #endif
21
22 namespace MiniZinc {
23 namespace Ranges {
24
25 /**
26 * \brief Base for range iterators with explicit min and max
27 *
28 * The iterator provides members \a mi and \a ma for storing the
29 * limits of the currently iterated range. The iterator
30 * continues until \a mi becomes greater than \a ma. The member function
31 * finish does exactly that.
32 *
33 * \ingroup FuncIterRanges
34 */
35
36 template <class Val>
37 class MinMax {
38 protected:
39 /// Minimum of current range
40 Val _mi;
41 /// Maximum of current range
42 Val _ma;
43 /// %Set range such that iteration stops
44 void finish();
45
46 public:
47 /// \name Constructors and initialization
48 //@{
49 /// Default constructor
50 MinMax();
51 /// Initialize with range \a min to \a max
52 MinMax(Val min, Val max);
53 //@}
54
55 /// \name Iteration control
56 //@{
57 /// Test whether iterator is still at a range or done
58 bool operator()() const;
59 //@}
60
61 /// \name Range access
62 //@{
63 /// Return smallest value of range
64 Val min() const;
65 /// Return largest value of range
66 Val max() const;
67 /// Return width of range (distance between minimum and maximum)
68 Val width() const;
69 //@}
70 };
71
72 template <class Val>
finish()73 inline void MinMax<Val>::finish() {
74 _mi = 1;
75 _ma = 0;
76 }
77
78 template <class Val>
MinMax()79 inline MinMax<Val>::MinMax() {}
80
81 template <class Val>
MinMax(Val min,Val max)82 inline MinMax<Val>::MinMax(Val min, Val max) : _mi(min), _ma(max) {}
83
84 template <class Val>
operator ()() const85 inline bool MinMax<Val>::operator()() const {
86 return _mi <= _ma;
87 }
88
89 template <class Val>
min() const90 inline Val MinMax<Val>::min() const {
91 return _mi;
92 }
93 template <class Val>
max() const94 inline Val MinMax<Val>::max() const {
95 return _ma;
96 }
97 template <class Val>
width() const98 inline Val MinMax<Val>::width() const {
99 if (_mi > _ma) {
100 return 0;
101 }
102 if (_mi.isFinite() && _ma.isFinite()) {
103 return _ma - _mi + 1;
104 }
105 return Val::infinity();
106 }
107
108 template <class Val, class I>
109 class Bounded {
110 protected:
111 I _i;
112 Val _min;
113 bool _useMin;
114 Val _max;
115 bool _useMax;
116 Bounded(I& i, Val min0, bool umin0, Val max0, bool umax0);
117
118 public:
119 static Bounded miniter(I& i, Val min);
120 static Bounded maxiter(I& i, Val max);
121 static Bounded minmaxiter(I& i, Val min, Val max);
122
123 /// \name Iteration control
124 //@{
125 /// Test whether iterator is still at a range or done
126 bool operator()() const;
127 /// Move iterator to next range (if possible)
128 void operator++();
129 //@}
130
131 /// \name Range access
132 //@{
133 /// Return smallest value of range
134 Val min() const;
135 /// Return largest value of range
136 Val max() const;
137 /// Return width of range (distance between minimum and maximum)
138 Val width() const;
139 //@}
140 };
141
142 template <class Val, class I>
Bounded(I & i,Val min0,bool umin0,Val max0,bool umax0)143 inline Bounded<Val, I>::Bounded(I& i, Val min0, bool umin0, Val max0, bool umax0)
144 : _i(i), _min(min0), _useMin(umin0), _max(max0), _useMax(umax0) {
145 while (_i() && _useMin && _i.max() < _min) {
146 ++_i;
147 }
148 }
149 template <class Val, class I>
miniter(I & i,Val min)150 inline Bounded<Val, I> Bounded<Val, I>::miniter(I& i, Val min) {
151 return Bounded(i, min, true, 0, false);
152 }
153 template <class Val, class I>
maxiter(I & i,Val max)154 inline Bounded<Val, I> Bounded<Val, I>::maxiter(I& i, Val max) {
155 return Bounded(i, 0, false, max, true);
156 }
157 template <class Val, class I>
minmaxiter(I & i,Val min,Val max)158 inline Bounded<Val, I> Bounded<Val, I>::minmaxiter(I& i, Val min, Val max) {
159 return Bounded(i, min, true, max, true);
160 }
161
162 template <class Val, class I>
operator ()() const163 inline bool Bounded<Val, I>::operator()() const {
164 return _i() && (!_useMax || _i.min() <= _max);
165 }
166 template <class Val, class I>
operator ++()167 inline void Bounded<Val, I>::operator++() {
168 ++_i;
169 while (_i() && _useMin && _i.max() < _min) {
170 ++_i;
171 }
172 }
173 template <class Val, class I>
min() const174 inline Val Bounded<Val, I>::min() const {
175 return _useMin ? std::max(_min, _i.min()) : _i.min();
176 }
177 template <class Val, class I>
max() const178 inline Val Bounded<Val, I>::max() const {
179 return _useMax ? std::min(_max, _i.max()) : _i.max();
180 }
181 template <class Val, class I>
width() const182 inline Val Bounded<Val, I>::width() const {
183 if (min() > max()) {
184 return 0;
185 }
186 if (min().isFinite() && max().isFinite()) {
187 return max() - min() + 1;
188 }
189 return Val::infinity();
190 }
191
192 template <class Val>
193 class Const {
194 protected:
195 Val _min;
196 Val _max;
197 bool _done;
198
199 public:
200 Const(Val min0, Val max0);
201
202 /// \name Iteration control
203 //@{
204 /// Test whether iterator is still at a range or done
205 bool operator()() const;
206 /// Move iterator to next range (if possible)
207 void operator++();
208 //@}
209
210 /// \name Range access
211 //@{
212 /// Return smallest value of range
213 Val min() const;
214 /// Return largest value of range
215 Val max() const;
216 /// Return width of range (distance between minimum and maximum)
217 Val width() const;
218 //@}
219 };
220
221 template <class Val>
Const(Val min0,Val max0)222 inline Const<Val>::Const(Val min0, Val max0) : _min(min0), _max(max0), _done(min0 > max0) {}
223 template <class Val>
operator ()() const224 inline bool Const<Val>::operator()() const {
225 return !_done;
226 }
227 template <class Val>
operator ++()228 inline void Const<Val>::operator++() {
229 _done = true;
230 }
231 template <class Val>
min() const232 inline Val Const<Val>::min() const {
233 return _min;
234 }
235 template <class Val>
max() const236 inline Val Const<Val>::max() const {
237 return _max;
238 }
239 template <class Val>
width() const240 inline Val Const<Val>::width() const {
241 if (min() > max()) {
242 return 0;
243 }
244 if (min().isFinite() && max().isFinite()) {
245 return max() - min() + 1;
246 }
247 return Val::infinity();
248 }
249
250 /**
251 * \brief Range iterator for computing union (binary)
252 *
253 * \ingroup FuncIterRanges
254 */
255 template <class Val, class I, class J>
256 class Union : public MinMax<Val> {
257 protected:
258 /// First iterator
259 I _i;
260 /// Second iterator
261 J _j;
262
263 public:
264 /// \name Constructors and initialization
265 //@{
266 /// Default constructor
267 Union();
268 /// Initialize with iterator \a i and \a j
269 Union(I& i, J& j);
270 /// Initialize with iterator \a i and \a j
271 void init(I& i, J& j);
272 //@}
273
274 /// \name Iteration control
275 //@{
276 /// Move iterator to next range (if possible)
277 void operator++();
278 //@}
279 };
280
281 /// Return whether an interval ending with \a x overlaps with an interval starting at \a y
overlaps(const IntVal & x,const IntVal & y)282 inline bool overlaps(const IntVal& x, const IntVal& y) { return x.plus(1) >= y; }
283 /// Return whether an interval ending with \a x overlaps with an interval starting at \a y
overlaps(const FloatVal & x,const FloatVal & y)284 inline bool overlaps(const FloatVal& x, const FloatVal& y) {
285 if (x.isPlusInfinity()) {
286 return true;
287 }
288 if (y.isMinusInfinity()) {
289 return true;
290 }
291 if (x.isFinite() && y.isFinite()) {
292 return std::nextafter(x.toDouble(), INFINITY) >= y.toDouble();
293 }
294 return x >= y;
295 }
next_higher(const IntVal & x)296 inline IntVal next_higher(const IntVal& x) { return x.plus(1); }
next_lower(const IntVal & x)297 inline IntVal next_lower(const IntVal& x) { return x.minus(1); }
next_higher(const FloatVal & x)298 inline FloatVal next_higher(const FloatVal& x) {
299 if (x.isFinite()) {
300 return std::nextafter(x.toDouble(), INFINITY);
301 }
302 return x;
303 }
next_lower(const FloatVal & x)304 inline FloatVal next_lower(const FloatVal& x) {
305 if (x.isFinite()) {
306 return std::nextafter(x.toDouble(), -INFINITY);
307 }
308 return x;
309 }
310
311 /*
312 * Binary union
313 *
314 */
315
316 template <class Val, class I, class J>
operator ++()317 inline void Union<Val, I, J>::operator++() {
318 if (!_i() && !_j()) {
319 MinMax<Val>::finish();
320 return;
321 }
322
323 if (!_i() || (_j() && (!overlaps(_j.max(), _i.min())))) {
324 MinMax<Val>::_mi = _j.min();
325 MinMax<Val>::_ma = _j.max();
326 ++_j;
327 return;
328 }
329 if (!_j() || (_i() && (!overlaps(_i.max(), _j.min())))) {
330 MinMax<Val>::_mi = _i.min();
331 MinMax<Val>::_ma = _i.max();
332 ++_i;
333 return;
334 }
335
336 MinMax<Val>::_mi = std::min(_i.min(), _j.min());
337 MinMax<Val>::_ma = std::max(_i.max(), _j.max());
338
339 ++_i;
340 ++_j;
341
342 next:
343 if (_i() && (overlaps(MinMax<Val>::_ma, _i.min()))) {
344 MinMax<Val>::_ma = std::max(MinMax<Val>::_ma, _i.max());
345 ++_i;
346 goto next;
347 }
348 if (_j() && (overlaps(MinMax<Val>::_ma, _j.min()))) {
349 MinMax<Val>::_ma = std::max(MinMax<Val>::_ma, _j.max());
350 ++_j;
351 goto next;
352 }
353 }
354
355 template <class Val, class I, class J>
Union()356 inline Union<Val, I, J>::Union() {}
357
358 template <class Val, class I, class J>
Union(I & i,J & j)359 inline Union<Val, I, J>::Union(I& i, J& j) : _i(i), _j(j) {
360 operator++();
361 }
362
363 template <class Val, class I, class J>
init(I & i,J & j)364 inline void Union<Val, I, J>::init(I& i, J& j) {
365 _i = i;
366 _j = j;
367 operator++();
368 }
369
370 /**
371 * \brief Range iterator for computing intersection (binary)
372 *
373 * \ingroup FuncIterRanges
374 */
375 template <class Val, class I, class J>
376 class Inter : public MinMax<Val> {
377 protected:
378 /// First iterator
379 I _i;
380 /// Second iterator
381 J _j;
382
383 public:
384 /// \name Constructors and initialization
385 //@{
386 /// Default constructor
387 Inter();
388 /// Initialize with iterator \a i and \a j
389 Inter(I& i, J& j);
390 /// Initialize with iterator \a i and \a j
391 void init(I& i, J& j);
392 //@}
393
394 /// \name Iteration control
395 //@{
396 /// Move iterator to next range (if possible)
397 void operator++();
398 //@}
399 };
400
401 /*
402 * Binary intersection
403 *
404 */
405
406 template <class Val, class I, class J>
operator ++()407 inline void Inter<Val, I, J>::operator++() {
408 if (!_i() || !_j()) {
409 goto done;
410 }
411 do {
412 while (_i() && (_i.max() < _j.min())) {
413 ++_i;
414 }
415 if (!_i()) {
416 goto done;
417 }
418 while (_j() && (_j.max() < _i.min())) {
419 ++_j;
420 }
421 if (!_j()) {
422 goto done;
423 }
424 } while (_i.max() < _j.min());
425 // Now the intervals overlap: consume the smaller interval
426 MinMax<Val>::_ma = std::min(_i.max(), _j.max());
427 MinMax<Val>::_mi = std::max(_i.min(), _j.min());
428 if (_i.max() < _j.max()) {
429 ++_i;
430 } else {
431 ++_j;
432 }
433 return;
434 done:
435 MinMax<Val>::finish();
436 }
437
438 template <class Val, class I, class J>
Inter()439 inline Inter<Val, I, J>::Inter() {}
440
441 template <class Val, class I, class J>
Inter(I & i,J & j)442 inline Inter<Val, I, J>::Inter(I& i, J& j) : _i(i), _j(j) {
443 operator++();
444 }
445
446 template <class Val, class I, class J>
init(I & i,J & j)447 inline void Inter<Val, I, J>::init(I& i, J& j) {
448 _i = i;
449 _j = j;
450 operator++();
451 }
452
453 /**
454 * \brief Range iterator for computing set difference
455 *
456 * \ingroup FuncIterRanges
457 */
458
459 template <class Val, class I, class J>
460 class Diff : public MinMax<Val> {
461 protected:
462 /// Iterator from which to subtract
463 I _i;
464 /// Iterator to be subtracted
465 J _j;
466
467 public:
468 /// \name Constructors and initialization
469 //@{
470 /// Default constructor
471 Diff();
472 /// Initialize with iterator \a i and \a j
473 Diff(I& i, J& j);
474 /// Initialize with iterator \a i and \a j
475 void init(I& i, J& j);
476 //@}
477
478 /// \name Iteration control
479 //@{
480 /// Move iterator to next range (if possible)
481 void operator++();
482 //@}
483 };
484
485 template <class Val, class I, class J>
operator ++()486 inline void Diff<Val, I, J>::operator++() {
487 // Precondition: mi <= ma
488 // Task: find next mi greater than ma
489 while (true) {
490 if (!_i()) {
491 break;
492 }
493 bool isInfinite = (!MinMax<Val>::_ma.isFinite() && MinMax<Val>::_ma > 0);
494 MinMax<Val>::_mi = next_higher(MinMax<Val>::_ma);
495 MinMax<Val>::_ma = _i.max();
496 if (isInfinite || MinMax<Val>::_mi > _i.max()) {
497 ++_i;
498 if (!_i()) {
499 break;
500 }
501 MinMax<Val>::_mi = _i.min();
502 MinMax<Val>::_ma = _i.max();
503 }
504 while (_j() && (_j.max() < MinMax<Val>::_mi)) {
505 ++_j;
506 }
507 if (_j() && (_j.min() <= MinMax<Val>::_ma)) {
508 // Now the interval [mi ... ma] must be shrunken
509 // Is [mi ... ma] completely consumed?
510 if ((MinMax<Val>::_mi >= _j.min()) && (MinMax<Val>::_ma <= _j.max())) {
511 continue;
512 }
513 // Does [mi ... ma] overlap on the left?
514 if (_j.min() <= MinMax<Val>::_mi) {
515 MinMax<Val>::_mi = next_higher(_j.max());
516 // Search for max!
517 ++_j;
518 if (_j() && (_j.min() <= MinMax<Val>::_ma)) {
519 MinMax<Val>::_ma = next_lower(_j.min());
520 }
521 } else {
522 MinMax<Val>::_ma = next_lower(_j.min());
523 }
524 }
525 return;
526 }
527 MinMax<Val>::finish();
528 }
529
530 template <class Val, class I, class J>
Diff()531 inline Diff<Val, I, J>::Diff() {}
532
533 template <class Val, class I, class J>
Diff(I & i,J & j)534 inline Diff<Val, I, J>::Diff(I& i, J& j) : _i(i), _j(j) {
535 if (!_i()) {
536 MinMax<Val>::finish();
537 } else {
538 MinMax<Val>::_mi = next_lower(_i.min());
539 MinMax<Val>::_ma = MinMax<Val>::_mi;
540 operator++();
541 }
542 }
543
544 template <class Val, class I, class J>
init(I & i,J & j)545 inline void Diff<Val, I, J>::init(I& i, J& j) {
546 _i = i;
547 _j = j;
548 if (!_i()) {
549 MinMax<Val>::finish();
550 } else {
551 MinMax<Val>::_mi = next_lower(_i.min());
552 MinMax<Val>::_ma = MinMax<Val>::_mi;
553 operator++();
554 }
555 }
556
557 /**
558 * \brief Value iterator from range iterator
559 *
560 * \ingroup FuncIterValues
561 */
562 template <class I>
563 class ToValues {
564 protected:
565 /// Range iterator used
566 I _i;
567 /// Current value
568 IntVal _cur;
569 /// End of current range
570 IntVal _max;
571 /// Initialize iterator
572 void start();
573
574 public:
575 /// \name Constructors and initialization
576 //@{
577 /// Default constructor
578 ToValues();
579 /// Initialize with values from range iterator \a i
580 ToValues(I& i);
581 /// Initialize with values from range iterator \a i
582 void init(I& i);
583 //@}
584
585 /// \name Iteration control
586 //@{
587 /// Test whether iterator is still at a value or done
588 bool operator()() const;
589 /// Move iterator to next value (if possible)
590 void operator++();
591 //@}
592
593 /// \name Value access
594 //@{
595 /// Return current value
596 IntVal val() const;
597 //@}
598 };
599
600 template <class I>
ToValues()601 inline ToValues<I>::ToValues() {}
602
603 template <class I>
start()604 inline void ToValues<I>::start() {
605 if (_i()) {
606 _cur = _i.min();
607 _max = _i.max();
608 } else {
609 _cur = 1;
610 _max = 0;
611 }
612 }
613
614 template <class I>
ToValues(I & i)615 inline ToValues<I>::ToValues(I& i) : _i(i) {
616 start();
617 }
618
619 template <class I>
init(I & i)620 inline void ToValues<I>::init(I& i) {
621 _i = i;
622 start();
623 }
624
625 template <class I>
operator ()() const626 inline bool ToValues<I>::operator()() const {
627 return (_cur <= _max);
628 }
629
630 template <class I>
operator ++()631 inline void ToValues<I>::operator++() {
632 ++_cur;
633 if (_cur > _max) {
634 ++_i;
635 if (_i()) {
636 _cur = _i.min();
637 _max = _i.max();
638 }
639 }
640 }
641
642 template <class I>
val() const643 inline IntVal ToValues<I>::val() const {
644 return _cur;
645 }
646
647 /**
648 * \defgroup FuncIterRangesOp Operations on range iterators
649 *
650 * \ingroup FuncIterRanges
651 */
652
653 //@{
654 /// Cardinality of the set represented by range iterator \a i
655 template <class I>
656 IntVal cardinality(I& i);
657
658 /// Check whether range iterators \a i and \a j are equal
659 template <class I, class J>
660 bool equal(I& i, J& j);
661
662 /// Check whether range iterator \a i is subset of range iterator \a j
663 template <class I, class J>
664 bool subset(I& i, J& j);
665
666 /// Check whether range iterators \a i and \a j are disjoint
667 template <class I, class J>
668 bool disjoint(I& i, J& j);
669
670 /// Comapre two iterators with each other
671 enum CompareStatus {
672 CS_SUBSET, ///< First is subset of second iterator
673 CS_DISJOINT, ///< Intersection is empty
674 CS_NONE ///< Neither of the above
675 };
676
677 /// Check whether range iterator \a i is a subset of \a j, or whether they are disjoint
678 template <class I, class J>
679 CompareStatus compare(I& i, J& j);
680 //@}
681
682 template <class I>
cardinality(I & i)683 inline IntVal cardinality(I& i) {
684 IntVal s = 0;
685 while (i()) {
686 if (i.width().isFinite()) {
687 s += i.width();
688 ++i;
689 } else {
690 return IntVal::infinity();
691 }
692 }
693 return s;
694 }
695
696 template <class I, class J>
equal(I & i,J & j)697 inline bool equal(I& i, J& j) {
698 // Are i and j equal?
699 while (i() && j()) {
700 if ((i.min() == j.min()) && (i.max() == j.max())) {
701 ++i;
702 ++j;
703 } else {
704 return false;
705 }
706 }
707 return !i() && !j();
708 }
709
710 template <class I, class J>
subset(I & i,J & j)711 inline bool subset(I& i, J& j) {
712 // Is i subset of j?
713 while (i() && j()) {
714 if (j.max() < i.min()) {
715 ++j;
716 } else if ((i.min() >= j.min()) && (i.max() <= j.max())) {
717 ++i;
718 } else {
719 return false;
720 }
721 }
722 return !i();
723 }
724
725 template <class I, class J>
disjoint(I & i,J & j)726 inline bool disjoint(I& i, J& j) {
727 // Are i and j disjoint?
728 while (i() && j()) {
729 if (j.max() < i.min()) {
730 ++j;
731 } else if (i.max() < j.min()) {
732 ++i;
733 } else {
734 return false;
735 }
736 }
737 return true;
738 }
739
740 template <class I, class J>
compare(I & i,J & j)741 inline CompareStatus compare(I& i, J& j) {
742 bool subset = true;
743 bool disjoint = true;
744 while (i() && j()) {
745 if (j.max() < i.min()) {
746 ++j;
747 } else if (i.max() < j.min()) {
748 ++i;
749 subset = false;
750 } else if ((i.min() >= j.min()) && (i.max() <= j.max())) {
751 ++i;
752 disjoint = false;
753 } else if (i.max() <= j.max()) {
754 ++i;
755 disjoint = false;
756 subset = false;
757 } else if (j.max() <= i.max()) {
758 ++j;
759 disjoint = false;
760 subset = false;
761 }
762 }
763 if (i()) {
764 subset = false;
765 }
766 if (subset) {
767 return CS_SUBSET;
768 }
769 return disjoint ? CS_DISJOINT : CS_NONE;
770 }
771
772 template <class I, class J>
less(I & i,J & j)773 inline bool less(I& i, J& j) {
774 while (i()) {
775 if (!j()) {
776 return false;
777 }
778 if (i.min() < j.min()) {
779 return true;
780 }
781 if (i.min() > j.min()) {
782 return false;
783 }
784 if (i.max() < j.max()) {
785 return true;
786 }
787 if (i.max() > j.max()) {
788 ++j;
789 return j();
790 }
791 ++i;
792 ++j;
793 }
794 return static_cast<bool>(j());
795 }
796
797 template <class I, class J>
less_eq(I & i,J & j)798 inline bool less_eq(I& i, J& j) {
799 while (i()) {
800 if (!j()) {
801 return false;
802 }
803 if (i.min() < j.min()) {
804 return true;
805 }
806 if (i.min() > j.min()) {
807 return false;
808 }
809 if (i.max() < j.max()) {
810 return true;
811 }
812 if (i.max() > j.max()) {
813 ++j;
814 return j();
815 }
816 ++i;
817 ++j;
818 }
819 return true;
820 }
821
822 } // namespace Ranges
823 } // namespace MiniZinc
824