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_LDSB_HH__
00039 #define __GECODE_INT_LDSB_HH__
00040
00041 #include <gecode/int.hh>
00042
00047 namespace Gecode { namespace Int { namespace LDSB {
00048
00050 class Literal {
00051 public:
00053 Literal(void);
00055 Literal(int _var, int _val);
00056
00059 int _variable;
00063 int _value;
00064
00067 bool operator <(const Literal &rhs) const;
00068 };
00069
00081 GECODE_INT_EXPORT
00082 std::pair<int,int>
00083 findVar(int *indices, unsigned int n_values, unsigned int seq_size, int index);
00084 }}}
00085
00086 namespace Gecode {
00088 template<>
00089 class ArrayTraits<ArgArray<VarImpBase*> > {
00090 public:
00091 typedef ArgArray<VarImpBase*> StorageType;
00092 typedef VarImpBase* ValueType;
00093 typedef ArgArray<VarImpBase*> ArgsType;
00094 };
00095
00097 typedef ArgArray<Int::LDSB::Literal> LiteralArgs;
00099 template<>
00100 class ArrayTraits<LiteralArgs> {
00101 public:
00102 typedef LiteralArgs StorageType;
00103 typedef Int::LDSB::Literal ValueType;
00104 typedef LiteralArgs ArgsType;
00105 };
00106 }
00107
00108 namespace Gecode { namespace Int { namespace LDSB {
00110 class GECODE_INT_EXPORT SymmetryObject {
00111 public:
00113 int nrefs;
00115 SymmetryObject(void);
00117 virtual ~SymmetryObject(void);
00118 };
00120 class GECODE_INT_EXPORT VariableSymmetryObject : public SymmetryObject {
00121 public:
00123 VarImpBase** xs;
00125 int nxs;
00127 VariableSymmetryObject(ArgArray<VarImpBase*> vars);
00129 ~VariableSymmetryObject(void);
00130 };
00132 class GECODE_INT_EXPORT ValueSymmetryObject : public SymmetryObject {
00133 public:
00135 IntSet values;
00137 ValueSymmetryObject(IntSet vs);
00138 };
00140 class GECODE_INT_EXPORT VariableSequenceSymmetryObject : public SymmetryObject {
00141 public:
00143 VarImpBase** xs;
00145 int nxs;
00147 int seq_size;
00149 VariableSequenceSymmetryObject(ArgArray<VarImpBase*> vars, int ss);
00151 ~VariableSequenceSymmetryObject();
00152 };
00154 class GECODE_INT_EXPORT ValueSequenceSymmetryObject : public SymmetryObject {
00155 public:
00157 IntArgs values;
00159 int seq_size;
00161 ValueSequenceSymmetryObject(IntArgs vs, int ss);
00162 };
00163
00165 template<class View>
00166 class SymmetryImp {
00167 public:
00169 virtual ArgArray<Literal> symmetric(Literal, const ViewArray<View>&) const = 0;
00171 virtual void update(Literal) = 0;
00173 virtual SymmetryImp<View>* copy(Space& home, bool share) const = 0;
00175 virtual size_t dispose(Space& home) = 0;
00177 virtual ~SymmetryImp(void);
00179 static void* operator new(size_t s, Space& home);
00181 static void operator delete(void*,Space&);
00183 static void operator delete(void*);
00184 };
00186 template <class View>
00187 class VariableSymmetryImp : public SymmetryImp<View> {
00188 protected:
00190 Support::BitSetOffset<Space> indices;
00191 public:
00193 VariableSymmetryImp<View>(Space& home, int* vs, unsigned int n);
00195 VariableSymmetryImp<View>(Space& home, const VariableSymmetryImp<View>& other);
00197 virtual size_t dispose(Space& home);
00199 void update(Literal);
00201 virtual ArgArray<Literal> symmetric(Literal, const ViewArray<View>&) const;
00203 SymmetryImp<View>* copy(Space& home, bool share) const;
00204 };
00206 template <class View>
00207 class ValueSymmetryImp : public SymmetryImp<View>
00208 {
00209 public:
00211 Support::BitSetOffset<Space> values;
00213 ValueSymmetryImp<View>(Space& home, int* vs, unsigned int n);
00215 ValueSymmetryImp<View>(Space& home, const ValueSymmetryImp<View>& other);
00217 virtual size_t dispose(Space& home);
00219 void update(Literal);
00221 virtual ArgArray<Literal> symmetric(Literal, const ViewArray<View>&) const;
00223 SymmetryImp<View>* copy(Space& home, bool share) const;
00224 };
00226 template <class View>
00227 class VariableSequenceSymmetryImp : public SymmetryImp<View>
00228 {
00229 protected:
00231 unsigned int *indices;
00233 unsigned int n_indices;
00235 unsigned int seq_size;
00237 unsigned int n_seqs;
00238
00240
00241
00242
00243
00244
00245
00246 int *lookup;
00248 unsigned int lookup_size;
00249
00252 int getVal(unsigned int sequence, unsigned int position) const;
00253 public:
00255 VariableSequenceSymmetryImp<View>(Space& home, int *_indices, unsigned int n, unsigned int seqsize);
00257 VariableSequenceSymmetryImp<View>(Space& home, bool share, const VariableSequenceSymmetryImp<View>& s);
00259 virtual size_t dispose(Space& home);
00261 void update(Literal);
00263 virtual ArgArray<Literal> symmetric(Literal, const ViewArray<View>&) const;
00265 SymmetryImp<View>* copy(Space& home, bool share) const;
00266 };
00268 template <class View>
00269 class ValueSequenceSymmetryImp : public SymmetryImp<View>
00270 {
00271 protected:
00273 int *values;
00275 unsigned int n_values;
00277 unsigned int seq_size;
00279 unsigned int n_seqs;
00281 Support::BitSet<Space> dead_sequences;
00284 int getVal(unsigned int sequence, unsigned int position) const;
00285 private:
00286 ValueSequenceSymmetryImp<View>(const ValueSequenceSymmetryImp<View>&);
00287 public:
00289 ValueSequenceSymmetryImp<View>(Space& home, int* _values, unsigned int n, unsigned int seqsize);
00291 ValueSequenceSymmetryImp<View>(Space& home, const ValueSequenceSymmetryImp<View>& vss);
00293 virtual size_t dispose(Space& home);
00295 void update(Literal);
00297 virtual ArgArray<Literal> symmetric(Literal, const ViewArray<View>&) const;
00299 SymmetryImp<View>* copy(Space& home, bool share) const;
00300 };
00301
00304 template<class Val>
00305 class GECODE_VTABLE_EXPORT LDSBChoice : public PosValChoice<Val> {
00306 private:
00308 const Literal * const _literals;
00310 const int _nliterals;
00311 public:
00314 LDSBChoice(const Brancher& b, unsigned int a, const Pos& p, const Val& n,
00315 const Literal* literals, int nliterals);
00317 ~LDSBChoice(void);
00319 const Literal* literals(void) const;
00321 int nliterals(void) const;
00323 virtual size_t size(void) const;
00325 virtual void archive(Archive& e) const;
00326 };
00327
00336 template<class View, int n, class Val, unsigned int a,
00337 class Filter, class Print>
00338 class LDSBBrancher : public ViewValBrancher<View,n,Val,a,Filter,Print> {
00339 public:
00340 using typename ViewValBrancher<View,n,Val,a,Filter,Print>::Var;
00342 SymmetryImp<View>** _syms;
00344 int _nsyms;
00345
00346 int _prevPos;
00347 protected:
00349 LDSBBrancher(Space& home, bool share, LDSBBrancher& b);
00351 LDSBBrancher(Home home,
00352 ViewArray<View>& x,
00353 ViewSel<View>* vs[n],
00354 ValSelCommitBase<View,Val>* vsc,
00355 SymmetryImp<View>** syms, int nsyms,
00356 BranchFilter<Var> bf,
00357 VarValPrint<Var,Val> vvp);
00358 public:
00360 virtual const Choice* choice(Space& home);
00362 virtual const Choice* choice(const Space& home, Archive& e);
00364 virtual ExecStatus commit(Space& home, const Choice& c, unsigned int b);
00366 virtual Actor* copy(Space& home, bool share);
00368 virtual size_t dispose(Space& home);
00370 static void post(Home home,
00371 ViewArray<View>& x,
00372 ViewSel<View>* vs[n],
00373 ValSelCommitBase<View,Val>* vsc,
00374 SymmetryImp<View>** syms,
00375 int nsyms,
00376 BranchFilter<Var> bf,
00377 VarValPrint<Var,Val> vvp);
00378 };
00379
00381 template<class View, int n, class Val, unsigned int a>
00382 void postldsbbrancher(Home home,
00383 ViewArray<View>& x,
00384 ViewSel<View>* vs[n],
00385 ValSelCommitBase<View,Val>* vsc,
00386 SymmetryImp<View>** syms, int nsyms,
00387 BranchFilter<typename View::VarType> bf,
00388 VarValPrint<typename View::VarType,Val> vvp);
00389
00391 template<class View>
00392 ModEvent prune(Space& home, View x, int v);
00393
00394 }}}
00395
00396 #include <gecode/int/ldsb/brancher.hpp>
00397 #include <gecode/int/ldsb/sym-imp.hpp>
00398
00399 #endif
00400
00401
00402