view.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: 2011-08-19 16:47:28 +0200 (Fri, 19 Aug 2011) $ by $Author: tack $
00015  *     $Revision: 12318 $
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 <iostream>
00043 
00044 namespace Gecode { namespace Set {
00045 
00060   class SetView : public VarImpView<SetVar> {
00061   protected:
00062     using VarImpView<SetVar>::x;
00063   public:
00065 
00066 
00067     SetView(void);
00069     SetView(const SetVar& y);
00071     SetView(SetVarImp* y);
00073 
00075 
00076 
00078     unsigned int cardMin(void) const;
00080     unsigned int cardMax(void) const;
00082     int lubMin(void) const;
00084     int lubMax(void) const;
00086     int lubMinN(unsigned int n) const;
00088     int glbMin(void) const;
00090     int glbMax(void) const;
00091 
00093     unsigned int glbSize(void) const;
00095     unsigned int lubSize(void) const;
00097     unsigned int unknownSize(void) const;
00099 
00101 
00102 
00103     bool contains(int i) const;
00105     bool notContains(int i) const;
00107 
00108 
00110 
00111 
00112     ModEvent cardMin(Space& home, unsigned int m);
00114     ModEvent cardMax(Space& home, unsigned int m);
00119     ModEvent include(Space& home,int i,int j);
00124     ModEvent exclude(Space& home,int i,int j);
00126     ModEvent include(Space& home,int i);
00128     ModEvent exclude(Space& home,int i);
00133     ModEvent intersect(Space& home,int i,int j);
00135     ModEvent intersect(Space& home,int i);
00137 
00139 
00140 
00142     template<class I> ModEvent excludeI(Space& home, I& i);
00144     template<class I> ModEvent includeI(Space& home, I& i);
00146     template<class I> ModEvent intersectI(Space& home, I& iter);
00148 
00150 
00151 
00152     static ModEvent modevent(const Delta& d);
00154     int glbMin(const Delta& d) const;
00156     int glbMax(const Delta& d) const;
00158     bool glbAny(const Delta& d) const;
00160     int lubMin(const Delta& d) const;
00162     int lubMax(const Delta& d) const;
00164     bool lubAny(const Delta& d) const;
00166   };
00167 
00172   template<class Char, class Traits>
00173   std::basic_ostream<Char,Traits>&
00174   operator <<(std::basic_ostream<Char,Traits>& os, const SetView& x);
00175 
00176 
00177 
00178   // Forward declarations for friends
00179   class ConstSetView;
00180   bool same(const ConstSetView&, const ConstSetView&);
00181   bool before(const ConstSetView&, const ConstSetView&);
00182 
00190   class ConstSetView : public ConstView<SetView> {
00191     friend class LubRanges<ConstSetView>;
00192     friend class GlbRanges<ConstSetView>;
00193     friend bool Gecode::Set::same(const Gecode::Set::ConstSetView&,
00194                                   const Gecode::Set::ConstSetView&);
00195     friend bool Gecode::Set::before(const Gecode::Set::ConstSetView&,
00196                                     const Gecode::Set::ConstSetView&);
00197   private:
00198     int *ranges;
00199     int size;
00200     unsigned int domSize;
00201   public:
00203 
00204 
00205     ConstSetView(void);
00207     ConstSetView(Space& home, const IntSet& s);
00209 
00211 
00212 
00213     unsigned int cardMin(void) const;
00215     unsigned int cardMax(void) const;
00217     int lubMin(void) const;
00219     int lubMax(void) const;
00221     int lubMinN(unsigned int n) const;
00223     int glbMin(void) const;
00225     int glbMax(void) const;
00226 
00228     unsigned int glbSize(void) const;
00230     unsigned int lubSize(void) const;
00232     unsigned int unknownSize(void) const;
00234 
00236 
00237 
00238     bool contains(int i) const;
00240     bool notContains(int i) const;
00242 
00243 
00245 
00246 
00247     ModEvent cardMin(Space& home, unsigned int m);
00249     ModEvent cardMax(Space& home, unsigned int m);
00254     ModEvent include(Space& home,int i,int j);
00259     ModEvent exclude(Space& home,int i,int j);
00261     ModEvent include(Space& home,int i);
00263     ModEvent exclude(Space& home,int i);
00268     ModEvent intersect(Space& home,int i,int j);
00270     ModEvent intersect(Space& home,int i);
00272 
00274 
00275 
00277     template<class I> ModEvent excludeI(Space& home, I& i);
00279     template<class I> ModEvent includeI(Space& home, I& i);
00281     template<class I> ModEvent intersectI(Space& home, I& iter);
00283 
00285 
00286 
00287     void update(Space& home, bool share, ConstSetView& y);
00289 
00291 
00292 
00293     int glbMin(const Delta& d) const;
00295     int glbMax(const Delta& d) const;
00297     bool glbAny(const Delta& d) const;
00299     int lubMin(const Delta& d) const;
00301     int lubMax(const Delta& d) const;
00303     bool lubAny(const Delta& d) const;
00305 
00306   };
00307 
00312   template<class Char, class Traits>
00313   std::basic_ostream<Char,Traits>&
00314   operator <<(std::basic_ostream<Char,Traits>& os, const ConstSetView& x);
00315 
00320 
00321   bool same(const ConstSetView& x, const ConstSetView& y);
00323   bool before(const ConstSetView& x, const ConstSetView& y);
00325 
00326 
00335   class EmptyView : public ConstView<SetView> {
00336   public:
00338 
00339 
00340     EmptyView(void);
00342 
00344 
00345 
00346     unsigned int cardMin(void) const;
00348     unsigned int cardMax(void) const;
00350     int lubMin(void) const;
00352     int lubMax(void) const;
00354     int lubMinN(unsigned int n) const;
00356     int glbMin(void) const;
00358     int glbMax(void) const;
00359 
00361     unsigned int glbSize(void) const;
00363     unsigned int lubSize(void) const;
00365     unsigned int unknownSize(void) const;
00367 
00369 
00370 
00371     bool contains(int i) const;
00373     bool notContains(int i) const;
00375 
00376 
00378 
00379 
00380     ModEvent cardMin(Space& home, unsigned int m);
00382     ModEvent cardMax(Space& home, unsigned int m);
00387     ModEvent include(Space& home,int i,int j);
00392     ModEvent exclude(Space& home,int i,int j);
00394     ModEvent include(Space& home,int i);
00396     ModEvent exclude(Space& home,int i);
00401     ModEvent intersect(Space& home,int i,int j);
00403     ModEvent intersect(Space& home,int i);
00405 
00407 
00408 
00410     template<class I> ModEvent excludeI(Space& home, I& i);
00412     template<class I> ModEvent includeI(Space& home, I& i);
00414     template<class I> ModEvent intersectI(Space& home, I& iter);
00416 
00418 
00419 
00420     int glbMin(const Delta& d) const;
00422     int glbMax(const Delta& d) const;
00424     bool glbAny(const Delta& d) const;
00426     int lubMin(const Delta& d) const;
00428     int lubMax(const Delta& d) const;
00430     bool lubAny(const Delta& d) const;
00432 
00433   };
00434 
00439   template<class Char, class Traits>
00440   std::basic_ostream<Char,Traits>&
00441   operator <<(std::basic_ostream<Char,Traits>& os, const EmptyView& x);
00442 
00443 
00448 
00449   bool same(const EmptyView& x, const EmptyView& y);
00451 
00452 
00461   class UniverseView : public ConstView<SetView> {
00462   public:
00464 
00465 
00466     UniverseView(void);
00468 
00470 
00471 
00473     unsigned int cardMin(void) const;
00475     unsigned int cardMax(void) const;
00477     int lubMin(void) const;
00479     int lubMax(void) const;
00481     int lubMinN(unsigned int n) const;
00483     int glbMin(void) const;
00485     int glbMax(void) const;
00486 
00488     unsigned int glbSize(void) const;
00490     unsigned int lubSize(void) const;
00492     unsigned int unknownSize(void) const;
00494 
00496 
00497 
00498     bool contains(int i) const;
00500     bool notContains(int i) const;
00502 
00503 
00505 
00506 
00507     ModEvent cardMin(Space& home, unsigned int m);
00509     ModEvent cardMax(Space& home, unsigned int m);
00514     ModEvent include(Space& home,int i,int j);
00519     ModEvent exclude(Space& home,int i,int j);
00521     ModEvent include(Space& home,int i);
00523     ModEvent exclude(Space& home,int i);
00528     ModEvent intersect(Space& home,int i,int j);
00530     ModEvent intersect(Space& home,int i);
00532 
00534 
00535 
00537     template<class I> ModEvent excludeI(Space& home, I& i);
00539     template<class I> ModEvent includeI(Space& home, I& i);
00541     template<class I> ModEvent intersectI(Space& home, I& iter);
00543 
00545 
00546 
00547     int glbMin(const Delta& d) const;
00549     int glbMax(const Delta& d) const;
00551     bool glbAny(const Delta& d) const;
00553     int lubMin(const Delta& d) const;
00555     int lubMax(const Delta& d) const;
00557     bool lubAny(const Delta& d) const;
00559 
00560   };
00561 
00566   template<class Char, class Traits>
00567   std::basic_ostream<Char,Traits>&
00568   operator <<(std::basic_ostream<Char,Traits>& os, const UniverseView& x);
00569 
00570 
00575 
00576   bool same(const UniverseView& x, const UniverseView& y);
00578 
00579 
00580 
00589   class SingletonView :
00590     public DerivedView<Gecode::Int::IntView> {
00591   protected:
00592     using DerivedView<Gecode::Int::IntView>::x;
00593 
00595     static PropCond pc_settoint(PropCond pc);
00597     static ModEvent me_inttoset(ModEvent me);
00599     static ModEvent me_settoint(ModEvent me);
00600 
00601   public:
00603 
00604 
00605     SingletonView(void);
00607     SingletonView(Gecode::Int::IntView& y);
00609     SingletonView(const Gecode::IntVar& y);
00611 
00613 
00614 
00616     unsigned int cardMin(void) const;
00618     unsigned int cardMax(void) const;
00620     int lubMin(void) const;
00622     int lubMax(void) const;
00624     int lubMinN(unsigned int n) const;
00626     int glbMin(void) const;
00628     int glbMax(void) const;
00629 
00631     unsigned int glbSize(void) const;
00633     unsigned int lubSize(void) const;
00635     unsigned int unknownSize(void) const;
00637 
00639 
00640 
00641     bool contains(int i) const;
00643     bool notContains(int i) const;
00645 
00646 
00648 
00649 
00650     ModEvent cardMin(Space& home, unsigned int m);
00652     ModEvent cardMax(Space& home, unsigned int m);
00657     ModEvent include(Space& home,int i,int j);
00662     ModEvent exclude(Space& home,int i,int j);
00664     ModEvent include(Space& home,int i);
00666     ModEvent exclude(Space& home,int i);
00671     ModEvent intersect(Space& home,int i,int j);
00673     ModEvent intersect(Space& home,int i);
00675 
00677 
00678 
00680     template<class I> ModEvent excludeI(Space& home, I& i);
00682     template<class I> ModEvent includeI(Space& home, I& i);
00684     template<class I> ModEvent intersectI(Space& home, I& iter);
00686 
00688 
00689 
00690     static void schedule(Space& home, Propagator& p, ModEvent me);
00692     static ModEvent me(const ModEventDelta& med);
00694     static ModEventDelta med(ModEvent);
00696 
00698 
00699 
00706     void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
00708     void cancel(Space& home, Propagator& p, PropCond pc);
00710     void subscribe(Space& home, Advisor& a);
00712     void cancel(Space& home, Advisor& a);
00714 
00716 
00717 
00718     static ModEvent modevent(const Delta& d);
00720     int glbMin(const Delta& d) const;
00722     int glbMax(const Delta& d) const;
00724     bool glbAny(const Delta& d) const;
00726     int lubMin(const Delta& d) const;
00728     int lubMax(const Delta& d) const;
00730     bool lubAny(const Delta& d) const;
00732 
00733   };
00734 
00739   template<class Char, class Traits>
00740   std::basic_ostream<Char,Traits>&
00741   operator <<(std::basic_ostream<Char,Traits>& os, const SingletonView& x);
00742 
00743 
00753   template<class View>
00754   class ComplementView
00755     : public DerivedView<View> {
00756   protected:
00757     using DerivedView<View>::x;
00758 
00759   public:
00761     static PropCond pc_negateset(PropCond pc);
00763     static ModEvent me_negateset(ModEvent me);
00764 
00766 
00767 
00768     ComplementView(void);
00770     explicit ComplementView(View& y);
00772 
00774 
00775 
00777     unsigned int cardMin(void) const;
00779     unsigned int cardMax(void) const;
00781     int lubMin(void) const;
00783     int lubMax(void) const;
00785     int lubMinN(unsigned int n) const;
00787     int glbMin(void) const;
00789     int glbMax(void) const;
00790 
00792     unsigned int glbSize(void) const;
00794     unsigned int lubSize(void) const;
00796     unsigned int unknownSize(void) const;
00798 
00800 
00801 
00802     bool contains(int i) const;
00804     bool notContains(int i) const;
00806 
00807 
00809 
00810 
00811     ModEvent cardMin(Space& home, unsigned int m);
00813     ModEvent cardMax(Space& home, unsigned int m);
00818     ModEvent include(Space& home,int i,int j);
00823     ModEvent exclude(Space& home,int i,int j);
00825     ModEvent include(Space& home,int i);
00827     ModEvent exclude(Space& home,int i);
00832     ModEvent intersect(Space& home,int i,int j);
00834     ModEvent intersect(Space& home,int i);
00836 
00838 
00839 
00841     template<class I> ModEvent excludeI(Space& home, I& i);
00843     template<class I> ModEvent includeI(Space& home, I& i);
00845     template<class I> ModEvent intersectI(Space& home, I& iter);
00847 
00849 
00850 
00851     static void schedule(Space& home, Propagator& p, ModEvent me);
00853     static ModEvent me(const ModEventDelta& med);
00855     static ModEventDelta med(ModEvent);
00857 
00859 
00860 
00867     void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
00869     void cancel(Space& home, Propagator& p, PropCond pc);
00871     void subscribe(Space& home, Advisor& a);
00873     void cancel(Space& home, Advisor& a);
00875 
00877 
00878 
00879     static ModEvent modevent(const Delta& d);
00881     int glbMin(const Delta& d) const;
00883     int glbMax(const Delta& d) const;
00885     bool glbAny(const Delta& d) const;
00887     int lubMin(const Delta& d) const;
00889     int lubMax(const Delta& d) const;
00891     bool lubAny(const Delta& d) const;
00893 
00894   };
00895 
00900   template<class Char, class Traits, class View>
00901   std::basic_ostream<Char,Traits>&
00902   operator <<(std::basic_ostream<Char,Traits>& os,
00903               const ComplementView<View>& x);
00904 
00905 
00906   template<class View> class LubDiffRanges;
00907   template<class View> class GlbDiffRanges;
00908 
00920   template<class View>
00921   class CachedView
00922     : public DerivedView<View> {
00923     friend class LubDiffRanges<View>;
00924     friend class GlbDiffRanges<View>;
00925   protected:
00926     using DerivedView<View>::x;
00927 
00929     LUBndSet lubCache;
00931     GLBndSet glbCache;
00932 
00933   public:
00934 
00936 
00937 
00938     CachedView(void);
00940     explicit CachedView(const View& y);
00942 
00944 
00945 
00947     unsigned int cardMin(void) const;
00949     unsigned int cardMax(void) const;
00951     int lubMin(void) const;
00953     int lubMax(void) const;
00955     int lubMinN(unsigned int n) const;
00957     int glbMin(void) const;
00959     int glbMax(void) const;
00960 
00962     unsigned int glbSize(void) const;
00964     unsigned int lubSize(void) const;
00966     unsigned int unknownSize(void) const;
00968 
00970 
00971 
00972     bool contains(int i) const;
00974     bool notContains(int i) const;
00976 
00977 
00979 
00980 
00981     ModEvent cardMin(Space& home, unsigned int m);
00983     ModEvent cardMax(Space& home, unsigned int m);
00988     ModEvent include(Space& home,int i,int j);
00993     ModEvent exclude(Space& home,int i,int j);
00995     ModEvent include(Space& home,int i);
00997     ModEvent exclude(Space& home,int i);
01002     ModEvent intersect(Space& home,int i,int j);
01004     ModEvent intersect(Space& home,int i);
01006 
01008 
01009 
01011     template<class I> ModEvent excludeI(Space& home, I& i);
01013     template<class I> ModEvent includeI(Space& home, I& i);
01015     template<class I> ModEvent intersectI(Space& home, I& iter);
01017 
01019 
01020 
01021     static void schedule(Space& home, Propagator& p, ModEvent me);
01023     static ModEvent me(const ModEventDelta& med);
01025     static ModEventDelta med(ModEvent);
01027 
01029 
01030 
01037     void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
01039     void cancel(Space& home, Propagator& p, PropCond pc);
01041     void subscribe(Space& home, Advisor& a);
01043     void cancel(Space& home, Advisor& a);
01045 
01047 
01048 
01049     static ModEvent modevent(const Delta& d);
01051     int glbMin(const Delta& d) const;
01053     int glbMax(const Delta& d) const;
01055     bool glbAny(const Delta& d) const;
01057     int lubMin(const Delta& d) const;
01059     int lubMax(const Delta& d) const;
01061     bool lubAny(const Delta& d) const;
01063 
01065 
01066 
01067     void initCache(Space& home, const IntSet& glb, const IntSet& lub);
01069     void cacheGlb(Space& home);
01071     void cacheLub(Space& home);
01073     bool glbModified(void) const;
01075     bool lubModified(void) const;
01077 
01079 
01080 
01081     void update(Space& home, bool share, CachedView<View>& y);
01083   };
01084 
01089   template<class Char, class Traits, class View>
01090   std::basic_ostream<Char,Traits>&
01091   operator <<(std::basic_ostream<Char,Traits>& os,
01092               const CachedView<View>& x);
01093 
01098   template<class View>
01099   class GlbDiffRanges
01100     : public Iter::Ranges::Diff<GlbRanges<View>,BndSetRanges> {
01101   protected:
01103     GlbRanges<View> gr;
01105     BndSetRanges cr;
01106   public:
01108     GlbDiffRanges(const CachedView<View>& x);
01109   };
01110 
01115   template<class View>
01116   class LubDiffRanges
01117     : public Iter::Ranges::Diff<BndSetRanges,LubRanges<View> > {
01118   protected:
01120     BndSetRanges cr;
01122     LubRanges<View> lr;
01123   public:
01125     LubDiffRanges(const CachedView<View>& x);
01126   };
01127 
01128 }}
01129 
01130 #include <gecode/set/var/set.hpp>
01131 
01132 #include <gecode/set/view/set.hpp>
01133 
01134 #include <gecode/set/view/const.hpp>
01135 #include <gecode/set/view/singleton.hpp>
01136 #include <gecode/set/view/complement.hpp>
01137 #include <gecode/set/view/cached.hpp>
01138 
01139 #include <gecode/set/view/print.hpp>
01140 #include <gecode/set/var/print.hpp>
01141 
01142 // STATISTICS: set-var