00001 #ifndef QPID_RANGESET_H
00002 #define QPID_RANGESET_H
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025 #include "qpid/InlineVector.h"
00026 #include <boost/iterator/iterator_facade.hpp>
00027 #include <boost/operators.hpp>
00028 #include <boost/bind.hpp>
00029 #include <algorithm>
00030
00031 namespace qpid {
00032
00037 template <class T>
00038 class Range {
00039 public:
00040 static Range makeClosed(const T& first, T last) { return Range(first, ++last); }
00041
00042 Range() : begin_(), end_() {}
00043 explicit Range(const T& t) : begin_(t), end_(t) { ++end_; }
00044 Range(const T& b, const T& e) : begin_(b), end_(e) { assert(b <= e); }
00045
00046 T begin() const { return begin_; }
00048 T end() const { return end_; }
00049
00050 T first() const { assert(!empty()); return begin_; }
00052 T last() const { assert(!empty()); T ret=end_; return --ret; }
00053
00054 void begin(const T& t) { begin_ = t; }
00055 void end(const T& t) { end_ = t; }
00056
00057 bool empty() const { return begin_ == end_; }
00058
00059 bool contains(const T& x) const { return begin_ <= x && x < end_; }
00060 bool contains(const Range& r) const { return begin_ <= r.begin_ && r.end_ <= end_; }
00061 bool strictContains(const Range& r) const { return begin_ < r.begin_ && r.end_ < end_; }
00062
00063 bool operator==(const Range& x) { return begin_ == x.begin_ && end_== x.end_; }
00064
00065 bool operator<(const T& t) const { return end_ < t; }
00066 bool operator<(const Range<T>& r) const { return end_ < r.begin_; }
00067
00069 bool touching(const Range& r) const {
00070 return std::max(begin_, r.begin_) <= std::min(end_, r.end_);
00071 }
00072
00074 void merge(const Range& r) {
00075 assert(touching(r));
00076 begin_ = std::min(begin_, r.begin_);
00077 end_ = std::max(end_, r.end_);
00078 }
00079
00080 operator bool() const { return !empty(); }
00081
00082 template <class S> void serialize(S& s) { s(begin_)(end_); }
00083
00084 private:
00085 T begin_, end_;
00086 };
00087
00088
00094 template <class T>
00095 class RangeSet
00096 : boost::additive1<RangeSet<T>,
00097 boost::additive2<RangeSet<T>, Range<T>,
00098 boost::additive2<RangeSet<T>, T> > >
00099 {
00100 typedef InlineVector<Range<T>, 3> Ranges;
00101
00102 public:
00103
00104 class iterator : public boost::iterator_facade<
00105 iterator,
00106 const T,
00107 boost::forward_traversal_tag>
00108 {
00109 public:
00110 iterator() : ranges(), iter(), value() {}
00111
00112 private:
00113 typedef typename Ranges::const_iterator RangesIter;
00114 iterator(const Ranges& r, const RangesIter& i, const T& t)
00115 : ranges(&r), iter(i), value(t) {}
00116
00117 void increment();
00118 bool equal(const iterator& i) const;
00119 const T& dereference() const { return value; }
00120
00121 const Ranges* ranges;
00122 RangesIter iter;
00123 T value;
00124
00125 friend class RangeSet<T>;
00126 friend class boost::iterator_core_access;
00127 };
00128
00129 typedef iterator const_iterator;
00130
00131 RangeSet() {}
00132 explicit RangeSet(const Range<T>& r) { *this += r; }
00133 RangeSet(const T& a, const T& b) { *this += Range<T>(a,b); }
00134
00135 bool contiguous() const { return ranges.size() <= 1; }
00136
00137 bool contains(const T& t) const;
00138 bool contains(const Range<T>&) const;
00139
00141 Range<T> toRange() const;
00142
00143 bool operator==(const RangeSet<T>&) const;
00144
00145 void addRange (const Range<T>&);
00146 void addSet (const RangeSet<T>&);
00147
00148 RangeSet<T>& operator+=(const T& t) { return *this += Range<T>(t); }
00149 RangeSet<T>& operator+=(const Range<T>& r) { addRange(r); return *this; }
00150 RangeSet<T>& operator+=(const RangeSet<T>& s) { addSet(s); return *this; }
00151
00152 void removeRange (const Range<T>&);
00153 void removeSet (const RangeSet<T>&);
00154
00155 RangeSet<T>& operator-=(const T& t) { return *this -= Range<T>(t); }
00156 RangeSet<T>& operator-=(const Range<T>& r) { removeRange(r); return *this; }
00157 RangeSet<T>& operator-=(const RangeSet<T>& s) { removeSet(s); return *this; }
00158
00159 T front() const { return ranges.front().begin(); }
00160 T back() const { return ranges.back().end(); }
00161
00162
00163 iterator begin() const;
00164 iterator end() const;
00165
00166
00167 typedef typename Ranges::const_iterator RangeIterator;
00168 RangeIterator rangesBegin() const { return ranges.begin(); }
00169 RangeIterator rangesEnd() const { return ranges.end(); }
00170 size_t rangesSize() const { return ranges.size(); }
00171
00172
00173 uint32_t span() const;
00174
00175 bool empty() const { return ranges.empty(); }
00176 void clear() { ranges.clear(); }
00177
00181 Range<T> rangeContaining(const T&) const;
00182
00183 template <class S> void serialize(S& s) { s.split(*this); s(ranges.begin(), ranges.end()); }
00184 template <class S> void encode(S& s) const { s(uint16_t(ranges.size()*sizeof(Range<T>))); }
00185 template <class S> void decode(S& s) { uint16_t sz; s(sz); ranges.resize(sz/sizeof(Range<T>)); }
00186
00187 private:
00188 Ranges ranges;
00189
00190 template <class U> friend std::ostream& operator<<(std::ostream& o, const RangeSet<U>& r);
00191
00192 friend class iterator;
00193 };
00194
00195 template <class T>
00196 std::ostream& operator<<(std::ostream& o, const Range<T>& r) {
00197 return o << "[" << r.begin() << "," << r.end() << ")";
00198 }
00199
00200 template <class T>
00201 std::ostream& operator<<(std::ostream& o, const RangeSet<T>& rs) {
00202 std::ostream_iterator<Range<T> > i(o, " ");
00203 o << "{ ";
00204 std::copy(rs.ranges.begin(), rs.ranges.end(), i);
00205 return o << "}";
00206 }
00207
00208 template <class T>
00209 bool RangeSet<T>::contains(const T& t) const {
00210 typename Ranges::const_iterator i =
00211 std::lower_bound(ranges.begin(), ranges.end(), Range<T>(t));
00212 return i != ranges.end() && i->contains(t);
00213 }
00214
00215 template <class T>
00216 bool RangeSet<T>::contains(const Range<T>& r) const {
00217 typename Ranges::const_iterator i =
00218 std::lower_bound(ranges.begin(), ranges.end(), r);
00219 return i != ranges.end() && i->contains(r);
00220 }
00221
00222 template <class T> void RangeSet<T>::addRange(const Range<T>& r) {
00223 if (r.empty()) return;
00224 typename Ranges::iterator i =
00225 std::lower_bound(ranges.begin(), ranges.end(), r);
00226 if (i == ranges.end() || !i->touching(r))
00227 ranges.insert(i, r);
00228 else {
00229 i->merge(r);
00230 typename Ranges::iterator j = i;
00231 if (++j != ranges.end() && i->touching(*j)) {
00232 i->merge(*j);
00233 ranges.erase(j);
00234 }
00235 }
00236 }
00237
00238
00239 template <class T> void RangeSet<T>::addSet(const RangeSet<T>& s) {
00240 typedef RangeSet<T>& (RangeSet<T>::*RangeSetRangeOp)(const Range<T>&);
00241 std::for_each(s.ranges.begin(), s.ranges.end(),
00242 boost::bind((RangeSetRangeOp)&RangeSet<T>::operator+=, this, _1));
00243 }
00244
00245 template <class T> void RangeSet<T>::removeRange(const Range<T>& r) {
00246 if (r.empty()) return;
00247 typename Ranges::iterator i,j;
00248 i = std::lower_bound(ranges.begin(), ranges.end(), r);
00249 if (i == ranges.end() || i->begin() >= r.end())
00250 return;
00251 if (*i == r)
00252 ranges.erase(i);
00253 else if (i->strictContains(r)) {
00254 Range<T> i1(i->begin(), r.begin());
00255 Range<T> i2(r.end(), i->end());
00256 *i = i2;
00257 ranges.insert(i, i1);
00258 } else {
00259 if (i->begin() < r.begin()) {
00260 i->end(r.begin());
00261 ++i;
00262 }
00263 for (j = i; j != ranges.end() && r.contains(*j); ++j)
00264 ;
00265 if (j != ranges.end() && j->end() > r.end())
00266 j->begin(r.end());
00267 ranges.erase(i,j);
00268 }
00269 }
00270
00271 template <class T> void RangeSet<T>::removeSet(const RangeSet<T>& r) {
00272 std::for_each(
00273 r.ranges.begin(), r.ranges.end(),
00274 boost::bind(&RangeSet<T>::removeRange, this, _1));
00275 }
00276
00277 template <class T> Range<T> RangeSet<T>::toRange() const {
00278 assert(contiguous());
00279 return empty() ? Range<T>() : ranges.front();
00280 }
00281
00282 template <class T> void RangeSet<T>::iterator::increment() {
00283 assert(ranges && iter != ranges->end());
00284 if (!iter->contains(++value)) {
00285 ++iter;
00286 if (iter == ranges->end())
00287 *this=iterator();
00288 else
00289 value=iter->begin();
00290 }
00291 }
00292
00293 template <class T> bool RangeSet<T>::operator==(const RangeSet<T>& r) const {
00294 return ranges.size() == r.ranges.size() && std::equal(ranges.begin(), ranges.end(), r.ranges.begin());
00295 }
00296
00297 template <class T> typename RangeSet<T>::iterator RangeSet<T>::begin() const {
00298 return empty() ? end() : iterator(ranges, ranges.begin(), front());
00299 }
00300
00301 template <class T> typename RangeSet<T>::iterator RangeSet<T>::end() const {
00302 return iterator();
00303 }
00304
00305 template <class T> bool RangeSet<T>::iterator::equal(const iterator& i) const {
00306 return ranges==i.ranges && (ranges==0 || value==i.value);
00307 }
00308
00309 template <class T> Range<T> RangeSet<T>::rangeContaining(const T& t) const {
00310 typename Ranges::const_iterator i =
00311 std::lower_bound(ranges.begin(), ranges.end(), Range<T>(t));
00312 return (i != ranges.end() && i->contains(t)) ? *i : Range<T>(t,t);
00313 }
00314
00315 template <class T> uint32_t RangeSet<T>::span() const {
00316 if (ranges.empty()) return 0;
00317 return ranges.back().last() - ranges.front().first();
00318 }
00319
00320
00321 }
00322
00323
00324 #endif