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 : public Iter::Values::IsValueIter<I> {
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 size_t
00196 Weights<View>::dispose(Space& home) {
00197 assert(!home.failed());
00198 x.cancel(home,*this, PC_SET_ANY);
00199 y.cancel(home,*this, Gecode::Int::PC_INT_BND);
00200 (void) Propagator::dispose(home);
00201 return sizeof(*this);
00202 }
00203
00204 template<class View>
00205 Actor*
00206 Weights<View>::copy(Space& home, bool share) {
00207 return new (home) Weights(home,share,*this);
00208 }
00209
00211 template<class I>
00212 forceinline
00213 int weightI(SharedArray<int>& elements,
00214 SharedArray<int>& weights,
00215 I& iter) {
00216 int sum = 0;
00217 int i = 0;
00218 Iter::Ranges::ToValues<I> v(iter);
00219 for (; v(); ++v) {
00220
00221 while (elements[i]<v.val()) i++;
00222 assert(elements[i] == v.val());
00223 sum += weights[i];
00224 }
00225 assert(!v());
00226 return sum;
00227 }
00228
00229
00231 class IntLess {
00232 public:
00233 bool operator ()(int x, int y);
00234 };
00235
00236 forceinline bool
00237 IntLess::operator ()(int x, int y) {
00238 return x < y;
00239 }
00240
00241 template<class View>
00242 ExecStatus
00243 Weights<View>::propagate(Space& home, const ModEventDelta&) {
00244
00245 ModEvent me = ME_SET_NONE;
00246
00247 if (!x.assigned()) {
00248
00249 int size = elements.size();
00250 Region r(home);
00251 int* currentWeights = r.alloc<int>(size);
00252
00253 UnknownRanges<View> ur(x);
00254 Iter::Ranges::ToValues<UnknownRanges<View> > urv(ur);
00255 for (int i=0; i<size; i++) {
00256 if (!urv() || elements[i]<urv.val()) {
00257 currentWeights[i] = 0;
00258 } else {
00259 assert(elements[i] == urv.val());
00260 currentWeights[i] = weights[i];
00261 ++urv;
00262 }
00263 }
00264
00265
00266 IntLess il;
00267 Support::quicksort<int>(currentWeights, size, il);
00268
00269
00270 int delta = std::min(x.unknownSize(), x.cardMax() - x.glbSize());
00271
00272
00273 GlbRanges<View> glb(x);
00274 int glbWeight = weightI<GlbRanges<View> >(elements, weights, glb);
00275
00276
00277
00278
00279
00280
00281 int lowWeight = glbWeight;
00282 for (int i=0; i<delta-1; i++) {
00283 if (currentWeights[i] >= 0)
00284 break;
00285 lowWeight+=currentWeights[i];
00286 }
00287
00288
00289
00290
00291 int lowestWeight = lowWeight;
00292 if (delta>0 && currentWeights[delta-1]<0)
00293 lowestWeight+=currentWeights[delta-1];
00294
00295
00296
00297
00298 if ( (x.cardMin() - x.glbSize() > 0 &&
00299 currentWeights[x.cardMin() - x.glbSize() - 1] >= 0) ||
00300 currentWeights[0] >= 0 ) {
00301 int lowestPosWeight = glbWeight;
00302 for (unsigned int i=0; i<x.cardMin() - x.glbSize(); i++) {
00303 lowestPosWeight += currentWeights[i];
00304 }
00305 lowestWeight = std::max(lowestWeight, lowestPosWeight);
00306 }
00307
00308
00309
00310
00311 int highestWeight = glbWeight;
00312 for (int i=0; i<delta; i++) {
00313 if (currentWeights[size-i-1]<=0)
00314 break;
00315 highestWeight += currentWeights[size-i-1];
00316 }
00317
00318
00319 GECODE_ME_CHECK(y.gq(home, lowestWeight));
00320 GECODE_ME_CHECK(y.lq(home, highestWeight));
00321
00322
00323
00324
00325 int remainingCapacity = y.max()-lowWeight;
00326
00327 UnknownRanges<View> ur2(x);
00328 Iter::Ranges::ToValues<UnknownRanges<View> > urv2(ur2);
00329 OverweightValues<Iter::Ranges::ToValues<UnknownRanges<View> > >
00330 ov(remainingCapacity, elements, weights, urv2);
00331 Iter::Values::ToRanges<OverweightValues<
00332 Iter::Ranges::ToValues<UnknownRanges<View> > > > ovr(ov);
00333 me = x.excludeI(home, ovr);
00334 GECODE_ME_CHECK(me);
00335 }
00336 if (x.assigned()) {
00337
00338 GlbRanges<View> glb(x);
00339 int w =
00340 weightI<GlbRanges<View> >(elements, weights, glb);
00341 GECODE_ME_CHECK(y.eq(home, w));
00342 return ES_SUBSUMED(*this,home);
00343 }
00344
00345 return me_modified(me) ? ES_NOFIX : ES_FIX;
00346 }
00347
00348 }}}
00349
00350