Generated on Mon Nov 30 23:53:35 2009 for Gecode by doxygen 1.6.1

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: 2009-10-12 17:36:53 +0200 (Mon, 12 Oct 2009) $ by $Author: schulte $
00015  *     $Revision: 9878 $
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   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       // Skip all elements below the current
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       // Collect the weights of the elements in the unknown set in an array
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       // Sort the weights of the unknown elements
00266       IntLess il;
00267       Support::quicksort<int>(currentWeights, size, il);
00268 
00269       // The maximum number of elements that can still be added to x
00270       int delta = std::min(x.unknownSize(), x.cardMax() - x.glbSize());
00271 
00272       // The weight of the elements already in x
00273       GlbRanges<View> glb(x);
00274       int glbWeight = weightI<GlbRanges<View> >(elements, weights, glb);
00275 
00276       // Compute the weight of the current lower bound of x, plus at most
00277       // delta-1 further elements with smallest negative weights. This weight
00278       // determines which elements in the upper bound cannot possibly be
00279       // added to x (those whose weight would exceed the capacity even if
00280       // all other elements are minimal)
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       // Compute the lowest possible weight of x. If there is another element
00289       // with negative weight left, then add its weight to lowWeight.
00290       // Otherwise lowWeight is already the lowest possible weight.
00291       int lowestWeight = lowWeight;
00292       if (delta>0 && currentWeights[delta-1]<0)
00293         lowestWeight+=currentWeights[delta-1];
00294 
00295       // If after including the minimal number of required elements,
00296       // no more element with negative weight is available, then
00297       // a tighter lower bound can be computed.
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       // Compute the highest possible weight of x as the weight of the lower
00309       // bound plus the weight of the delta heaviest elements still in the
00310       // upper bound.
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       // Prune the weight using the computed bounds
00319       GECODE_ME_CHECK(y.gq(home, lowestWeight));
00320       GECODE_ME_CHECK(y.lq(home, highestWeight));
00321 
00322       // Exclude all elements that are too heavy from the set x.
00323       // Elements are too heavy if their weight alone already
00324       // exceeds the remaining capacity
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       // If x is assigned, just compute its weight and assign y.
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 // STATISTICS: set-prop