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 Actor*
00086 LinkMulti::copy(Space& home, bool share) {
00087 return new (home) LinkMulti(home,share,*this);
00088 }
00089
00090 forceinline size_t
00091 LinkMulti::dispose(Space& home) {
00092 Advisors<Advisor> as(c);
00093 x.cancel(home,as.advisor());
00094 c.dispose(home);
00095 (void) MixNaryOnePropagator<BoolView,PC_BOOL_NONE,IntView,PC_INT_DOM>
00096 ::dispose(home);
00097 return sizeof(*this);
00098 }
00099
00100 PropCost
00101 LinkMulti::cost(const Space&, const ModEventDelta& med) const {
00102 if ((status == S_ONE) || (IntView::me(med) == ME_INT_VAL))
00103 return PropCost::unary(PropCost::LO);
00104 else
00105 return PropCost::linear(PropCost::LO, x.size());
00106 }
00107
00108 void
00109 LinkMulti::reschedule(Space& home) {
00110 if (status == S_ONE)
00111 BoolView::schedule(home,*this,ME_BOOL_VAL);
00112 y.reschedule(home,*this,PC_INT_DOM);
00113 }
00114
00115 ExecStatus
00116 LinkMulti::advise(Space&, Advisor&, const Delta& d) {
00117 if (status == S_RUN)
00118 return ES_FIX;
00119
00120 if (BoolView::one(d))
00121 status = S_ONE;
00122 return ES_NOFIX;
00123 }
00124
00125 ExecStatus
00126 LinkMulti::propagate(Space& home, const ModEventDelta& med) {
00127 int n = x.size();
00128
00129
00130 assert((y.min()-o >= 0) && (y.max()-o < n));
00131
00132 if (y.assigned()) {
00133 status = S_RUN;
00134 int j=y.val()-o;
00135 GECODE_ME_CHECK(x[j].one(home));
00136 for (int i=0; i<j; i++)
00137 GECODE_ME_CHECK(x[i].zero(home));
00138 for (int i=j+1; i<n; i++)
00139 GECODE_ME_CHECK(x[i].zero(home));
00140 return home.ES_SUBSUMED(*this);
00141 }
00142
00143
00144 if (status == S_ONE) {
00145 status = S_RUN;
00146 for (int i=0; true; i++)
00147 if (x[i].one()) {
00148 for (int j=0; j<i; j++)
00149 GECODE_ME_CHECK(x[j].zero(home));
00150 for (int j=i+1; j<n; j++)
00151 GECODE_ME_CHECK(x[j].zero(home));
00152 GECODE_ME_CHECK(y.eq(home,i+o));
00153 return home.ES_SUBSUMED(*this);
00154 }
00155 GECODE_NEVER;
00156 }
00157
00158 status = S_RUN;
00159
00160 redo:
00161
00162
00163 {
00164 int min=y.min()-o;
00165 for (int i=0; i<min; i++)
00166 GECODE_ME_CHECK(x[i].zero(home));
00167 x.drop_fst(min); o += min; n = x.size();
00168
00169 int max=y.max()-o;
00170 for (int i=max+1; i<n; i++)
00171 GECODE_ME_CHECK(x[i].zero(home));
00172 x.drop_lst(max); n = x.size();
00173 }
00174
00175 {
00176
00177 int i=0;
00178 while ((i < n) && x[i].zero()) i++;
00179 if (i >= n)
00180 return ES_FAILED;
00181 x.drop_fst(i); o += i; n = x.size();
00182 }
00183
00184 {
00185
00186 int i=n-1;
00187 while ((i >= 0) && x[i].zero()) i--;
00188 assert(i >= 0);
00189 x.drop_lst(i); n = x.size();
00190 }
00191
00192 assert(n >= 1);
00193
00194
00195 if (n == 1) {
00196 GECODE_ME_CHECK(x[0].one(home));
00197 GECODE_ME_CHECK(y.eq(home,o));
00198 return home.ES_SUBSUMED(*this);
00199 }
00200
00201
00202 GECODE_ME_CHECK(y.gq(home,o));
00203 GECODE_ME_CHECK(y.lq(home,o+n-1));
00204 if ((y.min() > o) || (y.max() < o+n-1))
00205 goto redo;
00206
00207 assert((n >= 2) && x[0].none() && x[n-1].none());
00208 assert((y.min()-o == 0) && (y.max()-o == n-1));
00209
00210
00211 if ((IntView::me(med) == ME_INT_BND) || (IntView::me(med) == ME_INT_DOM)) {
00212 ViewValues<IntView> v(y);
00213 int i=0;
00214 do {
00215 int j = v.val()-o;
00216 if (i < j) {
00217 GECODE_ME_CHECK(x[i].zero(home));
00218 ++i;
00219 } else if (i > j) {
00220 ++v;
00221 } else {
00222 assert(i == j);
00223 ++i; ++v;
00224 }
00225 } while (v() && (i < n));
00226 }
00227
00228
00229 if (BoolView::me(med) == ME_BOOL_VAL) {
00230 BoolIter bv(x,o);
00231 GECODE_ME_CHECK(y.minus_v(home,bv,false));
00232 }
00233 status = S_NONE;
00234 return ES_FIX;
00235 }
00236
00237 }}}
00238
00239
00240