weights.cc
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
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
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