Generated on Sat Aug 25 2012 03:32:45 for Gecode by doxygen 1.8.1.2
lq.hpp
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  * Copyright:
7  * Guido Tack, 2011
8  *
9  * Last modified:
10  * $Date: 2011-08-25 00:34:16 +1000 (Thu, 25 Aug 2011) $ by $Author: tack $
11  * $Revision: 12346 $
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 namespace Gecode { namespace Set { namespace Rel {
39 
44  protected:
46  unsigned int xsize;
50  int* ub;
52  bool xlm;
54  bool xum;
56  bool ylm;
58  bool yum;
60  void set(int i, bool j) {
61  if (j)
62  b.set(i);
63  else
64  b.clear(i);
65  }
66 
68  class CSIter {
69  public:
73  unsigned int i;
75  int xoff;
77  int yoff;
79  void operator++ (void) {
80  i++;
81  while (i<cs->xsize && !cs->b.get(xoff+2*i+yoff))
82  i++;
83  }
85  CSIter(void) {}
87  CSIter(CharacteristicSets& cs0, int xoff0, int yoff0)
88  : cs(&cs0), i(-1), xoff(xoff0), yoff(yoff0) {
89  ++(*this);
90  }
92  bool operator() (void) const { return i<cs->xsize; }
94  int val(void) const { return cs->ub[i]; }
95  };
96 
97  public:
99  template<class View0, class View1>
100  CharacteristicSets(Region& re, View0 x, View1 y);
101 
103  bool xmin(int i) const { return b.get(2*i); }
105  bool xmax(int i) const { return b.get(2*i+1); }
107  bool ymin(int i) const { return b.get(2*xsize+2*i); }
109  bool ymax(int i) const { return b.get(2*xsize+2*i+1); }
110 
112  void xmin(int i, bool j) { set(2*i,j); }
114  void xmax(int i, bool j) { set(2*i+1,j); }
116  void ymin(int i, bool j) { set(2*xsize+2*i,j); }
118  void ymax(int i, bool j) { set(2*xsize+2*i+1,j); }
119 
121  ModEvent xlq(int i, bool j) {
122  if (!j) {
123  if (xmin(i)) return ME_SET_FAILED;
124  if (xmax(i)) {
125  xmax(i,false);
126  xum=true;
127  }
128  }
129  return ME_SET_NONE;
130  }
132  ModEvent xgq(int i, bool j) {
133  if (j) {
134  if (!xmax(i)) return ME_SET_FAILED;
135  if (!xmin(i)) {
136  xmin(i,true);
137  xlm=true;
138  }
139  }
140  return ME_SET_NONE;
141  }
143  ModEvent ylq(int i, bool j) {
144  if (!j) {
145  if (ymin(i)) return ME_SET_FAILED;
146  if (ymax(i)) {
147  ymax(i,false);
148  yum=true;
149  }
150  }
151  return ME_SET_NONE;
152  }
154  ModEvent ygq(int i, bool j) {
155  if (j) {
156  if (!ymax(i)) return ME_SET_FAILED;
157  if (!ymin(i)) {
158  ymin(i,true);
159  ylm=true;
160  }
161  }
162  return ME_SET_NONE;
163  }
164 
166  int size(void) const { return xsize; }
167 
169  template<class View0, class View1>
170  ExecStatus prune(Space& home, View0 x, View1 y) {
171  if (xlm) {
172  CSIter i(*this,0,0);
174  GECODE_ME_CHECK(x.includeI(home,ir));
175  }
176  if (xum) {
177  CSIter i(*this,0,1);
179  GECODE_ME_CHECK(x.intersectI(home,ir));
180  }
181  if (ylm) {
182  CSIter i(*this,2*xsize,0);
184  GECODE_ME_CHECK(y.includeI(home,ir));
185  }
186  if (yum) {
187  CSIter i(*this,2*xsize,1);
189  GECODE_ME_CHECK(y.intersectI(home,ir));
190  }
191  return ES_OK;
192  }
193 
194  };
195 
196  template<class View0, class View1>
198  : xlm(false), xum(false), ylm(false), yum(false) {
199  LubRanges<View0> xlub(x);
200  LubRanges<View1> ylub(y);
202  Iter::Ranges::Cache xylubc(re,xylub);
203  xsize = Iter::Ranges::size(xylubc);
204  b.init(re,4*xsize);
205  ub = re.alloc<int>(xsize);
206  xylubc.reset();
208  LubRanges<View0> xur(x);
209  GlbRanges<View0> xlr(x);
210  LubRanges<View1> yur(y);
211  GlbRanges<View1> ylr(y);
216  for (int i=0; xylubv(); ++xylubv, ++i) {
217  ub[i] = xylubv.val();
218  if (xlv() && xylubv.val()==xlv.val()) {
219  b.set(2*i);
220  ++xlv;
221  }
222  if (xuv() && xylubv.val()==xuv.val()) {
223  b.set(2*i+1);
224  ++xuv;
225  }
226  if (ylv() && xylubv.val()==ylv.val()) {
227  b.set(2*xsize+2*i);
228  ++ylv;
229  }
230  if (yuv() && xylubv.val()==yuv.val()) {
231  b.set(2*xsize+2*i+1);
232  ++yuv;
233  }
234  }
235  }
236 
237  template<class View0, class View1, bool strict>
239  Lq<View0,View1,strict>::Lq(Home home, View0 x, View1 y)
240  : MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y) {}
241 
242  template<class View0, class View1, bool strict>
244  Lq<View0,View1,strict>::Lq(Space& home, bool share, Lq& p)
245  : MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,share,p) {}
246 
247  template<class View0, class View1, bool strict>
248  ExecStatus
249  Lq<View0,View1,strict>::post(Home home, View0 x, View1 y) {
250  if (strict)
251  GECODE_ME_CHECK(y.cardMin(home,1));
252  (void) new (home) Lq(home,x,y);
253  return ES_OK;
254  }
255 
256  template<class View0, class View1, bool strict>
257  Actor*
258  Lq<View0,View1,strict>::copy(Space& home, bool share) {
259  return new (home) Lq(home,share,*this);
260  }
261 
262  template<class View0, class View1, bool strict>
263  ExecStatus
265  if ( (!strict) && x1.cardMax()==0) {
266  GECODE_ME_CHECK(x0.cardMax(home,0));
267  }
268 
269  if (x0.cardMax()==0) {
270  return home.ES_SUBSUMED(*this);
271  }
272 
273  if (x0.glbMin() < x1.lubMin())
274  return ES_FAILED;
275  if (x1.glbMin() < x0.lubMin())
276  return home.ES_SUBSUMED(*this);
277 
278  bool assigned = x0.assigned() && x1.assigned();
279 
280  Region re(home);
281  CharacteristicSets cs(re,x0,x1);
282 
283  /*
284  * State 1
285  *
286  */
287  int i=0;
288  int firsti=0;
289  int n=cs.size();
290  while ((i<n) && cs.xmin(i) == cs.ymax(i)) {
291  // case: =, >=
292  GECODE_ME_CHECK(cs.xlq(i,cs.ymax(i)));
293  GECODE_ME_CHECK(cs.ygq(i,cs.xmin(i)));
294  i++;
295  }
296 
297  if (i == n) {// case: $
298  if (strict) {
299  return ES_FAILED;
300  } else {
301  GECODE_ES_CHECK(cs.prune(home,x0,x1));
302  return home.ES_SUBSUMED(*this);
303  }
304  }
305 
306  // Possible cases left: <, <=, > (yields failure), ?
307  GECODE_ME_CHECK(cs.xlq(i,cs.ymax(i)));
308  GECODE_ME_CHECK(cs.ygq(i,cs.xmin(i)));
309 
310  if (cs.xmax(i) < cs.ymin(i)) { // case: < (after tell)
311  GECODE_ES_CHECK(cs.prune(home,x0,x1));
312  return home.ES_SUBSUMED(*this);
313  }
314 
315  firsti=i;
316 
317  /*
318  * State 2
319  * prefix: (?|<=)
320  *
321  */
322  i++;
323 
324  while ((i < n) &&
325  (cs.xmin(i) == cs.ymax(i)) &&
326  (cs.xmax(i) == cs.ymin(i))) { // case: =
327  i++;
328  }
329 
330  if (i == n) { // case: $
331  if (strict)
332  goto rewrite_le;
333  else
334  goto rewrite_lq;
335  }
336 
337  if (cs.xmax(i) < cs.ymin(i)) // case: <
338  goto rewrite_lq;
339 
340  if (cs.xmin(i) > cs.ymax(i)) // case: >
341  goto rewrite_le;
342 
343  if (cs.xmax(i) <= cs.ymin(i)) {
344  // case: <= (invariant: not =, <)
345  /*
346  * State 3
347  * prefix: (?|<=),<=
348  *
349  */
350  i++;
351 
352  while ((i < n) && (cs.xmax(i) == cs.ymin(i))) {// case: <=, =
353  i++;
354  }
355 
356  if (i == n) { // case: $
357  if (strict) {
358  GECODE_ES_CHECK(cs.prune(home,x0,x1));
359  return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
360  } else {
361  goto rewrite_lq;
362  }
363  }
364 
365  if (cs.xmax(i) < cs.ymin(i)) // case: <
366  goto rewrite_lq;
367 
368  GECODE_ES_CHECK(cs.prune(home,x0,x1));
369  return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
370  }
371 
372  if (cs.xmin(i) >= cs.ymax(i)) {
373  // case: >= (invariant: not =, >)
374  /*
375  * State 4
376  * prefix: (?|<=) >=
377  *
378  */
379  i++;
380 
381  while ((i < n) && (cs.xmin(i) == cs.ymax(i))) {
382  // case: >=, =
383  i++;
384  }
385 
386  if (i == n) { // case: $
387  if (strict) {
388  goto rewrite_le;
389  } else {
390  GECODE_ES_CHECK(cs.prune(home,x0,x1));
391  return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
392  }
393  }
394 
395  if (cs.xmin(i) > cs.ymax(i)) // case: >
396  goto rewrite_le;
397 
398  GECODE_ES_CHECK(cs.prune(home,x0,x1));
399  return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
400  }
401 
402  GECODE_ES_CHECK(cs.prune(home,x0,x1));
403  return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
404 
405  rewrite_le:
406  GECODE_ME_CHECK(cs.xlq(firsti,false));
407  GECODE_ME_CHECK(cs.ygq(firsti,true));
408  GECODE_ES_CHECK(cs.prune(home,x0,x1));
409  return home.ES_SUBSUMED(*this);
410  rewrite_lq:
411  GECODE_ES_CHECK(cs.prune(home,x0,x1));
412  return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
413  }
414 
415 }}}
416 
417 // STATISTICS: set-prop