Generated on Thu Jul 6 07:06:49 2006 for Gecode by doxygen 1.4.7

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 "gecode/set/int.hh"
00031 
00032 #include "gecode/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   size_t
00044   Weights::dispose(Space* home) {
00045     assert(!home->failed());
00046     x.cancel(home,this, PC_SET_ANY);
00047     y.cancel(home,this, Gecode::Int::PC_INT_BND);
00048     (void) Propagator::dispose(home);
00049     return sizeof(*this);
00050   }
00051 
00052   Actor*
00053   Weights::copy(Space* home, bool share) {
00054     return new (home) Weights(home,share,*this);
00055   }
00056 
00057   enum CostType { POS_COST, NEG_COST, ALL_COST };
00058 
00059   template <class I, CostType c>
00060   forceinline
00061   int weightI(Support::SharedArray<int>& elements,
00062               Support::SharedArray<int>& weights,
00063               I& iter) {
00064     int sum = 0;
00065     int i = 0;
00066     for (Iter::Ranges::ToValues<I> v(iter); v(); ++v) {
00067       // Skip all elements below the current
00068       while (elements[i]<v.val()) i++;
00069       assert(elements[i] == v.val());
00070       switch (c) {
00071       case ALL_COST:
00072         sum += weights[i];
00073         break;
00074       case POS_COST:
00075         if (weights[i] > 0) sum += weights[i];
00076         break;
00077       case NEG_COST:
00078         if (weights[i] < 0) sum += weights[i];
00079         break;
00080       }
00081     }
00082     return sum;
00083   }
00084 
00085 
00087   class IntLt {
00088   public:
00089     bool operator()(int x, int y);
00090   };
00091 
00092   forceinline bool 
00093   IntLt::operator()(int x, int y) {
00094     return x < y;
00095   }
00096 
00097   ExecStatus
00098   Weights::propagate(Space* home) {
00099 
00100     if (x.assigned()) {
00101       GlbRanges<SetView> glb(x);
00102       int w = 
00103         weightI<GlbRanges<SetView>,ALL_COST>(elements, weights, glb);
00104       GECODE_ME_CHECK(y.eq(home, w));
00105       return ES_SUBSUMED;
00106     }
00107 
00108     int lowCost;
00109     int lowestCost;
00110     int highestCost;
00111     int size = elements.size();
00112     {
00113       UnknownRanges<SetView> ur(x);
00114       Iter::Ranges::ToValues<UnknownRanges<SetView> > urv(ur);
00115       GECODE_AUTOARRAY(int, currentWeights, size);
00116       for (int i=0; i<size; i++) {
00117         if (!urv() || elements[i]<urv.val()) {
00118           currentWeights[i] = 0;
00119         } else {
00120           assert(elements[i] == urv.val());
00121           currentWeights[i] = weights[i];
00122           ++urv;
00123         }
00124       }
00125 
00126       IntLt ilt;
00127       Support::quicksort<int>(currentWeights, size, ilt);
00128 
00129       GlbRanges<SetView> glb(x);
00130       lowCost = weightI<GlbRanges<SetView>,ALL_COST>(elements, weights, glb);
00131       highestCost =
00132         weightI<GlbRanges<SetView>,ALL_COST>(elements, weights, glb);
00133 
00134       int delta = std::min(x.unknownSize(), x.cardMax() - x.glbSize());
00135 
00136       for (int i=0; i<delta-1; i++) {
00137         if (currentWeights[i] >= 0)
00138           break;
00139         lowCost+=currentWeights[i];
00140       }
00141       lowestCost = lowCost;
00142       if (delta>0 && currentWeights[delta-1]<0)
00143         lowestCost+=currentWeights[delta-1];
00144 
00145       for (int i=0; i<delta; i++) {
00146         if (currentWeights[size-i-1]<=0)
00147           break;
00148         highestCost += currentWeights[size-i-1];
00149       }
00150 
00151     }
00152 
00153     GECODE_ME_CHECK(y.gq(home, lowestCost));
00154     GECODE_ME_CHECK(y.lq(home, highestCost));
00155 
00156     ModEvent me;
00157     {
00158       UnknownRanges<SetView> ur2(x);
00159       Iter::Ranges::ToValues<UnknownRanges<SetView> > urv(ur2);
00160       OverweightValues<Iter::Ranges::ToValues<UnknownRanges<SetView> > >
00161         ov(y.max()-lowCost, elements, weights, urv);
00162       Iter::Values::ToRanges<OverweightValues<
00163         Iter::Ranges::ToValues<UnknownRanges<SetView> > > > ovr(ov);
00164       me = x.excludeI(home, ovr);
00165       GECODE_ME_CHECK(me);
00166     }
00167 
00168     if (x.assigned()) {
00169       GlbRanges<SetView> glb(x);
00170       int w = 
00171         weightI<GlbRanges<SetView>,ALL_COST>(elements, weights, glb);
00172       GECODE_ME_CHECK(y.eq(home, w));
00173       return ES_SUBSUMED;
00174     }
00175     return me_modified(me) ? ES_NOFIX : ES_FIX;
00176   }
00177 
00178 
00179 }}}
00180 
00181 // STATISTICS: set-prop