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

brancher.hpp

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 <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<Var> bf,
00099                  VarValPrint<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<Var> bf,
00116        VarValPrint<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   // Compute choice
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     // Making the PVC here is not so nice, I think.
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     // Compute symmetries.
00154 
00155     int choicePos = pvc->pos().pos;
00156     int choiceVal = pvc->val();
00157     delete c;
00158 
00159     _prevPos = choicePos;
00160 
00161     // TODO: It should be possible to use simpler containers than the
00162     // STL ones here.
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     // Convert "seen" vector into array.
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       // Post the branching constraint.
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       // Post the branching constraint.
00247       ExecStatus fromBase = ViewValBrancher<View,n,Val,a,Filter,Print>
00248         ::commit(home, c, b);
00249       GECODE_ES_CHECK(fromBase);
00250 
00251       // Post prunings.
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 // STATISTICS: int-branch