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 void reschedule(Space& home);
00206 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00208 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00210 virtual size_t dispose(Space& home);
00212 template<class Var>
00213 static ExecStatus post(Home home,
00214 const VarArgArray<Var>& x, const DFA& dfa);
00215 };
00216
00218 template<class Var>
00219 ExecStatus post_lgp(Home home,
00220 const VarArgArray<Var>& x, const DFA& dfa);
00221
00222 }}}
00223
00224 #include <gecode/int/extensional/layered-graph.hpp>
00225
00226
00227 namespace Gecode { namespace Int { namespace Extensional {
00228
00229 typedef TupleSet::Tuple Tuple;
00230 typedef Support::BitSetBase BitSet;
00231 typedef Support::BitSetBase* Domain;
00232
00243 template<class View, bool subscribe = true>
00244 class Base : public Propagator {
00245 protected:
00246 ViewArray<View> x;
00247 TupleSet tupleSet;
00248 Tuple** last_data;
00249
00250 TupleSet::TupleSetI* ts(void);
00251
00253 Base(Space& home, bool share, Base<View,subscribe>& p);
00255 Base(Home home, ViewArray<View>& x, const TupleSet& t);
00257 void init_last(Space& home, Tuple** source, Tuple* base);
00259 Tuple last(int i, int n);
00261 Tuple last_next(int i, int n);
00263 void init_dom(Space& home, Domain dom);
00265 bool valid(Tuple t, Domain dom);
00267 Tuple find_support(Domain dom, int i, int n);
00268 public:
00270 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00272 virtual void reschedule(Space& home);
00274 virtual size_t dispose(Space& home);
00275 };
00276
00277 }}}
00278
00279 #include <gecode/int/extensional/base.hpp>
00280
00281
00282 namespace Gecode { namespace Int { namespace Extensional {
00283
00296 template<class View, bool shared>
00297 class Basic : public Base<View> {
00298 protected:
00299 using Base<View>::x;
00300 using Base<View>::tupleSet;
00301 using Base<View>::ts;
00302 using Base<View>::last;
00303 using Base<View>::last_next;
00304 using Base<View>::init_last;
00305 using Base<View>::init_dom;
00306 using Base<View>::find_support;
00307
00309 Basic(Space& home, bool share, Basic<View,shared>& p);
00311 Basic(Home home, ViewArray<View>& x, const TupleSet& t);
00312
00313 public:
00315 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00322 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00324 virtual Actor* copy(Space& home, bool share);
00326 static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& t);
00327 };
00328
00329 }}}
00330
00331 #include <gecode/int/extensional/basic.hpp>
00332
00333
00334 namespace Gecode { namespace Int { namespace Extensional {
00344 template<class View>
00345 class Incremental : public Base<View, false> {
00346 protected:
00347 using Base<View, false>::x;
00348 using Base<View, false>::tupleSet;
00349 using Base<View, false>::ts;
00350 using Base<View, false>::last;
00351 using Base<View, false>::last_next;
00352 using Base<View, false>::init_last;
00353 using Base<View, false>::init_dom;
00355 class SupportEntry : public FreeList {
00356 public:
00358 Tuple t;
00359
00361
00362
00363 SupportEntry* next(void) const;
00365 SupportEntry** nextRef(void);
00367
00369
00370
00371 SupportEntry(Tuple t);
00373 SupportEntry(Tuple t, SupportEntry* n);
00375
00377
00378
00379 void dispose(Space& home, SupportEntry* l);
00381 void dispose(Space& home);
00382
00384 static void* operator new(size_t s, Space& home);
00386 static void operator delete(void* p);
00388 static void operator delete(void* p, Space& home);
00390 };
00392 class WorkEntry : public FreeList {
00393 public:
00395 int i;
00397 int n;
00398
00400
00401
00402 WorkEntry(int i, int n, WorkEntry* ne);
00404
00406
00407
00408 WorkEntry* next(void) const;
00410 void next(WorkEntry* n);
00412
00414
00415
00416 void dispose(Space& home);
00417
00419 static void* operator new(size_t s, Space& home);
00421 static void operator delete(void* p);
00423 static void operator delete(void* p, Space& home);
00425 };
00427 class Work {
00428 private:
00430 WorkEntry* we;
00431 public:
00433 Work(void);
00435 bool empty(void) const;
00437 void push(Space& home, int i, int n);
00439 void pop(Space& home, int& i, int& n);
00440 };
00442 Work w_support;
00444 Work w_remove;
00445
00447 SupportEntry** support_data;
00449 int unassigned;
00450
00452 Incremental(Space& home, bool share, Incremental<View>& p);
00454 Incremental(Home home, ViewArray<View>& x, const TupleSet& t);
00456 void init_support(Space& home);
00458 void find_support(Space& home, Domain dom, int i, int n);
00460 void add_support(Space& home, Tuple l);
00462 void remove_support(Space& home, Tuple l, int i, int n);
00464 SupportEntry* support(int i, int n);
00465 public:
00472 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00474 virtual void reschedule(Space& home);
00476 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00478 virtual Actor* copy(Space& home, bool share);
00480 static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& t);
00482 size_t dispose(Space& home);
00483 private:
00485 class SupportAdvisor : public Advisor {
00486 public:
00488 int i;
00490 SupportAdvisor(Space& home, Propagator& p, Council<SupportAdvisor>& c,
00491 int i);
00493 SupportAdvisor(Space& home, bool share, SupportAdvisor& a);
00495 void dispose(Space& home, Council<SupportAdvisor>& c);
00496 };
00498 Council<SupportAdvisor> ac;
00499 public:
00501 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00502 };
00503
00504 }}}
00505
00506 #include <gecode/int/extensional/incremental.hpp>
00507
00508
00509 #endif
00510
00511
00512