Generated on Sat Jun 2 2018 07:17:44 for Gecode by doxygen 1.8.13
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  * 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 Int { namespace Channel {
39 
44  template<class View, class Offset>
45  class DomInfo {
46  public:
48  View view;
50  unsigned int size;
52  int min;
54  int max;
56  void init(View x, int n);
58  void update(Space& home, DomInfo<View,Offset>& vcb);
60  bool doval(void) const;
62  bool dodom(void) const;
64  void assigned(void);
66  void removed(int i);
68  void done(Offset& o);
69  };
70 
71  template<class View, class Offset>
72  forceinline void
74  view = x;
75  size = static_cast<unsigned int>(n);
76  min = 0;
77  max = n-1;
78  }
79 
80  template<class View, class Offset>
81  forceinline void
83  view.update(home,di.view);
84  size = di.size;
85  min = di.min;
86  max = di.max;
87  }
88 
89  template<class View, class Offset>
90  forceinline bool
92  return (size != 1) && view.assigned();
93  }
94 
95  template<class View, class Offset>
96  forceinline bool
98  return size != view.size();
99  }
100 
101  template<class View, class Offset>
102  forceinline void
104  size = 1;
105  }
106 
107  template<class View, class Offset>
108  forceinline void
110  size--;
111  if (i == min)
112  min++;
113  else if (i == max)
114  max--;
115  }
116 
117  template<class View, class Offset>
118  forceinline void
120  size = view.size();
121  min = o(view).min();
122  max = o(view).max();
123  }
124 
125  // Propagate domain information from x to y
126  template<class View, class Offset>
127  ExecStatus
130  for (int i = n; i--; )
131  // Only views with not yet propagated missing values
132  if (x[i].dodom()) {
133  // Iterate the values in the complement of x[i]
135  xir(ox(x[i].view));
137  xirc(x[i].min,x[i].max,xir);
140  while (jv()) {
141  // j is not in the domain of x[i], so prune i from y[j]
142  int j = jv.val();
143  ModEvent me = oy(y[j].view).nq(home,i);
144  if (me_failed(me))
145  return ES_FAILED;
146  if (me_modified(me)) {
147  if (me == ME_INT_VAL) {
148  // Record that y[j] has been assigned and must be propagated
149  ya.push(j);
150  } else {
151  // Obvious as x[i] is different from j
152  y[j].removed(i);
153  }
154  }
155  ++jv;
156  }
157  // Update which values have been propagated and what are the new bounds
158  x[i].done(ox);
159  }
160  return ES_OK;
161  }
162 
163  /*
164  * The actual propagator
165  *
166  */
167  template<class View, class Offset, bool shared>
170  Offset& ox, Offset& oy)
171  : Base<DomInfo<View,Offset>,Offset,PC_INT_DOM>(home,n,xy,ox,oy) {}
172 
173  template<class View, class Offset, bool shared>
177 
178  template<class View, class Offset, bool shared>
179  Actor*
181  return new (home) Dom<View,Offset,shared>(home,*this);
182  }
183 
184  template<class View, class Offset, bool shared>
185  PropCost
187  const ModEventDelta& med) const {
188  if (View::me(med) == ME_INT_VAL)
190  else
192  }
193 
194  template<class View, class Offset, bool shared>
195  ExecStatus
197  Region r;
198  ProcessStack xa(r,n);
199  ProcessStack ya(r,n);
200 
203 
204  if (View::me(med) == ME_INT_VAL) {
205  // Scan x and y for assigned but not yet propagated views
206  for (int i = n; i--; ) {
207  if (x[i].doval()) xa.push(i);
208  if (y[i].doval()) ya.push(i);
209  }
210 
211  if (shared) {
212  do {
213  // Propagate assigned views for x
215  (home,n,x,ox,y,oy,n_na,xa,ya)));
216  // Propagate assigned views for y
218  (home,n,y,oy,x,ox,n_na,ya,xa)));
219  assert(ya.empty());
220  } while (!xa.empty() || !ya.empty());
221  return home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
222  } else {
223  do {
224  // Propagate assigned views for x
226  (home,n,x,ox,y,oy,n_na,xa,ya)));
227  // Propagate assigned views for y
229  (home,n,y,oy,x,ox,n_na,ya,xa)));
230  assert(ya.empty());
231  } while (!xa.empty());
232  return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM));
233  }
234  }
235 
236  // Process changed views for y
237  // This propagates from y to x and possibly records xs that
238  // got assigned
239  GECODE_ES_CHECK(prop_dom(home,n,y,oy,x,ox,xa));
240 
241  // Process assigned views for x
243  (home,n,x,ox,y,oy,n_na,xa,ya)));
244 
245  // Perform domain consistent propagation for distinct on the x views
246  if (dc.available()) {
247  GECODE_ES_CHECK(dc.sync());
248  } else {
249  ViewArray<View> xv(r,n);
250  for (int i=n; i--; )
251  xv[i] = x[i].view;
252  GECODE_ES_CHECK(dc.init(home,xv));
253  }
254  bool assigned;
255  GECODE_ES_CHECK(dc.propagate(home,assigned));
256  if (assigned) {
257  // This has assigned some more views in x which goes unnoticed
258  // (that is, not recorded in xa). This must be checked and propagated
259  // to the y views, however the distinctness on x is already
260  // propagated.
261  for (int i=n; i--; )
262  if (x[i].doval()) {
263  int j = ox(x[i].view).val();
264  // Assign the y variable to i (or test if already assigned!)
265  ModEvent me = oy(y[j].view).eq(home,i);
266  if (me_failed(me))
267  return ES_FAILED;
268  if (me_modified(me)) {
269  // Record that y[j] has been assigned and must be propagated
270  assert(me == ME_INT_VAL);
271  // Otherwise the modification event would not be ME_INT_VAL
272  ya.push(j);
273  }
274  x[i].assigned(); n_na--;
275  }
276  }
277 
278  // Process changed views for x
279  // This propagates from x to y and possibly records ys that
280  // got assigned
281  GECODE_ES_CHECK(prop_dom(home,n,x,ox,y,oy,ya));
282 
283  // Process assigned view again (some might have been found above)
284  while (!xa.empty() || !ya.empty()) {
285  // Process assigned views for x
287  (home,n,x,ox,y,oy,n_na,xa,ya)));
288  // Process assigned views for y
290  (home,n,y,oy,x,ox,n_na,ya,xa)));
291  };
292 
293  if (shared) {
294  for (int i=2*n; i--; )
295  if (!xy[i].view.assigned())
296  return ES_NOFIX;
297  return home.ES_SUBSUMED(*this);
298  } else {
299  return (n_na == 0) ? home.ES_SUBSUMED(*this) : ES_FIX;
300  }
301  }
302 
303  template<class View, class Offset, bool shared>
304  ExecStatus
306  Offset& ox, Offset& oy) {
307  assert(n > 0);
308  if (n == 1) {
309  GECODE_ME_CHECK(ox(xy[0].view).eq(home,0));
310  GECODE_ME_CHECK(oy(xy[1].view).eq(home,0));
311  return ES_OK;
312  }
313  for (int i=n; i--; ) {
314  GECODE_ME_CHECK(ox(xy[i ].view).gq(home,0));
315  GECODE_ME_CHECK(ox(xy[i ].view).le(home,n));
316  GECODE_ME_CHECK(oy(xy[i+n].view).gq(home,0));
317  GECODE_ME_CHECK(oy(xy[i+n].view).le(home,n));
318  }
319  (void) new (home) Dom<View,Offset,shared>(home,n,xy,ox,oy);
320  return ES_OK;
321  }
322 
323 }}}
324 
325 // STATISTICS: int-prop
326 
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:169
Distinct::DomCtrl< View > dc
Propagation controller for propagating distinct.
Definition: channel.hh:142
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:4706
bool dodom(void) const
Check whether propagation for domain is to be done.
Definition: dom.hpp:97
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3482
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition: core.hpp:3495
Offset ox
Offset transformation for x variables.
Definition: channel.hh:62
bool doval(void) const
Check whether propagation for assignment is to be done.
Definition: dom.hpp:91
bool empty(void) const
Test whether stack is empty.
int ModEvent
Type for modification events.
Definition: core.hpp:62
DomInfo< View, Offset > * xy
View and information for both x and y.
Definition: channel.hh:66
Offset oy
Offset transformation for y variables.
Definition: channel.hh:64
void done(Offset &o)
Update the size and bounds information after pruning.
Definition: dom.hpp:119
Handle to region.
Definition: region.hpp:53
#define forceinline
Definition: config.hpp:185
Propagation has computed fixpoint.
Definition: core.hpp:476
void update(Space &home, DomInfo< View, Offset > &vcb)
Update during cloning.
Definition: dom.hpp:82
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: dom.hpp:186
Computation spaces.
Definition: core.hpp:1701
Base-class for both propagators and branchers.
Definition: core.hpp:627
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:91
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
Gecode::IntArgs i(4, 1, 2, 3, 4)
void assigned(void)
Record that view got assigned.
Definition: dom.hpp:103
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Execution has resulted in failure.
Definition: core.hpp:473
int n
Number of views (actually twice as many for both x and y)
Definition: channel.hh:58
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:128
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1034
static ExecStatus post(Home home, int n, DomInfo< View, Offset > *xy, Offset &ox, Offset &oy)
Post propagator for channeling on xy.
Definition: dom.hpp:305
Value iterator from range iterator.
Domain consistent channel propagator.
Definition: channel.hh:134
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: dom.hpp:196
Expensive.
Definition: core.hpp:513
View arrays.
Definition: array.hpp:224
unsigned int size
Last propagated size.
Definition: dom.hpp:50
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
Definition: core.hpp:3488
Converter with fixed offset.
Definition: view.hpp:635
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:765
Combine view with information for domain propagation.
Definition: dom.hpp:45
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:765
Base-class for channel propagators.
Definition: channel.hh:55
Propagation cost.
Definition: core.hpp:485
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: dom.hpp:180
ExecStatus
Definition: core.hpp:471
void init(View x, int n)
Initialize.
Definition: dom.hpp:73
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
int max
Last propagated maximum.
Definition: dom.hpp:54
Stack with fixed number of elements.
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:59
int min
Last propagated minimum.
Definition: dom.hpp:52
Post propagator for SetVar x
Definition: set.hh:765
Execution is okay.
Definition: core.hpp:475
View view
The view.
Definition: dom.hpp:48
Propagation has not computed fixpoint.
Definition: core.hpp:474
Dom(Space &home, Dom &p)
Constructor for cloning p.
bool shared(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether views share same variable.
Definition: view.hpp:735
Gecode toplevel namespace
void removed(int i)
Record that one value got removed.
Definition: dom.hpp:109
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
Home class for posting propagators
Definition: core.hpp:853
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:54
int n_na
Total number of not assigned views (not known to be assigned)
Definition: channel.hh:60
Range iterator for computing the complement (described by values)