const.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Guido Tack <tack@gecode.org> 00005 * 00006 * Copyright: 00007 * Guido Tack, 2004 00008 * 00009 * Last modified: 00010 * $Date: 2010-07-28 17:35:33 +0200 (Wed, 28 Jul 2010) $ by $Author: schulte $ 00011 * $Revision: 11294 $ 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 Set { 00039 00044 class ArrayRanges { 00045 private: 00046 int *_ranges; 00047 int _size; 00048 int _pos; 00049 public: 00051 00052 00053 ArrayRanges(void) : _ranges(NULL), _size(0), _pos(0) {} 00055 ArrayRanges(int *ranges, int size) 00056 : _ranges(ranges), _size(size), _pos(0) {} 00058 void init(int* ranges, int size) { 00059 _ranges = ranges; _size = size; _pos = 0; 00060 } 00062 00064 00065 00066 bool operator ()(void) const { return _pos<_size; } 00068 void operator ++(void) { _pos++; } 00070 00072 00073 00074 int min(void) const { return _ranges[_pos*2]; } 00076 int max(void) const { return _ranges[_pos*2+1]; } 00078 unsigned int width(void) const { 00079 return static_cast<unsigned int>(_ranges[_pos*2+1]-_ranges[_pos*2]+1); 00080 } 00082 }; 00083 00084 forceinline 00085 ConstSetView::ConstSetView(void) : ranges(NULL), size(0), domSize(0) {} 00086 00087 forceinline 00088 ConstSetView::ConstSetView(Space& home, const IntSet& dom) { 00089 size = dom.ranges(); 00090 domSize = 0; 00091 if (size > 0) { 00092 ranges = home.alloc<int>(2*size); 00093 IntSetRanges dr(dom); 00094 for (int i=0; dr(); ++dr, i+=2) { 00095 int min = dr.min(); int max = dr.max(); 00096 ranges[i] = min; 00097 ranges[i+1] = max; 00098 domSize += static_cast<unsigned int>(max-min+1); 00099 } 00100 } else { 00101 ranges = NULL; 00102 } 00103 } 00104 00105 forceinline unsigned int 00106 ConstSetView::glbSize(void) const { return domSize; } 00107 00108 forceinline unsigned int 00109 ConstSetView::lubSize(void) const { return domSize; } 00110 00111 forceinline unsigned int 00112 ConstSetView::unknownSize(void) const { return 0; } 00113 00114 forceinline bool 00115 ConstSetView::contains(int i) const { 00116 for (int j=size; j--; ) { 00117 if (ranges[2*j+1] < i) 00118 return false; 00119 if (ranges[2*j] >= i) 00120 return true; 00121 } 00122 return false; 00123 } 00124 00125 forceinline bool 00126 ConstSetView::notContains(int i) const { 00127 return !contains(i); 00128 } 00129 00130 forceinline unsigned int 00131 ConstSetView::cardMin(void) const { return domSize; } 00132 00133 forceinline unsigned int 00134 ConstSetView::cardMax(void) const { return domSize; } 00135 00136 forceinline int 00137 ConstSetView::lubMin(void) const { 00138 return size==0 ? BndSet::MIN_OF_EMPTY : ranges[0]; 00139 } 00140 00141 forceinline int 00142 ConstSetView::lubMax(void) const { 00143 return size==0 ? BndSet::MAX_OF_EMPTY : ranges[size*2-1]; 00144 } 00145 00146 forceinline int 00147 ConstSetView::glbMin(void) const { return lubMin(); } 00148 00149 forceinline int 00150 ConstSetView::glbMax(void) const { return lubMax(); } 00151 00152 forceinline ModEvent 00153 ConstSetView::cardMin(Space&,unsigned int c) { 00154 return c<=domSize ? ME_SET_NONE : ME_SET_FAILED; 00155 } 00156 00157 forceinline ModEvent 00158 ConstSetView::cardMax(Space&,unsigned int c) { 00159 return c>=domSize ? ME_SET_NONE : ME_SET_FAILED; 00160 } 00161 00162 forceinline ModEvent 00163 ConstSetView::include(Space&,int c) { 00164 return contains(c) ? ME_SET_NONE : ME_SET_FAILED; 00165 } 00166 00167 forceinline ModEvent 00168 ConstSetView::exclude(Space&,int c) { 00169 return contains(c) ? ME_SET_FAILED : ME_SET_NONE; 00170 } 00171 00172 forceinline ModEvent 00173 ConstSetView::intersect(Space&,int c) { 00174 return (size==0 || 00175 (size==1 && 00176 ranges[0]==ranges[1] && ranges[0]==c)) ? 00177 ME_SET_NONE : ME_SET_FAILED; 00178 } 00179 00180 forceinline ModEvent 00181 ConstSetView::intersect(Space&,int i,int j) { 00182 return (glbMin()>=i && glbMax()<=j) ? 00183 ME_SET_NONE : ME_SET_FAILED; 00184 } 00185 00186 forceinline ModEvent 00187 ConstSetView::include(Space&,int i,int j) { 00188 Iter::Ranges::Singleton single(i,j); 00189 ArrayRanges ar(ranges, size); 00190 return (single() && Iter::Ranges::subset(single, ar)) ? 00191 ME_SET_NONE : ME_SET_FAILED; 00192 } 00193 00194 forceinline ModEvent 00195 ConstSetView::exclude(Space&,int i,int j) { 00196 Iter::Ranges::Singleton single(i,j); 00197 ArrayRanges ar(ranges, size); 00198 return (single() && Iter::Ranges::subset(single, ar)) ? 00199 ME_SET_FAILED : ME_SET_NONE; 00200 } 00201 00202 template<class I> ModEvent 00203 ConstSetView::excludeI(Space&,I& i) { 00204 ArrayRanges ar(ranges, size); 00205 return (i() && Iter::Ranges::subset(i, ar)) ? ME_SET_FAILED : ME_SET_NONE; 00206 } 00207 00208 template<class I> ModEvent 00209 ConstSetView::includeI(Space&,I& i) { 00210 ArrayRanges ar(ranges, size); 00211 return Iter::Ranges::subset(i, ar) ? ME_SET_NONE : ME_SET_FAILED; 00212 } 00213 00214 template<class I> ModEvent 00215 ConstSetView::intersectI(Space&,I& i) { 00216 ArrayRanges ar(ranges, size); 00217 return Iter::Ranges::subset(ar, i) ? ME_SET_NONE : ME_SET_FAILED; 00218 } 00219 00220 forceinline void 00221 ConstSetView::update(Space& home, bool share, ConstSetView& p) { 00222 ConstView<SetView>::update(home,share,p); 00223 // dispose old ranges 00224 if (size > 0) 00225 home.free<int>(ranges, 2); 00226 00227 domSize = p.domSize; 00228 size = p.size; 00229 if (size == 0) { 00230 ranges = NULL; 00231 } else { 00232 // copy ranges from p 00233 ranges = home.alloc<int>(2*size); 00234 for (int i=size; i--; ) { 00235 ranges[2*i] = p.ranges[2*i]; 00236 ranges[2*i+1] = p.ranges[2*i+1]; 00237 } 00238 } 00239 } 00240 00241 00242 /* 00243 * Delta information for advisors 00244 * 00245 */ 00246 forceinline int 00247 ConstSetView::glbMin(const Delta&) const { 00248 GECODE_NEVER; 00249 return 0; 00250 } 00251 forceinline int 00252 ConstSetView::glbMax(const Delta&) const { 00253 GECODE_NEVER; 00254 return 0; 00255 } 00256 forceinline bool 00257 ConstSetView::glbAny(const Delta&) const { 00258 GECODE_NEVER; 00259 return false; 00260 } 00261 forceinline int 00262 ConstSetView::lubMin(const Delta&) const { 00263 GECODE_NEVER; 00264 return 0; 00265 } 00266 forceinline int 00267 ConstSetView::lubMax(const Delta&) const { 00268 GECODE_NEVER; 00269 return 0; 00270 } 00271 forceinline bool 00272 ConstSetView::lubAny(const Delta&) const { 00273 GECODE_NEVER; 00274 return false; 00275 } 00276 00277 forceinline 00278 EmptyView::EmptyView(void) {} 00279 00280 00281 00282 forceinline unsigned int 00283 EmptyView::glbSize(void) const { return 0; } 00284 00285 forceinline unsigned int 00286 EmptyView::lubSize(void) const { return 0; } 00287 00288 forceinline unsigned int 00289 EmptyView::unknownSize(void) const { return 0; } 00290 00291 forceinline bool 00292 EmptyView::contains(int) const { return false; } 00293 00294 forceinline bool 00295 EmptyView::notContains(int) const { return true; } 00296 00297 forceinline unsigned int 00298 EmptyView::cardMin(void) const { return 0; } 00299 00300 forceinline unsigned int 00301 EmptyView::cardMax(void) const { return 0; } 00302 00303 forceinline int 00304 EmptyView::lubMin(void) const { return 0; } 00305 00306 forceinline int 00307 EmptyView::lubMax(void) const { return 0; } 00308 00309 forceinline int 00310 EmptyView::glbMin(void) const { return 0; } 00311 00312 forceinline int 00313 EmptyView::glbMax(void) const { return 0; } 00314 00315 forceinline ModEvent 00316 EmptyView::cardMin(Space&,unsigned int c) { 00317 return c==0 ? ME_SET_NONE : ME_SET_FAILED; 00318 } 00319 00320 forceinline ModEvent 00321 EmptyView::cardMax(Space&,unsigned int) { 00322 return ME_SET_NONE; 00323 } 00324 00325 00326 forceinline ModEvent 00327 EmptyView::include(Space&,int) { 00328 return ME_SET_FAILED; 00329 } 00330 00331 forceinline ModEvent 00332 EmptyView::exclude(Space&,int) { return ME_SET_NONE; } 00333 00334 forceinline ModEvent 00335 EmptyView::intersect(Space&,int) { return ME_SET_NONE; } 00336 00337 forceinline ModEvent 00338 EmptyView::intersect(Space&,int,int) { return ME_SET_NONE; } 00339 00340 forceinline ModEvent 00341 EmptyView::include(Space&,int,int) { 00342 return ME_SET_FAILED; } 00343 00344 forceinline ModEvent 00345 EmptyView::exclude(Space&,int,int) { return ME_SET_NONE; } 00346 00347 template<class I> ModEvent 00348 EmptyView::excludeI(Space&,I&) { 00349 return ME_SET_NONE; 00350 } 00351 00352 template<class I> ModEvent 00353 EmptyView::includeI(Space&,I& i) { 00354 return i() ? ME_SET_FAILED : ME_SET_NONE; 00355 } 00356 00357 template<class I> ModEvent 00358 EmptyView::intersectI(Space&,I&) { 00359 return ME_SET_NONE; 00360 } 00361 00362 /* 00363 * Delta information for advisors 00364 * 00365 */ 00366 forceinline int 00367 EmptyView::glbMin(const Delta&) const { 00368 GECODE_NEVER; 00369 return 0; 00370 } 00371 00372 forceinline int 00373 EmptyView::glbMax(const Delta&) const { 00374 GECODE_NEVER; 00375 return 0; 00376 } 00377 00378 forceinline bool 00379 EmptyView::glbAny(const Delta&) const { 00380 GECODE_NEVER; 00381 return false; 00382 } 00383 00384 forceinline int 00385 EmptyView::lubMin(const Delta&) const { 00386 GECODE_NEVER; 00387 return 0; 00388 } 00389 00390 forceinline int 00391 EmptyView::lubMax(const Delta&) const { 00392 GECODE_NEVER; 00393 return 0; 00394 } 00395 00396 forceinline bool 00397 EmptyView::lubAny(const Delta&) const { 00398 GECODE_NEVER; 00399 return false; 00400 } 00401 00402 // Constant universe variable 00403 00404 forceinline 00405 UniverseView::UniverseView(void) {} 00406 00407 forceinline unsigned int 00408 UniverseView::glbSize(void) const { return Set::Limits::card; } 00409 00410 forceinline unsigned int 00411 UniverseView::lubSize(void) const { return Set::Limits::card; } 00412 00413 forceinline unsigned int 00414 UniverseView::unknownSize(void) const { return 0; } 00415 00416 forceinline bool 00417 UniverseView::contains(int) const { return true; } 00418 00419 forceinline bool 00420 UniverseView::notContains(int) const { return false; } 00421 00422 forceinline unsigned int 00423 UniverseView::cardMin(void) const { return Set::Limits::card; } 00424 00425 forceinline unsigned int 00426 UniverseView::cardMax(void) const { return Limits::card; } 00427 00428 forceinline int 00429 UniverseView::lubMin(void) const { return Limits::card; } 00430 00431 forceinline int 00432 UniverseView::lubMax(void) const { return Limits::card; } 00433 00434 forceinline int 00435 UniverseView::glbMin(void) const { return Limits::card; } 00436 00437 forceinline int 00438 UniverseView::glbMax(void) const { return Limits::card; } 00439 00440 forceinline ModEvent 00441 UniverseView::cardMin(Space&,unsigned int c) { 00442 return c>Limits::card ? ME_SET_FAILED : ME_SET_NONE; 00443 } 00444 00445 forceinline ModEvent 00446 UniverseView::cardMax(Space&,unsigned int c) { 00447 return c>=Limits::card ? ME_SET_NONE : ME_SET_FAILED; 00448 } 00449 00450 00451 forceinline ModEvent 00452 UniverseView::include(Space&,int) { 00453 return ME_SET_NONE; 00454 } 00455 00456 forceinline ModEvent 00457 UniverseView::exclude(Space&,int) { return ME_SET_FAILED; } 00458 00459 forceinline ModEvent 00460 UniverseView::intersect(Space&,int) { return ME_SET_FAILED; } 00461 00462 forceinline ModEvent 00463 UniverseView::include(Space&,int,int) { return ME_SET_NONE; } 00464 00465 forceinline ModEvent 00466 UniverseView::exclude(Space&,int,int) { return ME_SET_FAILED; } 00467 00468 template<class I> ModEvent 00469 UniverseView::excludeI(Space&,I& i) { 00470 return i() ? ME_SET_FAILED : ME_SET_NONE; 00471 } 00472 00473 template<class I> forceinline ModEvent 00474 UniverseView::includeI(Space&,I&) { 00475 return ME_SET_NONE; 00476 } 00477 00478 forceinline ModEvent 00479 UniverseView::intersect(Space&,int i,int j) { 00480 return (i>Limits::min || 00481 j<Limits::max) ? ME_SET_FAILED : ME_SET_NONE; 00482 } 00483 00484 template<class I> forceinline ModEvent 00485 UniverseView::intersectI(Space&,I& i) { 00486 return (i() && 00487 (i.min()>Limits::min || 00488 i.max()<Limits::max) ) ? 00489 ME_SET_FAILED : ME_SET_NONE; 00490 } 00491 00492 00493 /* 00494 * Delta information for advisors 00495 * 00496 */ 00497 forceinline int 00498 UniverseView::glbMin(const Delta&) const { 00499 GECODE_NEVER; 00500 return 0; 00501 } 00502 00503 forceinline int 00504 UniverseView::glbMax(const Delta&) const { 00505 GECODE_NEVER; 00506 return 0; 00507 } 00508 00509 forceinline bool 00510 UniverseView::glbAny(const Delta&) const { 00511 GECODE_NEVER; 00512 return false; 00513 } 00514 00515 forceinline int 00516 UniverseView::lubMin(const Delta&) const { 00517 GECODE_NEVER; 00518 return 0; 00519 } 00520 00521 forceinline int 00522 UniverseView::lubMax(const Delta&) const { 00523 GECODE_NEVER; 00524 return 0; 00525 } 00526 00527 forceinline bool 00528 UniverseView::lubAny(const Delta&) const { 00529 GECODE_NEVER; 00530 return false; 00531 } 00532 00533 /* 00534 * Iterators 00535 * 00536 */ 00537 00542 template<> 00543 class LubRanges<EmptyView> : public Iter::Ranges::Empty { 00544 public: 00546 00547 00548 LubRanges(void) {} 00550 LubRanges(const EmptyView& x) { (void)x; } 00552 void init(const EmptyView& x) { (void)x; } 00554 }; 00555 00560 template<> 00561 class GlbRanges<EmptyView> : public Iter::Ranges::Empty { 00562 public: 00564 00565 00566 GlbRanges(void) {} 00568 GlbRanges(const EmptyView& x) { (void)x; } 00570 void init(const EmptyView& x) { (void)x; } 00572 }; 00573 00578 template<> 00579 class LubRanges<UniverseView> : public Iter::Ranges::Singleton { 00580 public: 00582 00583 00584 LubRanges(void) 00585 : Iter::Ranges::Singleton(Limits::min, 00586 Limits::max) {} 00588 LubRanges(const UniverseView& x) 00589 : Iter::Ranges::Singleton(Limits::min, 00590 Limits::max) { 00591 (void)x; 00592 } 00594 void init(const UniverseView& x) { (void)x; } 00596 }; 00597 00602 template<> 00603 class GlbRanges<UniverseView> : public Iter::Ranges::Singleton { 00604 public: 00606 00607 00608 GlbRanges(void) 00609 : Iter::Ranges::Singleton(Limits::min, 00610 Limits::max) {} 00612 GlbRanges(const UniverseView& x) 00613 : Iter::Ranges::Singleton(Limits::min, 00614 Limits::max) { 00615 (void)x; 00616 } 00618 void init(const UniverseView& x) { (void)x; } 00620 }; 00621 00622 00627 template<> 00628 class LubRanges<ConstSetView> { 00629 private: 00630 ArrayRanges ar; 00631 public: 00633 00634 00635 LubRanges(void) {} 00637 LubRanges(const ConstSetView& x) : ar(x.ranges,x.size) {} 00639 void init(const ConstSetView& x) { 00640 ar.init(x.ranges,x.size); 00641 } 00643 00645 00646 00647 bool operator ()(void) const { return ar(); } 00649 void operator ++(void) { ++ar; } 00651 00653 00654 00655 int min(void) const { return ar.min(); } 00657 int max(void) const { return ar.max(); } 00659 unsigned int width(void) const { return ar.width(); } 00661 }; 00662 00667 template<> 00668 class GlbRanges<ConstSetView> : public LubRanges<ConstSetView> { 00669 public: 00671 00672 00673 GlbRanges(void) {} 00675 GlbRanges(const ConstSetView& x) : LubRanges<ConstSetView>(x) {} 00677 void init(const ConstSetView& x) { 00678 LubRanges<ConstSetView>::init(x); 00679 } 00681 }; 00682 00683 /* 00684 * Testing 00685 * 00686 */ 00687 forceinline bool 00688 same(const ConstSetView& x, const ConstSetView& y) { 00689 if ((x.size != y.size) || (x.domSize != y.domSize)) 00690 return false; 00691 for (int i=x.size; i--; ) 00692 if (x.ranges[2*i] != y.ranges[2*i] || 00693 x.ranges[2*i+1] != y.ranges[2*i+1]) 00694 return false; 00695 return true; 00696 } 00697 forceinline bool 00698 before(const ConstSetView& x, const ConstSetView& y) { 00699 if (x.size < y.size) 00700 return true; 00701 if (x.domSize < y.domSize) 00702 return true; 00703 for (int i=x.size; i--; ) 00704 if (x.ranges[2*i] < y.ranges[2*i] || 00705 x.ranges[2*i+1] < y.ranges[2*i+1]) 00706 return true; 00707 return false; 00708 } 00709 00710 00711 forceinline bool 00712 same(const EmptyView&, const EmptyView&) { 00713 return true; 00714 } 00715 forceinline bool 00716 same(const UniverseView&, const UniverseView&) { 00717 return true; 00718 } 00719 00720 }} 00721 00722 // STATISTICS: set-var 00723