Generated on Fri Aug 31 2012 16:21:05 for Gecode by doxygen 1.8.1.2
dom.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  *
6  * Contributing authors:
7  * Gabor Szokoli <szokoli@gecode.org>
8  *
9  * Copyright:
10  * Guido Tack, 2004, 2005
11  *
12  * Last modified:
13  * $Date: 2011-08-25 00:34:16 +1000 (Thu, 25 Aug 2011) $ by $Author: tack $
14  * $Revision: 12346 $
15  *
16  * This file is part of Gecode, the generic constraint
17  * development environment:
18  * http://www.gecode.org
19  *
20  * Permission is hereby granted, free of charge, to any person obtaining
21  * a copy of this software and associated documentation files (the
22  * "Software"), to deal in the Software without restriction, including
23  * without limitation the rights to use, copy, modify, merge, publish,
24  * distribute, sublicense, and/or sell copies of the Software, and to
25  * permit persons to whom the Software is furnished to do so, subject to
26  * the following conditions:
27  *
28  * The above copyright notice and this permission notice shall be
29  * included in all copies or substantial portions of the Software.
30  *
31  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
32  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
33  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
34  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
35  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
36  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
37  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
38  *
39  */
40 
41 #include <gecode/set.hh>
42 #include <gecode/set/rel.hh>
43 
44 namespace Gecode {
45 
46  void
47  dom(Home home, SetVar s, SetRelType r, int i) {
48  Set::Limits::check(i, "Set::dom");
49  IntSet d(i,i);
50  dom(home, s, r, d);
51  }
52 
53  void
54  dom(Home home, SetVar s, SetRelType r, int i, int j) {
55  Set::Limits::check(i, "Set::dom");
56  Set::Limits::check(j, "Set::dom");
57  IntSet d(i,j);
58  dom(home, s, r, d);
59  }
60 
61  void
62  dom(Home home, SetVar s, SetRelType r, const IntSet& is) {
63  Set::Limits::check(is, "Set::dom");
64  if (home.failed()) return;
65 
66  Set::SetView _s(s);
67 
68  switch (r) {
69  case SRT_EQ:
70  {
71  if (is.ranges() == 1) {
72  GECODE_ME_FAIL(_s.include(home, is.min(), is.max()));
73  GECODE_ME_FAIL(_s.intersect(home, is.min(), is.max()));
74  } else {
75  IntSetRanges rd1(is);
76  GECODE_ME_FAIL(_s.includeI(home, rd1));
77  IntSetRanges rd2(is);
78  GECODE_ME_FAIL(_s.intersectI(home, rd2));
79  }
80  }
81  break;
82  case SRT_LQ:
83  {
84  Set::ConstSetView cv(home, is);
87  ::post(home,s,cv)));
88  }
89  break;
90  case SRT_LE:
91  {
92  Set::ConstSetView cv(home, is);
95  ::post(home,s,cv)));
96  }
97  break;
98  case SRT_GQ:
99  {
100  Set::ConstSetView cv(home, is);
103  ::post(home,cv,s)));
104  }
105  break;
106  case SRT_GR:
107  {
108  Set::ConstSetView cv(home, is);
111  ::post(home,cv,s)));
112  }
113  break;
114  case SRT_DISJ:
115  {
116  if (is.ranges() == 1) {
117  GECODE_ME_FAIL(_s.exclude(home, is.min(), is.max()));
118  } else {
119  IntSetRanges rd(is);
120  GECODE_ME_FAIL(_s.excludeI(home, rd));
121  }
122  }
123  break;
124  case SRT_NQ:
125  {
126  Set::ConstSetView cv(home, is);
129  cv)));
130  }
131  break;
132  case SRT_SUB:
133  {
134  if (is.ranges() == 1) {
135  GECODE_ME_FAIL(_s.intersect(home, is.min(), is.max()));
136  } else {
137  IntSetRanges rd(is);
138  GECODE_ME_FAIL(_s.intersectI(home, rd));
139  }
140  }
141  break;
142  case SRT_SUP:
143  {
144  if (is.ranges() == 1) {
145  GECODE_ME_FAIL(_s.include(home, is.min(), is.max()));
146  } else {
147  IntSetRanges rd(is);
148  GECODE_ME_FAIL(_s.includeI(home, rd));
149  }
150  }
151  break;
152  case SRT_CMPL:
153  {
154  if (is.ranges() == 1) {
155  GECODE_ME_FAIL(_s.exclude(home, is.min(), is.max()));
157  _s.include(home,
159  is.min()-1) );
161  _s.include(home, is.max()+1,
162  Set::Limits::max) );
163  } else {
164  IntSetRanges rd1(is);
166  GECODE_ME_FAIL(_s.includeI(home, rdC1));
167  IntSetRanges rd2(is);
169  GECODE_ME_FAIL(_s.intersectI(home, rdC2));
170  }
171  }
172  break;
173  default:
174  throw Set::UnknownRelation("Set::dom");
175  }
176  }
177 
178  void
179  dom(Home home, SetVar s, SetRelType r, int i, BoolVar b) {
180  Set::Limits::check(i, "Set::dom");
181  IntSet d(i,i);
182  dom(home, s, r, d, b);
183  }
184 
185  void
186  dom(Home home, SetVar s, SetRelType r, int i, int j, BoolVar b) {
187  Set::Limits::check(i, "Set::dom");
188  Set::Limits::check(j, "Set::dom");
189  IntSet d(i,j);
190  dom(home, s, r, d, b);
191  }
192 
193  void
194  dom(Home home, SetVar s, SetRelType r, const IntSet& is, BoolVar b) {
195  Set::Limits::check(is, "Set::dom");
196  if (home.failed()) return;
197  switch (r) {
198  case SRT_EQ:
199  {
200  Set::ConstSetView cv(home, is);
203  Set::ConstSetView>::post(home, s, cv, b)));
204  }
205  break;
206  case SRT_LQ:
207  {
208  Set::ConstSetView cv(home, is);
211  ::post(home,s,cv,b)));
212  }
213  break;
214  case SRT_LE:
215  {
216  Set::ConstSetView cv(home, is);
219  ::post(home,s,cv,b)));
220  }
221  break;
222  case SRT_GQ:
223  {
224  Set::ConstSetView cv(home, is);
227  ::post(home,cv,s,b)));
228  }
229  break;
230  case SRT_GR:
231  {
232  Set::ConstSetView cv(home, is);
235  ::post(home,cv,s,b)));
236  }
237  break;
238  case SRT_NQ:
239  {
240  BoolVar notb(home,0,1);
241  rel(home, b, IRT_NQ, notb);
242  Set::ConstSetView cv(home, is);
245  Set::ConstSetView>::post(home, s, cv, notb)));
246  }
247  break;
248  case SRT_SUB:
249  {
250  Set::ConstSetView cv(home, is);
253  ::post(home, s, cv, b)));
254  }
255  break;
256  case SRT_SUP:
257  {
258  Set::ConstSetView cv(home, is);
261  ::post(home, cv, s, b)));
262  }
263  break;
264  case SRT_DISJ:
265  {
266  // x||y <=> b is equivalent to
267  // ( y <= complement(x) and x<=complement(y) ) <=> b
268 
269  // compute complement of is
270  IntSetRanges dr1(is);
272  IntSet dcompl(dc1);
273  Set::ConstSetView cvcompl(home, dcompl);
276  ::post(home, s, cvcompl, b)));
277  }
278  break;
279  case SRT_CMPL:
280  {
281  Set::SetView sv(s);
282 
283  IntSetRanges dr1(is);
285  IntSet dcompl(dc1);
286  Set::ConstSetView cvcompl(home, dcompl);
287 
290  ::post(home, sv, cvcompl, b)));
291  }
292  break;
293  default:
294  throw Set::UnknownRelation("Set::dom");
295  }
296  }
297 
298 }
299 
300 // STATISTICS: set-post