00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
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
00505