Generated on Mon May 10 06:46:34 2010 for Gecode by doxygen 1.6.3

branch.hh

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2002
00008  *
00009  *  Last modified:
00010  *     $Date: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $
00011  *     $Revision: 10684 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #ifndef __GECODE_INT_BRANCH_HH__
00039 #define __GECODE_INT_BRANCH_HH__
00040 
00041 #include <gecode/int.hh>
00042 
00048 namespace Gecode { namespace Int { namespace Branch {
00049 
00050   /*
00051    * Value selection classes
00052    *
00053    */
00054 
00062   template<class View>
00063   class ValMin : public ValSelBase<View,int> {
00064   public:
00066     ValMin(void);
00068     ValMin(Space& home, const ValBranchOptions& vbo);
00070     int val(Space& home, View x) const;
00072     ModEvent tell(Space& home, unsigned int a, View x, int n);
00073   };
00074 
00082   template<class View>
00083   class ValMed : public ValSelBase<View,int> {
00084   public:
00086     ValMed(void);
00088     ValMed(Space& home, const ValBranchOptions& vbo);
00090     int val(Space& home, View x) const;
00092     ModEvent tell(Space& home, unsigned int a, View x, int n);
00093   };
00094 
00102   template<class _View>
00103   class ValRnd {
00104   protected:
00106     Support::RandomGenerator r;
00107   public:
00109     typedef _View View;
00111     typedef int Val;
00113     typedef Support::RandomGenerator Choice;
00115     static const unsigned int alternatives = 2;
00117     ValRnd(void);
00119     ValRnd(Space& home, const ValBranchOptions& vbo);
00121     int val(Space& home, _View x);
00123     ModEvent tell(Space& home, unsigned int a, _View x, int n);
00125     Support::RandomGenerator choice(Space& home);
00127     void commit(Space& home, const Support::RandomGenerator& c, unsigned a);
00129     void update(Space& home, bool share, ValRnd& vs);
00131     void dispose(Space& home);
00132   };
00133 
00142   template<class View>
00143   class ValSplitMin : public ValSelBase<View,int> {
00144   public:
00146     ValSplitMin(void);
00148     ValSplitMin(Space& home, const ValBranchOptions& vbo);
00150     int val(Space& home, View x) const;
00152     ModEvent tell(Space& home, unsigned int a, View x, int n);
00153   };
00154 
00155 
00164   template<class View>
00165   class ValRangeMin : public ValSelBase<View,int> {
00166   public:
00168     ValRangeMin(void);
00170     ValRangeMin(Space& home, const ValBranchOptions& vbo);
00172     int val(Space& home, View x) const;
00174     ModEvent tell(Space& home, unsigned int a, View x, int n);
00175   };
00176 
00177 
00179   class NoValue {};
00180 
00188   template<class View>
00189   class ValZeroOne : public ValSelBase<View,NoValue> {
00190   public:
00192     ValZeroOne(void);
00194     ValZeroOne(Space& home, const ValBranchOptions& vbo);
00196     NoValue val(Space& home, View x) const;
00198     ModEvent tell(Space& home, unsigned int a, View x, NoValue n);
00199   };
00200 
00201 
00206   template<class ViewSel, class View>
00207   class ViewValuesBrancher : public ViewBrancher<ViewSel> {
00208   protected:
00209     using ViewBrancher<ViewSel>::x;
00210     using ViewBrancher<ViewSel>::viewsel;
00212     ViewValuesBrancher(Space& home, bool share, ViewValuesBrancher& b);
00214     ViewValuesBrancher(Home home, ViewArray<typename ViewSel::View>& x,
00215                        ViewSel& vi_s);
00216   public:
00218     virtual const Choice* choice(Space& home);
00220     virtual ExecStatus commit(Space& home, const Choice& c, unsigned int a);
00222     virtual Actor* copy(Space& home, bool share);
00224     static void post(Home home, ViewArray<typename ViewSel::View>& x,
00225                      ViewSel& vi_s);
00226   };
00227 
00228 
00230   template<class View>
00231   class AssignValMin : public ValMin<View> {
00232   public:
00234     static const unsigned int alternatives = 1;
00236     AssignValMin(void);
00238     AssignValMin(Space& home, const ValBranchOptions& vbo);
00239   };
00240 
00242   template<class View>
00243   class AssignValMed : public ValMed<View> {
00244   public:
00246     static const unsigned int alternatives = 1;
00248     AssignValMed(void);
00250     AssignValMed(Space& home, const ValBranchOptions& vbo);
00251   };
00252 
00254   template<class View>
00255   class AssignValRnd : public ValRnd<View> {
00256   public:
00258     static const unsigned int alternatives = 1;
00260     AssignValRnd(void);
00262     AssignValRnd(Space& home, const ValBranchOptions& vbo);
00263   };
00264 
00266   template<class View>
00267   class AssignValZero : public ValZeroOne<View> {
00268   public:
00270     static const unsigned int alternatives = 1;
00272     AssignValZero(void);
00274     AssignValZero(Space& home, const ValBranchOptions& vbo);
00275   };
00276 
00277   /*
00278    * Variable selection classes
00279    *
00280    */
00281 
00288   class ByMinMin : public ViewSelBase<IntView> {
00289   protected:
00291     int min;
00292   public:
00294     ByMinMin(void);
00296     ByMinMin(Space& home, const VarBranchOptions& vbo);
00298     ViewSelStatus init(Space& home, IntView x);
00300     ViewSelStatus select(Space& home, IntView x);
00301   };
00302 
00309   class ByMinMax : public ViewSelBase<IntView> {
00310   protected:
00312     int min;
00313   public:
00315     ByMinMax(void);
00317     ByMinMax(Space& home, const VarBranchOptions& vbo);
00319     ViewSelStatus init(Space& home, IntView x);
00321     ViewSelStatus select(Space& home, IntView x);
00322   };
00323 
00330   class ByMaxMin : public ViewSelBase<IntView> {
00331   protected:
00333     int max;
00334   public:
00336     ByMaxMin(void);
00338     ByMaxMin(Space& home, const VarBranchOptions& vbo);
00340     ViewSelStatus init(Space& home, IntView x);
00342     ViewSelStatus select(Space& home, IntView x);
00343   };
00344 
00351   class ByMaxMax : public ViewSelBase<IntView> {
00352   protected:
00354     int max;
00355   public:
00357     ByMaxMax(void);
00359     ByMaxMax(Space& home, const VarBranchOptions& vbo);
00361     ViewSelStatus init(Space& home, IntView x);
00363     ViewSelStatus select(Space& home, IntView x);
00364   };
00365 
00372   class BySizeMin : public ViewSelBase<IntView> {
00373   protected:
00375     unsigned int size;
00376   public:
00378     BySizeMin(void);
00380     BySizeMin(Space& home, const VarBranchOptions& vbo);
00382     ViewSelStatus init(Space& home, IntView x);
00384     ViewSelStatus select(Space& home, IntView x);
00385   };
00386 
00393   class BySizeMax : public ViewSelBase<IntView> {
00394   protected:
00396     unsigned int size;
00397   public:
00399     BySizeMax(void);
00401     BySizeMax(Space& home, const VarBranchOptions& vbo);
00403     ViewSelStatus init(Space& home, IntView x);
00405     ViewSelStatus select(Space& home, IntView x);
00406   };
00407 
00415   class BySizeDegreeMin : public ViewSelBase<IntView> {
00416   protected:
00418     double sizedegree;
00419   public:
00421     BySizeDegreeMin(void);
00423     BySizeDegreeMin(Space& home, const VarBranchOptions& vbo);
00425     ViewSelStatus init(Space& home, IntView x);
00427     ViewSelStatus select(Space& home, IntView x);
00428   };
00429 
00437   class BySizeDegreeMax : public ViewSelBase<IntView> {
00438   protected:
00440     double sizedegree;
00441   public:
00443     BySizeDegreeMax(void);
00445     BySizeDegreeMax(Space& home, const VarBranchOptions& vbo);
00447     ViewSelStatus init(Space& home, IntView x);
00449     ViewSelStatus select(Space& home, IntView x);
00450   };
00451 
00458   class BySizeAfcMin : public ViewSelBase<IntView> {
00459   protected:
00461     double sizeafc;
00462   public:
00464     BySizeAfcMin(void);
00466     BySizeAfcMin(Space& home, const VarBranchOptions& vbo);
00468     ViewSelStatus init(Space& home, IntView x);
00470     ViewSelStatus select(Space& home, IntView x);
00471   };
00472 
00479   class BySizeAfcMax : public ViewSelBase<IntView> {
00480   protected:
00482     double sizeafc;
00483   public:
00485     BySizeAfcMax(void);
00487     BySizeAfcMax(Space& home, const VarBranchOptions& vbo);
00489     ViewSelStatus init(Space& home, IntView x);
00491     ViewSelStatus select(Space& home, IntView x);
00492   };
00493 
00500   class ByRegretMinMin : public ViewSelBase<IntView> {
00501   protected:
00503     unsigned int regret;
00504   public:
00506     ByRegretMinMin(void);
00508     ByRegretMinMin(Space& home, const VarBranchOptions& vbo);
00510     ViewSelStatus init(Space& home, IntView x);
00512     ViewSelStatus select(Space& home, IntView x);
00513   };
00514 
00521   class ByRegretMinMax : public ViewSelBase<IntView> {
00522   protected:
00524     unsigned int regret;
00525   public:
00527     ByRegretMinMax(void);
00529     ByRegretMinMax(Space& home, const VarBranchOptions& vbo);
00531     ViewSelStatus init(Space& home, IntView x);
00533     ViewSelStatus select(Space& home, IntView x);
00534   };
00535 
00542   class ByRegretMaxMin : public ViewSelBase<IntView> {
00543   protected:
00545     unsigned int regret;
00546   public:
00548     ByRegretMaxMin(void);
00550     ByRegretMaxMin(Space& home, const VarBranchOptions& vbo);
00552     ViewSelStatus init(Space& home, IntView x);
00554     ViewSelStatus select(Space& home, IntView x);
00555   };
00556 
00563   class ByRegretMaxMax : public ViewSelBase<IntView> {
00564   protected:
00566     unsigned int regret;
00567   public:
00569     ByRegretMaxMax(void);
00571     ByRegretMaxMax(Space& home, const VarBranchOptions& vbo);
00573     ViewSelStatus init(Space& home, IntView x);
00575     ViewSelStatus select(Space& home, IntView x);
00576   };
00577 
00578 }}}
00579 
00580 #include <gecode/int/branch/select-val.hpp>
00581 #include <gecode/int/branch/select-values.hpp>
00582 #include <gecode/int/branch/select-view.hpp>
00583 #include <gecode/int/branch/post-val-int.hpp>
00584 #include <gecode/int/branch/post-val-bool.hpp>
00585 
00586 #endif
00587 
00588 // STATISTICS: int-branch