Generated on Sat Aug 25 2012 03:32:54 for Gecode by doxygen 1.8.1.2
set.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Guido Tack <tack@gecode.org>
5  * Christian Schulte <schulte@gecode.org>
6  * Mikael Lagerkvist <lagerkvist@gecode.org>
7  *
8  * Copyright:
9  * Guido Tack, 2005
10  * Christian Schulte, 2005
11  * Mikael Lagerkvist, 2005
12  *
13  * Last modified:
14  * $Date: 2011-08-25 00:34:16 +1000 (Thu, 25 Aug 2011) $ by $Author: tack $
15  * $Revision: 12346 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 #include "test/set.hh"
43 
44 #include <algorithm>
45 
46 namespace Test { namespace Set {
47 
48  CountableSet::CountableSet(const Gecode::IntSet& d0) : d(d0), cur(0) {
49  Gecode::IntSetRanges isr(d);
50  lubmax =
51  static_cast<unsigned int>(pow(static_cast<double>(2.0),
52  static_cast<int>(Gecode::Iter::Ranges::size(isr))));
53  }
54 
56  cur++;
57  }
58 
60  d = d0;
61  cur = 0;
62  Gecode::IntSetRanges isr(d);
63  lubmax =
64  static_cast<unsigned int>(pow(static_cast<double>(2.0),
65  static_cast<int>(Gecode::Iter::Ranges::size(isr))));
66  }
67 
68  int CountableSet::val(void) const {
69  return cur;
70  }
71 
72  SetAssignment::SetAssignment(int n0, const Gecode::IntSet& d0, int _withInt)
73  : n(n0), dsv(new CountableSet[n]), ir(_withInt, d0), done(false), lub(d0),
74  withInt(_withInt) {
75  for (int i=n; i--; )
76  dsv[i].init(lub);
77  }
78 
79  void
81  int i = n-1;
82  while (true) {
83  ++dsv[i];
84  if (dsv[i]())
85  return;
86  dsv[i].init(lub);
87  --i;
88  if (i<0) {
89  if (withInt==0) {
90  done = true;
91  return;
92  }
93  ++ir;
94  if (ir()) {
95  i = n-1;
96  for (int j=n; j--; )
97  dsv[j].init(lub);
98  } else {
99  done = true;
100  return;
101  }
102  }
103  }
104  }
105 
106 }}
107 
108 std::ostream&
109 operator<<(std::ostream& os, const Test::Set::SetAssignment& a) {
110  int n = a.size();
111  os << "{";
112  for (int i=0; i<n; i++) {
114  Gecode::IntSet icsv(csv);
115  os << icsv << ((i!=n-1) ? "," : "}");
116  }
117  if (a.withInt > 0)
118  os << a.ints();
119  return os;
120 }
121 
122 namespace Test { namespace Set {
123 
125  SetTest* t, bool log)
126  : d(d0), x(*this, n, Gecode::IntSet::empty, d), y(*this, i, d),
127  withInt(i), b(*this, 0, 1), reified(r), test(t) {
128  if (opt.log && log) {
129  olog << ind(2) << "Initial: x[]=" << x;
130  olog << " y[]=" << y;
131  if (reified)
132  olog << " b=" << b;
133  olog << std::endl;
134  }
135  }
136 
138  : Gecode::Space(share,s), d(s.d), withInt(s.withInt),
139  reified(s.reified), test(s.test) {
140  x.update(*this, share, s.x);
141  y.update(*this, share, s.y);
142  b.update(*this, share, s.b);
143  }
144 
145  Gecode::Space*
146  SetTestSpace::copy(bool share) {
147  return new SetTestSpace(share,*this);
148  }
149 
150  void
152  if (reified){
153  test->post(*this,x,y,b);
154  if (opt.log)
155  olog << ind(3) << "Posting reified propagator" << std::endl;
156  } else {
157  test->post(*this,x,y);
158  if (opt.log)
159  olog << ind(3) << "Posting propagator" << std::endl;
160  }
161  }
162 
163  bool
165  if (opt.log) {
166  olog << ind(3) << "Fixpoint: x[]=" << x
167  << " y[]=" << y << std::endl;
168  bool f=(status() == Gecode::SS_FAILED);
169  olog << ind(3) << " --> x[]=" << x
170  << " y[]=" << y << std::endl;
171  return f;
172  } else {
173  return status() == Gecode::SS_FAILED;
174  }
175  }
176 
177  void
179  if (opt.log) {
180  olog << ind(4) << "x[" << i << "] ";
181  switch (srt) {
182  case Gecode::SRT_EQ: olog << "="; break;
183  case Gecode::SRT_LQ: olog << "<="; break;
184  case Gecode::SRT_LE: olog << "<"; break;
185  case Gecode::SRT_GQ: olog << ">="; break;
186  case Gecode::SRT_GR: olog << ">"; break;
187  case Gecode::SRT_NQ: olog << "!="; break;
188  case Gecode::SRT_SUB: olog << "sub"; break;
189  case Gecode::SRT_SUP: olog << "sup"; break;
190  case Gecode::SRT_DISJ: olog << "||"; break;
191  case Gecode::SRT_CMPL: olog << "^-1 = "; break;
192  }
193  olog << is << std::endl;
194  }
195  Gecode::dom(*this, x[i], srt, is);
196  }
197 
198  void
199  SetTestSpace::cardinality(int i, int cmin, int cmax) {
200  if (opt.log) {
201  olog << ind(4) << cmin << " <= #(x[" << i << "]) <= " << cmax
202  << std::endl;
203  }
204  Gecode::cardinality(*this, x[i], cmin, cmax);
205  }
206 
207  void
209  if (opt.log) {
210  olog << ind(4) << "y[" << i << "] ";
211  switch (irt) {
212  case Gecode::IRT_EQ: olog << "="; break;
213  case Gecode::IRT_NQ: olog << "!="; break;
214  case Gecode::IRT_LQ: olog << "<="; break;
215  case Gecode::IRT_LE: olog << "<"; break;
216  case Gecode::IRT_GQ: olog << ">="; break;
217  case Gecode::IRT_GR: olog << ">"; break;
218  }
219  olog << " " << n << std::endl;
220  }
221  Gecode::rel(*this, y[i], irt, n);
222  }
223 
224  void
225  SetTestSpace::rel(bool sol) {
226  int n = sol ? 1 : 0;
227  assert(reified);
228  if (opt.log)
229  olog << ind(4) << "b = " << n << std::endl;
230  Gecode::rel(*this, b, Gecode::IRT_EQ, n);
231  }
232 
233  void
235  for (int i=a.size(); i--; ) {
236  CountableSetRanges csv(a.lub, a[i]);
237  Gecode::IntSet ai(csv);
238  rel(i, Gecode::SRT_EQ, ai);
239  if (Base::fixpoint() && failed())
240  return;
241  }
242  for (int i=withInt; i--; ) {
243  rel(i, Gecode::IRT_EQ, a.ints()[i]);
244  if (Base::fixpoint() && failed())
245  return;
246  }
247  }
248 
249  bool
251  for (int i=x.size(); i--; )
252  if (!x[i].assigned())
253  return false;
254  for (int i=y.size(); i--; )
255  if (!y[i].assigned())
256  return false;
257  return true;
258  }
259 
260  void
262  using namespace Gecode;
263  SetVarUnknownRanges ur(x[i]);
264  CountableSetRanges air(a.lub, a[i]);
266  CountableSetRanges> diff(ur, air);
269  for (int j=0; j<v; j++, ++diffV) {}
270  rel(i, Gecode::SRT_DISJ, Gecode::IntSet(diffV.val(), diffV.val()));
271  }
272 
273  void
275  using namespace Gecode;
276  SetVarUnknownRanges ur(x[i]);
277  CountableSetRanges air(a.lub, a[i]);
279  CountableSetRanges> inter(ur, air);
282  for (int j=0; j<v; j++, ++interV) {}
283  rel(i, Gecode::SRT_SUP, Gecode::IntSet(interV.val(), interV.val()));
284  }
285 
286  bool
288  if (failed())
289  return true;
290  SetTestSpace* c = static_cast<SetTestSpace*>(clone());
291  if (opt.log)
292  olog << ind(3) << "Testing fixpoint on copy" << std::endl;
293  c->post();
294  if (c->failed()) {
295  delete c; return false;
296  }
297 
298  for (int i=x.size(); i--; )
299  if (x[i].glbSize() != c->x[i].glbSize() ||
300  x[i].lubSize() != c->x[i].lubSize() ||
301  x[i].cardMin() != c->x[i].cardMin() ||
302  x[i].cardMax() != c->x[i].cardMax()) {
303  delete c;
304  return false;
305  }
306  for (int i=y.size(); i--; )
307  if (y[i].size() != c->y[i].size()) {
308  delete c; return false;
309  }
310  if (reified && (b.size() != c->b.size())) {
311  delete c; return false;
312  }
313  if (opt.log)
314  olog << ind(3) << "Finished testing fixpoint on copy" << std::endl;
315  delete c;
316  return true;
317  }
318 
319  bool
321  using namespace Gecode;
322  bool setsAssigned = true;
323  for (int j=x.size(); j--; )
324  if (!x[j].assigned()) {
325  setsAssigned = false;
326  break;
327  }
328  bool intsAssigned = true;
329  for (int j=y.size(); j--; )
330  if (!y[j].assigned()) {
331  intsAssigned = false;
332  break;
333  }
334 
335  // Select variable to be pruned
336  int i;
337  if (intsAssigned) {
338  i = Base::rand(x.size());
339  } else if (setsAssigned) {
340  i = Base::rand(y.size());
341  } else {
342  i = Base::rand(x.size()+y.size());
343  }
344 
345  if (setsAssigned || i>=x.size()) {
346  if (i>=x.size())
347  i = i-x.size();
348  while (y[i].assigned()) {
349  i = (i+1) % y.size();
350  }
351  // Prune int var
352 
353  // Select mode for pruning
354  switch (Base::rand(3)) {
355  case 0:
356  if (a.ints()[i] < y[i].max()) {
357  int v=a.ints()[i]+1+
358  Base::rand(static_cast<unsigned int>(y[i].max()-a.ints()[i]));
359  assert((v > a.ints()[i]) && (v <= y[i].max()));
360  rel(i, Gecode::IRT_LE, v);
361  }
362  break;
363  case 1:
364  if (a.ints()[i] > y[i].min()) {
365  int v=y[i].min()+
366  Base::rand(static_cast<unsigned int>(a.ints()[i]-y[i].min()));
367  assert((v < a.ints()[i]) && (v >= y[i].min()));
368  rel(i, Gecode::IRT_GR, v);
369  }
370  break;
371  default:
372  int v;
374  unsigned int skip = Base::rand(y[i].size()-1);
375  while (true) {
376  if (it.width() > skip) {
377  v = it.min() + skip;
378  if (v == a.ints()[i]) {
379  if (it.width() == 1) {
380  ++it; v = it.min();
381  } else if (v < it.max()) {
382  ++v;
383  } else {
384  --v;
385  }
386  }
387  break;
388  }
389  skip -= it.width();
390  ++it;
391  }
392  rel(i, Gecode::IRT_NQ, v);
393  }
394  return (!Base::fixpoint() || fixprob());
395  }
396  while (x[i].assigned()) {
397  i = (i+1) % x.size();
398  }
400  CountableSetRanges air1(a.lub, a[i]);
402  CountableSetRanges> diff(ur1, air1);
404  CountableSetRanges air2(a.lub, a[i]);
406  CountableSetRanges> inter(ur2, air2);
407 
408  CountableSetRanges aisizer(a.lub, a[i]);
409  unsigned int aisize = Gecode::Iter::Ranges::size(aisizer);
410 
411  // Select mode for pruning
412  switch (Base::rand(5)) {
413  case 0:
414  if (inter()) {
416  addToGlb(v, i, a);
417  }
418  break;
419  case 1:
420  if (diff()) {
422  removeFromLub(v, i, a);
423  }
424  break;
425  case 2:
426  if (x[i].cardMin() < aisize) {
427  unsigned int newc = x[i].cardMin() + 1 +
428  Base::rand(aisize - x[i].cardMin());
429  assert( newc > x[i].cardMin() );
430  assert( newc <= aisize );
432  }
433  break;
434  case 3:
435  if (x[i].cardMax() > aisize) {
436  unsigned int newc = x[i].cardMax() - 1 -
437  Base::rand(x[i].cardMax() - aisize);
438  assert( newc < x[i].cardMax() );
439  assert( newc >= aisize );
440  cardinality(i, 0, newc);
441  }
442  break;
443  default:
444  if (inter()) {
446  addToGlb(v, i, a);
447  } else {
449  removeFromLub(v, i, a);
450  }
451  }
452  return (!Base::fixpoint() || fixprob());
453  }
454 
455 
457 #define CHECK_TEST(T,M) \
458 if (opt.log) \
459  olog << ind(3) << "Check: " << (M) << std::endl; \
460 if (!(T)) { \
461  problem = (M); delete s; goto failed; \
462 }
463 
465 #define START_TEST(T) \
466  if (opt.log) { \
467  olog.str(""); \
468  olog << ind(2) << "Testing: " << (T) << std::endl; \
469  } \
470  test = (T);
471 
472  bool
473  SetTest::run(void) {
474  const char* test = "NONE";
475  const char* problem = "NONE";
476 
477  SetAssignment* ap = new SetAssignment(arity,lub,withInt);
478  SetAssignment& a = *ap;
479  while (a()) {
480  bool is_sol = solution(a);
481  if (opt.log)
482  olog << ind(1) << "Assignment: " << a
483  << (is_sol ? " (solution)" : " (no solution)")
484  << std::endl;
485 
486  START_TEST("Assignment (after posting)");
487  {
488  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,false,this);
489  SetTestSpace* sc = NULL;
490  s->post();
491  switch (Base::rand(3)) {
492  case 0:
493  if (opt.log)
494  olog << ind(3) << "No copy" << std::endl;
495  sc = s;
496  s = NULL;
497  break;
498  case 1:
499  if (opt.log)
500  olog << ind(3) << "Unshared copy" << std::endl;
501  if (s->status() != Gecode::SS_FAILED) {
502  sc = static_cast<SetTestSpace*>(s->clone(true));
503  } else {
504  sc = s; s = NULL;
505  }
506  break;
507  case 2:
508  if (opt.log)
509  olog << ind(3) << "Unshared copy" << std::endl;
510  if (s->status() != Gecode::SS_FAILED) {
511  sc = static_cast<SetTestSpace*>(s->clone(false));
512  } else {
513  sc = s; s = NULL;
514  }
515  break;
516  default: assert(false);
517  }
518  sc->assign(a);
519  if (is_sol) {
520  CHECK_TEST(!sc->failed(), "Failed on solution");
521  CHECK_TEST(sc->propagators()==0, "No subsumption");
522  } else {
523  CHECK_TEST(sc->failed(), "Solved on non-solution");
524  }
525  delete s; delete sc;
526  }
527  START_TEST("Assignment (before posting)");
528  {
529  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,false,this);
530  s->assign(a);
531  s->post();
532  if (is_sol) {
533  CHECK_TEST(!s->failed(), "Failed on solution");
534  CHECK_TEST(s->propagators()==0, "No subsumption");
535  } else {
536  CHECK_TEST(s->failed(), "Solved on non-solution");
537  }
538  delete s;
539  }
540  if (reified) {
541  START_TEST("Assignment reified (before posting)");
542  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,true,this);
543  s->assign(a);
544  s->post();
545  CHECK_TEST(!s->failed(), "Failed");
546  CHECK_TEST(s->propagators()==0, "No subsumption");
547  CHECK_TEST(s->b.assigned(), "Control variable unassigned");
548  if (is_sol) {
549  CHECK_TEST(s->b.val()==1, "Zero on solution");
550  } else {
551  CHECK_TEST(s->b.val()==0, "One on non-solution");
552  }
553  delete s;
554  }
555  if (reified) {
556  START_TEST("Assignment reified (after posting)");
557  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,true,this);
558  s->post();
559  s->assign(a);
560  CHECK_TEST(!s->failed(), "Failed");
561  CHECK_TEST(s->propagators()==0, "No subsumption");
562  CHECK_TEST(s->b.assigned(), "Control variable unassigned");
563  if (is_sol) {
564  CHECK_TEST(s->b.val()==1, "Zero on solution");
565  } else {
566  CHECK_TEST(s->b.val()==0, "One on non-solution");
567  }
568  delete s;
569  }
570  START_TEST("Prune");
571  {
572  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,false,this);
573  s->post();
574  while (!s->failed() && !s->assigned())
575  if (!s->prune(a)) {
576  problem = "No fixpoint";
577  delete s;
578  goto failed;
579  }
580  s->assign(a);
581  if (is_sol) {
582  CHECK_TEST(!s->failed(), "Failed on solution");
583  CHECK_TEST(s->propagators()==0, "No subsumption");
584  } else {
585  CHECK_TEST(s->failed(), "Solved on non-solution");
586  }
587  delete s;
588  }
589  if (reified) {
590  START_TEST("Prune reified");
591  SetTestSpace* s = new SetTestSpace(arity,lub,withInt,true,this);
592  s->post();
593  while (!s->assigned() && !s->b.assigned())
594  if (!s->prune(a)) {
595  problem = "No fixpoint";
596  delete s;
597  goto failed;
598  }
599  CHECK_TEST(!s->failed(), "Failed");
600  CHECK_TEST(s->propagators()==0, "No subsumption");
601  CHECK_TEST(s->b.assigned(), "Control variable unassigned");
602  if (is_sol) {
603  CHECK_TEST(s->b.val()==1, "Zero on solution");
604  } else {
605  CHECK_TEST(s->b.val()==0, "One on non-solution");
606  }
607  delete s;
608  }
609  ++a;
610  }
611  delete ap;
612  return true;
613  failed:
614  if (opt.log)
615  olog << "FAILURE" << std::endl
616  << ind(1) << "Test: " << test << std::endl
617  << ind(1) << "Problem: " << problem << std::endl;
618  if (a() && opt.log)
619  olog << ind(1) << "Assignment: " << a << std::endl;
620  delete ap;
621 
622  return false;
623  }
624 
625  const Gecode::SetRelType SetRelTypes::srts[] =
628 
629  const Gecode::SetOpType SetOpTypes::sots[] =
632 
633 }}
634 
635 #undef START_TEST
636 #undef CHECK_TEST
637 
638 // STATISTICS: test-set