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