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