Generated on Wed Jan 4 17:49:14 2006 for Gecode by doxygen 1.4.6

weights.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Guido Tack <tack@gecode.org>
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Contributing authors:
00007  *     Gabor Szokoli <szokoli@gecode.org>
00008  *
00009  *  Copyright:
00010  *     Guido Tack, 2004
00011  *     Christian Schulte, 2004
00012  *     Gabor Szokoli, 2004
00013  *
00014  *  Last modified:
00015  *     $Date: 2005-10-25 13:10:13 +0200 (Tue, 25 Oct 2005) $ by $Author: tack $
00016  *     $Revision: 2407 $
00017  *
00018  *  This file is part of Gecode, the generic constraint
00019  *  development environment:
00020  *     http://www.gecode.org
00021  *
00022  *  See the file "LICENSE" for information on usage and
00023  *  redistribution of this file, and for a
00024  *     DISCLAIMER OF ALL WARRANTIES.
00025  *
00026  */
00027 
00028 
00029 
00030 #include "set/int.hh"
00031 
00032 #include "iter.hh"
00033 
00034 using namespace Gecode::Int;
00035 
00036 namespace Gecode { namespace Set { namespace Int {
00037 
00038   PropCost
00039   Weights::cost(void) const {
00040     return PC_LINEAR_LO;
00041   }
00042 
00043   Weights::~Weights(void) {
00044     x.cancel(this, PC_SET_ANY);
00045     y.cancel(this, Gecode::Int::PC_INT_BND);
00046   }
00047 
00048   Actor*
00049   Weights::copy(Space* home, bool share) {
00050     return new (home) Weights(home,share,*this);
00051   }
00052 
00053   enum CostType { POS_COST, NEG_COST, ALL_COST };
00054 
00055   template <class I, CostType c>
00056   forceinline
00057   int weightI(Support::SharedArray<int>& elements,
00058               Support::SharedArray<int>& weights,
00059               I& iter) {
00060     int sum = 0;
00061     int i = 0;
00062     for (Iter::Ranges::ToValues<I> v(iter); v(); ++v) {
00063       // Skip all elements below the current
00064       while (elements[i]<v.val()) i++;
00065       assert(elements[i] == v.val());
00066       switch (c) {
00067       case ALL_COST:
00068         sum += weights[i];
00069         break;
00070       case POS_COST:
00071         if (weights[i] > 0) sum += weights[i];
00072         break;
00073       case NEG_COST:
00074         if (weights[i] < 0) sum += weights[i];
00075         break;
00076       }
00077     }
00078     return sum;
00079   }
00080 
00081 
00082 
00083   class IntLt {
00084   public:
00085     bool operator()(int x, int y);
00086   };
00087 
00088   forceinline bool 
00089   IntLt::operator()(int x, int y) {
00090     return x < y;
00091   }
00092 
00093   ExecStatus
00094   Weights::propagate(Space* home) {
00095 
00096     if (x.assigned()) {
00097       GlbRanges<SetView> glb(x);
00098       int w = 
00099         weightI<GlbRanges<SetView>,ALL_COST>(elements, weights, glb);
00100       GECODE_ME_CHECK(y.eq(home, w));
00101       return ES_SUBSUMED;
00102     }
00103 
00104     int lowCost;
00105     int lowestCost;
00106     int highestCost;
00107     int size = elements.size();
00108     {
00109       UnknownRanges<SetView> ur(x);
00110       Iter::Ranges::ToValues<UnknownRanges<SetView> > urv(ur);
00111       GECODE_AUTOARRAY(int, currentWeights, size);
00112       for (int i=0; i<size; i++) {
00113         if (!urv() || elements[i]<urv.val()) {
00114           currentWeights[i] = 0;
00115         } else {
00116           assert(elements[i] == urv.val());
00117           currentWeights[i] = weights[i];
00118           ++urv;
00119         }
00120       }
00121 
00122       IntLt ilt;
00123       Support::quicksort<int>(currentWeights, size, ilt);
00124 
00125       GlbRanges<SetView> glb(x);
00126       lowCost = weightI<GlbRanges<SetView>,ALL_COST>(elements, weights, glb);
00127       highestCost =
00128         weightI<GlbRanges<SetView>,ALL_COST>(elements, weights, glb);
00129 
00130       int delta = std::min(x.unknownSize(), x.cardMax() - x.glbSize());
00131 
00132       for (int i=0; i<delta-1; i++) {
00133         if (currentWeights[i] >= 0)
00134           break;
00135         lowCost+=currentWeights[i];
00136       }
00137       lowestCost = lowCost;
00138       if (delta>0 && currentWeights[delta-1]<0)
00139         lowestCost+=currentWeights[delta-1];
00140 
00141       for (int i=0; i<delta; i++) {
00142         if (currentWeights[size-i-1]<=0)
00143           break;
00144         highestCost += currentWeights[size-i-1];
00145       }
00146 
00147     }
00148 
00149     GECODE_ME_CHECK(y.gq(home, lowestCost));
00150     GECODE_ME_CHECK(y.lq(home, highestCost));
00151 
00152     ModEvent me;
00153     {
00154       UnknownRanges<SetView> ur2(x);
00155       Iter::Ranges::ToValues<UnknownRanges<SetView> > urv(ur2);
00156       OverweightValues<Iter::Ranges::ToValues<UnknownRanges<SetView> > >
00157         ov(y.max()-lowCost, elements, weights, urv);
00158       Iter::Values::ToRanges<OverweightValues<
00159         Iter::Ranges::ToValues<UnknownRanges<SetView> > > > ovr(ov);
00160       me = x.excludeI(home, ovr);
00161       GECODE_ME_CHECK(me);
00162     }
00163 
00164     if (x.assigned()) {
00165       GlbRanges<SetView> glb(x);
00166       int w = 
00167         weightI<GlbRanges<SetView>,ALL_COST>(elements, weights, glb);
00168       GECODE_ME_CHECK(y.eq(home, w));
00169       return ES_SUBSUMED;
00170     }
00171     return me_modified(me) ? ES_NOFIX : ES_FIX;
00172   }
00173 
00174 
00175 }}}
00176 
00177 // STATISTICS: set-prop