Generated on Sat Feb 7 2015 02:01:29 for Gecode by doxygen 1.8.9.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: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
13  * $Revision: 13068 $
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>
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
virtual Actor * copy(Space &home, bool)
Copy propagator during cloning.
Definition: disjoint.hpp:93
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:4032
Range iterator for the unknown set.
Definition: var-imp.hpp:406
Range iterator for singleton range.
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1662
int ModEvent
Type for modification events.
Definition: core.hpp:146
Base-class for propagators.
Definition: core.hpp:755
Range iterator for the greatest lower bound.
Definition: var-imp.hpp:363
Handle to region.
Definition: region.hpp:61
Propagator for element with disjointness
Definition: element.hh:186
Propagation has computed fixpoint.
Definition: core.hpp:528
Computation spaces.
Definition: core.hpp:1362
Range iterator for the least upper bound.
Definition: var-imp.hpp:321
Base-class for both propagators and branchers.
Definition: core.hpp:666
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Range iterator for computing intersection (binary)
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: disjoint.hpp:99
Value iterator from range iterator.
Range iterator for integer sets.
Definition: var-imp.hpp:189
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
Definition: integerset.hpp:300
void dispose(Space &home)
Free memory used by this set.
Definition: integerset.hpp:64
static ExecStatus post(Home home, IdxViewArray &x, RView y)
Post propagator for .
Definition: disjoint.hpp:64
const Gecode::PropCond PC_SET_ANY
Propagate when any bound or the cardinality of a view changes.
Definition: var-type.hpp:248
SetExpr inter(const SetVarArgs &x)
Intersection of set variables.
Definition: set-expr.cpp:696
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:2877
Propagation cost.
Definition: core.hpp:537
Range iterator cache
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Definition: idx-view.hpp:129
ExecStatus
Definition: core.hpp:523
#define forceinline
Definition: config.hpp:132
Growing sets of integers.
Definition: var-imp.hpp:209
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: disjoint.hpp:84
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:63
Execution is okay.
Definition: core.hpp:527
int val(void) const
Return current value.
Gecode toplevel namespace
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: disjoint.hpp:78
ElementDisjoint(Space &home, bool share, ElementDisjoint &p)
Constructor for cloning p.
Definition: disjoint.hpp:55
int size(void) const
Return the current size.
Definition: idx-view.hpp:103
void update(Space &home, bool share, IdxViewArray< View > &x)
Cloning.
Definition: idx-view.hpp:144