Generated on Thu Mar 13 2014 04:39:29 for Gecode by doxygen 1.8.1.2
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: 2011-04-02 00:26:13 +1100 (Sat, 02 Apr 2011) $ by $Author: tack $
15  * $Revision: 11858 $
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