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 "set/int.hh"
00031
00032 #include "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 Match::~Match(void) {
00042 x0.cancel(this, PC_SET_ANY);
00043 xs.cancel(this, Gecode::Int::PC_INT_BND);
00044 }
00045
00046 Actor*
00047 Match::copy(Space* home, bool share) {
00048 return new (home) Match(home,share,*this);
00049 }
00050
00051 ExecStatus
00052 Match::propagate(Space* home) {
00053
00054 int xs_size = xs.size();
00055
00056 bool loopFlag;
00057
00058 do {
00059 loopFlag = false;
00060
00061
00062 GECODE_ME_CHECK(xs[0].gq(home,x0.lubMin()));
00063 for (int i=xs_size-1; i--; ) {
00064 GECODE_ME_CHECK(xs[i+1].gq(home,xs[i].min() + 1));
00065 }
00066
00067 GECODE_ME_CHECK(xs[xs_size-1].lq(home,x0.lubMax()));
00068 for (int i=xs_size-2; i--; ) {
00069 GECODE_ME_CHECK(xs[i].lq(home,xs[i+1].max() - 1));
00070 }
00071
00072
00073 for (int i=xs_size; i--; ) {
00074 if (xs[i].assigned())
00075 GECODE_ME_CHECK(x0.include(home,xs[i].val()));
00076 }
00077
00078
00079 for (int i=xs_size; i--; ) {
00080 LubRanges<SetView> ub(x0);
00081 ModEvent me = xs[i].inter(home,ub);
00082 if (me_modified(me)) {
00083 loopFlag = true;
00084 } else {
00085 GECODE_ME_CHECK(me);
00086 }
00087 }
00088
00089
00090 ModEvent me1 =
00091 x0.exclude(home,Limits::Set::int_min,xs[0].min()-1);
00092 ModEvent me2 =
00093 x0.exclude(home,xs[xs_size-1].max()+1,Limits::Set::int_max);
00094 if (me_modified(me1)) {
00095 loopFlag = true;
00096 } else {
00097 GECODE_ME_CHECK(me1);
00098 }
00099 if (me_modified(me2)) {
00100 loopFlag = true;
00101 } else {
00102 GECODE_ME_CHECK(me2);
00103 }
00104 for (int i=xs_size-1; i--; ) {
00105 int start = xs[i].max() + 1;
00106 int end = xs[i+1].min() - 1;
00107 if (start<=end) {
00108 ModEvent me = x0.exclude(home,start,end);
00109 if (me_modified(me)) {
00110 loopFlag = true;
00111 } else {
00112 GECODE_ME_CHECK(me);
00113 }
00114 }
00115 }
00116
00117
00118 if (x0.glbSize()>0) {
00119
00120 LubRanges<SetView> ub(x0);
00121 Iter::Ranges::ToValues<LubRanges<SetView> > ubv(ub);
00122 GlbRanges<SetView> lb(x0);
00123 Iter::Ranges::ToValues<GlbRanges<SetView> > lbv(lb);
00124
00125 int i=0;
00126 for (; ubv() && lbv() && ubv.val()==lbv.val();
00127 ++ubv, ++lbv, i++) {
00128 ModEvent me = (xs[i].eq(home,lbv.val()));
00129 if (me_modified(me)) {
00130 loopFlag = true;
00131 } else {
00132 GECODE_ME_CHECK(me);
00133 }
00134 }
00135
00136 if (i<xs_size-1 && x0.lubMax()==x0.glbMax()) {
00137 LubRanges<SetView> lbx0(x0);
00138 GlbRanges<SetView> ubx0(x0);
00139 Iter::Ranges::Inter<LubRanges<SetView>,GlbRanges<SetView> >
00140 inter(lbx0, ubx0);
00141
00142 int to = x0.glbMax();
00143 int from = to;
00144 while (inter()) {
00145 from = inter.min();
00146 ++inter;
00147 }
00148
00149 int i=xs_size-1;
00150 for (int j=to; j>=from;j--,i--) {
00151 ModEvent me = xs[i].eq(home,j);
00152 if (me_modified(me)) {
00153 loopFlag = true;
00154 } else {
00155 GECODE_ME_CHECK(me);
00156 }
00157 }
00158 }
00159 }
00160
00161 } while (loopFlag);
00162
00163 for (int i=xs_size; i--; )
00164 if (!xs[i].assigned())
00165 return ES_FIX;
00166 return ES_SUBSUMED;
00167 }
00168
00169 }}}
00170
00171