Generated on Sat Feb 7 2015 02:01:30 for Gecode by doxygen 1.8.9.1
set.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Guido Tack <tack@gecode.org>
5  * Christian Schulte <schulte@gecode.org>
6  * Mikael Lagerkvist <lagerkvist@gecode.org>
7  *
8  * Copyright:
9  * Guido Tack, 2005
10  * Christian Schulte, 2005
11  * Mikael Lagerkvist, 2005
12  *
13  * Last modified:
14  * $Date: 2013-03-05 14:40:46 +0100 (Tue, 05 Mar 2013) $ by $Author: schulte $
15  * $Revision: 13435 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 #include "test/set.hh"
43 
44 #include <algorithm>
45 
46 namespace Test { namespace Set {
47 
48  CountableSet::CountableSet(const Gecode::IntSet& d0) : d(d0), cur(0) {
49  Gecode::IntSetRanges isr(d);
50  lubmax =
51  static_cast<unsigned int>(pow(static_cast<double>(2.0),
52  static_cast<int>(Gecode::Iter::Ranges::size(isr))));
53  }
54 
56  cur++;
57  }
58 
60  d = d0;
61  cur = 0;
62  Gecode::IntSetRanges isr(d);
63  lubmax =
64  static_cast<unsigned int>(pow(static_cast<double>(2.0),
65  static_cast<int>(Gecode::Iter::Ranges::size(isr))));
66  }
67 
68  int CountableSet::val(void) const {
69  return cur;
70  }
71 
72  SetAssignment::SetAssignment(int n0, const Gecode::IntSet& d0, int _withInt)
73  : n(n0), dsv(new CountableSet[n]), ir(_withInt, d0), done(false), lub(d0),
74  withInt(_withInt) {
75  for (int i=n; i--; )
76  dsv[i].init(lub);
77  }
78 
79  void
81  int i = n-1;
82  while (true) {
83  ++dsv[i];
84  if (dsv[i]())
85  return;
86  dsv[i].init(lub);
87  --i;
88  if (i<0) {
89  if (withInt==0) {
90  done = true;
91  return;
92  }
93  ++ir;
94  if (ir()) {
95  i = n-1;
96  for (int j=n; j--; )
97  dsv[j].init(lub);
98  } else {
99  done = true;
100  return;
101  }
102  }
103  }
104  }
105 
106 }}
107 
108 std::ostream&
109 operator<<(std::ostream& os, const Test::Set::SetAssignment& a) {
110  int n = a.size();
111  os << "{";
112  for (int i=0; i<n; i++) {
114  Gecode::IntSet icsv(csv);
115  os << icsv << ((i!=n-1) ? "," : "}");
116  }
117  if (a.withInt > 0)
118  os << a.ints();
119  return os;
120 }
121 
122 namespace Test { namespace Set {
123 
125  SetTest* t, bool log)
126  : d(d0), y(*this, i, d),
127  withInt(i), r(Gecode::BoolVar(*this, 0, 1),Gecode::RM_EQV),
128  reified(false), test(t) {
129  using namespace Gecode;
131  x = SetVarArray(*this, n, Gecode::IntSet::empty, u);
132  SetVarArgs _x(*this, n, Gecode::IntSet::empty, d);
133  if (x.size() == 1)
134  dom(*this,x[0],_x[0]);
135  else
136  dom(*this,x,_x);
137  if (opt.log && log) {
138  olog << ind(2) << "Initial: x[]=" << x;
139  olog << " y[]=" << y;
140  olog << std::endl;
141  }
142  }
143 
145  SetTest* t, Gecode::ReifyMode rm, bool log)
146  : d(d0), x(*this, n, Gecode::IntSet::empty, d), y(*this, i, d),
147  withInt(i), r(Gecode::BoolVar(*this, 0, 1),rm),
148  reified(true), test(t) {
149  if (opt.log && log) {
150  olog << ind(2) << "Initial: x[]=" << x;
151  olog << " y[]=" << y;
152  olog << " b=" << r.var();
153  olog << std::endl;
154  }
155  }
156 
158  : Gecode::Space(share,s), d(s.d), withInt(s.withInt),
159  reified(s.reified), test(s.test) {
160  x.update(*this, share, s.x);
161  y.update(*this, share, s.y);
163  Gecode::BoolVar sr(s.r.var());
164  b.update(*this, share, sr);
165  r.var(b); r.mode(s.r.mode());
166  }
167 
168  Gecode::Space*
169  SetTestSpace::copy(bool share) {
170  return new SetTestSpace(share,*this);
171  }
172 
173  void
175  if (reified){
176  test->post(*this,x,y,r);
177  if (opt.log)
178  olog << ind(3) << "Posting reified propagator" << std::endl;
179  } else {
180  test->post(*this,x,y);
181  if (opt.log)
182  olog << ind(3) << "Posting propagator" << std::endl;
183  }
184  }
185 
186  bool
188  if (opt.log) {
189  olog << ind(3) << "Fixpoint: x[]=" << x
190  << " y[]=" << y << std::endl;
191  bool f=(status() == Gecode::SS_FAILED);
192  olog << ind(3) << " --> x[]=" << x
193  << " y[]=" << y << std::endl;
194  return f;
195  } else {
196  return status() == Gecode::SS_FAILED;
197  }
198  }
199 
200  void
202  if (opt.log) {
203  olog << ind(4) << "x[" << i << "] ";
204  switch (srt) {
205  case Gecode::SRT_EQ: olog << "="; break;
206  case Gecode::SRT_LQ: olog << "<="; break;
207  case Gecode::SRT_LE: olog << "<"; break;
208  case Gecode::SRT_GQ: olog << ">="; break;
209  case Gecode::SRT_GR: olog << ">"; break;
210  case Gecode::SRT_NQ: olog << "!="; break;
211  case Gecode::SRT_SUB: olog << "sub"; break;
212  case Gecode::SRT_SUP: olog << "sup"; break;
213  case Gecode::SRT_DISJ: olog << "||"; break;
214  case Gecode::SRT_CMPL: olog << "^-1 = "; break;
215  }
216  olog << is << std::endl;
217  }
218  Gecode::dom(*this, x[i], srt, is);
219  }
220 
221  void
222  SetTestSpace::cardinality(int i, int cmin, int cmax) {
223  if (opt.log) {
224  olog << ind(4) << cmin << " <= #(x[" << i << "]) <= " << cmax
225  << std::endl;
226  }
227  Gecode::cardinality(*this, x[i], cmin, cmax);
228  }
229 
230  void
232  if (opt.log) {
233  olog << ind(4) << "y[" << i << "] ";
234  switch (irt) {
235  case Gecode::IRT_EQ: olog << "="; break;
236  case Gecode::IRT_NQ: olog << "!="; break;
237  case Gecode::IRT_LQ: olog << "<="; break;
238  case Gecode::IRT_LE: olog << "<"; break;
239  case Gecode::IRT_GQ: olog << ">="; break;
240  case Gecode::IRT_GR: olog << ">"; break;
241  }
242  olog << " " << n << std::endl;
243  }
244  Gecode::rel(*this, y[i], irt, n);
245  }
246 
247  void
248  SetTestSpace::rel(bool sol) {
249  int n = sol ? 1 : 0;
250  assert(reified);
251  if (opt.log)
252  olog << ind(4) << "b = " << n << std::endl;
253  Gecode::rel(*this, r.var(), Gecode::IRT_EQ, n);
254  }
255 
256  void
258  for (int i=a.size(); i--; ) {
259  CountableSetRanges csv(a.lub, a[i]);
260  Gecode::IntSet ai(csv);
261  rel(i, Gecode::SRT_EQ, ai);
262  if (Base::fixpoint() && failed())
263  return;
264  }
265  for (int i=withInt; i--; ) {
266  rel(i, Gecode::IRT_EQ, a.ints()[i]);
267  if (Base::fixpoint() && failed())
268  return;
269  }
270  }
271 
272  bool
274  for (int i=x.size(); i--; )
275  if (!x[i].assigned())
276  return false;
277  for (int i=y.size(); i--; )
278  if (!y[i].assigned())
279  return false;
280  return true;
281  }
282 
283  void
285  using namespace Gecode;
286  SetVarUnknownRanges ur(x[i]);
287  CountableSetRanges air(a.lub, a[i]);
289  CountableSetRanges> diff(ur, air);
291  <Gecode::SetVarUnknownRanges, CountableSetRanges> > diffV(diff);
292  for (int j=0; j<v; j++, ++diffV) {}
293  rel(i, Gecode::SRT_DISJ, Gecode::IntSet(diffV.val(), diffV.val()));
294  }
295 
296  void
298  using namespace Gecode;
299  SetVarUnknownRanges ur(x[i]);
300  CountableSetRanges air(a.lub, a[i]);
302  CountableSetRanges> inter(ur, air);
304  <Gecode::SetVarUnknownRanges, CountableSetRanges> > interV(inter);
305  for (int j=0; j<v; j++, ++interV) {}
306  rel(i, Gecode::SRT_SUP, Gecode::IntSet(interV.val(), interV.val()));
307  }
308 
309  bool
311  if (failed())
312  return true;
313  SetTestSpace* c = static_cast<SetTestSpace*>(clone());
314  if (opt.log)
315  olog << ind(3) << "Testing fixpoint on copy" << std::endl;
316  c->post();
317  if (c->failed()) {
318  delete c; return false;
319  }
320 
321  for (int i=x.size(); i--; )
322  if (x[i].glbSize() != c->x[i].glbSize() ||
323  x[i].lubSize() != c->x[i].lubSize() ||
324  x[i].cardMin() != c->x[i].cardMin() ||
325  x[i].cardMax() != c->x[i].cardMax()) {
326  delete c;
327  return false;
328  }
329  for (int i=y.size(); i--; )
330  if (y[i].size() != c->y[i].size()) {
331  delete c; return false;
332  }
333  if (reified && (r.var().size() != c->r.var().size())) {
334  delete c; return false;
335  }
336  if (opt.log)
337  olog << ind(3) << "Finished testing fixpoint on copy" << std::endl;
338  delete c;
339  return true;
340  }
341 
342  bool
344  using namespace Gecode;
345  bool setsAssigned = true;
346  for (int j=x.size(); j--; )
347  if (!x[j].assigned()) {
348  setsAssigned = false;
349  break;
350  }
351  bool intsAssigned = true;
352  for (int j=y.size(); j--; )
353  if (!y[j].assigned()) {
354  intsAssigned = false;
355  break;
356  }
357 
358  // Select variable to be pruned
359  int i;
360  if (intsAssigned) {
361  i = Base::rand(x.size());
362  } else if (setsAssigned) {
363  i = Base::rand(y.size());
364  } else {
365  i = Base::rand(x.size()+y.size());
366  }
367 
368  if (setsAssigned || i>=x.size()) {
369  if (i>=x.size())
370  i = i-x.size();
371  while (y[i].assigned()) {
372  i = (i+1) % y.size();
373  }
374  // Prune int var
375 
376  // Select mode for pruning
377  switch (Base::rand(3)) {
378  case 0:
379  if (a.ints()[i] < y[i].max()) {
380  int v=a.ints()[i]+1+
381  Base::rand(static_cast<unsigned int>(y[i].max()-a.ints()[i]));
382  assert((v > a.ints()[i]) && (v <= y[i].max()));
383  rel(i, Gecode::IRT_LE, v);
384  }
385  break;
386  case 1:
387  if (a.ints()[i] > y[i].min()) {
388  int v=y[i].min()+
389  Base::rand(static_cast<unsigned int>(a.ints()[i]-y[i].min()));
390  assert((v < a.ints()[i]) && (v >= y[i].min()));
391  rel(i, Gecode::IRT_GR, v);
392  }
393  break;
394  default:
395  int v;
397  unsigned int skip = Base::rand(y[i].size()-1);
398  while (true) {
399  if (it.width() > skip) {
400  v = it.min() + skip;
401  if (v == a.ints()[i]) {
402  if (it.width() == 1) {
403  ++it; v = it.min();
404  } else if (v < it.max()) {
405  ++v;
406  } else {
407  --v;
408  }
409  }
410  break;
411  }
412  skip -= it.width();
413  ++it;
414  }
415  rel(i, Gecode::IRT_NQ, v);
416  }
417  return (!Base::fixpoint() || fixprob());
418  }
419  while (x[i].assigned()) {
420  i = (i+1) % x.size();
421  }
423  CountableSetRanges air1(a.lub, a[i]);
425  CountableSetRanges> diff(ur1, air1);
426  Gecode::SetVarUnknownRanges ur2(x[i]);
427  CountableSetRanges air2(a.lub, a[i]);
428  Gecode::Iter::Ranges::Inter<Gecode::SetVarUnknownRanges,
429  CountableSetRanges> inter(ur2, air2);
430 
431  CountableSetRanges aisizer(a.lub, a[i]);
432  unsigned int aisize = Gecode::Iter::Ranges::size(aisizer);
433 
434  // Select mode for pruning
435  switch (Base::rand(5)) {
436  case 0:
437  if (inter()) {
439  addToGlb(v, i, a);
440  }
441  break;
442  case 1:
443  if (diff()) {
445  removeFromLub(v, i, a);
446  }
447  break;
448  case 2:
449  if (x[i].cardMin() < aisize) {
450  unsigned int newc = x[i].cardMin() + 1 +
451  Base::rand(aisize - x[i].cardMin());
452  assert( newc > x[i].cardMin() );
453  assert( newc <= aisize );
455  }
456  break;
457  case 3:
458  if (x[i].cardMax() > aisize) {
459  unsigned int newc = x[i].cardMax() - 1 -
460  Base::rand(x[i].cardMax() - aisize);
461  assert( newc < x[i].cardMax() );
462  assert( newc >= aisize );
463  cardinality(i, 0, newc);
464  }
465  break;
466  default:
467  if (inter()) {
469  addToGlb(v, i, a);
470  } else {
472  removeFromLub(v, i, a);
473  }
474  }
475  return (!Base::fixpoint() || fixprob());
476  }
477 
478 
480 #define CHECK_TEST(T,M) \
481 if (opt.log) \
482  olog << ind(3) << "Check: " << (M) << std::endl; \
483 if (!(T)) { \
484  problem = (M); delete s; goto failed; \
485 }
486 
488 #define START_TEST(T) \
489  if (opt.log) { \
490  olog.str(""); \
491  olog << ind(2) << "Testing: " << (T) << std::endl; \
492  } \
493  test = (T);
494 
495  bool
496  SetTest::run(void) {
497  using namespace Gecode;
498  const char* test = "NONE";
499  const char* problem = "NONE";
500 
501  SetAssignment* ap = new SetAssignment(arity,lub,withInt);
502  SetAssignment& a = *ap;
503  while (a()) {
504  bool is_sol = solution(a);
505  if (opt.log)
506  olog << ind(1) << "Assignment: " << a
507  << (is_sol ? " (solution)" : " (no solution)")
508  << std::endl;
509 
510  START_TEST("Assignment (after posting)");
511  {
512  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this);
513  SetTestSpace* sc = NULL;
514  s->post();
515  switch (Base::rand(3)) {
516  case 0:
517  if (opt.log)
518  olog << ind(3) << "No copy" << std::endl;
519  sc = s;
520  s = NULL;
521  break;
522  case 1:
523  if (opt.log)
524  olog << ind(3) << "Unshared copy" << std::endl;
525  if (s->status() != Gecode::SS_FAILED) {
526  sc = static_cast<SetTestSpace*>(s->clone(true));
527  } else {
528  sc = s; s = NULL;
529  }
530  break;
531  case 2:
532  if (opt.log)
533  olog << ind(3) << "Unshared copy" << std::endl;
534  if (s->status() != Gecode::SS_FAILED) {
535  sc = static_cast<SetTestSpace*>(s->clone(false));
536  } else {
537  sc = s; s = NULL;
538  }
539  break;
540  default: assert(false);
541  }
542  sc->assign(a);
543  if (is_sol) {
544  CHECK_TEST(!sc->failed(), "Failed on solution");
545  CHECK_TEST(sc->propagators()==0, "No subsumption");
546  } else {
547  CHECK_TEST(sc->failed(), "Solved on non-solution");
548  }
549  delete s; delete sc;
550  }
551  START_TEST("Assignment (before posting)");
552  {
553  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this);
554  s->assign(a);
555  s->post();
556  if (is_sol) {
557  CHECK_TEST(!s->failed(), "Failed on solution");
558  CHECK_TEST(s->propagators()==0, "No subsumption");
559  } else {
560  CHECK_TEST(s->failed(), "Solved on non-solution");
561  }
562  delete s;
563  }
564  START_TEST("Prune");
565  {
566  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this);
567  s->post();
568  while (!s->failed() && !s->assigned())
569  if (!s->prune(a)) {
570  problem = "No fixpoint";
571  delete s;
572  goto failed;
573  }
574  s->assign(a);
575  if (is_sol) {
576  CHECK_TEST(!s->failed(), "Failed on solution");
577  CHECK_TEST(s->propagators()==0, "No subsumption");
578  } else {
579  CHECK_TEST(s->failed(), "Solved on non-solution");
580  }
581  delete s;
582  }
583 
584  if (reified) {
585  START_TEST("Assignment reified (rewrite after post, <=>)");
586  {
587  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_EQV);
588  s->post();
589  s->rel(is_sol);
590  s->assign(a);
591  CHECK_TEST(!s->failed(), "Failed");
592  CHECK_TEST(s->propagators()==0, "No subsumption");
593  delete s;
594  }
595  START_TEST("Assignment reified (rewrite after post, =>)");
596  {
597  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_IMP);
598  s->post();
599  s->rel(is_sol);
600  s->assign(a);
601  CHECK_TEST(!s->failed(), "Failed");
602  CHECK_TEST(s->propagators()==0, "No subsumption");
603  delete s;
604  }
605  START_TEST("Assignment reified (rewrite after post, <=)");
606  {
607  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_PMI);
608  s->post();
609  s->rel(is_sol);
610  s->assign(a);
611  CHECK_TEST(!s->failed(), "Failed");
612  CHECK_TEST(s->propagators()==0, "No subsumption");
613  delete s;
614  }
615  {
616  START_TEST("Assignment reified (rewrite failure, <=>)");
617  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_EQV);
618  s->post();
619  s->rel(!is_sol);
620  s->assign(a);
621  CHECK_TEST(s->failed(), "Not failed");
622  delete s;
623  }
624  {
625  START_TEST("Assignment reified (rewrite failure, =>)");
626  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_IMP);
627  s->post();
628  s->rel(!is_sol);
629  s->assign(a);
630  if (is_sol) {
631  CHECK_TEST(!s->failed(), "Failed");
632  CHECK_TEST(s->propagators()==0, "No subsumption");
633  } else {
634  CHECK_TEST(s->failed(), "Not failed");
635  }
636  delete s;
637  }
638  {
639  START_TEST("Assignment reified (rewrite failure, <=)");
640  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_PMI);
641  s->post();
642  s->rel(!is_sol);
643  s->assign(a);
644  if (is_sol) {
645  CHECK_TEST(s->failed(), "Not failed");
646  } else {
647  CHECK_TEST(!s->failed(), "Failed");
648  CHECK_TEST(s->propagators()==0, "No subsumption");
649  }
650  delete s;
651  }
652  START_TEST("Assignment reified (immediate rewrite, <=>)");
653  {
654  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_EQV);
655  s->rel(is_sol);
656  s->post();
657  s->assign(a);
658  CHECK_TEST(!s->failed(), "Failed");
659  CHECK_TEST(s->propagators()==0, "No subsumption");
660  delete s;
661  }
662  START_TEST("Assignment reified (immediate rewrite, =>)");
663  {
664  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_IMP);
665  s->rel(is_sol);
666  s->post();
667  s->assign(a);
668  CHECK_TEST(!s->failed(), "Failed");
669  CHECK_TEST(s->propagators()==0, "No subsumption");
670  delete s;
671  }
672  START_TEST("Assignment reified (immediate rewrite, <=)");
673  {
674  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_PMI);
675  s->rel(is_sol);
676  s->post();
677  s->assign(a);
678  CHECK_TEST(!s->failed(), "Failed");
679  CHECK_TEST(s->propagators()==0, "No subsumption");
680  delete s;
681  }
682  START_TEST("Assignment reified (immediate failure, <=>)");
683  {
684  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_EQV);
685  s->rel(!is_sol);
686  s->post();
687  s->assign(a);
688  CHECK_TEST(s->failed(), "Not failed");
689  delete s;
690  }
691  START_TEST("Assignment reified (immediate failure, =>)");
692  {
693  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_IMP);
694  s->rel(!is_sol);
695  s->post();
696  s->assign(a);
697  if (is_sol) {
698  CHECK_TEST(!s->failed(), "Failed");
699  CHECK_TEST(s->propagators()==0, "No subsumption");
700  } else {
701  CHECK_TEST(s->failed(), "Not failed");
702  }
703  delete s;
704  }
705  START_TEST("Assignment reified (immediate failure, <=)");
706  {
707  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_PMI);
708  s->rel(!is_sol);
709  s->post();
710  s->assign(a);
711  if (is_sol) {
712  CHECK_TEST(s->failed(), "Not failed");
713  } else {
714  CHECK_TEST(!s->failed(), "Failed");
715  CHECK_TEST(s->propagators()==0, "No subsumption");
716  }
717  delete s;
718  }
719  START_TEST("Assignment reified (before posting, <=>)");
720  {
721  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_EQV);
722  s->assign(a);
723  s->post();
724  CHECK_TEST(!s->failed(), "Failed");
725  CHECK_TEST(s->propagators()==0, "No subsumption");
726  CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
727  if (is_sol) {
728  CHECK_TEST(s->r.var().val()==1, "Zero on solution");
729  } else {
730  CHECK_TEST(s->r.var().val()==0, "One on non-solution");
731  }
732  delete s;
733  }
734  START_TEST("Assignment reified (before posting, =>)");
735  {
736  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_IMP);
737  s->assign(a);
738  s->post();
739  CHECK_TEST(!s->failed(), "Failed");
740  CHECK_TEST(s->propagators()==0, "No subsumption");
741  if (is_sol) {
742  CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
743  } else {
744  CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
745  CHECK_TEST(s->r.var().val()==0, "One on non-solution");
746  }
747  delete s;
748  }
749  START_TEST("Assignment reified (before posting, <=)");
750  {
751  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_PMI);
752  s->assign(a);
753  s->post();
754  CHECK_TEST(!s->failed(), "Failed");
755  CHECK_TEST(s->propagators()==0, "No subsumption");
756  if (is_sol) {
757  CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
758  CHECK_TEST(s->r.var().val()==1, "Zero on solution");
759  } else {
760  CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
761  }
762  delete s;
763  }
764  START_TEST("Assignment reified (after posting, <=>)");
765  {
766  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_EQV);
767  s->post();
768  s->assign(a);
769  CHECK_TEST(!s->failed(), "Failed");
770  CHECK_TEST(s->propagators()==0, "No subsumption");
771  CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
772  if (is_sol) {
773  CHECK_TEST(s->r.var().val()==1, "Zero on solution");
774  } else {
775  CHECK_TEST(s->r.var().val()==0, "One on non-solution");
776  }
777  delete s;
778  }
779  START_TEST("Assignment reified (after posting, =>)");
780  {
781  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_IMP);
782  s->post();
783  s->assign(a);
784  CHECK_TEST(!s->failed(), "Failed");
785  CHECK_TEST(s->propagators()==0, "No subsumption");
786  if (is_sol) {
787  CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
788  } else {
789  CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
790  CHECK_TEST(s->r.var().val()==0, "One on non-solution");
791  }
792  delete s;
793  }
794  START_TEST("Assignment reified (after posting, <=)");
795  {
796  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_PMI);
797  s->post();
798  s->assign(a);
799  CHECK_TEST(!s->failed(), "Failed");
800  CHECK_TEST(s->propagators()==0, "No subsumption");
801  if (is_sol) {
802  CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
803  CHECK_TEST(s->r.var().val()==1, "Zero on solution");
804  } else {
805  CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
806  }
807  delete s;
808  }
809  START_TEST("Prune reified, <=>");
810  {
811  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_EQV);
812  s->post();
813  while (!s->failed() &&
814  (!s->assigned() || !s->r.var().assigned()))
815  if (!s->prune(a)) {
816  problem = "No fixpoint";
817  delete s;
818  goto failed;
819  }
820  CHECK_TEST(!s->failed(), "Failed");
821  CHECK_TEST(s->propagators()==0, "No subsumption");
822  CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
823  if (is_sol) {
824  CHECK_TEST(s->r.var().val()==1, "Zero on solution");
825  } else {
826  CHECK_TEST(s->r.var().val()==0, "One on non-solution");
827  }
828  delete s;
829  }
830  START_TEST("Prune reified, =>");
831  {
832  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_IMP);
833  s->post();
834  while (!s->failed() &&
835  (!s->assigned() || (!is_sol && !s->r.var().assigned())))
836  if (!s->prune(a)) {
837  problem = "No fixpoint";
838  delete s;
839  goto failed;
840  }
841  CHECK_TEST(!s->failed(), "Failed");
842  CHECK_TEST(s->propagators()==0, "No subsumption");
843  if (is_sol) {
844  CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
845  } else {
846  CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
847  CHECK_TEST(s->r.var().val()==0, "One on non-solution");
848  }
849  delete s;
850  }
851  START_TEST("Prune reified, <=");
852  {
853  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,this,RM_PMI);
854  s->post();
855  while (!s->failed() &&
856  (!s->assigned() || (is_sol && !s->r.var().assigned())))
857  if (!s->prune(a)) {
858  problem = "No fixpoint";
859  delete s;
860  goto failed;
861  }
862  CHECK_TEST(!s->failed(), "Failed");
863  CHECK_TEST(s->propagators()==0, "No subsumption");
864  if (is_sol) {
865  CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
866  CHECK_TEST(s->r.var().val()==1, "Zero on solution");
867  } else {
868  CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
869  }
870  delete s;
871  }
872  }
873  ++a;
874  }
875  delete ap;
876  return true;
877  failed:
878  if (opt.log)
879  olog << "FAILURE" << std::endl
880  << ind(1) << "Test: " << test << std::endl
881  << ind(1) << "Problem: " << problem << std::endl;
882  if (a() && opt.log)
883  olog << ind(1) << "Assignment: " << a << std::endl;
884  delete ap;
885 
886  return false;
887  }
888 
889  const Gecode::SetRelType SetRelTypes::srts[] =
892 
893  const Gecode::SetOpType SetOpTypes::sots[] =
896 
897 }}
898 
899 #undef START_TEST
900 #undef CHECK_TEST
901 
902 // STATISTICS: test-set
void removeFromLub(int v, int i, const SetAssignment &a)
Remove value v from the upper bound of x[i].
Definition: set.cpp:284
void operator++(void)
Move to next subset.
Definition: set.cpp:55
void cardinality(int i, int cmin, int cmax)
Perform cardinality tell operation on x[i].
Definition: set.cpp:222
NodeType t
Type of node.
Definition: bool-expr.cpp:234
SetRelType
Common relation types for sets.
Definition: set.hh:644
int size(void) const
Return arity.
Definition: set.hh:189
Inverse implication for reification.
Definition: int.hh:847
ReifyMode mode(void) const
Return reification mode.
Definition: reify.hpp:60
Simple class for describing identation.
Definition: test.hh:70
Gecode::Reify r
Reification information.
Definition: set.hh:209
const int min
Smallest allowed integer in integer set.
Definition: set.hh:101
Range iterator for integer sets.
Definition: int.hh:271
void log(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:151
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
BoolVar var(void) const
Return Boolean control variable.
Definition: reify.hpp:52
void update(Space &home, bool share, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition: var.hpp:128
static Gecode::Support::RandomGenerator rand
Random number generator.
Definition: test.hh:138
Gecode::SetVarArray x
Set variables to be tested.
Definition: set.hh:203
Space * clone(bool share=true, CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:2854
void assign(const SetAssignment &a)
Assign all variables to values in a.
Definition: set.cpp:257
Less or equal ( )
Definition: int.hh:906
int val(void) const
Return current subset.
Definition: set.cpp:68
void pow(Home home, FloatVar x0, int n, FloatVar x1)
Post propagator for for $n 0$.
Definition: arithmetic.cpp:117
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: bool.hpp:85
CountableSet(void)
Default constructor.
Definition: set.hh:146
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:44
SetOpType
Common operations for sets.
Definition: set.hh:661
Greater ( )
Definition: int.hh:909
Superset ( )
Definition: set.hh:648
Complement.
Definition: set.hh:650
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:103
SetAssignment(int n, const Gecode::IntSet &d, int i=0)
Initialize with n set variables, initial bound d and i int variables.
Definition: set.cpp:72
const int max
Largest allowed integer in integer set.
Definition: set.hh:99
Computation spaces.
Definition: core.hpp:1362
Greater or equal ( )
Definition: int.hh:908
Difference.
Definition: set.hh:665
int val(void) const
Return assigned value.
Definition: bool.hpp:61
ChannelShared csv(Gecode::ICL_VAL)
Iterator for the unknown ranges of a set variable.
Definition: set.hh:336
Gecode::IntSet d(v, 7)
bool reified
Whether the test is for a reified propagator.
Definition: set.hh:211
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1072
void rel(int i, Gecode::SetRelType srt, const Gecode::IntSet &is)
Perform set tell operation on x[i].
Definition: set.cpp:201
unsigned int propagators(void) const
Return number of propagators.
Definition: core.cpp:196
const FloatNum min
Smallest allowed float value.
Definition: float.hh:833
int min(void) const
Return smallest value of range.
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Equality ( )
Definition: int.hh:904
bool assigned(void) const
Test whether all variables are assigned.
Definition: set.cpp:273
Options opt
The options.
Definition: test.cpp:101
IntRelType
Relation types for integers.
Definition: int.hh:903
Range iterator for computing intersection (binary)
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
const Test::Int::Assignment & ints(void) const
Return assignment for integer variables.
Definition: set.hh:187
Less or equal ( )
Definition: set.hh:651
static bool fixpoint(void)
Throw a coin whether to compute a fixpoint.
Definition: test.hpp:70
void post(void)
Post propagator.
Definition: set.cpp:174
bool failed(void)
Compute a fixpoint and check for failure.
Definition: set.cpp:187
Value iterator from range iterator.
unsigned int size(I &i)
Size of all ranges of range iterator i.
Subset ( )
Definition: set.hh:647
virtual bool run(void)
Perform test.
Definition: set.cpp:496
bool log
Whether to log the tests.
Definition: test.hh:95
Gecode::IntSet lub
The common superset for all domains.
Definition: set.hh:170
Intersection
Definition: set.hh:664
Less ( )
Definition: int.hh:907
Integer sets.
Definition: int.hh:171
Less ( )
Definition: set.hh:652
#define START_TEST(T)
Start new test.
Definition: set.cpp:488
struct Gecode::Space::@52::@54 c
Data available only during copying.
static const IntSet empty
Empty set.
Definition: int.hh:262
Gecode::IntSet d
Initial domain.
Definition: set.hh:201
SetTestSpace(int n, Gecode::IntSet &d0, int i, SetTest *t, bool log=true)
Create test space without reification.
Definition: set.cpp:124
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Boolean integer variables.
Definition: int.hh:491
LinIntExpr cardinality(const SetExpr &e)
Cardinality of set expression.
Definition: set-expr.cpp:815
SetExpr inter(const SetVarArgs &x)
Intersection of set variables.
Definition: set-expr.cpp:696
union Gecode::@518::NNF::@57 u
Union depending on nodetype t.
const int v[7]
Definition: distinct.cpp:207
bool prune(const SetAssignment &a)
Perform random pruning.
Definition: set.cpp:343
General test support.
Definition: afc.cpp:43
Union.
Definition: set.hh:662
Passing set variables.
Definition: set.hh:490
Greater or equal ( )
Definition: set.hh:653
int withInt
How many integer variables to iterate.
Definition: set.hh:172
void addToGlb(int v, int i, const SetAssignment &a)
Remove value v from the lower bound of x[i].
Definition: set.cpp:297
virtual void post(Gecode::Space &home, Gecode::SetVarArray &x, Gecode::IntVarArray &y)=0
Post propagator.
Disjoint union.
Definition: set.hh:663
Base class for tests with set constraints
Definition: set.hh:271
Generate all set assignments.
Definition: set.hh:158
void operator++(void)
Move to next assignment.
Definition: set.cpp:80
bool fixprob(void)
Perform fixpoint computation.
Definition: set.cpp:310
std::ostringstream olog
Stream used for logging.
Definition: test.cpp:57
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
Gecode::IntVarArray y
Int variables to be tested.
Definition: set.hh:205
Range iterator producing subsets of an IntSet.
Definition: set.hh:114
Greater ( )
Definition: set.hh:654
Equality ( )
Definition: set.hh:645
Disjoint ( )
Definition: set.hh:649
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:252
int withInt
How many integer variables are used by the test.
Definition: set.hh:207
bool assigned(void) const
Test whether view is assigned.
Definition: var.hpp:123
Set variable array
Definition: set.hh:571
Disequality ( )
Definition: set.hh:646
int max(void) const
Return largest value of range.
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
Implication for reification.
Definition: int.hh:840
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const FloatView &x)
Print float variable view.
Definition: print.hpp:62
Range iterator for computing set difference.
Definition: ranges-diff.hpp:47
Disequality ( )
Definition: int.hh:905
#define CHECK_TEST(T, M)
Check the test result and handle failed test.
Definition: set.cpp:480
SetTest * test
The test currently run.
Definition: set.hh:213
Space is failed
Definition: core.hpp:1301
Space for executing set tests.
Definition: set.hh:198
Iterate all subsets of a given set.
Definition: set.hh:134
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:985
ReifyMode
Mode for reification.
Definition: int.hh:826
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
virtual Gecode::Space * copy(bool share)
Copy space during cloning.
Definition: set.cpp:169
void init(const Gecode::IntSet &s)
Initialize with set s.
Definition: set.cpp:59
Equivalence for reification (default)
Definition: int.hh:833