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-09-01 12:02:08 +0200 (Wed, 01 Sep 2010) $ by $Author: schulte $ 00011 * $Revision: 11371 $ 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, BranchFilter bf); 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, BranchFilter bf=NULL); 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