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_NVALUES_HH__
00039 #define __GECODE_INT_NVALUES_HH__
00040
00041 #include <gecode/int.hh>
00042 #include <gecode/int/val-set.hh>
00043
00049 namespace Gecode { namespace Int { namespace NValues {
00050
00052 enum RangeEventType {
00054 RET_FST = 0,
00056 RET_LST = 1,
00058 RET_END = 2
00059 };
00060
00062 class RangeEvent {
00063 public:
00065 RangeEventType ret;
00067 int val;
00069 int view;
00071 bool operator <(RangeEvent re) const;
00072 };
00073
00075 class SymBitMatrix : public Support::BitSet<Region> {
00076 protected:
00078 int n;
00080 int pos(int x, int y) const;
00081 public:
00083 SymBitMatrix(Region& r, int n);
00085 bool get(int x, int y) const;
00087 void set(int x, int y);
00088 };
00089
00090 }}}
00091
00092 #include <gecode/int/nvalues/range-event.hpp>
00093 #include <gecode/int/nvalues/sym-bit-matrix.hpp>
00094
00095 #include <gecode/int/view-val-graph.hh>
00096
00097 namespace Gecode { namespace Int { namespace NValues {
00098
00100 class Graph : public ViewValGraph::Graph<IntView> {
00101 protected:
00103 int n_matched;
00104 public:
00106 Graph(void);
00108 int size(void) const;
00110 void init(Space& home, const ValSet& vs, const ViewArray<IntView>& x);
00112 void sync(Space& home);
00113
00114
00115
00116
00117
00118 bool mark(Space& home);
00120 ExecStatus prune(Space& home);
00121 };
00122
00123 }}}
00124
00125 #include <gecode/int/nvalues/graph.hpp>
00126
00127 namespace Gecode { namespace Int { namespace NValues {
00128
00135 template<class VY>
00136 class IntBase
00137 : public MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND> {
00138 protected:
00139 using MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>::x;
00140 using MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>::y;
00142 ValSet vs;
00144 IntBase(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
00146 IntBase(Space& home, bool share, IntBase<VY>& p);
00148 void add(Space& home);
00154 void disjoint(Space& home, Region& r, int*& dis, int& n_dis);
00156 void eliminate(Space& home);
00158 int size(Space& home) const;
00160 ExecStatus all_in_valset(Space& home);
00169 ExecStatus prune_lower(Space& home, int* dis, int n_dis);
00176 ExecStatus prune_upper(Space& home, Graph& g);
00177 public:
00179 virtual PropCost cost(const Space&, const ModEventDelta&) const;
00181 virtual size_t dispose(Space& home);
00182 };
00183
00190 template<class VY>
00191 class EqInt : public IntBase<VY> {
00192 protected:
00193 using IntBase<VY>::x;
00194 using IntBase<VY>::y;
00195 using IntBase<VY>::vs;
00196 using IntBase<VY>::add;
00197 using IntBase<VY>::all_in_valset;
00198 using IntBase<VY>::disjoint;
00199 using IntBase<VY>::prune_lower;
00200 using IntBase<VY>::prune_upper;
00202 Graph g;
00204 EqInt(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
00206 EqInt(Space& home, bool share, EqInt<VY>& p);
00207 public:
00209 virtual Propagator* copy(Space& home, bool share);
00211 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00213 static ExecStatus post(Home home, ViewArray<IntView>& x, VY y);
00215 virtual size_t dispose(Space& home);
00216 };
00217
00224 template<class VY>
00225 class LqInt : public IntBase<VY> {
00226 protected:
00227 using IntBase<VY>::x;
00228 using IntBase<VY>::y;
00229 using IntBase<VY>::vs;
00230 using IntBase<VY>::add;
00231 using IntBase<VY>::all_in_valset;
00232 using IntBase<VY>::disjoint;
00233 using IntBase<VY>::prune_lower;
00234 using IntBase<VY>::prune_upper;
00236 LqInt(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
00238 LqInt(Space& home, bool share, LqInt<VY>& p);
00239 public:
00241 virtual Propagator* copy(Space& home, bool share);
00243 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00245 static ExecStatus post(Home home, ViewArray<IntView>& x, VY y);
00247 virtual size_t dispose(Space& home);
00248 };
00249
00256 template<class VY>
00257 class GqInt : public IntBase<VY> {
00258 protected:
00259 using IntBase<VY>::x;
00260 using IntBase<VY>::y;
00261 using IntBase<VY>::vs;
00262 using IntBase<VY>::add;
00263 using IntBase<VY>::all_in_valset;
00264 using IntBase<VY>::disjoint;
00265 using IntBase<VY>::prune_lower;
00266 using IntBase<VY>::prune_upper;
00267 using IntBase<VY>::eliminate;
00269 Graph g;
00271 GqInt(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
00273 GqInt(Space& home, bool share, GqInt<VY>& p);
00274 public:
00276 virtual Propagator* copy(Space& home, bool share);
00278 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00280 static ExecStatus post(Home home, ViewArray<IntView>& x, VY y);
00281 };
00282
00283 }}}
00284
00285 #include <gecode/int/nvalues/int-base.hpp>
00286 #include <gecode/int/nvalues/int-eq.hpp>
00287 #include <gecode/int/nvalues/int-lq.hpp>
00288 #include <gecode/int/nvalues/int-gq.hpp>
00289
00290 namespace Gecode { namespace Int { namespace NValues {
00291
00298 template<class VY>
00299 class BoolBase : public Propagator {
00300 protected:
00302 static const int VS_ZERO = 1 << 0;
00304 static const int VS_ONE = 1 << 1;
00306 int status;
00308 Council<ViewAdvisor<BoolView> > c;
00310 VY y;
00312 BoolBase(Home home, int status, ViewArray<BoolView>& x, VY y);
00314 BoolBase(Space& home, bool share, BoolBase<VY>& p);
00315 public:
00317 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00319 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00321 virtual size_t dispose(Space& home);
00322 };
00323
00330 template<class VY>
00331 class EqBool : public BoolBase<VY> {
00332 protected:
00333 using BoolBase<VY>::VS_ZERO;
00334 using BoolBase<VY>::VS_ONE;
00335 using BoolBase<VY>::status;
00336 using BoolBase<VY>::c;
00337 using BoolBase<VY>::y;
00339 EqBool(Home home, int status, ViewArray<BoolView>& x, VY y);
00341 EqBool(Space& home, bool share, EqBool<VY>& p);
00342 public:
00344 virtual Actor* copy(Space& home, bool share);
00346 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00353 static ExecStatus post(Home home, ViewArray<BoolView>& x, VY y);
00354 };
00355
00362 template<class VY>
00363 class LqBool : public BoolBase<VY> {
00364 protected:
00365 using BoolBase<VY>::VS_ZERO;
00366 using BoolBase<VY>::VS_ONE;
00367 using BoolBase<VY>::status;
00368 using BoolBase<VY>::c;
00369 using BoolBase<VY>::y;
00371 LqBool(Home home, int status, ViewArray<BoolView>& x, VY y);
00373 LqBool(Space& home, bool share, LqBool<VY>& p);
00374 public:
00376 virtual Actor* copy(Space& home, bool share);
00378 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00385 static ExecStatus post(Home home, ViewArray<BoolView>& x, VY y);
00386 };
00387
00394 template<class VY>
00395 class GqBool : public BoolBase<VY> {
00396 protected:
00397 using BoolBase<VY>::VS_ZERO;
00398 using BoolBase<VY>::VS_ONE;
00399 using BoolBase<VY>::status;
00400 using BoolBase<VY>::c;
00401 using BoolBase<VY>::y;
00403 GqBool(Home home, int status, ViewArray<BoolView>& x, VY y);
00405 GqBool(Space& home, bool share, GqBool<VY>& p);
00406 public:
00408 virtual Actor* copy(Space& home, bool share);
00410 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00417 static ExecStatus post(Home home, ViewArray<BoolView>& x, VY y);
00418 };
00419
00420 }}}
00421
00422 #include <gecode/int/nvalues/bool-base.hpp>
00423 #include <gecode/int/nvalues/bool-eq.hpp>
00424 #include <gecode/int/nvalues/bool-lq.hpp>
00425 #include <gecode/int/nvalues/bool-gq.hpp>
00426
00427 #endif
00428
00429