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 <gecode/set/ldsb.hh>
00035 #include <gecode/set/branch.hh>
00036 #include <map>
00037
00038 namespace Gecode {
00039 using namespace Int::LDSB;
00040
00041
00042
00043
00044 SymmetryHandle VariableSymmetry(const SetVarArgs& x) {
00045 ArgArray<VarImpBase*> a(x.size());
00046 for (int i = 0 ; i < x.size() ; i++)
00047 a[i] = x[i].varimp();
00048 return SymmetryHandle(new VariableSymmetryObject(a));
00049 }
00050 SymmetryHandle VariableSequenceSymmetry(const SetVarArgs& x, int ss) {
00051 ArgArray<VarImpBase*> a(x.size());
00052 for (int i = 0 ; i < x.size() ; i++)
00053 a[i] = x[i].varimp();
00054 return SymmetryHandle(new VariableSequenceSymmetryObject(a, ss));
00055 }
00056 }
00057
00058 namespace Gecode { namespace Int { namespace LDSB {
00059 template <>
00060 ModEvent prune<Set::SetView>(Space& home, Set::SetView x, int v) {
00061 return x.exclude(home, v);
00062 }
00063 }}}
00064
00065 namespace Gecode { namespace Set { namespace LDSB {
00066
00068 class VariableMap : public std::map<VarImpBase*,int> {};
00069
00070
00071
00072
00073
00074 SymmetryImp<SetView>* createSetSym(Space& home, const SymmetryHandle& s,
00075 VariableMap variableMap) {
00076 VariableSymmetryObject* varref =
00077 dynamic_cast<VariableSymmetryObject*>(s.ref);
00078 ValueSymmetryObject* valref =
00079 dynamic_cast<ValueSymmetryObject*>(s.ref);
00080 VariableSequenceSymmetryObject* varseqref =
00081 dynamic_cast<VariableSequenceSymmetryObject*>(s.ref);
00082 ValueSequenceSymmetryObject* valseqref =
00083 dynamic_cast<ValueSequenceSymmetryObject*>(s.ref);
00084 if (varref) {
00085 int n = varref->nxs;
00086 int* indices = home.alloc<int>(n);
00087 for (int i = 0 ; i < n ; i++) {
00088 VariableMap::const_iterator index = variableMap.find(varref->xs[i]);
00089 if (index == variableMap.end())
00090 throw
00091 Int::LDSBUnbranchedVariable("VariableSymmetryObject::createSet");
00092 indices[i] = index->second;
00093 }
00094 return new (home) VariableSymmetryImp<SetView>(home, indices, n);
00095 }
00096 if (valref) {
00097 int n = valref->values.size();
00098 int *vs = home.alloc<int>(n);
00099 int i = 0;
00100 for (IntSetValues v(valref->values) ; v() ; ++v) {
00101 vs[i] = v.val();
00102 i++;
00103 }
00104 return new (home) ValueSymmetryImp<SetView>(home, vs, n);
00105 }
00106 if (varseqref) {
00107 int n = varseqref->nxs;
00108 int* indices = home.alloc<int>(n);
00109 for (int i = 0 ; i < n ; i++) {
00110 VariableMap::const_iterator index =
00111 variableMap.find(varseqref->xs[i]);
00112 if (index == variableMap.end())
00113 throw
00114 Int::LDSBUnbranchedVariable("VariableSequenceSymmetryObject::createSet");
00115 indices[i] = index->second;
00116 }
00117 return new (home) VariableSequenceSymmetryImp<SetView>(home, indices, n,
00118 varseqref->seq_size);
00119 }
00120 if (valseqref) {
00121 unsigned int n = valseqref->values.size();
00122 int *vs = home.alloc<int>(n);
00123 for (unsigned int i = 0 ; i < n ; i++)
00124 vs[i] = valseqref->values[i];
00125 return new (home) ValueSequenceSymmetryImp<SetView>(home, vs, n,
00126 valseqref->seq_size);
00127 }
00128 GECODE_NEVER;
00129 return NULL;
00130 }
00131 }}}
00132
00133 namespace Gecode {
00134
00135 using namespace Set::LDSB;
00136
00137 void
00138 branch(Home home, const SetVarArgs& x,
00139 SetVarBranch vars, SetValBranch vals,
00140 const Symmetries& syms,
00141 SetBranchFilter bf,
00142 SetVarValPrint vvp) {
00143 using namespace Set;
00144 if (home.failed()) return;
00145 vars.expand(home,x);
00146 ViewArray<SetView> xv(home,x);
00147 ViewSel<SetView>* vs[1] = {
00148 Branch::viewsel(home,vars)
00149 };
00150
00151
00152
00153 VariableMap variableMap;
00154 for (int i = 0 ; i < x.size() ; i++)
00155 variableMap[x[i].varimp()] = i;
00156
00157
00158
00159 int n = syms.size();
00160 SymmetryImp<SetView>** array =
00161 static_cast<Space&>(home).alloc<SymmetryImp<SetView>* >(n);
00162 for (int i = 0 ; i < n ; i++) {
00163 array[i] = createSetSym(home, syms[i], variableMap);
00164 }
00165
00166 postldsbsetbrancher<SetView,1,int,2>
00167 (home,xv,vs,Branch::valselcommit(home,vals),array,n,bf,vvp);
00168 }
00169
00170 void
00171 branch(Home home, const SetVarArgs& x,
00172 TieBreak<SetVarBranch> vars, SetValBranch vals,
00173 const Symmetries& syms,
00174 SetBranchFilter bf,
00175 SetVarValPrint vvp) {
00176 using namespace Set;
00177 if (home.failed()) return;
00178 vars.a.expand(home,x);
00179 if ((vars.a.select() == SetVarBranch::SEL_NONE) ||
00180 (vars.a.select() == SetVarBranch::SEL_RND))
00181 vars.b = SET_VAR_NONE();
00182 vars.b.expand(home,x);
00183 if ((vars.b.select() == SetVarBranch::SEL_NONE) ||
00184 (vars.b.select() == SetVarBranch::SEL_RND))
00185 vars.c = SET_VAR_NONE();
00186 vars.c.expand(home,x);
00187 if ((vars.c.select() == SetVarBranch::SEL_NONE) ||
00188 (vars.c.select() == SetVarBranch::SEL_RND))
00189 vars.d = SET_VAR_NONE();
00190 vars.d.expand(home,x);
00191 if (vars.b.select() == SetVarBranch::SEL_NONE) {
00192 branch(home,x,vars.a,vals,syms,bf,vvp);
00193 } else {
00194
00195
00196 VariableMap variableMap;
00197 for (int i = 0 ; i < x.size() ; i++)
00198 variableMap[x[i].varimp()] = i;
00199
00200
00201
00202 int n = syms.size();
00203 SymmetryImp<SetView>** array =
00204 static_cast<Space&>(home).alloc<SymmetryImp<SetView>* >(n);
00205 for (int i = 0 ; i < n ; i++) {
00206 array[i] = Set::LDSB::createSetSym(home, syms[i], variableMap);
00207 }
00208
00209 ViewArray<SetView> xv(home,x);
00210 ValSelCommitBase<SetView,int>* vsc = Branch::valselcommit(home,vals);
00211 if (vars.c.select() == SetVarBranch::SEL_NONE) {
00212 ViewSel<SetView>* vs[2] = {
00213 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
00214 };
00215 postldsbsetbrancher<SetView,2,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
00216 } else if (vars.d.select() == SetVarBranch::SEL_NONE) {
00217 ViewSel<SetView>* vs[3] = {
00218 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
00219 Branch::viewsel(home,vars.c)
00220 };
00221 postldsbsetbrancher<SetView,3,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
00222 } else {
00223 ViewSel<SetView>* vs[4] = {
00224 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
00225 Branch::viewsel(home,vars.c),Branch::viewsel(home,vars.d)
00226 };
00227 postldsbsetbrancher<SetView,4,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
00228 }
00229 }
00230 }
00231
00232 }
00233
00234