text: /* -*- 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
  