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 Set { namespace LDSB {
00035
00036 template<class View, int n, class Val, unsigned int a,
00037 class Filter, class Print>
00038 LDSBSetBrancher<View,n,Val,a,Filter,Print>
00039 ::LDSBSetBrancher(Home home, ViewArray<View>& x,
00040 ViewSel<View>* vs[n],
00041 ValSelCommitBase<View,Val>* vsc,
00042 SymmetryImp<View>** syms, int nsyms,
00043 BranchFilter<Var> bf,
00044 VarValPrint<Var,Val> vvp)
00045 : LDSBBrancher<View,n,Val,a,Filter,Print>
00046 (home, x, vs, vsc, syms, nsyms, bf, vvp),
00047 _prevPos(-1),
00048 _copiedSyms(NULL),
00049 _nCopiedSyms(0),
00050 _stable(false) {
00051
00052 int seen = 0;
00053 int dest = this->_nsyms - 1;
00054 for (int i = 0 ; i < this->_nsyms - seen ; i++) {
00055 if (dynamic_cast<ValueSymmetryImp<View>*>(this->_syms[i])) {
00056 SymmetryImp<View>* t = this->_syms[i];
00057 this->_syms[i] = this->_syms[dest];
00058 this->_syms[dest] = t;
00059 dest--;
00060 seen++;
00061 }
00062 }
00063 _nValueSymmetries = seen;
00064 _nNonValueSymmetries = this->_nsyms - seen;
00065 }
00066
00067 template<class View, int n, class Val, unsigned int a,
00068 class Filter, class Print>
00069 LDSBSetBrancher<View,n,Val,a,Filter,Print>::
00070 LDSBSetBrancher(Space& home,
00071 LDSBSetBrancher<View,n,Val,a,Filter,Print>& b)
00072 : LDSBBrancher<View,n,Val,a,Filter,Print>(home,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));
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 class Filter, class Print>
00132 void
00133 LDSBSetBrancher<View,n,Val,a,Filter,Print>::
00134 updatePart1(Space& home, int choicePos) {
00135 if (_nValueSymmetries > 0) {
00136
00137
00138 if (choicePos != _prevPos) {
00139 if (_prevPos != -1) {
00140 int i = 0;
00141 for (int j = _nNonValueSymmetries ; j < this->_nsyms ; j++) {
00142 this->_syms[j] = _copiedSyms[i];
00143 i++;
00144 }
00145
00146 for (int i = 0 ; i < _nCopiedSyms ; i++) {
00147 ValueSymmetryImp<View>* ns =
00148 specialUpdate(home, _copiedSyms[i], _leftBranchValues);
00149 if (ns) {
00150 this->_syms = home.realloc<SymmetryImp<View>*>(this->_syms,
00151 this->_nsyms,
00152 this->_nsyms+1);
00153 this->_syms[this->_nsyms] = ns;
00154 this->_nsyms++;
00155 this->_nValueSymmetries++;
00156 }
00157 }
00158 }
00159
00160
00161 _leftBranchValues = IntSet::empty;
00162 _prevPos = choicePos;
00163 if (_nCopiedSyms > 0) home.free(_copiedSyms, _nCopiedSyms);
00164 _nCopiedSyms = _nValueSymmetries;
00165 _copiedSyms = home.alloc<ValueSymmetryImp<View>*>(_nCopiedSyms);
00166 {
00167 int i = 0;
00168 for (int j = _nNonValueSymmetries ; j < this->_nsyms ; j++) {
00169 ValueSymmetryImp<View>* vsi =
00170 static_cast<ValueSymmetryImp<View>*>(this->_syms[j]);
00171 _copiedSyms[i] =
00172 static_cast<ValueSymmetryImp<View>*>(vsi->copy(home));
00173 i++;
00174 }
00175 }
00176 }
00177 }
00178 }
00179
00180
00181 template<class View, int n, class Val, unsigned int a,
00182 class Filter, class Print>
00183 const Choice*
00184 LDSBSetBrancher<View,n,Val,a,Filter,Print>::choice(Space& home) {
00185
00186 const Choice* c = ViewValBrancher<View,n,Val,a,Filter,Print>::choice(home);
00187 const PosValChoice<Val>* pvc = static_cast<const PosValChoice<Val>* >(c);
00188
00189
00190
00191 int choicePos = pvc->pos().pos;
00192 delete c;
00193
00194 assert(!_stable);
00195 updatePart1(home, choicePos);
00196
00197 return LDSBBrancher<View,n,Val,a,Filter,Print>::choice(home);
00198 }
00199
00200 template<class View, int n, class Val, unsigned int a,
00201 class Filter, class Print>
00202 ExecStatus
00203 LDSBSetBrancher<View,n,Val,a,Filter,Print>
00204 ::commit(Space& home, const Choice& c, unsigned int b) {
00205 const LDSBChoice<Val>& pvc
00206 = static_cast<const LDSBChoice<Val>&>(c);
00207 int choicePos = pvc.pos().pos;
00208 int choiceVal = pvc.val();
00209
00210 if (!_stable)
00211 updatePart1(home, choicePos);
00212
00213 if (b == 0) {
00214 IntArgs ia;
00215 for (IntSetValues v(_leftBranchValues) ; v() ; ++v) {
00216 ia << v.val();
00217 }
00218 ia << choiceVal;
00219 _leftBranchValues = IntSet(ia);
00220
00221
00222 ExecStatus fromBase = ViewValBrancher<View,n,Val,a,Filter,Print>
00223 ::commit(home, c, b);
00224 GECODE_ES_CHECK(fromBase);
00225 for (int i = 0 ; i < this->_nsyms ; i++)
00226 this->_syms[i]->update(Literal(choicePos, choiceVal));
00227 } else if (b == 1) {
00228
00229 ExecStatus fromBase = ViewValBrancher<View,n,Val,a,Filter,Print>
00230 ::commit(home, c, b);
00231 GECODE_ES_CHECK(fromBase);
00232
00233
00234 int nliterals = pvc.nliterals();
00235 const Literal* literals = pvc.literals();
00236 for (int i = 0 ; i < nliterals ; i++) {
00237 const Literal& l = literals[i];
00238 ModEvent me = prune<View>(home, this->x[l._variable], l._value);
00239 GECODE_ME_CHECK(me);
00240 }
00241 }
00242
00243 return ES_OK;
00244 }
00245
00246 template<class View, int n, class Val, unsigned int a,
00247 class Filter, class Print>
00248 Actor*
00249 LDSBSetBrancher<View,n,Val,a,Filter,Print>::copy(Space& home) {
00250 return new (home) LDSBSetBrancher<View,n,Val,a,Filter,Print>
00251 (home,*this);
00252 }
00253
00254 template<class View, int n, class Val, unsigned int a,
00255 class Filter, class Print>
00256 forceinline void
00257 LDSBSetBrancher<View,n,Val,a,Filter,Print>::
00258 post(Home home, ViewArray<View>& x,
00259 ViewSel<View>* vs[n], ValSelCommitBase<View,Val>* vsc,
00260 SymmetryImp<View>** syms, int nsyms,
00261 BranchFilter<Var> bf,
00262 VarValPrint<Var,Val> vvp) {
00263 (void) new (home) LDSBSetBrancher<View,n,Val,a,Filter,Print>
00264 (home,x,vs,vsc,syms,nsyms,bf,vvp);
00265 }
00266
00267 template<class View, int n, class Val, unsigned int a>
00268 forceinline void
00269 postldsbsetbrancher(Home home,
00270 ViewArray<View>& x,
00271 ViewSel<View>* vs[n],
00272 ValSelCommitBase<View,Val>* vsc,
00273 SymmetryImp<View>** syms, int nsyms,
00274 BranchFilter<typename View::VarType> bf,
00275 VarValPrint<typename View::VarType,Val> vvp) {
00276 if (bf) {
00277 if (vvp) {
00278 LDSBSetBrancher<View,n,Val,a,BrancherFilter<View>,BrancherPrint<View,Val> >
00279 ::post(home,x,vs,vsc,syms,nsyms,bf,vvp);
00280 } else {
00281 LDSBSetBrancher<View,n,Val,a,BrancherFilter<View>,BrancherNoPrint<View,Val> >
00282 ::post(home,x,vs,vsc,syms,nsyms,bf,vvp);
00283 }
00284 } else {
00285 if (vvp) {
00286 LDSBSetBrancher<View,n,Val,a,BrancherNoFilter<View>,BrancherPrint<View,Val> >
00287 ::post(home,x,vs,vsc,syms,nsyms,bf,vvp);
00288 } else {
00289 LDSBSetBrancher<View,n,Val,a,BrancherNoFilter<View>,BrancherNoPrint<View,Val> >
00290 ::post(home,x,vs,vsc,syms,nsyms,bf,vvp);
00291 }
00292 }
00293 }
00294
00295 }}}
00296
00297