select-view.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-10-13 21:12:58 +0200 (Tue, 13 Oct 2009) $ by $Author: schulte $ 00017 * $Revision: 9897 $ 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 forceinline 00047 BySizeMin::BySizeMin(void) : size(0U) {} 00048 forceinline 00049 BySizeMin::BySizeMin(Space& home, const VarBranchOptions& vbo) 00050 : ViewSelBase<SetView>(home,vbo), size(0U) {} 00051 forceinline ViewSelStatus 00052 BySizeMin::init(Space&, SetView x) { 00053 size = x.unknownSize(); 00054 return (size == 1) ? VSS_BEST : VSS_BETTER; 00055 } 00056 forceinline ViewSelStatus 00057 BySizeMin::select(Space&, SetView x) { 00058 unsigned int us = x.unknownSize(); 00059 if (us < size) { 00060 size = us; 00061 return (size == 1) ? VSS_BEST : VSS_BETTER; 00062 } else if (us > size) { 00063 return VSS_WORSE; 00064 } else { 00065 return VSS_TIE; 00066 } 00067 } 00068 00069 00070 forceinline 00071 BySizeMax::BySizeMax(void) : size(0U) {} 00072 forceinline 00073 BySizeMax::BySizeMax(Space& home, const VarBranchOptions& vbo) 00074 : ViewSelBase<SetView>(home,vbo), size(0U) {} 00075 forceinline ViewSelStatus 00076 BySizeMax::init(Space&, SetView x) { 00077 size = x.unknownSize(); 00078 return VSS_BETTER; 00079 } 00080 forceinline ViewSelStatus 00081 BySizeMax::select(Space&, SetView x) { 00082 unsigned int us = x.unknownSize(); 00083 if (us > size) { 00084 size = us; 00085 return VSS_BETTER; 00086 } else if (us < size) { 00087 return VSS_WORSE; 00088 } else { 00089 return VSS_TIE; 00090 } 00091 } 00092 00093 00094 forceinline 00095 ByMinMin::ByMinMin(void) : min(0) {} 00096 forceinline 00097 ByMinMin::ByMinMin(Space& home, const VarBranchOptions& vbo) 00098 : ViewSelBase<SetView>(home,vbo), min(0) {} 00099 forceinline ViewSelStatus 00100 ByMinMin::init(Space&, SetView x) { 00101 UnknownRanges<SetView> u(x); 00102 min = u.min(); 00103 return VSS_BETTER; 00104 } 00105 forceinline ViewSelStatus 00106 ByMinMin::select(Space&, SetView x) { 00107 UnknownRanges<SetView> u(x); 00108 if (u.min() < min) { 00109 min = u.min(); return VSS_BETTER; 00110 } else if (u.min() > min) { 00111 return VSS_WORSE; 00112 } else { 00113 return VSS_TIE; 00114 } 00115 } 00116 00117 00118 forceinline 00119 ByMinMax::ByMinMax(void) : min(0) {} 00120 forceinline 00121 ByMinMax::ByMinMax(Space& home, const VarBranchOptions& vbo) 00122 : ViewSelBase<SetView>(home,vbo), min(0) {} 00123 forceinline ViewSelStatus 00124 ByMinMax::init(Space&, SetView x) { 00125 UnknownRanges<SetView> u(x); 00126 min = u.min(); 00127 return VSS_BETTER; 00128 } 00129 forceinline ViewSelStatus 00130 ByMinMax::select(Space&, SetView x) { 00131 UnknownRanges<SetView> u(x); 00132 if (u.min() > min) { 00133 min = u.min(); return VSS_BETTER; 00134 } else if (u.min() < min) { 00135 return VSS_WORSE; 00136 } else { 00137 return VSS_TIE; 00138 } 00139 } 00140 00141 00142 forceinline 00143 ByMaxMin::ByMaxMin(void) : max(0) {} 00144 forceinline 00145 ByMaxMin::ByMaxMin(Space& home, const VarBranchOptions& vbo) 00146 : ViewSelBase<SetView>(home,vbo), max(0) {} 00147 forceinline ViewSelStatus 00148 ByMaxMin::init(Space&, SetView x) { 00149 for (UnknownRanges<SetView> u(x); u(); ++u) 00150 max = u.max(); 00151 return VSS_BETTER; 00152 } 00153 forceinline ViewSelStatus 00154 ByMaxMin::select(Space&, SetView x) { 00155 int um = 0; 00156 for (UnknownRanges<SetView> u(x); u(); ++u) 00157 um = u.max(); 00158 if (um < max) { 00159 max = um; return VSS_BETTER; 00160 } else if (um > max) { 00161 return VSS_WORSE; 00162 } else { 00163 return VSS_TIE; 00164 } 00165 } 00166 00167 00168 forceinline 00169 ByMaxMax::ByMaxMax(void) : max(0) {} 00170 forceinline 00171 ByMaxMax::ByMaxMax(Space& home, const VarBranchOptions& vbo) 00172 : ViewSelBase<SetView>(home,vbo), max(0) {} 00173 forceinline ViewSelStatus 00174 ByMaxMax::init(Space&, SetView x) { 00175 for (UnknownRanges<SetView> u(x); u(); ++u) 00176 max = u.max(); 00177 return VSS_BETTER; 00178 } 00179 forceinline ViewSelStatus 00180 ByMaxMax::select(Space&, SetView x) { 00181 int um = 0; 00182 for (UnknownRanges<SetView> u(x); u(); ++u) 00183 um = u.max(); 00184 if (um > max) { 00185 max = um; return VSS_BETTER; 00186 } else if (um < max) { 00187 return VSS_WORSE; 00188 } else { 00189 return VSS_TIE; 00190 } 00191 } 00192 00193 00194 // Select variable with smallest size/degree 00195 forceinline 00196 BySizeDegreeMin::BySizeDegreeMin(void) : sizedegree(0) {} 00197 forceinline 00198 BySizeDegreeMin::BySizeDegreeMin(Space& home, const VarBranchOptions& vbo) 00199 : ViewSelBase<SetView>(home,vbo), sizedegree(0) {} 00200 forceinline ViewSelStatus 00201 BySizeDegreeMin::init(Space&, SetView x) { 00202 UnknownRanges<SetView> u(x); 00203 sizedegree = 00204 static_cast<double>(Iter::Ranges::size(u))/ 00205 static_cast<double>(x.degree()); 00206 return VSS_BETTER; 00207 } 00208 forceinline ViewSelStatus 00209 BySizeDegreeMin::select(Space&, SetView x) { 00210 UnknownRanges<SetView> u(x); 00211 double sd = 00212 static_cast<double>(Iter::Ranges::size(u))/ 00213 static_cast<double>(x.degree()); 00214 if (sd < sizedegree) { 00215 sizedegree = sd; return VSS_BETTER; 00216 } else if (sd > sizedegree) { 00217 return VSS_WORSE; 00218 } else { 00219 return VSS_TIE; 00220 } 00221 } 00222 00223 00224 // Select variable with largest size/degree 00225 forceinline 00226 BySizeDegreeMax::BySizeDegreeMax(void) : sizedegree(0) {} 00227 forceinline 00228 BySizeDegreeMax::BySizeDegreeMax(Space& home, const VarBranchOptions& vbo) 00229 : ViewSelBase<SetView>(home,vbo), sizedegree(0) {} 00230 forceinline ViewSelStatus 00231 BySizeDegreeMax::init(Space&, SetView x) { 00232 UnknownRanges<SetView> u(x); 00233 sizedegree = 00234 static_cast<double>(Iter::Ranges::size(u))/ 00235 static_cast<double>(x.degree()); 00236 return VSS_BETTER; 00237 } 00238 forceinline ViewSelStatus 00239 BySizeDegreeMax::select(Space&, View x) { 00240 UnknownRanges<SetView> u(x); 00241 double sd = 00242 static_cast<double>(Iter::Ranges::size(u))/ 00243 static_cast<double>(x.degree()); 00244 if (sd > sizedegree) { 00245 sizedegree = sd; return VSS_BETTER; 00246 } else if (sd < sizedegree) { 00247 return VSS_WORSE; 00248 } else { 00249 return VSS_TIE; 00250 } 00251 } 00252 00253 // Select variable with smallest size/afc 00254 forceinline 00255 BySizeAfcMin::BySizeAfcMin(void) : sizeafc(0) {} 00256 forceinline 00257 BySizeAfcMin::BySizeAfcMin(Space& home, const VarBranchOptions& vbo) 00258 : ViewSelBase<SetView>(home,vbo), sizeafc(0) {} 00259 forceinline ViewSelStatus 00260 BySizeAfcMin::init(Space&, SetView x) { 00261 UnknownRanges<SetView> u(x); 00262 sizeafc = static_cast<double>(Iter::Ranges::size(u))/x.afc(); 00263 return VSS_BETTER; 00264 } 00265 forceinline ViewSelStatus 00266 BySizeAfcMin::select(Space&, SetView x) { 00267 UnknownRanges<SetView> u(x); 00268 double sa = static_cast<double>(Iter::Ranges::size(u))/x.afc(); 00269 if (sa < sizeafc) { 00270 sizeafc = sa; return VSS_BETTER; 00271 } else if (sa > sizeafc) { 00272 return VSS_WORSE; 00273 } else { 00274 return VSS_TIE; 00275 } 00276 } 00277 00278 00279 // Select variable with largest size/afc 00280 forceinline 00281 BySizeAfcMax::BySizeAfcMax(void) : sizeafc(0) {} 00282 forceinline 00283 BySizeAfcMax::BySizeAfcMax(Space& home, const VarBranchOptions& vbo) 00284 : ViewSelBase<SetView>(home,vbo), sizeafc(0) {} 00285 forceinline ViewSelStatus 00286 BySizeAfcMax::init(Space&, SetView x) { 00287 UnknownRanges<SetView> u(x); 00288 sizeafc = static_cast<double>(Iter::Ranges::size(u))/x.afc(); 00289 return VSS_BETTER; 00290 } 00291 forceinline ViewSelStatus 00292 BySizeAfcMax::select(Space&, View x) { 00293 UnknownRanges<SetView> u(x); 00294 double sa = static_cast<double>(Iter::Ranges::size(u))/x.afc(); 00295 if (sa > sizeafc) { 00296 sizeafc = sa; return VSS_BETTER; 00297 } else if (sa < sizeafc) { 00298 return VSS_WORSE; 00299 } else { 00300 return VSS_TIE; 00301 } 00302 } 00303 00304 }}} 00305 00306 // STATISTICS: set-branch