Generated on Sat Feb 7 2015 02:01:20 for Gecode by doxygen 1.8.9.1
dom.hpp
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  * Contributing authors:
7  * Mikael Lagerkvist <lagerkvist@gecode.org>
8  *
9  * Copyright:
10  * Christian Schulte, 2006
11  * Mikael Lagerkvist, 2006
12  *
13  * Last modified:
14  * $Date: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
15  * $Revision: 13068 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 namespace Gecode { namespace Int { namespace Channel {
43 
48  template<class View, class Offset>
49  class DomInfo {
50  public:
52  View view;
54  unsigned int size;
56  int min;
58  int max;
60  void init(View x, int n);
62  void update(Space& home, bool share, DomInfo<View,Offset>& vcb);
64  bool doval(void) const;
66  bool dodom(void) const;
68  void assigned(void);
70  void removed(int i);
72  void done(Offset& o);
73  };
74 
75  template<class View, class Offset>
76  forceinline void
78  view = x;
79  size = static_cast<unsigned int>(n);
80  min = 0;
81  max = n-1;
82  }
83 
84  template<class View, class Offset>
85  forceinline void
88  view.update(home,share,di.view);
89  size = di.size;
90  min = di.min;
91  max = di.max;
92  }
93 
94  template<class View, class Offset>
95  forceinline bool
97  return (size != 1) && view.assigned();
98  }
99 
100  template<class View, class Offset>
101  forceinline bool
103  return size != view.size();
104  }
105 
106  template<class View, class Offset>
107  forceinline void
109  size = 1;
110  }
111 
112  template<class View, class Offset>
113  forceinline void
115  size--;
116  if (i == min)
117  min++;
118  else if (i == max)
119  max--;
120  }
121 
122  template<class View, class Offset>
123  forceinline void
125  size = view.size();
126  min = o(view).min();
127  max = o(view).max();
128  }
129 
130  // Propagate domain information from x to y
131  template<class View, class Offset>
132  ExecStatus
135  for (int i = n; i--; )
136  // Only views with not yet propagated missing values
137  if (x[i].dodom()) {
138  // Iterate the values in the complement of x[i]
140  xir(ox(x[i].view));
142  xirc(x[i].min,x[i].max,xir);
145  while (jv()) {
146  // j is not in the domain of x[i], so prune i from y[j]
147  int j = jv.val();
148  ModEvent me = oy(y[j].view).nq(home,i);
149  if (me_failed(me))
150  return ES_FAILED;
151  if (me_modified(me)) {
152  if (me == ME_INT_VAL) {
153  // Record that y[j] has been assigned and must be propagated
154  ya.push(j);
155  } else {
156  // Obvious as x[i] is different from j
157  y[j].removed(i);
158  }
159  }
160  ++jv;
161  }
162  // Update which values have been propagated and what are the new bounds
163  x[i].done(ox);
164  }
165  return ES_OK;
166  }
167 
168  /*
169  * The actual propagator
170  *
171  */
172  template<class View, class Offset, bool shared>
175  Offset& ox, Offset& oy)
176  : Base<DomInfo<View,Offset>,Offset,PC_INT_DOM>(home,n,xy,ox,oy) {}
177 
178  template<class View, class Offset, bool shared>
180  Dom<View,Offset,shared>::Dom(Space& home, bool share,
182  : Base<DomInfo<View,Offset>,Offset,PC_INT_DOM>(home,share,p) {}
183 
184  template<class View, class Offset, bool shared>
185  Actor*
187  return new (home) Dom<View,Offset,shared>(home,share,*this);
188  }
189 
190  template<class View, class Offset, bool shared>
191  PropCost
193  const ModEventDelta& med) const {
194  if (View::me(med) == ME_INT_VAL)
196  else
198  }
199 
200  template<class View, class Offset, bool shared>
201  ExecStatus
203  Region r(home);
204  ProcessStack xa(r,n);
205  ProcessStack ya(r,n);
206 
207  DomInfo<View,Offset>* x = xy;
208  DomInfo<View,Offset>* y = xy+n;
209 
210  if (View::me(med) == ME_INT_VAL) {
211  // Scan x and y for assigned but not yet propagated views
212  for (int i = n; i--; ) {
213  if (x[i].doval()) xa.push(i);
214  if (y[i].doval()) ya.push(i);
215  }
216 
217  if (shared) {
218  do {
219  // Propagate assigned views for x
221  (home,n,x,ox,y,oy,n_na,xa,ya)));
222  // Propagate assigned views for y
224  (home,n,y,oy,x,ox,n_na,ya,xa)));
225  assert(ya.empty());
226  } while (!xa.empty() || !ya.empty());
227  return home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
228  } else {
229  do {
230  // Propagate assigned views for x
232  (home,n,x,ox,y,oy,n_na,xa,ya)));
233  // Propagate assigned views for y
235  (home,n,y,oy,x,ox,n_na,ya,xa)));
236  assert(ya.empty());
237  } while (!xa.empty());
238  return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM));
239  }
240  }
241 
242  // Process changed views for y
243  // This propagates from y to x and possibly records xs that
244  // got assigned
245  GECODE_ES_CHECK(prop_dom(home,n,y,oy,x,ox,xa));
246 
247  // Process assigned views for x
249  (home,n,x,ox,y,oy,n_na,xa,ya)));
250 
251  // Perform domain consistent propagation for distinct on the x views
252  if (dc.available()) {
253  GECODE_ES_CHECK(dc.sync(home));
254  } else {
255  ViewArray<View> xv(r,n);
256  for (int i=n; i--; )
257  xv[i] = x[i].view;
258  GECODE_ES_CHECK(dc.init(home,xv));
259  }
260  bool assigned;
261  GECODE_ES_CHECK(dc.propagate(home,assigned));
262  if (assigned) {
263  // This has assigned some more views in x which goes unnoticed
264  // (that is, not recorded in xa). This must be checked and propagated
265  // to the y views, however the distinctness on x is already
266  // propagated.
267  for (int i=n; i--; )
268  if (x[i].doval()) {
269  int j = ox(x[i].view).val();
270  // Assign the y variable to i (or test if already assigned!)
271  ModEvent me = oy(y[j].view).eq(home,i);
272  if (me_failed(me))
273  return ES_FAILED;
274  if (me_modified(me)) {
275  // Record that y[j] has been assigned and must be propagated
276  assert(me == ME_INT_VAL);
277  // Otherwise the modification event would not be ME_INT_VAL
278  ya.push(j);
279  }
280  x[i].assigned(); n_na--;
281  }
282  }
283 
284  // Process changed views for x
285  // This propagates from x to y and possibly records ys that
286  // got assigned
287  GECODE_ES_CHECK(prop_dom(home,n,x,ox,y,oy,ya));
288 
289  // Process assigned view again (some might have been found above)
290  while (!xa.empty() || !ya.empty()) {
291  // Process assigned views for x
293  (home,n,x,ox,y,oy,n_na,xa,ya)));
294  // Process assigned views for y
296  (home,n,y,oy,x,ox,n_na,ya,xa)));
297  };
298 
299  if (shared) {
300  for (int i=2*n; i--; )
301  if (!xy[i].view.assigned())
302  return ES_NOFIX;
303  return home.ES_SUBSUMED(*this);
304  } else {
305  return (n_na == 0) ? home.ES_SUBSUMED(*this) : ES_FIX;
306  }
307  }
308 
309  template<class View, class Offset, bool shared>
310  ExecStatus
312  Offset& ox, Offset& oy) {
313  assert(n > 0);
314  if (n == 1) {
315  GECODE_ME_CHECK(ox(xy[0].view).eq(home,0));
316  GECODE_ME_CHECK(oy(xy[1].view).eq(home,0));
317  return ES_OK;
318  }
319  for (int i=n; i--; ) {
320  GECODE_ME_CHECK(ox(xy[i ].view).gq(home,0));
321  GECODE_ME_CHECK(ox(xy[i ].view).le(home,n));
322  GECODE_ME_CHECK(oy(xy[i+n].view).gq(home,0));
323  GECODE_ME_CHECK(oy(xy[i+n].view).le(home,n));
324  }
325  (void) new (home) Dom<View,Offset,shared>(home,n,xy,ox,oy);
326  return ES_OK;
327  }
328 
329 }}}
330 
331 // STATISTICS: int-prop
332 
void push(const T &x)
Push element x on top of stack.
ExecStatus prop_val(Space &home, int n, Info *x, Offset &ox, Info *y, Offset &oy, int &n_na, ProcessStack &xa, ProcessStack &ya)
Definition: val.hpp:173
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:4032
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
void update(Space &home, bool share, DomInfo< View, Offset > &vcb)
Update during cloning.
Definition: dom.hpp:86
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition: core.hpp:2986
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
int ModEvent
Type for modification events.
Definition: core.hpp:146
Expensive.
Definition: core.hpp:564
void done(Offset &o)
Update the size and bounds information after pruning.
Definition: dom.hpp:124
Handle to region.
Definition: region.hpp:61
Propagation has computed fixpoint.
Definition: core.hpp:528
Computation spaces.
Definition: core.hpp:1362
Base-class for both propagators and branchers.
Definition: core.hpp:666
Range iterator for integer views.
Definition: view.hpp:54
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:84
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
bool empty(void) const
Test whether stack is empty.
Gecode::IntArgs i(4, 1, 2, 3, 4)
void assigned(void)
Record that view got assigned.
Definition: dom.hpp:108
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Execution has resulted in failure.
Definition: core.hpp:525
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
Dom(Space &home, bool share, Dom &p)
Constructor for cloning p.
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
ExecStatus prop_dom(Space &home, int n, DomInfo< View, Offset > *x, Offset &ox, DomInfo< View, Offset > *y, Offset &oy, ProcessStack &ya)
Definition: dom.hpp:133
static ExecStatus post(Home home, int n, DomInfo< View, Offset > *xy, Offset &ox, Offset &oy)
Post propagator for channeling on xy.
Definition: dom.hpp:311
Value iterator from range iterator.
unsigned int size(I &i)
Size of all ranges of range iterator i.
Domain consistent channel propagator.
Definition: channel.hh:136
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: dom.hpp:192
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: dom.hpp:202
View arrays.
Definition: array.hpp:234
unsigned int size
Last propagated size.
Definition: dom.hpp:54
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
Definition: core.hpp:2979
Converter with fixed offset.
Definition: view.hpp:617
Combine view with information for domain propagation.
Definition: dom.hpp:49
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Base-class for channel propagators.
Definition: channel.hh:59
Propagation cost.
Definition: core.hpp:537
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
ExecStatus
Definition: core.hpp:523
void init(View x, int n)
Initialize.
Definition: dom.hpp:77
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
int max
Last propagated maximum.
Definition: dom.hpp:58
bool doval(void) const
Check whether propagation for assignment is to be done.
Definition: dom.hpp:96
#define forceinline
Definition: config.hpp:132
Stack with fixed number of elements.
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:63
int min
Last propagated minimum.
Definition: dom.hpp:56
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: dom.hpp:186
Execution is okay.
Definition: core.hpp:527
View view
The view.
Definition: dom.hpp:52
Propagation has not computed fixpoint.
Definition: core.hpp:526
bool dodom(void) const
Check whether propagation for domain is to be done.
Definition: dom.hpp:102
bool shared(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether views share same variable.
Definition: view.hpp:662
Gecode toplevel namespace
void removed(int i)
Record that one value got removed.
Definition: dom.hpp:114
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58
Range iterator for computing the complement (described by values)