Generated on Sat Jan 20 2018 22:21:12 for Gecode by doxygen 1.8.13
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: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
17  * $Revision: 15137 $
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  */
85  }
86 
87  template<class Card>
88  void
90  x.reschedule(home, *this, PC_INT_VAL);
91  k.reschedule(home, *this, PC_INT_VAL);
92  }
93 
94  template<class Card>
98  assert(x.size() > 0);
99 
100  Region r(home);
101  // count[i] denotes how often value k[i].card() occurs in x
102  int* count = r.alloc<int>(k.size());
103 
104  // initialization
105  int sum_min = 0;
106  int removed = 0;
107  for (int i = k.size(); i--; ) {
108  removed += k[i].counter();
109  sum_min += k[i].min();
110  count[i] = 0;
111  }
112 
113  // less than or equal than the total number of free variables
114  // to satisfy the required occurences
115  for (int i = k.size(); i--; )
116  GECODE_ME_CHECK(k[i].lq(home, x.size()+removed-(sum_min - k[i].min())));
117 
118  // number of unassigned views
119  int non = x.size();
120 
121  for (int i = x.size(); i--; )
122  if (x[i].assigned()) {
123  int idx;
124  if (!lookupValue(k,x[i].val(),idx)) {
125  return ES_FAILED;
126  }
127  count[idx]++;
128  non--;
129  }
130 
131  // check for subsumption
132  if (non == 0) {
133  for (int i = k.size(); i--; )
134  GECODE_ME_CHECK((k[i].eq(home, count[i] + k[i].counter())));
135  return home.ES_SUBSUMED(p);
136  }
137 
138  // total number of unsatisfied miminum occurences
139  int req = 0;
140  // number of values whose min requirements are not yet met
141  int n_r = 0;
142  // if only one value is unsatisified single holds the index of that value
143  int single = -1;
144  // total number of assigned views wrt. the original probem size
145  int t_noa = 0;
146 
147  for (int i = k.size(); i--; ) {
148  int ci = count[i] + k[i].counter();
149  t_noa += ci;
150  if (ci == 0) { // this works
151  req += k[i].min();
152  n_r++;
153  single = i;
154  }
155 
156  // number of unassigned views cannot satisfy
157  // the required minimum occurence
158  if (req > non) {
159  return ES_FAILED;
160  }
161  }
162 
163  // if only one unsatisfied occurences is left
164  if ((req == non) && (n_r == 1)) {
165  // This works as the x are not shared!
166  for (int i = x.size(); i--; ) {
167  // try to assign it
168  if (!x[i].assigned()) {
169  GECODE_ME_CHECK(x[i].eq(home, k[single].card()));
170  assert((single >= 0) && (single < k.size()));
171  count[single]++;
172  }
173  }
174  assert((single >= 0) && (single < k.size()));
175 
176  for (int i = k.size(); i--; )
177  GECODE_ME_CHECK(k[i].eq(home, count[i] + k[i].counter()));
178  return home.ES_SUBSUMED(p);
179  }
180 
181  // Bitset for indexes that can be removed
182  Support::BitSet<Region> rem(r,static_cast<unsigned int>(k.size()));
183 
184  for (int i = k.size(); i--; ) {
185  int ci = count[i] + k[i].counter();
186  if (ci == k[i].max()) {
187  assert(!rem.get(i));
188  rem.set(static_cast<unsigned int>(i));
189  k[i].counter(ci);
190  // the solution contains ci occurences of value k[i].card();
191  GECODE_ME_CHECK(k[i].eq(home, ci));
192  } else {
193  if (ci > k[i].max()) {
194  return ES_FAILED;
195  }
196 
197  // in case of variable cardinalities
198  if (Card::propagate) {
199  GECODE_ME_CHECK(k[i].gq(home, ci));
200  int occupied = t_noa - ci;
201  GECODE_ME_CHECK(k[i].lq(home, x.size() + removed - occupied));
202  }
203  }
204  // reset counter
205  count[i] = 0;
206  }
207 
208  // reduce the problem size
209  {
210  int n_x = x.size();
211  for (int i = n_x; i--; ) {
212  if (x[i].assigned()) {
213  int idx;
214  if (!lookupValue(k,x[i].val(),idx)) {
215  return ES_FAILED;
216  }
217  if (rem.get(static_cast<unsigned int>(idx)))
218  x[i]=x[--n_x];
219  }
220  }
221  x.size(n_x);
222  }
223 
224  // remove values
225  {
226  // Values to prune
227  int* pr = r.alloc<int>(k.size());
228  // Number of values to prune
229  int n_pr = 0;
231  pr[n_pr++] = k[i.val()].card();
232  Support::quicksort(pr,n_pr);
233  for (int i = x.size(); i--;) {
234  Iter::Values::Array pi(pr,n_pr);
235  GECODE_ME_CHECK(x[i].minus_v(home, pi, false));
236  }
237  }
238 
239  {
240  bool all_assigned = true;
241 
242  for (int i = x.size(); i--; ) {
243  if (x[i].assigned()) {
244  int idx;
245  if (!lookupValue(k,x[i].val(),idx)) {
246  return ES_FAILED;
247  }
248  count[idx]++;
249  } else {
250  all_assigned = false;
251  }
252  }
253 
254  if (all_assigned) {
255  for (int i = k.size(); i--; )
256  GECODE_ME_CHECK((k[i].eq(home, count[i] + k[i].counter())));
257  return home.ES_SUBSUMED(p);
258  }
259  }
260 
261  if (Card::propagate) {
262  // check again consistency of cardinalities
263  int reqmin = 0;
264  int allmax = 0;
265  for (int i = k.size(); i--; ) {
266  if (k[i].counter() > k[i].max()) {
267  return ES_FAILED;
268  }
269  allmax += k[i].max() - k[i].counter();
270  if (k[i].counter() < k[i].min())
271  reqmin += k[i].min() - k[i].counter();
272  GECODE_ME_CHECK((k[i].lq(home, x.size()+k[i].counter())));
273  }
274 
275  if ((x.size() < reqmin) || (allmax < x.size())) {
276  return ES_FAILED;
277  }
278  }
279 
280  return ES_NOFIX;
281  }
282 
283  template<class Card>
284  ExecStatus
286  return prop_val<Card>(home, *this, x, k);
287  }
288 
289  template<class Card>
290  ExecStatus
293  GECODE_ES_CHECK((postSideConstraints<Card>(home,x,k)));
294 
295  if (isDistinct<Card>(home,x,k))
296  return Distinct::Val<IntView>::post(home,x);
297 
298  (void) new (home) Val<Card>(home,x,k);
299  return ES_OK;
300  }
301 
302 
303 }}}
304 
305 // STATISTICS: int-prop
306 
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
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition: array.hpp:1429
static ExecStatus post(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post propagator for views x and cardinalities k.
Definition: val.hpp:291
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4841
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3614
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
Definition: count.cpp:44
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:53
Val(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Constructor for posting.
Definition: val.hpp:47
Base-class for propagators.
Definition: core.hpp:1092
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: array.hpp:1400
Handle to region.
Definition: region.hpp:61
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost funtion returning high linear.
Definition: val.hpp:79
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:105
Computation spaces.
Definition: core.hpp:1748
Base-class for both propagators and branchers.
Definition: core.hpp:696
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:95
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
Execution has resulted in failure.
Definition: core.hpp:542
ExecStatus prop_val(Space &home, Propagator &p, ViewArray< IntView > &x, ViewArray< Card > &k)
Definition: val.hpp:96
virtual void reschedule(Space &home)
Schedule function.
Definition: val.hpp:89
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: val.hpp:285
const int * pi[]
Definition: photo.cpp:14266
void set(unsigned int i)
Set bit i.
Expensive.
Definition: core.hpp:582
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to all views.
Definition: array.hpp:1408
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:56
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for view array x.
Definition: val.hpp:174
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:71
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: val.hpp:73
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3354
Propagation cost.
Definition: core.hpp:554
ExecStatus
Definition: core.hpp:540
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
#define forceinline
Definition: config.hpp:173
Post propagator for SetVar x
Definition: set.hh:784
Execution is okay.
Definition: core.hpp:544
Propagation has not computed fixpoint.
Definition: core.hpp:543
Gecode toplevel namespace
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Home class for posting propagators
Definition: core.hpp:922
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:82