Generated on Sat Aug 25 2012 03:32:44 for Gecode by doxygen 1.8.1.2
bool.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  *
6  * Copyright:
7  * Christian Schulte, 2005
8  *
9  * Last modified:
10  * $Date: 2011-10-06 23:38:44 +1100 (Thu, 06 Oct 2011) $ by $Author: schulte $
11  * $Revision: 12421 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include "test/int.hh"
39 
40 #include <gecode/minimodel.hh>
41 
42 namespace Test { namespace Int {
43 
45  namespace Bool {
46 
47  inline int
48  check(int x0, Gecode::BoolOpType op, int x1) {
49  switch (op) {
50  case Gecode::BOT_AND: return x0 & x1;
51  case Gecode::BOT_OR: return x0 | x1;
52  case Gecode::BOT_IMP: return !x0 | x1;
53  case Gecode::BOT_EQV: return x0 == x1;
54  case Gecode::BOT_XOR: return x0 != x1;
55  default: GECODE_NEVER;
56  }
58  return 0;
59  }
60 
66 
67  class BinXYZ : public Test {
68  protected:
71  public:
74  : Test("Bool::Bin::XYZ::"+str(op0),3,0,1), op(op0) {}
76  virtual bool solution(const Assignment& x) const {
77  return check(x[0],op,x[1]) == x[2];
78  }
80  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
81  using namespace Gecode;
82  rel(home,
83  channel(home,x[0]), op, channel(home,x[1]),
84  channel(home,x[2]));
85  }
86  };
87 
89  class BinXXY : public Test {
90  protected:
93  public:
96  : Test("Bool::Bin::XXY::"+str(op0),2,0,1), op(op0) {}
98  virtual bool solution(const Assignment& x) const {
99  return check(x[0],op,x[0]) == x[1];
100  }
102  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
103  using namespace Gecode;
104  BoolVar b = channel(home,x[0]);
105  rel(home, b, op, b, channel(home,x[1]));
106  }
107  };
108 
110  class BinXYX : public Test {
111  protected:
114  public:
117  : Test("Bool::Bin::XYX::"+str(op0),2,0,1), op(op0) {}
119  virtual bool solution(const Assignment& x) const {
120  return check(x[0],op,x[1]) == x[0];
121  }
123  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
124  using namespace Gecode;
125  BoolVar b = channel(home,x[0]);
126  rel(home, b, op, channel(home,x[1]), b);
127  }
128  };
129 
131  class BinXYY : public Test {
132  protected:
135  public:
138  : Test("Bool::Bin::XYY::"+str(op0),2,0,1), op(op0) {}
140  virtual bool solution(const Assignment& x) const {
141  return check(x[0],op,x[1]) == x[1];
142  }
144  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
145  using namespace Gecode;
146  BoolVar b = channel(home,x[1]);
147  rel(home, channel(home,x[0]), op, b, b);
148  }
149  };
150 
152  class BinXXX : public Test {
153  protected:
156  public:
159  : Test("Bool::Bin::XXX::"+str(op0),1,0,1), op(op0) {}
161  virtual bool solution(const Assignment& x) const {
162  return check(x[0],op,x[0]) == x[0];
163  }
165  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
166  using namespace Gecode;
167  BoolVar b = channel(home,x[0]);
168  rel(home, b, op, b, b);
169  }
170  };
171 
173  class BinConstXY : public Test {
174  protected:
178  int c;
179  public:
182  : Test("Bool::Bin::XY::"+str(op0)+"::"+str(c0),2,0,1),
183  op(op0), c(c0) {}
185  virtual bool solution(const Assignment& x) const {
186  return check(x[0],op,x[1]) == c;
187  }
189  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
190  using namespace Gecode;
191  rel(home, channel(home,x[0]), op, channel(home,x[1]), c);
192  }
193  };
194 
196  class BinConstXX : public Test {
197  protected:
201  int c;
202  public:
205  : Test("Bool::Bin::XX::"+str(op0)+"::"+str(c0),1,0,1),
206  op(op0), c(c0) {}
208  virtual bool solution(const Assignment& x) const {
209  return check(x[0],op,x[0]) == c;
210  }
212  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
213  using namespace Gecode;
214  BoolVar b = channel(home,x[0]);
215  rel(home, b, op, b, c);
216  }
217  };
218 
220  class Nary : public Test {
221  protected:
224  public:
227  : Test("Bool::Nary::"+str(op0)+"::"+str(n),n+1,0,1), op(op0) {}
229  virtual bool solution(const Assignment& x) const {
230  int n = x.size()-1;
231  int b = check(x[n-2],op,x[n-1]);
232  for (int i=0; i<n-2; i++)
233  b = check(x[i],op,b);
234  return b == x[n];
235  }
237  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
238  using namespace Gecode;
239  BoolVarArgs b(x.size()-1);
240  for (int i=x.size()-1; i--; )
241  b[i]=channel(home,x[i]);
242  rel(home, op, b, channel(home,x[x.size()-1]));
243  }
244  };
245 
247  class NaryShared : public Test {
248  protected:
251  public:
254  : Test("Bool::Nary::Shared::"+str(op0)+"::"+str(n),n,0,1),
255  op(op0) {
256  if ((op == Gecode::BOT_EQV) || (op == Gecode::BOT_XOR))
257  testfix = false;
258  }
260  virtual bool solution(const Assignment& x) const {
261  int n = x.size();
262  int b = check(x[n-2],op,x[n-1]);
263  for (int i=0; i<n-2; i++)
264  b = check(x[i],op,b);
265  return b == x[n-1];
266  }
268  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
269  using namespace Gecode;
270  BoolVarArgs b(x.size());
271  for (int i=x.size(); i--; )
272  b[i]=channel(home,x[i]);
273  rel(home, op, b, b[x.size()-1]);
274  }
275  };
276 
278  class NaryConst : public Test {
279  protected:
283  int c;
284  public:
286  NaryConst(Gecode::BoolOpType op0, int n, int c0)
287  : Test("Bool::Nary::"+str(op0)+"::"+str(n)+"::"+str(c0),n,0,1),
288  op(op0), c(c0) {}
290  virtual bool solution(const Assignment& x) const {
291  int n = x.size();
292  int b = check(x[n-2],op,x[n-1]);
293  for (int i=0; i<n-2; i++)
294  b = check(x[i],op,b);
295  return b == c;
296  }
298  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
299  using namespace Gecode;
300  BoolVarArgs b(x.size());
301  for (int i=x.size(); i--; )
302  b[i]=channel(home,x[i]);
303  rel(home, op, b, c);
304  }
305  };
306 
307 
309  class ClauseXYZ : public Test {
310  protected:
313  public:
316  : Test("Bool::Clause::XYZ::"+str(op0)+"::"+str(n),n+1,0,1), op(op0) {}
318  virtual bool solution(const Assignment& x) const {
319  int n = (x.size()-1) / 2;
320  int b;
321  if (n == 1) {
322  b = check(x[0],op,!x[1]);
323  } else {
324  b = check(x[0],op,!x[n]);
325  for (int i=1; i<n; i++)
326  b = check(b,op,check(x[i],op,!x[n+i]));
327  }
328  return b == x[x.size()-1];
329  }
331  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
332  using namespace Gecode;
333  int n = (x.size()-1) / 2;
334  BoolVarArgs a(n), b(n);
335  for (int i=n; i--; ) {
336  a[i]=channel(home,x[i]);
337  b[i]=channel(home,x[i+n]);
338  }
339  clause(home, op, a, b, channel(home,x[x.size()-1]));
340  }
341  };
342 
344  class ClauseXXYYX : public Test {
345  protected:
348  public:
351  : Test("Bool::Clause::XXYYX::"+str(op0)+"::"+str(n),n,0,1),
352  op(op0) {}
354  virtual bool solution(const Assignment& x) const {
355  int n = x.size() / 2;
356  int b;
357  if (n == 1) {
358  b = check(x[0],op,!x[1]);
359  } else {
360  b = check(x[0],op,!x[n]);
361  for (int i=1; i<n; i++)
362  b = check(b,op,check(x[i],op,!x[n+i]));
363  }
364  return b == x[0];
365  }
367  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
368  using namespace Gecode;
369  int n = x.size() / 2;
370  BoolVarArgs a(2*n), b(2*n);
371  for (int i=n; i--; ) {
372  a[i]=a[i+n]=channel(home,x[i]);
373  b[i]=b[i+n]=channel(home,x[i+n]);
374  }
375  clause(home, op, a, b, a[0]);
376  }
377  };
378 
380  class ClauseXXY : public Test {
381  protected:
384  public:
387  : Test("Bool::Clause::XXY::"+str(op0)+"::"+str(n),n,0,1),
388  op(op0) {}
390  virtual bool solution(const Assignment& x) const {
391  return (x[0] == 1) == (op == Gecode::BOT_OR);
392  }
394  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
395  using namespace Gecode;
396  int n = x.size() / 2;
397  BoolVarArgs a(2*n), b(2*n);
398  for (int i=n; i--; ) {
399  a[i]=b[i+n]=channel(home,x[i]);
400  b[i]=a[i+n]=channel(home,x[i+n]);
401  }
402  clause(home, op, a, b, a[0]);
403  }
404  };
405 
407  class ClauseConst : public Test {
408  protected:
412  int c;
413  public:
415  ClauseConst(Gecode::BoolOpType op0, int n, int c0)
416  : Test("Bool::Clause::"+str(op0)+"::"+str(n)+"::"+str(c0),n,0,1),
417  op(op0), c(c0) {}
419  virtual bool solution(const Assignment& x) const {
420  int n = x.size() / 2;
421  int b;
422  if (n == 1) {
423  b = check(x[0],op,!x[1]);
424  } else {
425  b = check(x[0],op,!x[n]);
426  for (int i=1; i<n; i++)
427  b = check(b,op,check(x[i],op,!x[n+i]));
428  }
429  return b == c;
430  }
432  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
433  using namespace Gecode;
434  int n = x.size() / 2;
435  BoolVarArgs a(n), b(n);
436  for (int i=n; i--; ) {
437  a[i]=channel(home,x[i]);
438  b[i]=channel(home,x[i+n]);
439  }
440  clause(home, op, a, b, c);
441  }
442  };
443 
445  class Create {
446  public:
448  Create(void) {
449  using namespace Gecode;
450  for (BoolOpTypes bots; bots(); ++bots) {
451  (void) new BinXYZ(bots.bot());
452  (void) new BinXXY(bots.bot());
453  (void) new BinXYX(bots.bot());
454  (void) new BinXYY(bots.bot());
455  (void) new BinXXX(bots.bot());
456  (void) new BinConstXY(bots.bot(),0);
457  (void) new BinConstXY(bots.bot(),1);
458  (void) new BinConstXX(bots.bot(),0);
459  (void) new BinConstXX(bots.bot(),1);
460  (void) new Nary(bots.bot(),2);
461  (void) new Nary(bots.bot(),6);
462  (void) new Nary(bots.bot(),10);
463  (void) new NaryShared(bots.bot(),2);
464  (void) new NaryShared(bots.bot(),6);
465  (void) new NaryShared(bots.bot(),10);
466  (void) new NaryConst(bots.bot(),2,0);
467  (void) new NaryConst(bots.bot(),6,0);
468  (void) new NaryConst(bots.bot(),10,0);
469  (void) new NaryConst(bots.bot(),2,1);
470  (void) new NaryConst(bots.bot(),6,1);
471  (void) new NaryConst(bots.bot(),10,1);
472  if ((bots.bot() == BOT_AND) || (bots.bot() == BOT_OR)) {
473  (void) new ClauseXYZ(bots.bot(),2);
474  (void) new ClauseXYZ(bots.bot(),6);
475  (void) new ClauseXYZ(bots.bot(),10);
476  (void) new ClauseXXYYX(bots.bot(),2);
477  (void) new ClauseXXYYX(bots.bot(),6);
478  (void) new ClauseXXYYX(bots.bot(),10);
479  (void) new ClauseXXY(bots.bot(),2);
480  (void) new ClauseXXY(bots.bot(),6);
481  (void) new ClauseXXY(bots.bot(),10);
482  (void) new ClauseConst(bots.bot(),2,0);
483  (void) new ClauseConst(bots.bot(),6,0);
484  (void) new ClauseConst(bots.bot(),10,0);
485  (void) new ClauseConst(bots.bot(),2,1);
486  (void) new ClauseConst(bots.bot(),6,1);
487  (void) new ClauseConst(bots.bot(),10,1);
488  }
489  }
490  }
491  };
492 
495 
496  }
497 }}
498 
499 // STATISTICS: test-int
500