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 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
00508