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