Generated on Mon Aug 27 2012 17:15:39 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  * Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5  *
6  * Contributing authors:
7  * Christian Schulte <schulte@gecode.org>
8  * Guido Tack <tack@gecode.org>
9  *
10  * Copyright:
11  * Patrick Pekczynski, 2005
12  * Christian Schulte, 2009
13  * Guido Tack, 2009
14  *
15  * Last modified:
16  * $Date: 2010-07-15 01:46:18 +1000 (Thu, 15 Jul 2010) $ by $Author: schulte $
17  * $Revision: 11192 $
18  *
19  * This file is part of Gecode, the generic constraint
20  * development environment:
21  * http://www.gecode.org
22  *
23  * Permission is hereby granted, free of charge, to any person obtaining
24  * a copy of this software and associated documentation files (the
25  * "Software"), to deal in the Software without restriction, including
26  * without limitation the rights to use, copy, modify, merge, publish,
27  * distribute, sublicense, and/or sell copies of the Software, and to
28  * permit persons to whom the Software is furnished to do so, subject to
29  * the following conditions:
30  *
31  * The above copyright notice and this permission notice shall be
32  * included in all copies or substantial portions of the Software.
33  *
34  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
35  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
36  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
37  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
38  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
39  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
40  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
41  */
42 
43 namespace Gecode { namespace Int { namespace GCC {
44 
45  template<class Card>
49  : Propagator(home), x(x0), k(k0){
50  x.subscribe(home, *this, PC_INT_VAL);
51  k.subscribe(home, *this, PC_INT_VAL);
52  }
53 
54  template<class Card>
56  Val<Card>::Val(Space& home, bool share, Val<Card>& p)
57  : Propagator(home,share,p) {
58  x.update(home,share, p.x);
59  k.update(home,share, p.k);
60  }
61 
62  template<class Card>
63  forceinline size_t
65  x.cancel(home,*this, PC_INT_VAL);
66  k.cancel(home,*this, PC_INT_VAL);
67  (void) Propagator::dispose(home);
68  return sizeof(*this);
69  }
70 
71  template<class Card>
72  Actor*
73  Val<Card>::copy(Space& home, bool share) {
74  return new (home) Val<Card>(home,share,*this);
75  }
76 
77  template<class Card>
78  PropCost
79  Val<Card>::cost(const Space&, const ModEventDelta&) const {
80  /*
81  * Complexity depends on the time needed for value lookup in \a k
82  * which is O(n log n).
83  */
84  return PropCost::linear(PropCost::HI,x.size());
85  }
86 
87  template<class Card>
91  assert(x.size() > 0);
92 
93  Region r(home);
94  // count[i] denotes how often value k[i].card() occurs in x
95  int* count = r.alloc<int>(k.size());
96 
97  // initialization
98  int sum_min = 0;
99  int removed = 0;
100  for (int i = k.size(); i--; ) {
101  removed += k[i].counter();
102  sum_min += k[i].min();
103  count[i] = 0;
104  }
105 
106  // less than or equal than the total number of free variables
107  // to satisfy the required occurences
108  for (int i = k.size(); i--; )
109  GECODE_ME_CHECK(k[i].lq(home, x.size()+removed-(sum_min - k[i].min())));
110 
111  // number of unassigned views
112  int non = x.size();
113 
114  for (int i = x.size(); i--; )
115  if (x[i].assigned()) {
116  int idx;
117  if (!lookupValue(k,x[i].val(),idx)) {
118  return ES_FAILED;
119  }
120  count[idx]++;
121  non--;
122  }
123 
124  // check for subsumption
125  if (non == 0) {
126  for (int i = k.size(); i--; )
127  GECODE_ME_CHECK((k[i].eq(home, count[i] + k[i].counter())));
128  return home.ES_SUBSUMED(p);
129  }
130 
131  // total number of unsatisfied miminum occurences
132  int req = 0;
133  // number of values whose min requirements are not yet met
134  int n_r = 0;
135  // if only one value is unsatisified single holds the index of that value
136  int single = -1;
137  // total number of assigned views wrt. the original probem size
138  int t_noa = 0;
139 
140  for (int i = k.size(); i--; ) {
141  int ci = count[i] + k[i].counter();
142  t_noa += ci;
143  if (ci == 0) { // this works
144  req += k[i].min();
145  n_r++;
146  single = i;
147  }
148 
149  // number of unassigned views cannot satisfy
150  // the required minimum occurence
151  if (req > non) {
152  return ES_FAILED;
153  }
154  }
155 
156  // if only one unsatisfied occurences is left
157  if ((req == non) && (n_r == 1)) {
158  // This works as the x are not shared!
159  for (int i = x.size(); i--; ) {
160  // try to assign it
161  if (!x[i].assigned()) {
162  GECODE_ME_CHECK(x[i].eq(home, k[single].card()));
163  assert((single >= 0) && (single < k.size()));
164  count[single]++;
165  }
166  }
167  assert((single >= 0) && (single < k.size()));
168 
169  for (int i = k.size(); i--; )
170  GECODE_ME_CHECK(k[i].eq(home, count[i] + k[i].counter()));
171  return home.ES_SUBSUMED(p);
172  }
173 
174  // Bitset for indexes that can be removed
175  Support::BitSet<Region> rem(r,static_cast<unsigned int>(k.size()));
176 
177  for (int i = k.size(); i--; ) {
178  int ci = count[i] + k[i].counter();
179  if (ci == k[i].max()) {
180  assert(!rem.get(i));
181  rem.set(static_cast<unsigned int>(i));
182  k[i].counter(ci);
183  // the solution contains ci occurences of value k[i].card();
184  GECODE_ME_CHECK(k[i].eq(home, ci));
185  } else {
186  if (ci > k[i].max()) {
187  return ES_FAILED;
188  }
189 
190  // in case of variable cardinalities
191  if (Card::propagate) {
192  GECODE_ME_CHECK(k[i].gq(home, ci));
193  int occupied = t_noa - ci;
194  GECODE_ME_CHECK(k[i].lq(home, x.size() + removed - occupied));
195  }
196  }
197  // reset counter
198  count[i] = 0;
199  }
200 
201  // reduce the problem size
202  {
203  int n_x = x.size();
204  for (int i = n_x; i--; ) {
205  if (x[i].assigned()) {
206  int idx;
207  if (!lookupValue(k,x[i].val(),idx)) {
208  return ES_FAILED;
209  }
210  if (rem.get(static_cast<unsigned int>(idx)))
211  x[i]=x[--n_x];
212  }
213  }
214  x.size(n_x);
215  }
216 
217  // remove values
218  {
219  // Values to prune
220  int* p = r.alloc<int>(k.size());
221  // Number of values to prune
222  int n_p = 0;
224  p[n_p++] = k[i.val()].card();
225  Support::quicksort(p,n_p);
226  for (int i = x.size(); i--;) {
227  Iter::Values::Array pi(p,n_p);
228  GECODE_ME_CHECK(x[i].minus_v(home, pi, false));
229  }
230  }
231 
232  {
233  bool all_assigned = true;
234 
235  for (int i = x.size(); i--; ) {
236  if (x[i].assigned()) {
237  int idx;
238  if (!lookupValue(k,x[i].val(),idx)) {
239  return ES_FAILED;
240  }
241  count[idx]++;
242  } else {
243  all_assigned = false;
244  }
245  }
246 
247  if (all_assigned) {
248  for (int i = k.size(); i--; )
249  GECODE_ME_CHECK((k[i].eq(home, count[i] + k[i].counter())));
250  return home.ES_SUBSUMED(p);
251  }
252  }
253 
254  if (Card::propagate) {
255  // check again consistency of cardinalities
256  int reqmin = 0;
257  int allmax = 0;
258  for (int i = k.size(); i--; ) {
259  if (k[i].counter() > k[i].max()) {
260  return ES_FAILED;
261  }
262  allmax += k[i].max() - k[i].counter();
263  if (k[i].counter() < k[i].min())
264  reqmin += k[i].min() - k[i].counter();
265  GECODE_ME_CHECK((k[i].lq(home, x.size()+k[i].counter())));
266  }
267 
268  if ((x.size() < reqmin) || (allmax < x.size())) {
269  return ES_FAILED;
270  }
271  }
272 
273  return ES_NOFIX;
274  }
275 
276  template<class Card>
277  ExecStatus
279  return prop_val<Card>(home, *this, x, k);
280  }
281 
282  template<class Card>
283  ExecStatus
286  GECODE_ES_CHECK((postSideConstraints<Card>(home,x,k)));
287 
288  if (isDistinct<Card>(home,x,k))
289  return Distinct::Val<IntView>::post(home,x);
290 
291  (void) new (home) Val<Card>(home,x,k);
292  return ES_OK;
293  }
294 
295 
296 }}}
297 
298 // STATISTICS: int-prop
299