virtual-ranges-union.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 #include "gecode/support/static-pqueue.hh"
00023
00024 namespace Gecode { namespace Iter { namespace Ranges { namespace Virt {
00025
00033 class Union : public MinMax, public Iterator {
00035 Iterator* i;
00037 Iterator* j;
00038 Union(const Union&);
00039 public:
00041
00042
00043 Union(void);
00045 Union(Iterator* i, Iterator* j);
00047 ~Union(void);
00049
00051
00052
00053 virtual int min(void) const;
00055 virtual int max(void) const;
00057 virtual unsigned int width(void) const;
00059
00061
00062
00063 void operator++(void);
00065 virtual bool operator()(void);
00067 };
00068
00069
00075 class NaryUnion : public MinMax, public Iterator {
00076 private:
00077 NaryUnion(const NaryUnion&);
00078 protected:
00080 class RangeUnionOrder {
00081 public:
00082 bool operator()(const Iterator*, const Iterator*) const;
00083 };
00085 RangeUnionOrder order;
00087 Support::PQueue<Iterator*,RangeUnionOrder> r;
00088 public:
00090
00091
00092 NaryUnion(void);
00094 NaryUnion(Iterator** i, int n);
00096
00098
00099
00100 virtual int min(void) const;
00102 virtual int max(void) const;
00104 virtual unsigned int width(void) const;
00106
00108
00109
00110 void operator++(void);
00112 virtual bool operator()(void);
00114 };
00115
00116
00117
00118
00119
00120
00121
00122
00123 forceinline void
00124 Union::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 forceinline
00153 Union::Union(void) {}
00154
00155 forceinline
00156 Union::Union(Iterator* i0, Iterator* j0)
00157 : i(i0), j(j0) {
00158 operator++();
00159 }
00160
00161 forceinline
00162 Union::~Union(void) { delete i; delete j; }
00163
00164 forceinline bool
00165 Union::operator()(void) { return MinMax::operator()(); }
00166
00167 forceinline int
00168 Union::min(void) const { return MinMax::min(); }
00169
00170 forceinline int
00171 Union::max(void) const { return MinMax::max(); }
00172
00173 forceinline unsigned int
00174 Union::width(void) const { return MinMax::width(); }
00175
00176
00177
00178
00179
00180
00181 forceinline bool
00182 NaryUnion::RangeUnionOrder::operator()(const Iterator* a,
00183 const Iterator* b) const {
00184 return a->min() > b->min();
00185 }
00186
00187 inline void
00188 NaryUnion::operator++(void) {
00189 if (r.empty()) {
00190 finish(); return;
00191 }
00192 mi = r.top()->min();
00193 ma = r.top()->max();
00194 do {
00195 if (ma < r.top()->max())
00196 ma = r.top()->max();
00197 ++(*(r.top()));
00198 if (!((*r.top()))()) {
00199 r.remove();
00200 if (r.empty())
00201 return;
00202 } else {
00203 r.fix();
00204 }
00205 } while (ma+1 >= r.top()->min());
00206 }
00207
00208
00209 forceinline
00210 NaryUnion::NaryUnion(void) {}
00211
00212 inline
00213 NaryUnion::NaryUnion(Iterator** r0, int n)
00214 : order(), r(n,order) {
00215 for (int i = n; i--; )
00216 if ((*(r0[i]))())
00217 r.insert(r0[i]);
00218 operator++();
00219 }
00220
00221 forceinline bool
00222 NaryUnion::operator()(void) { return MinMax::operator()(); }
00223
00224 forceinline int
00225 NaryUnion::min(void) const { return MinMax::min(); }
00226
00227 forceinline int
00228 NaryUnion::max(void) const { return MinMax::max(); }
00229
00230 forceinline unsigned int
00231 NaryUnion::width(void) const { return MinMax::width(); }
00232
00233 }}}}
00234
00235
00236