Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
30 kB · 918 lines
C++
at develop
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- *//* * Main author: * Christian Schulte <schulte@gecode.org> * * Copyright: * Christian Schulte, 2012 * * This file is part of Gecode, the generic constraint * development environment: * http://www.gecode.org * * Permission is hereby granted, free of charge, to any person obtaining * a copy of this software and associated documentation files (the * "Software"), to deal in the Software without restriction, including * without limitation the rights to use, copy, modify, merge, publish, * distribute, sublicense, and/or sell copies of the Software, and to * permit persons to whom the Software is furnished to do so, subject to * the following conditions: * * The above copyright notice and this permission notice shall be * included in all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. * */
namespace Gecode {
/** * \defgroup TaskBranchViewSel Generic view selection for brancher based on view and value selection * * \ingroup TaskBranchViewVal */ //@{ /// Abstract class for view selection template<class View_> class ViewSel { public: /// Define the view type typedef View_ View; /// The corresponding variable type typedef typename View::VarType Var; /// \name Initialization //@{ /// Constructor for creation ViewSel(Space& home, const VarBranch<Var>& vb); /// Constructor for copying during cloning ViewSel(Space& home, ViewSel<View>& vs); //@} /// \name View selection and tie breaking //@{ /// Select a view from \a x starting from \a s and return its position virtual int select(Space& home, ViewArray<View>& x, int s) = 0; /// Select a view from \a x starting from \a s and return its position virtual int select(Space& home, ViewArray<View>& x, int s, BrancherFilter<View>& f) = 0; /// Select a view from \a x starting from \a s and return its position virtual int select(Space& home, ViewArray<View>& x, int s, BrancherNoFilter<View>& f); /// Select ties from \a x starting from \a s virtual void ties(Space& home, ViewArray<View>& x, int s, int* ties, int& n) = 0; /// Select ties from \a x starting from \a s virtual void ties(Space& home, ViewArray<View>& x, int s, int* ties, int& n, BrancherFilter<View>& f) = 0; /// Select ties from \a x starting from \a s virtual void ties(Space& home, ViewArray<View>& x, int s, int* ties, int& n, BrancherNoFilter<View>& f); /// Break ties in \a x and update to new ties virtual void brk(Space& home, ViewArray<View>& x, int* ties, int& n) = 0; /// Select a view from \a x considering views with positions in \a ties virtual int select(Space& home, ViewArray<View>& x, int* ties, int n) = 0; //@} /// \name Resource management and cloning //@{ /// Create copy during cloning virtual ViewSel<View>* copy(Space& home) = 0; /// Whether dispose must always be called (that is, notice is needed) virtual bool notice(void) const; /// Dispose view selection virtual void dispose(Space& home); /// Unused destructor virtual ~ViewSel(void); //@} /// \name Memory management //@{ /// Allocate memory from space static void* operator new(size_t s, Space& home); /// Return memory to space static void operator delete(void* p, Space& home); /// Needed for exceptions static void operator delete(void* p); //@} };
/// Select the first unassigned view template<class View> class ViewSelNone : public ViewSel<View> { protected: typedef typename ViewSel<View>::Var Var; public: /// \name Initialization //@{ /// Constructor for creation ViewSelNone(Space& home, const VarBranch<Var>& vb); /// Constructor for copying during cloning ViewSelNone(Space& home, ViewSelNone<View>& vs); //@} /// \name View selection and tie breaking //@{ /// Select a view from \a x starting at \a s and return its position virtual int select(Space& home, ViewArray<View>& x, int s); /// Select a view from \a x starting at \a s and return its position virtual int select(Space& home, ViewArray<View>& x, int s, BrancherFilter<View>& f); /// Select ties from \a x starting at \a s virtual void ties(Space& home, ViewArray<View>& x, int s, int* ties, int& n); /// Select ties from \a x starting at \a s virtual void ties(Space& home, ViewArray<View>& x, int s, int* ties, int& n, BrancherFilter<View>& f); /// Break ties in \a x and update to new ties virtual void brk(Space& home, ViewArray<View>& x, int* ties, int& n); /// Select a view from \a x considering view with positions in \a ties virtual int select(Space& home, ViewArray<View>& x, int* ties, int n); //@} /// \name Resource management and cloning //@{ /// Create copy during cloning virtual ViewSel<View>* copy(Space& home); //@} };
/// Select a view randomly template<class View> class ViewSelRnd : public ViewSel<View> { protected: typedef typename ViewSel<View>::Var Var; /// The random number generator used Rnd r; public: /// \name Initialization //@{ /// Constructor for creation ViewSelRnd(Space& home, const VarBranch<Var>& vb); /// Constructor for copying during cloning ViewSelRnd(Space& home, ViewSelRnd<View>& vs); //@} /// \name View selection and tie breaking //@{ /// Select a view from \a x starting from \a s and return its position virtual int select(Space& home, ViewArray<View>& x, int s); /// Select a view from \a x starting from \a s and return its position virtual int select(Space& home, ViewArray<View>& x, int s, BrancherFilter<View>& f); /// Select ties from \a x starting from \a s virtual void ties(Space& home, ViewArray<View>& x, int s, int* ties, int& n); /// Select ties from \a x starting from \a s virtual void ties(Space& home, ViewArray<View>& x, int s, int* ties, int& n, BrancherFilter<View>& f); /// Break ties in \a x and update to new ties virtual void brk(Space& home, ViewArray<View>& x, int* ties, int& n); /// Select a view from \a x considering view with positions in \a ties virtual int select(Space& home, ViewArray<View>& x, int* ties, int n); //@} /// \name Resource management and cloning //@{ /// Create copy during cloning virtual ViewSel<View>* copy(Space& home); //@} };
/// Choose views with smaller merit values class ChooseMin { public: /// Return true if \a a is better than \a b template<class Val> bool operator ()(Val a, Val b) const; };
/// Choose views with larger merit values class ChooseMax { public: /// Return true if \a a is better than \a b template<class Val> bool operator ()(Val a, Val b) const; };
/// Choose view according to merit template<class Choose, class Merit> class ViewSelChoose : public ViewSel<typename Merit::View> { protected: typedef typename ViewSel<typename Merit::View>::Var Var; typedef typename ViewSel<typename Merit::View>::View View; /// Type of merit typedef typename Merit::Val Val; /// How to choose Choose c; /// The merit object used Merit m; public: /// \name Initialization //@{ /// Constructor for creation ViewSelChoose(Space& home, const VarBranch<Var>& vb); /// Constructor for copying during cloning ViewSelChoose(Space& home, ViewSelChoose<Choose,Merit>& vs); //@} /// \name View selection and tie breaking //@{ /// Select a view from \a x starting from \a s and return its position virtual int select(Space& home, ViewArray<View>& x, int s); /// Select a view from \a x starting from \a s and return its position virtual int select(Space& home, ViewArray<View>& x, int s, BrancherFilter<View>& f); /// Select ties from \a x starting from \a s virtual void ties(Space& home, ViewArray<View>& x, int s, int* ties, int& n); /// Select ties from \a x starting from \a s virtual void ties(Space& home, ViewArray<View>& x, int s, int* ties, int& n, BrancherFilter<View>& f); /// Break ties in \a x and update to new ties virtual void brk(Space& home, ViewArray<View>& x, int* ties, int& n); /// Select a view from \a x considering views with positions in \a ties virtual int select(Space& home, ViewArray<View>& x, int* ties, int n); //@} /// \name Resource management and cloning //@{ /// Whether dispose must always be called (that is, notice is needed) virtual bool notice(void) const; /// Delete view selection virtual void dispose(Space& home); //@} };
/// Choose view according to merit taking tie-break limit into account template<class Choose, class Merit> class ViewSelChooseTbl : public ViewSelChoose<Choose,Merit> { protected: typedef typename ViewSelChoose<Choose,Merit>::Val Val; typedef typename ViewSelChoose<Choose,Merit>::View View; typedef typename ViewSelChoose<Choose,Merit>::Var Var; using ViewSelChoose<Choose,Merit>::c; using ViewSelChoose<Choose,Merit>::m; /// Tie-break limit function SharedData<BranchTbl> tbl; public: /// \name Initialization //@{ /// Constructor for initialization ViewSelChooseTbl(Space& home, const VarBranch<Var>& vb); /// Constructor for copying during cloning ViewSelChooseTbl(Space& home, ViewSelChooseTbl<Choose,Merit>& vs); //@} /// \name View selection and tie breaking //@{ /// Select ties from \a x starting from \a s virtual void ties(Space& home, ViewArray<View>& x, int s, int* ties, int& n); /// Select ties from \a x starting from \a s virtual void ties(Space& home, ViewArray<View>& x, int s, int* ties, int& n, BrancherFilter<View>& f); /// Break ties in \a x and update to new ties virtual void brk(Space& home, ViewArray<View>& x, int* ties, int& n); //@} /// \name Resource management and cloning //@{ /// Whether dispose must always be called (that is, notice is needed) virtual bool notice(void) const; /// Delete view selection virtual void dispose(Space& home); //@} };
/// Select view with least merit template<class Merit> class ViewSelMin : public ViewSelChoose<ChooseMin,Merit> { typedef typename ViewSelChoose<ChooseMin,Merit>::View View; typedef typename ViewSelChoose<ChooseMin,Merit>::Var Var; public: /// \name Initialization //@{ /// Constructor for initialization ViewSelMin(Space& home, const VarBranch<Var>& vb); /// Constructor for copying during cloning ViewSelMin(Space& home, ViewSelMin<Merit>& vs); //@} /// \name Resource management and cloning //@{ /// Create copy during cloning virtual ViewSel<View>* copy(Space& home); //@} };
/// Select view with least merit taking tie-break limit into account template<class Merit> class ViewSelMinTbl : public ViewSelChooseTbl<ChooseMin,Merit> { typedef typename ViewSelChooseTbl<ChooseMin,Merit>::View View; typedef typename ViewSelChooseTbl<ChooseMin,Merit>::Var Var; public: /// \name Initialization //@{ /// Constructor for initialization ViewSelMinTbl(Space& home, const VarBranch<Var>& vb); /// Constructor for copying during cloning ViewSelMinTbl(Space& home, ViewSelMinTbl<Merit>& vs); //@} /// \name Resource management and cloning //@{ /// Create copy during cloning virtual ViewSel<View>* copy(Space& home); //@} };
/// Select view with largest merit template<class Merit> class ViewSelMax : public ViewSelChoose<ChooseMax,Merit> { typedef typename ViewSelChoose<ChooseMax,Merit>::View View; typedef typename ViewSelChoose<ChooseMax,Merit>::Var Var; public: /// \name Initialization //@{ /// Constructor for initialization ViewSelMax(Space& home, const VarBranch<Var>& vb); /// Constructor for copying during cloning ViewSelMax(Space& home, ViewSelMax<Merit>& vs); //@} /// \name Resource management and cloning //@{ /// Create copy during cloning virtual ViewSel<View>* copy(Space& home); //@} };
/// Select view with largest merit taking tie-break limit into account template<class Merit> class ViewSelMaxTbl : public ViewSelChooseTbl<ChooseMax,Merit> { typedef typename ViewSelChooseTbl<ChooseMax,Merit>::View View; typedef typename ViewSelChooseTbl<ChooseMax,Merit>::Var Var; public: /// \name Initialization //@{ /// Constructor for initialization ViewSelMaxTbl(Space& home, const VarBranch<Var>& vb); /// Constructor for copying during cloning ViewSelMaxTbl(Space& home, ViewSelMaxTbl<Merit>& vs); //@} /// \name Resource management and cloning //@{ /// Create copy during cloning virtual ViewSel<View>* copy(Space& home); //@} }; //@}
template<class View> forceinline ViewSel<View>::ViewSel(Space&, const VarBranch<Var>&) {} template<class View> forceinline ViewSel<View>::ViewSel(Space&, ViewSel<View>&) {} template<class View> int ViewSel<View>::select(Space&, ViewArray<View>&, int, BrancherNoFilter<View>&) { GECODE_NEVER; return 0; } template<class View> void ViewSel<View>::ties(Space&, ViewArray<View>&, int, int*, int&, BrancherNoFilter<View>&) { GECODE_NEVER; } template<class View> bool ViewSel<View>::notice(void) const { return false; } template<class View> void ViewSel<View>::dispose(Space&) {} template<class View> ViewSel<View>::~ViewSel(void) {} template<class View> forceinline void ViewSel<View>::operator delete(void*) {} template<class View> forceinline void ViewSel<View>::operator delete(void*, Space&) {} template<class View> forceinline void* ViewSel<View>::operator new(size_t s, Space& home) { return home.ralloc(s); }
template<class View> forceinline ViewSelNone<View>::ViewSelNone(Space& home, const VarBranch<Var>& vb) : ViewSel<View>(home,vb) {} template<class View> forceinline ViewSelNone<View>::ViewSelNone(Space& home, ViewSelNone<View>& vs) : ViewSel<View>(home,vs) {} template<class View> int ViewSelNone<View>::select(Space&, ViewArray<View>&, int s) { return s; } template<class View> int ViewSelNone<View>::select(Space&, ViewArray<View>&, int s, BrancherFilter<View>&) { return s; } template<class View> void ViewSelNone<View>::ties(Space&, ViewArray<View>& x, int s, int* ties, int& n) { int j=0; ties[j++]=s; for (int i=s+1; i<x.size(); i++) if (!x[i].assigned()) ties[j++]=i; n=j; assert(n > 0); } template<class View> void ViewSelNone<View>::ties(Space& home, ViewArray<View>& x, int s, int* ties, int& n, BrancherFilter<View>& f) { int j=0; ties[j++]=s; for (int i=s+1; i<x.size(); i++) if (!x[i].assigned() && f(home,x[i],i)) ties[j++]=i; n=j; assert(n > 0); } template<class View> void ViewSelNone<View>::brk(Space&, ViewArray<View>&, int*, int&) { // Nothing needs to be done } template<class View> int ViewSelNone<View>::select(Space&, ViewArray<View>&, int* ties, int) { return ties[0]; } template<class View> ViewSel<View>* ViewSelNone<View>::copy(Space& home) { return new (home) ViewSelNone<View>(home,*this); }
template<class View> forceinline ViewSelRnd<View>::ViewSelRnd(Space& home, const VarBranch<Var>& vb) : ViewSel<View>(home,vb), r(vb.rnd()) {} template<class View> forceinline ViewSelRnd<View>::ViewSelRnd(Space& home, ViewSelRnd<View>& vs) : ViewSel<View>(home,vs), r(vs.r) {} template<class View> int ViewSelRnd<View>::select(Space&, ViewArray<View>& x, int s) { unsigned int n=1; int j=s; for (int i=s+1; i<x.size(); i++) if (!x[i].assigned()) { n++; if (r(n) == 0U) j=i; } return j; } template<class View> int ViewSelRnd<View>::select(Space& home, ViewArray<View>& x, int s, BrancherFilter<View>& f) { unsigned int n=1; int j=s; for (int i=s+1; i<x.size(); i++) if (!x[i].assigned() && f(home,x[i],i)) { n++; if (r(n) == 0U) j=i; } return j; } template<class View> void ViewSelRnd<View>::ties(Space& home, ViewArray<View>& x, int s, int* ties, int& n) { n=1; ties[0] = select(home,x,s); } template<class View> void ViewSelRnd<View>::ties(Space& home, ViewArray<View>& x, int s, int* ties, int& n, BrancherFilter<View>&) { n=1; ties[0] = select(home,x,s); } template<class View> void ViewSelRnd<View>::brk(Space&, ViewArray<View>&, int* ties, int& n) { ties[0] = ties[static_cast<int>(r(static_cast<unsigned int>(n)))]; n=1; } template<class View> int ViewSelRnd<View>::select(Space&, ViewArray<View>&, int* ties, int n) { return ties[static_cast<int>(r(static_cast<unsigned int>(n)))]; } template<class View> ViewSel<View>* ViewSelRnd<View>::copy(Space& home) { return new (home) ViewSelRnd<View>(home,*this); }
template<class Val> forceinline bool ChooseMin::operator ()(Val a, Val b) const { return a < b; } template<class Val> forceinline bool ChooseMax::operator ()(Val a, Val b) const { return a > b; }
template<class Choose, class Merit> forceinline ViewSelChoose<Choose,Merit>::ViewSelChoose(Space& home, const VarBranch<Var>& vb) : ViewSel<View>(home,vb), m(home,vb) {}
template<class Choose, class Merit> forceinline ViewSelChoose<Choose,Merit>::ViewSelChoose(Space& home, ViewSelChoose<Choose,Merit>& vs) : ViewSel<View>(home,vs), m(home,vs.m) {}
template<class Choose, class Merit> int ViewSelChoose<Choose,Merit>::select(Space& home, ViewArray<View>& x, int s) { // Consider x[s] as the so-far best view int b_i = s; Val b_m = m(home,x[s],s); // Scan all non-assigned views from s+1 onwards for (int i=s+1; i<x.size(); i++) if (!x[i].assigned()) { Val mxi = m(home,x[i],i); if (c(mxi,b_m)) { b_i = i; b_m = mxi; } } return b_i; }
template<class Choose, class Merit> int ViewSelChoose<Choose,Merit>::select(Space& home, ViewArray<View>& x, int s, BrancherFilter<View>& f) { // Consider x[s] as the so-far best view int b_i = s; Val b_m = m(home,x[s],s); // Scan all non-assigned views from s+1 onwards for (int i=s+1; i<x.size(); i++) if (!x[i].assigned() && f(home,x[i],i)) { Val mxi = m(home,x[i],i); if (c(mxi,b_m)) { b_i = i; b_m = mxi; } } return b_i; }
template<class Choose, class Merit> void ViewSelChoose<Choose,Merit>::ties(Space& home, ViewArray<View>& x, int s, int* ties, int& n) { // Consider x[s] as the so-far best view and record as tie Val b = m(home,x[s],s); int j=0; ties[j++]=s; for (int i=s+1; i<x.size(); i++) if (!x[i].assigned()) { Val mxi = m(home,x[i],i); if (c(mxi,b)) { // Found a better one, reset all ties and record j=0; ties[j++]=i; b=mxi; } else if (mxi == b) { // Found a tie, record ties[j++]=i; } } n=j; // There must be at least one tie, of course! assert(n > 0); }
template<class Choose, class Merit> void ViewSelChoose<Choose,Merit>::ties(Space& home, ViewArray<View>& x, int s, int* ties, int& n, BrancherFilter<View>& f) { // Consider x[s] as the so-far best view and record as tie Val b = m(home,x[s],s); int j=0; ties[j++]=s; for (int i=s+1; i<x.size(); i++) if (!x[i].assigned() && f(home,x[i],i)) { Val mxi = m(home,x[i],i); if (c(mxi,b)) { // Found a better one, reset all ties and record j=0; ties[j++]=i; b=mxi; } else if (mxi == b) { // Found a tie, record ties[j++]=i; } } n=j; // There must be at least one tie, of course! assert(n > 0); }
template<class Choose, class Merit> void ViewSelChoose<Choose,Merit>::brk(Space& home, ViewArray<View>& x, int* ties, int& n) { // Keep first tie in place Val b = m(home,x[ties[0]],ties[0]); int j=1; // Scan remaining ties for (int i=1; i<n; i++) { Val mxi = m(home,x[ties[i]],ties[i]); if (c(mxi,b)) { // Found a better one, reset all ties b=mxi; j=0; ties[j++]=ties[i]; } else if (mxi == b) { // Found a tie and record it ties[j++]=ties[i]; } } n=j; // There must be at least one tie, of course! assert(n > 0); }
template<class Choose, class Merit> int ViewSelChoose<Choose,Merit>::select(Space& home, ViewArray<View>& x, int* ties, int n) { int b_i = ties[0]; Val b_m = m(home,x[ties[0]],ties[0]); for (int i=1; i<n; i++) { Val mxi = m(home,x[ties[i]],ties[i]); if (c(mxi,b_m)) { b_i = ties[i]; b_m = mxi; } } return b_i; }
template<class Choose, class Merit> bool ViewSelChoose<Choose,Merit>::notice(void) const { return m.notice(); }
template<class Choose, class Merit> void ViewSelChoose<Choose,Merit>::dispose(Space& home) { m.dispose(home); }
template<class Choose, class Merit> forceinline ViewSelChooseTbl<Choose,Merit>::ViewSelChooseTbl(Space& home, const VarBranch<Var>& vb) : ViewSelChoose<Choose,Merit>(home,vb), tbl(vb.tbl()) { if (!tbl()) throw InvalidFunction("ViewSelChooseTbl::ViewSelChooseTbl"); }
template<class Choose, class Merit> forceinline ViewSelChooseTbl<Choose,Merit>::ViewSelChooseTbl (Space& home, ViewSelChooseTbl<Choose,Merit>& vs) : ViewSelChoose<Choose,Merit>(home,vs), tbl(vs.tbl) { }
template<class Choose, class Merit> void ViewSelChooseTbl<Choose,Merit>::ties(Space& home, ViewArray<View>& x, int s, int* ties, int& n) { // Find the worst and best merit value Val w = m(home,x[s],s); Val b = w; for (int i=s+1; i<x.size(); i++) if (!x[i].assigned()) { Val mxi = m(home,x[i],i); if (c(mxi,b)) b=mxi; else if (c(w,mxi)) w=mxi; } // Compute tie-break limit GECODE_VALID_FUNCTION(tbl()); double l = tbl()(home,static_cast<double>(w),static_cast<double>(b)); // If the limit is not better than the worst merit, everything is a tie if (!c(l,static_cast<double>(w))) { int j=0; for (int i=s; i<x.size(); i++) if (!x[i].assigned()) ties[j++]=i; n=j; } else { // The limit is not allowed to better than the best merit value if (c(l,static_cast<double>(b))) l = static_cast<double>(b); // Record all ties that are not worse than the limit merit value int j=0; for (int i=s; i<x.size(); i++) if (!x[i].assigned() && !c(l,static_cast<double>(m(home,x[i],i)))) ties[j++]=i; n=j; } // There will be at least one tie (the best will qualify, of course) assert(n > 0); }
template<class Choose, class Merit> void ViewSelChooseTbl<Choose,Merit>::ties(Space& home, ViewArray<View>& x, int s, int* ties, int& n, BrancherFilter<View>& f) { // Find the worst and best merit value assert(f(home,x[s],s)); Val w = m(home,x[s],s); Val b = w; for (int i=s+1; i<x.size(); i++) if (!x[i].assigned() && f(home,x[i],i)) { Val mxi = m(home,x[i],i); if (c(mxi,b)) b=mxi; else if (c(w,mxi)) w=mxi; } // Compute tie-break limit GECODE_VALID_FUNCTION(tbl()); double l = tbl()(home,static_cast<double>(w),static_cast<double>(b)); // If the limit is not better than the worst merit, everything is a tie if (!c(l,static_cast<double>(w))) { int j=0; for (int i=s; i<x.size(); i++) if (!x[i].assigned() && f(home,x[i],i)) ties[j++]=i; n=j; } else { // The limit is not allowed to better than the best merit value if (c(l,static_cast<double>(b))) l = static_cast<double>(b); // Record all ties that are not worse than the limit merit value int j=0; for (int i=s; i<x.size(); i++) if (!x[i].assigned() && f(home,x[i],i) && !c(l,static_cast<double>(m(home,x[i],i)))) ties[j++]=i; n=j; } // There will be at least one tie (the best will qualify, of course) assert(n > 0); }
template<class Choose, class Merit> void ViewSelChooseTbl<Choose,Merit>::brk(Space& home, ViewArray<View>& x, int* ties, int& n) { // Find the worst and best merit value Val w = m(home,x[ties[0]],ties[0]); Val b = w; for (int i=1; i<n; i++) { Val mxi = m(home,x[ties[i]],ties[i]); if (c(mxi,b)) b=mxi; else if (c(w,mxi)) w=mxi; } // Compute tie-break limit GECODE_VALID_FUNCTION(tbl()); double l = tbl()(home,static_cast<double>(w),static_cast<double>(b)); // If the limit is not better than the worst merit, everything is a tie // and no breaking is required if (c(l,static_cast<double>(w))) { // The limit is not allowed to better than the best merit value if (c(l,static_cast<double>(b))) l = static_cast<double>(b); // Keep all ties that are not worse than the limit merit value int j=0; for (int i=0; i<n; i++) if (!c(l,static_cast<double>(m(home,x[ties[i]],ties[i])))) ties[j++]=ties[i]; n=j; } // There will be at least one tie (the best will qualify) assert(n > 0); } template<class Choose, class Merit> bool ViewSelChooseTbl<Choose,Merit>::notice(void) const { return true; } template<class Choose, class Merit> void ViewSelChooseTbl<Choose,Merit>::dispose(Space&) { tbl.~SharedData<BranchTbl>(); }
template<class Merit> forceinline ViewSelMin<Merit>::ViewSelMin(Space& home, const VarBranch<Var>& vb) : ViewSelChoose<ChooseMin,Merit>(home,vb) {}
template<class Merit> forceinline ViewSelMin<Merit>::ViewSelMin(Space& home, ViewSelMin<Merit>& vs) : ViewSelChoose<ChooseMin,Merit>(home,vs) {}
template<class Merit> ViewSel<typename ViewSelMin<Merit>::View>* ViewSelMin<Merit>::copy(Space& home) { return new (home) ViewSelMin<Merit>(home,*this); }
template<class Merit> forceinline ViewSelMinTbl<Merit>::ViewSelMinTbl(Space& home, const VarBranch<Var>& vb) : ViewSelChooseTbl<ChooseMin,Merit>(home,vb) {}
template<class Merit> forceinline ViewSelMinTbl<Merit>::ViewSelMinTbl(Space& home, ViewSelMinTbl<Merit>& vs) : ViewSelChooseTbl<ChooseMin,Merit>(home,vs) {}
template<class Merit> ViewSel<typename ViewSelMinTbl<Merit>::View>* ViewSelMinTbl<Merit>::copy(Space& home) { return new (home) ViewSelMinTbl<Merit>(home,*this); }
template<class Merit> forceinline ViewSelMax<Merit>::ViewSelMax(Space& home, const VarBranch<Var>& vb) : ViewSelChoose<ChooseMax,Merit>(home,vb) {}
template<class Merit> forceinline ViewSelMax<Merit>::ViewSelMax(Space& home, ViewSelMax<Merit>& vs) : ViewSelChoose<ChooseMax,Merit>(home,vs) {}
template<class Merit> ViewSel<typename ViewSelMax<Merit>::View>* ViewSelMax<Merit>::copy(Space& home) { return new (home) ViewSelMax<Merit>(home,*this); }
template<class Merit> forceinline ViewSelMaxTbl<Merit>::ViewSelMaxTbl(Space& home, const VarBranch<Var>& vb) : ViewSelChooseTbl<ChooseMax,Merit>(home,vb) {}
template<class Merit> forceinline ViewSelMaxTbl<Merit>::ViewSelMaxTbl(Space& home, ViewSelMaxTbl<Merit>& vs) : ViewSelChooseTbl<ChooseMax,Merit>(home,vs) {}
template<class Merit> ViewSel<typename ViewSelMaxTbl<Merit>::View>* ViewSelMaxTbl<Merit>::copy(Space& home) { return new (home) ViewSelMaxTbl<Merit>(home,*this); }
}
// STATISTICS: kernel-branch