Generated on Thu Feb 14 2013 20:59:29 for Gecode by doxygen 1.8.3.1
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, 2002
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 <gecode/int/bool.hh>
39 #include <gecode/int/rel.hh>
40 
41 namespace Gecode {
42 
43  void
45  using namespace Int;
46  if (home.failed()) return;
47  switch (r) {
48  case IRT_EQ:
50  ::post(home,x0,x1)));
51  break;
52  case IRT_NQ:
53  {
54  NegBoolView n1(x1);
56  ::post(home,x0,n1)));
57  }
58  break;
59  case IRT_GQ:
61  break;
62  case IRT_LQ:
64  break;
65  case IRT_GR:
67  break;
68  case IRT_LE:
70  break;
71  default:
72  throw UnknownRelation("Int::rel");
73  }
74  }
75 
76  void
77  rel(Home home, BoolVar x0, IntRelType r, int n, IntConLevel) {
78  using namespace Int;
79  if (home.failed()) return;
80  BoolView x(x0);
81  if (n == 0) {
82  switch (r) {
83  case IRT_LQ:
84  case IRT_EQ:
85  GECODE_ME_FAIL(x.zero(home)); break;
86  case IRT_NQ:
87  case IRT_GR:
88  GECODE_ME_FAIL(x.one(home)); break;
89  case IRT_LE:
90  home.fail(); break;
91  case IRT_GQ:
92  break;
93  default:
94  throw UnknownRelation("Int::rel");
95  }
96  } else if (n == 1) {
97  switch (r) {
98  case IRT_GQ:
99  case IRT_EQ:
100  GECODE_ME_FAIL(x.one(home)); break;
101  case IRT_NQ:
102  case IRT_LE:
103  GECODE_ME_FAIL(x.zero(home)); break;
104  case IRT_GR:
105  home.fail(); break;
106  case IRT_LQ:
107  break;
108  default:
109  throw UnknownRelation("Int::rel");
110  }
111  } else {
112  throw NotZeroOne("Int::rel");
113  }
114  }
115 
116  void
118  IntConLevel) {
119  using namespace Int;
120  if (home.failed()) return;
121  switch (r) {
122  case IRT_EQ:
124  ::post(home,x0,x1,b)));
125  break;
126  case IRT_NQ:
127  {
128  NegBoolView n(b);
130  ::post(home,x0,x1,n)));
131  }
132  break;
133  case IRT_GQ:
134  std::swap(x0,x1);
135  case IRT_LQ:
136  {
137  NegBoolView n0(x0);
139  ::post(home,n0,x1,b)));
140  }
141  break;
142  case IRT_GR:
143  std::swap(x0,x1);
144  case IRT_LE:
145  {
146  NegBoolView n1(x1), n(b);
148  ::post(home,x0,n1,n)));
149  }
150  break;
151  default:
152  throw UnknownRelation("Int::rel");
153  }
154  }
155 
156  void
157  rel(Home home, BoolVar x0, IntRelType r, int n, BoolVar b,
158  IntConLevel) {
159  using namespace Int;
160  if (home.failed()) return;
161  BoolView x(x0);
162  BoolView y(b);
163  if (n == 0) {
164  switch (r) {
165  case IRT_LQ:
166  case IRT_EQ:
167  {
168  NegBoolView z(y);
170  ::post(home,x,z)));
171  }
172  break;
173  case IRT_NQ:
174  case IRT_GR:
176  ::post(home,x,y)));
177  break;
178  case IRT_LE:
179  GECODE_ME_FAIL(y.zero(home));
180  break;
181  case IRT_GQ:
182  GECODE_ME_FAIL(y.one(home));
183  break;
184  default:
185  throw UnknownRelation("Int::rel");
186  }
187  } else if (n == 1) {
188  switch (r) {
189  case IRT_GQ:
190  case IRT_EQ:
192  ::post(home,x,y)));
193  break;
194  case IRT_NQ:
195  case IRT_LE:
196  {
197  NegBoolView z(y);
199  ::post(home,x,z)));
200  }
201  break;
202  case IRT_GR:
203  GECODE_ME_FAIL(y.zero(home));
204  break;
205  case IRT_LQ:
206  GECODE_ME_FAIL(y.one(home));
207  break;
208  default:
209  throw UnknownRelation("Int::rel");
210  }
211  } else {
212  throw NotZeroOne("Int::rel");
213  }
214  }
215 
216  void
217  rel(Home home, const BoolVarArgs& x, IntRelType r, BoolVar y,
218  IntConLevel) {
219  using namespace Int;
220  if (home.failed()) return;
221  switch (r) {
222  case IRT_EQ:
223  for (int i=x.size(); i--; ) {
225  ::post(home,x[i],y)));
226  }
227  break;
228  case IRT_NQ:
229  {
230  NegBoolView n(y);
231  for (int i=x.size(); i--; ) {
233  ::post(home,x[i],n)));
234  }
235  }
236  break;
237  case IRT_GQ:
238  for (int i=x.size(); i--; ) {
240  }
241  break;
242  case IRT_LQ:
243  for (int i=x.size(); i--; ) {
245  }
246  break;
247  case IRT_GR:
248  for (int i=x.size(); i--; ) {
250  }
251  break;
252  case IRT_LE:
253  for (int i=x.size(); i--; ) {
255  }
256  break;
257  default:
258  throw UnknownRelation("Int::rel");
259  }
260  }
261 
262  void
263  rel(Home home, const BoolVarArgs& x, IntRelType r, int n,
264  IntConLevel) {
265  using namespace Int;
266  if (home.failed()) return;
267  if (n == 0) {
268  switch (r) {
269  case IRT_LQ:
270  case IRT_EQ:
271  for (int i=x.size(); i--; ) {
272  BoolView xi(x[i]); GECODE_ME_FAIL(xi.zero(home));
273  }
274  break;
275  case IRT_NQ:
276  case IRT_GR:
277  for (int i=x.size(); i--; ) {
278  BoolView xi(x[i]); GECODE_ME_FAIL(xi.one(home));
279  }
280  break;
281  case IRT_LE:
282  home.fail(); break;
283  case IRT_GQ:
284  break;
285  default:
286  throw UnknownRelation("Int::rel");
287  }
288  } else if (n == 1) {
289  switch (r) {
290  case IRT_GQ:
291  case IRT_EQ:
292  for (int i=x.size(); i--; ) {
293  BoolView xi(x[i]); GECODE_ME_FAIL(xi.one(home));
294  }
295  break;
296  case IRT_NQ:
297  case IRT_LE:
298  for (int i=x.size(); i--; ) {
299  BoolView xi(x[i]); GECODE_ME_FAIL(xi.zero(home));
300  }
301  break;
302  case IRT_GR:
303  home.fail(); break;
304  case IRT_LQ:
305  break;
306  default:
307  throw UnknownRelation("Int::rel");
308  }
309  } else {
310  throw NotZeroOne("Int::rel");
311  }
312  }
313 
314  void
316  using namespace Int;
317  if (home.failed() || ((r != IRT_NQ) && (x.size() < 2)))
318  return;
319 
320  switch (r) {
321  case IRT_EQ:
322  {
323  ViewArray<BoolView> y(home,x);
325  }
326  break;
327  case IRT_NQ:
328  {
329  ViewArray<BoolView> y(home,x);
331  }
332  break;
333  case IRT_LE:
334  if (x.size() == 2) {
335  GECODE_ES_FAIL(Bool::Le<BoolView>::post(home,x[0],x[1]));
336  } else {
337  home.fail();
338  }
339  break;
340  case IRT_LQ:
341  {
342  ViewArray<BoolView> y(home,x);
344  }
345  break;
346  case IRT_GR:
347  if (x.size() == 2) {
348  GECODE_ES_FAIL(Bool::Le<BoolView>::post(home,x[1],x[0]));
349  } else {
350  home.fail();
351  }
352  break;
353  case IRT_GQ:
354  {
355  ViewArray<BoolView> y(home,x.size());
356  for (int i=x.size(); i--; )
357  y[i] = x[x.size()-1-i];
359  }
360  for (int i=x.size()-1; i--; )
362  break;
363  default:
364  throw UnknownRelation("Int::rel");
365  }
366  }
367 
368  void
369  rel(Home home, const BoolVarArgs& x, IntRelType r, const BoolVarArgs& y,
370  IntConLevel) {
371  using namespace Int;
372  if (x.size() != y.size())
373  throw ArgumentSizeMismatch("Int::rel");
374  if (home.failed()) return;
375 
376  switch (r) {
377  case IRT_GR:
378  {
379  ViewArray<BoolView> xv(home,x), yv(home,y);
381  }
382  break;
383  case IRT_LE:
384  {
385  ViewArray<BoolView> xv(home,x), yv(home,y);
387  }
388  break;
389  case IRT_GQ:
390  {
391  ViewArray<BoolView> xv(home,x), yv(home,y);
392  GECODE_ES_FAIL(Rel::LexLqLe<BoolView>::post(home,yv,xv,false));
393  }
394  break;
395  case IRT_LQ:
396  {
397  ViewArray<BoolView> xv(home,x), yv(home,y);
398  GECODE_ES_FAIL(Rel::LexLqLe<BoolView>::post(home,xv,yv,false));
399  }
400  break;
401  case IRT_EQ:
402  for (int i=x.size(); i--; ) {
404  ::post(home,x[i],y[i])));
405  }
406  break;
407  case IRT_NQ:
408  {
409  ViewArray<BoolView> xv(home,x), yv(home,y);
411  }
412  break;
413  default:
414  throw UnknownRelation("Int::rel");
415  }
416  }
417 
418  void
419  rel(Home home, BoolVar x0, BoolOpType o, BoolVar x1, BoolVar x2,
420  IntConLevel) {
421  using namespace Int;
422  if (home.failed()) return;
423  switch (o) {
424  case BOT_AND:
425  {
426  NegBoolView n0(x0); NegBoolView n1(x1); NegBoolView n2(x2);
428  ::post(home,n0,n1,n2)));
429  }
430  break;
431  case BOT_OR:
433  ::post(home,x0,x1,x2)));
434  break;
435  case BOT_IMP:
436  {
437  NegBoolView n0(x0);
439  ::post(home,n0,x1,x2)));
440  }
441  break;
442  case BOT_EQV:
444  ::post(home,x0,x1,x2)));
445  break;
446  case BOT_XOR:
447  {
448  NegBoolView n2(x2);
450  ::post(home,x0,x1,n2)));
451  }
452  break;
453  default:
454  throw UnknownOperation("Int::rel");
455  }
456  }
457 
458  void
459  rel(Home home, BoolVar x0, BoolOpType o, BoolVar x1, int n,
460  IntConLevel) {
461  using namespace Int;
462  if (home.failed()) return;
463  if (n == 0) {
464  switch (o) {
465  case BOT_AND:
466  {
467  NegBoolView n0(x0); NegBoolView n1(x1);
469  ::post(home,n0,n1)));
470  }
471  break;
472  case BOT_OR:
473  {
474  BoolView b0(x0); BoolView b1(x1);
475  GECODE_ME_FAIL(b0.zero(home));
476  GECODE_ME_FAIL(b1.zero(home));
477  }
478  break;
479  case BOT_IMP:
480  {
481  BoolView b0(x0); BoolView b1(x1);
482  GECODE_ME_FAIL(b0.one(home));
483  GECODE_ME_FAIL(b1.zero(home));
484  }
485  break;
486  case BOT_EQV:
487  {
488  NegBoolView n0(x0);
490  }
491  break;
492  case BOT_XOR:
494  break;
495  default:
496  throw UnknownOperation("Int::rel");
497  }
498  } else if (n == 1) {
499  switch (o) {
500  case BOT_AND:
501  {
502  BoolView b0(x0); BoolView b1(x1);
503  GECODE_ME_FAIL(b0.one(home));
504  GECODE_ME_FAIL(b1.one(home));
505  }
506  break;
507  case BOT_OR:
509  break;
510  case BOT_IMP:
511  {
512  NegBoolView n0(x0);
514  ::post(home,n0,x1)));
515  }
516  break;
517  case BOT_EQV:
519  break;
520  case BOT_XOR:
521  {
522  NegBoolView n0(x0);
524  }
525  break;
526  default:
527  throw UnknownOperation("Int::rel");
528  }
529  } else {
530  throw NotZeroOne("Int::rel");
531  }
532  }
533 
534  void
535  rel(Home home, BoolOpType o, const BoolVarArgs& x, BoolVar y,
536  IntConLevel) {
537  using namespace Int;
538  if (home.failed()) return;
539  int m = x.size();
540  Region r(home);
541  switch (o) {
542  case BOT_AND:
543  {
544  ViewArray<NegBoolView> b(home,m);
545  for (int i=m; i--; ) {
546  NegBoolView nb(x[i]); b[i]=nb;
547  }
548  NegBoolView ny(y);
549  b.unique(home);
551  ::post(home,b,ny)));
552  }
553  break;
554  case BOT_OR:
555  {
556  ViewArray<BoolView> b(home,x);
557  b.unique(home);
559  }
560  break;
561  case BOT_IMP:
562  if (m < 2) {
563  throw TooFewArguments("Int::rel");
564  } else {
565  ViewArray<NegBoolView> a(home,x.size()-1);
566  for (int i=x.size()-1; i--; )
567  a[i]=NegBoolView(x[i]);
568  ViewArray<BoolView> b(home,1);
569  b[0]=x[x.size()-1];
571  ::post(home,b,a,y)));
572  }
573  break;
574  case BOT_EQV:
575  {
576  ViewArray<BoolView> xy(home, x.size() + 1);
577  for (int i=x.size(); i--; )
578  xy[i] = x[i];
579  xy[x.size()] = y;
581  }
582  break;
583  case BOT_XOR:
584  {
585  ViewArray<BoolView> xy(home, x.size() + 1);
586  for (int i=x.size(); i--; )
587  xy[i] = x[i];
588  xy[x.size()] = y;
590  }
591  break;
592  default:
593  throw UnknownOperation("Int::rel");
594  }
595  }
596 
597  void
598  rel(Home home, BoolOpType o, const BoolVarArgs& x, int n,
599  IntConLevel) {
600  using namespace Int;
601  if ((n < 0) || (n > 1))
602  throw NotZeroOne("Int::rel");
603  if (home.failed()) return;
604  int m = x.size();
605  Region r(home);
606  switch (o) {
607  case BOT_AND:
608  if (n == 0) {
609  ViewArray<NegBoolView> b(home,m);
610  for (int i=m; i--; ) {
611  NegBoolView nb(x[i]); b[i]=nb;
612  }
613  b.unique(home);
615  } else {
616  for (int i=m; i--; ) {
617  BoolView b(x[i]); GECODE_ME_FAIL(b.one(home));
618  }
619  }
620  break;
621  case BOT_OR:
622  if (n == 0) {
623  for (int i=m; i--; ) {
624  BoolView b(x[i]); GECODE_ME_FAIL(b.zero(home));
625  }
626  } else {
627  ViewArray<BoolView> b(home,x);
628  b.unique(home);
630  }
631  break;
632  case BOT_IMP:
633  if (m < 2) {
634  throw TooFewArguments("Int::rel");
635  } else if (n == 0) {
636  for (int i=m-1; i--; )
637  GECODE_ME_FAIL(BoolView(x[i]).one(home));
638  GECODE_ME_FAIL(BoolView(x[m-1]).zero(home));
639  } else {
640  ViewArray<NegBoolView> a(home,x.size()-1);
641  for (int i=x.size()-1; i--; )
642  a[i]=NegBoolView(x[i]);
643  ViewArray<BoolView> b(home,1);
644  b[0]=x[x.size()-1];
646  ::post(home,b,a)));
647  }
648  break;
649  case BOT_EQV:
650  {
651  ViewArray<BoolView> b(home,x);
653  }
654  break;
655  case BOT_XOR:
656  {
657  ViewArray<BoolView> b(home,x);
658  GECODE_ES_FAIL(Bool::NaryEqv::post(home,b,1^n));
659  }
660  break;
661  default:
662  throw UnknownOperation("Int::rel");
663  }
664  }
665 
666  void
667  clause(Home home, BoolOpType o, const BoolVarArgs& x, const BoolVarArgs& y,
668  int n, IntConLevel) {
669  using namespace Int;
670  if ((n < 0) || (n > 1))
671  throw NotZeroOne("Int::rel");
672  if (home.failed()) return;
673  switch (o) {
674  case BOT_AND:
675  if (n == 0) {
676  ViewArray<NegBoolView> xv(home,x.size());
677  for (int i=x.size(); i--; ) {
678  NegBoolView n(x[i]); xv[i]=n;
679  }
680  ViewArray<BoolView> yv(home,y);
681  xv.unique(home); yv.unique(home);
683  ::post(home,xv,yv)));
684  } else {
685  for (int i=x.size(); i--; ) {
686  BoolView b(x[i]); GECODE_ME_FAIL(b.one(home));
687  }
688  for (int i=y.size(); i--; ) {
689  BoolView b(y[i]); GECODE_ME_FAIL(b.zero(home));
690  }
691  }
692  break;
693  case BOT_OR:
694  if (n == 0) {
695  for (int i=x.size(); i--; ) {
696  BoolView b(x[i]); GECODE_ME_FAIL(b.zero(home));
697  }
698  for (int i=y.size(); i--; ) {
699  BoolView b(y[i]); GECODE_ME_FAIL(b.one(home));
700  }
701  } else {
702  ViewArray<BoolView> xv(home,x);
703  ViewArray<NegBoolView> yv(home,y.size());
704  for (int i=y.size(); i--; ) {
705  NegBoolView n(y[i]); yv[i]=n;
706  }
707  xv.unique(home); yv.unique(home);
709  ::post(home,xv,yv)));
710  }
711  break;
712  default:
713  throw IllegalOperation("Int::clause");
714  }
715  }
716 
717  void
718  clause(Home home, BoolOpType o, const BoolVarArgs& x, const BoolVarArgs& y,
719  BoolVar z, IntConLevel) {
720  using namespace Int;
721  if (home.failed()) return;
722  switch (o) {
723  case BOT_AND:
724  {
725  ViewArray<NegBoolView> xv(home,x.size());
726  for (int i=x.size(); i--; ) {
727  NegBoolView n(x[i]); xv[i]=n;
728  }
729  ViewArray<BoolView> yv(home,y);
730  xv.unique(home); yv.unique(home);
731  NegBoolView nz(z);
733  ::post(home,xv,yv,nz)));
734  }
735  break;
736  case BOT_OR:
737  {
738  ViewArray<BoolView> xv(home,x);
739  ViewArray<NegBoolView> yv(home,y.size());
740  for (int i=y.size(); i--; ) {
741  NegBoolView n(y[i]); yv[i]=n;
742  }
743  xv.unique(home); yv.unique(home);
745  ::post(home,xv,yv,z)));
746  }
747  break;
748  default:
749  throw IllegalOperation("Int::clause");
750  }
751  }
752 
753 }
754 
755 // STATISTICS: int-post