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 Set { namespace LDSB {
00039
00040 template<class View, int n, class Val, unsigned int a>
00041 LDSBSetBrancher<View,n,Val,a>
00042 ::LDSBSetBrancher(Home home, ViewArray<View>& x,
00043 ViewSel<View>* vs[n],
00044 ValSelCommitBase<View,Val>* vsc,
00045 SymmetryImp<View>** syms, int nsyms,
00046 SetBranchFilter bf,
00047 VarValPrint vvp)
00048 : LDSBBrancher<View,n,Val,a>(home, x, vs, vsc, syms, nsyms, bf, vvp),
00049 _prevPos(-1),
00050 _copiedSyms(NULL),
00051 _nCopiedSyms(0),
00052 _stable(false) {
00053
00054 int seen = 0;
00055 int dest = this->_nsyms - 1;
00056 for (int i = 0 ; i < this->_nsyms - seen ; i++) {
00057 if (dynamic_cast<ValueSymmetryImp<View>*>(this->_syms[i])) {
00058 SymmetryImp<View>* t = this->_syms[i];
00059 this->_syms[i] = this->_syms[dest];
00060 this->_syms[dest] = t;
00061 dest--;
00062 seen++;
00063 }
00064 }
00065 _nValueSymmetries = seen;
00066 _nNonValueSymmetries = this->_nsyms - seen;
00067 }
00068
00069 template<class View, int n, class Val, unsigned int a>
00070 LDSBSetBrancher<View,n,Val,a>::
00071 LDSBSetBrancher(Space& home, bool shared, LDSBSetBrancher<View,n,Val,a>& b)
00072 : LDSBBrancher<View,n,Val,a>(home,shared,b),
00073 _prevPos(b._prevPos),
00074 _nNonValueSymmetries(b._nNonValueSymmetries),
00075 _nValueSymmetries(b._nValueSymmetries),
00076 _nCopiedSyms(b._nCopiedSyms),
00077 _leftBranchValues(b._leftBranchValues),
00078 _stable(b._stable) {
00079 if (_nCopiedSyms > 0) {
00080 _copiedSyms = home.alloc<ValueSymmetryImp<View>*>(_nCopiedSyms);
00081 for (int i = 0 ; i < _nCopiedSyms ; i++)
00082 _copiedSyms[i] = static_cast<ValueSymmetryImp<View>*>(
00083 b._copiedSyms[i]->copy(home, shared));
00084 } else {
00085 _copiedSyms = NULL;
00086 }
00087 }
00088
00098 template <class View>
00099 ValueSymmetryImp<View>*
00100 specialUpdate(Space& home, ValueSymmetryImp<View>* s, IntSet usedValues) {
00101
00102 IntArgs intersection;
00103 IntArgs difference;
00104 int n = 0;
00105 for (int i = s->values.next(s->values.offset()) ;
00106 i <= s->values.max_bit() ; i = s->values.next(i+1)) {
00107 n++;
00108 if (usedValues.in(i))
00109 intersection << i;
00110 else
00111 difference << i;
00112 }
00113
00114 for (IntSetValues v(usedValues) ; v() ; ++v) {
00115 s->update(Literal(0, v.val()));
00116 }
00117
00118 if (intersection.size() < 2)
00119 return NULL;
00120 int *a = new int[intersection.size()];
00121 for (int i = 0 ; i < intersection.size() ; i++) {
00122 a[i] = intersection[i];
00123 }
00124 ValueSymmetryImp<View>* ns =
00125 new (home) ValueSymmetryImp<View>(home, a, intersection.size());
00126 delete [] a;
00127 return ns;
00128 }
00129
00130 template<class View, int n, class Val, unsigned int a>
00131 void
00132 LDSBSetBrancher<View,n,Val,a>::
00133 updatePart1(Space& home, int choicePos) {
00134 if (_nValueSymmetries > 0) {
00135
00136
00137 if (choicePos != _prevPos) {
00138 if (_prevPos != -1) {
00139 int i = 0;
00140 for (int j = _nNonValueSymmetries ; j < this->_nsyms ; j++) {
00141 this->_syms[j] = _copiedSyms[i];
00142 i++;
00143 }
00144
00145 for (int i = 0 ; i < _nCopiedSyms ; i++) {
00146 ValueSymmetryImp<View>* ns =
00147 specialUpdate(home, _copiedSyms[i], _leftBranchValues);
00148 if (ns) {
00149 this->_syms = home.realloc<SymmetryImp<View>*>(this->_syms,
00150 this->_nsyms,
00151 this->_nsyms+1);
00152 this->_syms[this->_nsyms] = ns;
00153 this->_nsyms++;
00154 this->_nValueSymmetries++;
00155 }
00156 }
00157 }
00158
00159
00160 _leftBranchValues = IntSet::empty;
00161 _prevPos = choicePos;
00162 if (_nCopiedSyms > 0) home.free(_copiedSyms, _nCopiedSyms);
00163 _nCopiedSyms = _nValueSymmetries;
00164 _copiedSyms = home.alloc<ValueSymmetryImp<View>*>(_nCopiedSyms);
00165 int i = 0;
00166 for (int j = _nNonValueSymmetries ; j < this->_nsyms ; j++) {
00167 ValueSymmetryImp<View>* vsi =
00168 static_cast<ValueSymmetryImp<View>*>(this->_syms[j]);
00169 _copiedSyms[i] =
00170 static_cast<ValueSymmetryImp<View>*>(vsi->copy(home, false));
00171 i++;
00172 }
00173 }
00174 }
00175 }
00176
00177
00178 template<class View, int n, class Val, unsigned int a>
00179 const Choice*
00180 LDSBSetBrancher<View,n,Val,a>::choice(Space& home) {
00181
00182 const Choice* c = ViewValBrancher<View,n,Val,a>::choice(home);
00183 const PosValChoice<Val>* pvc = static_cast<const PosValChoice<Val>* >(c);
00184
00185
00186
00187 int choicePos = pvc->pos().pos;
00188 delete c;
00189
00190 assert(!_stable);
00191 updatePart1(home, choicePos);
00192
00193 return LDSBBrancher<View,n,Val,a>::choice(home);
00194 }
00195
00196 template<class View, int n, class Val, unsigned int a>
00197 ExecStatus
00198 LDSBSetBrancher<View,n,Val,a>
00199 ::commit(Space& home, const Choice& c, unsigned int b) {
00200 const LDSBChoice<Val>& pvc
00201 = static_cast<const LDSBChoice<Val>&>(c);
00202 int choicePos = pvc.pos().pos;
00203 int choiceVal = pvc.val();
00204
00205 if (!_stable)
00206 updatePart1(home, choicePos);
00207
00208 if (b == 0) {
00209 IntArgs ia;
00210 for (IntSetValues v(_leftBranchValues) ; v() ; ++v) {
00211 ia << v.val();
00212 }
00213 ia << choiceVal;
00214 _leftBranchValues = IntSet(ia);
00215
00216
00217 ExecStatus fromBase = ViewValBrancher<View,n,Val,a>::commit(home, c, b);
00218 GECODE_ES_CHECK(fromBase);
00219 for (int i = 0 ; i < this->_nsyms ; i++)
00220 this->_syms[i]->update(Literal(choicePos, choiceVal));
00221 } else if (b == 1) {
00222
00223 ExecStatus fromBase = ViewValBrancher<View,n,Val,a>::commit(home, c, b);
00224 GECODE_ES_CHECK(fromBase);
00225
00226
00227 int nliterals = pvc.nliterals();
00228 const Literal* literals = pvc.literals();
00229 for (int i = 0 ; i < nliterals ; i++) {
00230 const Literal& l = literals[i];
00231 ModEvent me = prune<View>(home, this->x[l._variable], l._value);
00232 GECODE_ME_CHECK(me);
00233 }
00234 }
00235
00236 return ES_OK;
00237 }
00238
00239 template<class View, int n, class Val, unsigned int a>
00240 Actor*
00241 LDSBSetBrancher<View,n,Val,a>::copy(Space& home, bool shared) {
00242 return new (home) LDSBSetBrancher<View,n,Val,a>(home,shared,*this);
00243 }
00244
00245 template<class View, int n, class Val, unsigned int a>
00246 forceinline BrancherHandle
00247 LDSBSetBrancher<View,n,Val,a>::
00248 post(Home home, ViewArray<View>& x,
00249 ViewSel<View>* vs[n], ValSelCommitBase<View,Val>* vsc,
00250 SymmetryImp<View>** syms, int nsyms,
00251 SetBranchFilter bf,
00252 VarValPrint vvp) {
00253 return *new (home) LDSBSetBrancher<View,n,Val,a>(home,x,vs,vsc,syms,nsyms,bf,vvp);
00254 }
00255
00256 }}}
00257
00258