support-values.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, 2008 00008 * 00009 * Last modified: 00010 * $Date: 2010-01-28 17:13:59 +0100 (Thu, 28 Jan 2010) $ by $Author: schulte $ 00011 * $Revision: 10244 $ 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 template<class View, class A> 00041 forceinline void 00042 SupportValues<View,A>::reset(void) { 00043 rp = rp_fst; v = rp->min; 00044 max = rp->min + static_cast<int>((rp+1)->pos - rp->pos) - 1; 00045 } 00046 00047 template<class View, class A> 00048 inline 00049 SupportValues<View,A>::SupportValues(A& a0, View x0) 00050 : a(a0), x(x0), bs(a,x.size(),true) { 00051 unsigned int n = 0; 00052 for (ViewRanges<View> r(x); r(); ++r) 00053 n++; 00054 rp_fst = a.template alloc<RangePos>(n+1); 00055 rp_lst = rp_fst + n; 00056 unsigned int p = 0; 00057 int i = 0; 00058 for (ViewRanges<View> r(x); r(); ++r) { 00059 rp_fst[i].min = r.min(); 00060 rp_fst[i].pos = p; 00061 p += r.width(); i++; 00062 } 00063 rp_fst[i].pos=p; 00064 reset(); 00065 } 00066 00067 template<class View, class A> 00068 forceinline 00069 SupportValues<View,A>::~SupportValues(void) { 00070 bs.dispose(a); 00071 a.free(rp_fst,static_cast<unsigned long int>(rp_lst-rp_fst+1)); 00072 } 00073 00074 template<class View, class A> 00075 forceinline void 00076 SupportValues<View,A>::operator ++(void) { 00077 if (++v > max) 00078 if (++rp < rp_lst) { 00079 v = rp->min; 00080 max = rp->min + static_cast<int>((rp+1)->pos - rp->pos) - 1; 00081 } 00082 } 00083 00084 template<class View, class A> 00085 forceinline bool 00086 SupportValues<View,A>::operator ()(void) const { 00087 return rp < rp_lst; 00088 } 00089 00090 template<class View, class A> 00091 forceinline int 00092 SupportValues<View,A>::val(void) const { 00093 return v; 00094 } 00095 00096 template<class View, class A> 00097 forceinline void 00098 SupportValues<View,A>::support(void) { 00099 bs.clear(rp->pos + static_cast<unsigned int>(v-rp->min)); 00100 } 00101 00102 template<class View, class A> 00103 forceinline bool 00104 SupportValues<View,A>::_support(int n) { 00105 RangePos* l = rp_fst; 00106 RangePos* r = rp_lst-1; 00107 while (true) { 00108 if (l > r) return false; 00109 RangePos* m = l + (r-l)/2; 00110 int max = m->min + static_cast<int>((m+1)->pos - m->pos) - 1; 00111 if ((n >= m->min) && (n <= max)) { 00112 bs.clear(m->pos + static_cast<unsigned int>(n-m->min)); 00113 return true; 00114 } 00115 if (l == r) return false; 00116 if (n < m->min) 00117 r=m-1; 00118 else 00119 l=m+1; 00120 } 00121 GECODE_NEVER; 00122 return false; 00123 } 00124 00125 template<class View, class A> 00126 forceinline bool 00127 SupportValues<View,A>::support(int n) { 00128 if ((n < x.min()) || (n > x.max())) 00129 return false; 00130 return _support(n); 00131 } 00132 00133 template<class View, class A> 00134 forceinline bool 00135 SupportValues<View,A>::support(double n) { 00136 if ((n < x.min()) || (n > x.max())) 00137 return false; 00138 return _support(static_cast<int>(n)); 00139 } 00140 00141 template<class View, class A> 00142 forceinline void 00143 SupportValues<View,A>::Unsupported::find(void) { 00144 // Skip all supported positions 00145 while ((p < sv.x.size()) && !sv.bs.get(p)) 00146 p = sv.bs.next(p); 00147 // Move to matching range 00148 while ((rp < sv.rp_lst) && (p >= (rp+1)->pos)) 00149 rp++; 00150 } 00151 00152 template<class View, class A> 00153 forceinline 00154 SupportValues<View,A>::Unsupported::Unsupported(SupportValues& sv0) 00155 : rp(sv0.rp_fst), p(0), sv(sv0) { 00156 find(); 00157 } 00158 00159 template<class View, class A> 00160 forceinline void 00161 SupportValues<View,A>::Unsupported::operator ++(void) { 00162 p++; find(); 00163 } 00164 00165 template<class View, class A> 00166 forceinline bool 00167 SupportValues<View,A>::Unsupported::operator ()(void) const { 00168 return rp < sv.rp_lst; 00169 } 00170 00171 template<class View, class A> 00172 forceinline int 00173 SupportValues<View,A>::Unsupported::val(void) const { 00174 return static_cast<int>(rp->min+(p-rp->pos)); 00175 } 00176 00177 template<class View, class A> 00178 inline ModEvent 00179 SupportValues<View,A>::tell(Space& home) { 00180 Unsupported u(*this); 00181 return x.minus_v(home,u,false); 00182 } 00183 00184 }} 00185 00186 // STATISTICS: int-prop 00187