task.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * Guido Tack <tack@gecode.org> 00006 * 00007 * Copyright: 00008 * Christian Schulte, 2009 00009 * Guido Tack, 2010 00010 * 00011 * Last modified: 00012 * $Date: 2011-01-18 23:37:08 +0100 (Tue, 18 Jan 2011) $ by $Author: tack $ 00013 * $Revision: 11551 $ 00014 * 00015 * This file is part of Gecode, the generic constraint 00016 * development environment: 00017 * http://www.gecode.org 00018 * 00019 * Permission is hereby granted, free of charge, to any person obtaining 00020 * a copy of this software and associated documentation files (the 00021 * "Software"), to deal in the Software without restriction, including 00022 * without limitation the rights to use, copy, modify, merge, publish, 00023 * distribute, sublicense, and/or sell copies of the Software, and to 00024 * permit persons to whom the Software is furnished to do so, subject to 00025 * the following conditions: 00026 * 00027 * The above copyright notice and this permission notice shall be 00028 * included in all copies or substantial portions of the Software. 00029 * 00030 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00031 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00032 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00033 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00034 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00035 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00036 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00037 * 00038 */ 00039 00040 namespace Gecode { namespace Scheduling { namespace Unary { 00041 00042 /* 00043 * Mandatory fixed task 00044 */ 00045 00046 forceinline 00047 ManFixPTask::ManFixPTask(void) {} 00048 forceinline 00049 ManFixPTask::ManFixPTask(IntVar s, int p) : _s(s), _p(p) {} 00050 forceinline void 00051 ManFixPTask::init(IntVar s, int p) { 00052 _s=s; _p=p; 00053 } 00054 forceinline void 00055 ManFixPTask::init(const ManFixPTask& t) { 00056 _s=t._s; _p=t._p; 00057 } 00058 00059 forceinline int 00060 ManFixPTask::est(void) const { 00061 return _s.min(); 00062 } 00063 forceinline int 00064 ManFixPTask::ect(void) const { 00065 return _s.min()+_p; 00066 } 00067 forceinline int 00068 ManFixPTask::lst(void) const { 00069 return _s.max(); 00070 } 00071 forceinline int 00072 ManFixPTask::lct(void) const { 00073 return _s.max()+_p; 00074 } 00075 forceinline int 00076 ManFixPTask::pmin(void) const { 00077 return _p; 00078 } 00079 forceinline int 00080 ManFixPTask::pmax(void) const { 00081 return _p; 00082 } 00083 forceinline IntVar 00084 ManFixPTask::st(void) const { 00085 return _s; 00086 } 00087 00088 forceinline bool 00089 ManFixPTask::mandatory(void) const { 00090 return true; 00091 } 00092 forceinline bool 00093 ManFixPTask::excluded(void) const { 00094 return false; 00095 } 00096 forceinline bool 00097 ManFixPTask::optional(void) const { 00098 return false; 00099 } 00100 00101 forceinline bool 00102 ManFixPTask::assigned(void) const { 00103 return _s.assigned(); 00104 } 00105 00106 forceinline ModEvent 00107 ManFixPTask::est(Space& home, int n) { 00108 return _s.gq(home,n); 00109 } 00110 forceinline ModEvent 00111 ManFixPTask::ect(Space& home, int n) { 00112 return _s.gq(home,n-_p); 00113 } 00114 forceinline ModEvent 00115 ManFixPTask::lst(Space& home, int n) { 00116 return _s.lq(home,n); 00117 } 00118 forceinline ModEvent 00119 ManFixPTask::lct(Space& home, int n) { 00120 return _s.lq(home,n-_p); 00121 } 00122 forceinline ModEvent 00123 ManFixPTask::norun(Space& home, int e, int l) { 00124 if (e <= l) { 00125 Iter::Ranges::Singleton r(e-_p+1,l); 00126 return _s.minus_r(home,r,false); 00127 } else { 00128 return Int::ME_INT_NONE; 00129 } 00130 } 00131 00132 00133 forceinline ModEvent 00134 ManFixPTask::mandatory(Space&) { 00135 return Int::ME_INT_NONE; 00136 } 00137 forceinline ModEvent 00138 ManFixPTask::excluded(Space&) { 00139 return Int::ME_INT_FAILED; 00140 } 00141 00142 forceinline void 00143 ManFixPTask::update(Space& home, bool share, ManFixPTask& t) { 00144 _s.update(home,share,t._s); _p=t._p; 00145 } 00146 00147 forceinline void 00148 ManFixPTask::subscribe(Space& home, Propagator& p, PropCond pc) { 00149 _s.subscribe(home, p, pc); 00150 } 00151 forceinline void 00152 ManFixPTask::cancel(Space& home, Propagator& p, PropCond pc) { 00153 _s.cancel(home, p, pc); 00154 } 00155 00156 template<class Char, class Traits> 00157 std::basic_ostream<Char,Traits>& 00158 operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTask& t) { 00159 std::basic_ostringstream<Char,Traits> s; 00160 s.copyfmt(os); s.width(0); 00161 s << t.est() << ':' << t.pmin() << ':' << t.lct(); 00162 return os << s.str(); 00163 } 00164 00165 /* 00166 * Mandatory fixed task with fixed processing, start or end time 00167 */ 00168 00169 forceinline 00170 ManFixPSETask::ManFixPSETask(void) {} 00171 forceinline 00172 ManFixPSETask::ManFixPSETask(TaskType t, IntVar s, int p) 00173 : ManFixPTask(s,p), _t(t) {} 00174 forceinline void 00175 ManFixPSETask::init(TaskType t, IntVar s, int p) { 00176 ManFixPTask::init(s,p); _t=t; 00177 } 00178 forceinline void 00179 ManFixPSETask::init(const ManFixPSETask& t0) { 00180 ManFixPTask::init(t0); _t = t0._t; 00181 } 00182 00183 forceinline int 00184 ManFixPSETask::est(void) const { 00185 return (_t == TT_FIXS) ? _p : _s.min(); 00186 } 00187 forceinline int 00188 ManFixPSETask::ect(void) const { 00189 switch (_t) { 00190 case TT_FIXP: return _s.min()+_p; 00191 case TT_FIXS: return _s.min(); 00192 case TT_FIXE: return _p; 00193 default: GECODE_NEVER; 00194 } 00195 return 0; 00196 } 00197 forceinline int 00198 ManFixPSETask::lst(void) const { 00199 return (_t == TT_FIXS) ? _p : _s.max(); 00200 } 00201 forceinline int 00202 ManFixPSETask::lct(void) const { 00203 switch (_t) { 00204 case TT_FIXP: return _s.max()+_p; 00205 case TT_FIXS: return _s.max(); 00206 case TT_FIXE: return _p; 00207 default: GECODE_NEVER; 00208 } 00209 return 0; 00210 } 00211 forceinline int 00212 ManFixPSETask::pmin(void) const { 00213 switch (_t) { 00214 case TT_FIXP: return _p; 00215 case TT_FIXS: return _s.min()-_p; 00216 case TT_FIXE: return _p-_s.max(); 00217 default: GECODE_NEVER; 00218 } 00219 return 0; 00220 } 00221 forceinline int 00222 ManFixPSETask::pmax(void) const { 00223 switch (_t) { 00224 case TT_FIXP: return _p; 00225 case TT_FIXS: return _s.max()-_p; 00226 case TT_FIXE: return _p-_s.min(); 00227 default: GECODE_NEVER; 00228 } 00229 return 0; 00230 } 00231 00232 forceinline ModEvent 00233 ManFixPSETask::est(Space& home, int n) { 00234 switch (_t) { 00235 case TT_FIXE: // fall through 00236 case TT_FIXP: return _s.gq(home,n); 00237 case TT_FIXS: return (n <= _p) ? Int::ME_INT_NONE : Int::ME_INT_FAILED; 00238 default: GECODE_NEVER; 00239 } 00240 return Int::ME_INT_NONE; 00241 } 00242 forceinline ModEvent 00243 ManFixPSETask::ect(Space& home, int n) { 00244 switch (_t) { 00245 case TT_FIXE: return (n <= _p) ? Int::ME_INT_NONE : Int::ME_INT_FAILED; 00246 case TT_FIXP: return _s.gq(home,n-_p); 00247 case TT_FIXS: return _s.gq(home,n); 00248 default: GECODE_NEVER; 00249 } 00250 return Int::ME_INT_NONE; 00251 } 00252 forceinline ModEvent 00253 ManFixPSETask::lst(Space& home, int n) { 00254 switch (_t) { 00255 case TT_FIXE: // fall through 00256 case TT_FIXP: return _s.lq(home,n); 00257 case TT_FIXS: return (n >= _p) ? Int::ME_INT_NONE : Int::ME_INT_FAILED; 00258 default: GECODE_NEVER; 00259 } 00260 return Int::ME_INT_NONE; 00261 } 00262 forceinline ModEvent 00263 ManFixPSETask::lct(Space& home, int n) { 00264 switch (_t) { 00265 case TT_FIXE: return (n >= _p) ? Int::ME_INT_NONE : Int::ME_INT_FAILED; 00266 case TT_FIXP: return _s.lq(home,n-_p); 00267 case TT_FIXS: return _s.lq(home,n); 00268 default: GECODE_NEVER; 00269 } 00270 return Int::ME_INT_NONE; 00271 } 00272 forceinline ModEvent 00273 ManFixPSETask::norun(Space& home, int e, int l) { 00274 if (e <= l) { 00275 switch (_t) { 00276 case TT_FIXP: 00277 { 00278 Iter::Ranges::Singleton r(e-_p+1,l); 00279 return _s.minus_r(home,r,false); 00280 } 00281 case TT_FIXE: 00282 if (e <= _p) 00283 return _s.gr(home,l); 00284 break; 00285 case TT_FIXS: 00286 if (l >= _p) 00287 return _s.lq(home,e); 00288 break; 00289 default: 00290 GECODE_NEVER; 00291 } 00292 return Int::ME_INT_NONE; 00293 } else { 00294 return Int::ME_INT_NONE; 00295 } 00296 } 00297 00298 forceinline void 00299 ManFixPSETask::update(Space& home, bool share, ManFixPSETask& t) { 00300 ManFixPTask::update(home,share,t); _t=t._t; 00301 } 00302 00303 template<class Char, class Traits> 00304 std::basic_ostream<Char,Traits>& 00305 operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETask& t) { 00306 std::basic_ostringstream<Char,Traits> s; 00307 s.copyfmt(os); s.width(0); 00308 s << t.est() << ':' << t.pmin() << ':' << t.lct(); 00309 return os << s.str(); 00310 } 00311 00312 /* 00313 * Mandatory flexible task 00314 */ 00315 00316 forceinline 00317 ManFlexTask::ManFlexTask(void) {} 00318 forceinline 00319 ManFlexTask::ManFlexTask(IntVar s, IntVar p, IntVar e) 00320 : _s(s), _p(p), _e(e) {} 00321 forceinline void 00322 ManFlexTask::init(IntVar s, IntVar p, IntVar e) { 00323 _s=s; _p=p; _e=e; 00324 } 00325 forceinline void 00326 ManFlexTask::init(const ManFlexTask& t) { 00327 _s=t._s; _p=t._p; _e=t._e; 00328 } 00329 00330 forceinline int 00331 ManFlexTask::est(void) const { 00332 return _s.min(); 00333 } 00334 forceinline int 00335 ManFlexTask::ect(void) const { 00336 return _e.min(); 00337 } 00338 forceinline int 00339 ManFlexTask::lst(void) const { 00340 return _s.max(); 00341 } 00342 forceinline int 00343 ManFlexTask::lct(void) const { 00344 return _e.max(); 00345 } 00346 forceinline int 00347 ManFlexTask::pmin(void) const { 00348 return _p.min(); 00349 } 00350 forceinline int 00351 ManFlexTask::pmax(void) const { 00352 return _p.max(); 00353 } 00354 forceinline IntVar 00355 ManFlexTask::st(void) const { 00356 return _s; 00357 } 00358 forceinline IntVar 00359 ManFlexTask::p(void) const { 00360 return _p; 00361 } 00362 forceinline IntVar 00363 ManFlexTask::e(void) const { 00364 return _e; 00365 } 00366 00367 forceinline bool 00368 ManFlexTask::mandatory(void) const { 00369 return true; 00370 } 00371 forceinline bool 00372 ManFlexTask::excluded(void) const { 00373 return false; 00374 } 00375 forceinline bool 00376 ManFlexTask::optional(void) const { 00377 return false; 00378 } 00379 00380 forceinline bool 00381 ManFlexTask::assigned(void) const { 00382 return _s.assigned() && _p.assigned() && _e.assigned(); 00383 } 00384 00385 forceinline ModEvent 00386 ManFlexTask::est(Space& home, int n) { 00387 return _s.gq(home,n); 00388 } 00389 forceinline ModEvent 00390 ManFlexTask::ect(Space& home, int n) { 00391 return _e.gq(home,n); 00392 } 00393 forceinline ModEvent 00394 ManFlexTask::lst(Space& home, int n) { 00395 return _s.lq(home,n); 00396 } 00397 forceinline ModEvent 00398 ManFlexTask::lct(Space& home, int n) { 00399 return _e.lq(home,n); 00400 } 00401 forceinline ModEvent 00402 ManFlexTask::norun(Space& home, int e, int l) { 00403 if (e <= l) { 00404 Iter::Ranges::Singleton sr(e-_p.min()+1,l); 00405 GECODE_ME_CHECK(_s.minus_r(home,sr,false)); 00406 Iter::Ranges::Singleton er(e+1,_p.min()+l); 00407 return _e.minus_r(home,er,false); 00408 } else { 00409 return Int::ME_INT_NONE; 00410 } 00411 } 00412 00413 00414 forceinline ModEvent 00415 ManFlexTask::mandatory(Space&) { 00416 return Int::ME_INT_NONE; 00417 } 00418 forceinline ModEvent 00419 ManFlexTask::excluded(Space&) { 00420 return Int::ME_INT_FAILED; 00421 } 00422 00423 forceinline void 00424 ManFlexTask::update(Space& home, bool share, ManFlexTask& t) { 00425 _s.update(home,share,t._s); 00426 _p.update(home,share,t._p); 00427 _e.update(home,share,t._e); 00428 } 00429 00430 forceinline void 00431 ManFlexTask::subscribe(Space& home, Propagator& p, PropCond pc) { 00432 _s.subscribe(home, p, pc); 00433 _p.subscribe(home, p, pc); 00434 _e.subscribe(home, p, pc); 00435 } 00436 forceinline void 00437 ManFlexTask::cancel(Space& home, Propagator& p, PropCond pc) { 00438 _s.cancel(home, p, pc); 00439 _p.cancel(home, p, pc); 00440 _e.cancel(home, p, pc); 00441 } 00442 00443 template<class Char, class Traits> 00444 std::basic_ostream<Char,Traits>& 00445 operator <<(std::basic_ostream<Char,Traits>& os, const ManFlexTask& t) { 00446 std::basic_ostringstream<Char,Traits> s; 00447 s.copyfmt(os); s.width(0); 00448 s << t.est() << ':' << t.lst() << ':' << t.pmin() << ':' 00449 << t.pmax() << ':' << t.ect() << ':' << t.lct(); 00450 return os << s.str(); 00451 } 00452 00453 /* 00454 * Optional fixed task 00455 */ 00456 00457 forceinline 00458 OptFixPTask::OptFixPTask(void) {} 00459 forceinline 00460 OptFixPTask::OptFixPTask(IntVar s, int p, BoolVar m) { 00461 ManFixPTask::init(s,p); _m=m; 00462 } 00463 forceinline void 00464 OptFixPTask::init(IntVar s, int p, BoolVar m) { 00465 ManFixPTask::init(s,p); _m=m; 00466 } 00467 00468 template<class Char, class Traits> 00469 std::basic_ostream<Char,Traits>& 00470 operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPTask& t) { 00471 std::basic_ostringstream<Char,Traits> s; 00472 s.copyfmt(os); s.width(0); 00473 s << t.est() << ':' << t.pmin() << ':' << t.lct() << ':' 00474 << (t.mandatory() ? '1' : (t.optional() ? '?' : '0')); 00475 return os << s.str(); 00476 } 00477 00478 /* 00479 * Optional fixed task 00480 */ 00481 00482 forceinline 00483 OptFixPSETask::OptFixPSETask(void) {} 00484 forceinline 00485 OptFixPSETask::OptFixPSETask(TaskType t,IntVar s,int p,BoolVar m) { 00486 ManFixPSETask::init(t,s,p); _m=m; 00487 } 00488 forceinline void 00489 OptFixPSETask::init(TaskType t, IntVar s, int p, BoolVar m) { 00490 ManFixPSETask::init(t,s,p); _m=m; 00491 } 00492 00493 template<class Char, class Traits> 00494 std::basic_ostream<Char,Traits>& 00495 operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPSETask& t) { 00496 std::basic_ostringstream<Char,Traits> s; 00497 s.copyfmt(os); s.width(0); 00498 s << t.est() << ':' << t.pmin() << ':' << t.lct() << ':' 00499 << (t.mandatory() ? '1' : (t.optional() ? '?' : '0')); 00500 return os << s.str(); 00501 } 00502 00503 /* 00504 * Optional flexible task 00505 */ 00506 00507 forceinline 00508 OptFlexTask::OptFlexTask(void) {} 00509 forceinline 00510 OptFlexTask::OptFlexTask(IntVar s, IntVar p, IntVar e, BoolVar m) { 00511 ManFlexTask::init(s,p,e); _m=m; 00512 } 00513 forceinline void 00514 OptFlexTask::init(IntVar s, IntVar p, IntVar e, BoolVar m) { 00515 ManFlexTask::init(s,p,e); _m=m; 00516 } 00517 00518 template<class Char, class Traits> 00519 std::basic_ostream<Char,Traits>& 00520 operator <<(std::basic_ostream<Char,Traits>& os, const OptFlexTask& t) { 00521 std::basic_ostringstream<Char,Traits> s; 00522 s.copyfmt(os); s.width(0); 00523 s << t.est() << ':' << t.lst() << ':' << t.pmin() << ':' 00524 << t.pmax() << ':' << t.ect() << ':' << t.lct() << ':' 00525 << (t.mandatory() ? '1' : (t.optional() ? '?' : '0')); 00526 return os << s.str(); 00527 } 00528 00529 }}} 00530 00531 // STATISTICS: scheduling-var