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