00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include <gecode/set.hh>
00039 #include <gecode/int.hh>
00040
00041 namespace Gecode { namespace Set { namespace Int {
00042
00044 template<class I>
00045 class OverweightValues {
00046 private:
00048 int threshold;
00050 I iter;
00052 const SharedArray<int> elements;
00054 const SharedArray<int> weights;
00056 int index;
00058 void next(void);
00059 public:
00061
00062
00063 OverweightValues(void);
00065 OverweightValues(int t,
00066 SharedArray<int>& elements0,
00067 SharedArray<int>& weights0,
00068 I& i);
00070 void init(int t,
00071 SharedArray<int>& elements0,
00072 SharedArray<int>& weights0,
00073 I& i);
00075
00077
00078
00079 bool operator ()(void) const;
00081 void operator ++(void);
00083
00084
00085
00086 int val(void) const;
00088 };
00089
00090 template<class I>
00091 forceinline void
00092 OverweightValues<I>::next(void) {
00093 while (iter()) {
00094 while (elements[index]<iter.val()) index++;
00095 assert(elements[index]==iter.val());
00096 if (weights[index] > threshold) {
00097 return;
00098 }
00099 ++iter;
00100 }
00101 }
00102
00103 template<class I>
00104 forceinline
00105 OverweightValues<I>::OverweightValues(void) {}
00106
00107 template<class I>
00108 forceinline
00109 OverweightValues<I>::OverweightValues(int t,
00110 SharedArray<int>& elements0,
00111 SharedArray<int>& weights0,
00112 I& i) : threshold(t),
00113 iter(i),
00114 elements(elements0),
00115 weights(weights0),
00116 index(0) {
00117 next();
00118 }
00119
00120 template<class I>
00121 forceinline void
00122 OverweightValues<I>::init(int t,
00123 SharedArray<int>& elements0,
00124 SharedArray<int>& weights0,
00125 I& i) {
00126 threshold = t; iter = i;
00127 elements = elements0; weights = weights0;
00128 index = 0;
00129 next();
00130 }
00131
00132 template<class I>
00133 forceinline bool
00134 OverweightValues<I>::operator ()(void) const { return iter(); }
00135
00136 template<class I>
00137 forceinline void
00138 OverweightValues<I>::operator ++(void) { ++iter; next(); }
00139
00140 template<class I>
00141 forceinline int
00142 OverweightValues<I>::val(void) const { return elements[index]; }
00143
00144 template<class View>
00145 forceinline
00146 Weights<View>::Weights(Home home,
00147 const SharedArray<int>& elements0,
00148 const SharedArray<int>& weights0,
00149 View x0, Gecode::Int::IntView y0)
00150 : Propagator(home), elements(elements0), weights(weights0),
00151 x(x0), y(y0) {
00152 home.notice(*this,AP_DISPOSE);
00153 x.subscribe(home,*this, PC_SET_ANY);
00154 y.subscribe(home,*this, Gecode::Int::PC_INT_BND);
00155 }
00156
00157 template<class View>
00158 forceinline
00159 Weights<View>::Weights(Space& home, Weights& p)
00160 : Propagator(home,p), elements(p.elements), weights(p.weights) {
00161 x.update(home,p.x);
00162 y.update(home,p.y);
00163 }
00164
00165 template<class View>
00166 inline ExecStatus
00167 Weights<View>::post(Home home, const SharedArray<int>& elements,
00168 const SharedArray<int>& weights,
00169 View x, Gecode::Int::IntView y) {
00170 if (elements.size() != weights.size())
00171 throw ArgumentSizeMismatch("Weights");
00172 Region r;
00173 int* els_arr = r.alloc<int>(elements.size());
00174 for (int i=elements.size(); i--;)
00175 els_arr[i] = elements[i];
00176 IntSet els(els_arr, elements.size());
00177 IntSetRanges er(els);
00178 GECODE_ME_CHECK(x.intersectI(home, er));
00179 (void) new (home) Weights(home,elements,weights,x,y);
00180 return ES_OK;
00181 }
00182
00183 template<class View>
00184 PropCost
00185 Weights<View>::cost(const Space&, const ModEventDelta&) const {
00186 return PropCost::linear(PropCost::LO, y.size()+1);
00187 }
00188
00189 template<class View>
00190 void
00191 Weights<View>::reschedule(Space& home) {
00192 x.reschedule(home,*this, PC_SET_ANY);
00193 y.reschedule(home,*this, Gecode::Int::PC_INT_BND);
00194 }
00195
00196 template<class View>
00197 forceinline size_t
00198 Weights<View>::dispose(Space& home) {
00199 home.ignore(*this,AP_DISPOSE);
00200 x.cancel(home,*this, PC_SET_ANY);
00201 y.cancel(home,*this, Gecode::Int::PC_INT_BND);
00202 elements.~SharedArray();
00203 weights.~SharedArray();
00204 (void) Propagator::dispose(home);
00205 return sizeof(*this);
00206 }
00207
00208 template<class View>
00209 Actor*
00210 Weights<View>::copy(Space& home) {
00211 return new (home) Weights(home,*this);
00212 }
00213
00215 template<class I>
00216 forceinline
00217 int weightI(SharedArray<int>& elements,
00218 SharedArray<int>& weights,
00219 I& iter) {
00220 int sum = 0;
00221 int i = 0;
00222 Iter::Ranges::ToValues<I> v(iter);
00223 for (; v(); ++v) {
00224
00225 while (elements[i]<v.val()) i++;
00226 assert(elements[i] == v.val());
00227 sum += weights[i];
00228 }
00229 assert(!v());
00230 return sum;
00231 }
00232
00233
00235 class IntLess {
00236 public:
00237 bool operator ()(int x, int y);
00238 };
00239
00240 forceinline bool
00241 IntLess::operator ()(int x, int y) {
00242 return x < y;
00243 }
00244
00245 template<class View>
00246 ExecStatus
00247 Weights<View>::propagate(Space& home, const ModEventDelta&) {
00248 ModEvent me = ME_SET_NONE;
00249
00250 if (!x.assigned()) {
00251
00252 int size = elements.size();
00253 Region r;
00254 int* minWeights = r.alloc<int>(size);
00255 int* maxWeights = r.alloc<int>(size);
00256
00257 UnknownRanges<View> ur(x);
00258 Iter::Ranges::ToValues<UnknownRanges<View> > urv(ur);
00259 for (int i=0; i<size; i++) {
00260 if (!urv() || elements[i]<urv.val()) {
00261 minWeights[i] = INT_MAX;
00262 maxWeights[i] = INT_MIN;
00263 } else {
00264 assert(elements[i] == urv.val());
00265 minWeights[i] = weights[i];
00266 maxWeights[i] = weights[i];
00267 ++urv;
00268 }
00269 }
00270
00271
00272 IntLess il;
00273 Support::quicksort<int>(minWeights, size, il);
00274 Support::quicksort<int>(maxWeights, size, il);
00275
00276
00277 int delta = static_cast<int>(std::min(x.unknownSize(), x.cardMax() - x.glbSize()));
00278
00279
00280 GlbRanges<View> glb(x);
00281 int glbWeight = weightI<GlbRanges<View> >(elements, weights, glb);
00282
00283
00284
00285
00286
00287
00288 int lowWeight = glbWeight;
00289 for (int i=0; i<delta-1; i++) {
00290 if (minWeights[i] >= 0)
00291 break;
00292 lowWeight+=minWeights[i];
00293 }
00294
00295
00296
00297
00298 int lowestWeight = lowWeight;
00299 if (delta>0 && minWeights[delta-1]<0)
00300 lowestWeight+=minWeights[delta-1];
00301
00302
00303
00304
00305 if ( (x.cardMin() - x.glbSize() > 0 &&
00306 minWeights[x.cardMin() - x.glbSize() - 1] >= 0) ||
00307 minWeights[0] >= 0 ) {
00308 int lowestPosWeight = glbWeight;
00309 for (unsigned int i=0; i<x.cardMin() - x.glbSize(); i++) {
00310 lowestPosWeight += minWeights[i];
00311 }
00312 lowestWeight = std::max(lowestWeight, lowestPosWeight);
00313 }
00314
00315
00316
00317
00318 int highestWeight = glbWeight;
00319 for (int i=0; i<delta; i++) {
00320 if (maxWeights[size-i-1]<=0)
00321 break;
00322 highestWeight += maxWeights[size-i-1];
00323 }
00324
00325
00326 GECODE_ME_CHECK(y.gq(home, lowestWeight));
00327 GECODE_ME_CHECK(y.lq(home, highestWeight));
00328
00329
00330
00331
00332 int remainingCapacity = y.max()-lowWeight;
00333
00334 UnknownRanges<View> ur2(x);
00335 Iter::Ranges::ToValues<UnknownRanges<View> > urv2(ur2);
00336 OverweightValues<Iter::Ranges::ToValues<UnknownRanges<View> > >
00337 ov(remainingCapacity, elements, weights, urv2);
00338 Iter::Values::ToRanges<OverweightValues<
00339 Iter::Ranges::ToValues<UnknownRanges<View> > > > ovr(ov);
00340 me = x.excludeI(home, ovr);
00341 GECODE_ME_CHECK(me);
00342 }
00343 if (x.assigned()) {
00344
00345 GlbRanges<View> glb(x);
00346 int w =
00347 weightI<GlbRanges<View> >(elements, weights, glb);
00348 GECODE_ME_CHECK(y.eq(home, w));
00349 return home.ES_SUBSUMED(*this);
00350 }
00351
00352
00353 return ES_NOFIX;
00354 }
00355
00356 }}}
00357
00358