gecode » set » view
complement.hpp

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: 2009-09-08 21:10:29 +0200 (Tue, 08 Sep 2009) $ by $Author: schulte $
00015  *     $Revision: 9692 $
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 {
00045 
00046   namespace Set {
00047 
00048     template<class View>
00049     forceinline
00050     ComplementView<View>::ComplementView(void) {}
00051 
00052     template<class View>
00053     forceinline
00054     ComplementView<View>::ComplementView(View& s0)
00055       : DerivedViewBase<View>(s0) {}
00056 
00057     template<class View>
00058     forceinline ModEvent
00059     ComplementView<View>::me_negateset(ModEvent me) {
00060       switch(me) {
00061       case ME_SET_LUB : return ME_SET_GLB;
00062       case ME_SET_GLB : return ME_SET_LUB;
00063       case ME_SET_CLUB : return ME_SET_CGLB;
00064       case ME_SET_CGLB : return ME_SET_CLUB;
00065       default: return me;
00066       }
00067     }
00068 
00069     template<class View>
00070     forceinline PropCond
00071     ComplementView<View>::pc_negateset(PropCond pc) {
00072       switch(pc) {
00073       case PC_SET_CLUB  : return PC_SET_CGLB;
00074       case PC_SET_CGLB  : return PC_SET_CLUB;
00075       default: return pc;
00076       }
00077     }
00078 
00079     template<class View>
00080     forceinline bool
00081     ComplementView<View>::assigned(void) const { return view.assigned(); }
00082 
00083     template<class View>
00084     forceinline unsigned int
00085     ComplementView<View>::glbSize(void) const {
00086       return Limits::card - view.lubSize();
00087     }
00088 
00089     template<class View>
00090     forceinline unsigned int
00091     ComplementView<View>::lubSize(void) const {
00092       return Limits::card - view.glbSize();
00093     }
00094 
00095     template<class View>
00096     forceinline unsigned int
00097     ComplementView<View>::unknownSize(void) const {
00098       return lubSize() - glbSize();
00099     }
00100 
00101     template<class View>
00102     forceinline bool
00103     ComplementView<View>::contains(int n) const { return view.notContains(n); }
00104 
00105     template<class View>
00106     forceinline bool
00107     ComplementView<View>::notContains(int n) const { return view.contains(n); }
00108 
00109     template<class View>
00110     forceinline unsigned int
00111     ComplementView<View>::cardMin() const {
00112       return Limits::card - view.cardMax();
00113     }
00114 
00115     template<class View>
00116     forceinline unsigned int
00117     ComplementView<View>::cardMax() const {
00118       return Limits::card - view.cardMin();
00119     }
00120 
00121     template<class View>
00122     forceinline int
00123     ComplementView<View>::lubMin() const {
00124       GlbRanges<View> lb(view);
00125       RangesCompl<GlbRanges<View> > lbc(lb);
00126       if (lbc()) {
00127         return lbc.min();
00128       } else {
00129         return BndSet::MIN_OF_EMPTY;
00130       }
00131     }
00132 
00133     template<class View>
00134     forceinline int
00135     ComplementView<View>::lubMax() const {
00136       GlbRanges<View> lb(view);
00137       RangesCompl<GlbRanges<View> > lbc(lb);
00138       if (lbc()) {
00139         while(lbc()) ++lbc;
00140         return lbc.max();
00141       } else {
00142         return BndSet::MAX_OF_EMPTY;
00143       }
00144     }
00145 
00146     template<class View>
00147     forceinline int
00148     ComplementView<View>::glbMin() const {
00149       LubRanges<View> ub(view);
00150       RangesCompl<LubRanges<View> > ubc(ub);
00151       if (ubc()) {
00152         return ubc.min();
00153       } else {
00154         return BndSet::MIN_OF_EMPTY;
00155       }
00156     }
00157 
00158     template<class View>
00159     forceinline int
00160     ComplementView<View>::glbMax() const {
00161       LubRanges<View> ub(view);
00162       RangesCompl<LubRanges<View> > ubc(ub);
00163       if (ubc()) {
00164         while(ubc()) ++ubc;
00165         return ubc.max();
00166       } else {
00167         return BndSet::MAX_OF_EMPTY;
00168       }
00169     }
00170 
00171     template<class View>
00172     forceinline ModEvent
00173     ComplementView<View>::cardMin(Space& home, unsigned int c) {
00174       if (c < Limits::card)
00175         return me_negateset(view.cardMax(home, Limits::card - c));
00176       return ME_SET_NONE;
00177     }
00178 
00179     template<class View>
00180     forceinline ModEvent
00181     ComplementView<View>::cardMax(Space& home, unsigned int c) {
00182       if (c < Limits::card)
00183         return me_negateset(view.cardMin(home, Limits::card - c));
00184       return ME_SET_NONE;
00185     }
00186 
00187     template<class View>
00188     forceinline ModEvent
00189     ComplementView<View>::include(Space& home, int c) {
00190       return me_negateset((view.exclude(home, c)));
00191     }
00192 
00193     template<class View>
00194     forceinline ModEvent
00195     ComplementView<View>::exclude(Space& home, int c) {
00196       return me_negateset((view.include(home, c)));
00197     }
00198 
00199     template<class View>
00200     forceinline ModEvent
00201     ComplementView<View>::intersect(Space& home, int c) {
00202       Iter::Ranges::Singleton si(c,c);
00203       RangesCompl<Iter::Ranges::Singleton> csi(si);
00204       return me_negateset((view.includeI(home, csi)));
00205     }
00206 
00207     template<class View>
00208     forceinline ModEvent
00209     ComplementView<View>::intersect(Space& home, int i, int j) {
00210       Iter::Ranges::Singleton si(i,j);
00211       RangesCompl<Iter::Ranges::Singleton> csi(si);
00212       return me_negateset((view.includeI(home, csi)));
00213     }
00214 
00215     template<class View>
00216     forceinline ModEvent
00217     ComplementView<View>::include(Space& home, int j, int k) {
00218       return me_negateset(view.exclude(home,j,k));
00219     }
00220 
00221     template<class View>
00222     forceinline ModEvent
00223     ComplementView<View>::exclude(Space& home, int j, int k) {
00224       return me_negateset(view.include(home,j,k));
00225     }
00226 
00227     template<class View>
00228     template<class I> ModEvent
00229     ComplementView<View>::excludeI(Space& home,I& iter) {
00230       return me_negateset(view.includeI(home,iter));
00231     }
00232 
00233     template<class View>
00234     template<class I> ModEvent
00235     ComplementView<View>::includeI(Space& home,I& iter) {
00236       return me_negateset(view.excludeI(home,iter));
00237     }
00238 
00239     template<class View>
00240     template<class I> ModEvent
00241     ComplementView<View>::intersectI(Space& home,I& iter) {
00242       RangesCompl<I> c(iter);
00243       return me_negateset(view.includeI(home,c));
00244     }
00245 
00246     template<class View>
00247     forceinline void
00248     ComplementView<View>::subscribe(Space& home, Propagator& p, PropCond pc,
00249                                     bool process) {
00250       view.subscribe(home,p, pc_negateset(pc),process);
00251     }
00252 
00253     template<class View>
00254     forceinline void
00255     ComplementView<View>::cancel(Space& home, Propagator& p, PropCond pc) {
00256       view.cancel(home,p, pc_negateset(pc));
00257     }
00258 
00259     template<class View>
00260     forceinline void
00261     ComplementView<View>::subscribe(Space& home, Advisor& a) {
00262       view.subscribe(home,a);
00263     }
00264 
00265     template<class View>
00266     forceinline void
00267     ComplementView<View>::cancel(Space& home, Advisor& a) {
00268       view.cancel(home,a);
00269     }
00270 
00271     template<class View>
00272     forceinline void
00273     ComplementView<View>::schedule(Space& home, Propagator& p, ModEvent me) {
00274       return View::schedule(home,p,me_negateset(me));
00275     }
00276     template<class View>
00277     forceinline ModEvent
00278     ComplementView<View>::me(const ModEventDelta& med) {
00279       return me_negateset(View::me(med));
00280     }
00281 
00282     template<class View>
00283     forceinline ModEventDelta
00284     ComplementView<View>::med(ModEvent me) {
00285       return me_negateset(View::med(me));
00286     }
00287 
00288     template<class View>
00289     forceinline void
00290     ComplementView<View>::update(Space& home, bool share,
00291                                  ComplementView& y) {
00292       view.update(home,share,y.view);
00293     }
00294 
00295 
00296     /*
00297      * Delta information for advisors
00298      *
00299      */
00300 
00301     template<class View>
00302     forceinline ModEvent
00303     ComplementView<View>::modevent(const Delta& d) {
00304       return me_negateset(View::modevent(d));
00305     }
00306 
00307     template<class View>
00308     forceinline int
00309     ComplementView<View>::glbMin(const Delta& d) const {
00310       return view.lubMin(d);
00311     }
00312 
00313     template<class View>
00314     forceinline int
00315     ComplementView<View>::glbMax(const Delta& d) const {
00316       return view.lubMax(d);
00317     }
00318 
00319     template<class View>
00320     forceinline bool
00321     ComplementView<View>::glbAny(const Delta& d) const {
00322       return view.lubAny(d);
00323     }
00324 
00325     template<class View>
00326     forceinline int
00327     ComplementView<View>::lubMin(const Delta& d) const {
00328       return view.glbMin(d);
00329     }
00330 
00331     template<class View>
00332     forceinline int
00333     ComplementView<View>::lubMax(const Delta& d) const {
00334       return view.glbMax(d);
00335     }
00336 
00337     template<class View>
00338     forceinline bool
00339     ComplementView<View>::lubAny(const Delta& d) const {
00340       return view.glbAny(d);
00341     }
00342 
00343 
00348     template<class View>
00349     class LubRanges<ComplementView<View> > {
00350     private:
00351       GlbRanges<View> lb;
00352       RangesCompl<GlbRanges<View> > lbc;
00353     public:
00355 
00356 
00357       LubRanges(void) {}
00359       LubRanges(const ComplementView<View>& x);
00361       void init(const ComplementView<View>& x);
00362 
00364 
00365 
00366       bool operator ()(void) const;
00368       void operator ++(void);
00370 
00372 
00373 
00374       int min(void) const;
00376       int max(void) const;
00378       unsigned int width(void) const;
00380     };
00381 
00382     template<class View>
00383     forceinline
00384     LubRanges<ComplementView<View> >::LubRanges(const ComplementView<View>& s)
00385       : lb(s.base()), lbc(lb) {}
00386 
00387     template<class View>
00388     forceinline void
00389     LubRanges<ComplementView<View> >::init(const ComplementView<View>& s) {
00390       lb.init(s.base());
00391       lbc.init(lb);
00392     }
00393 
00394     template<class View>
00395     forceinline bool
00396     LubRanges<ComplementView<View> >::operator ()(void) const { return lbc(); }
00397 
00398     template<class View>
00399     forceinline void
00400     LubRanges<ComplementView<View> >::operator ++(void) { return ++lbc; }
00401 
00402     template<class View>
00403     forceinline int
00404     LubRanges<ComplementView<View> >::min(void) const { return lbc.min(); }
00405 
00406     template<class View>
00407     forceinline int
00408     LubRanges<ComplementView<View> >::max(void) const { return lbc.max(); }
00409 
00410     template<class View>
00411     forceinline unsigned int
00412     LubRanges<ComplementView<View> >::width(void) const { return lbc.width(); }
00413 
00422     template<class View>
00423     class LubRanges<ComplementView<ComplementView<View> > > :
00424       public LubRanges<View> {
00425     public:
00427 
00428 
00429       LubRanges(void) {}
00431       LubRanges(const ComplementView<ComplementView<View> >& x);
00433       void init(const ComplementView<ComplementView<View> >& x);
00435     };
00436 
00437     template<class View>
00438     forceinline
00439     LubRanges<ComplementView<ComplementView<View> > >::
00440     LubRanges(const ComplementView<ComplementView<View> >& x) :
00441       LubRanges<View>(x) {}
00442 
00443     template<class View>
00444     forceinline void
00445     LubRanges<ComplementView<ComplementView<View> > >::
00446     init(const ComplementView<ComplementView<View> >& x) {
00447       LubRanges<View>::init(x);
00448     }
00449 
00454     template<class View>
00455     class GlbRanges<ComplementView<View> > {
00456     private:
00457       LubRanges<View> ub;
00458       RangesCompl<LubRanges<View> > ubc;
00459     public:
00461 
00462 
00463       GlbRanges(void) {}
00465       GlbRanges(const ComplementView<View> & x);
00467       void init(const ComplementView<View> & x);
00468 
00470 
00471 
00472       bool operator ()(void) const;
00474       void operator ++(void);
00476 
00478 
00479 
00480       int min(void) const;
00482       int max(void) const;
00484       unsigned int width(void) const;
00486     };
00487 
00488     template<class View>
00489     forceinline
00490     GlbRanges<ComplementView<View> >::GlbRanges(const ComplementView<View> & s)
00491       : ub(s.base()), ubc(ub) {}
00492 
00493     template<class View>
00494     forceinline void
00495     GlbRanges<ComplementView<View> >::init(const ComplementView<View> & s) {
00496       ub.init(s.base());
00497       ubc.init(ub);
00498     }
00499 
00500     template<class View>
00501     forceinline bool
00502     GlbRanges<ComplementView<View> >::operator ()(void) const { return ubc(); }
00503 
00504     template<class View>
00505     forceinline void
00506     GlbRanges<ComplementView<View> >::operator ++(void) { return ++ubc; }
00507 
00508     template<class View>
00509     forceinline int
00510     GlbRanges<ComplementView<View> >::min(void) const { return ubc.min(); }
00511 
00512     template<class View>
00513     forceinline int
00514     GlbRanges<ComplementView<View> >::max(void) const { return ubc.max(); }
00515 
00516     template<class View>
00517     forceinline unsigned int
00518     GlbRanges<ComplementView<View> >::width(void) const { return ubc.width(); }
00519 
00528     template<class View>
00529     class GlbRanges<ComplementView<ComplementView<View> > > :
00530       public GlbRanges<View> {
00531     public:
00533 
00534 
00535       GlbRanges(void) {}
00537       GlbRanges(const ComplementView<ComplementView<View> >& x);
00539       void init(const ComplementView<ComplementView<View> >& x);
00541     };
00542 
00543     template<class View>
00544     forceinline
00545     GlbRanges<ComplementView<ComplementView<View> > >::
00546     GlbRanges(const ComplementView<ComplementView<View> >& x) :
00547       GlbRanges<View>(x) {}
00548 
00549     template<class View>
00550     forceinline void
00551     GlbRanges<ComplementView<ComplementView<View> > >::
00552     init(const ComplementView<ComplementView<View> >& x) {
00553       GlbRanges<View>::init(x);
00554     }
00555 
00556     template<class Char, class Traits, class View>
00557     std::basic_ostream<Char,Traits>&
00558     operator <<(std::basic_ostream<Char,Traits>& os,
00559                 const ComplementView<View>& x) {
00560       std::basic_ostringstream<Char,Traits> s;
00561       s.copyfmt(os); s.width(0);
00562       s << "(" << x.base() << ")^C";
00563       return os << s.str();
00564     }
00565 
00566   }
00567 
00568 
00569   /*
00570    * Testing
00571    *
00572    */
00573   template<class View>
00574   forceinline bool
00575   same(const Set::ComplementView<View>& x,
00576        const Set::ComplementView<View>& y) {
00577     return same(x.base(),y.base());
00578   }
00579   template<class View>
00580   forceinline bool
00581   before(const Set::ComplementView<View>& x,
00582          const Set::ComplementView<View>& y) {
00583     return before(x.base(),y.base());
00584   }
00585   template<class View>
00586   forceinline bool
00587   same(const Set::ComplementView<Set::ComplementView<View> >& x,
00588        const Set::ComplementView<Set::ComplementView<View> >& y) {
00589     return same(x,y);
00590   }
00591   template<class View>
00592   forceinline bool
00593   before(const Set::ComplementView<Set::ComplementView<View> >& x,
00594          const Set::ComplementView<Set::ComplementView<View> >& y) {
00595     return before(x,y);
00596   }
00597 
00598 }
00599 
00600 // STATISTICS: set-var