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