ranges-inter.hpp
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 #include <algorithm>
00039
00040 namespace Gecode { namespace Iter { namespace Ranges {
00041
00047 template<class I, class J>
00048 class Inter : public MinMax {
00049 private:
00051 IsRangeIter<I> _checkI;
00053 IsRangeIter<J> _checkJ;
00054 protected:
00056 I i;
00058 J j;
00059 public:
00061
00062
00063 Inter(void);
00065 Inter(I& i, J& j);
00067 void init(I& i, J& j);
00069
00071
00072
00073 void operator ++(void);
00075 };
00076
00077
00083 template<class I>
00084 class NaryInter : public MinMax {
00085 private:
00087 IsRangeIter<I> _checkI;
00088 protected:
00090 I* is;
00092 int n;
00093 public:
00095
00096
00097 NaryInter(void);
00099 NaryInter(I* i, int n);
00101 void init(I* i, int n);
00103
00105
00106
00107 void operator ++(void);
00109 };
00110
00111
00112
00113
00114
00115
00116
00117 template<class I, class J>
00118 inline void
00119 Inter<I,J>::operator ++(void) {
00120 if (!i() || !j()) goto done;
00121 do {
00122 while (i() && (i.max() < j.min())) ++i;
00123 if (!i()) goto done;
00124 while (j() && (j.max() < i.min())) ++j;
00125 if (!j()) goto done;
00126 } while (i.max() < j.min());
00127
00128 ma = std::min(i.max(),j.max());
00129 mi = std::max(i.min(),j.min());
00130 if (i.max() < j.max()) ++i; else ++j;
00131 return;
00132 done:
00133 finish();
00134 }
00135
00136 template<class I, class J>
00137 forceinline
00138 Inter<I,J>::Inter(void) {}
00139
00140 template<class I, class J>
00141 forceinline
00142 Inter<I,J>::Inter(I& i0, J& j0)
00143 : i(i0), j(j0) {
00144 operator ++();
00145 }
00146
00147 template<class I, class J>
00148 forceinline void
00149 Inter<I,J>::init(I& i0, J& j0) {
00150 i = i0; j = j0;
00151 operator ++();
00152 }
00153
00154
00155
00156
00157
00158
00159
00160 template<class I>
00161 inline void
00162 NaryInter<I>::operator ++(void) {
00163
00164
00165 mi = ma+2;
00166 ma = is[0].max();
00167
00168 restart:
00169 for (int i = n; i--;) {
00170
00171 while (is[i]() && (is[i].max() < mi))
00172 ++is[i];
00173 if (!is[i]())
00174 goto done;
00175
00176 if (is[i].min() > ma) {
00177 mi=is[i].min();
00178 ma=is[i].max();
00179 goto restart;
00180 }
00181
00182 if (mi < is[i].min())
00183 mi = is[i].min();
00184 if (ma > is[i].max()) {
00185 ma = is[i].max();
00186 }
00187 }
00188 return;
00189 done:
00190 finish();
00191 }
00192
00193 template<class I>
00194 forceinline
00195 NaryInter<I>::NaryInter(void) {}
00196
00197 template<class I>
00198 inline
00199 NaryInter<I>::NaryInter(I* is0, int n0)
00200 : is(is0), n(n0) {
00201 if (!is[0]()) {
00202 finish();
00203 } else {
00204 ma=is[0].min()-2;
00205 operator ++();
00206 }
00207 }
00208
00209 template<class I>
00210 inline void
00211 NaryInter<I>::init(I* is0, int n0) {
00212 is = is0; n = n0;
00213 if (!is[0]()) {
00214 finish();
00215 } else {
00216 ma=is[0].min()-2;
00217 operator ++();
00218 }
00219 }
00220
00221 }}}
00222
00223
00224