Generated on Mon May 10 06:46:37 2010 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  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00005  *     Christian Schulte <schulte@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Mikael Lagerkvist, 2007
00009  *     Christian Schulte, 2004
00010  *
00011  *  Last modified:
00012  *     $Date: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $
00013  *     $Revision: 10684 $
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 #ifndef __GECODE_INT_EXTENSIONAL_HH__
00041 #define __GECODE_INT_EXTENSIONAL_HH__
00042 
00043 #include <gecode/int.hh>
00044 
00045 #include <gecode/int/rel.hh>
00046 
00052 namespace Gecode { namespace Int { namespace Extensional {
00053 
00068   template<class View, class Val, class Degree, class StateIdx>
00069   class LayeredGraph : public Propagator {
00070   protected:
00072     class State {
00073     public:
00074       Degree i_deg; 
00075       Degree o_deg; 
00076 
00077       void init(void);
00078     };
00080     class Edge {
00081     public:
00082       StateIdx i_state; 
00083       StateIdx o_state; 
00084     };
00086     class Support {
00087     public:
00088       Val val; 
00089       Degree n_edges; 
00090       Edge* edges; 
00091     };
00093     typedef typename Gecode::Support::IntTypeTraits<Val>::utype ValSize;
00095     class Layer {
00096     public:
00097       View x; 
00098       StateIdx n_states; 
00099       ValSize size; 
00100       State* states; 
00101       Support* support; 
00102     };
00104     class LayerValues {
00105     private:
00106       const Support* s1; 
00107       const Support* s2; 
00108     public:
00110       LayerValues(void);
00112       LayerValues(const Layer& l);
00114       void init(const Layer& l);
00116       bool operator ()(void) const;
00118       void operator ++(void);
00120       int val(void) const;
00121     };
00123     class Index : public Advisor {
00124     public:
00126       int i;
00128       Index(Space& home, Propagator& p, Council<Index>& c, int i);
00130       Index(Space& home, bool share, Index& a);
00131     };
00133     class IndexRange {
00134     private:
00135       int _fst; 
00136       int _lst; 
00137     public:
00139       IndexRange(void);
00141       void reset(void);
00143       void add(int i);
00145       void add(const IndexRange& ir);
00147       void lshift(int n);
00149       bool empty(void) const;
00151       int fst(void) const;
00153       int lst(void) const;
00154     };
00156     Council<Index> c;
00158     int n;
00160     Layer* layers;
00162     StateIdx max_states;
00164     unsigned int n_states;
00166     unsigned int n_edges;
00168     IndexRange i_ch;
00170     IndexRange o_ch;
00172     IndexRange a_ch;
00174     State& i_state(int i, StateIdx is);
00176     State& i_state(int i, const Edge& e);
00178     bool i_dec(int i, const Edge& e);
00180     State& o_state(int i, StateIdx os);
00182     State& o_state(int i, const Edge& e);
00184     bool o_dec(int i, const Edge& e);
00186     void audit(void);
00188     template<class Var>
00189     ExecStatus initialize(Space& home, 
00190                           const VarArgArray<Var>& x, const DFA& dfa);
00192     LayeredGraph(Space& home, bool share,
00193                  LayeredGraph<View,Val,Degree,StateIdx>& p);
00194   public:
00196     template<class Var>
00197     LayeredGraph(Home home, 
00198                  const VarArgArray<Var>& x, const DFA& dfa);
00200     virtual Actor* copy(Space& home, bool share);
00202     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00204     virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00206     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00208     virtual size_t dispose(Space& home);
00210     template<class Var>
00211     static ExecStatus post(Home home, 
00212                            const VarArgArray<Var>& x, const DFA& dfa);
00213   };
00214 
00216   template<class Var>
00217   ExecStatus post_lgp(Home home, 
00218                       const VarArgArray<Var>& x, const DFA& dfa);
00219 
00220 }}}
00221 
00222 #include <gecode/int/extensional/layered-graph.hpp>
00223 
00224 
00225 namespace Gecode { namespace Int { namespace Extensional {
00226 
00227   typedef TupleSet::Tuple Tuple;
00228   typedef Support::BitSetBase BitSet;
00229   typedef Support::BitSetBase* Domain;
00230 
00241   template<class View, bool subscribe = true>
00242   class Base : public Propagator {
00243   protected:
00244     ViewArray<View> x; 
00245     TupleSet tupleSet; 
00246     Tuple** last_data; 
00247 
00248     TupleSet::TupleSetI* ts(void);
00249 
00251     Base(Space& home, bool share, Base<View,subscribe>& p);
00253     Base(Home home, ViewArray<View>& x, const TupleSet& t);
00255     void init_last(Space& home, Tuple** source);
00257     Tuple last(int i, int n);
00259     Tuple last_next(int i, int n);
00261     void init_dom(Space& home, Domain dom);
00263     bool valid(Tuple t, Domain dom);
00265     Tuple find_support(Domain dom, int i, int n);
00266   public:
00268     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00270     virtual size_t dispose(Space& home);
00271   };
00272 }}}
00273 
00274 #include <gecode/int/extensional/base.hpp>
00275 
00276 
00277 namespace Gecode { namespace Int { namespace Extensional {
00278 
00291   template<class View, bool shared>
00292   class Basic : public Base<View> {
00293   protected:
00294     using Base<View>::x;
00295     using Base<View>::tupleSet;
00296     using Base<View>::ts;
00297     using Base<View>::last;
00298     using Base<View>::last_next;
00299     using Base<View>::init_last;
00300     using Base<View>::init_dom;
00301     using Base<View>::find_support;
00302 
00304     Basic(Space& home, bool share, Basic<View,shared>& p);
00306     Basic(Home home, ViewArray<View>& x, const TupleSet& t);
00307 
00308   public:
00310     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00317     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00319     virtual Actor* copy(Space& home, bool share);
00321     static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& t);
00322   };
00323 
00324 }}}
00325 
00326 #include <gecode/int/extensional/basic.hpp>
00327 
00328 
00329 namespace Gecode { namespace Int { namespace Extensional {
00339   template<class View>
00340   class Incremental : public Base<View, false> {
00341   protected:
00342     using Base<View, false>::x;
00343     using Base<View, false>::tupleSet;
00344     using Base<View, false>::ts;
00345     using Base<View, false>::last;
00346     using Base<View, false>::last_next;
00347     using Base<View, false>::init_last;
00348     using Base<View, false>::init_dom;
00350     class SupportEntry : public FreeList {
00351     public:
00353       Tuple t;
00354 
00356 
00357 
00358       SupportEntry* next(void) const;
00360       SupportEntry** nextRef(void);
00362 
00364 
00365 
00366       SupportEntry(Tuple t);
00368       SupportEntry(Tuple t, SupportEntry* n);
00370 
00372 
00373 
00374       void dispose(Space& home, SupportEntry* l);
00376       void dispose(Space& home);
00377 
00379       static void* operator new(size_t s, Space& home);
00381       static void operator delete(void* p);
00383       static void operator delete(void* p, Space& home);
00385     };
00387     class WorkEntry : public FreeList {
00388     public:
00390       int i;
00392       int n;
00393 
00395 
00396 
00397       WorkEntry(int i, int n, WorkEntry* ne);
00399 
00401 
00402 
00403       WorkEntry* next(void) const;
00405       void next(WorkEntry* n);
00407 
00409 
00410 
00411       void dispose(Space& home);
00412 
00414       static void* operator new(size_t s, Space& home);
00416       static void operator delete(void* p);
00418       static void operator delete(void* p, Space& home);
00420     };
00422     class Work {
00423     private:
00425       WorkEntry* we;
00426     public:
00428       Work(void);
00430       bool empty(void) const;
00432       void push(Space& home, int i, int n);
00434       void pop(Space& home, int& i, int& n);
00435     };
00437     Work w_support;
00439     Work w_remove;
00440 
00442     SupportEntry** support_data;
00444     int unassigned;
00445 
00447     Incremental(Space& home, bool share, Incremental<View>& p);
00449     Incremental(Home home, ViewArray<View>& x, const TupleSet& t);
00451     void init_support(Space& home);
00453     void find_support(Space& home, Domain dom, int i, int n);
00455     void add_support(Space& home, Tuple l);
00457     void remove_support(Space& home, Tuple l, int i, int n);
00459     SupportEntry* support(int i, int n);
00460   public:
00462     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00469     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00471     virtual Actor* copy(Space& home, bool share);
00473     static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& t);
00475     size_t dispose(Space& home);
00476   private:
00478     class SupportAdvisor : public Advisor {
00479     public:
00481       int i;
00483       SupportAdvisor(Space& home, Propagator& p, Council<SupportAdvisor>& c,
00484                      int i);
00486       SupportAdvisor(Space& home, bool share, SupportAdvisor& a);
00488       void dispose(Space& home, Council<SupportAdvisor>& c);
00489     };
00491     Council<SupportAdvisor> ac;
00492   public:
00494     virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00495   };
00496 
00497 }}}
00498 
00499 #include <gecode/int/extensional/incremental.hpp>
00500 
00501 
00502 #endif
00503 
00504 // STATISTICS: int-prop
00505