Generated on Tue May 22 09:40:01 2018 for Gecode by doxygen 1.6.3

ldsb.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christopher Mears <chris.mears@monash.edu>
00005  *
00006  *  Copyright:
00007  *     Christopher Mears, 2012
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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    * Implementation of some SymmetryHandle methods.
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    * The createSetSym function is an almost exact copy of
00072    * createIntSym/createBoolSym.
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     // Construct mapping from each variable in the array to its index
00152     // in the array.
00153     VariableMap variableMap;
00154     for (int i = 0 ; i < x.size() ; i++)
00155       variableMap[x[i].varimp()] = i;
00156 
00157     // Convert the modelling-level Symmetries object into an array of
00158     // SymmetryImp objects.
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       // Construct mapping from each variable in the array to its index
00195       // in the array.
00196       VariableMap variableMap;
00197       for (int i = 0 ; i < x.size() ; i++)
00198         variableMap[x[i].varimp()] = i;
00199 
00200       // Convert the modelling-level Symmetries object into an array of
00201       // SymmetryImp objects.
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 // STATISTICS: set-branch