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