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
00039
00040
00041
00042
00043
00044 #include <gecode/set.hh>
00045 #include <gecode/int.hh>
00046 #include <gecode/set/rel.hh>
00047
00048 namespace Gecode { namespace Set { namespace Int {
00049
00050 template<class View>
00051 forceinline
00052 Match<View>::Match(Home home, View y0, ViewArray< Gecode::Int::IntView >& ys)
00053 : Propagator(home), x0(y0), xs(ys) {
00054 x0.subscribe(home,*this, PC_SET_ANY);
00055 xs.subscribe(home,*this, Gecode::Int::PC_INT_BND);
00056 }
00057
00058 template<class View>
00059 forceinline
00060 Match<View>::Match(Space& home, bool share, Match& p)
00061 : Propagator(home,share,p) {
00062 x0.update(home,share,p.x0);
00063 xs.update(home,share,p.xs);
00064 }
00065
00066 template<class View>
00067 forceinline ExecStatus
00068 Match<View>::post(Home home, View x0, ViewArray<Gecode::Int::IntView>& xs) {
00069 unsigned int xs_size = static_cast<unsigned int>(xs.size());
00070 GECODE_ME_CHECK(x0.cardMin(home,xs_size));
00071 GECODE_ME_CHECK(x0.cardMax(home,xs_size));
00072 if (xs_size == 1) {
00073 SingletonView sv(xs[0]);
00074 GECODE_ES_CHECK((Rel::Eq<View,
00075 SingletonView>::post(home,x0, sv)));
00076 } else {
00077
00078
00079 (void) new (home) Match(home,x0,xs);
00080 }
00081 return ES_OK;
00082 }
00083
00084 template<class View>
00085 PropCost
00086 Match<View>::cost(const Space&, const ModEventDelta&) const {
00087 return PropCost::linear(PropCost::LO, xs.size()+1);
00088 }
00089
00090 template<class View>
00091 forceinline size_t
00092 Match<View>::dispose(Space& home) {
00093 x0.cancel(home,*this, PC_SET_ANY);
00094 xs.cancel(home,*this, Gecode::Int::PC_INT_BND);
00095 (void) Propagator::dispose(home);
00096 return sizeof(*this);
00097 }
00098
00099 template<class View>
00100 Actor*
00101 Match<View>::copy(Space& home, bool share) {
00102 return new (home) Match(home,share,*this);
00103 }
00104
00105 template<class View>
00106 ExecStatus
00107 Match<View>::propagate(Space& home, const ModEventDelta&) {
00108
00109 int xs_size = xs.size();
00110
00111 bool loopFlag;
00112
00113 do {
00114 loopFlag = false;
00115
00116
00117 GECODE_ME_CHECK(xs[0].gq(home,x0.lubMin()));
00118 for (int i=xs_size-1; i--; ) {
00119 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i+1].gq(home,xs[i].min() + 1));
00120 }
00121
00122 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[xs_size-1].lq(home,x0.lubMax()));
00123 for (int i=xs_size-2; i--; ) {
00124 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].lq(home,xs[i+1].max() - 1));
00125 }
00126
00127
00128 for (int i=xs_size; i--; ) {
00129 if (xs[i].assigned()) {
00130 GECODE_ME_CHECK_MODIFIED(loopFlag, x0.include(home,xs[i].val()));
00131 }
00132 }
00133
00134
00135 for (int i=xs_size; i--; ) {
00136 LubRanges<View> ub(x0);
00137 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].inter_r(home,ub,false));
00138 }
00139
00140
00141 GECODE_ME_CHECK_MODIFIED(loopFlag,
00142 x0.exclude(home,Limits::min,xs[0].min()-1));
00143 GECODE_ME_CHECK_MODIFIED(loopFlag,
00144 x0.exclude(home,xs[xs_size-1].max()+1,
00145 Limits::max));
00146
00147 for (int i=xs_size-1; i--; ) {
00148 int start = xs[i].max() + 1;
00149 int end = xs[i+1].min() - 1;
00150 if (start<=end) {
00151 GECODE_ME_CHECK_MODIFIED(loopFlag, x0.exclude(home,start,end));
00152 }
00153 }
00154
00155
00156 if (x0.glbSize()>0) {
00157
00158 LubRanges<View> ub(x0);
00159 Iter::Ranges::ToValues<LubRanges<View> > ubv(ub);
00160 GlbRanges<View> lb(x0);
00161 Iter::Ranges::ToValues<GlbRanges<View> > lbv(lb);
00162
00163 int i=0;
00164 for (; ubv() && lbv() && ubv.val()==lbv.val();
00165 ++ubv, ++lbv, i++) {
00166 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].eq(home,lbv.val()));
00167 }
00168
00169 if (i<xs_size-1 && x0.lubMax()==x0.glbMax()) {
00170 LubRanges<View> lbx0(x0);
00171 GlbRanges<View> ubx0(x0);
00172 Iter::Ranges::Inter<LubRanges<View>,GlbRanges<View> >
00173 inter(lbx0, ubx0);
00174
00175 int to = x0.glbMax();
00176 int from = to;
00177 while (inter()) {
00178 from = inter.min();
00179 ++inter;
00180 }
00181
00182 int i=xs_size-1;
00183 for (int j=to; j>=from;j--,i--) {
00184 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].eq(home,j));
00185 }
00186 }
00187 }
00188
00189 } while (loopFlag);
00190
00191 for (int i=xs_size; i--; )
00192 if (!xs[i].assigned())
00193 return ES_FIX;
00194 return home.ES_SUBSUMED(*this);
00195 }
00196
00197 }}}
00198
00199