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