Generated on Thu Apr 11 13:59:10 2019 for Gecode by doxygen 1.6.3

sym-imp.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christopher Mears <chris.mears@monash.edu>
00005  *
00006  *  Copyright:
00007  *     Christopher Mears, 2012
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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     // Find minimum and maximum value in _indices: the minimum is the
00069     // offset, and the maximum dictates how large the bitset needs to
00070     // be.
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     // Set the bits for the included indices.
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   // The minimum value in vs is the bitset's offset, and the maximum
00119   // dictates how large the bitset needs to be.
00120   template <class View>
00121   ValueSymmetryImp<View>
00122   ::ValueSymmetryImp(Space& home, int* vs, unsigned int n)
00123     : values(home, 0, 0) {
00124     // Find minimum and maximum value in vs: the minimum is the
00125     // offset, and the maximum dictates how large the bitset needs to
00126     // be.
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     // Set the bits for the included values.
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     Region region;
00228     Support::DynamicStack<Literal,Region> s(region);
00229     if (l._variable < (int)lookup_size) {
00230       int posIt = lookup[l._variable];
00231       if (posIt == -1) {
00232         return dynamicStackToArgArray(s);
00233       }
00234       unsigned int seqNum = posIt / seq_size;
00235       unsigned int seqPos = posIt % seq_size;
00236       for (unsigned int seq = 0 ; seq < n_seqs ; seq++) {
00237         if (seq == seqNum) {
00238           continue;
00239         }
00240         if (x[getVal(seq, seqPos)].assigned()) {
00241           continue;
00242         }
00243         bool active = true;
00244         const unsigned int *firstSeq = &indices[seqNum*seq_size];
00245         const unsigned int *secondSeq = &indices[seq*seq_size];
00246         for (unsigned int i = 0 ; i < seq_size ; i++) {
00247           const View& xv = x[firstSeq[i]];
00248           const View& yv = x[secondSeq[i]];
00249           if ((!xv.assigned() && !yv.assigned())
00250               || (xv.assigned() && yv.assigned() && xv.val() == yv.val())) {
00251             continue;
00252           } else {
00253             active = false;
00254             break;
00255           }
00256         }
00257 
00258         if (active) {
00259           s.push(Literal(secondSeq[seqPos], l._value));
00260         }
00261       }
00262     }
00263     return dynamicStackToArgArray(s);
00264   }
00265 
00266 
00267   template <class View>
00268   void
00269   VariableSequenceSymmetryImp<View>
00270   ::update(Literal l) {
00271     // Do nothing.
00272     (void) l;
00273   }
00274 
00275   template <class View>
00276   SymmetryImp<View>*
00277   VariableSequenceSymmetryImp<View>
00278   ::copy(Space& home) const {
00279     return new (home) VariableSequenceSymmetryImp<View>(home, *this);
00280   }
00281 
00282 
00283 
00284   template <class View>
00285   int
00286   ValueSequenceSymmetryImp<View>
00287   ::getVal(unsigned int sequence, unsigned int position) const {
00288     return values[sequence*seq_size + position];
00289   }
00290 
00291   template <class View>
00292   ValueSequenceSymmetryImp<View>
00293   ::ValueSequenceSymmetryImp(Space& home, int* _values, unsigned int n,
00294                              unsigned int seqsize)
00295     : n_values(n), seq_size(seqsize), n_seqs(n/seqsize),
00296       dead_sequences(home, n_seqs) {
00297     values = home.alloc<int>(n_values);
00298     for (unsigned int i = 0 ; i < n_values ; i++)
00299       values[i] = _values[i];
00300   }
00301 
00302   template <class View>
00303   ValueSequenceSymmetryImp<View>
00304   ::ValueSequenceSymmetryImp(Space& home,
00305                              const ValueSequenceSymmetryImp<View>& vss)
00306     : n_values(vss.n_values),
00307       seq_size(vss.seq_size),
00308       n_seqs(vss.n_seqs),
00309       dead_sequences(home, vss.dead_sequences) {
00310     values = home.alloc<int>(n_values);
00311     for (unsigned int i = 0 ; i < n_values ; i++)
00312       values[i] = vss.values[i];
00313   }
00314 
00315   template <class View>
00316   size_t
00317   ValueSequenceSymmetryImp<View>
00318   ::dispose(Space& home) {
00319     home.free(values, n_values);
00320     return sizeof(*this);
00321   }
00322 
00323   template <class View>
00324   void
00325   ValueSequenceSymmetryImp<View>
00326   ::update(Literal l) {
00327     unsigned int seq = 0;
00328     unsigned int pos = 0;
00329     for (unsigned int i = 0 ; i < n_values ; i++) {
00330       if (values[i] == l._value) {
00331         dead_sequences.set(seq);
00332         // TODO: This can be slightly optimised.
00333         while (pos < seq_size) {
00334           i++;
00335           pos++;
00336         }
00337       }
00338       pos++;
00339       if (pos == seq_size) {
00340         pos = 0;
00341         seq++;
00342       }
00343     }
00344   }
00345 
00346   template <class View>
00347   SymmetryImp<View>*
00348   ValueSequenceSymmetryImp<View>
00349   ::copy(Space& home) const {
00350     return new (home) ValueSequenceSymmetryImp<View>(home, *this);
00351   }
00352 
00353 }}}
00354 
00355 // STATISTICS: int-branch