support-values.icc
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 namespace Gecode { namespace Int {
00039
00040 template<class View>
00041 forceinline void
00042 SupportValues<View>::set(unsigned int i) {
00043 unsigned int p = i / bpui;
00044 bits[p] |= 1 << (i-p*bpui);
00045 }
00046
00047 template<class View>
00048 forceinline bool
00049 SupportValues<View>::bit(unsigned int i) const {
00050 unsigned int p = i / bpui;
00051 return (bits[p] & (1 << (i-p*bpui))) != 0;
00052 }
00053
00054 template<class View>
00055 forceinline void
00056 SupportValues<View>::reset(void) {
00057 rp = rp_fst; v = rp->min;
00058 max = rp->min + static_cast<int>((rp+1)->pos - rp->pos) - 1;
00059 }
00060
00061 template<class View>
00062 inline
00063 SupportValues<View>::SupportValues(View x0) : x(x0) {
00064 bits = Memory::bmalloc<unsigned int>((x.size() / bpui) + 1);
00065 for (unsigned int i = (x.size() / bpui) + 1; i--; )
00066 bits[i] = 0;
00067 unsigned int n = 0;
00068 for (ViewRanges<View> r(x); r(); ++r)
00069 n++;
00070 rp_fst = Memory::bmalloc<RangePos>(n+1);
00071 rp_lst = rp_fst + n;
00072 unsigned int p = 0;
00073 int i = 0;
00074 for (ViewRanges<View> r(x); r(); ++r) {
00075 rp_fst[i].min = r.min();
00076 rp_fst[i].pos = p;
00077 p += r.width(); i++;
00078 }
00079 rp_fst[i].pos=p;
00080 reset();
00081 }
00082
00083 template<class View>
00084 inline
00085 SupportValues<View>::~SupportValues(void) {
00086 Memory::free(bits);
00087 Memory::free(rp_fst);
00088 }
00089
00090 template<class View>
00091 forceinline void
00092 SupportValues<View>::operator++(void) {
00093 if (++v > max)
00094 if (++rp < rp_lst) {
00095 v = rp->min;
00096 max = rp->min + static_cast<int>((rp+1)->pos - rp->pos) - 1;
00097 }
00098 }
00099
00100 template<class View>
00101 forceinline bool
00102 SupportValues<View>::operator()(void) const {
00103 return rp < rp_lst;
00104 }
00105
00106 template<class View>
00107 forceinline int
00108 SupportValues<View>::val(void) const {
00109 return v;
00110 }
00111
00112 template<class View>
00113 forceinline void
00114 SupportValues<View>::support(void) {
00115 set(rp->pos + static_cast<unsigned int>(v-rp->min));
00116 }
00117
00118 template<class View>
00119 forceinline bool
00120 SupportValues<View>::_support(int n) {
00121 RangePos* l = rp_fst;
00122 RangePos* r = rp_lst-1;
00123 while (true) {
00124 if (l > r) return false;
00125 RangePos* m = l + (r-l)/2;
00126 int max = m->min + static_cast<int>((m+1)->pos - m->pos) - 1;
00127 if ((n >= m->min) && (n <= max)) {
00128 set(m->pos + static_cast<unsigned int>(n-m->min));
00129 return true;
00130 }
00131 if (l == r) return false;
00132 if (n < m->min)
00133 r=m-1;
00134 else
00135 l=m+1;
00136 }
00137 GECODE_NEVER;
00138 return false;
00139 }
00140
00141 template<class View>
00142 forceinline bool
00143 SupportValues<View>::support(int n) {
00144 if ((n < x.min()) || (n > x.max()))
00145 return false;
00146 return _support(n);
00147 }
00148
00149 template<class View>
00150 forceinline bool
00151 SupportValues<View>::support(double n) {
00152 if ((n < x.min()) || (n > x.max()))
00153 return false;
00154 return _support(static_cast<int>(n));
00155 }
00156
00157 template<class View>
00158 forceinline void
00159 SupportValues<View>::Unsupported::find(void) {
00160
00161 while ((p < sv.x.size()) && sv.bit(p))
00162 p++;
00163
00164 while ((rp < sv.rp_lst) && (p >= (rp+1)->pos))
00165 rp++;
00166 }
00167
00168 template<class View>
00169 forceinline
00170 SupportValues<View>::Unsupported::Unsupported(SupportValues& sv0)
00171 : rp(sv0.rp_fst), p(0), sv(sv0) {
00172 find();
00173 }
00174
00175 template<class View>
00176 forceinline void
00177 SupportValues<View>::Unsupported::operator++(void) {
00178 p++; find();
00179 }
00180
00181 template<class View>
00182 forceinline bool
00183 SupportValues<View>::Unsupported::operator()(void) const {
00184 return rp < sv.rp_lst;
00185 }
00186
00187 template<class View>
00188 forceinline int
00189 SupportValues<View>::Unsupported::val(void) const {
00190 return rp->min+(p-rp->pos);
00191 }
00192
00193 template<class View>
00194 inline ModEvent
00195 SupportValues<View>::tell(Space* home) {
00196 Unsupported u(*this);
00197 return x.minus_v(home,u,false);
00198 }
00199
00200 }}
00201
00202
00203