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 #ifndef __GECODE_INT_EXTENSIONAL_HH__
00039 #define __GECODE_INT_EXTENSIONAL_HH__
00040
00041 #include <gecode/int.hh>
00042
00043 #include <gecode/int/rel.hh>
00044
00050 namespace Gecode { namespace Int { namespace Extensional {
00051
00066 template<class View, class Val, class Degree, class StateIdx>
00067 class LayeredGraph : public Propagator {
00068 protected:
00070 class State {
00071 public:
00072 Degree i_deg;
00073 Degree o_deg;
00074
00075 void init(void);
00076 };
00078 class Edge {
00079 public:
00080 StateIdx i_state;
00081 StateIdx o_state;
00082 };
00084 class Support {
00085 public:
00086 Val val;
00087 Degree n_edges;
00088 Edge* edges;
00089 };
00091 typedef typename Gecode::Support::IntTypeTraits<Val>::utype ValSize;
00093 class Layer {
00094 public:
00095 View x;
00096 StateIdx n_states;
00097 ValSize size;
00098 State* states;
00099 Support* support;
00100 };
00102 class LayerValues {
00103 private:
00104 const Support* s1;
00105 const Support* s2;
00106 public:
00108 LayerValues(void);
00110 LayerValues(const Layer& l);
00112 void init(const Layer& l);
00114 bool operator ()(void) const;
00116 void operator ++(void);
00118 int val(void) const;
00119 };
00121 class Index : public Advisor {
00122 public:
00124 int i;
00126 Index(Space& home, Propagator& p, Council<Index>& c, int i);
00128 Index(Space& home, Index& a);
00129 };
00131 class IndexRange {
00132 private:
00133 int _fst;
00134 int _lst;
00135 public:
00137 IndexRange(void);
00139 void reset(void);
00141 void add(int i);
00143 void add(const IndexRange& ir);
00145 void lshift(int n);
00147 bool empty(void) const;
00149 int fst(void) const;
00151 int lst(void) const;
00152 };
00154 Council<Index> c;
00156 int n;
00158 Layer* layers;
00160 StateIdx max_states;
00162 unsigned int n_states;
00164 unsigned int n_edges;
00166 IndexRange i_ch;
00168 IndexRange o_ch;
00170 IndexRange a_ch;
00172 State& i_state(int i, StateIdx is);
00174 State& i_state(int i, const Edge& e);
00176 bool i_dec(int i, const Edge& e);
00178 State& o_state(int i, StateIdx os);
00180 State& o_state(int i, const Edge& e);
00182 bool o_dec(int i, const Edge& e);
00184 void audit(void);
00186 template<class Var>
00187 ExecStatus initialize(Space& home,
00188 const VarArgArray<Var>& x, const DFA& dfa);
00190 LayeredGraph(Space& home, LayeredGraph<View,Val,Degree,StateIdx>& p);
00191 public:
00193 template<class Var>
00194 LayeredGraph(Home home,
00195 const VarArgArray<Var>& x, const DFA& dfa);
00197 virtual Actor* copy(Space& home);
00199 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00201 virtual void reschedule(Space& home);
00203 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00205 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00207 virtual size_t dispose(Space& home);
00209 template<class Var>
00210 static ExecStatus post(Home home,
00211 const VarArgArray<Var>& x, const DFA& dfa);
00212 };
00213
00215 template<class Var>
00216 ExecStatus post_lgp(Home home,
00217 const VarArgArray<Var>& x, const DFA& dfa);
00218
00219 }}}
00220
00221 #include <gecode/int/extensional/layered-graph.hpp>
00222
00223
00224 namespace Gecode { namespace Int { namespace Extensional {
00225
00227 typedef Gecode::Support::BitSetData BitSetData;
00228
00229
00230
00231
00232 template<unsigned int size> class TinyBitSet;
00233
00235 template<class IndexType>
00236 class BitSet {
00237 template<class> friend class BitSet;
00238 template<unsigned int> friend class TinyBitSet;
00239 protected:
00241 IndexType _limit;
00243 IndexType* index;
00245 BitSetData* bits;
00247 void replace_and_decrease(IndexType i, BitSetData w);
00248 public:
00250 BitSet(Space& home, unsigned int n);
00252 template<class OldIndexType>
00253 BitSet(Space& home, const BitSet<OldIndexType>& bs);
00255 BitSet(Space& home, const TinyBitSet<1U>& tbs);
00257 BitSet(Space& home, const TinyBitSet<2U>& tbs);
00259 BitSet(Space& home, const TinyBitSet<3U>& tbs);
00261 BitSet(Space& home, const TinyBitSet<4U>& tbs);
00263 unsigned int limit(void) const;
00265 bool empty(void) const;
00267 unsigned int width(void) const;
00269 void clear_mask(BitSetData* mask) const;
00271 void add_to_mask(const BitSetData* b, BitSetData* mask) const;
00273 template<bool sparse>
00274 void intersect_with_mask(const BitSetData* mask);
00276 void intersect_with_masks(const BitSetData* a, const BitSetData* b);
00278 bool intersects(const BitSetData* b) const;
00280 void nand_with_mask(const BitSetData* b);
00282 unsigned int words(void) const;
00284 unsigned int size(void) const;
00285 };
00286
00287 }}}
00288
00289 #include <gecode/int/extensional/bit-set.hpp>
00290
00291 namespace Gecode { namespace Int { namespace Extensional {
00292
00294 template<unsigned int _size>
00295 class TinyBitSet {
00296 template<unsigned int> friend class TinyBitSet;
00297 protected:
00299 BitSetData bits[_size];
00300 public:
00302 TinyBitSet(Space& home, unsigned int n);
00304 template<unsigned int largersize>
00305 TinyBitSet(Space& home, const TinyBitSet<largersize>& tbs);
00307 template<class IndexType>
00308 TinyBitSet(Space& home, const BitSet<IndexType>& bs);
00310 int limit(void) const;
00312 bool empty(void) const;
00314 unsigned int width(void) const;
00316 void clear_mask(BitSetData* mask);
00318 void add_to_mask(const BitSetData* b, BitSetData* mask) const;
00320 template<bool sparse>
00321 void intersect_with_mask(const BitSetData* mask);
00323 void intersect_with_masks(const BitSetData* a, const BitSetData* b);
00325 bool intersects(const BitSetData* b);
00327 void nand_with_mask(const BitSetData* b);
00329 void nand_with_masks(const BitSetData* a, const BitSetData* b);
00331 unsigned int words(void) const;
00333 unsigned int size(void) const;
00334 };
00335
00336 }}}
00337
00338 #include <gecode/int/extensional/tiny-bit-set.hpp>
00339
00340 namespace Gecode { namespace Int { namespace Extensional {
00341
00343 typedef TupleSet::Tuple Tuple;
00344
00346 template<class View>
00347 class Compact : public Propagator {
00348 protected:
00350 typedef TupleSet::Range Range;
00352 class CTAdvisor : public ViewAdvisor<View> {
00353 public:
00354 using ViewAdvisor<View>::view;
00355 protected:
00357 const Range* _fst;
00359 const Range* _lst;
00360 public:
00362
00363
00364 CTAdvisor(Space& home, Propagator& p, Council<CTAdvisor>& c,
00365 const TupleSet& ts, View x0, int i);
00367 CTAdvisor(Space& home, CTAdvisor& a);
00369
00370 void adjust(void);
00372 const Range* fst(void) const;
00374 const Range* lst(void) const;
00376 void dispose(Space& home, Council<CTAdvisor>& c);
00377 };
00379
00380
00381 enum StatusType {
00382 SINGLE = 0,
00383 MULTIPLE = 1,
00384 NONE = 2,
00385 PROPAGATING = 3
00386 };
00388 class Status {
00389 protected:
00391 ptrdiff_t s;
00392 public:
00394 Status(StatusType t);
00396 Status(const Status& s);
00398 StatusType type(void) const;
00400 bool single(CTAdvisor& a) const;
00402 void touched(CTAdvisor& a);
00404 void none(void);
00406 void propagating(void);
00407 };
00409
00410
00411
00412 class ValidSupports {
00413 protected:
00415 const unsigned int n_words;
00417 int max;
00419 ViewRanges<View> xr;
00421 const Range* sr;
00423 int n;
00425 const BitSetData* s;
00426 public:
00428 ValidSupports(const Compact<View>& p, CTAdvisor& a);
00430 ValidSupports(const TupleSet& ts, int i, View x);
00432 void operator ++(void);
00434 bool operator ()(void) const;
00436 const BitSetData* supports(void) const;
00438 int val(void) const;
00439 };
00441 class LostSupports {
00442 protected:
00444 const unsigned int n_words;
00446 const Range* r;
00448 int l;
00450 int h;
00452 const BitSetData* s;
00453 public:
00455 LostSupports(const Compact<View>& p, CTAdvisor& a,
00456 int l, int h);
00458 void operator ++(void);
00460 bool operator ()(void) const;
00462 const BitSetData* supports(void) const;
00463 };
00465 protected:
00467 int unassigned;
00469 const unsigned int n_words;
00471 Status status;
00473 TupleSet ts;
00475 Council<CTAdvisor> c;
00477 Compact(Space& home, Compact& p);
00479 Compact(Home home, ViewArray<View>& x, const TupleSet& ts);
00481 const Range* range(CTAdvisor& a, int n);
00483 const BitSetData* supports(CTAdvisor& a, int n);
00484 public:
00486 size_t dispose(Space& home);
00487 };
00488
00502 template<class View, class Table>
00503 class CompactTable : public Compact<View> {
00504 public:
00505 typedef typename Compact<View>::ValidSupports ValidSupports;
00506 typedef typename Compact<View>::Range Range;
00507 typedef typename Compact<View>::CTAdvisor CTAdvisor;
00508 typedef typename Compact<View>::StatusType StatusType;
00509 typedef typename Compact<View>::Status Status;
00510 typedef typename Compact<View>::LostSupports LostSupports;
00511
00512 using Compact<View>::supports;
00513 using Compact<View>::unassigned;
00514 using Compact<View>::status;
00515 using Compact<View>::c;
00516 using Compact<View>::ts;
00517
00519 Table table;
00521 template<class TableProp>
00522 CompactTable(Space& home, TableProp& p);
00524 CompactTable(Home home, ViewArray<View>& x, const TupleSet& ts);
00525 public:
00527 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00529 virtual void reschedule(Space& home);
00531 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00533 virtual Actor* copy(Space& home);
00535 static ExecStatus post(Home home, ViewArray<View>& x, const TupleSet& ts);
00537 size_t dispose(Space& home);
00539 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00540 };
00541
00543 template<class View>
00544 ExecStatus postcompact(Home home, ViewArray<View>& x, const TupleSet& ts);
00545
00546 }}}
00547
00548 #include <gecode/int/extensional/compact.hpp>
00549
00550 #endif
00551
00552