Generated on for Gecode by doxygen 1.17.0
open-var-list.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main author:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2026
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include "test/int.hh"
36
38#include <gecode/search.hh>
39
40#ifdef GECODE_HAS_SET_VARS
41#include <gecode/set.hh>
42#endif
43#ifdef GECODE_HAS_FLOAT_VARS
44#include <gecode/float.hh>
45#endif
46
47#include <memory>
48#include <set>
49
50namespace Test { namespace Int {
51
52 namespace OpenList {
53
56 public:
58
60 : list(*this,
61 [](int i) {
62 return Gecode::IntSet(i,i);
63 },6) {}
64
66 : Gecode::Space(s) {
67 list.update(*this,s.list);
68 }
69
70 virtual Gecode::Space*
71 copy(void) {
72 return new OpenListSpace(*this);
73 }
74 };
75
78 public:
80 : ::Test::Base("Int::OpenList::Materialize",TestTags::check()) {}
81
82 virtual bool
83 run(void) {
84 using namespace Gecode;
85 OpenListSpace source;
86 rel(source,source.list.length(),IRT_GQ,3);
87 if ((source.status() == SS_FAILED) ||
88 (source.list.known_length() != 3))
89 return false;
90 for (int i=0; i<3; i++)
91 if (!source.list[i].assigned() ||
92 (source.list[i].val() != i))
93 return false;
94
95 OpenListSpace* clone =
96 static_cast<OpenListSpace*>(source.clone());
97 rel(*clone,clone->list.length(),IRT_GQ,5);
98 const bool clone_ok =
99 (clone->status() != SS_FAILED) &&
100 (clone->list.known_length() == 5) &&
101 clone->list[4].assigned() &&
102 (clone->list[4].val() == 4);
103 delete clone;
104 if (!clone_ok || (source.list.known_length() != 3))
105 return false;
106
107 OpenListSpace direct;
108 IntVar x = direct.list.get(direct,3);
109 return (direct.list.known_length() == 4) &&
110 (direct.list.length().min() == 4) &&
111 x.assigned() && (x.val() == 3) &&
112 (direct.status() != SS_FAILED);
113 }
114 };
115
117
119 public:
121
123
125 : list(*this,Gecode::IntSet(0,1),3) {
126 using namespace Gecode;
127 DFA accepts_one(0,{
128 {0,0,0}, {0,1,1},
129 {1,0,1}, {1,1,1}
130 },{1});
131 extensional(*this,list,accepts_one);
133 branch(*this,list.length(),INT_VAL_MIN());
134 else if (order == Order::LENGTH_MAX)
135 branch(*this,list.length(),INT_VAL_MAX());
136 branch(*this,list);
137 }
138
140 : Gecode::Space(s) {
141 list.update(*this,s.list);
142 }
143
144 virtual Gecode::Space*
145 copy(void) {
146 return new BranchOrderSpace(*this);
147 }
148 };
149
150 class BranchOrder : public ::Test::Base {
151 protected:
152 static bool
154 using namespace Gecode;
155 Search::Options options;
156 options.threads = 1;
157 options.c_d = 1000;
158 options.a_d = 1000;
160 DFS<BranchOrderSpace> engine(root,options);
161 delete root;
162
163 int solutions = 0;
164 int first = -1;
165 while (BranchOrderSpace* solution = engine.next()) {
166 if (solutions == 0)
167 first = solution->list.known_length();
168 solutions++;
169 delete solution;
170 }
171 return (first == first_length) && (solutions == 11);
172 }
173
174 public:
176 : ::Test::Base("Int::OpenList::BranchOrder") {}
177
178 virtual bool
185 };
186
188 public:
190
191 SelectorSpace(Gecode::IntValBranch vals, bool length_first=false)
192 : list(*this,[](int i) { return Gecode::IntSet(i,i+1); },3) {
193 using namespace Gecode;
194 if (length_first)
195 branch(*this,list.length(),INT_VAL_MIN());
197 }
198
200 list.update(*this,s.list);
201 }
202
203 virtual Gecode::Space*
204 copy(void) {
205 return new SelectorSpace(*this);
206 }
207 };
208
209 class Selectors : public ::Test::Base {
210 public:
211 Selectors(void) : ::Test::Base("Int::OpenList::Selectors") {}
212
213 virtual bool
214 run(void) {
215 using namespace Gecode;
216 const IntValBranch values[] = {
221 INT_VAL([](const Space&, IntVar x, int) { return x.max(); })
222 };
223 for (const IntValBranch& vals : values)
224 for (bool length_first : {false,true}) {
225 SelectorSpace root(vals,length_first);
226 Search::Options options;
227 options.threads = 1;
228 options.c_d = 1000;
229 options.a_d = 1000;
230 DFS<SelectorSpace> engine(&root,options);
231 int solutions = 0;
232 while (SelectorSpace* solution = engine.next()) {
233 bool valid = solution->list.length().assigned() &&
234 (solution->list.length().val() == solution->list.known_length());
235 for (int i=0; i<solution->list.known_length(); i++)
236 valid &= solution->list[i].assigned() &&
237 (solution->list[i].val() >= i) &&
238 (solution->list[i].val() <= i+1);
239 delete solution;
240 if (!valid)
241 return false;
242 solutions++;
243 }
244 if (solutions != 15)
245 return false;
246 }
247 return true;
248 }
249 };
250
251 class NoGoods : public ::Test::Base {
252 public:
253 NoGoods(void) : ::Test::Base("Int::OpenList::NoGoods") {}
254
255 virtual bool
256 run(void) {
257 using namespace Gecode;
259 root.list.materialize(root,1);
260 Search::NodeStop stop(6);
261 Search::Options options;
262 options.stop = &stop;
263 options.threads = 1;
264 options.nogoods_limit = 100;
265 std::unique_ptr<Search::Engine> engine
266 (Search::dfsengine(&root,options));
267 bool found[16] = {};
268 const auto record = [&found](SelectorSpace* solution) {
269 int code = 1;
270 for (int i=0; i<solution->list.known_length(); i++)
271 code = 2*code + solution->list[i].val()-i;
272 found[code] = true;
273 delete solution;
274 };
275 while (Space* solution = engine->next())
276 record(static_cast<SelectorSpace*>(solution));
277 if (!engine->stopped())
278 return false;
279 // Deeper choices refer to positions absent from the restart root.
280 engine->nogoods().post(root);
281 DFS<SelectorSpace> restarted(&root);
282 while (SelectorSpace* solution = restarted.next())
283 record(solution);
284 // Extracted nogoods must allow every unvisited word.
285 for (int code=2; code<16; code++)
286 if (!found[code])
287 return false;
288 return true;
289 }
290 };
291
293 public:
295
297 : list(*this,Gecode::IntSet({0,2,5}),3) {
298 using namespace Gecode;
299 list.materialize(*this,3);
300 branch(*this,list,
302 INT_VAR_MERIT_MAX([](const Space&, IntVar, int i) {
303 return i;
304 })),vals,
305 [](const Space&, IntVar, int i) { return i != 1; },
306 [](const Space&, const Brancher&, unsigned int, IntVar,
307 int i, const int& value, std::ostream& out) {
308 out << i << ":" << value;
309 });
310 }
311
313 list.update(*this,s.list);
314 }
315
316 virtual Gecode::Space*
317 copy(void) {
318 return new SelectorChoiceSpace(*this);
319 }
320 };
321
323 public:
324 SelectorChoice(void) : ::Test::Base("Int::OpenList::SelectorChoice") {}
325
326 virtual bool
327 run(void) {
328 using namespace Gecode;
329 for (int multi=0; multi<2; multi++) {
330 SelectorChoiceSpace source(multi ? INT_VALUES_MAX() : INT_VAL_MAX());
331 if (source.status() != SS_BRANCH)
332 return false;
333 const Choice* original = source.choice();
334 Archive archive;
335 original->archive(archive);
336 const Choice* restored = source.choice(archive);
337 bool valid = restored->alternatives() == (multi ? 3U : 2U);
338 for (unsigned int a=0; a<restored->alternatives(); a++) {
339 SelectorChoiceSpace* clone =
340 static_cast<SelectorChoiceSpace*>(source.clone());
341 clone->commit(*restored,a);
342 const int expected[] = {5,2,0};
343 valid &= !clone->failed() && !clone->list[0].assigned() &&
344 !clone->list[1].assigned();
345 if (multi || (a == 0))
346 valid &= clone->list[2].assigned() &&
347 (clone->list[2].val() == expected[a]);
348 else
349 valid &= !clone->list[2].in(5);
350 delete clone;
351 }
352 SelectorChoiceSpace* excluded =
353 static_cast<SelectorChoiceSpace*>(source.clone());
354 NGL* literal = excluded->ngl(*restored,0);
355 valid &= (literal != nullptr) && (literal->status(*excluded) == NGL::NONE);
356 if (literal)
357 valid &= (literal->prune(*excluded) != ES_FAILED) &&
358 !excluded->list[2].in(5);
359 delete excluded;
360 std::ostringstream printed;
361 source.print(*restored,0,printed);
362 valid &= printed.str() == "2:5";
363 delete restored;
364 delete original;
365 if (!valid)
366 return false;
367 }
368 return true;
369 }
370 };
371
372 class BoolSpace : public Gecode::Space {
373 public:
375
376 BoolSpace(bool length_first)
377 : list(*this,3) {
378 using namespace Gecode;
379 DFA accepts_one(0,{{0,0,0},{0,1,1},{1,0,1},{1,1,1}},{1});
380 extensional(*this,list,accepts_one);
381 if (length_first)
382 branch(*this,list.length(),INT_VAL_MIN());
383 branch(*this,list,
384 BOOL_VAR_MERIT_MAX([](const Space&, BoolVar, int i) { return i; }),
385 BOOL_VAL_MAX());
386 }
387
389 list.update(*this,s.list);
390 }
391
392 virtual Gecode::Space*
393 copy(void) {
394 return new BoolSpace(*this);
395 }
396 };
397
398 class BoolList : public ::Test::Base {
399 public:
400 BoolList(void) : ::Test::Base("Int::OpenList::Bool",TestTags::check()) {}
401
402 virtual bool
403 run(void) {
404 using namespace Gecode;
405 for (bool length_first : {false,true})
406 for (int recompute=0; recompute<2; recompute++) {
407 BoolSpace root(length_first);
408 Search::Options options;
409 options.threads = 1;
410 options.c_d = recompute ? 1000 : 1;
411 options.a_d = options.c_d;
412 DFS<BoolSpace> engine(&root,options);
413 int solutions = 0;
414 while (BoolSpace* solution = engine.next()) {
415 bool valid = solution->list.length().assigned() &&
416 (solution->list.length().val() == solution->list.known_length());
417 int ones = 0;
418 for (int i=0; i<solution->list.known_length(); i++) {
419 valid &= solution->list[i].assigned();
420 ones += solution->list[i].val();
421 }
422 delete solution;
423 if (!valid || (ones == 0))
424 return false;
425 solutions++;
426 }
427 if (solutions != 11)
428 return false;
429 }
430 return true;
431 }
432 };
433
434 template<class Var>
435 class AliasSpace : public Gecode::Space {
436 public:
438
440 : list(*this,[](Gecode::Space& home, int) {
441 return Var(home,0,1);
442 },16) {}
443
445 list.update(*this,s.list);
446 }
447
448 virtual Gecode::Space*
449 copy(void) {
450 return new AliasSpace(*this);
451 }
452
453 bool
454 rejects(int i) {
455 const int n = list.known_length();
456 try {
457 list.append(*this,list[i]);
458 } catch (const Gecode::Int::ArgumentSame&) {
459 return list.known_length() == n;
460 }
461 return false;
462 }
463 };
464
465 class Aliases : public ::Test::Base {
466 protected:
467 template<class Var>
468 static bool
469 check(void) {
470 using namespace Gecode;
471 AliasSpace<Var> source;
472 Var assigned(source,0,0);
473 source.list.append(source,assigned);
474 source.list.append(source,assigned);
475 Var first(source,0,1);
476 source.list.append(source,first);
477 source.list.append(source,Var(source,0,1));
478 if (!source.rejects(2))
479 return false;
480 rel(source,first,IRT_EQ,0);
481 source.list.append(source,first);
482 if ((source.list.known_length() != 5) ||
483 (source.status() == SS_FAILED))
484 return false;
485 std::unique_ptr<AliasSpace<Var>> clone
486 (static_cast<AliasSpace<Var>*>(source.clone()));
487 if (!clone->rejects(3))
488 return false;
489 clone->list.append(*clone,Var(*clone,0,1));
490 rel(*clone,clone->list[3],IRT_EQ,0);
491 clone->list.append(*clone,clone->list[3]);
492 return (clone->list.known_length() == 7) &&
493 (clone->status() != SS_FAILED) &&
494 (source.list.known_length() == 5) &&
495 !source.list[3].assigned() && source.rejects(3);
496 }
497
498 public:
499 Aliases(void) : ::Test::Base("Int::OpenList::Aliases",TestTags::check()) {}
500
501 virtual bool
502 run(void) {
504 }
505 };
506
508
510 public:
511#ifdef GECODE_HAS_SET_VARS
513#endif
514#ifdef GECODE_HAS_FLOAT_VARS
516#endif
517
519 using namespace Gecode;
520#ifdef GECODE_HAS_SET_VARS
522 [](Space& home, int i) {
523 return SetVar(home,IntSet(i,i),IntSet(i,i));
524 },3);
525 sets.materialize(*this,1);
526#endif
527#ifdef GECODE_HAS_FLOAT_VARS
529 [](Space& home, int i) { return FloatVar(home,i,i); },3);
530 floats.materialize(*this,1);
531#endif
532 }
533
535#ifdef GECODE_HAS_SET_VARS
536 sets.update(*this,s.sets);
537#endif
539 floats.update(*this,s.floats);
540#endif
541 }
542
543 virtual Gecode::Space*
544 copy(void) {
545 return new FactorySpace(*this);
546 }
547 };
548
549 class Factory : public ::Test::Base {
550 public:
551 Factory(void) : ::Test::Base("Int::OpenList::Factory",TestTags::check()) {}
552
553 virtual bool
554 run(void) {
555 using namespace Gecode;
556 FactorySpace source;
557 if (source.status() == SS_FAILED)
558 return false;
559 FactorySpace* clone = static_cast<FactorySpace*>(source.clone());
560#ifdef GECODE_HAS_SET_VARS
561 clone->sets.materialize(*clone,3);
562 clone->sets.close(*clone);
563 source.sets.close(source);
564#endif
565#ifdef GECODE_HAS_FLOAT_VARS
566 clone->floats.materialize(*clone,3);
567 clone->floats.close(*clone);
568 source.floats.close(source);
569#endif
570 bool valid = (clone->status() != SS_FAILED) &&
571 (source.status() != SS_FAILED);
572#ifdef GECODE_HAS_SET_VARS
573 valid &= (source.sets.known_length() == 1) &&
574 (clone->sets.known_length() == 3) &&
575 (clone->sets.length().val() == 3) &&
576 clone->sets[2].assigned() && (clone->sets[2].glbMin() == 2);
577#endif
578#ifdef GECODE_HAS_FLOAT_VARS
579 valid &= (source.floats.known_length() == 1) &&
580 (clone->floats.known_length() == 3) &&
581 (clone->floats.length().val() == 3) &&
582 clone->floats[2].assigned() && (clone->floats[2].min() == 2);
583#endif
584 delete clone;
585 return valid;
586 }
587 };
588
590 public:
591 FixedStatistics(void) : ::Test::Base("Int::OpenList::FixedStatistics") {}
592
593 virtual bool
594 run(void) {
595 using namespace Gecode;
596 for (int chb=0; chb<2; chb++) {
598 bool rejected = false;
599 try {
600 branch(open,open.list,
601 chb ? INT_VAR_CHB_MIN() : INT_VAR_ACTION_MIN(1.0),
602 INT_VAL_MIN());
603 } catch (const Gecode::Int::UnknownBranching&) {
604 rejected = true;
605 }
606 if (!rejected)
607 return false;
609 branch(fixed,fixed.list,
610 chb ? INT_VAR_CHB_MIN() : INT_VAR_ACTION_MIN(1.0),
611 INT_VAL_MIN());
612 DFS<SelectorChoiceSpace> engine(&fixed);
613 int solutions = 0;
614 while (SelectorChoiceSpace* solution = engine.next()) {
615 solutions++;
616 delete solution;
617 }
618 if (solutions != 27)
619 return false;
620 }
621 return true;
622 }
623 };
624
631
633 public:
635
637 : list(*this,Gecode::IntSet(0,4),
638 [](Gecode::Space& home, Gecode::OpenIntVarList x, int i) {
639 using namespace Gecode;
640 if (i == 0) {
641 rel(home,x[i],IRT_EQ,0);
642 } else {
643 linear(home,IntArgs({-1,1}),
644 IntVarArgs({x[i-1],x[i]}),IRT_EQ,1);
645 }
646 },4) {
647 Gecode::branch(*this,list);
648 }
649
651 : Gecode::Space(s) {
652 list.update(*this,s.list);
653 }
654
655 virtual Gecode::Space*
656 copy(void) {
657 return new TransitionSpace(*this);
658 }
659 };
660
661 class Transition : public ::Test::Base {
662 public:
664 : ::Test::Base("Int::OpenList::Transition") {}
665
666 virtual bool
667 run(void) {
668 using namespace Gecode;
669 Search::Options options;
670 options.threads = 1;
671 options.c_d = 1000;
672 options.a_d = 1000;
674 DFS<TransitionSpace> engine(root,options);
675 delete root;
676
677 int solutions = 0;
678 while (TransitionSpace* solution = engine.next()) {
679 bool valid =
680 solution->list.length().assigned() &&
681 (solution->list.length().val() ==
682 solution->list.known_length());
683 for (int i=0; i<solution->list.known_length(); i++)
684 valid &= solution->list[i].assigned() &&
685 (solution->list[i].val() == i);
686 delete solution;
687 if (!valid)
688 return false;
689 solutions++;
690 }
691 return solutions == 5;
692 }
693 };
694
695
697 class Views : public ::Test::Base {
698 class ViewSpace : public Gecode::Space {
699 public:
703
704 ViewSpace(void)
705 : list(*this,Gecode::IntSet(0,10),5),
706 direct(list), negative(list) {}
707
708 ViewSpace(ViewSpace& s) : Gecode::Space(s) {
709 list.update(*this,s.list);
710 direct.update(*this,s.direct);
711 negative.update(*this,s.negative);
712 }
713
714 Gecode::Space* copy(void) override {
715 return new ViewSpace(*this);
716 }
717 };
718 public:
719 Views(void)
720 : ::Test::Base("Int::OpenList::Views",TestTags::check()) {}
721
722 bool run(void) override {
723 using namespace Gecode;
724 ViewSpace source;
725 Gecode::Int::IntView length = source.negative.length();
726 if (me_failed(length.gq(source,2)) ||
727 (source.status() == SS_FAILED) ||
728 (source.direct.known_length() != 2) ||
729 (source.negative.known_length() != 2))
730 return false;
731 if (me_failed(source.negative[0].gq(source,-7)) ||
732 me_failed(source.direct[0].gq(source,2)) ||
733 (source.status() == SS_FAILED) ||
734 (source.list[0].min() != 2) || (source.list[0].max() != 7) ||
735 (source.negative[0].min() != -7) ||
736 (source.negative[0].max() != -2))
737 return false;
738
739 std::unique_ptr<ViewSpace> clone
740 (static_cast<ViewSpace*>(source.clone()));
741 clone->negative.materialize(*clone,3);
742 if (me_failed(clone->negative[0].eq(*clone,-5)) ||
743 me_failed(clone->direct.length().eq(*clone,3)) ||
744 (clone->status() == SS_FAILED) ||
745 (clone->list.known_length() != 3) ||
746 (clone->direct.known_length() != 3) ||
747 (clone->direct[0].val() != 5) ||
748 (clone->negative[2].min() != -10))
749 return false;
750 source.direct.materialize(source,4);
751 return (source.status() != SS_FAILED) &&
752 (source.list.known_length() == 4) &&
753 (source.negative.known_length() == 4) &&
754 (source.negative[3].max() == 0) &&
755 (source.list[0].min() == 2) && (source.list[0].max() == 7) &&
756 (clone->negative.known_length() == 3) &&
757 (clone->list.length().val() == 3);
758 }
759 };
760
761
763 class Constraint : public OpenTest {
764 public:
769 protected:
771 int width;
773 public:
774 Constraint(const std::string& name, Kind k, int size, int width0=2,
776 : OpenTest("OpenList::"+name,size,0,Gecode::IntSet(0,2),level),
777 kind(k), width(width0), relation(Gecode::IRT_LE) {}
778
780 : OpenTest("OpenList::Rel::"+str(relation0)+"::"+str(level),
781 3,0,Gecode::IntSet({0,2,5}),level),
782 kind(Kind::REL), width(0), relation(relation0) {}
783
784 virtual bool
785 solution(const Assignment& x) const {
786 switch (kind) {
787 case Kind::DISTINCT:
788 for (int i=0; i<x.size(); i++)
789 for (int j=0; j<i; j++)
790 if (x[i] == x[j])
791 return false;
792 return true;
793 case Kind::REL:
794 for (int i=1; i<x.size(); i++)
795 if (!cmp(x[i-1],relation,x[i]))
796 return false;
797 return true;
798 case Kind::SLIDING:
799 for (int i=0; i+width<=x.size(); i++) {
800 int count = 0;
801 for (int j=i; j<i+width; j++)
802 count += x[j] == 1;
803 if (count != 1)
804 return false;
805 }
806 return true;
809 for (int i=0; i+width<=x.size(); i++) {
810 int sum = 0;
811 for (int j=i; j<i+width; j++)
812 sum += x[j];
813 if ((kind == Kind::SLIDING_SUM) ? sum != 2 :
814 (sum < 1) || (sum > 3))
815 return false;
816 }
817 return true;
818 case Kind::MIN_MAX: {
819 int lower = x[0];
820 int upper = x[0];
821 for (int i=1; i<x.size(); i++) {
822 lower = std::min(lower,x[i]);
823 upper = std::max(upper,x[i]);
824 }
825 return (lower == 0) && (upper == 2);
826 }
827 case Kind::PRECEDE: {
828 bool seen = false;
829 for (int i=0; i<x.size(); i++) {
830 if ((x[i] == 1) && !seen)
831 return false;
832 seen |= x[i] == 0;
833 }
834 return true;
835 }
837 for (int i=0; i<x.size(); i++)
838 if (x[i] == 0)
839 return false;
840 return true;
841 }
843 return false;
844 }
845
846 virtual void
849 using namespace Gecode;
850 switch (kind) {
851 case Kind::DISTINCT:
852 distinct(home,list);
853 break;
854 case Kind::REL:
855 rel(home,list,relation,ipl);
856 break;
857 case Kind::SLIDING:
858 Gecode::sequence(home,list,IntSet(1,1),width,1,1);
859 break;
861 sliding_sum(home,list,width,2,2,ipl);
862 break;
864 sliding_sum(home,list,width,1,3,ipl);
865 break;
866 case Kind::MIN_MAX: {
867 IntVar minimum(home,0,0);
868 IntVar maximum(home,2,2);
869 min(home,list,minimum);
870 max(home,list,maximum);
871 break;
872 }
873 case Kind::PRECEDE:
874 precede(home,list,0,1);
875 break;
877 precede(home,list,0,0);
878 break;
879 }
880 }
881 };
882
884 class Extremum : public OpenTest {
885 bool minimum;
886 bool alias;
887 public:
888 Extremum(bool minimum0, bool alias0, Gecode::IntPropLevel level)
889 : OpenTest(std::string("OpenList::")+(minimum0 ? "Min" : "Max")+
890 (alias0 ? "Alias::" : "Result::")+str(level),
891 3,alias0 ? 0 : 1,Gecode::IntSet(0,2),level),
892 minimum(minimum0), alias(alias0) {}
893
894 bool solution(const Assignment& x) const override {
895 int value = x[0];
896 for (int i=1; i<3; i++)
897 value = minimum ? std::min(value,x[i]) : std::max(value,x[i]);
898 return value == x[alias ? 0 : 3];
899 }
900
902 Gecode::IntVarArray& x) override {
903 if (minimum)
904 Gecode::min(home,list,x[alias ? 0 : 3],ipl);
905 else
906 Gecode::max(home,list,x[alias ? 0 : 3],ipl);
907 }
908 };
909
912 class BoundsSpace : public Gecode::Space {
913 public:
915 Gecode::IntVar minimum;
916 Gecode::IntVar maximum;
917
918 BoundsSpace(void)
919 : list(*this,Gecode::IntSet(0,10),5),
920 minimum(*this,0,10), maximum(*this,0,10) {
921 Gecode::min(*this,list,minimum);
922 Gecode::max(*this,list,maximum);
923 }
924 BoundsSpace(BoundsSpace& s) : Gecode::Space(s) {
925 list.update(*this,s.list);
926 minimum.update(*this,s.minimum);
927 maximum.update(*this,s.maximum);
928 }
929 Gecode::Space* copy(void) override { return new BoundsSpace(*this); }
930 };
931 public:
933 : ::Test::Base("Int::OpenList::ExtremumBounds",TestTags::check()) {}
934
935 bool run(void) override {
936 using namespace Gecode;
937 BoundsSpace source;
938 source.list.materialize(source,2);
939 if (source.status() == SS_FAILED)
940 return false;
941 rel(source,source.list[0],IRT_GQ,4);
942 rel(source,source.list[1],IRT_GQ,6);
943 rel(source,source.list[0],IRT_LQ,7);
944 rel(source,source.list[1],IRT_LQ,8);
945 if ((source.status() == SS_FAILED) ||
946 (source.maximum.min() != 6) || (source.minimum.max() != 7) ||
947 (source.minimum.min() != 0) || (source.maximum.max() != 10))
948 return false;
949 rel(source,source.minimum,IRT_GQ,5);
950 rel(source,source.maximum,IRT_LQ,7);
951 if ((source.status() == SS_FAILED) ||
952 (source.list[0].min() != 5) || (source.list[1].min() != 6) ||
953 (source.list[0].max() != 7) || (source.list[1].max() != 7))
954 return false;
955 std::unique_ptr<BoundsSpace> clone
956 (static_cast<BoundsSpace*>(source.clone()));
957 clone->list.materialize(*clone,3);
958 if ((clone->status() == SS_FAILED) ||
959 (clone->list[2].min() != 5) || (clone->list[2].max() != 7) ||
960 (source.list.known_length() != 2))
961 return false;
962 rel(*clone,clone->list[2],IRT_EQ,5);
963 if ((clone->status() == SS_FAILED) || (clone->minimum.max() != 5) ||
964 (source.minimum.max() != 7))
965 return false;
966 clone->list.close(*clone);
967 rel(*clone,clone->list[0],IRT_EQ,7);
968 if ((clone->status() == SS_FAILED) ||
969 !clone->minimum.assigned() || (clone->minimum.val() != 5) ||
970 !clone->maximum.assigned() || (clone->maximum.val() != 7))
971 return false;
972 rel(source,source.maximum,IRT_LQ,5);
973 return source.status() == SS_FAILED;
974 }
975 };
976
978 class EmptyMinimum : public Test {
979 public:
980 EmptyMinimum(void) : Test("OpenList::EmptyMinimum",1,0,1) {}
981 virtual bool solution(const Assignment&) const { return false; }
982 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
983 Gecode::OpenIntVarList list(home,0);
984 Gecode::min(home,list,x[0]);
985 list.close(home);
986 }
987 };
988
990 public:
992 : ::Test::Base("Int::OpenList::IncrementalConstraints",
993 TestTags::check()) {}
994
995 virtual bool
996 run(void) {
997 using namespace Gecode;
998 class IncrementalSpace : public Space {
999 public:
1000 OpenIntVarList list;
1001 IntVar minimum;
1002 IntVar maximum;
1003
1004 IncrementalSpace(Constraint::Kind kind)
1005 : list(*this,IntSet(0,2),2),
1006 minimum(*this,0,2), maximum(*this,0,2) {
1007 switch (kind) {
1009 distinct(*this,list);
1010 break;
1012 rel(*this,list,IRT_LE);
1013 break;
1015 Gecode::sequence(*this,list,IntSet(1,1),2,1,1);
1016 break;
1018 sliding_sum(*this,list,2,2,2);
1019 break;
1021 min(*this,list,minimum);
1022 max(*this,list,maximum);
1023 break;
1025 precede(*this,list,0,1);
1026 break;
1027 default:
1029 }
1030 }
1031
1032 IncrementalSpace(IncrementalSpace& s)
1033 : Space(s) {
1034 list.update(*this,s.list);
1035 minimum.update(*this,s.minimum);
1036 maximum.update(*this,s.maximum);
1037 }
1038
1039 virtual Space*
1040 copy(void) {
1041 return new IncrementalSpace(*this);
1042 }
1043 };
1044
1045 for (Constraint::Kind kind : {
1048 IncrementalSpace source(kind);
1049 const int first = kind == Constraint::Kind::PRECEDE ? 2 :
1050 ((kind == Constraint::Kind::REL || kind == Constraint::Kind::MIN_MAX) ? 1 : 0);
1051 source.list.materialize(source,1);
1052 rel(source,source.list[0],IRT_EQ,first);
1053 if ((source.status() == SS_FAILED) || !source.list[0].assigned())
1054 return false;
1055
1056 std::unique_ptr<IncrementalSpace> clone
1057 (static_cast<IncrementalSpace*>(source.clone()));
1058 clone->list.materialize(*clone,2);
1059 clone->list.close(*clone);
1060 if (kind == Constraint::Kind::MIN_MAX)
1061 rel(*clone,clone->list[1],IRT_EQ,2);
1062 if ((clone->status() == SS_FAILED) ||
1063 (source.list.known_length() != 1))
1064 return false;
1065 switch (kind) {
1067 if (clone->list[1].in(0))
1068 return false;
1069 break;
1072 if (!clone->list[1].assigned() || (clone->list[1].val() != 2))
1073 return false;
1074 break;
1076 if (!clone->list[1].assigned() || (clone->list[1].val() != 1))
1077 return false;
1078 break;
1080 if (!clone->minimum.assigned() || (clone->minimum.val() != 1) ||
1081 !clone->maximum.assigned() || (clone->maximum.val() != 2))
1082 return false;
1083 break;
1085 if (clone->list[1].in(1))
1086 return false;
1087 break;
1088 default:
1090 }
1091 }
1092 return true;
1093 }
1094 };
1095
1097 public:
1099
1103
1105 list.update(*this,s.list);
1106 }
1107
1108 virtual Gecode::Space*
1109 copy(void) {
1110 return new CallbackSpace(*this);
1111 }
1112 };
1113
1116 class SetSpace : public Gecode::Space {
1117 public:
1119
1120 SetSpace(void) {}
1121
1122 SetSpace(SetSpace& s) : Gecode::Space(s) {
1123 values.update(*this,s.values);
1124 }
1125
1126 ~SetSpace(void) {
1127 values.dispose(*this);
1128 }
1129
1130 Gecode::Space* copy(void) override {
1131 return new SetSpace(*this);
1132 }
1133 };
1134
1135 static bool
1136 check(const SetSpace& home, const Gecode::IntSet& expected) {
1137 Gecode::Int::GrowableIntSetRanges actual(home.values);
1138 Gecode::IntSetRanges ranges(expected);
1139 for (; actual() && ranges(); ++actual, ++ranges) {
1140 if ((actual.min() != ranges.min()) ||
1141 (actual.max() != ranges.max()) ||
1142 (actual.width() != ranges.width()))
1143 return false;
1144 for (int value : {ranges.min()-1,ranges.min(),
1145 ranges.max(),ranges.max()+1})
1146 if (home.values.in(value) != expected.in(value))
1147 return false;
1148 }
1149 if (actual() || ranges())
1150 return false;
1151 for (int value=-40; value<=40; value++)
1152 if (home.values.in(value) != expected.in(value))
1153 return false;
1154 return true;
1155 }
1156
1157 static bool
1158 add(SetSpace& home, std::set<int>& expected,
1159 const Gecode::IntSet& batch) {
1160 Gecode::IntSetRanges ranges(batch);
1161 home.values.add_r(home,ranges);
1162 for (Gecode::IntSetValues values(batch); values(); ++values)
1163 expected.insert(values.val());
1164 const std::vector<int> values(expected.begin(),expected.end());
1165 return check(home,Gecode::IntSet(values.data(),
1166 static_cast<int>(values.size())));
1167 }
1168
1169 public:
1171 : ::Test::Base("Int::OpenList::GrowableIntSet",TestTags::check()) {}
1172
1173 bool run(void) override {
1174 using namespace Gecode;
1175 SetSpace source;
1176 std::set<int> expected;
1177 const IntSet batches[] = {
1178 IntSet::empty, IntSet({10,12}), IntSet(10,12),
1179 IntSet(-10,-8), IntSet(20,22), IntSet(0,2), IntSet(3,9),
1180 IntSet(-9,-7), IntSet(18,20), IntSet(11,11),
1181 IntSet({{-12,-9},{-6,1},{15,16},{19,24}}),
1183 };
1184 for (const IntSet& batch : batches)
1185 if (!add(source,expected,batch))
1186 return false;
1187 if (source.status() == SS_FAILED)
1188 return false;
1189 std::unique_ptr<SetSpace> clone
1190 (static_cast<SetSpace*>(source.clone()));
1191 std::unique_ptr<SetSpace> sibling
1192 (static_cast<SetSpace*>(source.clone()));
1193 std::set<int> clone_expected(expected);
1194 const IntSet growth({{-30,-29},{-20,-19},{14,14},{18,18},
1195 {26,26},{28,28},{30,30}});
1196 if (!add(*clone,clone_expected,IntSet(26,26)) ||
1197 !add(*clone,clone_expected,growth) ||
1198 !add(source,expected,IntSet::empty) ||
1199 !add(*sibling,expected,IntSet::empty))
1200 return false;
1201 // A single wide range exercises unsigned width and removes all holes.
1203 IntSetRanges ranges(full);
1204 source.values.add_r(source,ranges);
1205 return check(source,full) &&
1206 add(*clone,clone_expected,IntSet::empty) &&
1207 add(*sibling,expected,IntSet::empty);
1208 }
1209 };
1210
1213 public:
1215 : ::Test::Base("Int::OpenList::DistinctWaves",TestTags::check()) {}
1216
1217 bool run(void) override {
1218 using namespace Gecode;
1219 CallbackSpace source([](int) { return IntSet(1,4); },
1220 [](Space&, OpenIntVarList, int) {});
1221 distinct(source,source.list);
1222 source.list.append(source,IntVar(source,1,1));
1223 if (source.status() == SS_FAILED)
1224 return false;
1225 std::unique_ptr<CallbackSpace> duplicate
1226 (static_cast<CallbackSpace*>(source.clone()));
1227 // Reverse the chain so each assignment needs another pruning wave.
1228 for (int lower=3; lower>=1; lower--)
1229 source.list.append(source,IntVar(source,lower,lower+1));
1230 if (source.status() == SS_FAILED)
1231 return false;
1232 for (int i=1; i<4; i++)
1233 if (!source.list[i].assigned() || (source.list[i].val() != 5-i))
1234 return false;
1235 source.list.close(source);
1236 if ((source.status() == SS_FAILED) ||
1237 !source.list.length().assigned() ||
1238 (source.list.length().val() != 4))
1239 return false;
1240 duplicate->list.append(*duplicate,IntVar(*duplicate,1,2));
1241 duplicate->list.append(*duplicate,IntVar(*duplicate,1,2));
1242 return duplicate->status() == SS_FAILED;
1243 }
1244 };
1245
1248
1249 class GroupSpace : public Gecode::Space {
1250 public:
1251 enum class Kind { REL, SUM, PRECEDE };
1254
1255 GroupSpace(Kind kind, bool close)
1256 : list(*this,Gecode::IntSet(0,2),3) {
1257 using namespace Gecode;
1258 switch (kind) {
1259 case Kind::REL:
1260 rel((*this)(group),list,IRT_NQ);
1261 break;
1262 case Kind::SUM:
1263 sliding_sum((*this)(group),list,2,2,2);
1264 break;
1265 case Kind::PRECEDE:
1266 precede((*this)(group),list,0,1);
1267 break;
1268 }
1269 list.materialize(*this,2);
1270 if (close)
1271 list.close(*this);
1272 }
1273
1275 list.update(*this,s.list);
1276 }
1277
1278 virtual Gecode::Space*
1279 copy(void) {
1280 return new GroupSpace(*this);
1281 }
1282 };
1283
1285 class Group : public ::Test::Base {
1286 protected:
1288 bool kill;
1289 public:
1290 Group(const std::string& name, GroupSpace::Kind kind0, bool kill0)
1291 : ::Test::Base("Int::OpenList::Group::"+name+
1292 (kill0 ? "::Kill" : "::Disable")),
1293 kind(kind0), kill(kill0) {}
1294
1295 virtual bool
1296 run(void) {
1297 using namespace Gecode;
1298 for (int close=0; close<2; close++) {
1299 GroupSpace source(kind,close != 0);
1300 if (source.status() == SS_FAILED)
1301 return false;
1302 if (kill)
1303 source.group.kill(source);
1304 else
1305 source.group.disable(source);
1306 // These values are in the domains but violate each constraint.
1307 rel(source,source.list[0],IRT_EQ,
1308 kind == GroupSpace::Kind::PRECEDE ? 2 : 0);
1309 rel(source,source.list[1],IRT_EQ,
1310 kind == GroupSpace::Kind::PRECEDE ? 1 : 0);
1311 if (source.status() == SS_FAILED)
1312 return false;
1313 if (!kill) {
1314 source.group.enable(source);
1315 if (source.status() != SS_FAILED)
1316 return false;
1317 }
1318 }
1319 return true;
1320 }
1321 };
1322
1329
1330 class Dispose : public ::Test::Base {
1331 public:
1333 : ::Test::Base("Int::OpenList::Dispose",TestTags::check()) {}
1334
1335 virtual bool
1336 run(void) {
1337 using namespace Gecode;
1338 std::shared_ptr<int> domain(new int(0));
1339 std::shared_ptr<int> transition(new int(0));
1340 CallbackSpace* source = new CallbackSpace(
1341 [domain](int) { return IntSet(0,1); },
1342 [transition](Space&, OpenIntVarList, int) {});
1343 source->list.materialize(*source,2);
1344 DFA dfa(0,{{0,0,0},{0,1,0}},{0});
1345 extensional(*source,source->list,dfa);
1346 if (source->status() == SS_FAILED) {
1347 delete source;
1348 return false;
1349 }
1350 CallbackSpace* clone = static_cast<CallbackSpace*>(source->clone());
1351 delete source;
1352 const bool retained = (domain.use_count() > 1) &&
1353 (transition.use_count() > 1);
1354 delete clone;
1355 return retained && (domain.use_count() == 1) &&
1356 (transition.use_count() == 1);
1357 }
1358 };
1359
1361 public:
1363 : ::Test::Base("Int::OpenList::CallbackLength",TestTags::check()) {}
1364
1365 virtual bool
1366 run(void) {
1367 using namespace Gecode;
1368 for (int assign=0; assign<2; assign++)
1369 for (int close=0; close<2; close++) {
1370 CallbackSpace source([](int) { return IntSet(0,1); },
1371 [assign](Space& home, OpenIntVarList list, int i) {
1372 if (i == 0)
1373 rel(home,list.length(),assign ? IRT_EQ : IRT_GQ,3);
1374 });
1375 rel(source,source.list.length(),IRT_GQ,1);
1376 if (close)
1377 source.list.close(source);
1378 if ((source.status() == SS_FAILED) ||
1379 (source.list.known_length() != 3))
1380 return false;
1381 }
1382 return true;
1383 }
1384 };
1385
1387 class NoGPI : public ::Test::Base {
1388 protected:
1389 static void
1391 Gecode::IntVar x(home,0,10);
1392 Gecode::IntVar y(home,0,10);
1393 Gecode::rel(home(group),x,Gecode::IRT_LE,y);
1394 }
1395
1396 static int
1398 double afc) {
1399 int n = 0;
1400 for (Gecode::Propagators ps(home,group); ps(); ++ps) {
1401 if (ps.propagator().afc() != afc)
1402 return -1;
1403 n++;
1404 }
1405 return n;
1406 }
1407
1408 public:
1409 NoGPI(void)
1410 : ::Test::Base("Int::OpenList::NoGPI",TestTags::check()) {}
1411
1412 virtual bool
1413 run(void) {
1414 using namespace Gecode;
1415 CallbackSpace home([](int) { return IntSet(0,1); },
1416 [](Space&, OpenIntVarList, int) {});
1419 PropagatorGroup selected;
1420 PropagatorGroup ordinary;
1421 PropagatorGroup suppressed;
1422 OpenVarList<IntVar> list(home,
1423 [factory,selected](Space& home, int) {
1424 post(home,factory);
1425 {
1426 Space::UseGPI use_gpi(home);
1427 post(home,selected);
1428 }
1429 return IntVar(home,0,10);
1430 },
1431 [transition,selected](Space& home, OpenVarList<IntVar> list, int i) {
1432 post(home,transition);
1433 if (i == 3)
1434 throw 1;
1435 {
1436 Space::UseGPI use_gpi(home);
1437 post(home,selected);
1438 if (i == 0)
1439 list.materialize(home,2);
1440 post(home,selected);
1441 }
1442 post(home,transition);
1443 },4);
1444
1445 list.materialize(home,1);
1446 post(home,ordinary);
1447 if ((list.known_length() != 2) ||
1448 (count(home,factory,0.0) != 2) ||
1449 (count(home,transition,0.0) != 4) ||
1450 (count(home,selected,1.0) != 6))
1451 return false;
1452 {
1453 Space::NoGPI no_gpi(home);
1454 {
1455 Space::UseGPI use_gpi(home);
1456 list.append(home,IntVar(home,0,10));
1457 post(home,ordinary);
1458 }
1459 post(home,suppressed);
1460 }
1461 bool threw = false;
1462 try {
1463 list.append(home,IntVar(home,0,10));
1464 } catch (int) {
1465 threw = true;
1466 }
1467 post(home,ordinary);
1468 return threw && (count(home,factory,0.0) == 2) &&
1469 (count(home,transition,0.0) == 7) &&
1470 (count(home,selected,1.0) == 8) &&
1471 (count(home,ordinary,1.0) == 3) &&
1472 (count(home,suppressed,0.0) == 1) &&
1473 (home.status() != SS_FAILED);
1474 }
1475 };
1476
1477 class FailedGet : public ::Test::Base {
1478 public:
1480 : ::Test::Base("Int::OpenList::FailedGet") {}
1481
1482 virtual bool
1483 run(void) {
1484 using namespace Gecode;
1485 CallbackSpace source([](int) { return IntSet(0,1); },
1486 [](Space& home, OpenIntVarList, int) { home.fail(); });
1487 IntVar x = source.list.get(source,4);
1488 return source.failed() && (x.varimp() == nullptr);
1489 }
1490 };
1491
1493 class ValueCommit : public ::Test::Base {
1494 public:
1496 : ::Test::Base("Int::OpenList::ValueCommit") {}
1497
1498 virtual bool
1499 run(void) {
1500 using namespace Gecode;
1501 CallbackSpace source([](int) { return IntSet(0,1); },
1502 [](Space& home, OpenIntVarList, int i) {
1503 if (i == 1)
1504 home.fail();
1505 });
1506 source.list.materialize(source,1);
1507 branch(source,source.list);
1508 if (source.status() != SS_BRANCH)
1509 return false;
1510 const Choice* choice = source.choice();
1511 bool valid = true;
1512 for (unsigned int alternative=0; alternative<2; alternative++) {
1513 CallbackSpace* clone = static_cast<CallbackSpace*>(source.clone());
1514 rel(*clone,clone->list.length(),IRT_GQ,2);
1515 clone->commit(*choice,alternative);
1516 valid &= !clone->failed() && (clone->list.known_length() == 1) &&
1517 clone->list[0].assigned() &&
1518 (clone->list[0].val() == static_cast<int>(alternative));
1519 valid &= clone->status() == SS_FAILED;
1520 delete clone;
1521 }
1522 delete choice;
1523 return valid;
1524 }
1525 };
1526
1528 class ValueReplay : public ::Test::Base {
1529 public:
1531 : ::Test::Base("Int::OpenList::ValueReplay",TestTags::check()) {}
1532
1533 virtual bool
1534 run(void) {
1535 using namespace Gecode;
1536 CallbackSpace source([](int) { return IntSet(0,1); },
1537 [](Space& home, OpenIntVarList list, int i) {
1538 if (i == 0) {
1539 BoolVar zero(home,0,1);
1540 rel(home,list[0],IRT_EQ,0,Reify(zero));
1541 rel(home,list.length(),IRT_GQ,2,Reify(zero,RM_IMP));
1542 }
1543 });
1544 source.list.materialize(source,1);
1545 branch(source,source.list);
1546 if (source.status() != SS_BRANCH)
1547 return false;
1548 std::unique_ptr<const Choice> first(source.choice());
1549 std::unique_ptr<CallbackSpace> replay
1550 (static_cast<CallbackSpace*>(source.clone()));
1551 source.commit(*first,0);
1552 if ((source.status() != SS_BRANCH) ||
1553 (source.list.known_length() != 2))
1554 return false;
1555 std::unique_ptr<const Choice> second(source.choice());
1556 // Recomputation commits the path without propagating between choices.
1557 replay->commit(*first,0);
1558 for (unsigned int a=0; a<second->alternatives(); a++) {
1559 std::ostringstream printed;
1560 replay->print(*second,a,printed);
1561 if (printed.str().empty() || (replay->list.known_length() != 1))
1562 return false;
1563 }
1564 replay->commit(*second,0);
1565 return (replay->status() != SS_FAILED) &&
1566 (replay->list.known_length() == 2) &&
1567 replay->list[0].assigned() && (replay->list[0].val() == 0) &&
1568 replay->list[1].assigned() && (replay->list[1].val() == 0);
1569 }
1570 };
1571
1574 public:
1576 : ::Test::Base("Int::OpenList::ImpossibleWindow") {}
1577
1578 virtual bool
1579 run(void) {
1580 using namespace Gecode;
1581 for (int sum=0; sum<2; sum++)
1582 for (int size=0; size<3; size++) {
1583 CallbackSpace source([](int) { return IntSet(0,1); },
1584 [](Space&, OpenIntVarList, int) {});
1585 if (sum)
1586 sliding_sum(source,source.list,2,2,1);
1587 else
1588 Gecode::sequence(source,source.list,IntSet(0,1),2,3,3);
1589 rel(source,source.list.length(),IRT_EQ,size);
1590 const bool failed = source.status() == SS_FAILED;
1591 if (failed != (size == 2))
1592 return false;
1593 if (!failed && (source.list.known_length() != size))
1594 return false;
1595 }
1596 return true;
1597 }
1598 };
1599
1602 public:
1605
1606 PatternSpace(const PatternMining::Database& data, int support)
1607 : list(*this,data.domain(),data.max_length()) {
1608 Gecode::rel(*this,list.length(),Gecode::IRT_GQ,1);
1609 frequency = PatternMining::frequent(*this,list,data,support);
1610 Gecode::branch(*this,list);
1611 }
1612
1614 list.update(*this,s.list);
1615 frequency.update(*this,s.frequency);
1616 }
1617
1618 virtual Gecode::Space* copy(void) {
1619 return new PatternSpace(*this);
1620 }
1621 };
1622
1625 public:
1627 : ::Test::Base("Int::OpenList::Pattern::Enumeration",
1628 TestTags::check()) {}
1629
1630 virtual bool run(void) {
1631 using namespace Gecode;
1632 const PatternMining::Sequences inputs[] = {
1633 {{17,1000000,17},{17,1000000,17},{1000000,17,42},{17,42}},
1634 {{1,1},{1,2},{2,1}}
1635 };
1636 for (const PatternMining::Sequences& input : inputs) {
1637 std::set<std::vector<int>> candidates;
1638 for (const std::vector<int>& row : input)
1639 for (unsigned int mask=1; mask<(1U<<row.size()); mask++) {
1640 std::vector<int> pattern;
1641 for (unsigned int i=0; i<row.size(); i++)
1642 if (mask & (1U<<i))
1643 pattern.push_back(row[i]);
1644 candidates.insert(pattern);
1645 }
1646 const PatternMining::Database data(input);
1647 const int thresholds[] = {1,2,static_cast<int>(input.size())};
1648 for (int threshold : thresholds) {
1649 std::set<std::vector<int>> expected;
1650 std::set<std::vector<int>> found;
1651 for (const std::vector<int>& pattern : candidates) {
1652 int support = 0;
1653 for (const std::vector<int>& row : input) {
1654 auto next = row.begin();
1655 bool matches = true;
1656 for (int item : pattern) {
1657 next = std::find(next,row.end(),item);
1658 if (next == row.end()) {
1659 matches = false;
1660 break;
1661 }
1662 ++next;
1663 }
1664 support += matches;
1665 }
1666 if (support >= threshold)
1667 expected.insert(pattern);
1668 }
1669 PatternSpace root(data,threshold);
1670 Search::Options options;
1671 options.threads = 1;
1672 options.c_d = 1000;
1673 options.a_d = 1000;
1674 DFS<PatternSpace> search(&root,options);
1675 while (PatternSpace* solution = search.next()) {
1676 std::unique_ptr<PatternSpace> owned(solution);
1677 if (!solution->list.length().assigned() ||
1678 (solution->list.length().val() !=
1679 solution->list.known_length()))
1680 return false;
1681 std::vector<int> pattern;
1682 for (int i=0; i<solution->list.known_length(); i++) {
1683 if (!solution->list[i].assigned())
1684 return false;
1685 pattern.push_back(solution->list[i].val());
1686 }
1687 if (!solution->frequency.assigned() ||
1688 (solution->frequency.val() != data.support(pattern)) ||
1689 !found.insert(pattern).second)
1690 return false;
1691 }
1692 if (found != expected)
1693 return false;
1694 }
1695 }
1696 return true;
1697 }
1698 };
1699
1702 public:
1704 : ::Test::Base("Int::OpenList::Pattern::Growth",TestTags::check()) {}
1705
1706 virtual bool run(void) {
1707 using namespace Gecode;
1708 const PatternMining::Database data({{1,2,1},{1,2,2},{1,1,2}});
1709 PatternSpace source(data,2);
1710 source.list.materialize(source,1);
1711 rel(source,source.list[0],IRT_EQ,1);
1712 if (source.status() == SS_FAILED)
1713 return false;
1714 std::unique_ptr<PatternSpace> clone
1715 (static_cast<PatternSpace*>(source.clone()));
1716 clone->list.materialize(*clone,2);
1717 rel(*clone,clone->list[1],IRT_EQ,1);
1718 if ((clone->status() == SS_FAILED) ||
1719 !clone->list.length().assigned() ||
1720 (clone->list.length().val() != 2) ||
1721 (source.list.known_length() != 1) ||
1722 (source.list.length().min() != 1))
1723 return false;
1724 source.list.materialize(source,2);
1725 rel(source,source.list[1],IRT_EQ,2);
1726 if ((source.status() == SS_FAILED) ||
1727 !source.list.length().assigned() ||
1728 (source.list.length().val() != 2) ||
1729 (clone->list[1].val() != 1))
1730 return false;
1731
1732 // Assigning a later position must not advance the projected prefix.
1733 PatternSpace later(data,2);
1734 later.list.materialize(later,2);
1735 rel(later,later.list[1],IRT_EQ,2);
1736 if ((later.status() == SS_FAILED) || later.list[0].assigned())
1737 return false;
1738 std::unique_ptr<PatternSpace> invalid
1739 (static_cast<PatternSpace*>(later.clone()));
1740 rel(*invalid,invalid->list[0],IRT_EQ,2);
1741 if (invalid->status() != SS_FAILED)
1742 return false;
1743 rel(later,later.list[0],IRT_EQ,1);
1744 if (later.status() == SS_FAILED)
1745 return false;
1746
1747 // Both singleton prefixes are frequent, but no extension is frequent.
1748 const PatternMining::Database terminal({{1,1},{1,2},{2,1}});
1749 for (int item=1; item<=2; item++) {
1750 PatternSpace leaf(terminal,2);
1751 leaf.list.materialize(leaf,1);
1752 rel(leaf,leaf.list[0],IRT_EQ,item);
1753 if ((leaf.status() == SS_FAILED) ||
1754 !leaf.list.length().assigned() ||
1755 (leaf.list.length().val() != 1))
1756 return false;
1757 }
1758 return true;
1759 }
1760 };
1761
1764 public:
1766 : ::Test::Base("Int::OpenList::Pattern::Input",TestTags::check()) {}
1767
1768 virtual bool run(void) {
1769 using namespace PatternMining;
1770 std::istringstream rows("# comment\n17 -1 1000000 -1 -2\r\n"
1771 "17 -1 1000000 -1 -2\n");
1772 if (read_database(rows,Format::SPMF) !=
1773 Sequences({{17,1000000},{17,1000000}}) ||
1774 read_sequence("ABA",Format::LETTERS) != std::vector<int>({1,2,1}) ||
1775 read_sequence("17 1000000",Format::INTEGERS) !=
1776 std::vector<int>({17,1000000}) ||
1777 (minimum_support("33.333333",3) != 1) ||
1778 (minimum_support("33.333334",3) != 2) ||
1779 (minimum_support("100",2000000000) != 2000000000) ||
1780 (minimum_support("0.000001",2000000000) != 20))
1781 return false;
1782 for (const char* text : {"1 2 -1 -2", "1 -2", "1 -1",
1783 "1 -1 -2 2", "2147483648 -1 -2"}) {
1784 bool rejected = false;
1785 try {
1786 (void) read_sequence(text,Format::SPMF);
1787 } catch (const std::invalid_argument&) {
1788 rejected = true;
1789 }
1790 if (!rejected)
1791 return false;
1792 }
1793 for (const char* text : {"0", "101", "0.0000001",
1794 "184467440737095516160"}) {
1795 bool rejected = false;
1796 try {
1797 (void) minimum_support(text,3);
1798 } catch (const std::invalid_argument&) {
1799 rejected = true;
1800 }
1801 if (!rejected)
1802 return false;
1803 }
1804 return true;
1805 }
1806 };
1807
1811
1815
1820
1843 5,3,Gecode::IPL_DOM);
1845 4,2,Gecode::IPL_BND);
1856
1857 }
1858
1859}}
1860
1861// STATISTICS: test-int
Archive representation
Definition archive.hpp:42
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1606
Boolean integer variables.
Definition int.hh:534
Base-class for branchers.
Definition core.hpp:1460
Choice for performing commit
Definition core.hpp:1430
virtual void archive(Archive &e) const
Archive into e.
Definition core.cpp:958
unsigned int alternatives(void) const
Return number of alternatives.
Definition core.hpp:3999
Finite automaton with deterministic construction by default.
Definition int.hh:2620
Depth-first search engine.
Definition search.hh:1211
Float variables.
Definition float.hh:865
Passing integer arguments.
Definition int.hh:653
Range iterator for integer sets.
Definition int.hh:311
Value iterator for integer sets.
Definition int.hh:352
Integer sets.
Definition int.hh:179
bool in(int n) const
Return whether n is included in the set.
static const IntSet empty
Empty set.
Definition int.hh:302
Which values to select for branching first.
Definition int.hh:5969
Passing integer variables.
Definition int.hh:681
Integer variable array.
Definition int.hh:792
Integer variables.
Definition int.hh:390
int min(void) const
Return minimum of domain.
Definition int.hpp:62
int val(void) const
Return assigned value.
Definition int.hpp:56
int max(void) const
Return maximum of domain.
Definition int.hpp:70
Exception: Arguments contain same variable multiply
Definition exception.hpp:80
Borrowed forward iterator over a growable set's ranges.
A Space-owned set of integer values with growable canonical range storage.
bool in(int value) const
Test membership.
void add_r(Space &home, I added)
Add the ranges from a copyable, independent canonical iterator.
Integer view for integer variables.
Definition view.hpp:129
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition int.hpp:139
Exception: Unknown value or variable selection passed as argument
No-good literal recorded during search.
Definition core.hpp:1358
virtual ExecStatus prune(Space &home)=0
Propagate the negation of the no-good literal.
virtual NGL::Status status(const Space &home) const =0
Test the status of the no-good literal.
@ NONE
The literal is neither failed nor subsumed.
Definition core.hpp:1367
Open list of Boolean variables.
Definition int.hh:1118
Open list of integer variables.
Definition int.hh:1076
std::function< IntSet(int i)> Domain
Function returning the domain for position i.
Definition int.hh:1084
Space-local list of variables with an open length.
Definition int.hh:923
void materialize(Space &home, int n)
Materialize the first n variables.
void close(Space &home)
Close the list at its materialized length.
void update(Space &home, OpenVarList< Var > &s)
Update during cloning.
int known_length(void) const
Return the number of constructed positions (their values may be unassigned).
IntVar length(void) const
Return the eventual-length variable.
std::function< void(Space &home, OpenVarList< IntVar > x, int i)> Transition
Definition int.hh:959
Var get(Space &home, int i)
Require and return the variable at position i.
View interface to a space-local list with an open length.
Definition int.hh:1044
void materialize(Space &home, int n)
Require and construct at least the first n positions.
Int::IntView length(void) const
Return the eventual-length view.
int known_length(void) const
Return the number of constructed positions.
void update(Space &home, OpenViewList< View > &s)
Update during cloning.
Options for scripts
Definition driver.hh:447
Group of propagators.
Definition core.hpp:734
void disable(Space &home)
Disable all propagators in a group.
Definition core.cpp:1046
void enable(Space &home, bool s=true)
Enable all propagators in a group.
Definition core.cpp:1055
void kill(Space &home)
Kill all propagators in a group.
Definition core.cpp:1033
Class to iterate over propagators in a group.
Definition core.hpp:2890
Reification specification.
Definition int.hh:1176
Random number generator.
Definition rnd.hpp:42
virtual T * next(void)
Return next solution (nullptr, if none exists or search has been stopped).
Definition base.hpp:46
Stop-object based on number of nodes
Definition search.hh:951
Set variables
Definition set.hh:127
Suppress global propagator information during scoped posting.
Definition core.hpp:2070
Enable global propagator information during scoped posting.
Definition core.hpp:2092
Computation spaces.
Definition core.hpp:1787
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition var.hpp:116
bool assigned(void) const
Test whether view is assigned.
Definition var.hpp:111
Base class for variables.
Definition var.hpp:40
Immutable input, with dense ranks internally and original IDs externally.
int support(const std::vector< int > &pattern) const
Count supporting records, rather than embeddings within a record.
Base(std::string s)
Create and register a standard test with name s.
Definition test.cpp:125
Base * next(void) const
Return next test.
Definition test.hpp:103
const std::string & name(void) const
Return name of test.
Definition test.hpp:91
Base class for assignments
Definition int.hh:73
int size(void) const
Return number of variables.
Definition int.hpp:46
Gecode::OpenVarList< Var > list
virtual Gecode::Space * copy(void)
Copying member function.
virtual bool run(void)
Run test.
virtual bool run(void)
Run test.
virtual Gecode::Space * copy(void)
Copying member function.
Gecode::OpenBoolVarList list
virtual Gecode::Space * copy(void)
Copying member function.
static bool check(BranchOrderSpace::Order order, int first_length)
virtual bool run(void)
Run test.
virtual bool run(void)
Run test.
CallbackSpace(Gecode::OpenIntVarList::Domain domain, Gecode::OpenIntVarList::Transition transition)
virtual Gecode::Space * copy(void)
Copying member function.
Test constraint semantics both while growing and after closure.
Constraint(const std::string &name, Kind k, int size, int width0=2, Gecode::IntPropLevel level=Gecode::IPL_DEF)
Constraint(Gecode::IntRelType relation0, Gecode::IntPropLevel level)
virtual void post(Gecode::Space &home, Gecode::OpenIntVarList list, Gecode::IntVarArray &)
Post the tested relation on an open list and its variable array.
virtual bool solution(const Assignment &x) const
Check for solution.
virtual bool run(void)
Run test.
Values assigned before list growth can trigger several pruning waves.
bool run(void) override
Run test.
An empty list has no minimum.
virtual bool solution(const Assignment &) const
Check for solution.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint.
Bounds propagate through existing items before the list is closed.
bool run(void) override
Run test.
Extremum bounds must follow old items as well as newly appended items.
void post(Gecode::Space &home, Gecode::OpenIntVarList list, Gecode::IntVarArray &x) override
Post the tested relation on an open list and its variable array.
Extremum(bool minimum0, bool alias0, Gecode::IntPropLevel level)
bool solution(const Assignment &x) const override
Check for solution.
Gecode::OpenVarList< Gecode::SetVar > sets
Gecode::OpenVarList< Gecode::FloatVar > floats
virtual Gecode::Space * copy(void)
Copying member function.
virtual bool run(void)
Run test.
virtual bool run(void)
Run test.
virtual bool run(void)
Run test.
Gecode::PropagatorGroup group
GroupSpace(Kind kind, bool close)
virtual Gecode::Space * copy(void)
Copying member function.
Test group control after an open constraint has posted its children.
virtual bool run(void)
Run test.
Group(const std::string &name, GroupSpace::Kind kind0, bool kill0)
Range unions and later clone growth preserve canonical sets.
bool run(void) override
Run test.
Impossible window bounds still permit lists too short to contain a window.
Callbacks suppress AFC unless opted in; nested growth restores each scope.
virtual bool run(void)
Run test.
static void post(Gecode::Space &home, Gecode::PropagatorGroup group)
static int count(const Gecode::Space &home, Gecode::PropagatorGroup group, double afc)
virtual bool run(void)
Run test.
Test automatic and explicit list materialization.
Space used by open list materialization tests.
virtual Gecode::Space * copy(void)
Copying member function.
Compare complete solution sets with independently enumerated subsequences.
Clones keep separate projections; later assignments wait for their prefix.
virtual bool run(void)
Run test.
Input validation and exact rounding of percentage support.
virtual bool run(void)
Run test.
Search model for the private common-pattern projection.
virtual Gecode::Space * copy(void)
Copying member function.
PatternSpace(const PatternMining::Database &data, int support)
virtual Gecode::Space * copy(void)
Copying member function.
SelectorChoiceSpace(Gecode::IntValBranch vals)
virtual bool run(void)
Run test.
SelectorSpace(Gecode::IntValBranch vals, bool length_first=false)
virtual Gecode::Space * copy(void)
Copying member function.
virtual bool run(void)
Run test.
virtual Gecode::Space * copy(void)
Copying member function.
virtual bool run(void)
Run test.
A value commit must not construct positions required by pending propagation.
virtual bool run(void)
Run test.
Replay value choices after propagation has extended the original list.
virtual bool run(void)
Run test.
View handles share growth while cloned spaces keep independent domains.
bool run(void) override
Run test.
OpenTest(const std::string &name, int items, int extra, const Gecode::IntSet &domain, Gecode::IntPropLevel ipl=Gecode::IPL_DEF)
Initialize item and auxiliary variables with the common domain.
Definition int.cpp:1159
static std::string str(bool b)
Map bool to string.
Definition int.hpp:278
Gecode::IntPropLevel ipl
Propagation level.
Definition int.hh:281
static bool cmp(T x, Gecode::IntRelType r, T y)
Compare x and y with respect to r.
Definition int.hpp:296
Set of test tags.
Definition test.hh:105
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
void fail(void)
Fail space.
Definition core.hpp:4275
void assign(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatAssign vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Assign all x with variable selection vars and value selection vals.
Definition branch.cpp:111
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition linear.cpp:41
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
void extensional(Home home, const IntVarArgs &x, DFA d, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for extensional constraint described by a DFA.
void precede(Home home, const IntVarArgs &x, int s, int t, IntPropLevel=IPL_DEF)
Post propagator that s precedes t in x.
Definition precede.cpp:43
IntRelType
Relation types for integers.
Definition int.hh:1225
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:1274
@ IRT_EQ
Equality ( ).
Definition int.hh:1226
@ IRT_NQ
Disequality ( ).
Definition int.hh:1227
@ IRT_GQ
Greater or equal ( ).
Definition int.hh:1230
@ IRT_LE
Less ( ).
Definition int.hh:1229
@ IRT_GR
Greater ( ).
Definition int.hh:1231
@ IRT_LQ
Less or equal ( ).
Definition int.hh:1228
@ RM_IMP
Implication for reification.
Definition int.hh:1162
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:1279
@ IPL_DEF
Simple propagation levels.
Definition int.hh:1276
@ IPL_BND
Bounds propagation.
Definition int.hh:1278
Space(void)
Default constructor.
Definition core.cpp:121
virtual Space * copy(void)=0
Copying member function.
void print(const Choice &c, unsigned int a, std::ostream &o) const
Print branch for choice c and alternative a.
Definition core.cpp:687
Space * clone(void) const
Clone space.
Definition core.hpp:3384
const Choice * choice(void)
Create new choice for current brancher.
Definition core.cpp:568
SpaceStatus status(StatusStatistics &stat)
Query space status.
Definition core.cpp:281
NGL * ngl(const Choice &c, unsigned int a)
Create no-good literal for choice c and alternative a.
Definition core.cpp:673
@ SS_BRANCH
Space must be branched (at least one brancher left)
Definition core.hpp:1729
@ SS_FAILED
Space is failed
Definition core.hpp:1727
const int min
Smallest allowed integer value.
Definition int.hh:123
const int max
Largest allowed integer value.
Definition int.hh:121
Engine * dfsengine(Space *s, const Options &o)
Create depth-first engine.
Definition dfs.cpp:45
Gecode toplevel namespace
IntValBranch INT_VAL_SPLIT_MIN(void)
Select values not greater than mean of smallest and largest value.
Definition val.hpp:75
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition count.cpp:40
IntValBranch INT_VAL_RANGE_MIN(void)
Select the smallest range of the variable domain if it has several ranges, otherwise select values no...
Definition val.hpp:85
IntValBranch INT_VAL_RANGE_MAX(void)
Select the largest range of the variable domain if it has several ranges, otherwise select values gre...
Definition val.hpp:90
IntValBranch INT_VALUES_MAX(void)
Try all values starting from largest.
Definition val.hpp:105
void order(Home home, IntVar s0, int p0, IntVar s1, int p1, BoolVar b, IntPropLevel ipl=IPL_DEF)
Post propagators for ordering two tasks.
Definition order.cpp:41
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition sequence.cpp:47
IntValBranch INT_VAL_MED(void)
Select greatest value not greater than the median.
Definition val.hpp:60
IntValBranch INT_VAL(IntBranchVal v, IntBranchCommit c=nullptr)
Select value as defined by the value function v and commit function c Uses a commit function as defau...
Definition val.hpp:95
TieBreak< VarBranch > tiebreak(VarBranch a, VarBranch b)
Combine variable selection criteria a and b for tie-breaking.
Definition tiebreak.hpp:80
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
IntVarBranch INT_VAR_CHB_MIN(IntCHB c, BranchTbl tbl=nullptr)
Select variable with lowest CHB Q-score.
Definition var.hpp:166
IntValBranch INT_VALUES_MIN(void)
Try all values starting from smallest.
Definition val.hpp:100
IntValBranch INT_VAL_MAX(void)
Select largest value.
Definition val.hpp:65
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
Definition val.hpp:135
IntValBranch INT_VAL_SPLIT_MAX(void)
Select values greater than mean of smallest and largest value.
Definition val.hpp:80
LinIntExpr sum(const IntVarArgs &x)
Construct linear expression as sum of integer variables.
Definition int-expr.cpp:953
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55
IntVarBranch INT_VAR_MAX_MAX(BranchTbl tbl=nullptr)
Select variable with largest max.
Definition var.hpp:201
IntVarBranch INT_VAR_ACTION_MIN(double d=1.0, BranchTbl tbl=nullptr)
Select variable with lowest action with decay factor d.
Definition var.hpp:146
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:481
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
IntVarBranch INT_VAR_MERIT_MAX(IntBranchMerit bm, BranchTbl tbl=nullptr)
Select variable with highest merit according to branch merit function bm.
Definition var.hpp:111
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl=nullptr)
Select variable with smallest domain size.
Definition var.hpp:206
BoolVarBranch BOOL_VAR_MERIT_MAX(BoolBranchMerit bm, BranchTbl tbl=nullptr)
Select variable with highest merit according to branch merit function bm.
Definition var.hpp:379
IntValBranch INT_VAL_RND(Rnd r)
Select random value.
Definition val.hpp:70
std::vector< int > read_sequence(const std::string &line, Format format)
Read positive integer items or A..Z (represented by item IDs 1..26).
int minimum_support(const std::string &percent, int sequences)
Round the support percentage (at most six decimals) up to a record count.
IntVar frequent(Home home, OpenIntVarList pattern, const Database &database, int support)
Enforce minimum support and return its exact count when the pattern is complete.
std::vector< std::vector< int > > Sequences
Sequences read_database(std::istream &stream, Format format)
Read one sequence per line, counting duplicate rows as distinct records.
Constraint rel_lq(Gecode::IRT_LQ, Gecode::IPL_DEF)
DistinctWaves distinct_waves
Constraint rel_gq(Gecode::IRT_GQ, Gecode::IPL_DEF)
Group group_precede_disable("Precede", GroupSpace::Kind::PRECEDE, false)
Constraint distinct("Distinct", Constraint::Kind::DISTINCT, 3)
Constraint sum_three("SlidingSum3", Constraint::Kind::SLIDING_SUM, 5, 3)
Constraint sum_two_bnd("SlidingSum2Bnd", Constraint::Kind::SLIDING_SUM, 4, 2, Gecode::IPL_BND)
CallbackLength callback_length
Constraint range_three("SlidingSumRange3", Constraint::Kind::SLIDING_RANGE, 5, 3)
Group group_rel_kill("Rel", GroupSpace::Kind::REL, true)
Constraint sliding_range("SlidingSumRange", Constraint::Kind::SLIDING_RANGE, 4)
Constraint precedence("Precede", Constraint::Kind::PRECEDE, 3)
IncrementalConstraints incremental_constraints
SelectorChoice selector_choice
Group group_precede_kill("Precede", GroupSpace::Kind::PRECEDE, true)
Extremum min_alias(true, true, Gecode::IPL_DOM)
Constraint rel_eq(Gecode::IRT_EQ, Gecode::IPL_BND)
Extremum max_domain(false, false, Gecode::IPL_DOM)
Group group_sum_disable("Sum", GroupSpace::Kind::SUM, false)
Extremum min_result(true, false, Gecode::IPL_BND)
GrowableIntSet growable_int_set
ExtremumBounds extremum_bounds
PatternEnumeration pattern_enumeration
Extremum min_domain(true, false, Gecode::IPL_DOM)
Constraint sliding_one("Sliding1", Constraint::Kind::SLIDING, 3, 1)
Constraint sliding("Sliding", Constraint::Kind::SLIDING, 4)
Extremum max_alias(false, true, Gecode::IPL_DOM)
Group group_rel_disable("Rel", GroupSpace::Kind::REL, false)
Constraint sliding_three("Sliding3", Constraint::Kind::SLIDING, 5, 3)
Group group_sum_kill("Sum", GroupSpace::Kind::SUM, true)
OpenListMaterialize open_list_materialize
Constraint rel_le(Gecode::IRT_LE, Gecode::IPL_DEF)
ImpossibleWindow impossible_window
FixedStatistics fixed_statistics
Constraint sliding_sum("SlidingSum", Constraint::Kind::SLIDING_SUM, 4)
Constraint min_max("MinMax", Constraint::Kind::MIN_MAX, 3)
PatternGrowth pattern_growth
Constraint sum_three_dom("SlidingSum3Dom", Constraint::Kind::SLIDING_SUM, 5, 3, Gecode::IPL_DOM)
Constraint range_one("SlidingSumRange1", Constraint::Kind::SLIDING_RANGE, 3, 1)
Constraint rel_gr(Gecode::IRT_GR, Gecode::IPL_DEF)
Constraint precedence_same("PrecedeSame", Constraint::Kind::PRECEDE_SAME, 3)
Constraint rel_eq_dom(Gecode::IRT_EQ, Gecode::IPL_DOM)
Extremum max_result(false, false, Gecode::IPL_BND)
Constraint rel_nq(Gecode::IRT_NQ, Gecode::IPL_DEF)
Testing finite domain integers.
Definition int.cpp:41
General test support.
Definition afc.cpp:41
AFC afc
Definition afc.cpp:320
@ check
Basic integrity tests.
Definition test.hh:99
#define GECODE_HAS_FLOAT_VARS
Definition config.hpp:75
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56