complement.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 * Contributing authors: 00007 * Christian Schulte <schulte@gecode.org> 00008 * 00009 * Copyright: 00010 * Guido Tack, 2004 00011 * Christian Schulte, 2004 00012 * 00013 * Last modified: 00014 * $Date: 2010-06-29 10:39:13 +0200 (Tue, 29 Jun 2010) $ by $Author: schulte $ 00015 * $Revision: 11118 $ 00016 * 00017 * This file is part of Gecode, the generic constraint 00018 * development environment: 00019 * http://www.gecode.org 00020 * 00021 * Permission is hereby granted, free of charge, to any person obtaining 00022 * a copy of this software and associated documentation files (the 00023 * "Software"), to deal in the Software without restriction, including 00024 * without limitation the rights to use, copy, modify, merge, publish, 00025 * distribute, sublicense, and/or sell copies of the Software, and to 00026 * permit persons to whom the Software is furnished to do so, subject to 00027 * the following conditions: 00028 * 00029 * The above copyright notice and this permission notice shall be 00030 * included in all copies or substantial portions of the Software. 00031 * 00032 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00033 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00034 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00035 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00036 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00037 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00038 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00039 * 00040 */ 00041 00042 #include <sstream> 00043 00044 namespace Gecode { namespace Set { 00045 00046 template<class View> 00047 forceinline 00048 ComplementView<View>::ComplementView(void) {} 00049 00050 template<class View> 00051 forceinline 00052 ComplementView<View>::ComplementView(View& y) 00053 : DerivedView<View>(y) {} 00054 00055 template<class View> 00056 forceinline ModEvent 00057 ComplementView<View>::me_negateset(ModEvent me) { 00058 switch(me) { 00059 case ME_SET_LUB : return ME_SET_GLB; 00060 case ME_SET_GLB : return ME_SET_LUB; 00061 case ME_SET_CLUB : return ME_SET_CGLB; 00062 case ME_SET_CGLB : return ME_SET_CLUB; 00063 default: return me; 00064 } 00065 } 00066 00067 template<class View> 00068 forceinline PropCond 00069 ComplementView<View>::pc_negateset(PropCond pc) { 00070 switch(pc) { 00071 case PC_SET_CLUB : return PC_SET_CGLB; 00072 case PC_SET_CGLB : return PC_SET_CLUB; 00073 default: return pc; 00074 } 00075 } 00076 00077 template<class View> 00078 forceinline unsigned int 00079 ComplementView<View>::glbSize(void) const { 00080 return Limits::card - x.lubSize(); 00081 } 00082 00083 template<class View> 00084 forceinline unsigned int 00085 ComplementView<View>::lubSize(void) const { 00086 return Limits::card - x.glbSize(); 00087 } 00088 00089 template<class View> 00090 forceinline unsigned int 00091 ComplementView<View>::unknownSize(void) const { 00092 return lubSize() - glbSize(); 00093 } 00094 00095 template<class View> 00096 forceinline bool 00097 ComplementView<View>::contains(int n) const { return x.notContains(n); } 00098 00099 template<class View> 00100 forceinline bool 00101 ComplementView<View>::notContains(int n) const { return x.contains(n); } 00102 00103 template<class View> 00104 forceinline unsigned int 00105 ComplementView<View>::cardMin(void) const { 00106 return Limits::card - x.cardMax(); 00107 } 00108 00109 template<class View> 00110 forceinline unsigned int 00111 ComplementView<View>::cardMax(void) const { 00112 return Limits::card - x.cardMin(); 00113 } 00114 00115 template<class View> 00116 forceinline int 00117 ComplementView<View>::lubMin(void) const { 00118 GlbRanges<View> lb(x); 00119 RangesCompl<GlbRanges<View> > lbc(lb); 00120 if (lbc()) { 00121 return lbc.min(); 00122 } else { 00123 return BndSet::MIN_OF_EMPTY; 00124 } 00125 } 00126 00127 template<class View> 00128 forceinline int 00129 ComplementView<View>::lubMax(void) const { 00130 GlbRanges<View> lb(x); 00131 RangesCompl<GlbRanges<View> > lbc(lb); 00132 if (lbc()) { 00133 while(lbc()) ++lbc; 00134 return lbc.max(); 00135 } else { 00136 return BndSet::MAX_OF_EMPTY; 00137 } 00138 } 00139 00140 template<class View> 00141 forceinline int 00142 ComplementView<View>::glbMin(void) const { 00143 LubRanges<View> ub(x); 00144 RangesCompl<LubRanges<View> > ubc(ub); 00145 if (ubc()) { 00146 return ubc.min(); 00147 } else { 00148 return BndSet::MIN_OF_EMPTY; 00149 } 00150 } 00151 00152 template<class View> 00153 forceinline int 00154 ComplementView<View>::glbMax(void) const { 00155 LubRanges<View> ub(x); 00156 RangesCompl<LubRanges<View> > ubc(ub); 00157 if (ubc()) { 00158 while (ubc()) ++ubc; 00159 return ubc.max(); 00160 } else { 00161 return BndSet::MAX_OF_EMPTY; 00162 } 00163 } 00164 00165 template<class View> 00166 forceinline ModEvent 00167 ComplementView<View>::cardMin(Space& home, unsigned int c) { 00168 if (c < Limits::card) 00169 return me_negateset(x.cardMax(home, Limits::card - c)); 00170 return ME_SET_NONE; 00171 } 00172 00173 template<class View> 00174 forceinline ModEvent 00175 ComplementView<View>::cardMax(Space& home, unsigned int c) { 00176 if (c < Limits::card) 00177 return me_negateset(x.cardMin(home, Limits::card - c)); 00178 return ME_SET_NONE; 00179 } 00180 00181 template<class View> 00182 forceinline ModEvent 00183 ComplementView<View>::include(Space& home, int c) { 00184 return me_negateset((x.exclude(home, c))); 00185 } 00186 00187 template<class View> 00188 forceinline ModEvent 00189 ComplementView<View>::exclude(Space& home, int c) { 00190 return me_negateset((x.include(home, c))); 00191 } 00192 00193 template<class View> 00194 forceinline ModEvent 00195 ComplementView<View>::intersect(Space& home, int c) { 00196 Iter::Ranges::Singleton si(c,c); 00197 RangesCompl<Iter::Ranges::Singleton> csi(si); 00198 return me_negateset((x.includeI(home, csi))); 00199 } 00200 00201 template<class View> 00202 forceinline ModEvent 00203 ComplementView<View>::intersect(Space& home, int i, int j) { 00204 Iter::Ranges::Singleton si(i,j); 00205 RangesCompl<Iter::Ranges::Singleton> csi(si); 00206 return me_negateset((x.includeI(home, csi))); 00207 } 00208 00209 template<class View> 00210 forceinline ModEvent 00211 ComplementView<View>::include(Space& home, int j, int k) { 00212 return me_negateset(x.exclude(home,j,k)); 00213 } 00214 00215 template<class View> 00216 forceinline ModEvent 00217 ComplementView<View>::exclude(Space& home, int j, int k) { 00218 return me_negateset(x.include(home,j,k)); 00219 } 00220 00221 template<class View> 00222 template<class I> ModEvent 00223 ComplementView<View>::excludeI(Space& home,I& iter) { 00224 return me_negateset(x.includeI(home,iter)); 00225 } 00226 00227 template<class View> 00228 template<class I> ModEvent 00229 ComplementView<View>::includeI(Space& home,I& iter) { 00230 return me_negateset(x.excludeI(home,iter)); 00231 } 00232 00233 template<class View> 00234 template<class I> ModEvent 00235 ComplementView<View>::intersectI(Space& home,I& iter) { 00236 RangesCompl<I> c(iter); 00237 return me_negateset(x.includeI(home,c)); 00238 } 00239 00240 template<class View> 00241 forceinline void 00242 ComplementView<View>::subscribe(Space& home, Propagator& p, PropCond pc, 00243 bool schedule) { 00244 x.subscribe(home,p, pc_negateset(pc),schedule); 00245 } 00246 00247 template<class View> 00248 forceinline void 00249 ComplementView<View>::cancel(Space& home, Propagator& p, PropCond pc) { 00250 x.cancel(home,p, pc_negateset(pc)); 00251 } 00252 00253 template<class View> 00254 forceinline void 00255 ComplementView<View>::subscribe(Space& home, Advisor& a) { 00256 x.subscribe(home,a); 00257 } 00258 00259 template<class View> 00260 forceinline void 00261 ComplementView<View>::cancel(Space& home, Advisor& a) { 00262 x.cancel(home,a); 00263 } 00264 00265 template<class View> 00266 forceinline void 00267 ComplementView<View>::schedule(Space& home, Propagator& p, ModEvent me) { 00268 return View::schedule(home,p,me_negateset(me)); 00269 } 00270 template<class View> 00271 forceinline ModEvent 00272 ComplementView<View>::me(const ModEventDelta& med) { 00273 return me_negateset(View::me(med)); 00274 } 00275 00276 template<class View> 00277 forceinline ModEventDelta 00278 ComplementView<View>::med(ModEvent me) { 00279 return me_negateset(View::med(me)); 00280 } 00281 00282 /* 00283 * Delta information for advisors 00284 * 00285 */ 00286 00287 template<class View> 00288 forceinline ModEvent 00289 ComplementView<View>::modevent(const Delta& d) { 00290 return me_negateset(View::modevent(d)); 00291 } 00292 00293 template<class View> 00294 forceinline int 00295 ComplementView<View>::glbMin(const Delta& d) const { 00296 return x.lubMin(d); 00297 } 00298 00299 template<class View> 00300 forceinline int 00301 ComplementView<View>::glbMax(const Delta& d) const { 00302 return x.lubMax(d); 00303 } 00304 00305 template<class View> 00306 forceinline bool 00307 ComplementView<View>::glbAny(const Delta& d) const { 00308 return x.lubAny(d); 00309 } 00310 00311 template<class View> 00312 forceinline int 00313 ComplementView<View>::lubMin(const Delta& d) const { 00314 return x.glbMin(d); 00315 } 00316 00317 template<class View> 00318 forceinline int 00319 ComplementView<View>::lubMax(const Delta& d) const { 00320 return x.glbMax(d); 00321 } 00322 00323 template<class View> 00324 forceinline bool 00325 ComplementView<View>::lubAny(const Delta& d) const { 00326 return x.glbAny(d); 00327 } 00328 00329 00334 template<class View> 00335 class LubRanges<ComplementView<View> > { 00336 private: 00337 GlbRanges<View> lb; 00338 RangesCompl<GlbRanges<View> > lbc; 00339 public: 00341 00342 00343 LubRanges(void) {} 00345 LubRanges(const ComplementView<View>& x); 00347 void init(const ComplementView<View>& x); 00348 00350 00351 00352 bool operator ()(void) const; 00354 void operator ++(void); 00356 00358 00359 00360 int min(void) const; 00362 int max(void) const; 00364 unsigned int width(void) const; 00366 }; 00367 00368 template<class View> 00369 forceinline 00370 LubRanges<ComplementView<View> >::LubRanges(const ComplementView<View>& s) 00371 : lb(s.base()), lbc(lb) {} 00372 00373 template<class View> 00374 forceinline void 00375 LubRanges<ComplementView<View> >::init(const ComplementView<View>& s) { 00376 lb.init(s.base()); 00377 lbc.init(lb); 00378 } 00379 00380 template<class View> 00381 forceinline bool 00382 LubRanges<ComplementView<View> >::operator ()(void) const { return lbc(); } 00383 00384 template<class View> 00385 forceinline void 00386 LubRanges<ComplementView<View> >::operator ++(void) { return ++lbc; } 00387 00388 template<class View> 00389 forceinline int 00390 LubRanges<ComplementView<View> >::min(void) const { return lbc.min(); } 00391 00392 template<class View> 00393 forceinline int 00394 LubRanges<ComplementView<View> >::max(void) const { return lbc.max(); } 00395 00396 template<class View> 00397 forceinline unsigned int 00398 LubRanges<ComplementView<View> >::width(void) const { return lbc.width(); } 00399 00408 template<class View> 00409 class LubRanges<ComplementView<ComplementView<View> > > : 00410 public LubRanges<View> { 00411 public: 00413 00414 00415 LubRanges(void) {} 00417 LubRanges(const ComplementView<ComplementView<View> >& x); 00419 void init(const ComplementView<ComplementView<View> >& x); 00421 }; 00422 00423 template<class View> 00424 forceinline 00425 LubRanges<ComplementView<ComplementView<View> > >:: 00426 LubRanges(const ComplementView<ComplementView<View> >& x) : 00427 LubRanges<View>(x) {} 00428 00429 template<class View> 00430 forceinline void 00431 LubRanges<ComplementView<ComplementView<View> > >:: 00432 init(const ComplementView<ComplementView<View> >& x) { 00433 LubRanges<View>::init(x); 00434 } 00435 00440 template<class View> 00441 class GlbRanges<ComplementView<View> > { 00442 private: 00443 LubRanges<View> ub; 00444 RangesCompl<LubRanges<View> > ubc; 00445 public: 00447 00448 00449 GlbRanges(void) {} 00451 GlbRanges(const ComplementView<View> & x); 00453 void init(const ComplementView<View> & x); 00454 00456 00457 00458 bool operator ()(void) const; 00460 void operator ++(void); 00462 00464 00465 00466 int min(void) const; 00468 int max(void) const; 00470 unsigned int width(void) const; 00472 }; 00473 00474 template<class View> 00475 forceinline 00476 GlbRanges<ComplementView<View> >::GlbRanges(const ComplementView<View> & s) 00477 : ub(s.base()), ubc(ub) {} 00478 00479 template<class View> 00480 forceinline void 00481 GlbRanges<ComplementView<View> >::init(const ComplementView<View> & s) { 00482 ub.init(s.base()); 00483 ubc.init(ub); 00484 } 00485 00486 template<class View> 00487 forceinline bool 00488 GlbRanges<ComplementView<View> >::operator ()(void) const { return ubc(); } 00489 00490 template<class View> 00491 forceinline void 00492 GlbRanges<ComplementView<View> >::operator ++(void) { return ++ubc; } 00493 00494 template<class View> 00495 forceinline int 00496 GlbRanges<ComplementView<View> >::min(void) const { return ubc.min(); } 00497 00498 template<class View> 00499 forceinline int 00500 GlbRanges<ComplementView<View> >::max(void) const { return ubc.max(); } 00501 00502 template<class View> 00503 forceinline unsigned int 00504 GlbRanges<ComplementView<View> >::width(void) const { return ubc.width(); } 00505 00514 template<class View> 00515 class GlbRanges<ComplementView<ComplementView<View> > > : 00516 public GlbRanges<View> { 00517 public: 00519 00520 00521 GlbRanges(void) {} 00523 GlbRanges(const ComplementView<ComplementView<View> >& x); 00525 void init(const ComplementView<ComplementView<View> >& x); 00527 }; 00528 00529 template<class View> 00530 forceinline 00531 GlbRanges<ComplementView<ComplementView<View> > >:: 00532 GlbRanges(const ComplementView<ComplementView<View> >& x) : 00533 GlbRanges<View>(x) {} 00534 00535 template<class View> 00536 forceinline void 00537 GlbRanges<ComplementView<ComplementView<View> > >:: 00538 init(const ComplementView<ComplementView<View> >& x) { 00539 GlbRanges<View>::init(x); 00540 } 00541 00542 template<class Char, class Traits, class View> 00543 std::basic_ostream<Char,Traits>& 00544 operator <<(std::basic_ostream<Char,Traits>& os, 00545 const ComplementView<View>& x) { 00546 std::basic_ostringstream<Char,Traits> s; 00547 s.copyfmt(os); s.width(0); 00548 s << "(" << x.base() << ")^C"; 00549 return os << s.str(); 00550 } 00551 00552 }} 00553 00554 // STATISTICS: set-var