Generated on Fri Oct 19 11:25:05 2018 for Gecode by doxygen 1.6.3

extensional.hh

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Linnea Ingmar <linnea.ingmar@hotmail.com>
00005  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00006  *     Christian Schulte <schulte@gecode.org>
00007  *
00008  *  Copyright:
00009  *     Linnea Ingmar, 2017
00010  *     Mikael Lagerkvist, 2007
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 #ifndef __GECODE_INT_EXTENSIONAL_HH__
00039 #define __GECODE_INT_EXTENSIONAL_HH__
00040 
00041 #include <gecode/int.hh>
00042 
00043 #include <gecode/int/rel.hh>
00044 
00050 namespace Gecode { namespace Int { namespace Extensional {
00051 
00066   template<class View, class Val, class Degree, class StateIdx>
00067   class LayeredGraph : public Propagator {
00068   protected:
00070     class State {
00071     public:
00072       Degree i_deg; 
00073       Degree o_deg; 
00074 
00075       void init(void);
00076     };
00078     class Edge {
00079     public:
00080       StateIdx i_state; 
00081       StateIdx o_state; 
00082     };
00084     class Support {
00085     public:
00086       Val val; 
00087       Degree n_edges; 
00088       Edge* edges; 
00089     };
00091     typedef typename Gecode::Support::IntTypeTraits<Val>::utype ValSize;
00093     class Layer {
00094     public:
00095       View x; 
00096       StateIdx n_states; 
00097       ValSize size; 
00098       State* states; 
00099       Support* support; 
00100     };
00102     class LayerValues {
00103     private:
00104       const Support* s1; 
00105       const Support* s2; 
00106     public:
00108       LayerValues(void);
00110       LayerValues(const Layer& l);
00112       void init(const Layer& l);
00114       bool operator ()(void) const;
00116       void operator ++(void);
00118       int val(void) const;
00119     };
00121     class Index : public Advisor {
00122     public:
00124       int i;
00126       Index(Space& home, Propagator& p, Council<Index>& c, int i);
00128       Index(Space& home, Index& a);
00129     };
00131     class IndexRange {
00132     private:
00133       int _fst; 
00134       int _lst; 
00135     public:
00137       IndexRange(void);
00139       void reset(void);
00141       void add(int i);
00143       void add(const IndexRange& ir);
00145       void lshift(int n);
00147       bool empty(void) const;
00149       int fst(void) const;
00151       int lst(void) const;
00152     };
00154     Council<Index> c;
00156     int n;
00158     Layer* layers;
00160     StateIdx max_states;
00162     unsigned int n_states;
00164     unsigned int n_edges;
00166     IndexRange i_ch;
00168     IndexRange o_ch;
00170     IndexRange a_ch;
00172     State& i_state(int i, StateIdx is);
00174     State& i_state(int i, const Edge& e);
00176     bool i_dec(int i, const Edge& e);
00178     State& o_state(int i, StateIdx os);
00180     State& o_state(int i, const Edge& e);
00182     bool o_dec(int i, const Edge& e);
00184     void audit(void);
00186     template<class Var>
00187     ExecStatus initialize(Space& home,
00188                           const VarArgArray<Var>& x, const DFA& dfa);
00190     LayeredGraph(Space& home, LayeredGraph<View,Val,Degree,StateIdx>& p);
00191   public:
00193     template<class Var>
00194     LayeredGraph(Home home,
00195                  const VarArgArray<Var>& x, const DFA& dfa);
00197     virtual Actor* copy(Space& home);
00199     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00201     virtual void reschedule(Space& home);
00203     virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00205     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00207     virtual size_t dispose(Space& home);
00209     template<class Var>
00210     static ExecStatus post(Home home,
00211                            const VarArgArray<Var>& x, const DFA& dfa);
00212   };
00213 
00215   template<class Var>
00216   ExecStatus post_lgp(Home home,
00217                       const VarArgArray<Var>& x, const DFA& dfa);
00218 
00219 }}}
00220 
00221 #include <gecode/int/extensional/layered-graph.hpp>
00222 
00223 namespace Gecode { namespace Int { namespace Extensional {
00224 
00226   typedef Gecode::Support::BitSetData BitSetData;
00227 
00228   /*
00229    * Forward declarations
00230    */
00231   template<unsigned int size> class TinyBitSet;
00232 
00234   template<class IndexType>
00235   class BitSet {
00236     template<class> friend class BitSet;
00237     template<unsigned int> friend class TinyBitSet;
00238   protected:
00240     IndexType _limit;
00242     IndexType* _index;
00244     BitSetData* _bits;
00246     void replace_and_decrease(IndexType i, BitSetData w);
00247   public:
00249     BitSet(Space& home, unsigned int n);
00251     template<class OldIndexType>
00252     BitSet(Space& home, const BitSet<OldIndexType>& bs);
00254     BitSet(Space& home, const TinyBitSet<1U>& tbs);
00256     BitSet(Space& home, const TinyBitSet<2U>& tbs);
00258     BitSet(Space& home, const TinyBitSet<3U>& tbs);
00260     BitSet(Space& home, const TinyBitSet<4U>& tbs);
00262     unsigned int limit(void) const;
00264     bool empty(void) const;
00266     void flush(void);
00268     unsigned int width(void) const;
00270     void clear_mask(BitSetData* mask) const;
00272     void add_to_mask(const BitSetData* b, BitSetData* mask) const;
00274     template<bool sparse>
00275     void intersect_with_mask(const BitSetData* mask);
00277     void intersect_with_masks(const BitSetData* a, const BitSetData* b);
00279     bool intersects(const BitSetData* b) const;
00281     void nand_with_mask(const BitSetData* b);
00283     unsigned long long int ones(void) const;
00285     unsigned long long int ones(const BitSetData* b) const;
00287     unsigned long long int bits(void) const;
00289     unsigned int words(void) const;
00291     unsigned int size(void) const;
00292   };
00293 
00294 }}}
00295 
00296 #include <gecode/int/extensional/bit-set.hpp>
00297 
00298 namespace Gecode { namespace Int { namespace Extensional {
00299 
00301   template<unsigned int _size>
00302   class TinyBitSet {
00303     template<unsigned int> friend class TinyBitSet;
00304   protected:
00306     BitSetData _bits[_size];
00307   public:
00309     TinyBitSet(Space& home, unsigned int n);
00311     template<unsigned int largersize>
00312     TinyBitSet(Space& home, const TinyBitSet<largersize>& tbs);
00314     template<class IndexType>
00315     TinyBitSet(Space& home, const BitSet<IndexType>& bs);
00317     int limit(void) const;
00319     bool empty(void) const;
00321     void flush(void);
00323     unsigned int width(void) const;
00325     void clear_mask(BitSetData* mask);
00327     void add_to_mask(const BitSetData* b, BitSetData* mask) const;
00329     template<bool sparse>
00330     void intersect_with_mask(const BitSetData* mask);
00332     void intersect_with_masks(const BitSetData* a, const BitSetData* b);
00334     bool intersects(const BitSetData* b);
00336     void nand_with_mask(const BitSetData* b);
00338     void nand_with_masks(const BitSetData* a, const BitSetData* b);
00340     unsigned long long int ones(void) const;
00342     unsigned long long int ones(const BitSetData* b) const;
00344     unsigned long long int bits(void) const;
00346     unsigned int words(void) const;
00348     unsigned int size(void) const;
00349   };
00350       
00351 }}}
00352 
00353 #include <gecode/int/extensional/tiny-bit-set.hpp>
00354 
00355 namespace Gecode { namespace Int { namespace Extensional {
00356 
00358   typedef TupleSet::Tuple Tuple;
00359 
00361   template<class View, bool pos>
00362   class Compact : public Propagator {
00363   protected:
00365     typedef TupleSet::Range Range;
00367     class CTAdvisor : public ViewAdvisor<View> {
00368     public:
00369       using ViewAdvisor<View>::view;
00370     protected:
00372       const Range* _fst;
00374       const Range* _lst;
00375     public:
00377 
00378 
00379       CTAdvisor(Space& home, Propagator& p, Council<CTAdvisor>& c,
00380                 const TupleSet& ts, View x0, int i);
00382       CTAdvisor(Space& home, CTAdvisor& a);
00384 
00385       void adjust(void);
00387       const Range* fst(void) const;
00389       const Range* lst(void) const;
00391       void dispose(Space& home, Council<CTAdvisor>& c);
00392     };
00394 
00395 
00396 
00397     class ValidSupports {
00398     protected:
00400       const unsigned int n_words;
00402       int max;
00404       ViewRanges<View> xr;
00406       const Range* sr;
00408       const Range* lst;
00410       int n;
00412       const BitSetData* s;
00414       void find(void);
00415     public:
00417       ValidSupports(const Compact<View,pos>& p, CTAdvisor& a);
00419       ValidSupports(const TupleSet& ts, int i, View x);
00421       void operator ++(void);
00423       bool operator ()(void) const;
00425       const BitSetData* supports(void) const;
00427       int val(void) const;
00428     };
00430     class LostSupports {
00431     protected:
00433       const unsigned int n_words;
00435       const Range* r;
00437       const Range* lst;
00439       int l;
00441       int h;
00443       const BitSetData* s;
00444     public:
00446       LostSupports(const Compact<View,pos>& p, CTAdvisor& a,
00447                    int l, int h);
00449       void operator ++(void);
00451       bool operator ()(void) const;
00453       const BitSetData* supports(void) const;
00454     };
00456 
00457 
00458 
00459     bool all(void) const;
00461     bool atmostone(void) const;
00463   protected:
00465     const unsigned int n_words;
00467     TupleSet ts;
00469     Council<CTAdvisor> c;
00471     Compact(Space& home, Compact& p);
00473     Compact(Home home, const TupleSet& ts);
00475     template<class Table>
00476     void setup(Space& home, Table& table, ViewArray<View>& x);
00478     template<class Table>
00479     bool full(const Table& table) const;
00481     const Range* range(CTAdvisor& a, int n);
00483     const BitSetData* supports(CTAdvisor& a, int n);
00484   public:
00486     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00488     size_t dispose(Space& home);
00489   };
00490 
00503   template<class View, class Table>
00504   class PosCompact : public Compact<View,true> {
00505   public:
00506     typedef typename Compact<View,true>::ValidSupports ValidSupports;
00507     typedef typename Compact<View,true>::Range Range;
00508     typedef typename Compact<View,true>::CTAdvisor CTAdvisor;
00509     typedef typename Compact<View,true>::LostSupports LostSupports;
00510 
00511     using Compact<View,true>::setup;
00512     using Compact<View,true>::supports;
00513     using Compact<View,true>::all;
00514     using Compact<View,true>::atmostone;
00515     using Compact<View,true>::c;
00516     using Compact<View,true>::ts;
00517 
00519 
00520 
00521     enum StatusType {
00522       SINGLE      = 0, 
00523       MULTIPLE    = 1, 
00524       NONE        = 2, 
00525       PROPAGATING = 3  
00526     };
00528     class Status {
00529     protected:
00531       ptrdiff_t s;
00532     public:
00534       Status(StatusType t);
00536       Status(const Status& s);
00538       StatusType type(void) const;
00540       bool single(CTAdvisor& a) const;
00542       void touched(CTAdvisor& a);
00544       void none(void);
00546       void propagating(void);
00547     };
00549     Status status;
00551     Table table;
00553     bool empty(void) const;
00555     template<class TableProp>
00556     PosCompact(Space& home, TableProp& p);
00558     PosCompact(Home home, ViewArray<View>& x, const TupleSet& ts);
00559   public:
00561     virtual void reschedule(Space& home);
00563     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00565     virtual Actor* copy(Space& home);
00567     static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& ts);
00569     size_t dispose(Space& home);
00571     virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00572   };
00573 
00575   template<class View>
00576   ExecStatus postposcompact(Home home, ViewArray<View>& x, const TupleSet& ts);
00577 
00593   template<class View, class Table>
00594   class NegCompact : public Compact<View,false> {
00595   public:
00596     typedef typename Compact<View,false>::ValidSupports ValidSupports;
00597     typedef typename Compact<View,false>::Range Range;
00598     typedef typename Compact<View,false>::CTAdvisor CTAdvisor;
00599 
00600     using Compact<View,false>::setup;
00601     using Compact<View,false>::full;
00602     using Compact<View,false>::supports;
00603     using Compact<View,false>::atmostone;
00604     using Compact<View,false>::c;
00605     using Compact<View,false>::ts;
00606 
00608     Table table;
00610     template<class TableProp>
00611     NegCompact(Space& home, TableProp& p);
00613     NegCompact(Home home, ViewArray<View>& x, const TupleSet& ts);
00614   public:
00616     virtual void reschedule(Space& home);
00618     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00620     virtual Actor* copy(Space& home);
00622     static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& ts);
00624     size_t dispose(Space& home);
00626     virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00627   };
00628 
00630   template<class View>
00631   ExecStatus postnegcompact(Home home, ViewArray<View>& x, const TupleSet& ts);
00632 
00633 
00635   template<class View, class Table, class CtrlView, ReifyMode rm>
00636   class ReCompact : public Compact<View,false> {
00637   public:
00638     typedef typename Compact<View,false>::ValidSupports ValidSupports;
00639     typedef typename Compact<View,false>::Range Range;
00640     typedef typename Compact<View,false>::CTAdvisor CTAdvisor;
00641 
00642     using Compact<View,false>::setup;
00643     using Compact<View,false>::full;
00644     using Compact<View,false>::supports;
00645     using Compact<View,false>::c;
00646     using Compact<View,false>::ts;
00647 
00649     Table table;
00651     CtrlView b;
00653     ViewArray<View> y;
00655     template<class TableProp>
00656     ReCompact(Space& home, TableProp& p);
00658     ReCompact(Home home, ViewArray<View>& x, const TupleSet& ts, CtrlView b);
00659   public:
00661     virtual void reschedule(Space& home);
00663     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00665     virtual Actor* copy(Space& home);
00667     static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& ts,
00668                            CtrlView b);
00670     size_t dispose(Space& home);
00672     virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00673   };
00674 
00676   template<class View, class CtrlView, ReifyMode rm>
00677   ExecStatus postrecompact(Home home, ViewArray<View>& x, const TupleSet& ts,
00678                            CtrlView b);
00679 
00680 }}}
00681 
00682 #include <gecode/int/extensional/compact.hpp>
00683 
00684 #endif
00685 
00686 // STATISTICS: int-prop