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