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 #include <algorithm>
00035
00036 namespace Gecode { namespace Iter { namespace Ranges {
00037
00043 template<class I, class J>
00044 class Inter : public MinMax {
00045 protected:
00047 I i;
00049 J j;
00050 public:
00052
00053
00054 Inter(void);
00056 Inter(I& i, J& j);
00058 void init(I& i, J& j);
00060
00062
00063
00064 void operator ++(void);
00066 };
00067
00068
00074 class NaryInter : public RangeListIter {
00075 protected:
00077 RangeList* f;
00078 public:
00080
00081
00082 NaryInter(void);
00084 template<class I>
00085 NaryInter(Region& r, I& i);
00087 template<class I, class J>
00088 NaryInter(Region& r, I& i, J& j);
00090 template<class I>
00091 NaryInter(Region& r, I* i, int n);
00093 template<class I>
00094 void init(Region& r, I& i);
00096 template<class I, class J>
00097 void init(Region& r, I& i, J& j);
00099 template<class I>
00100 void init(Region& r, I* i, int n);
00102 template<class I>
00103 void operator &=(I& i);
00105 NaryInter& operator =(const NaryInter& m);
00107 };
00108
00109
00110
00111
00112
00113
00114
00115
00116 template<class I, class J>
00117 inline void
00118 Inter<I,J>::operator ++(void) {
00119 if (!i() || !j()) goto done;
00120 do {
00121 while (i() && (i.max() < j.min())) ++i;
00122 if (!i()) goto done;
00123 while (j() && (j.max() < i.min())) ++j;
00124 if (!j()) goto done;
00125 } while (i.max() < j.min());
00126
00127 ma = std::min(i.max(),j.max());
00128 mi = std::max(i.min(),j.min());
00129 if (i.max() < j.max()) ++i; else ++j;
00130 return;
00131 done:
00132 finish();
00133 }
00134
00135 template<class I, class J>
00136 forceinline
00137 Inter<I,J>::Inter(void) {}
00138
00139 template<class I, class J>
00140 forceinline
00141 Inter<I,J>::Inter(I& i0, J& j0)
00142 : i(i0), j(j0) {
00143 operator ++();
00144 }
00145
00146 template<class I, class J>
00147 forceinline void
00148 Inter<I,J>::init(I& i0, J& j0) {
00149 i = i0; j = j0;
00150 operator ++();
00151 }
00152
00153
00154
00155
00156
00157
00158
00159 forceinline
00160 NaryInter::NaryInter(void) {}
00161
00162 template<class I>
00163 forceinline void
00164 NaryInter::init(Region& r, I& i) {
00165 RangeListIter::init(r);
00166 f = NULL;
00167 set(copy(i));
00168 }
00169
00170 template<class I, class J>
00171 forceinline void
00172 NaryInter::init(Region& r, I& i, J& j) {
00173 RangeListIter::init(r);
00174 f = NULL;
00175 RangeList* h;
00176 RangeList** c = &h;
00177 while (i() && j()) {
00178 do {
00179 while (i() && (i.max() < j.min())) ++i;
00180 if (!i()) goto done;
00181 while (j() && (j.max() < i.min())) ++j;
00182 if (!j()) goto done;
00183 } while (i.max() < j.min());
00184
00185 RangeList* t = range(std::max(i.min(),j.min()),
00186 std::min(i.max(),j.max()));
00187 *c = t; c = &t->next;
00188 if (i.max() < j.max()) ++i; else ++j;
00189 }
00190 done:
00191 *c = NULL;
00192 set(h);
00193 }
00194
00195 template<class I>
00196 forceinline void
00197 NaryInter::init(Region& r, I* i, int n) {
00198 RangeListIter::init(r);
00199 f = NULL;
00200 if ((n > 0) && i[0]()) {
00201 RangeList* h;
00202 RangeList** c = &h;
00203
00204 int min = i[0].min();
00205 while (i[0]()) {
00206
00207 int max = i[0].max();
00208
00209 restart:
00210 for (int j=n; j--;) {
00211
00212 while (i[j]() && (i[j].max() < min))
00213 ++i[j];
00214 if (!i[j]())
00215 goto done;
00216 if (i[j].min() > max) {
00217 min=i[j].min();
00218 max=i[j].max();
00219 goto restart;
00220 }
00221
00222 if (min < i[j].min())
00223 min = i[j].min();
00224 if (max > i[j].max())
00225 max = i[j].max();
00226 }
00227 RangeList* t = range(min,max);
00228 *c = t; c = &t->next;
00229
00230 min = max + 2;
00231 }
00232 done:
00233 *c = NULL;
00234 set(h);
00235 }
00236 }
00237
00238 template<class I>
00239 forceinline
00240 NaryInter::NaryInter(Region& r, I& i) {
00241 init(r, i);
00242 }
00243 template<class I, class J>
00244 forceinline
00245 NaryInter::NaryInter(Region& r, I& i, J& j) {
00246 init(r, i, j);
00247 }
00248 template<class I>
00249 forceinline
00250 NaryInter::NaryInter(Region& r, I* i, int n) {
00251 init(r, i, n);
00252 }
00253
00254 template<class I>
00255 forceinline void
00256 NaryInter::operator &=(I& i) {
00257 RangeList* j = get();
00258
00259 RangeList* h;
00260 RangeList** c = &h;
00261 while (i() && (j != NULL)) {
00262 do {
00263 while (i() && (i.max() < j->min))
00264 ++i;
00265 if (!i()) goto done;
00266 while ((j != NULL) && (j->max < i.min())) {
00267 RangeList* t = j->next;
00268 j->next = f; f = j;
00269 j = t;
00270 }
00271 if (j == NULL) goto done;
00272 } while (i.max() < j->min);
00273
00274 RangeList* t = range(std::max(i.min(),j->min),
00275 std::min(i.max(),j->max),f);
00276 *c = t; c = &t->next;
00277 if (i.max() < j->max) {
00278 ++i;
00279 } else {
00280 RangeList* tn = j->next;
00281 j->next = f; f = j;
00282 j = tn;
00283 }
00284 }
00285 done:
00286
00287 while (j != NULL) {
00288 RangeList* t = j->next;
00289 j->next = f; f = j;
00290 j = t;
00291 }
00292 *c = NULL;
00293 set(h);
00294 }
00295
00296 forceinline NaryInter&
00297 NaryInter::operator =(const NaryInter& m) {
00298 f = NULL;
00299 return static_cast<NaryInter&>(RangeListIter::operator =(m));
00300 }
00301
00302 }}}
00303
00304
00305