Generated on Thu Mar 22 10:39:38 2012 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-07-14 17:46:18 +0200 (Wed, 14 Jul 2010) $ by $Author: schulte $
00013  *     $Revision: 11192 $
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   protected:
00273     virtual ~Base(void) {}
00274   };
00275 }}}
00276 
00277 #include <gecode/int/extensional/base.hpp>
00278 
00279 
00280 namespace Gecode { namespace Int { namespace Extensional {
00281 
00294   template<class View, bool shared>
00295   class Basic : public Base<View> {
00296   protected:
00297     using Base<View>::x;
00298     using Base<View>::tupleSet;
00299     using Base<View>::ts;
00300     using Base<View>::last;
00301     using Base<View>::last_next;
00302     using Base<View>::init_last;
00303     using Base<View>::init_dom;
00304     using Base<View>::find_support;
00305 
00307     Basic(Space& home, bool share, Basic<View,shared>& p);
00309     Basic(Home home, ViewArray<View>& x, const TupleSet& t);
00310 
00311   public:
00313     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00320     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00322     virtual Actor* copy(Space& home, bool share);
00324     static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& t);
00325   };
00326 
00327 }}}
00328 
00329 #include <gecode/int/extensional/basic.hpp>
00330 
00331 
00332 namespace Gecode { namespace Int { namespace Extensional {
00342   template<class View>
00343   class Incremental : public Base<View, false> {
00344   protected:
00345     using Base<View, false>::x;
00346     using Base<View, false>::tupleSet;
00347     using Base<View, false>::ts;
00348     using Base<View, false>::last;
00349     using Base<View, false>::last_next;
00350     using Base<View, false>::init_last;
00351     using Base<View, false>::init_dom;
00353     class SupportEntry : public FreeList {
00354     public:
00356       Tuple t;
00357 
00359 
00360 
00361       SupportEntry* next(void) const;
00363       SupportEntry** nextRef(void);
00365 
00367 
00368 
00369       SupportEntry(Tuple t);
00371       SupportEntry(Tuple t, SupportEntry* n);
00373 
00375 
00376 
00377       void dispose(Space& home, SupportEntry* l);
00379       void dispose(Space& home);
00380 
00382       static void* operator new(size_t s, Space& home);
00384       static void operator delete(void* p);
00386       static void operator delete(void* p, Space& home);
00388     };
00390     class WorkEntry : public FreeList {
00391     public:
00393       int i;
00395       int n;
00396 
00398 
00399 
00400       WorkEntry(int i, int n, WorkEntry* ne);
00402 
00404 
00405 
00406       WorkEntry* next(void) const;
00408       void next(WorkEntry* n);
00410 
00412 
00413 
00414       void dispose(Space& home);
00415 
00417       static void* operator new(size_t s, Space& home);
00419       static void operator delete(void* p);
00421       static void operator delete(void* p, Space& home);
00423     };
00425     class Work {
00426     private:
00428       WorkEntry* we;
00429     public:
00431       Work(void);
00433       bool empty(void) const;
00435       void push(Space& home, int i, int n);
00437       void pop(Space& home, int& i, int& n);
00438     };
00440     Work w_support;
00442     Work w_remove;
00443 
00445     SupportEntry** support_data;
00447     int unassigned;
00448 
00450     Incremental(Space& home, bool share, Incremental<View>& p);
00452     Incremental(Home home, ViewArray<View>& x, const TupleSet& t);
00454     void init_support(Space& home);
00456     void find_support(Space& home, Domain dom, int i, int n);
00458     void add_support(Space& home, Tuple l);
00460     void remove_support(Space& home, Tuple l, int i, int n);
00462     SupportEntry* support(int i, int n);
00463   public:
00465     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00472     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00474     virtual Actor* copy(Space& home, bool share);
00476     static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& t);
00478     size_t dispose(Space& home);
00479   private:
00481     class SupportAdvisor : public Advisor {
00482     public:
00484       int i;
00486       SupportAdvisor(Space& home, Propagator& p, Council<SupportAdvisor>& c,
00487                      int i);
00489       SupportAdvisor(Space& home, bool share, SupportAdvisor& a);
00491       void dispose(Space& home, Council<SupportAdvisor>& c);
00492     };
00494     Council<SupportAdvisor> ac;
00495   public:
00497     virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00498   };
00499 
00500 }}}
00501 
00502 #include <gecode/int/extensional/incremental.hpp>
00503 
00504 
00505 #endif
00506 
00507 // STATISTICS: int-prop
00508