Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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
39namespace 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>
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;
226 for (Iter::Values::BitSet<Support::BitSet<Region> > i(rem); i(); ++i)
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>
282 return prop_val<Card>(home, *this, x, k);
283 }
284
285 template<class Card>
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
int p
Number of positive literals for node type.
Base-class for both propagators and branchers.
Definition core.hpp:628
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3252
Home class for posting propagators
Definition core.hpp:856
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for view array x.
Definition val.hpp:185
Value consistent global cardinality propagator.
Definition gcc.hh:63
virtual void reschedule(Space &home)
Schedule function.
Definition val.hpp:85
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost funtion returning high linear.
Definition val.hpp:75
static ExecStatus post(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post propagator for views x and cardinalities k.
Definition val.hpp:287
ViewArray< Card > k
Array containing either fixed cardinalities or CardViews.
Definition gcc.hh:68
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition val.hpp:69
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition val.hpp:281
ViewArray< IntView > x
Views on which to perform value-propagation.
Definition gcc.hh:66
virtual size_t dispose(Space &home)
Destructor.
Definition val.hpp:60
Val(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Constructor for posting.
Definition val.hpp:43
Value iterator for array of integers
Value iterator for values in a bitset.
Propagation cost.
Definition core.hpp:486
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:4796
@ HI
Expensive.
Definition core.hpp:514
Base-class for propagators.
Definition core.hpp:1064
Handle to region.
Definition region.hpp:55
Computation spaces.
Definition core.hpp:1742
bool get(unsigned int i) const
Access value at bit i.
void set(unsigned int i)
Set bit i.
Simple bitsets.
Definition bitset.hpp:45
View arrays.
Definition array.hpp:253
void update(Space &home, ViewArray< View > &a)
Update array to be a clone of array a.
Definition array.hpp:1328
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition array.hpp:1341
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1156
const int * pi[]
Definition photo.cpp:14262
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
bool isDistinct(ViewArray< IntView > &x, ViewArray< Card > &k)
Check if GCC is equivalent to distinct.
Definition post.hpp:138
ExecStatus prop_val(Space &home, Propagator &p, ViewArray< IntView > &x, ViewArray< Card > &k)
Definition val.hpp:92
bool lookupValue(T &a, int v, int &i)
Return index of v in array a.
Definition view.hpp:45
ExecStatus postSideConstraints(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post side constraints for the GCC.
Definition post.hpp:60
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value)
Definition var-type.hpp:82
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode toplevel namespace
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition count.cpp:40
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
Definition set.hh:767
#define forceinline
Definition config.hpp:187