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 #include <deque>
00039 #include <set>
00040
00041 namespace Gecode { namespace Int { namespace LDSB {
00042
00043 forceinline
00044 Literal::Literal(void)
00045 : _variable(-1), _value(-1) {}
00046
00047 forceinline
00048 Literal::Literal(int idx, int val)
00049 : _variable(idx), _value(val) {}
00050
00051 forceinline
00052 bool
00053 Literal::operator <(const Literal &rhs) const {
00054 int d = rhs._variable - _variable;
00055 if (d > 0) return true;
00056 else if (d == 0) return rhs._value > _value;
00057 else return false;
00058 }
00059
00060
00061 template<class Val>
00062 inline
00063 LDSBChoice<Val>::LDSBChoice(const Brancher& b, unsigned int a, const Pos& p,
00064 const Val& n, const Literal* literals,
00065 int nliterals)
00066 : PosValChoice<Val>(b,a,p,n), _literals(literals), _nliterals(nliterals)
00067 {}
00068
00069 template<class Val>
00070 LDSBChoice<Val>::~LDSBChoice(void) {
00071 delete [] _literals;
00072 }
00073
00074 template<class Val>
00075 forceinline const Literal*
00076 LDSBChoice<Val>::literals(void) const { return _literals; }
00077
00078 template<class Val>
00079 forceinline int
00080 LDSBChoice<Val>::nliterals(void) const { return _nliterals; }
00081
00082 template<class Val>
00083 size_t
00084 LDSBChoice<Val>::size(void) const {
00085 return sizeof(LDSBChoice<Val>);
00086 }
00087
00088 template<class Val>
00089 void
00090 LDSBChoice<Val>::archive(Archive& e) const {
00091 PosValChoice<Val>::archive(e);
00092 e << _nliterals;
00093 for (int i = 0 ; i < _nliterals ; i++) {
00094 e << _literals[i]._variable;
00095 e << _literals[i]._value;
00096 }
00097 }
00098
00099
00100
00101 template<class View, int n, class Val, unsigned int a,
00102 class Filter, class Print>
00103 LDSBBrancher<View,n,Val,a,Filter,Print>
00104 ::LDSBBrancher(Home home, ViewArray<View>& x,
00105 ViewSel<View>* vs[n],
00106 ValSelCommitBase<View,Val>* vsc,
00107 SymmetryImp<View>** syms, int nsyms,
00108 BranchFilter<Var> bf,
00109 VarValPrint<Var,Val> vvp)
00110 : ViewValBrancher<View,n,Val,a,Filter,Print>(home, x, vs, vsc, bf, vvp),
00111 _syms(syms),
00112 _nsyms(nsyms),
00113 _prevPos(-1)
00114 {
00115 home.notice(*this, AP_DISPOSE, true);
00116 }
00117
00118 template<class View, int n, class Val, unsigned int a,
00119 class Filter, class Print>
00120 forceinline void
00121 LDSBBrancher<View,n,Val,a,Filter,Print>::
00122 post(Home home, ViewArray<View>& x,
00123 ViewSel<View>* vs[n], ValSelCommitBase<View,Val>* vsc,
00124 SymmetryImp<View>** syms, int nsyms,
00125 BranchFilter<Var> bf,
00126 VarValPrint<Var,Val> vvp) {
00127 (void) new (home) LDSBBrancher<View,n,Val,a,Filter,Print>
00128 (home,x,vs,vsc,syms,nsyms,bf,vvp);
00129 }
00130
00131 template<class View, int n, class Val, unsigned int a,
00132 class Filter, class Print>
00133 forceinline
00134 LDSBBrancher<View,n,Val,a,Filter,Print>::
00135 LDSBBrancher(Space& home, bool shared,
00136 LDSBBrancher<View,n,Val,a,Filter,Print>& b)
00137 : ViewValBrancher<View,n,Val,a,Filter,Print>(home,shared,b),
00138 _nsyms(b._nsyms),
00139 _prevPos(b._prevPos) {
00140 _syms = home.alloc<SymmetryImp<View>*>(_nsyms);
00141 for (int i = 0 ; i < _nsyms ; i++)
00142 _syms[i] = b._syms[i]->copy(home, shared);
00143 }
00144
00145 template<class View, int n, class Val, unsigned int a,
00146 class Filter, class Print>
00147 Actor*
00148 LDSBBrancher<View,n,Val,a,Filter,Print>::copy(Space& home, bool shared) {
00149 return new (home) LDSBBrancher<View,n,Val,a,Filter,Print>
00150 (home,shared,*this);
00151 }
00152
00153
00154
00155 template<class View, int n, class Val, unsigned int a,
00156 class Filter, class Print>
00157 const Choice*
00158 LDSBBrancher<View,n,Val,a,Filter,Print>::choice(Space& home) {
00159
00160 const Choice* c = ViewValBrancher<View,n,Val,a,Filter,Print>::choice(home);
00161 const PosValChoice<Val>* pvc = static_cast<const PosValChoice<Val>* >(c);
00162
00163
00164
00165 int choicePos = pvc->pos().pos;
00166 int choiceVal = pvc->val();
00167 delete c;
00168
00169 _prevPos = choicePos;
00170
00171
00172
00173 std::deque<Literal> queue;
00174 std::set<Literal> seen;
00175
00176 seen.insert(Literal(choicePos, choiceVal));
00177 queue.push_back(Literal(choicePos, choiceVal));
00178
00179 do {
00180 Literal l = queue[0];
00181 queue.pop_front();
00182
00183 for (int i = 0 ; i < _nsyms ; i++) {
00184 ArgArray<Literal> toExclude = _syms[i]->symmetric(l, this->x);
00185 for (int j = 0 ; j < toExclude.size() ; ++j) {
00186 if (seen.find(toExclude[j]) == seen.end())
00187 queue.push_back(toExclude[j]);
00188 seen.insert(toExclude[j]);
00189 }
00190 }
00191 } while (queue.size() > 0);
00192
00193
00194 int nliterals = static_cast<int>(seen.size());
00195 Literal* literals = new Literal[nliterals];
00196 std::set<Literal>::iterator it = seen.begin();
00197 for (int i = 0 ; i < nliterals ; i++) {
00198 literals[i] = *it;
00199 ++it;
00200 }
00201
00202 return new LDSBChoice<Val>(*this,a,choicePos,choiceVal, literals, nliterals);
00203 }
00204
00205
00206 template<class View, int n, class Val, unsigned int a,
00207 class Filter, class Print>
00208 const Choice*
00209 LDSBBrancher<View,n,Val,a,Filter,Print>::choice(const Space& home,
00210 Archive& e) {
00211 (void) home;
00212 int p; e >> p;
00213 Val v; e >> v;
00214 int nliterals; e >> nliterals;
00215 Literal* literals = new Literal[nliterals];
00216 for (int i = 0 ; i < nliterals ; i++) {
00217 e >> literals[i]._variable;
00218 e >> literals[i]._value;
00219 }
00220 return new LDSBChoice<Val>(*this,a,p,v, literals, nliterals);
00221 }
00222
00223 template <>
00224 inline
00225 ModEvent
00226 prune<Int::IntView>(Space& home, Int::IntView x, int v) {
00227 return x.nq(home, v);
00228 }
00229
00230 template <>
00231 inline
00232 ModEvent
00233 prune<Int::BoolView>(Space& home, Int::BoolView x, int v) {
00234 return x.nq(home, v);
00235 }
00236
00237
00238 template<class View, int n, class Val, unsigned int a,
00239 class Filter, class Print>
00240 ExecStatus
00241 LDSBBrancher<View,n,Val,a,Filter,Print>
00242 ::commit(Space& home, const Choice& c, unsigned int b) {
00243 const LDSBChoice<Val>& pvc
00244 = static_cast<const LDSBChoice<Val>&>(c);
00245 int choicePos = pvc.pos().pos;
00246 int choiceVal = pvc.val();
00247
00248 if (b == 0) {
00249
00250 ExecStatus fromBase = ViewValBrancher<View,n,Val,a,Filter,Print>
00251 ::commit(home, c, b);
00252 GECODE_ES_CHECK(fromBase);
00253 for (int i = 0 ; i < this->_nsyms ; i++)
00254 this->_syms[i]->update(Literal(choicePos, choiceVal));
00255 } else if (b == 1) {
00256
00257 ExecStatus fromBase = ViewValBrancher<View,n,Val,a,Filter,Print>
00258 ::commit(home, c, b);
00259 GECODE_ES_CHECK(fromBase);
00260
00261
00262 int nliterals = pvc.nliterals();
00263 const Literal* literals = pvc.literals();
00264 for (int i = 0 ; i < nliterals ; i++) {
00265 const Literal& l = literals[i];
00266 ModEvent me = prune<View>(home, this->x[l._variable], l._value);
00267 GECODE_ME_CHECK(me);
00268 }
00269 }
00270
00271 return ES_OK;
00272 }
00273
00274 template<class View, int n, class Val, unsigned int a,
00275 class Filter, class Print>
00276 size_t
00277 LDSBBrancher<View,n,Val,a,Filter,Print>::dispose(Space& home) {
00278 home.ignore(*this,AP_DISPOSE,true);
00279 (void) ViewValBrancher<View,n,Val,a,Filter,Print>::dispose(home);
00280 return sizeof(LDSBBrancher<View,n,Val,a,Filter,Print>);
00281 }
00282
00283 template<class View, int n, class Val, unsigned int a>
00284 forceinline void
00285 postldsbbrancher(Home home,
00286 ViewArray<View>& x,
00287 ViewSel<View>* vs[n],
00288 ValSelCommitBase<View,Val>* vsc,
00289 SymmetryImp<View>** syms, int nsyms,
00290 BranchFilter<typename View::VarType> bf,
00291 VarValPrint<typename View::VarType,Val> vvp) {
00292 if (bf) {
00293 if (vvp) {
00294 LDSBBrancher<View,n,Val,a,BrancherFilter<View>,BrancherPrint<View,Val>>
00295 ::post(home,x,vs,vsc,syms,nsyms,bf,vvp);
00296 } else {
00297 LDSBBrancher<View,n,Val,a,BrancherFilter<View>,BrancherNoPrint<View,Val> >
00298 ::post(home,x,vs,vsc,syms,nsyms,bf,vvp);
00299 }
00300 } else {
00301 if (vvp) {
00302 LDSBBrancher<View,n,Val,a,BrancherNoFilter<View>,BrancherPrint<View,Val>>
00303 ::post(home,x,vs,vsc,syms,nsyms,bf,vvp);
00304 } else {
00305 LDSBBrancher<View,n,Val,a,BrancherNoFilter<View>,BrancherNoPrint<View,Val> >
00306 ::post(home,x,vs,vsc,syms,nsyms,bf,vvp);
00307 }
00308 }
00309 }
00310
00311 }}}
00312
00313