Generated on Tue Apr 18 10:22:14 2017 for Gecode by doxygen 1.6.3

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: 2016-04-19 17:19:45 +0200 (Tue, 19 Apr 2016) $ by $Author: schulte $
00015  *     $Revision: 14967 $
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);
00349 
00351 
00352 
00353     bool operator ()(void) const;
00355     void operator ++(void);
00357 
00359 
00360 
00361     int min(void) const;
00363     int max(void) const;
00365     unsigned int width(void) const;
00367   };
00368 
00369   template<class View>
00370   forceinline
00371   LubRanges<ComplementView<View> >::LubRanges(const ComplementView<View>& s)
00372     : lb(s.base()), lbc(lb) {}
00373 
00374   template<class View>
00375   forceinline void
00376   LubRanges<ComplementView<View> >::init(const ComplementView<View>& s) {
00377     lb.init(s.base());
00378     lbc.init(lb);
00379   }
00380 
00381   template<class View>
00382   forceinline bool
00383   LubRanges<ComplementView<View> >::operator ()(void) const { return lbc(); }
00384 
00385   template<class View>
00386   forceinline void
00387   LubRanges<ComplementView<View> >::operator ++(void) { return ++lbc; }
00388 
00389   template<class View>
00390   forceinline int
00391   LubRanges<ComplementView<View> >::min(void) const { return lbc.min(); }
00392 
00393   template<class View>
00394   forceinline int
00395   LubRanges<ComplementView<View> >::max(void) const { return lbc.max(); }
00396 
00397   template<class View>
00398   forceinline unsigned int
00399   LubRanges<ComplementView<View> >::width(void) const { return lbc.width(); }
00400 
00409   template<class View>
00410   class LubRanges<ComplementView<ComplementView<View> > > :
00411     public LubRanges<View> {
00412   public:
00414 
00415 
00416     LubRanges(void) {}
00418     LubRanges(const ComplementView<ComplementView<View> >& x);
00420     void init(const ComplementView<ComplementView<View> >& x);
00422   };
00423 
00424   template<class View>
00425   forceinline
00426   LubRanges<ComplementView<ComplementView<View> > >::
00427   LubRanges(const ComplementView<ComplementView<View> >& x) :
00428     LubRanges<View>(x) {}
00429 
00430   template<class View>
00431   forceinline void
00432   LubRanges<ComplementView<ComplementView<View> > >::
00433   init(const ComplementView<ComplementView<View> >& x) {
00434     LubRanges<View>::init(x);
00435   }
00436 
00441   template<class View>
00442   class GlbRanges<ComplementView<View> > {
00443   private:
00444     LubRanges<View> ub;
00445     RangesCompl<LubRanges<View> > ubc;
00446   public:
00448 
00449 
00450     GlbRanges(void) {}
00452     GlbRanges(const ComplementView<View> & x);
00454     void init(const ComplementView<View> & x);
00456 
00458 
00459 
00460     bool operator ()(void) const;
00462     void operator ++(void);
00464 
00466 
00467 
00468     int min(void) const;
00470     int max(void) const;
00472     unsigned int width(void) const;
00474   };
00475 
00476   template<class View>
00477   forceinline
00478   GlbRanges<ComplementView<View> >::GlbRanges(const ComplementView<View> & s)
00479     : ub(s.base()), ubc(ub) {}
00480 
00481   template<class View>
00482   forceinline void
00483   GlbRanges<ComplementView<View> >::init(const ComplementView<View> & s) {
00484     ub.init(s.base());
00485     ubc.init(ub);
00486   }
00487 
00488   template<class View>
00489   forceinline bool
00490   GlbRanges<ComplementView<View> >::operator ()(void) const { return ubc(); }
00491 
00492   template<class View>
00493   forceinline void
00494   GlbRanges<ComplementView<View> >::operator ++(void) { return ++ubc; }
00495 
00496   template<class View>
00497   forceinline int
00498   GlbRanges<ComplementView<View> >::min(void) const { return ubc.min(); }
00499 
00500   template<class View>
00501   forceinline int
00502   GlbRanges<ComplementView<View> >::max(void) const { return ubc.max(); }
00503 
00504   template<class View>
00505   forceinline unsigned int
00506   GlbRanges<ComplementView<View> >::width(void) const { return ubc.width(); }
00507 
00516   template<class View>
00517   class GlbRanges<ComplementView<ComplementView<View> > > :
00518     public GlbRanges<View> {
00519   public:
00521 
00522 
00523     GlbRanges(void) {}
00525     GlbRanges(const ComplementView<ComplementView<View> >& x);
00527     void init(const ComplementView<ComplementView<View> >& x);
00529   };
00530 
00531   template<class View>
00532   forceinline
00533   GlbRanges<ComplementView<ComplementView<View> > >::
00534   GlbRanges(const ComplementView<ComplementView<View> >& x) :
00535     GlbRanges<View>(x) {}
00536 
00537   template<class View>
00538   forceinline void
00539   GlbRanges<ComplementView<ComplementView<View> > >::
00540   init(const ComplementView<ComplementView<View> >& x) {
00541     GlbRanges<View>::init(x);
00542   }
00543 
00544   template<class Char, class Traits, class View>
00545   std::basic_ostream<Char,Traits>&
00546   operator <<(std::basic_ostream<Char,Traits>& os,
00547               const ComplementView<View>& x) {
00548     std::basic_ostringstream<Char,Traits> s;
00549     s.copyfmt(os); s.width(0);
00550     s << "(" << x.base() << ")^C";
00551     return os << s.str();
00552   }
00553 
00554 }}
00555 
00556 // STATISTICS: set-var