lq-le.hpp
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 * Gabor Szokoli <szokoli@gecode.org> 00006 * 00007 * Copyright: 00008 * Christian Schulte, 2003 00009 * Gabor Szokoli, 2003 00010 * 00011 * Last modified: 00012 * $Date: 2010-03-03 17:32:21 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $ 00013 * $Revision: 10364 $ 00014 * 00015 * This file is part of Gecode, the generic constraint 00016 * development environment: 00017 * http://www.gecode.org 00018 * 00019 * Permission is hereby granted, free of charge, to any person obtaining 00020 * a copy of this software and associated documentation files (the 00021 * "Software"), to deal in the Software without restriction, including 00022 * without limitation the rights to use, copy, modify, merge, publish, 00023 * distribute, sublicense, and/or sell copies of the Software, and to 00024 * permit persons to whom the Software is furnished to do so, subject to 00025 * the following conditions: 00026 * 00027 * The above copyright notice and this permission notice shall be 00028 * included in all copies or substantial portions of the Software. 00029 * 00030 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00031 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00032 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00033 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00034 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00035 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00036 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00037 * 00038 */ 00039 00040 namespace Gecode { namespace Int { namespace Rel { 00041 00042 /* 00043 * Less or equal propagator 00044 * 00045 */ 00046 00047 template<class View> 00048 forceinline 00049 Lq<View>::Lq(Home home, View x0, View x1) 00050 : BinaryPropagator<View,PC_INT_BND>(home,x0,x1) {} 00051 00052 template<class View> 00053 ExecStatus 00054 Lq<View>::post(Home home, View x0, View x1) { 00055 GECODE_ME_CHECK(x0.lq(home,x1.max())); 00056 GECODE_ME_CHECK(x1.gq(home,x0.min())); 00057 if (!same(x0,x1) && (x0.max() > x1.min())) 00058 (void) new (home) Lq<View>(home,x0,x1); 00059 return ES_OK; 00060 } 00061 00062 template<class View> 00063 forceinline 00064 Lq<View>::Lq(Space& home, bool share, Lq<View>& p) 00065 : BinaryPropagator<View,PC_INT_BND>(home,share,p) {} 00066 00067 template<class View> 00068 Actor* 00069 Lq<View>::copy(Space& home, bool share) { 00070 return new (home) Lq<View>(home,share,*this); 00071 } 00072 00073 template<class View> 00074 ExecStatus 00075 Lq<View>::propagate(Space& home, const ModEventDelta&) { 00076 GECODE_ME_CHECK(x0.lq(home,x1.max())); 00077 GECODE_ME_CHECK(x1.gq(home,x0.min())); 00078 return (x0.max() <= x1.min()) ? home.ES_SUBSUMED(*this) : ES_FIX; 00079 } 00080 00081 00082 00083 00084 /* 00085 * Less propagator 00086 * 00087 */ 00088 template<class View> 00089 forceinline 00090 Le<View>::Le(Home home, View x0, View x1) 00091 : BinaryPropagator<View,PC_INT_BND>(home,x0,x1) {} 00092 00093 template<class View> 00094 ExecStatus 00095 Le<View>::post(Home home, View x0, View x1) { 00096 if (same(x0,x1)) 00097 return ES_FAILED; 00098 GECODE_ME_CHECK(x0.le(home,x1.max())); 00099 GECODE_ME_CHECK(x1.gr(home,x0.min())); 00100 if (x0.max() >= x1.min()) 00101 (void) new (home) Le<View>(home,x0,x1); 00102 return ES_OK; 00103 } 00104 00105 template<class View> 00106 forceinline 00107 Le<View>::Le(Space& home, bool share, Le<View>& p) 00108 : BinaryPropagator<View,PC_INT_BND>(home,share,p) {} 00109 00110 template<class View> 00111 Actor* 00112 Le<View>::copy(Space& home, bool share) { 00113 return new (home) Le<View>(home,share,*this); 00114 } 00115 00116 template<class View> 00117 ExecStatus 00118 Le<View>::propagate(Space& home, const ModEventDelta&) { 00119 GECODE_ME_CHECK(x0.le(home,x1.max())); 00120 GECODE_ME_CHECK(x1.gr(home,x0.min())); 00121 return (x0.max() < x1.min()) ? home.ES_SUBSUMED(*this) : ES_FIX; 00122 } 00123 00124 00125 00126 /* 00127 * Reified less or equal propagator 00128 * 00129 */ 00130 00131 template<class View, class CtrlView> 00132 forceinline 00133 ReLq<View,CtrlView>::ReLq(Home home, View x0, View x1, CtrlView b) 00134 : ReBinaryPropagator<View,PC_INT_BND,CtrlView>(home,x0,x1,b) {} 00135 00136 template<class View, class CtrlView> 00137 ExecStatus 00138 ReLq<View,CtrlView>::post(Home home, View x0, View x1, CtrlView b) { 00139 if (b.one()) 00140 return Lq<View>::post(home,x0,x1); 00141 if (b.zero()) 00142 return Le<View>::post(home,x1,x0); 00143 if (!same(x0,x1)) { 00144 switch (rtest_lq(x0,x1)) { 00145 case RT_TRUE: 00146 GECODE_ME_CHECK(b.one_none(home)); break; 00147 case RT_FALSE: 00148 GECODE_ME_CHECK(b.zero_none(home)); break; 00149 case RT_MAYBE: 00150 (void) new (home) ReLq<View,CtrlView>(home,x0,x1,b); break; 00151 default: GECODE_NEVER; 00152 } 00153 } else { 00154 GECODE_ME_CHECK(b.one_none(home)); 00155 } 00156 return ES_OK; 00157 } 00158 00159 template<class View, class CtrlView> 00160 forceinline 00161 ReLq<View,CtrlView>::ReLq(Space& home, bool share, ReLq& p) 00162 : ReBinaryPropagator<View,PC_INT_BND,CtrlView>(home,share,p) {} 00163 00164 template<class View, class CtrlView> 00165 Actor* 00166 ReLq<View,CtrlView>::copy(Space& home, bool share) { 00167 return new (home) ReLq<View,CtrlView>(home,share,*this); 00168 } 00169 00170 template<class View, class CtrlView> 00171 ExecStatus 00172 ReLq<View,CtrlView>::propagate(Space& home, const ModEventDelta&) { 00173 if (b.one()) 00174 GECODE_REWRITE(*this,Lq<View>::post(home(*this),x0,x1)); 00175 if (b.zero()) 00176 GECODE_REWRITE(*this,Le<View>::post(home(*this),x1,x0)); 00177 switch (rtest_lq(x0,x1)) { 00178 case RT_TRUE: 00179 GECODE_ME_CHECK(b.one_none(home)); return home.ES_SUBSUMED(*this); 00180 case RT_FALSE: 00181 GECODE_ME_CHECK(b.zero_none(home)); return home.ES_SUBSUMED(*this); 00182 case RT_MAYBE: 00183 break; 00184 default: GECODE_NEVER; 00185 } 00186 return ES_FIX; 00187 } 00188 00189 /* 00190 * Reified less or equal propagator involving one variable 00191 * 00192 */ 00193 00194 template<class View, class CtrlView> 00195 forceinline 00196 ReLqInt<View,CtrlView>::ReLqInt(Home home, View x, int c0, CtrlView b) 00197 : ReUnaryPropagator<View,PC_INT_BND,CtrlView>(home,x,b), c(c0) {} 00198 00199 template<class View, class CtrlView> 00200 ExecStatus 00201 ReLqInt<View,CtrlView>::post(Home home, View x, int c, CtrlView b) { 00202 if (b.one()) { 00203 GECODE_ME_CHECK(x.lq(home,c)); 00204 } else if (b.zero()) { 00205 GECODE_ME_CHECK(x.gr(home,c)); 00206 } else { 00207 switch (rtest_lq(x,c)) { 00208 case RT_TRUE: 00209 GECODE_ME_CHECK(b.one_none(home)); break; 00210 case RT_FALSE: 00211 GECODE_ME_CHECK(b.zero_none(home)); break; 00212 case RT_MAYBE: 00213 (void) new (home) ReLqInt<View,CtrlView>(home,x,c,b); break; 00214 default: GECODE_NEVER; 00215 } 00216 } 00217 return ES_OK; 00218 } 00219 00220 00221 template<class View, class CtrlView> 00222 forceinline 00223 ReLqInt<View,CtrlView>::ReLqInt(Space& home, bool share, ReLqInt& p) 00224 : ReUnaryPropagator<View,PC_INT_BND,CtrlView>(home,share,p), c(p.c) {} 00225 00226 template<class View, class CtrlView> 00227 Actor* 00228 ReLqInt<View,CtrlView>::copy(Space& home, bool share) { 00229 return new (home) ReLqInt<View,CtrlView>(home,share,*this); 00230 } 00231 00232 template<class View, class CtrlView> 00233 ExecStatus 00234 ReLqInt<View,CtrlView>::propagate(Space& home, const ModEventDelta&) { 00235 if (b.one()) { 00236 GECODE_ME_CHECK(x0.lq(home,c)); goto subsumed; 00237 } 00238 if (b.zero()) { 00239 GECODE_ME_CHECK(x0.gr(home,c)); goto subsumed; 00240 } 00241 switch (rtest_lq(x0,c)) { 00242 case RT_TRUE: 00243 GECODE_ME_CHECK(b.one_none(home)); goto subsumed; 00244 case RT_FALSE: 00245 GECODE_ME_CHECK(b.zero_none(home)); goto subsumed; 00246 case RT_MAYBE: 00247 break; 00248 default: GECODE_NEVER; 00249 } 00250 return ES_FIX; 00251 subsumed: 00252 return home.ES_SUBSUMED(*this); 00253 } 00254 00255 }}} 00256 00257 // STATISTICS: int-prop 00258