Generated on Mon May 5 05:54:05 2008 for Gecode by doxygen 1.5.5

complement.icc

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: 2008-02-06 18:48:22 +0100 (Wed, 06 Feb 2008) $ by $Author: schulte $
00015  *     $Revision: 6102 $
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 namespace Gecode { namespace Set {
00043 
00044   template <class View>
00045   forceinline
00046   ComplementView<View>::ComplementView(void) {}
00047 
00048   template <class View>
00049   forceinline
00050   ComplementView<View>::ComplementView(View& s0)
00051     : DerivedViewBase<View>(s0) {}
00052 
00053   template <class View>
00054   forceinline
00055   ComplementView<View>::ComplementView(Space* home,
00056                                        const Reflection::VarMap& vars,
00057                                        Reflection::Arg* arg)
00058   : DerivedViewBase<View>(View(home, vars, arg)) {}
00059 
00060   template <class View>
00061   forceinline ModEvent
00062   ComplementView<View>::me_negateset(ModEvent me) {
00063     switch(me) {
00064     case ME_SET_LUB : return ME_SET_GLB;
00065     case ME_SET_GLB : return ME_SET_LUB;
00066     case ME_SET_CLUB : return ME_SET_CGLB;
00067     case ME_SET_CGLB : return ME_SET_CLUB;
00068     default: return me;
00069     }
00070   }
00071 
00072   template <class View>
00073   forceinline PropCond
00074   ComplementView<View>::pc_negateset(PropCond pc) {
00075     switch(pc) {
00076     case PC_SET_CLUB  : return PC_SET_CGLB;
00077     case PC_SET_CGLB  : return PC_SET_CLUB;
00078     default: return pc;
00079     }
00080   }
00081 
00082   template <class View>
00083   forceinline bool
00084   ComplementView<View>::assigned(void) const { return view.assigned(); }
00085 
00086   template <class View>
00087   forceinline unsigned int
00088   ComplementView<View>::glbSize(void) const {
00089     return Limits::card - view.lubSize();
00090   }
00091 
00092   template <class View>
00093   forceinline unsigned int
00094   ComplementView<View>::lubSize(void) const {
00095     return Limits::card - view.glbSize();
00096   }
00097 
00098   template <class View>
00099   forceinline unsigned int
00100   ComplementView<View>::unknownSize(void) const {
00101     return lubSize() - glbSize();
00102   }
00103 
00104   template <class View>
00105   forceinline bool
00106   ComplementView<View>::contains(int n) const { return view.notContains(n); }
00107 
00108   template <class View>
00109   forceinline bool
00110   ComplementView<View>::notContains(int n) const { return view.contains(n); }
00111 
00112   template <class View>
00113   forceinline unsigned int
00114   ComplementView<View>::cardMin() const {
00115     return Limits::card - view.cardMax();
00116   }
00117 
00118   template <class View>
00119   forceinline unsigned int
00120   ComplementView<View>::cardMax() const {
00121     return Limits::card - view.cardMin();
00122   }
00123 
00124   template <class View>
00125   forceinline int
00126   ComplementView<View>::lubMin() const {
00127     GlbRanges<View> lb(view);
00128     RangesCompl<GlbRanges<View> > lbc(lb);
00129     if (lbc()) {
00130       return lbc.min();
00131     } else {
00132       return BndSet::MIN_OF_EMPTY;
00133     }
00134   }
00135 
00136   template <class View>
00137   forceinline int
00138   ComplementView<View>::lubMax() const {
00139     GlbRanges<View> lb(view);
00140     RangesCompl<GlbRanges<View> > lbc(lb);
00141     if (lbc()) {
00142       while(lbc()) ++lbc;
00143       return lbc.max();
00144     } else {
00145       return BndSet::MAX_OF_EMPTY;
00146     }
00147   }
00148 
00149   template <class View>
00150   forceinline int
00151   ComplementView<View>::glbMin() const {
00152     LubRanges<View> ub(view);
00153     RangesCompl<LubRanges<View> > ubc(ub);
00154     if (ubc()) {
00155       return ubc.min();
00156     } else {
00157       return BndSet::MIN_OF_EMPTY;
00158     }
00159   }
00160 
00161   template <class View>
00162   forceinline int
00163   ComplementView<View>::glbMax() const {
00164     LubRanges<View> ub(view);
00165     RangesCompl<LubRanges<View> > ubc(ub);
00166     if (ubc()) {
00167       while(ubc()) ++ubc;
00168       return ubc.max();
00169     } else {
00170       return BndSet::MAX_OF_EMPTY;
00171     }
00172   }
00173 
00174   template <class View>
00175   forceinline ModEvent
00176   ComplementView<View>::cardMin(Space* home, unsigned int c) {
00177     if (c < Limits::card)
00178       return me_negateset(view.cardMax(home, Limits::card - c));
00179     return ME_SET_NONE;
00180   }
00181 
00182   template <class View>
00183   forceinline ModEvent
00184   ComplementView<View>::cardMax(Space* home, unsigned int c) {
00185     if (c < Limits::card)
00186       return me_negateset(view.cardMin(home, Limits::card - c));
00187     return ME_SET_NONE;
00188   }
00189 
00190   template <class View>
00191   forceinline ModEvent
00192   ComplementView<View>::include(Space* home, int c) {
00193     return me_negateset((view.exclude(home, c)));
00194   }
00195 
00196   template <class View>
00197   forceinline ModEvent
00198   ComplementView<View>::exclude(Space* home, int c) {
00199     return me_negateset((view.include(home, c)));
00200   }
00201 
00202   template <class View>
00203   forceinline ModEvent
00204   ComplementView<View>::intersect(Space* home, int c) {
00205     Iter::Ranges::Singleton si(c,c);
00206     RangesCompl<Iter::Ranges::Singleton> csi(si);
00207     return me_negateset((view.includeI(home, csi)));
00208   }
00209 
00210   template <class View>
00211   forceinline ModEvent
00212   ComplementView<View>::intersect(Space* home, int i, int j) {
00213     Iter::Ranges::Singleton si(i,j);
00214     RangesCompl<Iter::Ranges::Singleton> csi(si);
00215     return me_negateset((view.includeI(home, csi)));
00216   }
00217 
00218   template <class View>
00219   forceinline ModEvent
00220   ComplementView<View>::include(Space* home, int j, int k) {
00221     return me_negateset(view.exclude(home,j,k));
00222   }
00223 
00224   template <class View>
00225   forceinline ModEvent
00226   ComplementView<View>::exclude(Space* home, int j, int k) {
00227     return me_negateset(view.include(home,j,k));
00228   }
00229 
00230   template <class View>
00231   template <class I> ModEvent
00232   ComplementView<View>::excludeI(Space* home,I& iter) {
00233     return me_negateset(view.includeI(home,iter));
00234   }
00235 
00236   template <class View>
00237   template <class I> ModEvent
00238   ComplementView<View>::includeI(Space* home,I& iter) {
00239     return me_negateset(view.excludeI(home,iter));
00240   }
00241 
00242   template <class View>
00243   template <class I> ModEvent
00244   ComplementView<View>::intersectI(Space* home,I& iter) {
00245     RangesCompl<I> c(iter);
00246     return me_negateset(view.includeI(home,c));
00247   }
00248 
00249   template <class View>
00250   forceinline void
00251   ComplementView<View>::subscribe(Space* home, Propagator* p, PropCond pc,
00252                                   bool process) {
00253     view.subscribe(home,p, pc_negateset(pc),process);
00254   }
00255 
00256   template <class View>
00257   forceinline void
00258   ComplementView<View>::cancel(Space* home, Propagator* p, PropCond pc) {
00259     view.cancel(home,p, pc_negateset(pc));
00260   }
00261 
00262   template <class View>
00263   forceinline void
00264   ComplementView<View>::subscribe(Space* home, Advisor* a) {
00265     view.subscribe(home,a);
00266   }
00267 
00268   template <class View>
00269   forceinline void
00270   ComplementView<View>::cancel(Space* home, Advisor* a) {
00271     view.cancel(home,a);
00272   }
00273 
00274   template <class View>
00275   forceinline void
00276   ComplementView<View>::schedule(Space* home, Propagator* p, ModEvent me) {
00277     return View::schedule(home,p,me_negateset(me));
00278   }
00279   template <class View>
00280   forceinline ModEvent
00281   ComplementView<View>::me(ModEventDelta med) {
00282     return me_negateset(View::me(med));
00283   }
00284 
00285   template <class View>
00286   forceinline ModEventDelta
00287   ComplementView<View>::med(ModEvent me) {
00288     return me_negateset(View::med(me));
00289   }
00290 
00291   template <class View>
00292   forceinline void
00293   ComplementView<View>::update(Space* home, bool share, 
00294                                ComplementView& y) {
00295     view.update(home,share,y.view);
00296   }
00297 
00298   template <class View>
00299   forceinline Reflection::Arg*
00300   ComplementView<View>::spec(const Space* home, Reflection::VarMap& m) const {
00301     return view.spec(home, m);
00302   }
00303 
00304   template <class View>
00305   inline Support::Symbol
00306   ComplementView<View>::type(void) {
00307     Support::Symbol t("Set::ComplementView<");
00308     t += View::type();
00309     t += ">";
00310     return t;
00311   }
00312 
00313   /*
00314    * Delta information for advisors
00315    *
00316    */
00317 
00318   template <class View>
00319   forceinline ModEvent
00320   ComplementView<View>::modevent(const Delta* d) {
00321     return me_negateset(View::modevent(d));
00322   }
00323   
00324   template <class View>
00325   forceinline int
00326   ComplementView<View>::glbMin(const Delta* d) const {
00327     return view.lubMin(d);
00328   }
00329 
00330   template <class View>
00331   forceinline int
00332   ComplementView<View>::glbMax(const Delta* d) const {
00333     return view.lubMax(d);
00334   }
00335 
00336   template <class View>
00337   forceinline bool
00338   ComplementView<View>::glbAny(const Delta* d) const {
00339     return view.lubAny(d);
00340   }
00341 
00342   template <class View>
00343   forceinline int
00344   ComplementView<View>::lubMin(const Delta* d) const {
00345     return view.glbMin(d);
00346   }
00347 
00348   template <class View>
00349   forceinline int
00350   ComplementView<View>::lubMax(const Delta* d) const {
00351     return view.glbMax(d);
00352   }
00353 
00354   template <class View>
00355   forceinline bool
00356   ComplementView<View>::lubAny(const Delta* d) const {
00357     return view.glbAny(d);
00358   }
00359 
00360   /*
00361    * Specialization for double negation
00362    *
00363    */
00364 
00365   template <class View>
00366   forceinline
00367   ComplementView<ComplementView<View> >::ComplementView(void) {}
00368 
00369   template <class View>
00370   forceinline
00371   ComplementView<ComplementView<View> >::
00372   ComplementView(ComplementView<View>& s0)
00373     : View(s0.base()) {}
00374 
00375 
00380   template <class View>
00381   class LubRanges<ComplementView<View> > {
00382   private:
00383     GlbRanges<View> lb;
00384     RangesCompl<GlbRanges<View> > lbc;
00385   public:
00387 
00388 
00389     LubRanges(void) {}
00391     LubRanges(const ComplementView<View>& x);
00393     void init(const ComplementView<View>& x);
00394 
00396 
00397 
00398     bool operator()(void) const;
00400     void operator++(void);
00402 
00404 
00405 
00406     int min(void) const;
00408     int max(void) const;
00410     unsigned int width(void) const;
00412   };
00413 
00414   template <class View>
00415   forceinline
00416   LubRanges<ComplementView<View> >::LubRanges(const ComplementView<View>& s)
00417     : lb(s.base()), lbc(lb) {}
00418 
00419   template <class View>
00420   forceinline void
00421   LubRanges<ComplementView<View> >::init(const ComplementView<View>& s) {
00422     lb.init(s.base());
00423     lbc.init(lb);
00424   }
00425 
00426   template <class View>
00427   forceinline bool
00428   LubRanges<ComplementView<View> >::operator()(void) const { return lbc(); }
00429 
00430   template <class View>
00431   forceinline void
00432   LubRanges<ComplementView<View> >::operator++(void) { return ++lbc; }
00433 
00434   template <class View>
00435   forceinline int
00436   LubRanges<ComplementView<View> >::min(void) const { return lbc.min(); }
00437 
00438   template <class View>
00439   forceinline int
00440   LubRanges<ComplementView<View> >::max(void) const { return lbc.max(); }
00441 
00442   template <class View>
00443   forceinline unsigned int
00444   LubRanges<ComplementView<View> >::width(void) const { return lbc.width(); }
00445 
00454   template <class View>
00455   class LubRanges<ComplementView<ComplementView<View> > > :
00456   public LubRanges<View> {
00457   public:
00459 
00460 
00461     LubRanges(void) {}
00463     LubRanges(const ComplementView<ComplementView<View> >& x);
00465     void init(const ComplementView<ComplementView<View> >& x);
00467   };
00468 
00469   template <class View>
00470   forceinline
00471   LubRanges<ComplementView<ComplementView<View> > >::
00472   LubRanges(const ComplementView<ComplementView<View> >& x) :
00473   LubRanges<View>(x) {}
00474 
00475   template <class View>
00476   forceinline void
00477   LubRanges<ComplementView<ComplementView<View> > >::
00478   init(const ComplementView<ComplementView<View> >& x) {
00479     LubRanges<View>::init(x);
00480   }
00481 
00486   template <class View>
00487   class GlbRanges<ComplementView<View> > {
00488   private:
00489     LubRanges<View> ub;
00490     RangesCompl<LubRanges<View> > ubc;
00491   public:
00493 
00494 
00495     GlbRanges(void) {}
00497     GlbRanges(const ComplementView<View> & x);
00499     void init(const ComplementView<View> & x);
00500 
00502 
00503 
00504     bool operator()(void) const;
00506     void operator++(void);
00508 
00510 
00511 
00512     int min(void) const;
00514     int max(void) const;
00516     unsigned int width(void) const;
00518   };
00519 
00520   template <class View>
00521   forceinline
00522   GlbRanges<ComplementView<View> >::GlbRanges(const ComplementView<View> & s)
00523     : ub(s.base()), ubc(ub) {}
00524 
00525   template <class View>
00526   forceinline void
00527   GlbRanges<ComplementView<View> >::init(const ComplementView<View> & s) {
00528     ub.init(s.base());
00529     ubc.init(ub);
00530   }
00531 
00532   template <class View>
00533   forceinline bool
00534   GlbRanges<ComplementView<View> >::operator()(void) const { return ubc(); }
00535 
00536   template <class View>
00537   forceinline void
00538   GlbRanges<ComplementView<View> >::operator++(void) { return ++ubc; }
00539 
00540   template <class View>
00541   forceinline int
00542   GlbRanges<ComplementView<View> >::min(void) const { return ubc.min(); }
00543 
00544   template <class View>
00545   forceinline int
00546   GlbRanges<ComplementView<View> >::max(void) const { return ubc.max(); }
00547 
00548   template <class View>
00549   forceinline unsigned int
00550   GlbRanges<ComplementView<View> >::width(void) const { return ubc.width(); }
00551   
00560   template <class View>
00561   class GlbRanges<ComplementView<ComplementView<View> > > :
00562   public GlbRanges<View> {
00563   public:
00565 
00566 
00567     GlbRanges(void) {}
00569     GlbRanges(const ComplementView<ComplementView<View> >& x);
00571     void init(const ComplementView<ComplementView<View> >& x);
00573   };
00574 
00575   template <class View>
00576   forceinline
00577   GlbRanges<ComplementView<ComplementView<View> > >::
00578   GlbRanges(const ComplementView<ComplementView<View> >& x) :
00579   GlbRanges<View>(x) {}
00580 
00581   template <class View>
00582   forceinline void
00583   GlbRanges<ComplementView<ComplementView<View> > >::
00584   init(const ComplementView<ComplementView<View> >& x) {
00585     GlbRanges<View>::init(x);
00586   }
00587 
00588 }
00589 
00590 
00591   /*
00592    * Testing
00593    *
00594    */
00595   template <class View>
00596   forceinline bool
00597   same(const Set::ComplementView<View>& x, 
00598        const Set::ComplementView<View>& y) {
00599     return same(x.base(),y.base());
00600   }
00601   template <class View>
00602   forceinline bool
00603   before(const Set::ComplementView<View>& x, 
00604          const Set::ComplementView<View>& y) {
00605     return before(x.base(),y.base());
00606   }
00607   template <class View>
00608   forceinline bool
00609   same(const Set::ComplementView<Set::ComplementView<View> >& x, 
00610        const Set::ComplementView<Set::ComplementView<View> >& y) {
00611     return same(x,y);
00612   }
00613   template <class View>
00614   forceinline bool
00615   before(const Set::ComplementView<Set::ComplementView<View> >& x, 
00616          const Set::ComplementView<Set::ComplementView<View> >& y) {
00617     return before(x,y);
00618   }
00619 
00620 }
00621 
00622 template <class View>
00623 forceinline
00624 std::ostream&
00625 operator<<(std::ostream& os, const Gecode::Set::ComplementView<View>& s) {
00626   return os << "(" << s.base() << ")^C";
00627 }
00628 
00629 // STATISTICS: set-var