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 "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
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