Generated on Thu Jul 6 07:06:51 2006 for Gecode by doxygen 1.4.7

complement.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Guido Tack <tack@gecode.org>
00004  *
00005  *  Contributing authors:
00006  *     Christian Schulte <schulte@gecode.org>
00007  *
00008  *  Copyright:
00009  *     Guido Tack, 2004
00010  *     Christian Schulte, 2004
00011  *
00012  *  Last modified:
00013  *     $Date: 2006-05-24 15:31:29 +0200 (Wed, 24 May 2006) $ by $Author: tack $
00014  *     $Revision: 3241 $
00015  *
00016  *  This file is part of Gecode, the generic constraint
00017  *  development environment:
00018  *     http://www.gecode.org
00019  *
00020  *  See the file "LICENSE" for information on usage and
00021  *  redistribution of this file, and for a
00022  *     DISCLAIMER OF ALL WARRANTIES.
00023  *
00024  */
00025 
00026 namespace Gecode { namespace Set {
00027 
00028   template <class View>
00029   forceinline
00030   ComplementView<View>::ComplementView(void) {}
00031 
00032   template <class View>
00033   forceinline
00034   ComplementView<View>::ComplementView(View& s0)
00035     : DerivedViewBase<View>(s0) {}
00036 
00037   template <class View>
00038   forceinline ModEvent
00039   ComplementView<View>::me_negateset(ModEvent me) {
00040     switch(me) {
00041     case ME_SET_LUB : return ME_SET_GLB;
00042     case ME_SET_GLB : return ME_SET_LUB;
00043     case ME_SET_CLUB : return ME_SET_CGLB;
00044     case ME_SET_CGLB : return ME_SET_CLUB;
00045     default: return me;
00046     }
00047   }
00048 
00049   template <class View>
00050   forceinline PropCond
00051   ComplementView<View>::pc_negateset(PropCond pc) {
00052     switch(pc) {
00053     case PC_SET_CLUB  : return PC_SET_CGLB;
00054     case PC_SET_CGLB  : return PC_SET_CLUB;
00055     default: return pc;
00056     }
00057   }
00058 
00059   template <class View>
00060   forceinline bool
00061   ComplementView<View>::assigned(void) const { return view.assigned(); }
00062 
00063   template <class View>
00064   forceinline unsigned int
00065   ComplementView<View>::glbSize(void) const {
00066     return Limits::Set::card_max - view.lubSize();
00067   }
00068 
00069   template <class View>
00070   forceinline unsigned int
00071   ComplementView<View>::lubSize(void) const {
00072     return Limits::Set::card_max - view.glbSize();
00073   }
00074 
00075   template <class View>
00076   forceinline unsigned int
00077   ComplementView<View>::unknownSize(void) const {
00078     return lubSize() - glbSize();
00079   }
00080 
00081   template <class View>
00082   forceinline bool
00083   ComplementView<View>::contains(int n) const { return view.notContains(n); }
00084 
00085   template <class View>
00086   forceinline bool
00087   ComplementView<View>::notContains(int n) const { return view.contains(n); }
00088 
00089   template <class View>
00090   forceinline unsigned int
00091   ComplementView<View>::cardMin() const {
00092     return Limits::Set::card_max - view.cardMax();
00093   }
00094 
00095   template <class View>
00096   forceinline unsigned int
00097   ComplementView<View>::cardMax() const {
00098     return Limits::Set::card_max - view.cardMin();
00099   }
00100 
00101   template <class View>
00102   forceinline int
00103   ComplementView<View>::lubMin() const {
00104     GlbRanges<View> lb(view);
00105     RangesCompl<GlbRanges<View> > lbc(lb);
00106     if (lbc()) {
00107       return lbc.min();
00108     } else {
00109       return BndSet::MIN_OF_EMPTY;
00110     }
00111   }
00112 
00113   template <class View>
00114   forceinline int
00115   ComplementView<View>::lubMax() const {
00116     GlbRanges<View> lb(view);
00117     RangesCompl<GlbRanges<View> > lbc(lb);
00118     if (lbc()) {
00119       while(lbc()) ++lbc;
00120       return lbc.max();
00121     } else {
00122       return BndSet::MAX_OF_EMPTY;
00123     }
00124   }
00125 
00126   template <class View>
00127   forceinline int
00128   ComplementView<View>::glbMin() const {
00129     LubRanges<View> ub(view);
00130     RangesCompl<LubRanges<View> > ubc(ub);
00131     if (ubc()) {
00132       return ubc.min();
00133     } else {
00134       return BndSet::MIN_OF_EMPTY;
00135     }
00136   }
00137 
00138   template <class View>
00139   forceinline int
00140   ComplementView<View>::glbMax() const {
00141     LubRanges<View> ub(view);
00142     RangesCompl<LubRanges<View> > ubc(ub);
00143     if (ubc()) {
00144       while(ubc()) ++ubc;
00145       return ubc.max();
00146     } else {
00147       return BndSet::MAX_OF_EMPTY;
00148     }
00149   }
00150 
00151   template <class View>
00152   forceinline ModEvent
00153   ComplementView<View>::cardMin(Space* home, unsigned int c) {
00154     if (c < Limits::Set::card_max)
00155       return me_negateset(view.cardMax(home, Limits::Set::card_max - c));
00156     return ME_SET_NONE;
00157   }
00158 
00159   template <class View>
00160   forceinline ModEvent
00161   ComplementView<View>::cardMax(Space* home, unsigned int c) {
00162     if (c < Limits::Set::card_max)
00163       return me_negateset(view.cardMin(home, Limits::Set::card_max - c));
00164     return ME_SET_NONE;
00165   }
00166 
00167   template <class View>
00168   forceinline ModEvent
00169   ComplementView<View>::include(Space* home, int c) {
00170     return me_negateset((view.exclude(home, c)));
00171   }
00172 
00173   template <class View>
00174   forceinline ModEvent
00175   ComplementView<View>::exclude(Space* home, int c) {
00176     return me_negateset((view.include(home, c)));
00177   }
00178 
00179   template <class View>
00180   forceinline ModEvent
00181   ComplementView<View>::intersect(Space* home, int c) {
00182     Iter::Ranges::Singleton si(c,c);
00183     return me_negateset((view.includeI(home, si)));
00184   }
00185 
00186   template <class View>
00187   forceinline ModEvent
00188   ComplementView<View>::intersect(Space* home, int i, int j) {
00189     Iter::Ranges::Singleton si(i,j);
00190     return me_negateset((view.includeI(home, si)));
00191   }
00192 
00193   template <class View>
00194   forceinline ModEvent
00195   ComplementView<View>::include(Space* home, int j, int k) {
00196     return me_negateset(view.exclude(home,j,k));
00197   }
00198 
00199   template <class View>
00200   forceinline ModEvent
00201   ComplementView<View>::exclude(Space* home, int j, int k) {
00202     return me_negateset(view.include(home,j,k));
00203   }
00204 
00205   template <class View>
00206   template <class I> ModEvent
00207   ComplementView<View>::excludeI(Space* home,I& iter) {
00208     return me_negateset(view.includeI(home,iter));
00209   }
00210 
00211   template <class View>
00212   template <class I> ModEvent
00213   ComplementView<View>::includeI(Space* home,I& iter) {
00214     return me_negateset(view.excludeI(home,iter));
00215   }
00216 
00217   template <class View>
00218   template <class I> ModEvent
00219   ComplementView<View>::intersectI(Space* home,I& iter) {
00220     RangesCompl<I> c(iter);
00221     return me_negateset(view.includeI(home,c));
00222   }
00223 
00224   template <class View>
00225   forceinline void
00226   ComplementView<View>::subscribe(Space* home, Propagator* p, PropCond pc) {
00227     view.subscribe(home,p, pc_negateset(pc));
00228   }
00229 
00230   template <class View>
00231   forceinline void
00232   ComplementView<View>::cancel(Space* home, Propagator* p, PropCond pc) {
00233     view.cancel(home,p, pc_negateset(pc));
00234   }
00235 
00236   template <class View>
00237   forceinline ModEvent
00238   ComplementView<View>::pme(const Propagator* p) {
00239     return me_negateset(View::pme(p));
00240   }
00241 
00242   template <class View>
00243   forceinline PropModEvent
00244   ComplementView<View>::pme(ModEvent me) {
00245     return me_negateset(View::pme(me));
00246   }
00247 
00248   template <class View>
00249   forceinline void
00250   ComplementView<View>::update(Space* home, bool share, 
00251                                ComplementView& y) {
00252     view.update(home,share,y.view);
00253   }
00254 
00255   /*
00256    * Specialization for double negation
00257    *
00258    */
00259 
00260   template <class View>
00261   forceinline
00262   ComplementView<ComplementView<View> >::ComplementView(void) {}
00263 
00264   template <class View>
00265   forceinline
00266   ComplementView<ComplementView<View> >::
00267   ComplementView(ComplementView<View>& s0)
00268     : View(s0.base()) {}
00269 
00270 
00275   template <class View>
00276   class LubRanges<ComplementView<View> > {
00277   private:
00278     GlbRanges<View> lb;
00279     RangesCompl<GlbRanges<View> > lbc;
00280   public:
00282 
00283 
00284     LubRanges(void) {}
00286     LubRanges(const ComplementView<View>& x);
00288     void init(const ComplementView<View>& x);
00289 
00291 
00292 
00293     bool operator()(void) const;
00295     void operator++(void);
00297 
00299 
00300 
00301     int min(void) const;
00303     int max(void) const;
00305     unsigned int width(void) const;
00307   };
00308 
00309   template <class View>
00310   forceinline
00311   LubRanges<ComplementView<View> >::LubRanges(const ComplementView<View>& s)
00312     : lb(s.base()), lbc(lb) {}
00313 
00314   template <class View>
00315   forceinline void
00316   LubRanges<ComplementView<View> >::init(const ComplementView<View>& s) {
00317     lb.init(s.base());
00318     lbc.init(lb);
00319   }
00320 
00321   template <class View>
00322   forceinline bool
00323   LubRanges<ComplementView<View> >::operator()(void) const { return lbc(); }
00324 
00325   template <class View>
00326   forceinline void
00327   LubRanges<ComplementView<View> >::operator++(void) { return ++lbc; }
00328 
00329   template <class View>
00330   forceinline int
00331   LubRanges<ComplementView<View> >::min(void) const { return lbc.min(); }
00332 
00333   template <class View>
00334   forceinline int
00335   LubRanges<ComplementView<View> >::max(void) const { return lbc.max(); }
00336 
00337   template <class View>
00338   forceinline unsigned int
00339   LubRanges<ComplementView<View> >::width(void) const { return lbc.width(); }
00340 
00349   template <class View>
00350   class LubRanges<ComplementView<ComplementView<View> > > :
00351   public LubRanges<View> {
00352   public:
00354 
00355 
00356     LubRanges(void) {}
00358     LubRanges(const ComplementView<ComplementView<View> >& x);
00360     void init(const ComplementView<ComplementView<View> >& x);
00362   };
00363 
00364   template <class View>
00365   forceinline
00366   LubRanges<ComplementView<ComplementView<View> > >::
00367   LubRanges(const ComplementView<ComplementView<View> >& x) :
00368   LubRanges<View>(x) {}
00369 
00370   template <class View>
00371   forceinline void
00372   LubRanges<ComplementView<ComplementView<View> > >::
00373   init(const ComplementView<ComplementView<View> >& x) {
00374     LubRanges<View>::init(x);
00375   }
00376 
00381   template <class View>
00382   class GlbRanges<ComplementView<View> > {
00383   private:
00384     LubRanges<View> ub;
00385     RangesCompl<LubRanges<View> > ubc;
00386   public:
00388 
00389 
00390     GlbRanges(void) {}
00392     GlbRanges(const ComplementView<View> & x);
00394     void init(const ComplementView<View> & x);
00395 
00397 
00398 
00399     bool operator()(void) const;
00401     void operator++(void);
00403 
00405 
00406 
00407     int min(void) const;
00409     int max(void) const;
00411     unsigned int width(void) const;
00413   };
00414 
00415   template <class View>
00416   forceinline
00417   GlbRanges<ComplementView<View> >::GlbRanges(const ComplementView<View> & s)
00418     : ub(s.base()), ubc(ub) {}
00419 
00420   template <class View>
00421   forceinline void
00422   GlbRanges<ComplementView<View> >::init(const ComplementView<View> & s) {
00423     ub.init(s.base());
00424     ubc.init(ub);
00425   }
00426 
00427   template <class View>
00428   forceinline bool
00429   GlbRanges<ComplementView<View> >::operator()(void) const { return ubc(); }
00430 
00431   template <class View>
00432   forceinline void
00433   GlbRanges<ComplementView<View> >::operator++(void) { return ++ubc; }
00434 
00435   template <class View>
00436   forceinline int
00437   GlbRanges<ComplementView<View> >::min(void) const { return ubc.min(); }
00438 
00439   template <class View>
00440   forceinline int
00441   GlbRanges<ComplementView<View> >::max(void) const { return ubc.max(); }
00442 
00443   template <class View>
00444   forceinline unsigned int
00445   GlbRanges<ComplementView<View> >::width(void) const { return ubc.width(); }
00446   
00455   template <class View>
00456   class GlbRanges<ComplementView<ComplementView<View> > > :
00457   public GlbRanges<View> {
00458   public:
00460 
00461 
00462     GlbRanges(void) {}
00464     GlbRanges(const ComplementView<ComplementView<View> >& x);
00466     void init(const ComplementView<ComplementView<View> >& x);
00468   };
00469 
00470   template <class View>
00471   forceinline
00472   GlbRanges<ComplementView<ComplementView<View> > >::
00473   GlbRanges(const ComplementView<ComplementView<View> >& x) :
00474   GlbRanges<View>(x) {}
00475 
00476   template <class View>
00477   forceinline void
00478   GlbRanges<ComplementView<ComplementView<View> > >::
00479   init(const ComplementView<ComplementView<View> >& x) {
00480     GlbRanges<View>::init(x);
00481   }
00482 
00483 }
00484 
00485 
00486   /*
00487    * Testing
00488    *
00489    */
00490   template <class View>
00491   forceinline bool
00492   same(const Set::ComplementView<View>& x, 
00493        const Set::ComplementView<View>& y) {
00494     return same(x.base(),y.base());
00495   }
00496   template <class View>
00497   forceinline bool
00498   before(const Set::ComplementView<View>& x, 
00499          const Set::ComplementView<View>& y) {
00500     return before(x.base(),y.base());
00501   }
00502   template <class View>
00503   forceinline bool
00504   same(const Set::ComplementView<Set::ComplementView<View> >& x, 
00505        const Set::ComplementView<Set::ComplementView<View> >& y) {
00506     return same(x,y);
00507   }
00508   template <class View>
00509   forceinline bool
00510   before(const Set::ComplementView<Set::ComplementView<View> >& x, 
00511          const Set::ComplementView<Set::ComplementView<View> >& y) {
00512     return before(x,y);
00513   }
00514 
00515 }
00516 
00517 template <class View>
00518 forceinline
00519 std::ostream&
00520 operator<<(std::ostream& os, const Gecode::Set::ComplementView<View>& s) {
00521   return os << "(" << s.base() << ")^C";
00522 }
00523 
00524 // STATISTICS: set-var