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