Generated on Fri Aug 24 2012 04:52:20 for Gecode by doxygen 1.8.1.1
disjoint.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  * Christian Schulte <schulte@gecode.org>
6  *
7  * Copyright:
8  * Guido Tack, 2004
9  * Christian Schulte, 2004
10  *
11  * Last modified:
12  * $Date: 2011-08-09 02:04:53 +1000 (Tue, 09 Aug 2011) $ by $Author: schulte $
13  * $Revision: 12253 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 namespace Gecode { namespace Set { namespace Element {
41 
42  template<class SView, class RView>
45  IdxViewArray& iv0,
46  RView y1)
47  : Propagator(home), iv(iv0), x1(y1) {
48 
49  x1.subscribe(home,*this, PC_SET_ANY);
50  iv.subscribe(home,*this, PC_SET_ANY);
51  }
52 
53  template<class SView, class RView>
56  ElementDisjoint& p)
57  : Propagator(home,share,p) {
58  x1.update(home,share,p.x1);
59  iv.update(home,share,p.iv);
60  }
61 
62  template<class SView, class RView>
65  RView x1) {
66  int n = xs.size();
67 
68  // s2 \subseteq {0,...,n-1}
69  Iter::Ranges::Singleton s(0, n-1);
70  GECODE_ME_CHECK(x1.intersectI(home,s));
71  (void) new (home)
72  ElementDisjoint(home,xs,x1);
73  return ES_OK;
74  }
75 
76  template<class SView, class RView>
77  PropCost
79  return PropCost::quadratic(PropCost::LO, iv.size()+2);
80  }
81 
82  template<class SView, class RView>
83  forceinline size_t
85  x1.cancel(home,*this, PC_SET_ANY);
86  iv.cancel(home,*this,PC_SET_ANY);
87  (void) Propagator::dispose(home);
88  return sizeof(*this);
89  }
90 
91  template<class SView, class RView>
92  Actor*
94  return new (home) ElementDisjoint(home,share,*this);
95  }
96 
97  template<class SView, class RView>
100  int n = iv.size();
101 
102  Region r(home);
103 
104  bool fix_flag = false;
105  do {
106  fix_flag = false;
107  // Compute union of all selected elements' lower bounds
108  GlbRanges<RView> x1lb(x1);
110  GLBndSet unionOfSelected(home);
111  for(int i=0; vx1lb(); ++vx1lb) {
112  while (iv[i].idx < vx1lb.val()) i++;
113  GlbRanges<SView> clb(iv[i].view);
114  unionOfSelected.includeI(home,clb);
115  }
116 
117  {
118  LubRanges<RView> x1ub(x1);
120  int i=0;
121  int j=0;
122  // Cancel all elements that are no longer in the upper bound
123  while (vx1ub()) {
124  if (iv[i].idx < vx1ub.val()) {
125  iv[i].view.cancel(home,*this, PC_SET_ANY);
126  i++;
127  continue;
128  }
129  iv[j] = iv[i];
130  ++vx1ub;
131  ++i; ++j;
132  }
133 
134  // cancel the variables with index greater than
135  // max of lub(x1)
136  for (int k=i; k<n; k++) {
137  iv[k].view.cancel(home,*this, PC_SET_ANY);
138  }
139  n = j;
140  iv.size(n);
141  }
142 
143  {
144  UnknownRanges<RView> x1u(x1);
145  Iter::Ranges::Cache x1uc(r,x1u);
147  vx1u(x1uc);
148  int i=0;
149  int j=0;
150  while (vx1u()) {
151  while (iv[i].idx < vx1u.val()) {
152  iv[j] = iv[i];
153  i++; j++;
154  }
155  assert(iv[i].idx == vx1u.val());
156 
157  SView candidate = iv[i].view;
158  int candidateInd = iv[i].idx;
159 
160  GlbRanges<SView> clb(candidate);
161  BndSetRanges uos(unionOfSelected);
163  inter(clb, uos);
164  if (inter()) {
165  ModEvent me = x1.exclude(home,candidateInd);
166  fix_flag |= me_modified(me);
167  GECODE_ME_CHECK(me);
168 
169  candidate.cancel(home,*this, PC_SET_ANY);
170  ++i;
171  ++vx1u;
172  continue;
173  }
174  iv[j] = iv[i];
175  ++vx1u;
176  ++i; ++j;
177  }
178 
179  unionOfSelected.dispose(home);
180 
181  // copy remaining variables
182  for (int k=i; k<n; k++) {
183  iv[j] = iv[k];
184  j++;
185  }
186  n = j;
187  iv.size(n);
188  }
189 
190  if (x1.cardMax()==0) {
191  // Selector is empty, we're done
192  return home.ES_SUBSUMED(*this);
193  }
194 
195  {
196  // remove all elements in a selected variable from
197  // all other selected variables
198  GlbRanges<RView> x1lb(x1);
200  int i=0;
201  for (; vx1lb(); ++vx1lb) {
202  while (iv[i].idx < vx1lb.val()) i++;
203  assert(iv[i].idx==vx1lb.val());
204  GlbRanges<RView> x1lb2(x1);
206  for (int j=0; vx1lb2(); ++vx1lb2) {
207  while (iv[j].idx < vx1lb2.val()) j++;
208  assert(iv[j].idx==vx1lb2.val());
209  if (iv[i].idx!=iv[j].idx) {
210  GlbRanges<SView> xilb(iv[i].view);
211  ModEvent me = iv[j].view.excludeI(home,xilb);
212  fix_flag |= me_modified(me);
213  GECODE_ME_CHECK(me);
214  }
215  }
216  }
217  }
218 
219  // remove all elements from the selector that overlap
220  // with all other possibly selected elements, if
221  // at least two more elements need to be selected
222  if (x1.cardMin()-x1.glbSize() > 1) {
223  UnknownRanges<RView> x1u(x1);
224  Iter::Ranges::Cache x1uc(r,x1u);
226  vx1u(x1uc);
227 
228  for (; vx1u() && x1.cardMin()-x1.glbSize() > 1; ++vx1u) {
229  int i = 0;
230  while (iv[i].idx < vx1u.val()) i++;
231  assert(iv[i].idx == vx1u.val());
232  bool flag=true;
233 
234  UnknownRanges<RView> x1u2(x1);
236  for (; vx1u2(); ++vx1u2) {
237  int j = 0;
238  while (iv[j].idx < vx1u2.val()) j++;
239  assert(iv[j].idx == vx1u2.val());
240  if (iv[i].idx!=iv[j].idx) {
241  GlbRanges<SView> xjlb(iv[j].view);
242  GlbRanges<SView> xilb(iv[i].view);
244  inter(xjlb, xilb);
245  if (!inter()) {
246  flag = false;
247  goto here;
248  }
249  }
250  }
251  here:
252  if (flag) {
253  ModEvent me = x1.exclude(home,iv[i].idx);
254  fix_flag |= me_modified(me);
255  GECODE_ME_CHECK(me);
256  }
257  }
258  }
259 
260  // if exactly two more elements need to be selected
261  // and there is a possible element i such that all other pairs of
262  // elements overlap, select i
263  UnknownRanges<RView> x1u(x1);
264  Iter::Ranges::Cache x1uc(r,x1u);
266  vx1u(x1uc);
267 
268  for (; x1.cardMin()-x1.glbSize() == 2 && vx1u(); ++vx1u) {
269  int i = 0;
270  while (iv[i].idx < vx1u.val()) i++;
271  assert (iv[i].idx == vx1u.val());
272  bool flag=true;
273 
274  UnknownRanges<RView> x1u2(x1);
276  for (; vx1u2(); ++vx1u2) {
277  int j = 0;
278  while (iv[j].idx < vx1u2.val()) j++;
279  assert (iv[j].idx == vx1u2.val());
280  if (iv[i].idx!=iv[j].idx) {
281  UnknownRanges<RView> x1u3(x1);
283  for (; vx1u3(); ++vx1u3) {
284  int k = 0;
285  while (iv[k].idx < vx1u3.val()) k++;
286  assert (iv[k].idx == vx1u3.val());
287  if (iv[j].idx!=iv[k].idx && iv[i].idx!=iv[k].idx) {
288  GlbRanges<SView> xjlb(iv[j].view);
289  GlbRanges<SView> xilb(iv[k].view);
291  inter(xjlb, xilb);
292  if (!inter()) {
293  flag = false;
294  goto here2;
295  }
296  }
297  }
298  }
299  }
300  here2:
301  if (flag) {
302  ModEvent me = x1.include(home,iv[i].idx);
303  fix_flag |= me_modified(me);
304  GECODE_ME_CHECK(me);
305  }
306  }
307  } while (fix_flag);
308 
309  bool allAssigned = true;
310  for (int i=iv.size(); i--;)
311  if (!iv[i].view.assigned()) {
312  allAssigned = false;
313  break;
314  }
315  if (!x1.assigned())
316  allAssigned = false;
317 
318  return allAssigned ? home.ES_SUBSUMED(*this) : ES_FIX;
319  }
320 
321 
322 }}}
323 
324 // STATISTICS: set-prop