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