Generated on Thu Mar 7 2013 10:21:35 for Gecode by doxygen 1.8.3.1
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: 2010-06-03 21:11:11 +1000 (Thu, 03 Jun 2010) $ by $Author: tack $
13  * $Revision: 11013 $
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 
95  TestSpace::TestSpace(int n, Gecode::IntSet& d0, bool r, Test* t, bool log)
96  : d(d0), x(*this,n,d), b(*this,0,1), reified(r), test(t) {
97  if (opt.log && log) {
98  olog << ind(2) << "Initial: x[]=" << x;
99  if (reified)
100  olog << " b=" << b;
101  olog << std::endl;
102  }
103  }
104 
106  : Gecode::Space(share,s), d(s.d), reified(s.reified), test(s.test) {
107  x.update(*this, share, s.x);
108  b.update(*this, share, s.b);
109  }
110 
111  Gecode::Space*
112  TestSpace::copy(bool share) {
113  return new TestSpace(share,*this);
114  }
115 
116  bool
117  TestSpace::assigned(void) const {
118  for (int i=x.size(); i--; )
119  if (!x[i].assigned())
120  return false;
121  return true;
122  }
123 
124  void
126  if (reified){
127  test->post(*this,x,b);
128  if (opt.log)
129  olog << ind(3) << "Posting reified propagator" << std::endl;
130  } else {
131  test->post(*this,x);
132  if (opt.log)
133  olog << ind(3) << "Posting propagator" << std::endl;
134  }
135  }
136 
137  bool
139  if (opt.log) {
140  olog << ind(3) << "Fixpoint: " << x;
141  bool f=(status() == Gecode::SS_FAILED);
142  olog << std::endl << ind(3) << " --> " << x << std::endl;
143  return f;
144  } else {
145  return status() == Gecode::SS_FAILED;
146  }
147  }
148 
149  void
151  if (opt.log) {
152  olog << ind(4) << "x[" << i << "] ";
153  switch (irt) {
154  case Gecode::IRT_EQ: olog << "="; break;
155  case Gecode::IRT_NQ: olog << "!="; break;
156  case Gecode::IRT_LQ: olog << "<="; break;
157  case Gecode::IRT_LE: olog << "<"; break;
158  case Gecode::IRT_GQ: olog << ">="; break;
159  case Gecode::IRT_GR: olog << ">"; break;
160  }
161  olog << " " << n << std::endl;
162  }
163  Gecode::rel(*this, x[i], irt, n);
164  }
165 
166  void
167  TestSpace::rel(bool sol) {
168  int n = sol ? 1 : 0;
169  assert(reified);
170  if (opt.log)
171  olog << ind(4) << "b = " << n << std::endl;
172  Gecode::rel(*this, b, Gecode::IRT_EQ, n);
173  }
174 
175  void
176  TestSpace::assign(const Assignment& a, bool skip) {
177  using namespace Gecode;
178  int i = skip ? static_cast<int>(Base::rand(a.size())) : -1;
179  for (int j=a.size(); j--; )
180  if (i != j) {
181  rel(j, IRT_EQ, a[j]);
182  if (Base::fixpoint() && failed())
183  return;
184  }
185  }
186 
187  void
189  using namespace Gecode;
190  // Select variable to be assigned
191  int i = Base::rand(x.size());
192  while (x[i].assigned()) {
193  i = (i+1) % x.size();
194  }
195  bool min = Base::rand(2);
196  rel(i, IRT_EQ, min ? x[i].min() : x[i].max());
197  }
198 
199  void
200  TestSpace::prune(int i, bool bounds_only) {
201  using namespace Gecode;
202  // Prune values
203  if (bounds_only) {
204  if (Base::rand(2) && !x[i].assigned()) {
205  int v=x[i].min()+1+Base::rand(static_cast
206  <unsigned int>(x[i].max()-x[i].min()));
207  assert((v > x[i].min()) && (v <= x[i].max()));
208  rel(i, Gecode::IRT_LE, v);
209  }
210  if (Base::rand(2) && !x[i].assigned()) {
211  int v=x[i].min()+Base::rand(static_cast
212  <unsigned int>(x[i].max()-x[i].min()));
213  assert((v < x[i].max()) && (v >= x[i].min()));
214  rel(i, Gecode::IRT_GR, v);
215  }
216  } else {
217  for (int vals = Base::rand(x[i].size()-1)+1; vals--; ) {
218  int v;
220  unsigned int skip = Base::rand(x[i].size()-1);
221  while (true) {
222  if (it.width() > skip) {
223  v = it.min() + skip; break;
224  }
225  skip -= it.width(); ++it;
226  }
227  rel(i, IRT_NQ, v);
228  }
229  }
230  }
231 
232  void
234  using namespace Gecode;
235  // Select variable to be pruned
236  int i = Base::rand(x.size());
237  while (x[i].assigned()) {
238  i = (i+1) % x.size();
239  }
240  prune(i, false);
241  }
242 
243  bool
244  TestSpace::prune(const Assignment& a, bool testfix) {
245  // Select variable to be pruned
246  int i = Base::rand(x.size());
247  while (x[i].assigned())
248  i = (i+1) % x.size();
249  // Select mode for pruning
250  switch (Base::rand(3)) {
251  case 0:
252  if (a[i] < x[i].max()) {
253  int v=a[i]+1+Base::rand(static_cast
254  <unsigned int>(x[i].max()-a[i]));
255  assert((v > a[i]) && (v <= x[i].max()));
256  rel(i, Gecode::IRT_LE, v);
257  }
258  break;
259  case 1:
260  if (a[i] > x[i].min()) {
261  int v=x[i].min()+Base::rand(static_cast
262  <unsigned int>(a[i]-x[i].min()));
263  assert((v < a[i]) && (v >= x[i].min()));
264  rel(i, Gecode::IRT_GR, v);
265  }
266  break;
267  default:
268  {
269  int v;
271  unsigned int skip = Base::rand(x[i].size()-1);
272  while (true) {
273  if (it.width() > skip) {
274  v = it.min() + skip;
275  if (v == a[i]) {
276  if (it.width() == 1) {
277  ++it; v = it.min();
278  } else if (v < it.max()) {
279  ++v;
280  } else {
281  --v;
282  }
283  }
284  break;
285  }
286  skip -= it.width(); ++it;
287  }
288  rel(i, Gecode::IRT_NQ, v);
289  break;
290  }
291  }
292  if (Base::fixpoint()) {
293  if (failed() || !testfix)
294  return true;
295  TestSpace* c = static_cast<TestSpace*>(clone());
296  if (opt.log)
297  olog << ind(3) << "Testing fixpoint on copy" << std::endl;
298  c->post();
299  if (c->failed()) {
300  delete c; return false;
301  }
302  for (int i=x.size(); i--; )
303  if (x[i].size() != c->x[i].size()) {
304  delete c; return false;
305  }
306  if (reified && (b.size() != c->b.size())) {
307  delete c; return false;
308  }
309  if (opt.log)
310  olog << ind(3) << "Finished testing fixpoint on copy" << std::endl;
311  delete c;
312  }
313  return true;
314  }
315 
316 
317  const Gecode::IntConLevel IntConLevels::icls[] =
319 
320  const Gecode::IntRelType IntRelTypes::irts[] =
323 
324  const Gecode::BoolOpType BoolOpTypes::bots[] =
327 
328  Assignment*
329  Test::assignment(void) const {
330  return new CpltAssignment(arity,dom);
331  }
332 
333 
335 #define CHECK_TEST(T,M) \
336 if (opt.log) \
337  olog << ind(3) << "Check: " << (M) << std::endl; \
338 if (!(T)) { \
339  problem = (M); delete s; goto failed; \
340 }
341 
343 #define START_TEST(T) \
344  if (opt.log) { \
345  olog.str(""); \
346  olog << ind(2) << "Testing: " << (T) << std::endl; \
347  } \
348  test = (T);
349 
350  bool
351  Test::ignore(const Assignment&) const {
352  return false;
353  }
354 
355  void
357  Gecode::BoolVar) {}
358 
359  bool
360  Test::run(void) {
361  using namespace Gecode;
362  const char* test = "NONE";
363  const char* problem = "NONE";
364 
365  // Set up assignments
366  Assignment* ap = assignment();
367  Assignment& a = *ap;
368 
369  // Set up space for all solution search
370  TestSpace* search_s = new TestSpace(arity,dom,false,this,false);
371  post(*search_s,search_s->x);
372  branch(*search_s,search_s->x,INT_VAR_NONE,INT_VAL_MIN);
373  Search::Options search_o;
374  search_o.threads = 1;
375  DFS<TestSpace> e_s(search_s,search_o);
376  delete search_s;
377 
378  while (a()) {
379  bool sol = solution(a);
380  if (opt.log) {
381  olog << ind(1) << "Assignment: " << a
382  << (sol ? " (solution)" : " (no solution)")
383  << std::endl;
384  }
385 
386  START_TEST("Assignment (after posting)");
387  {
388  TestSpace* s = new TestSpace(arity,dom,false,this);
389  TestSpace* sc = NULL;
390  s->post();
391  switch (Base::rand(3)) {
392  case 0:
393  if (opt.log)
394  olog << ind(3) << "No copy" << std::endl;
395  sc = s;
396  s = NULL;
397  break;
398  case 1:
399  if (opt.log)
400  olog << ind(3) << "Unshared copy" << std::endl;
401  if (s->status() != SS_FAILED) {
402  sc = static_cast<TestSpace*>(s->clone(false));
403  } else {
404  sc = s; s = NULL;
405  }
406  break;
407  case 2:
408  if (opt.log)
409  olog << ind(3) << "Shared copy" << std::endl;
410  if (s->status() != SS_FAILED) {
411  sc = static_cast<TestSpace*>(s->clone(true));
412  } else {
413  sc = s; s = NULL;
414  }
415  break;
416  default: assert(false);
417  }
418  sc->assign(a);
419  if (sol) {
420  CHECK_TEST(!sc->failed(), "Failed on solution");
421  CHECK_TEST(sc->propagators()==0, "No subsumption");
422  } else {
423  CHECK_TEST(sc->failed(), "Solved on non-solution");
424  }
425  delete s; delete sc;
426  }
427  START_TEST("Partial assignment (after posting)");
428  {
429  TestSpace* s = new TestSpace(arity,dom,false,this);
430  s->post();
431  s->assign(a,true);
432  (void) s->failed();
433  s->assign(a);
434  if (sol) {
435  CHECK_TEST(!s->failed(), "Failed on solution");
436  CHECK_TEST(s->propagators()==0, "No subsumption");
437  } else {
438  CHECK_TEST(s->failed(), "Solved on non-solution");
439  }
440  delete s;
441  }
442  START_TEST("Assignment (before posting)");
443  {
444  TestSpace* s = new TestSpace(arity,dom,false,this);
445  s->assign(a);
446  s->post();
447  if (sol) {
448  CHECK_TEST(!s->failed(), "Failed on solution");
449  CHECK_TEST(s->propagators()==0, "No subsumption");
450  } else {
451  CHECK_TEST(s->failed(), "Solved on non-solution");
452  }
453  delete s;
454  }
455  START_TEST("Partial assignment (before posting)");
456  {
457  TestSpace* s = new TestSpace(arity,dom,false,this);
458  s->assign(a,true);
459  s->post();
460  (void) s->failed();
461  s->assign(a);
462  if (sol) {
463  CHECK_TEST(!s->failed(), "Failed on solution");
464  CHECK_TEST(s->propagators()==0, "No subsumption");
465  } else {
466  CHECK_TEST(s->failed(), "Solved on non-solution");
467  }
468  delete s;
469  }
470  START_TEST("Prune");
471  {
472  TestSpace* s = new TestSpace(arity,dom,false,this);
473  s->post();
474  while (!s->failed() && !s->assigned())
475  if (!s->prune(a,testfix)) {
476  problem = "No fixpoint";
477  delete s;
478  goto failed;
479  }
480  s->assign(a);
481  if (sol) {
482  CHECK_TEST(!s->failed(), "Failed on solution");
483  CHECK_TEST(s->propagators()==0, "No subsumption");
484  } else {
485  CHECK_TEST(s->failed(), "Solved on non-solution");
486  }
487  delete s;
488  }
489 
490  if (reified && !ignore(a)) {
491  START_TEST("Assignment reified (rewrite after post)");
492  {
493  TestSpace* s = new TestSpace(arity,dom,true,this);
494  s->post();
495  s->rel(sol);
496  s->assign(a);
497  CHECK_TEST(!s->failed(), "Failed");
498  CHECK_TEST(s->propagators()==0, "No subsumption");
499  delete s;
500  }
501  START_TEST("Assignment reified (immediate rewrite)");
502  {
503  TestSpace* s = new TestSpace(arity,dom,true,this);
504  s->rel(sol);
505  s->post();
506  s->assign(a);
507  CHECK_TEST(!s->failed(), "Failed");
508  CHECK_TEST(s->propagators()==0, "No subsumption");
509  delete s;
510  }
511  START_TEST("Assignment reified (before posting)");
512  {
513  TestSpace* s = new TestSpace(arity,dom,true,this);
514  s->assign(a);
515  s->post();
516  CHECK_TEST(!s->failed(), "Failed");
517  CHECK_TEST(s->propagators()==0, "No subsumption");
518  CHECK_TEST(s->b.assigned(), "Control variable unassigned");
519  if (sol) {
520  CHECK_TEST(s->b.val()==1, "Zero on solution");
521  } else {
522  CHECK_TEST(s->b.val()==0, "One on non-solution");
523  }
524  delete s;
525  }
526  START_TEST("Assignment reified (after posting)");
527  {
528  TestSpace* s = new TestSpace(arity,dom,true,this);
529  s->post();
530  s->assign(a);
531  CHECK_TEST(!s->failed(), "Failed");
532  CHECK_TEST(s->propagators()==0, "No subsumption");
533  CHECK_TEST(s->b.assigned(), "Control variable unassigned");
534  if (sol) {
535  CHECK_TEST(s->b.val()==1, "Zero on solution");
536  } else {
537  CHECK_TEST(s->b.val()==0, "One on non-solution");
538  }
539  delete s;
540  }
541  START_TEST("Prune reified");
542  {
543  TestSpace* s = new TestSpace(arity,dom,true,this);
544  s->post();
545  while (!s->failed() && (!s->assigned() || !s->b.assigned()))
546  if (!s->prune(a,testfix)) {
547  problem = "No fixpoint";
548  delete s;
549  goto failed;
550  }
551  CHECK_TEST(!s->failed(), "Failed");
552  CHECK_TEST(s->propagators()==0, "No subsumption");
553  CHECK_TEST(s->b.assigned(), "Control variable unassigned");
554  if (sol) {
555  CHECK_TEST(s->b.val()==1, "Zero on solution");
556  } else {
557  CHECK_TEST(s->b.val()==0, "One on non-solution");
558  }
559  delete s;
560  }
561  }
562 
563  if (testsearch) {
564  if (sol) {
565  START_TEST("Search");
566  TestSpace* s = e_s.next();
567  CHECK_TEST(s != NULL, "Solutions exhausted");
568  CHECK_TEST(s->propagators()==0, "No subsumption");
569  for (int i=a.size(); i--; ) {
570  CHECK_TEST(s->x[i].assigned(), "Unassigned variable");
571  CHECK_TEST(a[i] == s->x[i].val(), "Wrong value in solution");
572  }
573  delete s;
574  }
575  }
576 
577  ++a;
578  }
579 
580  if (testsearch) {
581  test = "Search";
582  if (e_s.next() != NULL) {
583  problem = "Excess solutions";
584  goto failed;
585  }
586  }
587 
588  switch (contest) {
589  case CTL_NONE: break;
590  case CTL_DOMAIN: {
591  START_TEST("Full domain consistency");
592  TestSpace* s = new TestSpace(arity,dom,false,this);
593  s->post();
594  if (!s->failed()) {
595  while (!s->failed() && !s->assigned())
596  s->prune();
597  CHECK_TEST(!s->failed(), "Failed");
598  CHECK_TEST(s->propagators()==0, "No subsumption");
599  }
600  delete s;
601  // Fall-through -- domain implies bounds(d) and bounds(z)
602  }
603  case CTL_BOUNDS_D: {
604  START_TEST("Bounds(D)-consistency");
605  TestSpace* s = new TestSpace(arity,dom,false,this);
606  s->post();
607  for (int i = s->x.size(); i--; )
608  s->prune(i, false);
609  if (!s->failed()) {
610  while (!s->failed() && !s->assigned())
611  s->bound();
612  CHECK_TEST(!s->failed(), "Failed");
613  CHECK_TEST(s->propagators()==0, "No subsumption");
614  }
615  delete s;
616  // Fall-through -- bounds(d) implies bounds(z)
617  }
618  case CTL_BOUNDS_Z: {
619  START_TEST("Bounds(Z)-consistency");
620  TestSpace* s = new TestSpace(arity,dom,false,this);
621  s->post();
622  for (int i = s->x.size(); i--; )
623  s->prune(i, true);
624  if (!s->failed()) {
625  while (!s->failed() && !s->assigned())
626  s->bound();
627  CHECK_TEST(!s->failed(), "Failed");
628  CHECK_TEST(s->propagators()==0, "No subsumption");
629  }
630  delete s;
631  break;
632  }
633  }
634 
635  delete ap;
636  return true;
637 
638  failed:
639  if (opt.log)
640  olog << "FAILURE" << std::endl
641  << ind(1) << "Test: " << test << std::endl
642  << ind(1) << "Problem: " << problem << std::endl;
643  if (a() && opt.log)
644  olog << ind(1) << "Assignment: " << a << std::endl;
645  delete ap;
646 
647  return false;
648  }
649 
650 }}
651 
652 #undef START_TEST
653 #undef CHECK_TEST
654 
655 // STATISTICS: test-int