link-multi.cpp
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
00031
00032
00033
00034
00035
00036
00037
00038 #include <gecode/int/channel.hh>
00039
00040 namespace Gecode { namespace Int { namespace Channel {
00041
00043 class BoolIter {
00044 private:
00046 const ViewArray<BoolView>& x;
00048 const int o;
00050 int i;
00051 public:
00053 BoolIter(const ViewArray<BoolView>& x0, int o0);
00055 bool operator ()(void) const;
00057 int val(void) const;
00059 void operator ++(void);
00060 };
00061
00062 forceinline
00063 BoolIter::BoolIter(const ViewArray<BoolView>& x0, int o0) :
00064 x(x0), o(o0), i(0) {
00065 while ((i<x.size()) && !x[i].zero())
00066 i++;
00067 }
00068 forceinline bool
00069 BoolIter::operator ()(void) const {
00070 return i<x.size();
00071 }
00072 forceinline int
00073 BoolIter::val(void) const {
00074 assert(x[i].zero());
00075 return i+o;
00076 }
00077 forceinline void
00078 BoolIter::operator ++(void) {
00079 do {
00080 i++;
00081 } while ((i<x.size()) && !x[i].zero());
00082 }
00083
00084
00085 forceinline
00086 LinkMulti::LinkMulti(Space& home, bool share, LinkMulti& p)
00087 : MixNaryOnePropagator<BoolView,PC_BOOL_VAL,IntView,PC_INT_DOM>
00088 (home,share,p), o(p.o) {}
00089
00090 Actor*
00091 LinkMulti::copy(Space& home, bool share) {
00092 return new (home) LinkMulti(home,share,*this);
00093 }
00094
00095 PropCost
00096 LinkMulti::cost(const Space&, const ModEventDelta& med) const {
00097 if (IntView::me(med) == ME_INT_VAL)
00098 return PropCost::unary(PropCost::LO);
00099 else
00100 return PropCost::linear(PropCost::LO, x.size());
00101 }
00102
00103 ExecStatus
00104 LinkMulti::propagate(Space& home, const ModEventDelta& med) {
00105 int n = x.size();
00106
00107
00108 assert((y.min()-o >= 0) && (y.max()-o < n));
00109
00110 if (y.assigned()) {
00111 int j=y.val()-o;
00112 GECODE_ME_CHECK(x[j].one(home));
00113 for (int i=0; i<j; i++)
00114 GECODE_ME_CHECK(x[i].zero(home));
00115 for (int i=j+1; i<n; i++)
00116 GECODE_ME_CHECK(x[i].zero(home));
00117 return ES_SUBSUMED(*this,sizeof(*this));
00118 }
00119
00120 redo:
00121
00122
00123 {
00124 int min=y.min()-o;
00125 for (int i=0; i<min; i++)
00126 GECODE_ME_CHECK(x[i].zero(home));
00127 x.drop_fst(min); o += min; n = x.size();
00128
00129 int max=y.max()-o;
00130 for (int i=max+1; i<n; i++)
00131 GECODE_ME_CHECK(x[i].zero(home));
00132 x.drop_lst(max); n = x.size();
00133 }
00134
00135 {
00136
00137 int i=0;
00138 while ((i < n) && x[i].zero()) i++;
00139 if (i >= n)
00140 return ES_FAILED;
00141 x.drop_fst(i); o += i; n = x.size();
00142 }
00143
00144 {
00145
00146 int i=n-1;
00147 while ((i >= 0) && x[i].zero()) i--;
00148 assert(i >= 0);
00149 x.drop_lst(i); n = x.size();
00150 }
00151
00152 assert(n >= 1);
00153
00154
00155 if (n == 1) {
00156 GECODE_ME_CHECK(x[0].one(home));
00157 GECODE_ME_CHECK(y.eq(home,o));
00158 return ES_SUBSUMED(*this,sizeof(*this));
00159 }
00160
00161
00162 GECODE_ME_CHECK(y.gq(home,o));
00163 GECODE_ME_CHECK(y.lq(home,o+n-1));
00164 if ((y.min() > o) || (y.max() < o+n-1))
00165 goto redo;
00166
00167
00168 for (int i=n; i--; )
00169 if (x[i].one()) {
00170 for (int j=0; j<i; j++)
00171 GECODE_ME_CHECK(x[j].zero(home));
00172 for (int j=i+1; j<n; j++)
00173 GECODE_ME_CHECK(x[j].zero(home));
00174 GECODE_ME_CHECK(y.eq(home,i+o));
00175 return ES_SUBSUMED(*this,sizeof(*this));
00176 }
00177
00178 assert((n >= 2) && x[0].none() && x[n-1].none());
00179 assert((y.min()-o == 0) && (y.max()-o == n-1));
00180
00181
00182 if ((IntView::me(med) == ME_INT_BND) || (IntView::me(med) == ME_INT_DOM)) {
00183 ViewValues<IntView> v(y);
00184 int i=0;
00185 do {
00186 int j = v.val()-o;
00187 if (i < j) {
00188 GECODE_ME_CHECK(x[i].zero(home));
00189 ++i;
00190 } else if (i > j) {
00191 ++v;
00192 } else {
00193 assert(i == j);
00194 ++i; ++v;
00195 }
00196 } while (v() && (i < n));
00197 }
00198
00199
00200 if (BoolView::me(med) == ME_BOOL_VAL) {
00201 BoolIter bv(x,o);
00202 GECODE_ME_CHECK(y.minus_v(home,bv,false));
00203 }
00204 return ES_FIX;
00205 }
00206
00207 }}}
00208
00209
00210