this repo has no description
dekker.one
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>
42 forceinline
43 Val<Card>::Val(Home home,
44 ViewArray<IntView>& x0, ViewArray<Card>& k0)
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>
51 forceinline
52 Val<Card>::Val(Space& home, Val<Card>& p)
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
60 Val<Card>::dispose(Space& home) {
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*
69 Val<Card>::copy(Space& home) {
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
85 Val<Card>::reschedule(Space& home) {
86 x.reschedule(home, *this, PC_INT_VAL);
87 k.reschedule(home, *this, PC_INT_VAL);
88 }
89
90 template<class Card>
91 ExecStatus
92 prop_val(Space& home, Propagator& p,
93 ViewArray<IntView>& x, ViewArray<Card>& k) {
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>
280 ExecStatus
281 Val<Card>::propagate(Space& home, const ModEventDelta&) {
282 return prop_val<Card>(home, *this, x, k);
283 }
284
285 template<class Card>
286 ExecStatus
287 Val<Card>::post(Home home,
288 ViewArray<IntView>& x, ViewArray<Card>& k) {
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