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