Generated on Mon May 10 06:46:45 2010 for Gecode by doxygen 1.6.3

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-03-03 17:32:21 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $
00015  *     $Revision: 10364 $
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 = 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