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 LDSBBrancher<View,n,Val,a>
00103 ::LDSBBrancher(Home home, ViewArray<View>& x,
00104 ViewSel<View>* vs[n],
00105 ValSelCommitBase<View,Val>* vsc,
00106 SymmetryImp<View>** syms, int nsyms,
00107 BranchFilter bf,
00108 VarValPrint vvp)
00109 : ViewValBrancher<View,n,Val,a>(home, x, vs, vsc, bf, vvp),
00110 _syms(syms),
00111 _nsyms(nsyms),
00112 _prevPos(-1)
00113 {
00114 home.notice(*this, AP_DISPOSE, true);
00115 }
00116
00117 template<class View, int n, class Val, unsigned int a>
00118 forceinline BrancherHandle
00119 LDSBBrancher<View,n,Val,a>::
00120 post(Home home, ViewArray<View>& x,
00121 ViewSel<View>* vs[n], ValSelCommitBase<View,Val>* vsc,
00122 SymmetryImp<View>** syms, int nsyms,
00123 BranchFilter bf, VarValPrint vvp) {
00124 return *new (home) LDSBBrancher<View,n,Val,a>(home,x,vs,vsc,syms,nsyms,bf,vvp);
00125 }
00126
00127 template<class View, int n, class Val, unsigned int a>
00128 forceinline
00129 LDSBBrancher<View,n,Val,a>::
00130 LDSBBrancher(Space& home, bool shared, LDSBBrancher<View,n,Val,a>& b)
00131 : ViewValBrancher<View,n,Val,a>(home,shared,b),
00132 _nsyms(b._nsyms),
00133 _prevPos(b._prevPos) {
00134 _syms = home.alloc<SymmetryImp<View>*>(_nsyms);
00135 for (int i = 0 ; i < _nsyms ; i++)
00136 _syms[i] = b._syms[i]->copy(home, shared);
00137 }
00138
00139 template<class View, int n, class Val, unsigned int a>
00140 Actor*
00141 LDSBBrancher<View,n,Val,a>::copy(Space& home, bool shared) {
00142 return new (home) LDSBBrancher<View,n,Val,a>(home,shared,*this);
00143 }
00144
00145
00146
00147 template<class View, int n, class Val, unsigned int a>
00148 const Choice*
00149 LDSBBrancher<View,n,Val,a>::choice(Space& home) {
00150
00151 const Choice* c = ViewValBrancher<View,n,Val,a>::choice(home);
00152 const PosValChoice<Val>* pvc = static_cast<const PosValChoice<Val>* >(c);
00153
00154
00155
00156 int choicePos = pvc->pos().pos;
00157 int choiceVal = pvc->val();
00158 delete c;
00159
00160 _prevPos = choicePos;
00161
00162
00163
00164 std::deque<Literal> queue;
00165 std::set<Literal> seen;
00166
00167 seen.insert(Literal(choicePos, choiceVal));
00168 queue.push_back(Literal(choicePos, choiceVal));
00169
00170 do {
00171 Literal l = queue[0];
00172 queue.pop_front();
00173
00174 for (int i = 0 ; i < _nsyms ; i++) {
00175 ArgArray<Literal> toExclude = _syms[i]->symmetric(l, this->x);
00176 for (int j = 0 ; j < toExclude.size() ; ++j) {
00177 if (seen.find(toExclude[j]) == seen.end())
00178 queue.push_back(toExclude[j]);
00179 seen.insert(toExclude[j]);
00180 }
00181 }
00182 } while (queue.size() > 0);
00183
00184
00185 int nliterals = seen.size();
00186 Literal* literals = new Literal[nliterals];
00187 std::set<Literal>::iterator it = seen.begin();
00188 for (int i = 0 ; i < nliterals ; i++) {
00189 literals[i] = *it;
00190 ++it;
00191 }
00192
00193 return new LDSBChoice<Val>(*this,a,choicePos,choiceVal, literals, nliterals);
00194 }
00195
00196
00197 template<class View, int n, class Val, unsigned int a>
00198 const Choice*
00199 LDSBBrancher<View,n,Val,a>::choice(const Space& home, Archive& e) {
00200 (void) home;
00201 int p; e >> p;
00202 Val v; e >> v;
00203 int nliterals; e >> nliterals;
00204 Literal* literals = new Literal[nliterals];
00205 for (int i = 0 ; i < nliterals ; i++) {
00206 e >> literals[i]._variable;
00207 e >> literals[i]._value;
00208 }
00209 return new LDSBChoice<Val>(*this,a,p,v, literals, nliterals);
00210 }
00211
00212 template <>
00213 inline
00214 ModEvent
00215 prune<Int::IntView>(Space& home, Int::IntView x, int v) {
00216 return x.nq(home, v);
00217 }
00218
00219 template <>
00220 inline
00221 ModEvent
00222 prune<Int::BoolView>(Space& home, Int::BoolView x, int v) {
00223 return x.nq(home, v);
00224 }
00225
00226
00227 template<class View, int n, class Val, unsigned int a>
00228 ExecStatus
00229 LDSBBrancher<View,n,Val,a>
00230 ::commit(Space& home, const Choice& c, unsigned int b) {
00231 const LDSBChoice<Val>& pvc
00232 = static_cast<const LDSBChoice<Val>&>(c);
00233 int choicePos = pvc.pos().pos;
00234 int choiceVal = pvc.val();
00235
00236 if (b == 0) {
00237
00238 ExecStatus fromBase = ViewValBrancher<View,n,Val,a>::commit(home, c, b);
00239 GECODE_ES_CHECK(fromBase);
00240 for (int i = 0 ; i < this->_nsyms ; i++)
00241 this->_syms[i]->update(Literal(choicePos, choiceVal));
00242 } else if (b == 1) {
00243
00244 ExecStatus fromBase = ViewValBrancher<View,n,Val,a>::commit(home, c, b);
00245 GECODE_ES_CHECK(fromBase);
00246
00247
00248 int nliterals = pvc.nliterals();
00249 const Literal* literals = pvc.literals();
00250 for (int i = 0 ; i < nliterals ; i++) {
00251 const Literal& l = literals[i];
00252 ModEvent me = prune<View>(home, this->x[l._variable], l._value);
00253 GECODE_ME_CHECK(me);
00254 }
00255 }
00256
00257 return ES_OK;
00258 }
00259
00260 template<class View, int n, class Val, unsigned int a>
00261 size_t
00262 LDSBBrancher<View,n,Val,a>::dispose(Space& home) {
00263 home.ignore(*this,AP_DISPOSE,true);
00264 (void) ViewValBrancher<View,n,Val,a>::dispose(home);
00265 return sizeof(LDSBBrancher<View,n,Val,a>);
00266 }
00267
00268 }}}
00269
00270