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  * 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: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
17  * $Revision: 13068 $
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 
bool get(unsigned int i) const
Access value at bit i.
ViewArray< Card > k
Array containing either fixed cardinalities or CardViews.
Definition: gcc.hh:72
Value consistent global cardinality propagator.
Definition: gcc.hh:67
void update(Space &, bool share, ViewArray< View > &a)
Update array to be a clone of array a.
Definition: array.hpp:1387
static ExecStatus post(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post propagator for views x and cardinalities k.
Definition: val.hpp:284
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4041
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
Value iterator for array of integers
bool lookupValue(T &a, int v, int &i)
Return index of v in array a.
Definition: view.hpp:48
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
Val(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Constructor for posting.
Definition: val.hpp:47
Base-class for propagators.
Definition: core.hpp:755
Expensive.
Definition: core.hpp:564
Handle to region.
Definition: region.hpp:61
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:103
Computation spaces.
Definition: core.hpp:1362
Base-class for both propagators and branchers.
Definition: core.hpp:666
Value iterator for values in a bitset.
ViewArray< IntView > x
Views on which to perform value-propagation.
Definition: gcc.hh:70
#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
virtual size_t dispose(Space &home)
Destructor.
Definition: val.hpp:64
Gecode::IntArgs i(4, 1, 2, 3, 4)
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition: sort.hpp:134
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost funtion returning high linear.
Definition: val.hpp:79
Execution has resulted in failure.
Definition: core.hpp:525
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: array.hpp:1400
ExecStatus prop_val(Space &home, Propagator &p, ViewArray< IntView > &x, ViewArray< Card > &k)
Definition: val.hpp:89
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: val.hpp:278
void set(unsigned int i)
Set bit i.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for view array x.
Definition: val.hpp:174
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: val.hpp:73
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntConLevel)
Post propagator for .
Definition: count.cpp:44
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:2877
Propagation cost.
Definition: core.hpp:537
ExecStatus
Definition: core.hpp:523
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
#define forceinline
Definition: config.hpp:132
Execution is okay.
Definition: core.hpp:527
Propagation has not computed fixpoint.
Definition: core.hpp:526
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
Gecode toplevel namespace
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:82