complement.icc

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-08-24 11:25:05 +0200 (Thu, 24 Aug 2006) $ by $Author: schulte $
00014  *     $Revision: 3559 $
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                                   bool process) {
00228     view.subscribe(home,p, pc_negateset(pc),process);
00229   }
00230 
00231   template <class View>
00232   forceinline void
00233   ComplementView<View>::cancel(Space* home, Propagator* p, PropCond pc) {
00234     view.cancel(home,p, pc_negateset(pc));
00235   }
00236 
00237   template <class View>
00238   forceinline ModEvent
00239   ComplementView<View>::pme(const Propagator* p) {
00240     return me_negateset(View::pme(p));
00241   }
00242 
00243   template <class View>
00244   forceinline PropModEvent
00245   ComplementView<View>::pme(ModEvent me) {
00246     return me_negateset(View::pme(me));
00247   }
00248 
00249   template <class View>
00250   forceinline void
00251   ComplementView<View>::update(Space* home, bool share, 
00252                                ComplementView& y) {
00253     view.update(home,share,y.view);
00254   }
00255 
00256   /*
00257    * Specialization for double negation
00258    *
00259    */
00260 
00261   template <class View>
00262   forceinline
00263   ComplementView<ComplementView<View> >::ComplementView(void) {}
00264 
00265   template <class View>
00266   forceinline
00267   ComplementView<ComplementView<View> >::
00268   ComplementView(ComplementView<View>& s0)
00269     : View(s0.base()) {}
00270 
00271 
00276   template <class View>
00277   class LubRanges<ComplementView<View> > {
00278   private:
00279     GlbRanges<View> lb;
00280     RangesCompl<GlbRanges<View> > lbc;
00281   public:
00283 
00284 
00285     LubRanges(void) {}
00287     LubRanges(const ComplementView<View>& x);
00289     void init(const ComplementView<View>& x);
00290 
00292 
00293 
00294     bool operator()(void) const;
00296     void operator++(void);
00298 
00300 
00301 
00302     int min(void) const;
00304     int max(void) const;
00306     unsigned int width(void) const;
00308   };
00309 
00310   template <class View>
00311   forceinline
00312   LubRanges<ComplementView<View> >::LubRanges(const ComplementView<View>& s)
00313     : lb(s.base()), lbc(lb) {}
00314 
00315   template <class View>
00316   forceinline void
00317   LubRanges<ComplementView<View> >::init(const ComplementView<View>& s) {
00318     lb.init(s.base());
00319     lbc.init(lb);
00320   }
00321 
00322   template <class View>
00323   forceinline bool
00324   LubRanges<ComplementView<View> >::operator()(void) const { return lbc(); }
00325 
00326   template <class View>
00327   forceinline void
00328   LubRanges<ComplementView<View> >::operator++(void) { return ++lbc; }
00329 
00330   template <class View>
00331   forceinline int
00332   LubRanges<ComplementView<View> >::min(void) const { return lbc.min(); }
00333 
00334   template <class View>
00335   forceinline int
00336   LubRanges<ComplementView<View> >::max(void) const { return lbc.max(); }
00337 
00338   template <class View>
00339   forceinline unsigned int
00340   LubRanges<ComplementView<View> >::width(void) const { return lbc.width(); }
00341 
00350   template <class View>
00351   class LubRanges<ComplementView<ComplementView<View> > > :
00352   public LubRanges<View> {
00353   public:
00355 
00356 
00357     LubRanges(void) {}
00359     LubRanges(const ComplementView<ComplementView<View> >& x);
00361     void init(const ComplementView<ComplementView<View> >& x);
00363   };
00364 
00365   template <class View>
00366   forceinline
00367   LubRanges<ComplementView<ComplementView<View> > >::
00368   LubRanges(const ComplementView<ComplementView<View> >& x) :
00369   LubRanges<View>(x) {}
00370 
00371   template <class View>
00372   forceinline void
00373   LubRanges<ComplementView<ComplementView<View> > >::
00374   init(const ComplementView<ComplementView<View> >& x) {
00375     LubRanges<View>::init(x);
00376   }
00377 
00382   template <class View>
00383   class GlbRanges<ComplementView<View> > {
00384   private:
00385     LubRanges<View> ub;
00386     RangesCompl<LubRanges<View> > ubc;
00387   public:
00389 
00390 
00391     GlbRanges(void) {}
00393     GlbRanges(const ComplementView<View> & x);
00395     void init(const ComplementView<View> & x);
00396 
00398 
00399 
00400     bool operator()(void) const;
00402     void operator++(void);
00404 
00406 
00407 
00408     int min(void) const;
00410     int max(void) const;
00412     unsigned int width(void) const;
00414   };
00415 
00416   template <class View>
00417   forceinline
00418   GlbRanges<ComplementView<View> >::GlbRanges(const ComplementView<View> & s)
00419     : ub(s.base()), ubc(ub) {}
00420 
00421   template <class View>
00422   forceinline void
00423   GlbRanges<ComplementView<View> >::init(const ComplementView<View> & s) {
00424     ub.init(s.base());
00425     ubc.init(ub);
00426   }
00427 
00428   template <class View>
00429   forceinline bool
00430   GlbRanges<ComplementView<View> >::operator()(void) const { return ubc(); }
00431 
00432   template <class View>
00433   forceinline void
00434   GlbRanges<ComplementView<View> >::operator++(void) { return ++ubc; }
00435 
00436   template <class View>
00437   forceinline int
00438   GlbRanges<ComplementView<View> >::min(void) const { return ubc.min(); }
00439 
00440   template <class View>
00441   forceinline int
00442   GlbRanges<ComplementView<View> >::max(void) const { return ubc.max(); }
00443 
00444   template <class View>
00445   forceinline unsigned int
00446   GlbRanges<ComplementView<View> >::width(void) const { return ubc.width(); }
00447   
00456   template <class View>
00457   class GlbRanges<ComplementView<ComplementView<View> > > :
00458   public GlbRanges<View> {
00459   public:
00461 
00462 
00463     GlbRanges(void) {}
00465     GlbRanges(const ComplementView<ComplementView<View> >& x);
00467     void init(const ComplementView<ComplementView<View> >& x);
00469   };
00470 
00471   template <class View>
00472   forceinline
00473   GlbRanges<ComplementView<ComplementView<View> > >::
00474   GlbRanges(const ComplementView<ComplementView<View> >& x) :
00475   GlbRanges<View>(x) {}
00476 
00477   template <class View>
00478   forceinline void
00479   GlbRanges<ComplementView<ComplementView<View> > >::
00480   init(const ComplementView<ComplementView<View> >& x) {
00481     GlbRanges<View>::init(x);
00482   }
00483 
00484 }
00485 
00486 
00487   /*
00488    * Testing
00489    *
00490    */
00491   template <class View>
00492   forceinline bool
00493   same(const Set::ComplementView<View>& x, 
00494        const Set::ComplementView<View>& y) {
00495     return same(x.base(),y.base());
00496   }
00497   template <class View>
00498   forceinline bool
00499   before(const Set::ComplementView<View>& x, 
00500          const Set::ComplementView<View>& y) {
00501     return before(x.base(),y.base());
00502   }
00503   template <class View>
00504   forceinline bool
00505   same(const Set::ComplementView<Set::ComplementView<View> >& x, 
00506        const Set::ComplementView<Set::ComplementView<View> >& y) {
00507     return same(x,y);
00508   }
00509   template <class View>
00510   forceinline bool
00511   before(const Set::ComplementView<Set::ComplementView<View> >& x, 
00512          const Set::ComplementView<Set::ComplementView<View> >& y) {
00513     return before(x,y);
00514   }
00515 
00516 }
00517 
00518 template <class View>
00519 forceinline
00520 std::ostream&
00521 operator<<(std::ostream& os, const Gecode::Set::ComplementView<View>& s) {
00522   return os << "(" << s.base() << ")^C";
00523 }
00524 
00525 // STATISTICS: set-var