1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 2 /* 3 * Main authors: 4 * Christopher Mears <Chris.Mears@monash.edu> 5 * 6 * Contributing authors: 7 * Christian Schulte <schulte@gecode.org> 8 * Guido Tack <tack@gecode.org> 9 * 10 * Copyright: 11 * Christopher Mears, 2011 12 * Christian Schulte, 2011 13 * Guido Tack, 2011 14 * 15 * This file is part of Gecode, the generic constraint 16 * development environment: 17 * http://www.gecode.org 18 * 19 * Permission is hereby granted, free of charge, to any person obtaining 20 * a copy of this software and associated documentation files (the 21 * "Software"), to deal in the Software without restriction, including 22 * without limitation the rights to use, copy, modify, merge, publish, 23 * distribute, sublicense, and/or sell copies of the Software, and to 24 * permit persons to whom the Software is furnished to do so, subject to 25 * the following conditions: 26 * 27 * The above copyright notice and this permission notice shall be 28 * included in all copies or substantial portions of the Software. 29 * 30 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 31 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 32 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 33 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 34 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 35 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 36 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 37 * 38 */ 39 40 namespace Gecode { namespace Set { namespace Precede { 41 42 template<class View> 43 forceinline Index(Space & home,Propagator & p,Council<Index> & c,int i0)44 Single<View>::Index::Index(Space& home, Propagator& p, 45 Council<Index>& c, int i0) 46 : Advisor(home,p,c), i(i0) {} 47 48 template<class View> 49 forceinline Index(Space & home,Index & a)50 Single<View>::Index::Index(Space& home, Index& a) 51 : Advisor(home,a), i(a.i) {} 52 53 54 template<class View> 55 forceinline ExecStatus updateAlpha(Space & home)56 Single<View>::updateAlpha(Space& home) { 57 int n = x.size(); 58 while (alpha < n) { 59 if (x[alpha].notContains(s)) { 60 GECODE_ME_CHECK(x[alpha].exclude(home, t)); 61 } else if (x[alpha].contains(t)) { 62 GECODE_ME_CHECK(x[alpha].include(home, s)); 63 } else { 64 break; 65 } 66 alpha++; 67 } 68 return ES_OK; 69 } 70 71 template<class View> 72 forceinline ExecStatus updateBeta(Space & home)73 Single<View>::updateBeta(Space& home) { 74 int n = x.size(); 75 do { 76 beta++; 77 } while ((beta < n) && 78 (x[beta].notContains(s) || x[beta].contains(t))); 79 if (beta > gamma) { 80 GECODE_ME_CHECK(x[alpha].exclude(home, t)); 81 GECODE_ME_CHECK(x[alpha].include(home, s)); 82 } 83 return ES_OK; 84 } 85 86 template<class View> 87 forceinline Single(Home home,ViewArray<View> & x0,int s0,int t0,int b,int g)88 Single<View>::Single(Home home, ViewArray<View>& x0, 89 int s0, int t0, int b, int g) 90 : NaryPropagator<View, PC_SET_NONE>(home,x0), 91 c(home), s(s0), t(t0), alpha(0), beta(b), gamma(g) { 92 for (int i=x.size(); i--; ) 93 if (!x[i].assigned()) 94 x[i].subscribe(home,*new (home) Index(home,*this,c,i)); 95 View::schedule(home, *this, ME_SET_BB); 96 } 97 98 template<class View> 99 inline ExecStatus post(Home home,ViewArray<View> & x,int s,int t)100 Single<View>::post(Home home, ViewArray<View>& x, int s, int t) { 101 { 102 int alpha = 0; 103 while (alpha < x.size()) { 104 if (x[alpha].notContains(s)) { 105 GECODE_ME_CHECK(x[alpha].exclude(home, t)); 106 } else if (x[alpha].contains(t)) { 107 GECODE_ME_CHECK(x[alpha].include(home, s)); 108 } else { 109 break; 110 } 111 alpha++; 112 } 113 x.drop_fst(alpha); 114 if (x.size() == 0) 115 return ES_OK; 116 } 117 // alpha has been normalized to 0 118 int beta = 0, gamma = 0; 119 do { 120 gamma++; 121 } while ((gamma < x.size()) && 122 (!x[gamma].notContains(s) || !x[gamma].contains(t))); 123 do { 124 beta++; 125 } while ((beta < x.size()) && 126 (x[beta].notContains(s) || x[beta].contains(t))); 127 if (beta > gamma) { 128 GECODE_ME_CHECK(x[0].exclude(home, t)); 129 GECODE_ME_CHECK(x[0].include(home, s)); 130 return ES_OK; 131 } 132 if (gamma < x.size()) 133 x.drop_lst(gamma); 134 (void) new (home) Single<View>(home, x, s, t, beta, gamma); 135 return ES_OK; 136 } 137 138 139 140 template<class View> 141 forceinline Single(Space & home,Single & p)142 Single<View>::Single(Space& home, Single& p) 143 : NaryPropagator<View,PC_SET_NONE>(home, p), 144 s(p.s), t(p.t), 145 alpha(p.alpha), beta(p.beta), gamma(p.gamma) { 146 c.update(home, p.c); 147 } 148 template<class View> 149 Propagator* copy(Space & home)150 Single<View>::copy(Space& home) { 151 // Try to eliminate assigned views at the beginning 152 if (alpha > 0) { 153 int i = 0; 154 while ((i < alpha) && x[i].assigned()) 155 i++; 156 x.drop_fst(i); 157 for (Advisors<Index> as(c); as(); ++as) 158 as.advisor().i -= i; 159 alpha -= i; beta -= i; gamma -= i; 160 } 161 // Try to eliminate assigned views at the end 162 if (gamma < x.size()) { 163 int i = x.size()-1; 164 while ((i > gamma) && x[i].assigned()) 165 i--; 166 x.drop_lst(i); 167 } 168 return new (home) Single<View>(home, *this); 169 } 170 171 172 template<class View> 173 inline size_t dispose(Space & home)174 Single<View>::dispose(Space& home) { 175 // Cancel remaining advisors 176 for (Advisors<Index> as(c); as(); ++as) 177 x[as.advisor().i].cancel(home,as.advisor()); 178 c.dispose(home); 179 (void) NaryPropagator<View,PC_SET_NONE>::dispose(home); 180 return sizeof(*this); 181 } 182 183 template<class View> 184 PropCost cost(const Space &,const ModEventDelta &) const185 Single<View>::cost(const Space&, const ModEventDelta&) const { 186 return PropCost::linear(PropCost::LO, x.size()); 187 } 188 189 template<class View> 190 void reschedule(Space & home)191 Single<View>::reschedule(Space& home) { 192 View::schedule(home, *this, ME_SET_BB); 193 } 194 195 template<class View> 196 ExecStatus advise(Space & home,Advisor & a0,const Delta &)197 Single<View>::advise(Space& home, Advisor& a0, const Delta&) { 198 Index& a(static_cast<Index&>(a0)); 199 int i = a.i; 200 // Check for gamma 201 if ((beta <= gamma) && (i < gamma) && 202 x[i].notContains(s) && x[i].contains(t)) 203 gamma = i; 204 if (x[i].assigned()) { 205 a.dispose(home,c); 206 if (c.empty()) 207 return ES_NOFIX; 208 } else if ((i < alpha) || (i > gamma)) { 209 x[i].cancel(home,a); 210 a.dispose(home,c); 211 return (c.empty()) ? ES_NOFIX : ES_FIX; 212 } 213 if (beta > gamma) 214 return ES_NOFIX; 215 if ((alpha == i) || (beta == i)) 216 return ES_NOFIX; 217 return ES_FIX; 218 } 219 220 template<class View> 221 ExecStatus propagate(Space & home,const ModEventDelta &)222 Single<View>::propagate(Space& home, const ModEventDelta&) { 223 int n = x.size(); 224 if (beta > gamma) { 225 GECODE_ME_CHECK(x[alpha].exclude(home, t)); 226 GECODE_ME_CHECK(x[alpha].include(home, s)); 227 return home.ES_SUBSUMED(*this); 228 } 229 if (alpha < n && (x[alpha].notContains(s) || x[alpha].contains(t))) { 230 if (x[alpha].notContains(s)) { 231 GECODE_ME_CHECK(x[alpha].exclude(home, t)); 232 } else { 233 GECODE_ME_CHECK(x[alpha].include(home, s)); 234 } 235 alpha++; 236 while (alpha < beta) { 237 if (x[alpha].notContains(s)) { 238 GECODE_ME_CHECK(x[alpha].exclude(home, t)); 239 } else { 240 GECODE_ME_CHECK(x[alpha].include(home, s)); 241 } 242 alpha++; 243 } 244 GECODE_ES_CHECK(updateAlpha(home)); 245 beta = alpha; 246 if (alpha < n) 247 GECODE_ES_CHECK(updateBeta(home)); 248 } else if ((beta < n) && (x[beta].notContains(s) || x[beta].contains(t))) { 249 GECODE_ES_CHECK(updateBeta(home)); 250 } 251 252 return (c.empty()) ? home.ES_SUBSUMED(*this) : ES_FIX; 253 } 254 255 }}} 256 257 // STATISTICS: set-prop 258