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 namespace Gecode { namespace Int { namespace LDSB {
00035
00037 template <class T, class A>
00038 ArgArray<T>
00039 dynamicStackToArgArray(const Support::DynamicStack<T,A>& s) {
00040 ArgArray<T> a(s.entries());
00041 for (int i = 0 ; i < s.entries() ; ++i) {
00042 a[i] = s[i];
00043 }
00044 return a;
00045 }
00046
00047 template<class View>
00048 SymmetryImp<View>::~SymmetryImp(void) {}
00049
00050 template<class View>
00051 void*
00052 SymmetryImp<View>::operator new(size_t s, Space& home) {
00053 return home.ralloc(s);
00054 }
00055
00056 template<class View>
00057 void
00058 SymmetryImp<View>::operator delete(void*,Space&) {}
00059
00060 template<class View>
00061 void
00062 SymmetryImp<View>::operator delete(void*) {}
00063
00064 template <class View>
00065 VariableSymmetryImp<View>
00066 ::VariableSymmetryImp(Space& home, int* _indices, unsigned int n)
00067 : indices(home, 0, 0) {
00068
00069
00070
00071 int maximum = _indices[0];
00072 int minimum = _indices[0];
00073 for (unsigned int i = 1 ; i < n ; i++) {
00074 if (_indices[i] > maximum) maximum = _indices[i];
00075 if (_indices[i] < minimum) minimum = _indices[i];
00076 }
00077 indices.resize(home, maximum-minimum+1, minimum);
00078
00079
00080 for (unsigned int i = 0 ; i < n ; i++) {
00081 indices.set(_indices[i]);
00082 }
00083 }
00084
00085
00086
00087 template <class View>
00088 inline
00089 VariableSymmetryImp<View>
00090 ::VariableSymmetryImp(Space& home, const VariableSymmetryImp& other) :
00091 indices(home, other.indices) {}
00092
00093 template <class View>
00094 size_t
00095 VariableSymmetryImp<View>
00096 ::dispose(Space& home) {
00097 indices.dispose(home);
00098 return sizeof(*this);
00099 }
00100
00101 template <class View>
00102 void
00103 VariableSymmetryImp<View>
00104 ::update(Literal l) {
00105 if (indices.valid(l._variable)) {
00106 indices.clear(l._variable);
00107 }
00108 }
00109
00110 template <class View>
00111 SymmetryImp<View>*
00112 VariableSymmetryImp<View>::copy(Space& home) const {
00113 return new (home) VariableSymmetryImp<View>(home, *this);
00114 }
00115
00116
00117
00118
00119
00120 template <class View>
00121 ValueSymmetryImp<View>
00122 ::ValueSymmetryImp(Space& home, int* vs, unsigned int n)
00123 : values(home, 0, 0) {
00124
00125
00126
00127 assert(n > 0);
00128 int maximum = vs[0];
00129 int minimum = vs[0];
00130 for (unsigned int i = 1 ; i < n ; i++) {
00131 if (vs[i] > maximum) maximum = vs[i];
00132 if (vs[i] < minimum) minimum = vs[i];
00133 }
00134 values.resize(home, maximum-minimum+1, minimum);
00135
00136
00137 for (unsigned int i = 0 ; i < n ; i++) {
00138 values.set(vs[i]);
00139 }
00140 }
00141
00142 template <class View>
00143 ValueSymmetryImp<View>
00144 ::ValueSymmetryImp(Space& home, const ValueSymmetryImp<View>& other)
00145 : values(home, other.values) { }
00146
00147 template <class View>
00148 size_t
00149 ValueSymmetryImp<View>
00150 ::dispose(Space& home) {
00151 values.dispose(home);
00152 return sizeof(*this);
00153 }
00154
00155 template <class View>
00156 void
00157 ValueSymmetryImp<View>
00158 ::update(Literal l) {
00159 if (values.valid(l._value))
00160 values.clear(l._value);
00161 }
00162
00163 template <class View>
00164 SymmetryImp<View>*
00165 ValueSymmetryImp<View>::copy(Space& home) const {
00166 return new (home) ValueSymmetryImp(home, *this);
00167 }
00168
00169
00170
00171 template <class View>
00172 int
00173 VariableSequenceSymmetryImp<View>
00174 ::getVal(unsigned int sequence, unsigned int position) const {
00175 return indices[sequence*seq_size + position];
00176 }
00177
00178 template <class View>
00179 VariableSequenceSymmetryImp<View>
00180 ::VariableSequenceSymmetryImp(Space& home, int* _indices, unsigned int n,
00181 unsigned int seqsize)
00182 : n_indices(n), seq_size(seqsize), n_seqs(n/seqsize) {
00183 indices = home.alloc<unsigned int>(n_indices);
00184 unsigned int max_index = _indices[0];
00185 for (unsigned int i = 0 ; i < n_indices ; i++) {
00186 indices[i] = _indices[i];
00187 if (indices[i] > max_index)
00188 max_index = indices[i];
00189 }
00190
00191 lookup_size = max_index+1;
00192 lookup = home.alloc<int>(lookup_size);
00193 for (unsigned int i = 0 ; i < lookup_size ; i++)
00194 lookup[i] = -1;
00195 for (unsigned int i = 0 ; i < n_indices ; i++) {
00196 if (lookup[indices[i]] == -1)
00197 lookup[indices[i]] = i;
00198 }
00199 }
00200
00201 template <class View>
00202 VariableSequenceSymmetryImp<View>
00203 ::VariableSequenceSymmetryImp(Space& home,
00204 const VariableSequenceSymmetryImp& s)
00205 : n_indices(s.n_indices), seq_size(s.seq_size), n_seqs(s.n_seqs),
00206 lookup_size(s.lookup_size) {
00207 indices = home.alloc<unsigned int>(n_indices);
00208 memcpy(indices, s.indices, n_indices * sizeof(int));
00209 lookup = home.alloc<int>(lookup_size);
00210 memcpy(lookup, s.lookup, lookup_size * sizeof(int));
00211 }
00212
00213 template <class View>
00214 size_t
00215 VariableSequenceSymmetryImp<View>
00216 ::dispose(Space& home) {
00217 home.free<unsigned int>(indices, n_indices);
00218 home.free<int>(lookup, lookup_size);
00219 return sizeof(*this);
00220 }
00221
00223 template <class View>
00224 ArgArray<Literal>
00225 VariableSequenceSymmetryImp<View>
00226 ::symmetric(Literal l, const ViewArray<View>& x) const {
00227 Support::DynamicStack<Literal, Heap> s(heap);
00228 if (l._variable < (int)lookup_size) {
00229 int posIt = lookup[l._variable];
00230 if (posIt == -1) {
00231 return dynamicStackToArgArray(s);
00232 }
00233 unsigned int seqNum = posIt / seq_size;
00234 unsigned int seqPos = posIt % seq_size;
00235 for (unsigned int seq = 0 ; seq < n_seqs ; seq++) {
00236 if (seq == seqNum) {
00237 continue;
00238 }
00239 if (x[getVal(seq, seqPos)].assigned()) {
00240 continue;
00241 }
00242 bool active = true;
00243 const unsigned int *firstSeq = &indices[seqNum*seq_size];
00244 const unsigned int *secondSeq = &indices[seq*seq_size];
00245 for (unsigned int i = 0 ; i < seq_size ; i++) {
00246 const View& xv = x[firstSeq[i]];
00247 const View& yv = x[secondSeq[i]];
00248 if ((!xv.assigned() && !yv.assigned())
00249 || (xv.assigned() && yv.assigned() && xv.val() == yv.val())) {
00250 continue;
00251 } else {
00252 active = false;
00253 break;
00254 }
00255 }
00256
00257 if (active) {
00258 s.push(Literal(secondSeq[seqPos], l._value));
00259 }
00260 }
00261 }
00262 return dynamicStackToArgArray(s);
00263 }
00264
00265
00266 template <class View>
00267 void
00268 VariableSequenceSymmetryImp<View>
00269 ::update(Literal l) {
00270
00271 (void) l;
00272 }
00273
00274 template <class View>
00275 SymmetryImp<View>*
00276 VariableSequenceSymmetryImp<View>
00277 ::copy(Space& home) const {
00278 return new (home) VariableSequenceSymmetryImp<View>(home, *this);
00279 }
00280
00281
00282
00283 template <class View>
00284 int
00285 ValueSequenceSymmetryImp<View>
00286 ::getVal(unsigned int sequence, unsigned int position) const {
00287 return values[sequence*seq_size + position];
00288 }
00289
00290 template <class View>
00291 ValueSequenceSymmetryImp<View>
00292 ::ValueSequenceSymmetryImp(Space& home, int* _values, unsigned int n,
00293 unsigned int seqsize)
00294 : n_values(n), seq_size(seqsize), n_seqs(n/seqsize),
00295 dead_sequences(home, n_seqs) {
00296 values = home.alloc<int>(n_values);
00297 for (unsigned int i = 0 ; i < n_values ; i++)
00298 values[i] = _values[i];
00299 }
00300
00301 template <class View>
00302 ValueSequenceSymmetryImp<View>
00303 ::ValueSequenceSymmetryImp(Space& home,
00304 const ValueSequenceSymmetryImp<View>& vss)
00305 : n_values(vss.n_values),
00306 seq_size(vss.seq_size),
00307 n_seqs(vss.n_seqs),
00308 dead_sequences(home, vss.dead_sequences) {
00309 values = home.alloc<int>(n_values);
00310 for (unsigned int i = 0 ; i < n_values ; i++)
00311 values[i] = vss.values[i];
00312 }
00313
00314 template <class View>
00315 size_t
00316 ValueSequenceSymmetryImp<View>
00317 ::dispose(Space& home) {
00318 home.free(values, n_values);
00319 return sizeof(*this);
00320 }
00321
00322 template <class View>
00323 void
00324 ValueSequenceSymmetryImp<View>
00325 ::update(Literal l) {
00326 unsigned int seq = 0;
00327 unsigned int pos = 0;
00328 for (unsigned int i = 0 ; i < n_values ; i++) {
00329 if (values[i] == l._value) {
00330 dead_sequences.set(seq);
00331
00332 while (pos < seq_size) {
00333 i++;
00334 pos++;
00335 }
00336 }
00337 pos++;
00338 if (pos == seq_size) {
00339 pos = 0;
00340 seq++;
00341 }
00342 }
00343 }
00344
00345 template <class View>
00346 SymmetryImp<View>*
00347 ValueSequenceSymmetryImp<View>
00348 ::copy(Space& home) const {
00349 return new (home) ValueSequenceSymmetryImp<View>(home, *this);
00350 }
00351
00352 }}}
00353
00354