weights.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Guido Tack <tack@gecode.org> 00005 * Christian Schulte <schulte@gecode.org> 00006 * Gabor Szokoli <szokoli@gecode.org> 00007 * 00008 * Copyright: 00009 * Guido Tack, 2004 00010 * Christian Schulte, 2004 00011 * Gabor Szokoli, 2004 00012 * 00013 * Last modified: 00014 * $Date: 2010-07-14 17:46:18 +0200 (Wed, 14 Jul 2010) $ by $Author: schulte $ 00015 * $Revision: 11192 $ 00016 * 00017 * This file is part of Gecode, the generic constraint 00018 * development environment: 00019 * http://www.gecode.org 00020 * 00021 * Permission is hereby granted, free of charge, to any person obtaining 00022 * a copy of this software and associated documentation files (the 00023 * "Software"), to deal in the Software without restriction, including 00024 * without limitation the rights to use, copy, modify, merge, publish, 00025 * distribute, sublicense, and/or sell copies of the Software, and to 00026 * permit persons to whom the Software is furnished to do so, subject to 00027 * the following conditions: 00028 * 00029 * The above copyright notice and this permission notice shall be 00030 * included in all copies or substantial portions of the Software. 00031 * 00032 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00033 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00034 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00035 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00036 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00037 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00038 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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 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 // Skip all elements below the current 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 // Collect the weights of the elements in the unknown set in an array 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 // Sort the weights of the unknown elements 00265 IntLess il; 00266 Support::quicksort<int>(currentWeights, size, il); 00267 00268 // The maximum number of elements that can still be added to x 00269 int delta = static_cast<int>(std::min(x.unknownSize(), x.cardMax() - x.glbSize())); 00270 00271 // The weight of the elements already in x 00272 GlbRanges<View> glb(x); 00273 int glbWeight = weightI<GlbRanges<View> >(elements, weights, glb); 00274 00275 // Compute the weight of the current lower bound of x, plus at most 00276 // delta-1 further elements with smallest negative weights. This weight 00277 // determines which elements in the upper bound cannot possibly be 00278 // added to x (those whose weight would exceed the capacity even if 00279 // all other elements are minimal) 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 // Compute the lowest possible weight of x. If there is another element 00288 // with negative weight left, then add its weight to lowWeight. 00289 // Otherwise lowWeight is already the lowest possible weight. 00290 int lowestWeight = lowWeight; 00291 if (delta>0 && currentWeights[delta-1]<0) 00292 lowestWeight+=currentWeights[delta-1]; 00293 00294 // If after including the minimal number of required elements, 00295 // no more element with negative weight is available, then 00296 // a tighter lower bound can be computed. 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 // Compute the highest possible weight of x as the weight of the lower 00308 // bound plus the weight of the delta heaviest elements still in the 00309 // upper bound. 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 // Prune the weight using the computed bounds 00318 GECODE_ME_CHECK(y.gq(home, lowestWeight)); 00319 GECODE_ME_CHECK(y.lq(home, highestWeight)); 00320 00321 // Exclude all elements that are too heavy from the set x. 00322 // Elements are too heavy if their weight alone already 00323 // exceeds the remaining capacity 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 // If x is assigned, just compute its weight and assign y. 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 // STATISTICS: set-prop