Generated on Wed Jan 4 17:49:15 2006 for Gecode by doxygen 1.4.6

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: 2005-11-29 18:02:48 +0100 (Tue, 29 Nov 2005) $ by $Author: tack $
00014  *     $Revision: 2665 $
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(Propagator* p, PropCond pc) {
00233     view.cancel(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   template <class View>
00256   forceinline bool
00257   ComplementView<View>::destruct(void) { return View::destruct(); }
00258 
00259   /*
00260    * Specialization for double negation
00261    *
00262    */
00263 
00264   template <class View>
00265   forceinline
00266   ComplementView<ComplementView<View> >::ComplementView(void) {}
00267 
00268   template <class View>
00269   forceinline
00270   ComplementView<ComplementView<View> >::
00271   ComplementView(ComplementView<View>& s0)
00272     : View(s0.base()) {}
00273 
00274 
00279   template <class View>
00280   class LubRanges<ComplementView<View> > {
00281   private:
00282     GlbRanges<View> lb;
00283     RangesCompl<GlbRanges<View> > lbc;
00284   public:
00286 
00287 
00288     LubRanges(void) {}
00290     LubRanges(const ComplementView<View>& x);
00292     void init(const ComplementView<View>& x);
00293 
00295 
00296 
00297     bool operator()(void) const;
00299     void operator++(void);
00301 
00303 
00304 
00305     int min(void) const;
00307     int max(void) const;
00309     unsigned int width(void) const;
00311   };
00312 
00313   template <class View>
00314   forceinline
00315   LubRanges<ComplementView<View> >::LubRanges(const ComplementView<View>& s)
00316     : lb(s.base()), lbc(lb) {}
00317 
00318   template <class View>
00319   forceinline void
00320   LubRanges<ComplementView<View> >::init(const ComplementView<View>& s) {
00321     lb.init(s.base());
00322     lbc.init(lb);
00323   }
00324 
00325   template <class View>
00326   forceinline bool
00327   LubRanges<ComplementView<View> >::operator()(void) const { return lbc(); }
00328 
00329   template <class View>
00330   forceinline void
00331   LubRanges<ComplementView<View> >::operator++(void) { return ++lbc; }
00332 
00333   template <class View>
00334   forceinline int
00335   LubRanges<ComplementView<View> >::min(void) const { return lbc.min(); }
00336 
00337   template <class View>
00338   forceinline int
00339   LubRanges<ComplementView<View> >::max(void) const { return lbc.max(); }
00340 
00341   template <class View>
00342   forceinline unsigned int
00343   LubRanges<ComplementView<View> >::width(void) const { return lbc.width(); }
00344 
00353   template <class View>
00354   class LubRanges<ComplementView<ComplementView<View> > > :
00355   public LubRanges<View> {
00356   public:
00358 
00359 
00360     LubRanges(void) {}
00362     LubRanges(const ComplementView<ComplementView<View> >& x);
00364     void init(const ComplementView<ComplementView<View> >& x);
00366   };
00367 
00368   template <class View>
00369   forceinline
00370   LubRanges<ComplementView<ComplementView<View> > >::
00371   LubRanges(const ComplementView<ComplementView<View> >& x) :
00372   LubRanges<View>(x) {}
00373 
00374   template <class View>
00375   forceinline void
00376   LubRanges<ComplementView<ComplementView<View> > >::
00377   init(const ComplementView<ComplementView<View> >& x) {
00378     LubRanges<View>::init(x);
00379   }
00380 
00385   template <class View>
00386   class GlbRanges<ComplementView<View> > {
00387   private:
00388     LubRanges<View> ub;
00389     RangesCompl<LubRanges<View> > ubc;
00390   public:
00392 
00393 
00394     GlbRanges(void) {}
00396     GlbRanges(const ComplementView<View> & x);
00398     void init(const ComplementView<View> & x);
00399 
00401 
00402 
00403     bool operator()(void) const;
00405     void operator++(void);
00407 
00409 
00410 
00411     int min(void) const;
00413     int max(void) const;
00415     unsigned int width(void) const;
00417   };
00418 
00419   template <class View>
00420   forceinline
00421   GlbRanges<ComplementView<View> >::GlbRanges(const ComplementView<View> & s)
00422     : ub(s.base()), ubc(ub) {}
00423 
00424   template <class View>
00425   forceinline void
00426   GlbRanges<ComplementView<View> >::init(const ComplementView<View> & s) {
00427     ub.init(s.base());
00428     ubc.init(ub);
00429   }
00430 
00431   template <class View>
00432   forceinline bool
00433   GlbRanges<ComplementView<View> >::operator()(void) const { return ubc(); }
00434 
00435   template <class View>
00436   forceinline void
00437   GlbRanges<ComplementView<View> >::operator++(void) { return ++ubc; }
00438 
00439   template <class View>
00440   forceinline int
00441   GlbRanges<ComplementView<View> >::min(void) const { return ubc.min(); }
00442 
00443   template <class View>
00444   forceinline int
00445   GlbRanges<ComplementView<View> >::max(void) const { return ubc.max(); }
00446 
00447   template <class View>
00448   forceinline unsigned int
00449   GlbRanges<ComplementView<View> >::width(void) const { return ubc.width(); }
00450   
00459   template <class View>
00460   class GlbRanges<ComplementView<ComplementView<View> > > :
00461   public GlbRanges<View> {
00462   public:
00464 
00465 
00466     GlbRanges(void) {}
00468     GlbRanges(const ComplementView<ComplementView<View> >& x);
00470     void init(const ComplementView<ComplementView<View> >& x);
00472   };
00473 
00474   template <class View>
00475   forceinline
00476   GlbRanges<ComplementView<ComplementView<View> > >::
00477   GlbRanges(const ComplementView<ComplementView<View> >& x) :
00478   GlbRanges<View>(x) {}
00479 
00480   template <class View>
00481   forceinline void
00482   GlbRanges<ComplementView<ComplementView<View> > >::
00483   init(const ComplementView<ComplementView<View> >& x) {
00484     GlbRanges<View>::init(x);
00485   }
00486 
00487 }
00488 
00489 
00490   /*
00491    * Testing
00492    *
00493    */
00494   template <class View>
00495   forceinline bool
00496   same(const Set::ComplementView<View>& x, 
00497        const Set::ComplementView<View>& y) {
00498     return same(x.base(),y.base());
00499   }
00500   template <class View>
00501   forceinline bool
00502   before(const Set::ComplementView<View>& x, 
00503          const Set::ComplementView<View>& y) {
00504     return before(x.base(),y.base());
00505   }
00506   template <class View>
00507   forceinline bool
00508   same(const Set::ComplementView<Set::ComplementView<View> >& x, 
00509        const Set::ComplementView<Set::ComplementView<View> >& y) {
00510     return same(x,y);
00511   }
00512   template <class View>
00513   forceinline bool
00514   before(const Set::ComplementView<Set::ComplementView<View> >& x, 
00515          const Set::ComplementView<Set::ComplementView<View> >& y) {
00516     return before(x,y);
00517   }
00518 
00519 }
00520 
00521 template <class View>
00522 forceinline
00523 std::ostream&
00524 operator<<(std::ostream& os, const Gecode::Set::ComplementView<View>& s) {
00525   return os << "(" << s.base() << ")^C";
00526 }
00527 
00528 // STATISTICS: set-var