this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Guido Tack <tack@gecode.org>
5 * Christian Schulte <schulte@gecode.org>
6 * Gabor Szokoli <szokoli@gecode.org>
7 *
8 * Copyright:
9 * Guido Tack, 2004
10 * Christian Schulte, 2004
11 * Gabor Szokoli, 2004
12 *
13 * This file is part of Gecode, the generic constraint
14 * development environment:
15 * http://www.gecode.org
16 *
17 * Permission is hereby granted, free of charge, to any person obtaining
18 * a copy of this software and associated documentation files (the
19 * "Software"), to deal in the Software without restriction, including
20 * without limitation the rights to use, copy, modify, merge, publish,
21 * distribute, sublicense, and/or sell copies of the Software, and to
22 * permit persons to whom the Software is furnished to do so, subject to
23 * the following conditions:
24 *
25 * The above copyright notice and this permission notice shall be
26 * included in all copies or substantial portions of the Software.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 *
36 */
37
38#include <gecode/set.hh>
39#include <gecode/int.hh>
40
41namespace Gecode { namespace Set { namespace Int {
42
43 /// Value Iterator for values above a certain weight
44 template<class I>
45 class OverweightValues {
46 private:
47 /// The threshold above which values should be iterated
48 int threshold;
49 /// The value iterator
50 I iter;
51 /// A superset of the elements found in the iterator
52 SharedArray<int> elements;
53 /// Weights for all the possible elements
54 SharedArray<int> weights;
55 /// The current index into the elements and weights
56 int index;
57 /// Move to the next element
58 void next(void);
59 public:
60 /// \name Constructors and initialization
61 //@{
62 /// Default constructor
63 OverweightValues(void);
64 /// Initialize with elements/weights pairs, threshold \a t and iterator \a i
65 OverweightValues(int t,
66 SharedArray<int>& elements0,
67 SharedArray<int>& weights0,
68 I& i);
69 /// Initialize with elements/weights pairs, threshold \a t and iterator \a i
70 void init(int t,
71 SharedArray<int>& elements0,
72 SharedArray<int>& weights0,
73 I& i);
74 //@}
75
76 /// \name Iteration control
77 //@{
78 /// Test whether iterator is still at a value or done
79 bool operator ()(void) const;
80 /// Move iterator to next value (if possible)
81 void operator ++(void);
82 //@}
83 /// \name Value access
84 //@{
85 /// Return current value
86 int val(void) const;
87 //@}
88 };
89
90 template<class I>
91 forceinline void
92 OverweightValues<I>::next(void) {
93 while (iter()) {
94 while (elements[index]<iter.val()) index++;
95 assert(elements[index]==iter.val());
96 if (weights[index] > threshold) {
97 return;
98 }
99 ++iter;
100 }
101 }
102
103 template<class I>
104 forceinline
105 OverweightValues<I>::OverweightValues(void) {}
106
107 template<class I>
108 forceinline
109 OverweightValues<I>::OverweightValues(int t,
110 SharedArray<int>& elements0,
111 SharedArray<int>& weights0,
112 I& i) : threshold(t),
113 iter(i),
114 elements(elements0),
115 weights(weights0),
116 index(0) {
117 next();
118 }
119
120 template<class I>
121 forceinline void
122 OverweightValues<I>::init(int t,
123 SharedArray<int>& elements0,
124 SharedArray<int>& weights0,
125 I& i) {
126 threshold = t; iter = i;
127 elements = elements0; weights = weights0;
128 index = 0;
129 next();
130 }
131
132 template<class I>
133 forceinline bool
134 OverweightValues<I>::operator ()(void) const { return iter(); }
135
136 template<class I>
137 forceinline void
138 OverweightValues<I>::operator ++(void) { ++iter; next(); }
139
140 template<class I>
141 forceinline int
142 OverweightValues<I>::val(void) const { return elements[index]; }
143
144 template<class View>
145 forceinline
146 Weights<View>::Weights(Home home,
147 const SharedArray<int>& elements0,
148 const SharedArray<int>& weights0,
149 View x0, Gecode::Int::IntView y0)
150 : Propagator(home), elements(elements0), weights(weights0),
151 x(x0), y(y0) {
152 home.notice(*this,AP_DISPOSE);
153 x.subscribe(home,*this, PC_SET_ANY);
154 y.subscribe(home,*this, Gecode::Int::PC_INT_BND);
155 }
156
157 template<class View>
158 forceinline
159 Weights<View>::Weights(Space& home, Weights& p)
160 : Propagator(home,p), elements(p.elements), weights(p.weights) {
161 x.update(home,p.x);
162 y.update(home,p.y);
163 }
164
165 template<class View>
166 inline ExecStatus
167 Weights<View>::post(Home home, const SharedArray<int>& elements,
168 const SharedArray<int>& weights,
169 View x, Gecode::Int::IntView y) {
170 if (elements.size() != weights.size())
171 throw ArgumentSizeMismatch("Weights");
172 Region r;
173 int* els_arr = r.alloc<int>(elements.size());
174 for (int i=elements.size(); i--;)
175 els_arr[i] = elements[i];
176 IntSet els(els_arr, elements.size());
177 IntSetRanges er(els);
178 GECODE_ME_CHECK(x.intersectI(home, er));
179 (void) new (home) Weights(home,elements,weights,x,y);
180 return ES_OK;
181 }
182
183 template<class View>
184 PropCost
185 Weights<View>::cost(const Space&, const ModEventDelta&) const {
186 return PropCost::linear(PropCost::LO, y.size()+1);
187 }
188
189 template<class View>
190 void
191 Weights<View>::reschedule(Space& home) {
192 x.reschedule(home,*this, PC_SET_ANY);
193 y.reschedule(home,*this, Gecode::Int::PC_INT_BND);
194 }
195
196 template<class View>
197 forceinline size_t
198 Weights<View>::dispose(Space& home) {
199 home.ignore(*this,AP_DISPOSE);
200 x.cancel(home,*this, PC_SET_ANY);
201 y.cancel(home,*this, Gecode::Int::PC_INT_BND);
202 elements.~SharedArray();
203 weights.~SharedArray();
204 (void) Propagator::dispose(home);
205 return sizeof(*this);
206 }
207
208 template<class View>
209 Actor*
210 Weights<View>::copy(Space& home) {
211 return new (home) Weights(home,*this);
212 }
213
214 /// Compute the weight of the elements in the iterator \a I
215 template<class I>
216 forceinline
217 int weightI(SharedArray<int>& elements,
218 SharedArray<int>& weights,
219 I& iter) {
220 int sum = 0;
221 int i = 0;
222 Iter::Ranges::ToValues<I> v(iter);
223 for (; v(); ++v) {
224 // Skip all elements below the current
225 while (elements[i]<v.val()) i++;
226 assert(elements[i] == v.val());
227 sum += weights[i];
228 }
229 assert(!v());
230 return sum;
231 }
232
233
234 /// Sort order for integers
235 class IntLess {
236 public:
237 bool operator ()(int x, int y);
238 };
239
240 forceinline bool
241 IntLess::operator ()(int x, int y) {
242 return x < y;
243 }
244
245 template<class View>
246 ExecStatus
247 Weights<View>::propagate(Space& home, const ModEventDelta&) {
248 ModEvent me = ME_SET_NONE;
249
250 if (!x.assigned()) {
251 // Collect the weights of the elements in the unknown set in an array
252 int size = elements.size();
253 Region r;
254 int* minWeights = r.alloc<int>(size);
255 int* maxWeights = r.alloc<int>(size);
256
257 UnknownRanges<View> ur(x);
258 Iter::Ranges::ToValues<UnknownRanges<View> > urv(ur);
259 for (int i=0; i<size; i++) {
260 if (!urv() || elements[i]<urv.val()) {
261 minWeights[i] = INT_MAX;
262 maxWeights[i] = INT_MIN;
263 } else {
264 assert(elements[i] == urv.val());
265 minWeights[i] = weights[i];
266 maxWeights[i] = weights[i];
267 ++urv;
268 }
269 }
270
271 // Sort the weights of the unknown elements
272 IntLess il;
273 Support::quicksort<int>(minWeights, size, il);
274 Support::quicksort<int>(maxWeights, size, il);
275
276 // The maximum number of elements that can still be added to x
277 int delta = static_cast<int>(std::min(x.unknownSize(), x.cardMax() - x.glbSize()));
278
279 // The weight of the elements already in x
280 GlbRanges<View> glb(x);
281 int glbWeight = weightI<GlbRanges<View> >(elements, weights, glb);
282
283 // Compute the weight of the current lower bound of x, plus at most
284 // delta-1 further elements with smallest negative weights. This weight
285 // determines which elements in the upper bound cannot possibly be
286 // added to x (those whose weight would exceed the capacity even if
287 // all other elements are minimal)
288 int lowWeight = glbWeight;
289 for (int i=0; i<delta-1; i++) {
290 if (minWeights[i] >= 0)
291 break;
292 lowWeight+=minWeights[i];
293 }
294
295 // Compute the lowest possible weight of x. If there is another element
296 // with negative weight left, then add its weight to lowWeight.
297 // Otherwise lowWeight is already the lowest possible weight.
298 int lowestWeight = lowWeight;
299 if (delta>0 && minWeights[delta-1]<0)
300 lowestWeight+=minWeights[delta-1];
301
302 // If after including the minimal number of required elements,
303 // no more element with negative weight is available, then
304 // a tighter lower bound can be computed.
305 if ( (x.cardMin() - x.glbSize() > 0 &&
306 minWeights[x.cardMin() - x.glbSize() - 1] >= 0) ||
307 minWeights[0] >= 0 ) {
308 int lowestPosWeight = glbWeight;
309 for (unsigned int i=0; i<x.cardMin() - x.glbSize(); i++) {
310 lowestPosWeight += minWeights[i];
311 }
312 lowestWeight = std::max(lowestWeight, lowestPosWeight);
313 }
314
315 // Compute the highest possible weight of x as the weight of the lower
316 // bound plus the weight of the delta heaviest elements still in the
317 // upper bound.
318 int highestWeight = glbWeight;
319 for (int i=0; i<delta; i++) {
320 if (maxWeights[size-i-1]<=0)
321 break;
322 highestWeight += maxWeights[size-i-1];
323 }
324
325 // Prune the weight using the computed bounds
326 GECODE_ME_CHECK(y.gq(home, lowestWeight));
327 GECODE_ME_CHECK(y.lq(home, highestWeight));
328
329 // Exclude all elements that are too heavy from the set x.
330 // Elements are too heavy if their weight alone already
331 // exceeds the remaining capacity
332 int remainingCapacity = y.max()-lowWeight;
333
334 UnknownRanges<View> ur2(x);
335 Iter::Ranges::ToValues<UnknownRanges<View> > urv2(ur2);
336 OverweightValues<Iter::Ranges::ToValues<UnknownRanges<View> > >
337 ov(remainingCapacity, elements, weights, urv2);
338 Iter::Values::ToRanges<OverweightValues<
339 Iter::Ranges::ToValues<UnknownRanges<View> > > > ovr(ov);
340 me = x.excludeI(home, ovr);
341 GECODE_ME_CHECK(me);
342 }
343 if (x.assigned()) {
344 // If x is assigned, just compute its weight and assign y.
345 GlbRanges<View> glb(x);
346 int w =
347 weightI<GlbRanges<View> >(elements, weights, glb);
348 GECODE_ME_CHECK(y.eq(home, w));
349 return home.ES_SUBSUMED(*this);
350 }
351
352 // return me_modified(me) ? ES_NOFIX : ES_FIX;
353 return ES_NOFIX;
354 }
355
356}}}
357
358// STATISTICS: set-prop