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 void
00094 ChannelSorted<View>::reschedule(Space& home) {
00095 x0.reschedule(home,*this, PC_SET_ANY);
00096 xs.reschedule(home,*this, Gecode::Int::PC_INT_BND);
00097 }
00098
00099 template<class View>
00100 forceinline size_t
00101 ChannelSorted<View>::dispose(Space& home) {
00102 x0.cancel(home,*this, PC_SET_ANY);
00103 xs.cancel(home,*this, Gecode::Int::PC_INT_BND);
00104 (void) Propagator::dispose(home);
00105 return sizeof(*this);
00106 }
00107
00108 template<class View>
00109 Actor*
00110 ChannelSorted<View>::copy(Space& home, bool share) {
00111 return new (home) ChannelSorted(home,share,*this);
00112 }
00113
00114 template<class View>
00115 ExecStatus
00116 ChannelSorted<View>::propagate(Space& home, const ModEventDelta&) {
00117
00118 int xs_size = xs.size();
00119
00120 bool loopFlag;
00121
00122 do {
00123 loopFlag = false;
00124
00125
00126 GECODE_ME_CHECK(xs[0].gq(home,x0.lubMin()));
00127 for (int i=xs_size-1; i--; ) {
00128 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i+1].gq(home,xs[i].min() + 1));
00129 }
00130
00131 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[xs_size-1].lq(home,x0.lubMax()));
00132 for (int i=xs_size-2; i--; ) {
00133 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].lq(home,xs[i+1].max() - 1));
00134 }
00135
00136
00137 for (int i=xs_size; i--; ) {
00138 if (xs[i].assigned()) {
00139 GECODE_ME_CHECK_MODIFIED(loopFlag, x0.include(home,xs[i].val()));
00140 }
00141 }
00142
00143
00144 for (int i=xs_size; i--; ) {
00145 LubRanges<View> ub(x0);
00146 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].inter_r(home,ub,false));
00147 }
00148
00149
00150 GECODE_ME_CHECK_MODIFIED(loopFlag,
00151 x0.exclude(home,Limits::min,xs[0].min()-1));
00152 GECODE_ME_CHECK_MODIFIED(loopFlag,
00153 x0.exclude(home,xs[xs_size-1].max()+1,
00154 Limits::max));
00155
00156 for (int i=xs_size-1; i--; ) {
00157 int start = xs[i].max() + 1;
00158 int end = xs[i+1].min() - 1;
00159 if (start<=end) {
00160 GECODE_ME_CHECK_MODIFIED(loopFlag, x0.exclude(home,start,end));
00161 }
00162 }
00163
00164
00165 if (x0.glbSize()>0) {
00166
00167 LubRanges<View> ub(x0);
00168 Iter::Ranges::ToValues<LubRanges<View> > ubv(ub);
00169 GlbRanges<View> lb(x0);
00170 Iter::Ranges::ToValues<GlbRanges<View> > lbv(lb);
00171
00172 int i=0;
00173 for (; ubv() && lbv() && ubv.val()==lbv.val();
00174 ++ubv, ++lbv, i++) {
00175 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].eq(home,lbv.val()));
00176 }
00177
00178 if (i<xs_size-1 && x0.lubMax()==x0.glbMax()) {
00179 LubRanges<View> lbx0(x0);
00180 GlbRanges<View> ubx0(x0);
00181 Iter::Ranges::Inter<LubRanges<View>,GlbRanges<View> >
00182 inter(lbx0, ubx0);
00183
00184 int to = x0.glbMax();
00185 int from = to;
00186 while (inter()) {
00187 from = inter.min();
00188 ++inter;
00189 }
00190
00191 int k=xs_size-1;
00192 for (int j=to; j>=from;j--,k--) {
00193 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[k].eq(home,j));
00194 }
00195 }
00196 }
00197
00198 } while (loopFlag);
00199
00200 for (int i=xs_size; i--; )
00201 if (!xs[i].assigned())
00202 return ES_FIX;
00203 return home.ES_SUBSUMED(*this);
00204 }
00205
00206 }}}
00207
00208