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 * Guido Tack <tack@gecode.org> 00005 * Christian Schulte <schulte@gecode.org> 00006 * 00007 * Contributing authors: 00008 * Gabor Szokoli <szokoli@gecode.org> 00009 * 00010 * Copyright: 00011 * Guido Tack, 2004 00012 * Christian Schulte, 2004 00013 * Gabor Szokoli, 2004 00014 * 00015 * Last modified: 00016 * $Date: 2010-03-30 09:28:15 +0200 (Tue, 30 Mar 2010) $ by $Author: schulte $ 00017 * $Revision: 10593 $ 00018 * 00019 * This file is part of Gecode, the generic constraint 00020 * development environment: 00021 * http://www.gecode.org 00022 * 00023 * Permission is hereby granted, free of charge, to any person obtaining 00024 * a copy of this software and associated documentation files (the 00025 * "Software"), to deal in the Software without restriction, including 00026 * without limitation the rights to use, copy, modify, merge, publish, 00027 * distribute, sublicense, and/or sell copies of the Software, and to 00028 * permit persons to whom the Software is furnished to do so, subject to 00029 * the following conditions: 00030 * 00031 * The above copyright notice and this permission notice shall be 00032 * included in all copies or substantial portions of the Software. 00033 * 00034 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00035 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00036 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00037 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00038 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00039 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00040 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00041 * 00042 */ 00043 00044 #ifndef __GECODE_SET_BRANCH_HH__ 00045 #define __GECODE_SET_BRANCH_HH__ 00046 00047 #include <gecode/set.hh> 00048 00054 namespace Gecode { namespace Set { namespace Branch { 00055 00056 /* 00057 * Value selection classes 00058 * 00059 */ 00060 00061 00069 template<bool inc> 00070 class ValMin : public ValSelBase<SetView,int> { 00071 public: 00073 ValMin(void); 00075 ValMin(Space& home, const ValBranchOptions& vbo); 00077 int val(Space& home, SetView x) const; 00079 ModEvent tell(Space& home, unsigned int a, SetView x, int v); 00080 }; 00081 00089 template<bool inc> 00090 class ValMed : public ValSelBase<SetView,int> { 00091 public: 00093 ValMed(void); 00095 ValMed(Space& home, const ValBranchOptions& vbo); 00097 int val(Space& home, SetView x) const; 00099 ModEvent tell(Space& home, unsigned int a, SetView x, int v); 00100 }; 00101 00109 template<bool inc> 00110 class ValMax : public ValSelBase<SetView,int> { 00111 public: 00113 ValMax(void); 00115 ValMax(Space& home, const ValBranchOptions& vbo); 00117 int val(Space& home, SetView x) const; 00119 ModEvent tell(Space& home, unsigned int a, SetView x, int v); 00120 }; 00121 00129 template<bool inc> 00130 class ValRnd { 00131 protected: 00133 Support::RandomGenerator r; 00134 public: 00136 typedef SetView View; 00138 typedef int Val; 00140 typedef Support::RandomGenerator Choice; 00142 static const unsigned int alternatives = 2; 00144 ValRnd(void); 00146 ValRnd(Space& home, const ValBranchOptions& vbo); 00148 int val(Space& home, SetView x); 00150 ModEvent tell(Space& home, unsigned int a, SetView x, int n); 00152 Support::RandomGenerator choice(Space& home); 00154 void commit(Space& home, const Support::RandomGenerator& c, unsigned a); 00156 void update(Space& home, bool share, ValRnd& vs); 00158 void dispose(Space& home); 00159 }; 00160 00162 template<bool inc> 00163 class AssignValMin : public ValMin<inc> { 00164 public: 00166 static const unsigned int alternatives = 1; 00168 AssignValMin(void); 00170 AssignValMin(Space& home, const ValBranchOptions& vbo); 00171 }; 00172 00174 template<bool inc> 00175 class AssignValMed : public ValMed<inc> { 00176 public: 00178 static const unsigned int alternatives = 1; 00180 AssignValMed(void); 00182 AssignValMed(Space& home, const ValBranchOptions& vbo); 00183 }; 00184 00186 template<bool inc> 00187 class AssignValMax : public ValMax<inc> { 00188 public: 00190 static const unsigned int alternatives = 1; 00192 AssignValMax(void); 00194 AssignValMax(Space& home, const ValBranchOptions& vbo); 00195 }; 00196 00198 template<bool inc> 00199 class AssignValRnd : public ValRnd<inc> { 00200 public: 00202 static const unsigned int alternatives = 1; 00204 AssignValRnd(void); 00206 AssignValRnd(Space& home, const ValBranchOptions& vbo); 00207 }; 00208 00209 /* 00210 * View selection classes 00211 * 00212 */ 00213 00220 class ByMinMin : public ViewSelBase<SetView> { 00221 private: 00223 int min; 00224 public: 00226 ByMinMin(void); 00228 ByMinMin(Space& home, const VarBranchOptions& vbo); 00230 ViewSelStatus init(Space& home, SetView x); 00232 ViewSelStatus select(Space& home, SetView x); 00233 }; 00234 00241 class ByMinMax : public ViewSelBase<SetView> { 00242 private: 00244 int min; 00245 public: 00247 ByMinMax(void); 00249 ByMinMax(Space& home, const VarBranchOptions& vbo); 00251 ViewSelStatus init(Space& home, SetView x); 00253 ViewSelStatus select(Space& home, SetView x); 00254 }; 00255 00262 class ByMaxMin : public ViewSelBase<SetView> { 00263 private: 00265 int max; 00266 public: 00268 ByMaxMin(void); 00270 ByMaxMin(Space& home, const VarBranchOptions& vbo); 00272 ViewSelStatus init(Space& home, SetView x); 00274 ViewSelStatus select(Space& home, SetView x); 00275 }; 00276 00283 class ByMaxMax : public ViewSelBase<SetView> { 00284 private: 00286 int max; 00287 public: 00289 ByMaxMax(void); 00291 ByMaxMax(Space& home, const VarBranchOptions& vbo); 00293 ViewSelStatus init(Space& home, SetView x); 00295 ViewSelStatus select(Space& home, SetView x); 00296 }; 00297 00304 class BySizeMin : public ViewSelBase<SetView> { 00305 private: 00307 unsigned int size; 00308 public: 00310 BySizeMin(void); 00312 BySizeMin(Space& home, const VarBranchOptions& vbo); 00314 ViewSelStatus init(Space& home, SetView x); 00316 ViewSelStatus select(Space& home, SetView x); 00317 }; 00318 00325 class BySizeMax : public ViewSelBase<SetView> { 00326 private: 00328 unsigned int size; 00329 public: 00331 BySizeMax(void); 00333 BySizeMax(Space& home, const VarBranchOptions& vbo); 00335 ViewSelStatus init(Space& home, SetView x); 00337 ViewSelStatus select(Space& home, SetView x); 00338 }; 00339 00347 class BySizeDegreeMin : public ViewSelBase<SetView> { 00348 protected: 00350 double sizedegree; 00351 public: 00353 BySizeDegreeMin(void); 00355 BySizeDegreeMin(Space& home, const VarBranchOptions& vbo); 00357 ViewSelStatus init(Space& home, SetView x); 00359 ViewSelStatus select(Space& home, SetView x); 00360 }; 00361 00369 class BySizeDegreeMax : public ViewSelBase<SetView> { 00370 protected: 00372 double sizedegree; 00373 public: 00375 BySizeDegreeMax(void); 00377 BySizeDegreeMax(Space& home, const VarBranchOptions& vbo); 00379 ViewSelStatus init(Space& home, SetView x); 00381 ViewSelStatus select(Space& home, SetView x); 00382 }; 00383 00391 class BySizeAfcMin : public ViewSelBase<SetView> { 00392 protected: 00394 double sizeafc; 00395 public: 00397 BySizeAfcMin(void); 00399 BySizeAfcMin(Space& home, const VarBranchOptions& vbo); 00401 ViewSelStatus init(Space& home, SetView x); 00403 ViewSelStatus select(Space& home, SetView x); 00404 }; 00405 00413 class BySizeAfcMax : public ViewSelBase<SetView> { 00414 protected: 00416 double sizeafc; 00417 public: 00419 BySizeAfcMax(void); 00421 BySizeAfcMax(Space& home, const VarBranchOptions& vbo); 00423 ViewSelStatus init(Space& home, SetView x); 00425 ViewSelStatus select(Space& home, SetView x); 00426 }; 00427 00428 }}} 00429 00430 #include <gecode/set/branch/select-val.hpp> 00431 #include <gecode/set/branch/select-view.hpp> 00432 #include <gecode/set/branch/post-val.hpp> 00433 00434 #endif 00435 // STATISTICS: set-branch 00436