Generated on Fri Jan 28 2022 04:43:06 for Gecode by doxygen 1.8.13
int.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  * Mikael Lagerkvist <lagerkvist@gecode.org>
6  *
7  * Copyright:
8  * Christian Schulte, 2005
9  * Mikael Lagerkvist, 2005
10  *
11  * This file is part of Gecode, the generic constraint
12  * development environment:
13  * http://www.gecode.org
14  *
15  * Permission is hereby granted, free of charge, to any person obtaining
16  * a copy of this software and associated documentation files (the
17  * "Software"), to deal in the Software without restriction, including
18  * without limitation the rights to use, copy, modify, merge, publish,
19  * distribute, sublicense, and/or sell copies of the Software, and to
20  * permit persons to whom the Software is furnished to do so, subject to
21  * the following conditions:
22  *
23  * The above copyright notice and this permission notice shall be
24  * included in all copies or substantial portions of the Software.
25  *
26  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33  *
34  */
35 
36 #include "test/int.hh"
37 
38 #include <algorithm>
39 
40 namespace Test { namespace Int {
41 
42 
43  /*
44  * Complete assignments
45  *
46  */
47  void
49  int i = n-1;
50  while (true) {
51  ++dsv[i];
52  if (dsv[i]() || (i == 0))
53  return;
54  dsv[i--].init(d);
55  }
56  }
57 
58  /*
59  * Random assignments
60  *
61  */
62  void
64  for (int i = n; i--; )
65  vals[i]=randval();
66  a--;
67  }
68 
69  void
71  for (int i=n-_n1; i--; )
72  vals[i] = randval(d);
73  for (int i=_n1; i--; )
74  vals[n-_n1+i] = randval(_d1);
75  a--;
76  }
77 
78 }}
79 
80 std::ostream&
81 operator<<(std::ostream& os, const Test::Int::Assignment& a) {
82  int n = a.size();
83  os << "{";
84  for (int i=0; i<n; i++)
85  os << a[i] << ((i!=n-1) ? "," : "}");
86  return os;
87 }
88 
89 namespace Test { namespace Int {
90 
92  : d(d0), x(*this,n,Gecode::Int::Limits::min,Gecode::Int::Limits::max),
93  test(t), reified(false) {
94  Gecode::IntVarArgs _x(*this,n,d);
95  if (x.size() == 1)
96  Gecode::dom(*this,x[0],_x[0]);
97  else
98  Gecode::dom(*this,x,_x);
99  Gecode::BoolVar b(*this,0,1);
101  if (opt.log)
102  olog << ind(2) << "Initial: x[]=" << x
103  << std::endl;
104  }
105 
108  : d(d0), x(*this,n,Gecode::Int::Limits::min,Gecode::Int::Limits::max),
109  test(t), reified(true) {
110  Gecode::IntVarArgs _x(*this,n,d);
111  if (x.size() == 1)
112  Gecode::dom(*this,x[0],_x[0]);
113  else
114  Gecode::dom(*this,x,_x);
115  Gecode::BoolVar b(*this,0,1);
116  r = Gecode::Reify(b,rm);
117  if (opt.log)
118  olog << ind(2) << "Initial: x[]=" << x
119  << " b=" << r.var() << std::endl;
120  }
121 
123  : Gecode::Space(s), d(s.d), test(s.test), reified(s.reified) {
124  x.update(*this, s.x);
126  Gecode::BoolVar sr(s.r.var());
127  b.update(*this, sr);
128  r.var(b); r.mode(s.r.mode());
129  }
130 
133  return new TestSpace(*this);
134  }
135 
136  bool
137  TestSpace::assigned(void) const {
138  for (int i=x.size(); i--; )
139  if (!x[i].assigned())
140  return false;
141  return true;
142  }
143 
144  void
146  if (reified){
147  test->post(*this,x,r);
148  if (opt.log)
149  olog << ind(3) << "Posting reified propagator" << std::endl;
150  } else {
151  test->post(*this,x);
152  if (opt.log)
153  olog << ind(3) << "Posting propagator" << std::endl;
154  }
155  }
156 
157  bool
159  if (opt.log) {
160  olog << ind(3) << "Fixpoint: " << x;
161  bool f=(status() == Gecode::SS_FAILED);
162  olog << std::endl << ind(3) << " --> " << x << std::endl;
163  return f;
164  } else {
165  return status() == Gecode::SS_FAILED;
166  }
167  }
168 
169  int
171  assert(!assigned());
172  // Select variable to be pruned
173  int i = Base::rand(x.size());
174  while (x[i].assigned()) {
175  i = (i+1) % x.size();
176  }
177  return i;
178  }
179 
180  void
182  Gecode::IntRelType& irt, int& v) {
183  using namespace Gecode;
184  // Select mode for pruning
185  irt = IRT_EQ; // Means do nothing!
186  switch (Base::rand(3)) {
187  case 0:
188  if (a[i] < x[i].max()) {
189  v=a[i]+1+Base::rand(static_cast
190  <unsigned int>(x[i].max()-a[i]));
191  assert((v > a[i]) && (v <= x[i].max()));
192  irt = IRT_LE;
193  }
194  break;
195  case 1:
196  if (a[i] > x[i].min()) {
197  v=x[i].min()+Base::rand(static_cast
198  <unsigned int>(a[i]-x[i].min()));
199  assert((v < a[i]) && (v >= x[i].min()));
200  irt = IRT_GR;
201  }
202  break;
203  default:
204  {
206  unsigned int skip = Base::rand(x[i].size()-1);
207  while (true) {
208  if (it.width() > skip) {
209  v = it.min() + skip;
210  if (v == a[i]) {
211  if (it.width() == 1) {
212  ++it; v = it.min();
213  } else if (v < it.max()) {
214  ++v;
215  } else {
216  --v;
217  }
218  }
219  break;
220  }
221  skip -= it.width(); ++it;
222  }
223  irt = IRT_NQ;
224  break;
225  }
226  }
227  }
228 
229  void
231  if (opt.log) {
232  olog << ind(4) << "x[" << i << "] ";
233  switch (irt) {
234  case Gecode::IRT_EQ: olog << "="; break;
235  case Gecode::IRT_NQ: olog << "!="; break;
236  case Gecode::IRT_LQ: olog << "<="; break;
237  case Gecode::IRT_LE: olog << "<"; break;
238  case Gecode::IRT_GQ: olog << ">="; break;
239  case Gecode::IRT_GR: olog << ">"; break;
240  }
241  olog << " " << n << std::endl;
242  }
243  Gecode::rel(*this, x[i], irt, n);
244  }
245 
246  void
247  TestSpace::rel(bool sol) {
248  int n = sol ? 1 : 0;
249  assert(reified);
250  if (opt.log)
251  olog << ind(4) << "b = " << n << std::endl;
252  Gecode::rel(*this, r.var(), Gecode::IRT_EQ, n);
253  }
254 
255  void
256  TestSpace::assign(const Assignment& a, bool skip) {
257  using namespace Gecode;
258  int i = skip ? static_cast<int>(Base::rand(a.size())) : -1;
259  for (int j=a.size(); j--; )
260  if (i != j) {
261  rel(j, IRT_EQ, a[j]);
262  if (Base::fixpoint() && failed())
263  return;
264  }
265  }
266 
267  void
269  using namespace Gecode;
270  int i = rndvar();
271  bool min = Base::rand(2);
272  rel(i, IRT_EQ, min ? x[i].min() : x[i].max());
273  }
274 
275  void
276  TestSpace::prune(int i, bool bounds_only) {
277  using namespace Gecode;
278  // Prune values
279  if (bounds_only) {
280  if (Base::rand(2) && !x[i].assigned()) {
281  int v=x[i].min()+1+Base::rand(static_cast
282  <unsigned int>(x[i].max()-x[i].min()));
283  assert((v > x[i].min()) && (v <= x[i].max()));
284  rel(i, Gecode::IRT_LE, v);
285  }
286  if (Base::rand(2) && !x[i].assigned()) {
287  int v=x[i].min()+Base::rand(static_cast
288  <unsigned int>(x[i].max()-x[i].min()));
289  assert((v < x[i].max()) && (v >= x[i].min()));
290  rel(i, Gecode::IRT_GR, v);
291  }
292  } else {
293  for (int vals = Base::rand(x[i].size()-1)+1; vals--; ) {
294  int v;
296  unsigned int skip = Base::rand(x[i].size()-1);
297  while (true) {
298  if (it.width() > skip) {
299  v = it.min() + skip; break;
300  }
301  skip -= it.width(); ++it;
302  }
303  rel(i, IRT_NQ, v);
304  }
305  }
306  }
307 
308  void
310  prune(rndvar(), false);
311  }
312 
313  bool
314  TestSpace::prune(const Assignment& a, bool testfix) {
315  using namespace Gecode;
316  // Select variable to be pruned
317  int i = rndvar();
318  // Select mode for pruning
319  IntRelType irt;
320  int v;
321  rndrel(a,i,irt,v);
322  if (irt != IRT_EQ)
323  rel(i, irt, v);
324  if (Base::fixpoint()) {
325  if (failed() || !testfix)
326  return true;
327  TestSpace* c = static_cast<TestSpace*>(clone());
328  if (opt.log)
329  olog << ind(3) << "Testing fixpoint on copy" << std::endl;
330  c->post();
331  if (c->failed()) {
332  if (opt.log)
333  olog << ind(4) << "Copy failed after posting" << std::endl;
334  delete c; return false;
335  }
336  for (int i=x.size(); i--; )
337  if (x[i].size() != c->x[i].size()) {
338  if (opt.log)
339  olog << ind(4) << "Different domain size" << std::endl;
340  delete c; return false;
341  }
342  if (reified && (r.var().size() != c->r.var().size())) {
343  if (opt.log)
344  olog << ind(4) << "Different control variable" << std::endl;
345  delete c; return false;
346  }
347  if (opt.log)
348  olog << ind(3) << "Finished testing fixpoint on copy" << std::endl;
349  delete c;
350  }
351  return true;
352  }
353 
354  void
357  }
358 
359  void
362  (void) status();
363  }
364 
365  bool
367  bool testfix) {
368  using namespace Gecode;
369  // Disable propagators
370  c.disable();
371  // Select variable to be pruned
372  int i = rndvar();
373  // Select mode for pruning
374  IntRelType irt;
375  int v;
376  rndrel(a,i,irt,v);
377  if (irt != IRT_EQ) {
378  rel(i, irt, v);
379  c.rel(i, irt, v);
380  }
381  // Enable propagators
382  c.enable();
383  if (!testfix)
384  return true;
385  if (failed()) {
386  if (!c.failed()) {
387  if (opt.log)
388  olog << ind(3) << "No failure on disabled copy" << std::endl;
389  return false;
390  }
391  return true;
392  }
393  if (c.failed()) {
394  if (opt.log)
395  olog << ind(3) << "Failure on disabled copy" << std::endl;
396  return false;
397  }
398  for (int i=x.size(); i--; ) {
399  if (x[i].size() != c.x[i].size()) {
400  if (opt.log)
401  olog << ind(4) << "Different domain size" << std::endl;
402  return false;
403  }
404  if (reified && (r.var().size() != c.r.var().size())) {
405  if (opt.log)
406  olog << ind(4) << "Different control variable" << std::endl;
407  return false;
408  }
409  }
410  return true;
411  }
412 
413  unsigned int
415  return Gecode::PropagatorGroup::all.size(*this);
416  }
417 
418  const Gecode::IntPropLevel IntPropLevels::ipls[] =
420 
421  const Gecode::IntPropLevel IntPropBasicAdvanced::ipls[] =
423 
424  const Gecode::IntRelType IntRelTypes::irts[] =
427 
428  const Gecode::BoolOpType BoolOpTypes::bots[] =
431 
432  Assignment*
433  Test::assignment(void) const {
434  return new CpltAssignment(arity,dom);
435  }
436 
437 
439 #define CHECK_TEST(T,M) \
440 if (opt.log) \
441  olog << ind(3) << "Check: " << (M) << std::endl; \
442 if (!(T)) { \
443  problem = (M); delete s; goto failed; \
444 }
445 
447 #define START_TEST(T) \
448  if (opt.log) { \
449  olog.str(""); \
450  olog << ind(2) << "Testing: " << (T) << std::endl; \
451  } \
452  test = (T);
453 
454  bool
455  Test::ignore(const Assignment&) const {
456  return false;
457  }
458 
459  void
461  Gecode::Reify) {}
462 
463  bool
464  Test::run(void) {
465  using namespace Gecode;
466  const char* test = "NONE";
467  const char* problem = "NONE";
468 
469  // Set up assignments
470  Assignment* ap = assignment();
471  Assignment& a = *ap;
472 
473  // Set up space for all solution search
474  TestSpace* search_s = new TestSpace(arity,dom,this);
475  post(*search_s,search_s->x);
476  branch(*search_s,search_s->x,INT_VAR_NONE(),INT_VAL_MIN());
477  Search::Options search_o;
478  search_o.threads = 1;
479  DFS<TestSpace> e_s(search_s,search_o);
480  delete search_s;
481 
482  while (a()) {
483  bool sol = solution(a);
484  if (opt.log) {
485  olog << ind(1) << "Assignment: " << a
486  << (sol ? " (solution)" : " (no solution)")
487  << std::endl;
488  }
489 
490  START_TEST("Assignment (after posting)");
491  {
492  TestSpace* s = new TestSpace(arity,dom,this);
493  TestSpace* sc = NULL;
494  s->post();
495  switch (Base::rand(2)) {
496  case 0:
497  if (opt.log)
498  olog << ind(3) << "No copy" << std::endl;
499  sc = s;
500  s = NULL;
501  break;
502  case 1:
503  if (opt.log)
504  olog << ind(3) << "Copy" << std::endl;
505  if (s->status() != SS_FAILED) {
506  sc = static_cast<TestSpace*>(s->clone());
507  } else {
508  sc = s; s = NULL;
509  }
510  break;
511  default: assert(false);
512  }
513  sc->assign(a);
514  if (sol) {
515  CHECK_TEST(!sc->failed(), "Failed on solution");
516  CHECK_TEST(sc->propagators()==0, "No subsumption");
517  } else {
518  CHECK_TEST(sc->failed(), "Solved on non-solution");
519  }
520  delete s; delete sc;
521  }
522  START_TEST("Partial assignment (after posting)");
523  {
524  TestSpace* s = new TestSpace(arity,dom,this);
525  s->post();
526  s->assign(a,true);
527  (void) s->failed();
528  s->assign(a);
529  if (sol) {
530  CHECK_TEST(!s->failed(), "Failed on solution");
531  CHECK_TEST(s->propagators()==0, "No subsumption");
532  } else {
533  CHECK_TEST(s->failed(), "Solved on non-solution");
534  }
535  delete s;
536  }
537  START_TEST("Assignment (after posting, disable)");
538  {
539  TestSpace* s = new TestSpace(arity,dom,this);
540  s->post();
541  s->disable();
542  s->assign(a);
543  s->enable();
544  if (sol) {
545  CHECK_TEST(!s->failed(), "Failed on solution");
546  CHECK_TEST(s->propagators()==0, "No subsumption");
547  } else {
548  CHECK_TEST(s->failed(), "Solved on non-solution");
549  }
550  delete s;
551  }
552  START_TEST("Partial assignment (after posting, disable)");
553  {
554  TestSpace* s = new TestSpace(arity,dom,this);
555  s->post();
556  s->assign(a,true);
557  s->disable();
558  (void) s->failed();
559  s->assign(a);
560  s->enable();
561  if (sol) {
562  CHECK_TEST(!s->failed(), "Failed on solution");
563  CHECK_TEST(s->propagators()==0, "No subsumption");
564  } else {
565  CHECK_TEST(s->failed(), "Solved on non-solution");
566  }
567  delete s;
568  }
569  START_TEST("Assignment (before posting)");
570  {
571  TestSpace* s = new TestSpace(arity,dom,this);
572  s->assign(a);
573  s->post();
574  if (sol) {
575  CHECK_TEST(!s->failed(), "Failed on solution");
576  CHECK_TEST(s->propagators()==0, "No subsumption");
577  } else {
578  CHECK_TEST(s->failed(), "Solved on non-solution");
579  }
580  delete s;
581  }
582  START_TEST("Partial assignment (before posting)");
583  {
584  TestSpace* s = new TestSpace(arity,dom,this);
585  s->assign(a,true);
586  s->post();
587  (void) s->failed();
588  s->assign(a);
589  if (sol) {
590  CHECK_TEST(!s->failed(), "Failed on solution");
591  CHECK_TEST(s->propagators()==0, "No subsumption");
592  } else {
593  CHECK_TEST(s->failed(), "Solved on non-solution");
594  }
595  delete s;
596  }
597  START_TEST("Prune");
598  {
599  TestSpace* s = new TestSpace(arity,dom,this);
600  s->post();
601  while (!s->failed() && !s->assigned())
602  if (!s->prune(a,testfix)) {
603  problem = "No fixpoint";
604  delete s;
605  goto failed;
606  }
607  s->assign(a);
608  if (sol) {
609  CHECK_TEST(!s->failed(), "Failed on solution");
610  CHECK_TEST(s->propagators()==0, "No subsumption");
611  } else {
612  CHECK_TEST(s->failed(), "Solved on non-solution");
613  }
614  delete s;
615  }
616  START_TEST("Prune (disable)");
617  {
618  TestSpace* s = new TestSpace(arity,dom,this);
619  TestSpace* c = static_cast<TestSpace*>(s->clone());
620  s->post(); c->post();
621  while (!s->failed() && !s->assigned())
622  if (!s->disabled(a,*c,testfix)) {
623  problem = "Different result after re-enable";
624  delete s; delete c;
625  goto failed;
626  }
627  if (testfix && (s->failed() != c->failed())) {
628  problem = "Different failure after re-enable";
629  delete s; delete c;
630  goto failed;
631  }
632  delete s; delete c;
633  }
634  if (!ignore(a)) {
635  if (eqv()) {
636  {
637  START_TEST("Assignment reified (rewrite after post, <=>)");
638  TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
639  s->post();
640  s->rel(sol);
641  s->assign(a);
642  CHECK_TEST(!s->failed(), "Failed");
643  CHECK_TEST(s->propagators()==0, "No subsumption");
644  delete s;
645  }
646  {
647  START_TEST("Assignment reified (rewrite failure, <=>)");
648  TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
649  s->post();
650  s->rel(!sol);
651  s->assign(a);
652  CHECK_TEST(s->failed(), "Not failed");
653  delete s;
654  }
655  {
656  START_TEST("Assignment reified (immediate rewrite, <=>)");
657  TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
658  s->rel(sol);
659  s->post();
660  s->assign(a);
661  CHECK_TEST(!s->failed(), "Failed");
662  CHECK_TEST(s->propagators()==0, "No subsumption");
663  delete s;
664  }
665  {
666  START_TEST("Assignment reified (immediate failure, <=>)");
667  TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
668  s->rel(!sol);
669  s->post();
670  s->assign(a);
671  CHECK_TEST(s->failed(), "Not failed");
672  delete s;
673  }
674  {
675  START_TEST("Assignment reified (before posting, <=>)");
676  TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
677  s->assign(a);
678  s->post();
679  CHECK_TEST(!s->failed(), "Failed");
680  CHECK_TEST(s->propagators()==0, "No subsumption");
681  CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
682  if (sol) {
683  CHECK_TEST(s->r.var().val()==1, "Zero on solution");
684  } else {
685  CHECK_TEST(s->r.var().val()==0, "One on non-solution");
686  }
687  delete s;
688  }
689  {
690  START_TEST("Assignment reified (after posting, <=>)");
691  TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
692  s->post();
693  s->assign(a);
694  CHECK_TEST(!s->failed(), "Failed");
695  CHECK_TEST(s->propagators()==0, "No subsumption");
696  CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
697  if (sol) {
698  CHECK_TEST(s->r.var().val()==1, "Zero on solution");
699  } else {
700  CHECK_TEST(s->r.var().val()==0, "One on non-solution");
701  }
702  delete s;
703  }
704  {
705  START_TEST("Assignment reified (after posting, <=>, disable)");
706  TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
707  s->post();
708  s->disable();
709  s->assign(a);
710  s->enable();
711  CHECK_TEST(!s->failed(), "Failed");
712  CHECK_TEST(s->propagators()==0, "No subsumption");
713  CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
714  if (sol) {
715  CHECK_TEST(s->r.var().val()==1, "Zero on solution");
716  } else {
717  CHECK_TEST(s->r.var().val()==0, "One on non-solution");
718  }
719  delete s;
720  }
721  {
722  START_TEST("Prune reified, <=>");
723  TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
724  s->post();
725  while (!s->failed() &&
726  (!s->assigned() || !s->r.var().assigned()))
727  if (!s->prune(a,testfix)) {
728  problem = "No fixpoint";
729  delete s;
730  goto failed;
731  }
732  CHECK_TEST(!s->failed(), "Failed");
733  CHECK_TEST(s->propagators()==0, "No subsumption");
734  CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
735  if (sol) {
736  CHECK_TEST(s->r.var().val()==1, "Zero on solution");
737  } else {
738  CHECK_TEST(s->r.var().val()==0, "One on non-solution");
739  }
740  delete s;
741  }
742  {
743  START_TEST("Prune reified, <=>, disable");
744  TestSpace* s = new TestSpace(arity,dom,this,RM_EQV);
745  TestSpace* c = static_cast<TestSpace*>(s->clone());
746  s->post(); c->post();
747  while (!s->failed() &&
748  (!s->assigned() || !s->r.var().assigned()))
749  if (!s->disabled(a,*c,testfix)) {
750  problem = "No fixpoint";
751  delete s;
752  delete c;
753  goto failed;
754  }
755  CHECK_TEST(!c->failed(), "Failed");
756  CHECK_TEST(c->propagators()==0, "No subsumption");
757  CHECK_TEST(c->r.var().assigned(), "Control variable unassigned");
758  if (sol) {
759  CHECK_TEST(c->r.var().val()==1, "Zero on solution");
760  } else {
761  CHECK_TEST(c->r.var().val()==0, "One on non-solution");
762  }
763  delete s;
764  delete c;
765  }
766  }
767 
768  if (imp()) {
769  {
770  START_TEST("Assignment reified (rewrite after post, =>)");
771  TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
772  s->post();
773  s->rel(sol);
774  s->assign(a);
775  CHECK_TEST(!s->failed(), "Failed");
776  CHECK_TEST(s->propagators()==0, "No subsumption");
777  delete s;
778  }
779  {
780  START_TEST("Assignment reified (rewrite failure, =>)");
781  TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
782  s->post();
783  s->rel(!sol);
784  s->assign(a);
785  if (sol) {
786  CHECK_TEST(!s->failed(), "Failed");
787  CHECK_TEST(s->propagators()==0, "No subsumption");
788  } else {
789  CHECK_TEST(s->failed(), "Not failed");
790  }
791  delete s;
792  }
793  {
794  START_TEST("Assignment reified (immediate rewrite, =>)");
795  TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
796  s->rel(sol);
797  s->post();
798  s->assign(a);
799  CHECK_TEST(!s->failed(), "Failed");
800  CHECK_TEST(s->propagators()==0, "No subsumption");
801  delete s;
802  }
803  {
804  START_TEST("Assignment reified (immediate failure, =>)");
805  TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
806  s->rel(!sol);
807  s->post();
808  s->assign(a);
809  if (sol) {
810  CHECK_TEST(!s->failed(), "Failed");
811  CHECK_TEST(s->propagators()==0, "No subsumption");
812  } else {
813  CHECK_TEST(s->failed(), "Not failed");
814  }
815  delete s;
816  }
817  {
818  START_TEST("Assignment reified (before posting, =>)");
819  TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
820  s->assign(a);
821  s->post();
822  CHECK_TEST(!s->failed(), "Failed");
823  CHECK_TEST(s->propagators()==0, "No subsumption");
824  if (sol) {
825  CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
826  } else {
827  CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
828  CHECK_TEST(s->r.var().val()==0, "One on non-solution");
829  }
830  delete s;
831  }
832  {
833  START_TEST("Assignment reified (after posting, =>)");
834  TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
835  s->post();
836  s->assign(a);
837  CHECK_TEST(!s->failed(), "Failed");
838  CHECK_TEST(s->propagators()==0, "No subsumption");
839  if (sol) {
840  CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
841  } else {
842  CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
843  CHECK_TEST(s->r.var().val()==0, "One on non-solution");
844  }
845  delete s;
846  }
847  {
848  START_TEST("Assignment reified (after posting, =>, disable)");
849  TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
850  s->post();
851  s->disable();
852  s->assign(a);
853  s->enable();
854  CHECK_TEST(!s->failed(), "Failed");
855  CHECK_TEST(s->propagators()==0, "No subsumption");
856  if (sol) {
857  CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
858  } else {
859  CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
860  CHECK_TEST(s->r.var().val()==0, "One on non-solution");
861  }
862  delete s;
863  }
864  {
865  START_TEST("Prune reified, =>");
866  TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
867  s->post();
868  while (!s->failed() &&
869  (!s->assigned() || (!sol && !s->r.var().assigned())))
870  if (!s->prune(a,testfix)) {
871  problem = "No fixpoint";
872  delete s;
873  goto failed;
874  }
875  CHECK_TEST(!s->failed(), "Failed");
876  CHECK_TEST(s->propagators()==0, "No subsumption");
877  if (sol) {
878  CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
879  } else {
880  CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
881  CHECK_TEST(s->r.var().val()==0, "One on non-solution");
882  }
883  delete s;
884  }
885  {
886  START_TEST("Prune reified, =>, disable");
887  TestSpace* s = new TestSpace(arity,dom,this,RM_IMP);
888  TestSpace* c = static_cast<TestSpace*>(s->clone());
889  s->post(); c->post();
890  while (!s->failed() &&
891  (!s->assigned() || (!sol && !s->r.var().assigned())))
892  if (!s->disabled(a,*c,testfix)) {
893  problem = "No fixpoint";
894  delete s;
895  delete c;
896  goto failed;
897  }
898  CHECK_TEST(!c->failed(), "Failed");
899  CHECK_TEST(c->propagators()==0, "No subsumption");
900  if (sol) {
901  CHECK_TEST(!c->r.var().assigned(), "Control variable assigned");
902  } else {
903  CHECK_TEST(c->r.var().assigned(), "Control variable unassigned");
904  CHECK_TEST(c->r.var().val()==0, "One on non-solution");
905  }
906  delete s;
907  delete c;
908  }
909  }
910 
911  if (pmi()) {
912  {
913  START_TEST("Assignment reified (rewrite after post, <=)");
914  TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
915  s->post();
916  s->rel(sol);
917  s->assign(a);
918  CHECK_TEST(!s->failed(), "Failed");
919  CHECK_TEST(s->propagators()==0, "No subsumption");
920  delete s;
921  }
922  {
923  START_TEST("Assignment reified (rewrite failure, <=)");
924  TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
925  s->post();
926  s->rel(!sol);
927  s->assign(a);
928  if (sol) {
929  CHECK_TEST(s->failed(), "Not failed");
930  } else {
931  CHECK_TEST(!s->failed(), "Failed");
932  CHECK_TEST(s->propagators()==0, "No subsumption");
933  }
934  delete s;
935  }
936  {
937  START_TEST("Assignment reified (immediate rewrite, <=)");
938  TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
939  s->rel(sol);
940  s->post();
941  s->assign(a);
942  CHECK_TEST(!s->failed(), "Failed");
943  CHECK_TEST(s->propagators()==0, "No subsumption");
944  delete s;
945  }
946  {
947  START_TEST("Assignment reified (immediate failure, <=)");
948  TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
949  s->rel(!sol);
950  s->post();
951  s->assign(a);
952  if (sol) {
953  CHECK_TEST(s->failed(), "Not failed");
954  } else {
955  CHECK_TEST(!s->failed(), "Failed");
956  CHECK_TEST(s->propagators()==0, "No subsumption");
957  }
958  delete s;
959  }
960  {
961  START_TEST("Assignment reified (before posting, <=)");
962  TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
963  s->assign(a);
964  s->post();
965  CHECK_TEST(!s->failed(), "Failed");
966  CHECK_TEST(s->propagators()==0, "No subsumption");
967  if (sol) {
968  CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
969  CHECK_TEST(s->r.var().val()==1, "Zero on solution");
970  } else {
971  CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
972  }
973  delete s;
974  }
975  {
976  START_TEST("Assignment reified (after posting, <=)");
977  TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
978  s->post();
979  s->assign(a);
980  CHECK_TEST(!s->failed(), "Failed");
981  CHECK_TEST(s->propagators()==0, "No subsumption");
982  if (sol) {
983  CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
984  CHECK_TEST(s->r.var().val()==1, "Zero on solution");
985  } else {
986  CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
987  }
988  delete s;
989  }
990  {
991  START_TEST("Assignment reified (after posting, <=, disable)");
992  TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
993  s->post();
994  s->disable();
995  s->assign(a);
996  s->enable();
997  CHECK_TEST(!s->failed(), "Failed");
998  CHECK_TEST(s->propagators()==0, "No subsumption");
999  if (sol) {
1000  CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
1001  CHECK_TEST(s->r.var().val()==1, "Zero on solution");
1002  } else {
1003  CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
1004  }
1005  delete s;
1006  }
1007  {
1008  START_TEST("Prune reified, <=");
1009  TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
1010  s->post();
1011  while (!s->failed() &&
1012  (!s->assigned() || (sol && !s->r.var().assigned())))
1013  if (!s->prune(a,testfix)) {
1014  problem = "No fixpoint";
1015  delete s;
1016  goto failed;
1017  }
1018  CHECK_TEST(!s->failed(), "Failed");
1019  CHECK_TEST(s->propagators()==0, "No subsumption");
1020  if (sol) {
1021  CHECK_TEST(s->r.var().assigned(), "Control variable unassigned");
1022  CHECK_TEST(s->r.var().val()==1, "Zero on solution");
1023  } else {
1024  CHECK_TEST(!s->r.var().assigned(), "Control variable assigned");
1025  }
1026  delete s;
1027  }
1028  {
1029  START_TEST("Prune reified, <=, disable");
1030  TestSpace* s = new TestSpace(arity,dom,this,RM_PMI);
1031  TestSpace* c = static_cast<TestSpace*>(s->clone());
1032  s->post(); c->post();
1033  while (!s->failed() &&
1034  (!s->assigned() || (sol && !s->r.var().assigned())))
1035  if (!s->disabled(a,*c,testfix)) {
1036  problem = "No fixpoint";
1037  delete s;
1038  delete c;
1039  goto failed;
1040  }
1041  CHECK_TEST(!c->failed(), "Failed");
1042  CHECK_TEST(c->propagators()==0, "No subsumption");
1043  if (sol) {
1044  CHECK_TEST(c->r.var().assigned(), "Control variable unassigned");
1045  CHECK_TEST(c->r.var().val()==1, "Zero on solution");
1046  } else {
1047  CHECK_TEST(!c->r.var().assigned(), "Control variable assigned");
1048  }
1049  delete s;
1050  delete c;
1051  }
1052  }
1053  }
1054 
1055  if (testsearch) {
1056  if (sol) {
1057  START_TEST("Search");
1058  TestSpace* s = e_s.next();
1059  CHECK_TEST(s != NULL, "Solutions exhausted");
1060  CHECK_TEST(s->propagators()==0, "No subsumption");
1061  for (int i=a.size(); i--; ) {
1062  CHECK_TEST(s->x[i].assigned(), "Unassigned variable");
1063  CHECK_TEST(a[i] == s->x[i].val(), "Wrong value in solution");
1064  }
1065  delete s;
1066  }
1067  }
1068 
1069  ++a;
1070  }
1071 
1072  if (testsearch) {
1073  test = "Search";
1074  if (e_s.next() != NULL) {
1075  problem = "Excess solutions";
1076  goto failed;
1077  }
1078  }
1079 
1080  switch (contest) {
1081  case CTL_NONE: break;
1082  case CTL_DOMAIN: {
1083  START_TEST("Full domain consistency");
1084  TestSpace* s = new TestSpace(arity,dom,this);
1085  s->post();
1086  if (!s->failed()) {
1087  while (!s->failed() && !s->assigned())
1088  s->prune();
1089  CHECK_TEST(!s->failed(), "Failed");
1090  CHECK_TEST(s->propagators()==0, "No subsumption");
1091  }
1092  delete s;
1093  // Fall-through -- domain implies bounds(d) and bounds(z)
1094  }
1095  case CTL_BOUNDS_D: {
1096  START_TEST("Bounds(D)-consistency");
1097  TestSpace* s = new TestSpace(arity,dom,this);
1098  s->post();
1099  for (int i = s->x.size(); i--; )
1100  s->prune(i, false);
1101  if (!s->failed()) {
1102  while (!s->failed() && !s->assigned())
1103  s->bound();
1104  CHECK_TEST(!s->failed(), "Failed");
1105  CHECK_TEST(s->propagators()==0, "No subsumption");
1106  }
1107  delete s;
1108  // Fall-through -- bounds(d) implies bounds(z)
1109  }
1110  case CTL_BOUNDS_Z: {
1111  START_TEST("Bounds(Z)-consistency");
1112  TestSpace* s = new TestSpace(arity,dom,this);
1113  s->post();
1114  for (int i = s->x.size(); i--; )
1115  s->prune(i, true);
1116  if (!s->failed()) {
1117  while (!s->failed() && !s->assigned())
1118  s->bound();
1119  CHECK_TEST(!s->failed(), "Failed");
1120  CHECK_TEST(s->propagators()==0, "No subsumption");
1121  }
1122  delete s;
1123  break;
1124  }
1125  }
1126 
1127  delete ap;
1128  return true;
1129 
1130  failed:
1131  if (opt.log)
1132  olog << "FAILURE" << std::endl
1133  << ind(1) << "Test: " << test << std::endl
1134  << ind(1) << "Problem: " << problem << std::endl;
1135  if (a() && opt.log)
1136  olog << ind(1) << "Assignment: " << a << std::endl;
1137  delete ap;
1138 
1139  return false;
1140  }
1141 
1142 }}
1143 
1144 #undef START_TEST
1145 #undef CHECK_TEST
1146 
1147 // STATISTICS: test-int
Bounds propagation.
Definition: int.hh:978
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
virtual void operator++(void)
Move to next assignment.
Definition: int.cpp:70
void prune(int i, bool bounds_only)
Prune some random values from variable i.
Definition: int.cpp:276
NodeType t
Type of node.
Definition: bool-expr.cpp:230
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:96
#define CHECK_TEST(T, M)
Check the test result and handle failed test.
Definition: int.cpp:439
Gecode::IntSet d
Initial domain.
Definition: int.hh:152
Gecode::IntVarArray x
Variables to be tested.
Definition: int.hh:154
Inverse implication for reification.
Definition: int.hh:869
Simple class for describing identation.
Definition: test.hh:66
#define START_TEST(T)
Start new test.
Definition: int.cpp:447
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:908
ReifyMode mode(void) const
Return reification mode.
Definition: reify.hpp:56
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)=0
Post constraint.
int size(void) const
Return number of variables.
Definition: int.hpp:46
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:995
static Gecode::Support::RandomGenerator rand
Random number generator.
Definition: test.hh:134
virtual void operator++(void)
Move to next assignment.
Definition: int.cpp:48
BoolOpType
Operation types for Booleans.
Definition: int.hh:950
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: bool.hpp:81
void disable(Space &home)
Disable all propagators in a group.
Definition: core.cpp:950
static PropagatorGroup all
Group of all propagators.
Definition: core.hpp:786
bool assigned(void) const
Test whether view is assigned.
Definition: var.hpp:111
bool assigned(void) const
Test whether all variables are assigned.
Definition: int.cpp:137
Less or equal ( )
Definition: int.hh:928
Gecode::Reify r
Reification information.
Definition: int.hh:156
void init(const IntSet &s)
Initialize with values for s.
Definition: int-set-1.hpp:282
bool assigned(void) const
Test if all variables are assigned.
Definition: array.hpp:1008
Conjunction.
Definition: int.hh:951
virtual T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: base.hpp:46
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:40
void max(Home home, SetVar s, IntVar x, Reify r)
Definition: int.cpp:273
Implication.
Definition: int.hh:953
Integer variable array.
Definition: int.hh:763
bool failed(void)
Compute a fixpoint and check for failure.
Definition: int.cpp:158
void min(Home home, SetVar s, IntVar x, Reify r)
Definition: int.cpp:241
virtual Assignment * assignment(void) const
Create assignment.
Definition: int.cpp:433
Greater ( )
Definition: int.hh:931
Space for executing tests.
Definition: int.hh:149
Computation spaces.
Definition: core.hpp:1701
Greater or equal ( )
Definition: int.hh:930
unsigned int size(Space &home) const
Return number of propagators in a group.
Definition: core.cpp:926
Exclusive or.
Definition: int.hh:955
int n
Number of variables.
Definition: int.hh:61
Gecode::IntSet d
Domain for each variable.
Definition: int.hh:62
Reify imp(BoolVar x)
Use implication for reification.
Definition: reify.hpp:73
void prune(void)
Prune some random values for some random variable.
Definition: int.cpp:309
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Equality ( )
Definition: int.hh:926
Options opt
The options.
Definition: test.cpp:97
void rndrel(const Assignment &a, int i, Gecode::IntRelType &irt, int &v)
Randomly select a pruning rel for variable i.
Definition: int.cpp:181
Gecode::IntArgs i({1, 2, 3, 4})
No consistency-test.
Definition: int.hh:140
virtual bool run(void)
Perform test.
Definition: int.cpp:464
IntRelType
Relation types for integers.
Definition: int.hh:925
void rel(int i, Gecode::IntRelType irt, int n)
Perform integer tell operation on x[i].
Definition: int.cpp:230
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3181
void bound(void)
Assing a random variable to a random bound.
Definition: int.cpp:268
static bool fixpoint(void)
Throw a coin whether to compute a fixpoint.
Definition: test.hpp:66
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:55
Use basic propagation algorithm.
Definition: int.hh:981
struct Gecode::@593::NNF::@62::@63 b
For binary nodes (and, or, eqv)
unsigned int size(I &i)
Size of all ranges of range iterator i.
Reification specification.
Definition: int.hh:876
Value propagation.
Definition: int.hh:977
int min(void) const
Return smallest value of range.
TestSpace(int n, Gecode::IntSet &d, Test *t)
Create test space without reification.
Definition: int.cpp:91
Gecode::IntSetValues * dsv
Iterator for each variable.
Definition: int.hh:81
struct Gecode::Space::@58::@60 c
Data available only during copying.
void branch(Home home, const IntVarArgs &x, const BoolVarArgs &y, IntBoolVarBranch vars, IntValBranch vals)
Branch function for integer and Boolean variables.
Definition: branch.cpp:120
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition: var.hpp:116
Test for bounds(z)-consistency.
Definition: int.hh:143
Test for bounds(d)-consistency.
Definition: int.hh:142
bool log
Whether to log the tests.
Definition: test.hh:91
Less ( )
Definition: int.hh:929
Integer sets.
Definition: int.hh:174
Test for domain-consistency.
Definition: int.hh:141
Use advanced propagation algorithm.
Definition: int.hh:982
unsigned int propagators(void)
Return the number of propagators.
Definition: int.cpp:414
Reify eqv(BoolVar x)
Use equivalence for reification.
Definition: reify.hpp:69
Disjunction.
Definition: int.hh:952
Passing integer variables.
Definition: int.hh:656
void disable(void)
Disable propagators in space and compute fixpoint (make all idle)
Definition: int.cpp:360
std::ostream & operator<<(std::ostream &os, const Test::Int::Assignment &a)
Definition: int.cpp:81
Boolean integer variables.
Definition: int.hh:512
const int v[7]
Definition: distinct.cpp:259
void enable(void)
Enable propagators in space.
Definition: int.cpp:355
General test support.
Definition: afc.cpp:39
IntPropLevel
Propagation levels for integer propagators.
Definition: int.hh:974
virtual Gecode::Space * copy(void)
Copy space during cloning.
Definition: int.cpp:132
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
Space(void)
Default constructor.
Definition: core.cpp:115
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4001
void assign(const Assignment &a, bool skip=false)
Assign all (or all but one, if skip is true) variables to values in a.
Definition: int.cpp:256
Base class for assignments
Definition: int.hh:59
void enable(Space &home, bool s=true)
Enable all propagators in a group.
Definition: core.cpp:959
std::ostringstream olog
Stream used for logging.
Definition: test.cpp:53
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
Domain propagation Options: basic versus advanced propagation.
Definition: int.hh:979
Equivalence.
Definition: int.hh:954
BoolVar var(void) const
Return Boolean control variable.
Definition: reify.hpp:48
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:232
int max(void) const
Return largest value of range.
bool disabled(const Assignment &a, TestSpace &c, bool testfix)
Prune values also in a space c with disabled propagators, but not those in assignment a...
Definition: int.cpp:366
void threads(double n)
Set number of parallel threads.
Definition: options.hpp:292
Gecode toplevel namespace
Implication for reification.
Definition: int.hh:862
Disequality ( )
Definition: int.hh:927
virtual bool ignore(const Assignment &) const
Whether to ignore assignment for reification.
Definition: int.cpp:455
virtual void operator++(void)
Move to next assignment.
Definition: int.cpp:63
Space is failed
Definition: core.hpp:1641
Test * test
The test currently run.
Definition: int.hh:158
ReifyMode
Mode for reification.
Definition: int.hh:848
void post(void)
Post propagator.
Definition: int.cpp:145
Options for scripts
Definition: driver.hh:366
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.
Depth-first search engine.
Definition: search.hh:1036
Generate all assignments.
Definition: int.hh:79
Equivalence for reification (default)
Definition: int.hh:855
int val(void) const
Return assigned value.
Definition: bool.hpp:57
Reify pmi(BoolVar x)
Use reverse implication for reification.
Definition: reify.hpp:77
bool reified
Whether the test is for a reified propagator.
Definition: int.hh:160
int rndvar(void)
Randomly select an unassigned variable.
Definition: int.cpp:170