Generated on Mon Nov 30 23:53:26 2009 for Gecode by doxygen 1.6.1

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: 2009-10-12 17:36:53 +0200 (Mon, 12 Oct 2009) $ by $Author: schulte $
00013  *     $Revision: 9878 $
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       State(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     class Layer {
00094     public:
00095       View x; 
00096       unsigned int size; 
00097       Support* support; 
00098     };
00100     class LayerValues {
00101     private:
00102       const Support* s1; 
00103       const Support* s2; 
00104     public:
00106       LayerValues(void);
00108       LayerValues(const Layer& l);
00110       void init(const Layer& l);
00112       bool operator ()(void) const;
00114       void operator ++(void);
00116       int val(void) const;
00117     };
00119     class Index : public Advisor {
00120     public:
00122       StateIdx i;
00124       Index(Space& home, Propagator& p, Council<Index>& c, StateIdx i);
00126       Index(Space& home, bool share, Index& a);
00127     };
00129     class IndexRange {
00130     private:
00131       int _fst; 
00132       int _lst; 
00133     public:
00135       IndexRange(void);
00137       void reset(void);
00139       void add(int i);
00141       int fst(void) const;
00143       int lst(void) const;
00144     };
00146     Council<Index> c;
00148     int n;
00150     const int n_states;
00152     Layer* layers;
00154     State* states;
00156     IndexRange i_ch;
00158     IndexRange o_ch;
00159 
00161     template<class Var>
00162     ExecStatus initialize(Space& home, 
00163                           const VarArgArray<Var>& x, const DFA& dfa);
00165     LayeredGraph(Space& home, bool share,
00166                  LayeredGraph<View,Val,Degree,StateIdx>& p);
00167   public:
00169     template<class Var>
00170     LayeredGraph(Home home, 
00171                  const VarArgArray<Var>& x, const DFA& dfa);
00173     virtual Actor* copy(Space& home, bool share);
00175     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00177     virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00179     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00181     virtual size_t dispose(Space& home);
00183     template<class Var>
00184     static ExecStatus post(Home home, 
00185                            const VarArgArray<Var>& x, const DFA& dfa);
00186   };
00187 
00189   template<class Var>
00190   ExecStatus post_lgp(Home home, 
00191                       const VarArgArray<Var>& x, const DFA& dfa);
00192 
00193 }}}
00194 
00195 #include <gecode/int/extensional/layered-graph.hpp>
00196 
00197 
00198 #include <gecode/int/extensional/bitset.hpp>
00199 
00200 namespace Gecode { namespace Int { namespace Extensional {
00201 
00202   typedef TupleSet::Tuple Tuple;
00203   typedef BitSet* Domain;
00204 
00215   template<class View, bool subscribe = true>
00216   class Base : public Propagator {
00217   protected:
00218     ViewArray<View> x; 
00219     TupleSet tupleSet; 
00220     Tuple** last_data; 
00221 
00222     TupleSet::TupleSetI* ts(void);
00223 
00225     Base(Space& home, bool share, Base<View,subscribe>& p);
00227     Base(Home home, ViewArray<View>& x, const TupleSet& t);
00229     void init_last(Space& home, Tuple** source);
00231     Tuple last(int i, int n);
00233     Tuple last_next(int i, int n);
00235     void init_dom(Space& home, Domain dom);
00237     bool valid(Tuple t, Domain dom);
00239     Tuple find_support(Domain dom, int i, int n);
00240   public:
00242     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00244     virtual size_t dispose(Space& home);
00245   };
00246 }}}
00247 
00248 #include <gecode/int/extensional/base.hpp>
00249 
00250 
00251 namespace Gecode { namespace Int { namespace Extensional {
00252 
00265   template<class View, bool shared>
00266   class Basic : public Base<View> {
00267   protected:
00268     using Base<View>::x;
00269     using Base<View>::tupleSet;
00270     using Base<View>::ts;
00271     using Base<View>::last;
00272     using Base<View>::last_next;
00273     using Base<View>::init_last;
00274     using Base<View>::init_dom;
00275     using Base<View>::find_support;
00276 
00278     Basic(Space& home, bool share, Basic<View,shared>& p);
00280     Basic(Home home, ViewArray<View>& x, const TupleSet& t);
00281 
00282   public:
00284     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00291     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00293     virtual Actor* copy(Space& home, bool share);
00295     static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& t);
00296   };
00297 
00298 }}}
00299 
00300 #include <gecode/int/extensional/basic.hpp>
00301 
00302 
00303 namespace Gecode { namespace Int { namespace Extensional {
00313   template<class View>
00314   class Incremental : public Base<View, false> {
00315   protected:
00316     using Base<View, false>::x;
00317     using Base<View, false>::tupleSet;
00318     using Base<View, false>::ts;
00319     using Base<View, false>::last;
00320     using Base<View, false>::last_next;
00321     using Base<View, false>::init_last;
00322     using Base<View, false>::init_dom;
00324     class SupportEntry : public FreeList {
00325     public:
00327       Tuple t;
00328 
00330 
00331 
00332       SupportEntry* next(void) const;
00334       SupportEntry** nextRef(void);
00336 
00338 
00339 
00340       SupportEntry(Tuple t);
00342       SupportEntry(Tuple t, SupportEntry* n);
00344 
00346 
00347 
00348       void dispose(Space& home, SupportEntry* l);
00350       void dispose(Space& home);
00351 
00353       static void* operator new(size_t s, Space& home);
00355       static void operator delete(void* p);
00357       static void operator delete(void* p, Space& home);
00359     };
00361     class WorkEntry : public FreeList {
00362     public:
00364       int i;
00366       int n;
00367 
00369 
00370 
00371       WorkEntry(int i, int n, WorkEntry* ne);
00373 
00375 
00376 
00377       WorkEntry* next(void) const;
00379       void next(WorkEntry* n);
00381 
00383 
00384 
00385       void dispose(Space& home);
00386 
00388       static void* operator new(size_t s, Space& home);
00390       static void operator delete(void* p);
00392       static void operator delete(void* p, Space& home);
00394     };
00396     class Work {
00397     private:
00399       WorkEntry* we;
00400     public:
00402       Work(void);
00404       bool empty(void) const;
00406       void push(Space& home, int i, int n);
00408       void pop(Space& home, int& i, int& n);
00409     };
00411     Work w_support;
00413     Work w_remove;
00414 
00416     SupportEntry** support_data;
00418     int unassigned;
00419 
00421     Incremental(Space& home, bool share, Incremental<View>& p);
00423     Incremental(Home home, ViewArray<View>& x, const TupleSet& t);
00425     void init_support(Space& home);
00427     void find_support(Space& home, Domain dom, int i, int n);
00429     void add_support(Space& home, Tuple l);
00431     void remove_support(Space& home, Tuple l, int i, int n);
00433     SupportEntry* support(int i, int n);
00434   public:
00436     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00443     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00445     virtual Actor* copy(Space& home, bool share);
00447     static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& t);
00449     size_t dispose(Space& home);
00450   private:
00452     class SupportAdvisor : public Advisor {
00453     public:
00455       int i;
00457       SupportAdvisor(Space& home, Propagator& p, Council<SupportAdvisor>& c,
00458                      int i);
00460       SupportAdvisor(Space& home, bool share, SupportAdvisor& a);
00462       void dispose(Space& home, Council<SupportAdvisor>& c);
00463     };
00465     Council<SupportAdvisor> ac;
00466   public:
00468     virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00469   };
00470 
00471 }}}
00472 
00473 #include <gecode/int/extensional/incremental.hpp>
00474 
00475 
00476 #endif
00477 
00478 // STATISTICS: int-prop
00479