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  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #include <iostream>
00039 
00040 namespace Gecode { namespace Set {
00041 
00056   class SetView : public VarImpView<SetVar> {
00057   protected:
00058     using VarImpView<SetVar>::x;
00059   public:
00061 
00062 
00063     SetView(void);
00065     SetView(const SetVar& y);
00067     SetView(SetVarImp* y);
00069 
00071 
00072 
00074     unsigned int cardMin(void) const;
00076     unsigned int cardMax(void) const;
00078     int lubMin(void) const;
00080     int lubMax(void) const;
00082     int lubMinN(unsigned int n) const;
00084     int glbMin(void) const;
00086     int glbMax(void) const;
00087 
00089     unsigned int glbSize(void) const;
00091     unsigned int lubSize(void) const;
00093     unsigned int unknownSize(void) const;
00095 
00097 
00098 
00099     bool contains(int i) const;
00101     bool notContains(int i) const;
00103 
00104 
00106 
00107 
00108     ModEvent cardMin(Space& home, unsigned int m);
00110     ModEvent cardMax(Space& home, unsigned int m);
00115     ModEvent include(Space& home,int i,int j);
00120     ModEvent exclude(Space& home,int i,int j);
00122     ModEvent include(Space& home,int i);
00124     ModEvent exclude(Space& home,int i);
00129     ModEvent intersect(Space& home,int i,int j);
00131     ModEvent intersect(Space& home,int i);
00133 
00135 
00136 
00138     template<class I> ModEvent excludeI(Space& home, I& i);
00140     template<class I> ModEvent includeI(Space& home, I& i);
00142     template<class I> ModEvent intersectI(Space& home, I& iter);
00144 
00146 
00147 
00148     static ModEvent modevent(const Delta& d);
00150     int glbMin(const Delta& d) const;
00152     int glbMax(const Delta& d) const;
00154     bool glbAny(const Delta& d) const;
00156     int lubMin(const Delta& d) const;
00158     int lubMax(const Delta& d) const;
00160     bool lubAny(const Delta& d) const;
00162   };
00163 
00168   template<class Char, class Traits>
00169   std::basic_ostream<Char,Traits>&
00170   operator <<(std::basic_ostream<Char,Traits>& os, const SetView& x);
00171 
00172 
00173 
00174   // Forward declarations for friends
00175   class ConstSetView;
00176   bool operator ==(const ConstSetView&, const ConstSetView&);
00177   bool operator !=(const ConstSetView&, const ConstSetView&);
00178 
00186   class ConstSetView : public ConstView<SetView> {
00187     friend class LubRanges<ConstSetView>;
00188     friend class GlbRanges<ConstSetView>;
00189     friend bool Gecode::Set::operator ==(const Gecode::Set::ConstSetView&,
00190                                          const Gecode::Set::ConstSetView&);
00191     friend bool Gecode::Set::operator !=(const Gecode::Set::ConstSetView&,
00192                                          const Gecode::Set::ConstSetView&);
00193   private:
00194     int *ranges;
00195     int size;
00196     unsigned int domSize;
00197   public:
00199 
00200 
00201     ConstSetView(void);
00203     ConstSetView(Space& home, const IntSet& s);
00205 
00207 
00208 
00209     unsigned int cardMin(void) const;
00211     unsigned int cardMax(void) const;
00213     int lubMin(void) const;
00215     int lubMax(void) const;
00217     int lubMinN(unsigned int n) const;
00219     int glbMin(void) const;
00221     int glbMax(void) const;
00222 
00224     unsigned int glbSize(void) const;
00226     unsigned int lubSize(void) const;
00228     unsigned int unknownSize(void) const;
00230 
00232 
00233 
00234     bool contains(int i) const;
00236     bool notContains(int i) const;
00238 
00239 
00241 
00242 
00243     ModEvent cardMin(Space& home, unsigned int m);
00245     ModEvent cardMax(Space& home, unsigned int m);
00250     ModEvent include(Space& home,int i,int j);
00255     ModEvent exclude(Space& home,int i,int j);
00257     ModEvent include(Space& home,int i);
00259     ModEvent exclude(Space& home,int i);
00264     ModEvent intersect(Space& home,int i,int j);
00266     ModEvent intersect(Space& home,int i);
00268 
00270 
00271 
00273     template<class I> ModEvent excludeI(Space& home, I& i);
00275     template<class I> ModEvent includeI(Space& home, I& i);
00277     template<class I> ModEvent intersectI(Space& home, I& iter);
00279 
00281 
00282 
00283     void update(Space& home, ConstSetView& y);
00285 
00287 
00288 
00289     int glbMin(const Delta& d) const;
00291     int glbMax(const Delta& d) const;
00293     bool glbAny(const Delta& d) const;
00295     int lubMin(const Delta& d) const;
00297     int lubMax(const Delta& d) const;
00299     bool lubAny(const Delta& d) const;
00301 
00303 
00304 
00305     bool operator <(const ConstSetView& y) const;
00307   };
00308 
00313   template<class Char, class Traits>
00314   std::basic_ostream<Char,Traits>&
00315   operator <<(std::basic_ostream<Char,Traits>& os, const ConstSetView& x);
00316 
00321 
00322   bool operator ==(const ConstSetView& x, const ConstSetView& y);
00324   bool operator !=(const ConstSetView& x, const ConstSetView& y);
00326 
00327 
00336   class EmptyView : public ConstView<SetView> {
00337   public:
00339 
00340 
00341     EmptyView(void);
00343 
00345 
00346 
00347     unsigned int cardMin(void) const;
00349     unsigned int cardMax(void) const;
00351     int lubMin(void) const;
00353     int lubMax(void) const;
00355     int lubMinN(unsigned int n) const;
00357     int glbMin(void) const;
00359     int glbMax(void) const;
00360 
00362     unsigned int glbSize(void) const;
00364     unsigned int lubSize(void) const;
00366     unsigned int unknownSize(void) const;
00368 
00370 
00371 
00372     bool contains(int i) const;
00374     bool notContains(int i) const;
00376 
00377 
00379 
00380 
00381     ModEvent cardMin(Space& home, unsigned int m);
00383     ModEvent cardMax(Space& home, unsigned int m);
00388     ModEvent include(Space& home,int i,int j);
00393     ModEvent exclude(Space& home,int i,int j);
00395     ModEvent include(Space& home,int i);
00397     ModEvent exclude(Space& home,int i);
00402     ModEvent intersect(Space& home,int i,int j);
00404     ModEvent intersect(Space& home,int i);
00406 
00408 
00409 
00411     template<class I> ModEvent excludeI(Space& home, I& i);
00413     template<class I> ModEvent includeI(Space& home, I& i);
00415     template<class I> ModEvent intersectI(Space& home, I& iter);
00417 
00419 
00420 
00421     int glbMin(const Delta& d) const;
00423     int glbMax(const Delta& d) const;
00425     bool glbAny(const Delta& d) const;
00427     int lubMin(const Delta& d) const;
00429     int lubMax(const Delta& d) const;
00431     bool lubAny(const Delta& d) const;
00433 
00434   };
00435 
00440   template<class Char, class Traits>
00441   std::basic_ostream<Char,Traits>&
00442   operator <<(std::basic_ostream<Char,Traits>& os, const EmptyView& x);
00443 
00444 
00449 
00450   bool operator ==(const EmptyView& x, const EmptyView& y);
00452   bool operator !=(const EmptyView& x, const EmptyView& y);
00454 
00455 
00464   class UniverseView : public ConstView<SetView> {
00465   public:
00467 
00468 
00469     UniverseView(void);
00471 
00473 
00474 
00476     unsigned int cardMin(void) const;
00478     unsigned int cardMax(void) const;
00480     int lubMin(void) const;
00482     int lubMax(void) const;
00484     int lubMinN(unsigned int n) const;
00486     int glbMin(void) const;
00488     int glbMax(void) const;
00489 
00491     unsigned int glbSize(void) const;
00493     unsigned int lubSize(void) const;
00495     unsigned int unknownSize(void) const;
00497 
00499 
00500 
00501     bool contains(int i) const;
00503     bool notContains(int i) const;
00505 
00506 
00508 
00509 
00510     ModEvent cardMin(Space& home, unsigned int m);
00512     ModEvent cardMax(Space& home, unsigned int m);
00517     ModEvent include(Space& home,int i,int j);
00522     ModEvent exclude(Space& home,int i,int j);
00524     ModEvent include(Space& home,int i);
00526     ModEvent exclude(Space& home,int i);
00531     ModEvent intersect(Space& home,int i,int j);
00533     ModEvent intersect(Space& home,int i);
00535 
00537 
00538 
00540     template<class I> ModEvent excludeI(Space& home, I& i);
00542     template<class I> ModEvent includeI(Space& home, I& i);
00544     template<class I> ModEvent intersectI(Space& home, I& iter);
00546 
00548 
00549 
00550     int glbMin(const Delta& d) const;
00552     int glbMax(const Delta& d) const;
00554     bool glbAny(const Delta& d) const;
00556     int lubMin(const Delta& d) const;
00558     int lubMax(const Delta& d) const;
00560     bool lubAny(const Delta& d) const;
00562 
00563   };
00564 
00569   template<class Char, class Traits>
00570   std::basic_ostream<Char,Traits>&
00571   operator <<(std::basic_ostream<Char,Traits>& os, const UniverseView& x);
00572 
00573 
00578 
00579   bool operator ==(const UniverseView& x, const UniverseView& y);
00581   bool operator !=(const UniverseView& x, const UniverseView& y);
00583 
00584 
00585 
00594   class SingletonView : public DerivedView<Gecode::Int::IntView> {
00595   protected:
00596     using DerivedView<Gecode::Int::IntView>::x;
00597 
00599     static PropCond pc_settoint(PropCond pc);
00601     static ModEvent me_inttoset(ModEvent me);
00603     static ModEvent me_settoint(ModEvent me);
00604 
00605   public:
00607 
00608 
00609     SingletonView(void);
00611     SingletonView(Gecode::Int::IntView& y);
00613     SingletonView(const Gecode::IntVar& y);
00615 
00617 
00618 
00620     unsigned int cardMin(void) const;
00622     unsigned int cardMax(void) const;
00624     int lubMin(void) const;
00626     int lubMax(void) const;
00628     int lubMinN(unsigned int n) const;
00630     int glbMin(void) const;
00632     int glbMax(void) const;
00633 
00635     unsigned int glbSize(void) const;
00637     unsigned int lubSize(void) const;
00639     unsigned int unknownSize(void) const;
00641 
00643 
00644 
00645     bool contains(int i) const;
00647     bool notContains(int i) const;
00649 
00650 
00652 
00653 
00654     ModEvent cardMin(Space& home, unsigned int m);
00656     ModEvent cardMax(Space& home, unsigned int m);
00661     ModEvent include(Space& home,int i,int j);
00666     ModEvent exclude(Space& home,int i,int j);
00668     ModEvent include(Space& home,int i);
00670     ModEvent exclude(Space& home,int i);
00675     ModEvent intersect(Space& home,int i,int j);
00677     ModEvent intersect(Space& home,int i);
00679 
00681 
00682 
00684     template<class I> ModEvent excludeI(Space& home, I& i);
00686     template<class I> ModEvent includeI(Space& home, I& i);
00688     template<class I> ModEvent intersectI(Space& home, I& iter);
00690 
00692 
00693 
00694     static void schedule(Space& home, Propagator& p, ModEvent me);
00696     static ModEvent me(const ModEventDelta& med);
00698     static ModEventDelta med(ModEvent);
00700 
00702 
00703 
00710     void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
00712     void cancel(Space& home, Propagator& p, PropCond pc);
00714     void reschedule(Space& home, Propagator& p, PropCond pc);
00716     void subscribe(Space& home, Advisor& a);
00718     void cancel(Space& home, Advisor& a);
00720 
00722 
00723 
00724     static ModEvent modevent(const Delta& d);
00726     int glbMin(const Delta& d) const;
00728     int glbMax(const Delta& d) const;
00730     bool glbAny(const Delta& d) const;
00732     int lubMin(const Delta& d) const;
00734     int lubMax(const Delta& d) const;
00736     bool lubAny(const Delta& d) const;
00738 
00739   };
00740 
00745   template<class Char, class Traits>
00746   std::basic_ostream<Char,Traits>&
00747   operator <<(std::basic_ostream<Char,Traits>& os, const SingletonView& x);
00748 
00753 
00754   bool operator ==(const SingletonView& x, const SingletonView& y);
00756   bool operator !=(const SingletonView& x, const SingletonView& y);
00758 
00768   template<class View>
00769   class ComplementView : public DerivedView<View> {
00770   protected:
00771     using DerivedView<View>::x;
00772 
00773   public:
00775     static PropCond pc_negateset(PropCond pc);
00777     static ModEvent me_negateset(ModEvent me);
00778 
00780 
00781 
00782     ComplementView(void);
00784     explicit ComplementView(View& y);
00786 
00788 
00789 
00791     unsigned int cardMin(void) const;
00793     unsigned int cardMax(void) const;
00795     int lubMin(void) const;
00797     int lubMax(void) const;
00799     int lubMinN(unsigned int n) const;
00801     int glbMin(void) const;
00803     int glbMax(void) const;
00804 
00806     unsigned int glbSize(void) const;
00808     unsigned int lubSize(void) const;
00810     unsigned int unknownSize(void) const;
00812 
00814 
00815 
00816     bool contains(int i) const;
00818     bool notContains(int i) const;
00820 
00821 
00823 
00824 
00825     ModEvent cardMin(Space& home, unsigned int m);
00827     ModEvent cardMax(Space& home, unsigned int m);
00832     ModEvent include(Space& home,int i,int j);
00837     ModEvent exclude(Space& home,int i,int j);
00839     ModEvent include(Space& home,int i);
00841     ModEvent exclude(Space& home,int i);
00846     ModEvent intersect(Space& home,int i,int j);
00848     ModEvent intersect(Space& home,int i);
00850 
00852 
00853 
00855     template<class I> ModEvent excludeI(Space& home, I& i);
00857     template<class I> ModEvent includeI(Space& home, I& i);
00859     template<class I> ModEvent intersectI(Space& home, I& iter);
00861 
00863 
00864 
00865     static void schedule(Space& home, Propagator& p, ModEvent me);
00867     static ModEvent me(const ModEventDelta& med);
00869     static ModEventDelta med(ModEvent);
00871 
00873 
00874 
00881     void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
00883     void cancel(Space& home, Propagator& p, PropCond pc);
00885     void subscribe(Space& home, Advisor& a);
00887     void cancel(Space& home, Advisor& a);
00889 
00891 
00892 
00893     static ModEvent modevent(const Delta& d);
00895     int glbMin(const Delta& d) const;
00897     int glbMax(const Delta& d) const;
00899     bool glbAny(const Delta& d) const;
00901     int lubMin(const Delta& d) const;
00903     int lubMax(const Delta& d) const;
00905     bool lubAny(const Delta& d) const;
00907 
00908   };
00909 
00914   template<class Char, class Traits, class View>
00915   std::basic_ostream<Char,Traits>&
00916   operator <<(std::basic_ostream<Char,Traits>& os,
00917               const ComplementView<View>& x);
00918 
00923 
00924   template<class View>
00925   bool operator ==(const ComplementView<View>& x,
00926                    const ComplementView<View>& y);
00928   template<class View>
00929   bool operator !=(const ComplementView<View>& x,
00930                    const ComplementView<View>& y);
00932 
00933   template<class View> class LubDiffRanges;
00934   template<class View> class GlbDiffRanges;
00935 
00947   template<class View>
00948   class CachedView : public DerivedView<View> {
00949     friend class LubDiffRanges<View>;
00950     friend class GlbDiffRanges<View>;
00951   protected:
00952     using DerivedView<View>::x;
00953 
00955     LUBndSet lubCache;
00957     GLBndSet glbCache;
00958 
00959   public:
00960 
00962 
00963 
00964     CachedView(void);
00966     explicit CachedView(const View& y);
00968 
00970 
00971 
00973     unsigned int cardMin(void) const;
00975     unsigned int cardMax(void) const;
00977     int lubMin(void) const;
00979     int lubMax(void) const;
00981     int lubMinN(unsigned int n) const;
00983     int glbMin(void) const;
00985     int glbMax(void) const;
00986 
00988     unsigned int glbSize(void) const;
00990     unsigned int lubSize(void) const;
00992     unsigned int unknownSize(void) const;
00994 
00996 
00997 
00998     bool contains(int i) const;
01000     bool notContains(int i) const;
01002 
01003 
01005 
01006 
01007     ModEvent cardMin(Space& home, unsigned int m);
01009     ModEvent cardMax(Space& home, unsigned int m);
01014     ModEvent include(Space& home,int i,int j);
01019     ModEvent exclude(Space& home,int i,int j);
01021     ModEvent include(Space& home,int i);
01023     ModEvent exclude(Space& home,int i);
01028     ModEvent intersect(Space& home,int i,int j);
01030     ModEvent intersect(Space& home,int i);
01032 
01034 
01035 
01037     template<class I> ModEvent excludeI(Space& home, I& i);
01039     template<class I> ModEvent includeI(Space& home, I& i);
01041     template<class I> ModEvent intersectI(Space& home, I& iter);
01043 
01045 
01046 
01047     static void schedule(Space& home, Propagator& p, ModEvent me);
01049     static ModEvent me(const ModEventDelta& med);
01051     static ModEventDelta med(ModEvent);
01053 
01055 
01056 
01063     void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
01065     void cancel(Space& home, Propagator& p, PropCond pc);
01067     void subscribe(Space& home, Advisor& a);
01069     void cancel(Space& home, Advisor& a);
01071 
01073 
01074 
01075     static ModEvent modevent(const Delta& d);
01077     int glbMin(const Delta& d) const;
01079     int glbMax(const Delta& d) const;
01081     bool glbAny(const Delta& d) const;
01083     int lubMin(const Delta& d) const;
01085     int lubMax(const Delta& d) const;
01087     bool lubAny(const Delta& d) const;
01089 
01091 
01092 
01093     void initCache(Space& home, const IntSet& glb, const IntSet& lub);
01095     void cacheGlb(Space& home);
01097     void cacheLub(Space& home);
01099     bool glbModified(void) const;
01101     bool lubModified(void) const;
01103 
01105 
01106 
01107     void update(Space& home, CachedView<View>& y);
01109   };
01110 
01115   template<class Char, class Traits, class View>
01116   std::basic_ostream<Char,Traits>&
01117   operator <<(std::basic_ostream<Char,Traits>& os,
01118               const CachedView<View>& x);
01119 
01124 
01125   template<class View>
01126   bool operator ==(const CachedView<View>& x, const CachedView<View>& y);
01128   template<class View>
01129   bool operator !=(const CachedView<View>& x, const CachedView<View>& y);
01131 
01136   template<class View>
01137   class GlbDiffRanges
01138     : public Iter::Ranges::Diff<GlbRanges<View>,BndSetRanges> {
01139   protected:
01141     GlbRanges<View> gr;
01143     BndSetRanges cr;
01144   public:
01146     GlbDiffRanges(const CachedView<View>& x);
01147   };
01148 
01153   template<class View>
01154   class LubDiffRanges
01155     : public Iter::Ranges::Diff<BndSetRanges,LubRanges<View> > {
01156   protected:
01158     BndSetRanges cr;
01160     LubRanges<View> lr;
01161   public:
01163     LubDiffRanges(const CachedView<View>& x);
01164   };
01165 
01166 }}
01167 
01168 #include <gecode/set/var/set.hpp>
01169 
01170 #include <gecode/set/view/set.hpp>
01171 
01172 #include <gecode/set/view/const.hpp>
01173 #include <gecode/set/view/singleton.hpp>
01174 #include <gecode/set/view/complement.hpp>
01175 #include <gecode/set/view/cached.hpp>
01176 
01177 #include <gecode/set/view/print.hpp>
01178 #include <gecode/set/var/print.hpp>
01179 
01180 // STATISTICS: set-var