rel-test.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 * 00006 * Copyright: 00007 * Christian Schulte, 2003 00008 * 00009 * Last modified: 00010 * $Date: 2009-09-08 21:10:29 +0200 (Tue, 08 Sep 2009) $ by $Author: schulte $ 00011 * $Revision: 9692 $ 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 namespace Gecode { namespace Int { 00039 00040 /* 00041 * Testing equality 00042 * 00043 */ 00044 00045 template<class View> 00046 forceinline RelTest 00047 rtest_eq_bnd(View x, View y) { 00048 if ((x.min() > y.max()) || (x.max() < y.min())) return RT_FALSE; 00049 return (x.assigned() && y.assigned()) ? RT_TRUE : RT_MAYBE; 00050 } 00051 00052 template<class View> 00053 RelTest 00054 rtest_eq_dom_check(View x, View y) { 00055 ViewRanges<View> rx(x), ry(y); 00056 while (rx() && ry()) { 00057 if (rx.max() < ry.min()) { 00058 ++rx; 00059 } else if (ry.max() < rx.min()) { 00060 ++ry; 00061 } else return RT_MAYBE; 00062 } 00063 return RT_FALSE; 00064 } 00065 00066 template<class View> 00067 forceinline RelTest 00068 rtest_eq_dom(View x, View y) { 00069 RelTest rt = rtest_eq_bnd(x,y); 00070 if (rt != RT_MAYBE) return rt; 00071 return (x.range() && y.range()) ? RT_MAYBE : rtest_eq_dom_check(x,y); 00072 } 00073 00074 00075 template<class View> 00076 forceinline RelTest 00077 rtest_eq_bnd(View x, int n) { 00078 if ((n > x.max()) || (n < x.min())) return RT_FALSE; 00079 return x.assigned() ? RT_TRUE : RT_MAYBE; 00080 } 00081 00082 template<class View> 00083 RelTest 00084 rtest_eq_dom_check(View x, int n) { 00085 ViewRanges<View> rx(x); 00086 while (n > rx.max()) ++rx; 00087 return (n >= rx.min()) ? RT_MAYBE : RT_FALSE; 00088 } 00089 00090 template<class View> 00091 forceinline RelTest 00092 rtest_eq_dom(View x, int n) { 00093 RelTest rt = rtest_eq_bnd(x,n); 00094 if (rt != RT_MAYBE) return rt; 00095 return x.range() ? RT_MAYBE : rtest_eq_dom_check(x,n); 00096 } 00097 00098 00099 00100 /* 00101 * Testing disequality 00102 * 00103 */ 00104 00105 template<class View> 00106 forceinline RelTest 00107 rtest_nq_bnd(View x, View y) { 00108 if ((x.min() > y.max()) || (x.max() < y.min())) return RT_TRUE; 00109 return (x.assigned() && y.assigned()) ? RT_FALSE : RT_MAYBE; 00110 } 00111 00112 template<class View> 00113 forceinline RelTest 00114 rtest_nq_dom_check(View x, View y) { 00115 ViewRanges<View> rx(x), ry(y); 00116 while (rx() && ry()) { 00117 if (rx.max() < ry.min()) { 00118 ++rx; 00119 } else if (ry.max() < rx.min()) { 00120 ++ry; 00121 } else return RT_MAYBE; 00122 } 00123 return RT_TRUE; 00124 } 00125 00126 template<class View> 00127 forceinline RelTest 00128 rtest_nq_dom(View x, View y) { 00129 RelTest rt = rtest_nq_bnd(x,y); 00130 if (rt != RT_MAYBE) return rt; 00131 return (x.range() && y.range()) ? RT_MAYBE : rtest_nq_dom_check(x,y); 00132 } 00133 00134 00135 template<class View> 00136 forceinline RelTest 00137 rtest_nq_bnd(View x, int n) { 00138 if ((n > x.max()) || (n < x.min())) return RT_TRUE; 00139 return (x.assigned()) ? RT_FALSE : RT_MAYBE; 00140 } 00141 00142 template<class View> 00143 forceinline RelTest 00144 rtest_nq_dom_check(View x, int n) { 00145 ViewRanges<View> rx(x); 00146 while (n > rx.max()) ++rx; 00147 return (n >= rx.min()) ? RT_MAYBE : RT_TRUE; 00148 } 00149 00150 template<class View> 00151 forceinline RelTest 00152 rtest_nq_dom(View x, int n) { 00153 RelTest rt = rtest_nq_bnd(x,n); 00154 if (rt != RT_MAYBE) return rt; 00155 return x.range() ? RT_MAYBE : rtest_nq_dom_check(x,n); 00156 } 00157 00158 00159 /* 00160 * Testing inequalities 00161 * 00162 */ 00163 00164 template<class View> 00165 forceinline RelTest 00166 rtest_lq(View x, int n) { 00167 if (x.max() <= n) return RT_TRUE; 00168 if (x.min() > n) return RT_FALSE; 00169 return RT_MAYBE; 00170 } 00171 00172 template<class View> 00173 forceinline RelTest 00174 rtest_lq(View x, View y) { 00175 if (x.max() <= y.min()) return RT_TRUE; 00176 if (x.min() > y.max()) return RT_FALSE; 00177 return RT_MAYBE; 00178 } 00179 00180 template<class View> 00181 forceinline RelTest 00182 rtest_le(View x, int n) { 00183 if (x.max() < n) return RT_TRUE; 00184 if (x.min() >= n) return RT_FALSE; 00185 return RT_MAYBE; 00186 } 00187 00188 template<class View> 00189 forceinline RelTest 00190 rtest_le(View x, View y) { 00191 if (x.max() < y.min()) return RT_TRUE; 00192 if (x.min() >= y.max()) return RT_FALSE; 00193 return RT_MAYBE; 00194 } 00195 00196 template<class View> 00197 forceinline RelTest 00198 rtest_gq(View x, int n) { 00199 if (x.max() < n) return RT_FALSE; 00200 if (x.min() >= n) return RT_TRUE; 00201 return RT_MAYBE; 00202 } 00203 00204 template<class View> 00205 forceinline RelTest 00206 rtest_gq(View x, View y) { 00207 if (x.max() < y.min()) return RT_FALSE; 00208 if (x.min() >= y.max()) return RT_TRUE; 00209 return RT_MAYBE; 00210 } 00211 00212 template<class View> 00213 forceinline RelTest 00214 rtest_gr(View x, int n) { 00215 if (x.max() <= n) return RT_FALSE; 00216 if (x.min() > n) return RT_TRUE; 00217 return RT_MAYBE; 00218 } 00219 00220 template<class View> 00221 forceinline RelTest 00222 rtest_gr(View x, View y) { 00223 if (x.max() <= y.min()) return RT_FALSE; 00224 if (x.min() > y.max()) return RT_TRUE; 00225 return RT_MAYBE; 00226 } 00227 00228 }} 00229 00230 // STATISTICS: int-var 00231