match.cc
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 #include "gecode/set/int.hh"
00031
00032 #include "gecode/iter.hh"
00033
00034 namespace Gecode { namespace Set { namespace Int {
00035
00036 PropCost
00037 Match::cost(void) const {
00038 return PC_LINEAR_LO;
00039 }
00040
00041 size_t
00042 Match::dispose(Space* home) {
00043 assert(!home->failed());
00044 x0.cancel(home,this, PC_SET_ANY);
00045 xs.cancel(home,this, Gecode::Int::PC_INT_BND);
00046 (void) Propagator::dispose(home);
00047 return sizeof(*this);
00048 }
00049
00050 Actor*
00051 Match::copy(Space* home, bool share) {
00052 return new (home) Match(home,share,*this);
00053 }
00054
00055 ExecStatus
00056 Match::propagate(Space* home) {
00057
00058 int xs_size = xs.size();
00059
00060 bool loopFlag;
00061
00062 do {
00063 loopFlag = false;
00064
00065
00066 GECODE_ME_CHECK(xs[0].gq(home,x0.lubMin()));
00067 for (int i=xs_size-1; i--; ) {
00068 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i+1].gq(home,xs[i].min() + 1));
00069 }
00070
00071 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[xs_size-1].lq(home,x0.lubMax()));
00072 for (int i=xs_size-2; i--; ) {
00073 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].lq(home,xs[i+1].max() - 1));
00074 }
00075
00076
00077 for (int i=xs_size; i--; ) {
00078 if (xs[i].assigned()) {
00079 GECODE_ME_CHECK_MODIFIED(loopFlag, x0.include(home,xs[i].val()));
00080 }
00081 }
00082
00083
00084 for (int i=xs_size; i--; ) {
00085 LubRanges<SetView> ub(x0);
00086 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].inter(home,ub));
00087 }
00088
00089
00090 GECODE_ME_CHECK_MODIFIED(loopFlag,
00091 x0.exclude(home,Limits::Set::int_min,xs[0].min()-1));
00092 GECODE_ME_CHECK_MODIFIED(loopFlag,
00093 x0.exclude(home,xs[xs_size-1].max()+1,
00094 Limits::Set::int_max));
00095
00096 for (int i=xs_size-1; i--; ) {
00097 int start = xs[i].max() + 1;
00098 int end = xs[i+1].min() - 1;
00099 if (start<=end) {
00100 GECODE_ME_CHECK_MODIFIED(loopFlag, x0.exclude(home,start,end));
00101 }
00102 }
00103
00104
00105 if (x0.glbSize()>0) {
00106
00107 LubRanges<SetView> ub(x0);
00108 Iter::Ranges::ToValues<LubRanges<SetView> > ubv(ub);
00109 GlbRanges<SetView> lb(x0);
00110 Iter::Ranges::ToValues<GlbRanges<SetView> > lbv(lb);
00111
00112 int i=0;
00113 for (; ubv() && lbv() && ubv.val()==lbv.val();
00114 ++ubv, ++lbv, i++) {
00115 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].eq(home,lbv.val()));
00116 }
00117
00118 if (i<xs_size-1 && x0.lubMax()==x0.glbMax()) {
00119 LubRanges<SetView> lbx0(x0);
00120 GlbRanges<SetView> ubx0(x0);
00121 Iter::Ranges::Inter<LubRanges<SetView>,GlbRanges<SetView> >
00122 inter(lbx0, ubx0);
00123
00124 int to = x0.glbMax();
00125 int from = to;
00126 while (inter()) {
00127 from = inter.min();
00128 ++inter;
00129 }
00130
00131 int i=xs_size-1;
00132 for (int j=to; j>=from;j--,i--) {
00133 GECODE_ME_CHECK_MODIFIED(loopFlag, xs[i].eq(home,j));
00134 }
00135 }
00136 }
00137
00138 } while (loopFlag);
00139
00140 for (int i=xs_size; i--; )
00141 if (!xs[i].assigned())
00142 return ES_FIX;
00143 return ES_SUBSUMED;
00144 }
00145
00146 }}}
00147
00148