Generated on Sun Feb 17 15:24:25 2019 for Gecode by doxygen 1.6.3

view-sel.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main author:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 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 namespace Gecode {
00035 
00042 
00043   template<class _View>
00044   class ViewSel {
00045   public:
00047     typedef _View View;
00049     typedef typename View::VarType Var;
00051 
00052 
00053     ViewSel(Space& home, const VarBranch<Var>& vb);
00055     ViewSel(Space& home, ViewSel<View>& vs);
00057 
00058 
00059 
00060     virtual int select(Space& home, ViewArray<View>& x, int s) = 0;
00062     virtual int select(Space& home, ViewArray<View>& x, int s,
00063                        BrancherFilter<View>& f) = 0;
00065     virtual int select(Space& home, ViewArray<View>& x, int s,
00066                        BrancherNoFilter<View>& f);
00068     virtual void ties(Space& home, ViewArray<View>& x, int s,
00069                       int* ties, int& n) = 0;
00071     virtual void ties(Space& home, ViewArray<View>& x, int s,
00072                       int* ties, int& n,
00073                       BrancherFilter<View>& f) = 0;
00075     virtual void ties(Space& home, ViewArray<View>& x, int s,
00076                       int* ties, int& n,
00077                       BrancherNoFilter<View>& f);
00079     virtual void brk(Space& home, ViewArray<View>& x,
00080                      int* ties, int& n) = 0;
00082     virtual int select(Space& home, ViewArray<View>& x,
00083                        int* ties, int n) = 0;
00085 
00086 
00087 
00088     virtual ViewSel<View>* copy(Space& home) = 0;
00090     virtual bool notice(void) const;
00092     virtual void dispose(Space& home);
00094     virtual ~ViewSel(void);
00096 
00097 
00098 
00099     static void* operator new(size_t s, Space& home);
00101     static void operator delete(void* p, Space& home);
00103     static void operator delete(void* p);
00105   };
00106 
00108   template<class View>
00109   class ViewSelNone : public ViewSel<View> {
00110   protected:
00111     typedef typename ViewSel<View>::Var Var;
00112   public:
00114 
00115 
00116     ViewSelNone(Space& home, const VarBranch<Var>& vb);
00118     ViewSelNone(Space& home, ViewSelNone<View>& vs);
00120 
00121 
00122 
00123     virtual int select(Space& home, ViewArray<View>& x, int s);
00125     virtual int select(Space& home, ViewArray<View>& x, int s,
00126                        BrancherFilter<View>& f);
00128     virtual void ties(Space& home, ViewArray<View>& x, int s,
00129                       int* ties, int& n);
00131     virtual void ties(Space& home, ViewArray<View>& x, int s,
00132                       int* ties, int& n,
00133                       BrancherFilter<View>& f);
00135     virtual void brk(Space& home, ViewArray<View>& x,
00136                      int* ties, int& n);
00138     virtual int select(Space& home, ViewArray<View>& x, int* ties, int n);
00140 
00141 
00142 
00143     virtual ViewSel<View>* copy(Space& home);
00145   };
00146 
00148   template<class View>
00149   class ViewSelRnd : public ViewSel<View> {
00150   protected:
00151     typedef typename ViewSel<View>::Var Var;
00153     Rnd r;
00154   public:
00156 
00157 
00158     ViewSelRnd(Space& home, const VarBranch<Var>& vb);
00160     ViewSelRnd(Space& home, ViewSelRnd<View>& vs);
00162 
00163 
00164 
00165     virtual int select(Space& home, ViewArray<View>& x, int s);
00167     virtual int select(Space& home, ViewArray<View>& x, int s,
00168                        BrancherFilter<View>& f);
00170     virtual void ties(Space& home, ViewArray<View>& x, int s,
00171                       int* ties, int& n);
00173     virtual void ties(Space& home, ViewArray<View>& x, int s,
00174                       int* ties, int& n,
00175                       BrancherFilter<View>& f);
00177     virtual void brk(Space& home, ViewArray<View>& x, int* ties, int& n);
00179     virtual int select(Space& home, ViewArray<View>& x, int* ties, int n);
00181 
00182 
00183 
00184     virtual ViewSel<View>* copy(Space& home);
00186   };
00187 
00189   class ChooseMin {
00190   public:
00192     template<class Val>
00193     bool operator ()(Val a, Val b) const;
00194   };
00195 
00197   class ChooseMax {
00198   public:
00200     template<class Val>
00201     bool operator ()(Val a, Val b) const;
00202   };
00203 
00205   template<class Choose, class Merit>
00206   class ViewSelChoose : public ViewSel<typename Merit::View> {
00207   protected:
00208     typedef typename ViewSel<typename Merit::View>::Var Var;
00209     typedef typename ViewSel<typename Merit::View>::View View;
00211     typedef typename Merit::Val Val;
00213     Choose c;
00215     Merit m;
00216   public:
00218 
00219 
00220     ViewSelChoose(Space& home, const VarBranch<Var>& vb);
00222     ViewSelChoose(Space& home, ViewSelChoose<Choose,Merit>& vs);
00224 
00225 
00226 
00227     virtual int select(Space& home, ViewArray<View>& x, int s);
00229     virtual int select(Space& home, ViewArray<View>& x, int s,
00230                        BrancherFilter<View>& f);
00232     virtual void ties(Space& home, ViewArray<View>& x, int s,
00233                       int* ties, int& n);
00235     virtual void ties(Space& home, ViewArray<View>& x, int s,
00236                       int* ties, int& n,
00237                       BrancherFilter<View>& f);
00239     virtual void brk(Space& home, ViewArray<View>& x, int* ties, int& n);
00241     virtual int select(Space& home, ViewArray<View>& x, int* ties, int n);
00243 
00244 
00245 
00246     virtual bool notice(void) const;
00248     virtual void dispose(Space& home);
00250   };
00251 
00252 
00254   template<class Choose, class Merit>
00255   class ViewSelChooseTbl : public ViewSelChoose<Choose,Merit> {
00256   protected:
00257     typedef typename ViewSelChoose<Choose,Merit>::Val Val;
00258     typedef typename ViewSelChoose<Choose,Merit>::View View;
00259     typedef typename ViewSelChoose<Choose,Merit>::Var Var;
00260     using ViewSelChoose<Choose,Merit>::c;
00261     using ViewSelChoose<Choose,Merit>::m;
00263     SharedData<BranchTbl> tbl;
00264   public:
00266 
00267 
00268     ViewSelChooseTbl(Space& home, const VarBranch<Var>& vb);
00270     ViewSelChooseTbl(Space& home, ViewSelChooseTbl<Choose,Merit>& vs);
00272 
00273 
00274 
00275     virtual void ties(Space& home, ViewArray<View>& x, int s,
00276                       int* ties, int& n);
00278     virtual void ties(Space& home, ViewArray<View>& x, int s,
00279                       int* ties, int& n,
00280                       BrancherFilter<View>& f);
00282     virtual void brk(Space& home, ViewArray<View>& x, int* ties, int& n);
00284 
00285 
00286 
00287     virtual bool notice(void) const;
00289     virtual void dispose(Space& home);
00291   };
00292 
00294   template<class Merit>
00295   class ViewSelMin : public ViewSelChoose<ChooseMin,Merit> {
00296     typedef typename ViewSelChoose<ChooseMin,Merit>::View View;
00297     typedef typename ViewSelChoose<ChooseMin,Merit>::Var Var;
00298   public:
00300 
00301 
00302     ViewSelMin(Space& home, const VarBranch<Var>& vb);
00304     ViewSelMin(Space& home, ViewSelMin<Merit>& vs);
00306 
00307 
00308 
00309     virtual ViewSel<View>* copy(Space& home);
00311   };
00312 
00314   template<class Merit>
00315   class ViewSelMinTbl : public ViewSelChooseTbl<ChooseMin,Merit> {
00316     typedef typename ViewSelChooseTbl<ChooseMin,Merit>::View View;
00317     typedef typename ViewSelChooseTbl<ChooseMin,Merit>::Var Var;
00318   public:
00320 
00321 
00322     ViewSelMinTbl(Space& home, const VarBranch<Var>& vb);
00324     ViewSelMinTbl(Space& home, ViewSelMinTbl<Merit>& vs);
00326 
00327 
00328 
00329     virtual ViewSel<View>* copy(Space& home);
00331   };
00332 
00334   template<class Merit>
00335   class ViewSelMax : public ViewSelChoose<ChooseMax,Merit> {
00336     typedef typename ViewSelChoose<ChooseMax,Merit>::View View;
00337     typedef typename ViewSelChoose<ChooseMax,Merit>::Var Var;
00338   public:
00340 
00341 
00342     ViewSelMax(Space& home, const VarBranch<Var>& vb);
00344     ViewSelMax(Space& home, ViewSelMax<Merit>& vs);
00346 
00347 
00348 
00349     virtual ViewSel<View>* copy(Space& home);
00351   };
00352 
00354   template<class Merit>
00355   class ViewSelMaxTbl : public ViewSelChooseTbl<ChooseMax,Merit> {
00356     typedef typename ViewSelChooseTbl<ChooseMax,Merit>::View View;
00357     typedef typename ViewSelChooseTbl<ChooseMax,Merit>::Var Var;
00358   public:
00360 
00361 
00362     ViewSelMaxTbl(Space& home, const VarBranch<Var>& vb);
00364     ViewSelMaxTbl(Space& home, ViewSelMaxTbl<Merit>& vs);
00366 
00367 
00368 
00369     virtual ViewSel<View>* copy(Space& home);
00371   };
00373 
00374 
00375   template<class View>
00376   forceinline
00377   ViewSel<View>::ViewSel(Space&, const VarBranch<Var>&) {}
00378   template<class View>
00379   forceinline
00380   ViewSel<View>::ViewSel(Space&, ViewSel<View>&) {}
00381   template<class View>
00382   int
00383   ViewSel<View>::select(Space&, ViewArray<View>&, int,
00384                         BrancherNoFilter<View>&) {
00385     GECODE_NEVER;
00386     return 0;
00387   }
00388   template<class View>
00389   void
00390   ViewSel<View>::ties(Space&, ViewArray<View>&, int,
00391                       int*, int&,
00392                       BrancherNoFilter<View>&) {
00393     GECODE_NEVER;
00394   }
00395   template<class View>
00396   bool
00397   ViewSel<View>::notice(void) const {
00398     return false;
00399   }
00400   template<class View>
00401   void
00402   ViewSel<View>::dispose(Space&) {}
00403   template<class View>
00404   ViewSel<View>::~ViewSel(void) {}
00405   template<class View>
00406   forceinline void
00407   ViewSel<View>::operator delete(void*) {}
00408   template<class View>
00409   forceinline void
00410   ViewSel<View>::operator delete(void*, Space&) {}
00411   template<class View>
00412   forceinline void*
00413   ViewSel<View>::operator new(size_t s, Space& home) {
00414     return home.ralloc(s);
00415   }
00416 
00417 
00418 
00419   template<class View>
00420   forceinline
00421   ViewSelNone<View>::ViewSelNone(Space& home, const VarBranch<Var>& vb)
00422       : ViewSel<View>(home,vb) {}
00423   template<class View>
00424   forceinline
00425   ViewSelNone<View>::ViewSelNone(Space& home, ViewSelNone<View>& vs)
00426     : ViewSel<View>(home,vs) {}
00427   template<class View>
00428   int
00429   ViewSelNone<View>::select(Space&, ViewArray<View>&, int s) {
00430     return s;
00431   }
00432   template<class View>
00433   int
00434   ViewSelNone<View>::select(Space&, ViewArray<View>&, int s,
00435                             BrancherFilter<View>&) {
00436     return s;
00437   }
00438   template<class View>
00439   void
00440   ViewSelNone<View>::ties(Space&, ViewArray<View>& x, int s,
00441                           int* ties, int& n) {
00442     int j=0; ties[j++]=s;
00443     for (int i=s+1; i<x.size(); i++)
00444       if (!x[i].assigned())
00445         ties[j++]=i;
00446     n=j;
00447     assert(n > 0);
00448   }
00449   template<class View>
00450   void
00451   ViewSelNone<View>::ties(Space& home, ViewArray<View>& x, int s,
00452                           int* ties, int& n,
00453                           BrancherFilter<View>& f) {
00454     int j=0; ties[j++]=s;
00455     for (int i=s+1; i<x.size(); i++)
00456       if (!x[i].assigned() && f(home,x[i],i))
00457         ties[j++]=i;
00458     n=j;
00459     assert(n > 0);
00460   }
00461   template<class View>
00462   void
00463   ViewSelNone<View>::brk(Space&, ViewArray<View>&, int*, int&) {
00464     // Nothing needs to be done
00465   }
00466   template<class View>
00467   int
00468   ViewSelNone<View>::select(Space&, ViewArray<View>&, int* ties, int) {
00469     return ties[0];
00470   }
00471   template<class View>
00472   ViewSel<View>*
00473   ViewSelNone<View>::copy(Space& home) {
00474     return new (home) ViewSelNone<View>(home,*this);
00475   }
00476 
00477 
00478   template<class View>
00479   forceinline
00480   ViewSelRnd<View>::ViewSelRnd(Space& home, const VarBranch<Var>& vb)
00481       : ViewSel<View>(home,vb), r(vb.rnd()) {}
00482   template<class View>
00483   forceinline
00484   ViewSelRnd<View>::ViewSelRnd(Space& home, ViewSelRnd<View>& vs)
00485       : ViewSel<View>(home,vs), r(vs.r) {}
00486   template<class View>
00487   int
00488   ViewSelRnd<View>::select(Space&, ViewArray<View>& x, int s) {
00489     unsigned int n=1;
00490     int j=s;
00491     for (int i=s+1; i<x.size(); i++)
00492       if (!x[i].assigned()) {
00493         n++;
00494         if (r(n) == 0U)
00495           j=i;
00496       }
00497     return j;
00498   }
00499   template<class View>
00500   int
00501   ViewSelRnd<View>::select(Space& home, ViewArray<View>& x, int s,
00502                            BrancherFilter<View>& f) {
00503     unsigned int n=1;
00504     int j=s;
00505     for (int i=s+1; i<x.size(); i++)
00506       if (!x[i].assigned() && f(home,x[i],i)) {
00507         n++;
00508         if (r(n) == 0U)
00509           j=i;
00510       }
00511     return j;
00512   }
00513   template<class View>
00514   void
00515   ViewSelRnd<View>::ties(Space& home, ViewArray<View>& x, int s,
00516                          int* ties, int& n) {
00517     n=1; ties[0] = select(home,x,s);
00518   }
00519   template<class View>
00520   void
00521   ViewSelRnd<View>::ties(Space& home, ViewArray<View>& x, int s,
00522                          int* ties, int& n,
00523                          BrancherFilter<View>&) {
00524     n=1; ties[0] = select(home,x,s);
00525   }
00526   template<class View>
00527   void
00528   ViewSelRnd<View>::brk(Space&, ViewArray<View>&, int* ties, int& n) {
00529     ties[0] = ties[static_cast<int>(r(static_cast<unsigned int>(n)))];
00530     n=1;
00531   }
00532   template<class View>
00533   int
00534   ViewSelRnd<View>::select(Space&, ViewArray<View>&, int* ties, int n) {
00535     return ties[static_cast<int>(r(static_cast<unsigned int>(n)))];
00536   }
00537   template<class View>
00538   ViewSel<View>*
00539   ViewSelRnd<View>::copy(Space& home) {
00540     return new (home) ViewSelRnd<View>(home,*this);
00541   }
00542 
00543 
00544   template<class Val>
00545   forceinline bool
00546   ChooseMin::operator ()(Val a, Val b) const {
00547     return a < b;
00548   }
00549   template<class Val>
00550   forceinline bool
00551   ChooseMax::operator ()(Val a, Val b) const {
00552     return a > b;
00553   }
00554 
00555 
00556   template<class Choose, class Merit>
00557   forceinline
00558   ViewSelChoose<Choose,Merit>::ViewSelChoose(Space& home, const VarBranch<Var>& vb)
00559     : ViewSel<View>(home,vb), m(home,vb) {}
00560 
00561   template<class Choose, class Merit>
00562   forceinline
00563   ViewSelChoose<Choose,Merit>::ViewSelChoose(Space& home,
00564                                              ViewSelChoose<Choose,Merit>& vs)
00565     : ViewSel<View>(home,vs), m(home,vs.m) {}
00566 
00567   template<class Choose, class Merit>
00568   int
00569   ViewSelChoose<Choose,Merit>::select(Space& home, ViewArray<View>& x, int s) {
00570     // Consider x[s] as the so-far best view
00571     int b_i = s;
00572     Val b_m = m(home,x[s],s);
00573     // Scan all non-assigned views from s+1 onwards
00574     for (int i=s+1; i<x.size(); i++)
00575       if (!x[i].assigned()) {
00576         Val mxi = m(home,x[i],i);
00577         if (c(mxi,b_m)) {
00578           b_i = i; b_m = mxi;
00579         }
00580       }
00581     return b_i;
00582   }
00583 
00584   template<class Choose, class Merit>
00585   int
00586   ViewSelChoose<Choose,Merit>::select(Space& home, ViewArray<View>& x, int s,
00587                                       BrancherFilter<View>& f) {
00588     // Consider x[s] as the so-far best view
00589     int b_i = s;
00590     Val b_m = m(home,x[s],s);
00591     // Scan all non-assigned views from s+1 onwards
00592     for (int i=s+1; i<x.size(); i++)
00593       if (!x[i].assigned() && f(home,x[i],i)) {
00594         Val mxi = m(home,x[i],i);
00595         if (c(mxi,b_m)) {
00596           b_i = i; b_m = mxi;
00597         }
00598       }
00599     return b_i;
00600   }
00601 
00602   template<class Choose, class Merit>
00603   void
00604   ViewSelChoose<Choose,Merit>::ties(Space& home, ViewArray<View>& x, int s,
00605                                     int* ties, int& n) {
00606     // Consider x[s] as the so-far best view and record as tie
00607     Val b = m(home,x[s],s);
00608     int j=0; ties[j++]=s;
00609     for (int i=s+1; i<x.size(); i++)
00610       if (!x[i].assigned()) {
00611         Val mxi = m(home,x[i],i);
00612         if (c(mxi,b)) {
00613           // Found a better one, reset all ties and record
00614           j=0; ties[j++]=i; b=mxi;
00615         } else if (mxi == b) {
00616           // Found a tie, record
00617           ties[j++]=i;
00618         }
00619       }
00620     n=j;
00621     // There must be at least one tie, of course!
00622     assert(n > 0);
00623   }
00624 
00625   template<class Choose, class Merit>
00626   void
00627   ViewSelChoose<Choose,Merit>::ties(Space& home, ViewArray<View>& x, int s,
00628                                     int* ties, int& n,
00629                                     BrancherFilter<View>& f) {
00630     // Consider x[s] as the so-far best view and record as tie
00631     Val b = m(home,x[s],s);
00632     int j=0; ties[j++]=s;
00633     for (int i=s+1; i<x.size(); i++)
00634       if (!x[i].assigned() && f(home,x[i],i)) {
00635         Val mxi = m(home,x[i],i);
00636         if (c(mxi,b)) {
00637           // Found a better one, reset all ties and record
00638           j=0; ties[j++]=i; b=mxi;
00639         } else if (mxi == b) {
00640           // Found a tie, record
00641           ties[j++]=i;
00642         }
00643       }
00644     n=j;
00645     // There must be at least one tie, of course!
00646     assert(n > 0);
00647   }
00648 
00649   template<class Choose, class Merit>
00650   void
00651   ViewSelChoose<Choose,Merit>::brk(Space& home, ViewArray<View>& x,
00652                                    int* ties, int& n) {
00653     // Keep first tie in place
00654     Val b = m(home,x[ties[0]],ties[0]);
00655     int j=1;
00656     // Scan remaining ties
00657     for (int i=1; i<n; i++) {
00658       Val mxi = m(home,x[ties[i]],ties[i]);
00659       if (c(mxi,b)) {
00660         // Found a better one, reset all ties
00661         b=mxi; j=0; ties[j++]=ties[i];
00662       } else if (mxi == b) {
00663         // Found a tie and record it
00664         ties[j++]=ties[i];
00665       }
00666     }
00667     n=j;
00668     // There must be at least one tie, of course!
00669     assert(n > 0);
00670   }
00671 
00672   template<class Choose, class Merit>
00673   int
00674   ViewSelChoose<Choose,Merit>::select(Space& home, ViewArray<View>& x,
00675                                       int* ties, int n) {
00676     int b_i = ties[0];
00677     Val b_m = m(home,x[ties[0]],ties[0]);
00678     for (int i=1; i<n; i++) {
00679       Val mxi = m(home,x[ties[i]],ties[i]);
00680       if (c(mxi,b_m)) {
00681         b_i = ties[i]; b_m = mxi;
00682       }
00683     }
00684     return b_i;
00685   }
00686 
00687   template<class Choose, class Merit>
00688   bool
00689   ViewSelChoose<Choose,Merit>::notice(void) const {
00690     return m.notice();
00691   }
00692 
00693   template<class Choose, class Merit>
00694   void
00695   ViewSelChoose<Choose,Merit>::dispose(Space& home) {
00696     m.dispose(home);
00697   }
00698 
00699 
00700   template<class Choose, class Merit>
00701   forceinline
00702   ViewSelChooseTbl<Choose,Merit>::ViewSelChooseTbl(Space& home,
00703                                                    const VarBranch<Var>& vb)
00704     : ViewSelChoose<Choose,Merit>(home,vb), tbl(vb.tbl()) {
00705     if (!tbl())
00706       throw InvalidFunction("ViewSelChooseTbl::ViewSelChooseTbl");
00707   }
00708 
00709   template<class Choose, class Merit>
00710   forceinline
00711   ViewSelChooseTbl<Choose,Merit>::ViewSelChooseTbl
00712   (Space& home, ViewSelChooseTbl<Choose,Merit>& vs)
00713     : ViewSelChoose<Choose,Merit>(home,vs), tbl(vs.tbl) {
00714   }
00715 
00716   template<class Choose, class Merit>
00717   void
00718   ViewSelChooseTbl<Choose,Merit>::ties(Space& home, ViewArray<View>& x, int s,
00719                                        int* ties, int& n) {
00720     // Find the worst and best merit value
00721     Val w = m(home,x[s],s);
00722     Val b = w;
00723     for (int i=s+1; i<x.size(); i++)
00724       if (!x[i].assigned()) {
00725         Val mxi = m(home,x[i],i);
00726         if (c(mxi,b))
00727           b=mxi;
00728         else if (c(w,mxi))
00729           w=mxi;
00730       }
00731     // Compute tie-break limit
00732     GECODE_VALID_FUNCTION(tbl());
00733     double l = tbl()(home,static_cast<double>(w),static_cast<double>(b));
00734     // If the limit is not better than the worst merit, everything is a tie
00735     if (!c(l,static_cast<double>(w))) {
00736       int j=0;
00737       for (int i=s; i<x.size(); i++)
00738         if (!x[i].assigned())
00739           ties[j++]=i;
00740       n=j;
00741     } else {
00742       // The limit is not allowed to better than the best merit value
00743       if (c(l,static_cast<double>(b)))
00744         l = static_cast<double>(b);
00745       // Record all ties that are not worse than the limit merit value
00746       int j=0;
00747       for (int i=s; i<x.size(); i++)
00748         if (!x[i].assigned() && !c(l,static_cast<double>(m(home,x[i],i))))
00749           ties[j++]=i;
00750       n=j;
00751     }
00752     // There will be at least one tie (the best will qualify, of course)
00753     assert(n > 0);
00754   }
00755 
00756   template<class Choose, class Merit>
00757   void
00758   ViewSelChooseTbl<Choose,Merit>::ties(Space& home, ViewArray<View>& x, int s,
00759                                        int* ties, int& n,
00760                                        BrancherFilter<View>& f) {
00761     // Find the worst and best merit value
00762     assert(f(home,x[s],s));
00763     Val w = m(home,x[s],s);
00764     Val b = w;
00765     for (int i=s+1; i<x.size(); i++)
00766       if (!x[i].assigned() && f(home,x[i],i)) {
00767         Val mxi = m(home,x[i],i);
00768         if (c(mxi,b))
00769           b=mxi;
00770         else if (c(w,mxi))
00771           w=mxi;
00772       }
00773     // Compute tie-break limit
00774     GECODE_VALID_FUNCTION(tbl());
00775     double l = tbl()(home,static_cast<double>(w),static_cast<double>(b));
00776     // If the limit is not better than the worst merit, everything is a tie
00777     if (!c(l,static_cast<double>(w))) {
00778       int j=0;
00779       for (int i=s; i<x.size(); i++)
00780         if (!x[i].assigned() && f(home,x[i],i))
00781           ties[j++]=i;
00782       n=j;
00783     } else {
00784       // The limit is not allowed to better than the best merit value
00785       if (c(l,static_cast<double>(b)))
00786         l = static_cast<double>(b);
00787       // Record all ties that are not worse than the limit merit value
00788       int j=0;
00789       for (int i=s; i<x.size(); i++)
00790         if (!x[i].assigned() && f(home,x[i],i) &&
00791             !c(l,static_cast<double>(m(home,x[i],i))))
00792           ties[j++]=i;
00793       n=j;
00794     }
00795     // There will be at least one tie (the best will qualify, of course)
00796     assert(n > 0);
00797   }
00798 
00799   template<class Choose, class Merit>
00800   void
00801   ViewSelChooseTbl<Choose,Merit>::brk(Space& home, ViewArray<View>& x,
00802                                       int* ties, int& n) {
00803     // Find the worst and best merit value
00804     Val w = m(home,x[ties[0]],ties[0]);
00805     Val b = w;
00806     for (int i=1; i<n; i++) {
00807       Val mxi = m(home,x[ties[i]],ties[i]);
00808       if (c(mxi,b))
00809         b=mxi;
00810       else if (c(w,mxi))
00811         w=mxi;
00812     }
00813     // Compute tie-break limit
00814     GECODE_VALID_FUNCTION(tbl());
00815     double l = tbl()(home,static_cast<double>(w),static_cast<double>(b));
00816     // If the limit is not better than the worst merit, everything is a tie
00817     // and no breaking is required
00818     if (c(l,static_cast<double>(w))) {
00819       // The limit is not allowed to better than the best merit value
00820       if (c(l,static_cast<double>(b)))
00821         l = static_cast<double>(b);
00822       // Keep all ties that are not worse than the limit merit value
00823       int j=0;
00824       for (int i=0; i<n; i++)
00825         if (!c(l,static_cast<double>(m(home,x[ties[i]],ties[i]))))
00826           ties[j++]=ties[i];
00827       n=j;
00828     }
00829     // There will be at least one tie (the best will qualify)
00830     assert(n > 0);
00831   }
00832   template<class Choose, class Merit>
00833   bool
00834   ViewSelChooseTbl<Choose,Merit>::notice(void) const {
00835     return true;
00836   }
00837   template<class Choose, class Merit>
00838   void
00839   ViewSelChooseTbl<Choose,Merit>::dispose(Space&) {
00840     tbl.~SharedData<BranchTbl>();
00841   }
00842 
00843 
00844 
00845   template<class Merit>
00846   forceinline
00847   ViewSelMin<Merit>::ViewSelMin(Space& home, const VarBranch<Var>& vb)
00848     : ViewSelChoose<ChooseMin,Merit>(home,vb) {}
00849 
00850   template<class Merit>
00851   forceinline
00852   ViewSelMin<Merit>::ViewSelMin(Space& home, ViewSelMin<Merit>& vs)
00853     : ViewSelChoose<ChooseMin,Merit>(home,vs) {}
00854 
00855   template<class Merit>
00856   ViewSel<typename ViewSelMin<Merit>::View>*
00857   ViewSelMin<Merit>::copy(Space& home) {
00858     return new (home) ViewSelMin<Merit>(home,*this);
00859   }
00860 
00861 
00862   template<class Merit>
00863   forceinline
00864   ViewSelMinTbl<Merit>::ViewSelMinTbl(Space& home, const VarBranch<Var>& vb)
00865     : ViewSelChooseTbl<ChooseMin,Merit>(home,vb) {}
00866 
00867   template<class Merit>
00868   forceinline
00869   ViewSelMinTbl<Merit>::ViewSelMinTbl(Space& home, ViewSelMinTbl<Merit>& vs)
00870     : ViewSelChooseTbl<ChooseMin,Merit>(home,vs) {}
00871 
00872   template<class Merit>
00873   ViewSel<typename ViewSelMinTbl<Merit>::View>*
00874   ViewSelMinTbl<Merit>::copy(Space& home) {
00875     return new (home) ViewSelMinTbl<Merit>(home,*this);
00876   }
00877 
00878 
00879 
00880   template<class Merit>
00881   forceinline
00882   ViewSelMax<Merit>::ViewSelMax(Space& home, const VarBranch<Var>& vb)
00883     : ViewSelChoose<ChooseMax,Merit>(home,vb) {}
00884 
00885   template<class Merit>
00886   forceinline
00887   ViewSelMax<Merit>::ViewSelMax(Space& home, ViewSelMax<Merit>& vs)
00888     : ViewSelChoose<ChooseMax,Merit>(home,vs) {}
00889 
00890   template<class Merit>
00891   ViewSel<typename ViewSelMax<Merit>::View>*
00892   ViewSelMax<Merit>::copy(Space& home) {
00893     return new (home) ViewSelMax<Merit>(home,*this);
00894   }
00895 
00896 
00897 
00898   template<class Merit>
00899   forceinline
00900   ViewSelMaxTbl<Merit>::ViewSelMaxTbl(Space& home, const VarBranch<Var>& vb)
00901     : ViewSelChooseTbl<ChooseMax,Merit>(home,vb) {}
00902 
00903   template<class Merit>
00904   forceinline
00905   ViewSelMaxTbl<Merit>::ViewSelMaxTbl(Space& home, ViewSelMaxTbl<Merit>& vs)
00906     : ViewSelChooseTbl<ChooseMax,Merit>(home,vs) {}
00907 
00908   template<class Merit>
00909   ViewSel<typename ViewSelMaxTbl<Merit>::View>*
00910   ViewSelMaxTbl<Merit>::copy(Space& home) {
00911     return new (home) ViewSelMaxTbl<Merit>(home,*this);
00912   }
00913 
00914 
00915 
00916 }
00917 
00918 // STATISTICS: kernel-branch