Generated on Fri Jan 10 2020 11:38:25 for Gecode by doxygen 1.8.16
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  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  */
38 
39 namespace Gecode { namespace Int { namespace GCC {
40 
41  template<class Card>
45  : Propagator(home), x(x0), k(k0){
46  x.subscribe(home, *this, PC_INT_VAL);
47  k.subscribe(home, *this, PC_INT_VAL);
48  }
49 
50  template<class Card>
53  : Propagator(home,p) {
54  x.update(home, p.x);
55  k.update(home, p.k);
56  }
57 
58  template<class Card>
59  forceinline size_t
61  x.cancel(home,*this, PC_INT_VAL);
62  k.cancel(home,*this, PC_INT_VAL);
63  (void) Propagator::dispose(home);
64  return sizeof(*this);
65  }
66 
67  template<class Card>
68  Actor*
70  return new (home) Val<Card>(home,*this);
71  }
72 
73  template<class Card>
74  PropCost
75  Val<Card>::cost(const Space&, const ModEventDelta&) const {
76  /*
77  * Complexity depends on the time needed for value lookup in \a k
78  * which is O(n log n).
79  */
80  return PropCost::linear(PropCost::HI,x.size());
81  }
82 
83  template<class Card>
84  void
86  x.reschedule(home, *this, PC_INT_VAL);
87  k.reschedule(home, *this, PC_INT_VAL);
88  }
89 
90  template<class Card>
94  assert(x.size() > 0);
95 
96  Region r;
97  // count[i] denotes how often value k[i].card() occurs in x
98  int* count = r.alloc<int>(k.size());
99 
100  // initialization
101  int sum_min = 0;
102  int removed = 0;
103  for (int i=0; i<k.size(); i++) {
104  removed += k[i].counter();
105  sum_min += k[i].min();
106  count[i] = 0;
107  }
108 
109  // less than or equal than the total number of free variables
110  // to satisfy the required occurences
111  for (int i=0; i<k.size(); i++)
112  GECODE_ME_CHECK(k[i].lq(home, x.size()+removed-(sum_min - k[i].min())));
113 
114  // number of unassigned views
115  int non = x.size();
116 
117  for (int i=0; i<x.size(); i++)
118  if (x[i].assigned()) {
119  int idx;
120  if (!lookupValue(k,x[i].val(),idx)) {
121  return ES_FAILED;
122  }
123  count[idx]++;
124  non--;
125  }
126 
127  // check for subsumption
128  if (non == 0) {
129  for (int i=0; i<k.size(); i++)
130  GECODE_ME_CHECK((k[i].eq(home, count[i] + k[i].counter())));
131  return home.ES_SUBSUMED(p);
132  }
133 
134  // total number of unsatisfied miminum occurences
135  int req = 0;
136  // number of values whose min requirements are not yet met
137  int n_r = 0;
138  // if only one value is unsatisified single holds the index of that value
139  int single = -1;
140  // total number of assigned views wrt. the original probem size
141  int t_noa = 0;
142 
143  for (int i = k.size(); i--; ) {
144  int ci = count[i] + k[i].counter();
145  t_noa += ci;
146  if (ci == 0) { // this works
147  req += k[i].min();
148  n_r++;
149  single = i;
150  }
151 
152  // number of unassigned views cannot satisfy
153  // the required minimum occurence
154  if (req > non) {
155  return ES_FAILED;
156  }
157  }
158 
159  // if only one unsatisfied occurences is left
160  if ((req == non) && (n_r == 1)) {
161  // This works as the x are not shared!
162  for (int i = x.size(); i--; ) {
163  // try to assign it
164  if (!x[i].assigned()) {
165  GECODE_ME_CHECK(x[i].eq(home, k[single].card()));
166  assert((single >= 0) && (single < k.size()));
167  count[single]++;
168  }
169  }
170  assert((single >= 0) && (single < k.size()));
171 
172  for (int i = k.size(); i--; )
173  GECODE_ME_CHECK(k[i].eq(home, count[i] + k[i].counter()));
174  return home.ES_SUBSUMED(p);
175  }
176 
177  // Bitset for indexes that can be removed
178  Support::BitSet<Region> rem(r,static_cast<unsigned int>(k.size()));
179 
180  for (int i = k.size(); i--; ) {
181  int ci = count[i] + k[i].counter();
182  if (ci == k[i].max()) {
183  assert(!rem.get(i));
184  rem.set(static_cast<unsigned int>(i));
185  k[i].counter(ci);
186  // the solution contains ci occurences of value k[i].card();
187  GECODE_ME_CHECK(k[i].eq(home, ci));
188  } else {
189  if (ci > k[i].max()) {
190  return ES_FAILED;
191  }
192 
193  // in case of variable cardinalities
194  if (Card::propagate) {
195  GECODE_ME_CHECK(k[i].gq(home, ci));
196  int occupied = t_noa - ci;
197  GECODE_ME_CHECK(k[i].lq(home, x.size() + removed - occupied));
198  }
199  }
200  // reset counter
201  count[i] = 0;
202  }
203 
204  // reduce the problem size
205  {
206  int n_x = x.size();
207  for (int i = n_x; i--; ) {
208  if (x[i].assigned()) {
209  int idx;
210  if (!lookupValue(k,x[i].val(),idx)) {
211  return ES_FAILED;
212  }
213  if (rem.get(static_cast<unsigned int>(idx)))
214  x[i]=x[--n_x];
215  }
216  }
217  x.size(n_x);
218  }
219 
220  // remove values
221  {
222  // Values to prune
223  int* pr = r.alloc<int>(k.size());
224  // Number of values to prune
225  int n_pr = 0;
227  pr[n_pr++] = k[i.val()].card();
228  Support::quicksort(pr,n_pr);
229  for (int i = x.size(); i--;) {
230  Iter::Values::Array pi(pr,n_pr);
231  GECODE_ME_CHECK(x[i].minus_v(home, pi, false));
232  }
233  }
234 
235  {
236  bool all_assigned = true;
237 
238  for (int i = x.size(); i--; ) {
239  if (x[i].assigned()) {
240  int idx;
241  if (!lookupValue(k,x[i].val(),idx)) {
242  return ES_FAILED;
243  }
244  count[idx]++;
245  } else {
246  all_assigned = false;
247  }
248  }
249 
250  if (all_assigned) {
251  for (int i = k.size(); i--; )
252  GECODE_ME_CHECK((k[i].eq(home, count[i] + k[i].counter())));
253  return home.ES_SUBSUMED(p);
254  }
255  }
256 
257  if (Card::propagate) {
258  // check again consistency of cardinalities
259  int reqmin = 0;
260  int allmax = 0;
261  for (int i = k.size(); i--; ) {
262  if (k[i].counter() > k[i].max()) {
263  return ES_FAILED;
264  }
265  allmax += k[i].max() - k[i].counter();
266  if (k[i].counter() < k[i].min())
267  reqmin += k[i].min() - k[i].counter();
268  GECODE_ME_CHECK((k[i].lq(home, x.size()+k[i].counter())));
269  }
270 
271  if ((x.size() < reqmin) || (allmax < x.size())) {
272  return ES_FAILED;
273  }
274  }
275 
276  return ES_NOFIX;
277  }
278 
279  template<class Card>
280  ExecStatus
282  return prop_val<Card>(home, *this, x, k);
283  }
284 
285  template<class Card>
286  ExecStatus
289  GECODE_ES_CHECK((postSideConstraints<Card>(home,x,k)));
290 
291  if (isDistinct<Card>(x,k))
292  return Distinct::Val<IntView>::post(home,x);
293 
294  (void) new (home) Val<Card>(home,x,k);
295  return ES_OK;
296  }
297 
298 
299 }}}
300 
301 // STATISTICS: int-prop
302 
ViewArray< IntView > x
Views on which to perform value-propagation.
Definition: gcc.hh:66
Post propagator for SetVar x
Definition: set.hh:767
void set(unsigned int i)
Set bit i.
Value iterator for values in a bitset.
virtual size_t dispose(Space &home)
Destructor.
Definition: val.hpp:60
Value consistent global cardinality propagator.
Definition: gcc.hh:63
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: array.hpp:1341
ExecStatus prop_val(Space &home, Propagator &p, ViewArray< IntView > &x, ViewArray< Card > &k)
Definition: val.hpp:92
const int * pi[]
Definition: photo.cpp:14262
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3563
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost funtion returning high linear.
Definition: val.hpp:75
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
Value iterator for array of integers
Computation spaces.
Definition: core.hpp:1742
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4796
Base-class for both propagators and branchers.
Definition: core.hpp:628
bool lookupValue(T &a, int v, int &i)
Return index of v in array a.
Definition: view.hpp:45
Val(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Constructor for posting.
Definition: val.hpp:43
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition: sort.hpp:130
Gecode toplevel namespace
Base-class for propagators.
Definition: core.hpp:1064
static ExecStatus post(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post propagator for views x and cardinalities k.
Definition: val.hpp:287
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:101
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: val.hpp:281
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
void update(Space &home, ViewArray< View > &a)
Update array to be a clone of array a.
Definition: array.hpp:1328
Int ci(step1)
Home class for posting propagators
Definition: core.hpp:856
Handle to region.
Definition: region.hpp:55
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
virtual void reschedule(Space &home)
Schedule function.
Definition: val.hpp:85
Propagation cost.
Definition: core.hpp:486
bool get(unsigned int i) const
Access value at bit i.
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
Definition: count.cpp:40
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:82
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for view array x.
Definition: val.hpp:185
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1156
#define forceinline
Definition: config.hpp:185
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3252
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
Expensive.
Definition: core.hpp:514
ViewArray< Card > k
Array containing either fixed cardinalities or CardViews.
Definition: gcc.hh:68
Execution has resulted in failure.
Definition: core.hpp:474
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
Propagation has not computed fixpoint.
Definition: core.hpp:475
Gecode::IntArgs i({1, 2, 3, 4})
Execution is okay.
Definition: core.hpp:476
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: val.hpp:69
ExecStatus
Definition: core.hpp:472