select-val.hpp
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: 2009-09-08 21:10:29 +0200 (Tue, 08 Sep 2009) $ by $Author: schulte $ 00017 * $Revision: 9692 $ 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 namespace Gecode { namespace Set { namespace Branch { 00045 00046 template<bool inc> 00047 forceinline 00048 ValMin<inc>::ValMin(void) {} 00049 template<bool inc> 00050 forceinline 00051 ValMin<inc>::ValMin(Space& home, const ValBranchOptions& vbo) 00052 : ValSelBase<SetView,int>(home,vbo) {} 00053 template<bool inc> 00054 forceinline int 00055 ValMin<inc>::val(Space&, SetView x) const { 00056 UnknownRanges<SetView> u(x); 00057 return u.min(); 00058 } 00059 template<bool inc> 00060 forceinline ModEvent 00061 ValMin<inc>::tell(Space& home, unsigned int a, SetView x, int v) { 00062 return ((a == 0) == inc) ? x.include(home,v) : x.exclude(home,v); 00063 } 00064 00065 00066 template<bool inc> 00067 forceinline 00068 ValMed<inc>::ValMed(void) {} 00069 template<bool inc> 00070 forceinline 00071 ValMed<inc>::ValMed(Space& home, const ValBranchOptions& vbo) 00072 : ValSelBase<SetView,int>(home,vbo) {} 00073 template<bool inc> 00074 forceinline int 00075 ValMed<inc>::val(Space&, SetView x) const { 00076 UnknownRanges<SetView> u1(x); 00077 unsigned int i = Iter::Ranges::size(u1) / 2; 00078 UnknownRanges<SetView> u2(x); 00079 int med = (u2.min()+u2.max()) / 2; 00080 ++u2; 00081 if (!u2()) { 00082 return med; 00083 } 00084 UnknownRanges<SetView> u3(x); 00085 while (i >= u3.width()) { 00086 i -= u3.width(); 00087 ++u3; 00088 } 00089 return u3.min() + static_cast<int>(i); 00090 } 00091 template<bool inc> 00092 forceinline ModEvent 00093 ValMed<inc>::tell(Space& home, unsigned int a, SetView x, int v) { 00094 return ((a == 0) == inc) ? x.include(home,v) : x.exclude(home,v); 00095 } 00096 00097 template<bool inc> 00098 forceinline 00099 ValMax<inc>::ValMax(void) {} 00100 template<bool inc> 00101 forceinline 00102 ValMax<inc>::ValMax(Space& home, const ValBranchOptions& vbo) 00103 : ValSelBase<SetView,int>(home,vbo) {} 00104 template<bool inc> 00105 forceinline int 00106 ValMax<inc>::val(Space&, SetView x) const { 00107 int max = 0; 00108 for (UnknownRanges<SetView> u(x); u(); ++u) 00109 max = u.max(); 00110 return max; 00111 } 00112 template<bool inc> 00113 forceinline ModEvent 00114 ValMax<inc>::tell(Space& home, unsigned int a, SetView x, int v) { 00115 return ((a == 0) == inc) ? x.include(home,v) : x.exclude(home,v); 00116 } 00117 00118 00119 template<bool inc> 00120 forceinline 00121 ValRnd<inc>::ValRnd(void) {} 00122 template<bool inc> 00123 forceinline 00124 ValRnd<inc>::ValRnd(Space&, const ValBranchOptions& vbo) 00125 : r(vbo.seed) {} 00126 template<bool inc> 00127 forceinline int 00128 ValRnd<inc>::val(Space&, SetView x) { 00129 UnknownRanges<SetView> u(x); 00130 unsigned int p = r(Iter::Ranges::size(u)); 00131 for (UnknownRanges<SetView> i(x); i(); ++i) { 00132 if (i.width() > p) 00133 return i.min() + static_cast<int>(p); 00134 p -= i.width(); 00135 } 00136 GECODE_NEVER; 00137 return 0; 00138 } 00139 template<bool inc> 00140 forceinline ModEvent 00141 ValRnd<inc>::tell(Space& home, unsigned int a, SetView x, int v) { 00142 return ((a == 0) == inc) ? x.include(home,v) : x.exclude(home,v); 00143 } 00144 template<bool inc> 00145 forceinline Support::RandomGenerator 00146 ValRnd<inc>::choice(Space&) { 00147 return r; 00148 } 00149 template<bool inc> 00150 forceinline void 00151 ValRnd<inc>::commit(Space&, const Support::RandomGenerator& c, 00152 unsigned int) { 00153 r = c; 00154 } 00155 template<bool inc> 00156 forceinline void 00157 ValRnd<inc>::update(Space&, bool, ValRnd<inc>& vr) { 00158 r = vr.r; 00159 } 00160 template<bool inc> 00161 forceinline void 00162 ValRnd<inc>::dispose(Space&) {} 00163 00164 00165 template<bool inc> 00166 forceinline 00167 AssignValMin<inc>::AssignValMin(void) {} 00168 template<bool inc> 00169 forceinline 00170 AssignValMin<inc>::AssignValMin(Space& home, const ValBranchOptions& vbo) 00171 : ValMin<inc>(home,vbo) {} 00172 00173 template<bool inc> 00174 forceinline 00175 AssignValMed<inc>::AssignValMed(void) {} 00176 template<bool inc> 00177 forceinline 00178 AssignValMed<inc>::AssignValMed(Space& home, const ValBranchOptions& vbo) 00179 : ValMed<inc>(home,vbo) {} 00180 00181 template<bool inc> 00182 forceinline 00183 AssignValMax<inc>::AssignValMax(void) {} 00184 template<bool inc> 00185 forceinline 00186 AssignValMax<inc>::AssignValMax(Space& home, const ValBranchOptions& vbo) 00187 : ValMax<inc>(home,vbo) {} 00188 00189 template<bool inc> 00190 forceinline 00191 AssignValRnd<inc>::AssignValRnd(void) {} 00192 template<bool inc> 00193 forceinline 00194 AssignValRnd<inc>::AssignValRnd(Space& home, const ValBranchOptions& vbo) 00195 : ValRnd<inc>(home,vbo) {} 00196 00197 }}} 00198 00199 // STATISTICS: set-branch