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: 2016-09-02 15:36:56 +0200 (Fri, 02 Sep 2016) $ by $Author: schulte $
00015  *     $Revision: 15162 $
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 reschedule(Space& home, Propagator& p, PropCond pc);
00712     void subscribe(Space& home, Advisor& a);
00714     void cancel(Space& home, Advisor& a);
00716 
00718 
00719 
00720     static ModEvent modevent(const Delta& d);
00722     int glbMin(const Delta& d) const;
00724     int glbMax(const Delta& d) const;
00726     bool glbAny(const Delta& d) const;
00728     int lubMin(const Delta& d) const;
00730     int lubMax(const Delta& d) const;
00732     bool lubAny(const Delta& d) const;
00734 
00735   };
00736 
00741   template<class Char, class Traits>
00742   std::basic_ostream<Char,Traits>&
00743   operator <<(std::basic_ostream<Char,Traits>& os, const SingletonView& x);
00744 
00745 
00755   template<class View>
00756   class ComplementView
00757     : public DerivedView<View> {
00758   protected:
00759     using DerivedView<View>::x;
00760 
00761   public:
00763     static PropCond pc_negateset(PropCond pc);
00765     static ModEvent me_negateset(ModEvent me);
00766 
00768 
00769 
00770     ComplementView(void);
00772     explicit ComplementView(View& y);
00774 
00776 
00777 
00779     unsigned int cardMin(void) const;
00781     unsigned int cardMax(void) const;
00783     int lubMin(void) const;
00785     int lubMax(void) const;
00787     int lubMinN(unsigned int n) const;
00789     int glbMin(void) const;
00791     int glbMax(void) const;
00792 
00794     unsigned int glbSize(void) const;
00796     unsigned int lubSize(void) const;
00798     unsigned int unknownSize(void) const;
00800 
00802 
00803 
00804     bool contains(int i) const;
00806     bool notContains(int i) const;
00808 
00809 
00811 
00812 
00813     ModEvent cardMin(Space& home, unsigned int m);
00815     ModEvent cardMax(Space& home, unsigned int m);
00820     ModEvent include(Space& home,int i,int j);
00825     ModEvent exclude(Space& home,int i,int j);
00827     ModEvent include(Space& home,int i);
00829     ModEvent exclude(Space& home,int i);
00834     ModEvent intersect(Space& home,int i,int j);
00836     ModEvent intersect(Space& home,int i);
00838 
00840 
00841 
00843     template<class I> ModEvent excludeI(Space& home, I& i);
00845     template<class I> ModEvent includeI(Space& home, I& i);
00847     template<class I> ModEvent intersectI(Space& home, I& iter);
00849 
00851 
00852 
00853     static void schedule(Space& home, Propagator& p, ModEvent me);
00855     static ModEvent me(const ModEventDelta& med);
00857     static ModEventDelta med(ModEvent);
00859 
00861 
00862 
00869     void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
00871     void cancel(Space& home, Propagator& p, PropCond pc);
00873     void subscribe(Space& home, Advisor& a);
00875     void cancel(Space& home, Advisor& a);
00877 
00879 
00880 
00881     static ModEvent modevent(const Delta& d);
00883     int glbMin(const Delta& d) const;
00885     int glbMax(const Delta& d) const;
00887     bool glbAny(const Delta& d) const;
00889     int lubMin(const Delta& d) const;
00891     int lubMax(const Delta& d) const;
00893     bool lubAny(const Delta& d) const;
00895 
00896   };
00897 
00902   template<class Char, class Traits, class View>
00903   std::basic_ostream<Char,Traits>&
00904   operator <<(std::basic_ostream<Char,Traits>& os,
00905               const ComplementView<View>& x);
00906 
00907 
00908   template<class View> class LubDiffRanges;
00909   template<class View> class GlbDiffRanges;
00910 
00922   template<class View>
00923   class CachedView
00924     : public DerivedView<View> {
00925     friend class LubDiffRanges<View>;
00926     friend class GlbDiffRanges<View>;
00927   protected:
00928     using DerivedView<View>::x;
00929 
00931     LUBndSet lubCache;
00933     GLBndSet glbCache;
00934 
00935   public:
00936 
00938 
00939 
00940     CachedView(void);
00942     explicit CachedView(const View& y);
00944 
00946 
00947 
00949     unsigned int cardMin(void) const;
00951     unsigned int cardMax(void) const;
00953     int lubMin(void) const;
00955     int lubMax(void) const;
00957     int lubMinN(unsigned int n) const;
00959     int glbMin(void) const;
00961     int glbMax(void) const;
00962 
00964     unsigned int glbSize(void) const;
00966     unsigned int lubSize(void) const;
00968     unsigned int unknownSize(void) const;
00970 
00972 
00973 
00974     bool contains(int i) const;
00976     bool notContains(int i) const;
00978 
00979 
00981 
00982 
00983     ModEvent cardMin(Space& home, unsigned int m);
00985     ModEvent cardMax(Space& home, unsigned int m);
00990     ModEvent include(Space& home,int i,int j);
00995     ModEvent exclude(Space& home,int i,int j);
00997     ModEvent include(Space& home,int i);
00999     ModEvent exclude(Space& home,int i);
01004     ModEvent intersect(Space& home,int i,int j);
01006     ModEvent intersect(Space& home,int i);
01008 
01010 
01011 
01013     template<class I> ModEvent excludeI(Space& home, I& i);
01015     template<class I> ModEvent includeI(Space& home, I& i);
01017     template<class I> ModEvent intersectI(Space& home, I& iter);
01019 
01021 
01022 
01023     static void schedule(Space& home, Propagator& p, ModEvent me);
01025     static ModEvent me(const ModEventDelta& med);
01027     static ModEventDelta med(ModEvent);
01029 
01031 
01032 
01039     void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
01041     void cancel(Space& home, Propagator& p, PropCond pc);
01043     void subscribe(Space& home, Advisor& a);
01045     void cancel(Space& home, Advisor& a);
01047 
01049 
01050 
01051     static ModEvent modevent(const Delta& d);
01053     int glbMin(const Delta& d) const;
01055     int glbMax(const Delta& d) const;
01057     bool glbAny(const Delta& d) const;
01059     int lubMin(const Delta& d) const;
01061     int lubMax(const Delta& d) const;
01063     bool lubAny(const Delta& d) const;
01065 
01067 
01068 
01069     void initCache(Space& home, const IntSet& glb, const IntSet& lub);
01071     void cacheGlb(Space& home);
01073     void cacheLub(Space& home);
01075     bool glbModified(void) const;
01077     bool lubModified(void) const;
01079 
01081 
01082 
01083     void update(Space& home, bool share, CachedView<View>& y);
01085   };
01086 
01091   template<class Char, class Traits, class View>
01092   std::basic_ostream<Char,Traits>&
01093   operator <<(std::basic_ostream<Char,Traits>& os,
01094               const CachedView<View>& x);
01095 
01100   template<class View>
01101   class GlbDiffRanges
01102     : public Iter::Ranges::Diff<GlbRanges<View>,BndSetRanges> {
01103   protected:
01105     GlbRanges<View> gr;
01107     BndSetRanges cr;
01108   public:
01110     GlbDiffRanges(const CachedView<View>& x);
01111   };
01112 
01117   template<class View>
01118   class LubDiffRanges
01119     : public Iter::Ranges::Diff<BndSetRanges,LubRanges<View> > {
01120   protected:
01122     BndSetRanges cr;
01124     LubRanges<View> lr;
01125   public:
01127     LubDiffRanges(const CachedView<View>& x);
01128   };
01129 
01130 }}
01131 
01132 #include <gecode/set/var/set.hpp>
01133 
01134 #include <gecode/set/view/set.hpp>
01135 
01136 #include <gecode/set/view/const.hpp>
01137 #include <gecode/set/view/singleton.hpp>
01138 #include <gecode/set/view/complement.hpp>
01139 #include <gecode/set/view/cached.hpp>
01140 
01141 #include <gecode/set/view/print.hpp>
01142 #include <gecode/set/var/print.hpp>
01143 
01144 // STATISTICS: set-var