Generated on Sat Feb 7 2015 02:01:15 for Gecode by doxygen 1.8.9.1
val.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>
49  class ValInfo {
50  public:
52  View view;
54  bool a;
56  void init(View x, int n);
58  void update(Space& home, bool share, ValInfo<View>& vi);
60  bool doval(void) const;
62  bool dodom(void) const;
64  void assigned(void);
66  void removed(int i);
68  void done(void);
69  };
70 
71  template<class View>
72  forceinline void
73  ValInfo<View>::init(View x, int) {
74  view = x; a = false;
75  }
76 
77  template<class View>
78  forceinline void
79  ValInfo<View>::update(Space& home, bool share, ValInfo<View>& vi) {
80  view.update(home,share,vi.view); a = vi.a;
81  }
82 
83  template<class View>
84  forceinline bool
85  ValInfo<View>::doval(void) const {
86  return !a && view.assigned();
87  }
88 
89  template<class View>
90  forceinline bool
91  ValInfo<View>::dodom(void) const {
92  return false;
93  }
94 
95  template<class View>
96  forceinline void
98  a = true;
99  }
100 
101  template<class View>
102  forceinline void
104 
105  template<class View>
106  forceinline void
108 
109 
110  // Propagate assigned views for x
111  template<class View, class Offset, class Info>
112  ExecStatus
113  doprop_val(Space& home, int n, Info* x, Offset& ox,
114  Info* y, Offset& oy,
115  int& n_na, ProcessStack& xa, ProcessStack& ya) {
116  do {
117  int i = xa.pop();
118  int j = ox(x[i].view).val();
119  // Assign the y variable to i (or test if already assigned!)
120  {
121  ModEvent me = oy(y[j].view).eq(home,i);
122  if (me_failed(me)) {
123  return ES_FAILED;
124  }
125  // Record that y[j] has been assigned and must be propagated
126  if (me_modified(me))
127  ya.push(j);
128  }
129  // Prune the value j from all x variables
130  for (int k=i; k--; ) {
131  ModEvent me = ox(x[k].view).nq(home,j);
132  if (me_failed(me)) {
133  return ES_FAILED;
134  }
135  if (me_modified(me)) {
136  if (me == ME_INT_VAL) {
137  // Record that x[k] has been assigned and must be propagated
138  xa.push(k);
139  } else {
140  // One value has been removed and this removal does not need
141  // to be propagated again: after all y[j] = i, so it holds
142  // that y[j] != k.
143  x[k].removed(j);
144  }
145  }
146  }
147  // The same for the other views
148  for (int k=i+1; k<n; k++) {
149  ModEvent me = ox(x[k].view).nq(home,j);
150  if (me_failed(me)) {
151  return ES_FAILED;
152  }
153  if (me_modified(me)) {
154  if (me == ME_INT_VAL) {
155  // Record that x[k] has been assigned and must be propagated
156  xa.push(k);
157  } else {
158  // One value has been removed and this removal does not need
159  // to be propagated again: after all y[j] = i, so it holds
160  // that y[j] != k.
161  x[k].removed(j);
162  }
163  }
164  }
165  x[i].assigned(); n_na--;
166  } while (!xa.empty());
167  return ES_OK;
168  }
169 
170  // Just do a test whether a call to the routine is necessary
171  template<class View, class Offset, class Info>
173  prop_val(Space& home, int n, Info* x, Offset& ox, Info* y, Offset& oy,
174  int& n_na, ProcessStack& xa, ProcessStack& ya) {
175  if (xa.empty())
176  return ES_OK;
177  return doprop_val<View,Offset,Info>(home,n,x,ox,y,oy,n_na,xa,ya);
178  }
179 
180  /*
181  * The actual propagator
182  *
183  */
184  template<class View, class Offset, bool shared>
187  Offset& ox, Offset& oy)
188  : Base<ValInfo<View>,Offset,PC_INT_VAL>(home,n,xy,ox,oy) {}
189 
190  template<class View, class Offset, bool shared>
192  Val<View,Offset,shared>::Val(Space& home, bool share,
194  : Base<ValInfo<View>,Offset,PC_INT_VAL>(home,share,p) {}
195 
196  template<class View, class Offset, bool shared>
197  Actor*
199  return new (home) Val<View,Offset,shared>(home,share,*this);
200  }
201 
202  template<class View, class Offset, bool shared>
203  ExecStatus
205  Region r(home);
206  ProcessStack xa(r,n);
207  ProcessStack ya(r,n);
208 
209  ValInfo<View>* x = xy;
210  ValInfo<View>* y = xy+n;
211 
212  // Scan x and y for assigned but not yet propagated views
213  for (int i = n; i--; ) {
214  if (x[i].doval()) xa.push(i);
215  if (y[i].doval()) ya.push(i);
216  }
217 
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());
227 
228  if (n_na == 0)
229  return home.ES_SUBSUMED(*this);
230  return shared ? ES_NOFIX : ES_FIX;
231  }
232 
233  template<class View, class Offset, bool shared>
234  ExecStatus
236  Offset& ox, Offset& oy) {
237  assert(n > 0);
238  if (n == 1) {
239  GECODE_ME_CHECK(ox(xy[0].view).eq(home,0));
240  GECODE_ME_CHECK(oy(xy[1].view).eq(home,0));
241  return ES_OK;
242  }
243  for (int i=n; i--; ) {
244  GECODE_ME_CHECK(ox(xy[i ].view).gq(home,0));
245  GECODE_ME_CHECK(ox(xy[i ].view).le(home,n));
246  GECODE_ME_CHECK(oy(xy[i+n].view).gq(home,0));
247  GECODE_ME_CHECK(oy(xy[i+n].view).le(home,n));
248  }
249  (void) new (home) Val<View,Offset,shared>(home,n,xy,ox,oy);
250  return ES_OK;
251  }
252 
253 }}}
254 
255 // STATISTICS: int-prop
256 
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
bool doval(void) const
Check whether propagation for assignment is to be done.
Definition: val.hpp:85
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
bool a
Whether it has been propagated that view is assigned.
Definition: val.hpp:54
int ModEvent
Type for modification events.
Definition: core.hpp:146
void done(void)
Update the cardinality and bounds information after pruning.
Definition: val.hpp:107
static ExecStatus post(Home home, int n, ValInfo< View > *xy, Offset &ox, Offset &oy)
Post propagator for channeling.
Definition: val.hpp:235
Handle to region.
Definition: region.hpp:61
Propagation has computed fixpoint.
Definition: core.hpp:528
Computation spaces.
Definition: core.hpp:1362
Combine view with information for value propagation.
Definition: val.hpp:49
Naive channel propagator.
Definition: channel.hh:99
Base-class for both propagators and branchers.
Definition: core.hpp:666
void update(Space &home, bool share, ValInfo< View > &vi)
Update during cloning.
Definition: val.hpp:79
#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)
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
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: val.hpp:198
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
Converter with fixed offset.
Definition: view.hpp:617
Val(Space &home, bool share, Val &p)
Constructor for cloning p.
void removed(int i)
Record that one value got removed.
Definition: val.hpp:103
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Base-class for channel propagators.
Definition: channel.hh:59
ExecStatus
Definition: core.hpp:523
#define forceinline
Definition: config.hpp:132
Stack with fixed number of elements.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: val.hpp:204
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:63
T pop(void)
Pop topmost element from stack and return it.
Execution is okay.
Definition: core.hpp:527
Propagation has not computed fixpoint.
Definition: core.hpp:526
bool shared(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether views share same variable.
Definition: view.hpp:662
void assigned(void)
Record that view got assigned.
Definition: val.hpp:97
Gecode toplevel namespace
View view
The view.
Definition: val.hpp:52
void init(View x, int n)
Initialize.
Definition: val.hpp:73
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
ExecStatus doprop_val(Space &home, int n, Info *x, Offset &ox, Info *y, Offset &oy, int &n_na, ProcessStack &xa, ProcessStack &ya)
Definition: val.hpp:113
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:82
bool dodom(void) const
Check whether propagation for domain is to be done.
Definition: val.hpp:91