1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 2 /* 3 * Main authors: 4 * Christian Schulte <schulte@gecode.org> 5 * 6 * Copyright: 7 * Christian Schulte, 2009 8 * 9 * This file is part of Gecode, the generic constraint 10 * development environment: 11 * http://www.gecode.org 12 * 13 * Permission is hereby granted, free of charge, to any person obtaining 14 * a copy of this software and associated documentation files (the 15 * "Software"), to deal in the Software without restriction, including 16 * without limitation the rights to use, copy, modify, merge, publish, 17 * distribute, sublicense, and/or sell copies of the Software, and to 18 * permit persons to whom the Software is furnished to do so, subject to 19 * the following conditions: 20 * 21 * The above copyright notice and this permission notice shall be 22 * included in all copies or substantial portions of the Software. 23 * 24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 31 * 32 */ 33 34 namespace Gecode { 35 36 /** 37 * \brief Wait propagator for single view 38 * 39 * Requires \code #include <gecode/kernel/wait.hh> \endcode 40 * \ingroup FuncKernelProp 41 */ 42 template<class View> 43 class UnaryWait : public Propagator { 44 protected: 45 /// View to wait for becoming assigned 46 View x; 47 /// Continuation to execute 48 SharedData<std::function<void(Space& home)>> c; 49 /// Constructor for creation 50 UnaryWait(Home home, View x, std::function<void(Space& home)> c0); 51 /// Constructor for cloning \a p 52 UnaryWait(Space& home, UnaryWait& p); 53 public: 54 /// Perform copying during cloning 55 virtual Actor* copy(Space& home); 56 /// Const function (defined as low unary) 57 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 58 /// Schedule function 59 virtual void reschedule(Space& home); 60 /// Perform propagation 61 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 62 /// Post propagator that waits until \a x becomes assigned and then executes \a c 63 static ExecStatus post(Home home, View x, 64 std::function<void(Space& home)> c); 65 /// Delete propagator and return its size 66 virtual size_t dispose(Space& home); 67 }; 68 69 /** 70 * \brief Wait propagator for several views 71 * 72 * Requires \code #include <gecode/kernel/wait.hh> \endcode 73 * \ingroup FuncKernelProp 74 */ 75 template<class View> 76 class NaryWait : public Propagator { 77 protected: 78 /// Views to wait for becoming assigned 79 ViewArray<View> x; 80 /// Continuation to execute 81 SharedData<std::function<void(Space& home)>> c; 82 /// Constructor for creation 83 NaryWait(Home home, ViewArray<View>& x, 84 std::function<void(Space& home)> c0); 85 /// Constructor for cloning \a p 86 NaryWait(Space& home, NaryWait& p); 87 public: 88 /// Perform copying during cloning 89 virtual Actor* copy(Space& home); 90 /// Const function (defined as high unary) 91 virtual PropCost cost(const Space& home, const ModEventDelta& med) const; 92 /// Schedule function 93 virtual void reschedule(Space& home); 94 /// Perform propagation 95 virtual ExecStatus propagate(Space& home, const ModEventDelta& med); 96 /// Post propagator that waits until \a x becomes assigned and then executes \a c 97 static ExecStatus post(Home home, ViewArray<View>& x, 98 std::function<void(Space& home)> c); 99 /// Delete propagator and return its size 100 virtual size_t dispose(Space& home); 101 }; 102 103 104 /* 105 * Wait propagator for single view 106 * 107 */ 108 template<class View> 109 forceinline UnaryWait(Home home,View x0,std::function<void (Space & home)> c0)110 UnaryWait<View>::UnaryWait(Home home, View x0, 111 std::function<void(Space& home)> c0) 112 : Propagator(home), x(x0), c(c0) { 113 x.subscribe(home,*this,PC_GEN_ASSIGNED); 114 home.notice(*this,AP_DISPOSE); 115 } 116 template<class View> 117 forceinline UnaryWait(Space & home,UnaryWait & p)118 UnaryWait<View>::UnaryWait(Space& home, UnaryWait& p) 119 : Propagator(home,p), c(p.c) { 120 x.update(home,p.x); 121 } 122 template<class View> 123 Actor* copy(Space & home)124 UnaryWait<View>::copy(Space& home) { 125 return new (home) UnaryWait<View>(home,*this); 126 } 127 template<class View> 128 PropCost cost(const Space &,const ModEventDelta &) const129 UnaryWait<View>::cost(const Space&, const ModEventDelta&) const { 130 return PropCost::unary(PropCost::LO); 131 } 132 template<class View> 133 void reschedule(Space & home)134 UnaryWait<View>::reschedule(Space& home) { 135 x.reschedule(home,*this,PC_GEN_ASSIGNED); 136 } 137 template<class View> 138 ExecStatus propagate(Space & home,const ModEventDelta &)139 UnaryWait<View>::propagate(Space& home, const ModEventDelta&) { 140 assert(x.assigned()); 141 GECODE_VALID_FUNCTION(c()); 142 c()(home); 143 return home.failed() ? ES_FAILED : home.ES_SUBSUMED(*this); 144 } 145 template<class View> 146 forceinline ExecStatus post(Home home,View x,std::function<void (Space & home)> c)147 UnaryWait<View>::post(Home home, View x, 148 std::function<void(Space& home)> c) { 149 if (!c) 150 throw InvalidFunction("UnaryWait::post"); 151 if (x.assigned()) { 152 c(home); 153 return home.failed() ? ES_FAILED : ES_OK; 154 } else { 155 (void) new (home) UnaryWait<View>(home,x,c); 156 return ES_OK; 157 } 158 } 159 template<class View> 160 size_t dispose(Space & home)161 UnaryWait<View>::dispose(Space& home) { 162 x.cancel(home,*this,PC_GEN_ASSIGNED); 163 home.ignore(*this,AP_DISPOSE); 164 c.~SharedData<std::function<void(Space& home)>>(); 165 (void) Propagator::dispose(home); 166 return sizeof(*this); 167 } 168 169 170 /* 171 * Wait propagator for several views 172 * 173 */ 174 template<class View> 175 forceinline NaryWait(Home home,ViewArray<View> & x0,std::function<void (Space & home)> c0)176 NaryWait<View>::NaryWait(Home home, ViewArray<View>& x0, 177 std::function<void(Space& home)> c0) 178 : Propagator(home), x(x0), c(c0) { 179 assert(!x[0].assigned()); 180 x[0].subscribe(home,*this,PC_GEN_ASSIGNED); 181 home.notice(*this,AP_DISPOSE); 182 } 183 template<class View> 184 forceinline NaryWait(Space & home,NaryWait & p)185 NaryWait<View>::NaryWait(Space& home, NaryWait& p) 186 : Propagator(home,p), c(p.c) { 187 x.update(home,p.x); 188 } 189 template<class View> 190 Actor* copy(Space & home)191 NaryWait<View>::copy(Space& home) { 192 assert(!x[0].assigned()); 193 for (int i=x.size()-1; i>0; i--) 194 if (x[i].assigned()) 195 x.move_lst(i); 196 assert(x.size() > 0); 197 return new (home) NaryWait<View>(home,*this); 198 } 199 template<class View> 200 PropCost cost(const Space &,const ModEventDelta &) const201 NaryWait<View>::cost(const Space&, const ModEventDelta&) const { 202 return PropCost::unary(PropCost::HI); 203 } 204 template<class View> 205 void reschedule(Space & home)206 NaryWait<View>::reschedule(Space& home) { 207 x[0].reschedule(home,*this,PC_GEN_ASSIGNED); 208 } 209 template<class View> 210 ExecStatus propagate(Space & home,const ModEventDelta &)211 NaryWait<View>::propagate(Space& home, const ModEventDelta& ) { 212 assert(x[0].assigned()); 213 for (int i=x.size()-1; i>0; i--) 214 if (x[i].assigned()) 215 x.move_lst(i); 216 assert(x.size() > 0); 217 if (x.size() == 1) { 218 x.size(0); 219 GECODE_VALID_FUNCTION(c()); 220 c()(home); 221 return home.failed() ? ES_FAILED : home.ES_SUBSUMED(*this); 222 } else { 223 // Create new subscription 224 x.move_lst(0); 225 assert(!x[0].assigned()); 226 x[0].subscribe(home,*this,PC_GEN_ASSIGNED,false); 227 return ES_OK; 228 } 229 } 230 template<class View> 231 forceinline ExecStatus post(Home home,ViewArray<View> & x,std::function<void (Space & home)> c)232 NaryWait<View>::post(Home home, ViewArray<View>& x, 233 std::function<void(Space& home)> c) { 234 if (!c) 235 throw InvalidFunction("NaryWait::post"); 236 for (int i=x.size(); i--; ) 237 if (x[i].assigned()) 238 x.move_lst(i); 239 if (x.size() == 0) { 240 c(home); 241 return home.failed() ? ES_FAILED : ES_OK; 242 } else { 243 x.unique(); 244 if (x.size() == 1) { 245 return UnaryWait<View>::post(home,x[0],c); 246 } else { 247 (void) new (home) NaryWait<View>(home,x,c); 248 return ES_OK; 249 } 250 } 251 } 252 template<class View> 253 size_t dispose(Space & home)254 NaryWait<View>::dispose(Space& home) { 255 if (x.size() > 0) 256 x[0].cancel(home,*this,PC_GEN_ASSIGNED); 257 home.ignore(*this,AP_DISPOSE); 258 c.~SharedData<std::function<void(Space& home)>>(); 259 (void) Propagator::dispose(home); 260 return sizeof(*this); 261 } 262 263 } 264 265 // STATISTICS: kernel-prop 266