ranges-union.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 namespace Gecode { namespace Iter { namespace Ranges {
00039
00046 template<class I, class J>
00047 class Union : public MinMax {
00048 private:
00050 IsRangeIter<I> _checkI;
00052 IsRangeIter<J> _checkJ;
00053 private:
00055 I i;
00057 J j;
00058 public:
00060
00061
00062 Union(void);
00064 Union(I& i, J& j);
00066 void init(I& i, J& j);
00068
00070
00071
00072 void operator ++(void);
00074 };
00075
00076
00082 template<class I>
00083 class NaryUnion : public MinMax {
00084 private:
00086 IsRangeIter<I> _checkI;
00087 protected:
00089 class RangeUnionOrder {
00090 public:
00091 bool operator ()(const I&, const I&) const;
00092 };
00094 RangeUnionOrder order;
00096 PriorityQueue<I,RangeUnionOrder> r;
00097 public:
00099
00100
00101 NaryUnion(void);
00103 NaryUnion(I* i, int n);
00105 void init(I* i, int n);
00107
00109
00110
00111 void operator ++(void);
00113 };
00114
00115
00116
00117
00118
00119
00120
00121
00122 template<class I, class J>
00123 inline void
00124 Union<I,J>::operator ++(void) {
00125 if (!i() && !j()) {
00126 finish(); return;
00127 }
00128 if (!i()) {
00129 mi = j.min(); ma = j.max(); ++j; return;
00130 }
00131 if (!j()) {
00132 mi = i.min(); ma = i.max(); ++i; return;
00133 }
00134 if (i.min() < j.min()) {
00135 mi = i.min(); ma = i.max(); ++i;
00136 } else {
00137 mi = j.min(); ma = j.max(); ++j;
00138 }
00139 bool goOn;
00140 do {
00141 goOn = false;
00142 if (i() && (i.min() <= ma+1)) {
00143 ma = std::max(ma,i.max()); ++i; goOn=true;
00144 }
00145 if (j() && (j.min() <= ma+1)) {
00146 ma = std::max(ma,j.max()); ++j; goOn=true;
00147 }
00148 } while (goOn);
00149 }
00150
00151
00152 template<class I, class J>
00153 forceinline
00154 Union<I,J>::Union(void) {}
00155
00156 template<class I, class J>
00157 forceinline
00158 Union<I,J>::Union(I& i0, J& j0)
00159 : i(i0), j(j0) {
00160 operator ++();
00161 }
00162
00163 template<class I, class J>
00164 forceinline void
00165 Union<I,J>::init(I& i0, J& j0) {
00166 i = i0; j = j0;
00167 operator ++();
00168 }
00169
00170
00171
00172
00173
00174
00175
00176
00177 template<class I>
00178 forceinline bool
00179 NaryUnion<I>::RangeUnionOrder::operator ()(const I& a, const I& b) const {
00180 return a.min() > b.min();
00181 }
00182
00183 template<class I>
00184 inline void
00185 NaryUnion<I>::operator ++(void) {
00186 if (r.empty()) {
00187 finish(); return;
00188 }
00189 mi = r.top().min();
00190 ma = r.top().max();
00191 do {
00192 if (ma < r.top().max())
00193 ma = r.top().max();
00194 ++(r.top());
00195 if (!(r.top())()) {
00196 r.remove();
00197 if (r.empty())
00198 return;
00199 } else {
00200 r.fix();
00201 }
00202 } while (ma+1 >= r.top().min());
00203 }
00204
00205
00206 template<class I>
00207 forceinline
00208 NaryUnion<I>::NaryUnion(void) {}
00209
00210 template<class I>
00211 inline
00212 NaryUnion<I>::NaryUnion(I* r0, int n)
00213 : order(), r(n,order) {
00214 for (int i = n; i--; )
00215 if (r0[i]())
00216 r.insert(r0[i]);
00217 operator ++();
00218 }
00219
00220 template<class I>
00221 inline void
00222 NaryUnion<I>::init(I* r0, int n) {
00223 r.init(n,order);
00224 for (int i = n; i--; )
00225 if (r0[i]())
00226 r.insert(r0[i]);
00227 operator ++();
00228 }
00229
00230 }}}
00231
00232
00233