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