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-06-29 10:39:13 +0200 (Tue, 29 Jun 2010) $ by $Author: schulte $ 00011 * $Revision: 11118 $ 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 Iter::Ranges::IsRangeIter<I>(); 00205 ArrayRanges ar(ranges, size); 00206 return (i() && Iter::Ranges::subset(i, ar)) ? ME_SET_FAILED : ME_SET_NONE; 00207 } 00208 00209 template<class I> ModEvent 00210 ConstSetView::includeI(Space&,I& i) { 00211 Iter::Ranges::IsRangeIter<I>(); 00212 ArrayRanges ar(ranges, size); 00213 return Iter::Ranges::subset(i, ar) ? ME_SET_NONE : ME_SET_FAILED; 00214 } 00215 00216 template<class I> ModEvent 00217 ConstSetView::intersectI(Space&,I& i) { 00218 Iter::Ranges::IsRangeIter<I>(); 00219 ArrayRanges ar(ranges, size); 00220 return Iter::Ranges::subset(ar, i) ? ME_SET_NONE : ME_SET_FAILED; 00221 } 00222 00223 forceinline void 00224 ConstSetView::update(Space& home, bool share, ConstSetView& p) { 00225 ConstView<SetView>::update(home,share,p); 00226 // dispose old ranges 00227 if (size > 0) 00228 home.free<int>(ranges, 2); 00229 00230 domSize = p.domSize; 00231 size = p.size; 00232 if (size == 0) { 00233 ranges = NULL; 00234 } else { 00235 // copy ranges from p 00236 ranges = home.alloc<int>(2*size); 00237 for (int i=size; i--; ) { 00238 ranges[2*i] = p.ranges[2*i]; 00239 ranges[2*i+1] = p.ranges[2*i+1]; 00240 } 00241 } 00242 } 00243 00244 00245 /* 00246 * Delta information for advisors 00247 * 00248 */ 00249 forceinline int 00250 ConstSetView::glbMin(const Delta&) const { 00251 GECODE_NEVER; 00252 return 0; 00253 } 00254 forceinline int 00255 ConstSetView::glbMax(const Delta&) const { 00256 GECODE_NEVER; 00257 return 0; 00258 } 00259 forceinline bool 00260 ConstSetView::glbAny(const Delta&) const { 00261 GECODE_NEVER; 00262 return false; 00263 } 00264 forceinline int 00265 ConstSetView::lubMin(const Delta&) const { 00266 GECODE_NEVER; 00267 return 0; 00268 } 00269 forceinline int 00270 ConstSetView::lubMax(const Delta&) const { 00271 GECODE_NEVER; 00272 return 0; 00273 } 00274 forceinline bool 00275 ConstSetView::lubAny(const Delta&) const { 00276 GECODE_NEVER; 00277 return false; 00278 } 00279 00280 forceinline 00281 EmptyView::EmptyView(void) {} 00282 00283 00284 00285 forceinline unsigned int 00286 EmptyView::glbSize(void) const { return 0; } 00287 00288 forceinline unsigned int 00289 EmptyView::lubSize(void) const { return 0; } 00290 00291 forceinline unsigned int 00292 EmptyView::unknownSize(void) const { return 0; } 00293 00294 forceinline bool 00295 EmptyView::contains(int) const { return false; } 00296 00297 forceinline bool 00298 EmptyView::notContains(int) const { return true; } 00299 00300 forceinline unsigned int 00301 EmptyView::cardMin(void) const { return 0; } 00302 00303 forceinline unsigned int 00304 EmptyView::cardMax(void) const { return 0; } 00305 00306 forceinline int 00307 EmptyView::lubMin(void) const { return 0; } 00308 00309 forceinline int 00310 EmptyView::lubMax(void) const { return 0; } 00311 00312 forceinline int 00313 EmptyView::glbMin(void) const { return 0; } 00314 00315 forceinline int 00316 EmptyView::glbMax(void) const { return 0; } 00317 00318 forceinline ModEvent 00319 EmptyView::cardMin(Space&,unsigned int c) { 00320 return c==0 ? ME_SET_NONE : ME_SET_FAILED; 00321 } 00322 00323 forceinline ModEvent 00324 EmptyView::cardMax(Space&,unsigned int) { 00325 return ME_SET_NONE; 00326 } 00327 00328 00329 forceinline ModEvent 00330 EmptyView::include(Space&,int) { 00331 return ME_SET_FAILED; 00332 } 00333 00334 forceinline ModEvent 00335 EmptyView::exclude(Space&,int) { return ME_SET_NONE; } 00336 00337 forceinline ModEvent 00338 EmptyView::intersect(Space&,int) { return ME_SET_NONE; } 00339 00340 forceinline ModEvent 00341 EmptyView::intersect(Space&,int,int) { return ME_SET_NONE; } 00342 00343 forceinline ModEvent 00344 EmptyView::include(Space&,int,int) { 00345 return ME_SET_FAILED; } 00346 00347 forceinline ModEvent 00348 EmptyView::exclude(Space&,int,int) { return ME_SET_NONE; } 00349 00350 template<class I> ModEvent 00351 EmptyView::excludeI(Space&,I&) { 00352 Iter::Ranges::IsRangeIter<I>(); 00353 return ME_SET_NONE; 00354 } 00355 00356 template<class I> ModEvent 00357 EmptyView::includeI(Space&,I& i) { 00358 Iter::Ranges::IsRangeIter<I>(); 00359 return i() ? ME_SET_FAILED : ME_SET_NONE; 00360 } 00361 00362 template<class I> ModEvent 00363 EmptyView::intersectI(Space&,I&) { 00364 Iter::Ranges::IsRangeIter<I>(); 00365 return ME_SET_NONE; 00366 } 00367 00368 /* 00369 * Delta information for advisors 00370 * 00371 */ 00372 forceinline int 00373 EmptyView::glbMin(const Delta&) const { 00374 GECODE_NEVER; 00375 return 0; 00376 } 00377 00378 forceinline int 00379 EmptyView::glbMax(const Delta&) const { 00380 GECODE_NEVER; 00381 return 0; 00382 } 00383 00384 forceinline bool 00385 EmptyView::glbAny(const Delta&) const { 00386 GECODE_NEVER; 00387 return false; 00388 } 00389 00390 forceinline int 00391 EmptyView::lubMin(const Delta&) const { 00392 GECODE_NEVER; 00393 return 0; 00394 } 00395 00396 forceinline int 00397 EmptyView::lubMax(const Delta&) const { 00398 GECODE_NEVER; 00399 return 0; 00400 } 00401 00402 forceinline bool 00403 EmptyView::lubAny(const Delta&) const { 00404 GECODE_NEVER; 00405 return false; 00406 } 00407 00408 // Constant universe variable 00409 00410 forceinline 00411 UniverseView::UniverseView(void) {} 00412 00413 forceinline unsigned int 00414 UniverseView::glbSize(void) const { return Set::Limits::card; } 00415 00416 forceinline unsigned int 00417 UniverseView::lubSize(void) const { return Set::Limits::card; } 00418 00419 forceinline unsigned int 00420 UniverseView::unknownSize(void) const { return 0; } 00421 00422 forceinline bool 00423 UniverseView::contains(int) const { return true; } 00424 00425 forceinline bool 00426 UniverseView::notContains(int) const { return false; } 00427 00428 forceinline unsigned int 00429 UniverseView::cardMin(void) const { return Set::Limits::card; } 00430 00431 forceinline unsigned int 00432 UniverseView::cardMax(void) const { return Limits::card; } 00433 00434 forceinline int 00435 UniverseView::lubMin(void) const { return Limits::card; } 00436 00437 forceinline int 00438 UniverseView::lubMax(void) const { return Limits::card; } 00439 00440 forceinline int 00441 UniverseView::glbMin(void) const { return Limits::card; } 00442 00443 forceinline int 00444 UniverseView::glbMax(void) const { return Limits::card; } 00445 00446 forceinline ModEvent 00447 UniverseView::cardMin(Space&,unsigned int c) { 00448 return c>Limits::card ? ME_SET_FAILED : ME_SET_NONE; 00449 } 00450 00451 forceinline ModEvent 00452 UniverseView::cardMax(Space&,unsigned int c) { 00453 return c>=Limits::card ? ME_SET_NONE : ME_SET_FAILED; 00454 } 00455 00456 00457 forceinline ModEvent 00458 UniverseView::include(Space&,int) { 00459 return ME_SET_NONE; 00460 } 00461 00462 forceinline ModEvent 00463 UniverseView::exclude(Space&,int) { return ME_SET_FAILED; } 00464 00465 forceinline ModEvent 00466 UniverseView::intersect(Space&,int) { return ME_SET_FAILED; } 00467 00468 forceinline ModEvent 00469 UniverseView::include(Space&,int,int) { return ME_SET_NONE; } 00470 00471 forceinline ModEvent 00472 UniverseView::exclude(Space&,int,int) { return ME_SET_FAILED; } 00473 00474 template<class I> ModEvent 00475 UniverseView::excludeI(Space&,I& i) { 00476 Iter::Ranges::IsRangeIter<I>(); 00477 return i() ? ME_SET_FAILED : ME_SET_NONE; 00478 } 00479 00480 template<class I> forceinline ModEvent 00481 UniverseView::includeI(Space&,I&) { 00482 Iter::Ranges::IsRangeIter<I>(); 00483 return ME_SET_NONE; 00484 } 00485 00486 forceinline ModEvent 00487 UniverseView::intersect(Space&,int i,int j) { 00488 return (i>Limits::min || 00489 j<Limits::max) ? ME_SET_FAILED : ME_SET_NONE; 00490 } 00491 00492 template<class I> forceinline ModEvent 00493 UniverseView::intersectI(Space&,I& i) { 00494 Iter::Ranges::IsRangeIter<I>(); 00495 return (i() && 00496 (i.min()>Limits::min || 00497 i.max()<Limits::max) ) ? 00498 ME_SET_FAILED : ME_SET_NONE; 00499 } 00500 00501 00502 /* 00503 * Delta information for advisors 00504 * 00505 */ 00506 forceinline int 00507 UniverseView::glbMin(const Delta&) const { 00508 GECODE_NEVER; 00509 return 0; 00510 } 00511 00512 forceinline int 00513 UniverseView::glbMax(const Delta&) const { 00514 GECODE_NEVER; 00515 return 0; 00516 } 00517 00518 forceinline bool 00519 UniverseView::glbAny(const Delta&) const { 00520 GECODE_NEVER; 00521 return false; 00522 } 00523 00524 forceinline int 00525 UniverseView::lubMin(const Delta&) const { 00526 GECODE_NEVER; 00527 return 0; 00528 } 00529 00530 forceinline int 00531 UniverseView::lubMax(const Delta&) const { 00532 GECODE_NEVER; 00533 return 0; 00534 } 00535 00536 forceinline bool 00537 UniverseView::lubAny(const Delta&) const { 00538 GECODE_NEVER; 00539 return false; 00540 } 00541 00542 /* 00543 * Iterators 00544 * 00545 */ 00546 00551 template<> 00552 class LubRanges<EmptyView> : public Iter::Ranges::Empty { 00553 public: 00555 00556 00557 LubRanges(void) {} 00559 LubRanges(const EmptyView& x) { (void)x; } 00561 void init(const EmptyView& x) { (void)x; } 00563 }; 00564 00569 template<> 00570 class GlbRanges<EmptyView> : public Iter::Ranges::Empty { 00571 public: 00573 00574 00575 GlbRanges(void) {} 00577 GlbRanges(const EmptyView& x) { (void)x; } 00579 void init(const EmptyView& x) { (void)x; } 00581 }; 00582 00587 template<> 00588 class LubRanges<UniverseView> : public Iter::Ranges::Singleton { 00589 public: 00591 00592 00593 LubRanges(void) 00594 : Iter::Ranges::Singleton(Limits::min, 00595 Limits::max) {} 00597 LubRanges(const UniverseView& x) 00598 : Iter::Ranges::Singleton(Limits::min, 00599 Limits::max) { 00600 (void)x; 00601 } 00603 void init(const UniverseView& x) { (void)x; } 00605 }; 00606 00611 template<> 00612 class GlbRanges<UniverseView> : public Iter::Ranges::Singleton { 00613 public: 00615 00616 00617 GlbRanges(void) 00618 : Iter::Ranges::Singleton(Limits::min, 00619 Limits::max) {} 00621 GlbRanges(const UniverseView& x) 00622 : Iter::Ranges::Singleton(Limits::min, 00623 Limits::max) { 00624 (void)x; 00625 } 00627 void init(const UniverseView& x) { (void)x; } 00629 }; 00630 00631 00636 template<> 00637 class LubRanges<ConstSetView> { 00638 private: 00639 ArrayRanges ar; 00640 public: 00642 00643 00644 LubRanges(void) {} 00646 LubRanges(const ConstSetView& x) : ar(x.ranges,x.size) {} 00648 void init(const ConstSetView& x) { 00649 ar.init(x.ranges,x.size); 00650 } 00652 00654 00655 00656 bool operator ()(void) const { return ar(); } 00658 void operator ++(void) { ++ar; } 00660 00662 00663 00664 int min(void) const { return ar.min(); } 00666 int max(void) const { return ar.max(); } 00668 unsigned int width(void) const { return ar.width(); } 00670 }; 00671 00676 template<> 00677 class GlbRanges<ConstSetView> : public LubRanges<ConstSetView> { 00678 public: 00680 00681 00682 GlbRanges(void) {} 00684 GlbRanges(const ConstSetView& x) : LubRanges<ConstSetView>(x) {} 00686 void init(const ConstSetView& x) { 00687 LubRanges<ConstSetView>::init(x); 00688 } 00690 }; 00691 00692 /* 00693 * Testing 00694 * 00695 */ 00696 forceinline bool 00697 same(const ConstSetView& x, const ConstSetView& y) { 00698 if ((x.size != y.size) || (x.domSize != y.domSize)) 00699 return false; 00700 for (int i=x.size; i--; ) 00701 if (x.ranges[2*i] != y.ranges[2*i] || 00702 x.ranges[2*i+1] != y.ranges[2*i+1]) 00703 return false; 00704 return true; 00705 } 00706 forceinline bool 00707 before(const ConstSetView& x, const ConstSetView& y) { 00708 if (x.size < y.size) 00709 return true; 00710 if (x.domSize < y.domSize) 00711 return true; 00712 for (int i=x.size; i--; ) 00713 if (x.ranges[2*i] < y.ranges[2*i] || 00714 x.ranges[2*i+1] < y.ranges[2*i+1]) 00715 return true; 00716 return false; 00717 } 00718 00719 00720 forceinline bool 00721 same(const EmptyView&, const EmptyView&) { 00722 return true; 00723 } 00724 forceinline bool 00725 same(const UniverseView&, const UniverseView&) { 00726 return true; 00727 } 00728 00729 }} 00730 00731 // STATISTICS: set-var 00732