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
00068 bool touching(const Range& r) const {
00069 return std::max(begin_, r.begin_) <= std::min(end_, r.end_);
00070 }
00071
00073 void merge(const Range& r) {
00074 assert(touching(r));
00075 begin_ = std::min(begin_, r.begin_);
00076 end_ = std::max(end_, r.end_);
00077 }
00078
00079 operator bool() const { return !empty(); }
00080
00081 template <class S> void serialize(S& s) { s(begin_)(end_); }
00082
00083 private:
00084 T begin_, end_;
00085 };
00086
00087
00093 template <class T>
00094 class RangeSet
00095 : boost::additive1<RangeSet<T>,
00096 boost::additive2<RangeSet<T>, Range<T>,
00097 boost::additive2<RangeSet<T>, T> > >
00098 {
00099 public:
00100 typedef qpid::Range<T> Range;
00101
00102 private:
00103 typedef InlineVector<Range, 3> Ranges;
00104
00105 public:
00106
00107 class iterator : public boost::iterator_facade<
00108 iterator,
00109 const T,
00110 boost::forward_traversal_tag>
00111 {
00112 public:
00113 iterator() : ranges(), iter(), value() {}
00114
00115 private:
00116 typedef typename Ranges::const_iterator RangesIter;
00117 iterator(const Ranges& r, const RangesIter& i, const T& t)
00118 : ranges(&r), iter(i), value(t) {}
00119
00120 void increment();
00121 bool equal(const iterator& i) const;
00122 const T& dereference() const { return value; }
00123
00124 const Ranges* ranges;
00125 RangesIter iter;
00126 T value;
00127
00128 friend class RangeSet<T>;
00129 friend class boost::iterator_core_access;
00130 };
00131
00132 typedef iterator const_iterator;
00133
00134 RangeSet() {}
00135 explicit RangeSet(const Range& r) { *this += r; }
00136 RangeSet(const T& a, const T& b) { *this += Range(a,b); }
00137
00138 bool contiguous() const { return ranges.size() <= 1; }
00139
00140 bool contains(const T& t) const;
00141 bool contains(const Range&) const;
00142
00144 Range toRange() const;
00145
00146 bool operator==(const RangeSet<T>&) const;
00147
00148 void addRange (const Range&);
00149 void addSet (const RangeSet&);
00150
00151 RangeSet& operator+=(const T& t) { return *this += Range(t); }
00152 RangeSet& operator+=(const Range& r) { addRange(r); return *this; }
00153 RangeSet& operator+=(const RangeSet& s) { addSet(s); return *this; }
00154
00155 void removeRange (const Range&);
00156 void removeSet (const RangeSet&);
00157
00158 RangeSet& operator-=(const T& t) { return *this -= Range(t); }
00159 RangeSet& operator-=(const Range& r) { removeRange(r); return *this; }
00160 RangeSet& operator-=(const RangeSet& s) { removeSet(s); return *this; }
00161
00162 T front() const { return ranges.front().begin(); }
00163 T back() const { return ranges.back().end(); }
00164
00165
00166 iterator begin() const;
00167 iterator end() const;
00168
00169
00170 typedef typename Ranges::const_iterator RangeIterator;
00171 RangeIterator rangesBegin() const { return ranges.begin(); }
00172 RangeIterator rangesEnd() const { return ranges.end(); }
00173 size_t rangesSize() const { return ranges.size(); }
00174
00175 bool empty() const { return ranges.empty(); }
00176 void clear() { ranges.clear(); }
00177
00181 Range 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))); }
00185 template <class S> void decode(S& s) { uint16_t sz; s(sz); ranges.resize(sz/sizeof(Range)); }
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(), t);
00212 return i != ranges.end() && i->contains(t);
00213 }
00214
00215 template <class T>
00216 bool RangeSet<T>::contains(const Range& r) const {
00217 typename Ranges::const_iterator i =
00218 std::lower_bound(ranges.begin(), ranges.end(), r.begin());
00219 return i != ranges.end() && i->contains(r);
00220 }
00221
00222 template <class T> void RangeSet<T>::addRange(const Range& r) {
00223 if (r.empty()) return;
00224 typename Ranges::iterator i =
00225 std::lower_bound(ranges.begin(), ranges.end(), r.begin());
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 std::for_each(s.ranges.begin(), s.ranges.end(),
00241 boost::bind((RangeSet<T>& (RangeSet<T>::*)(const Range&))&RangeSet<T>::operator+=, this, _1));
00242 }
00243
00244 template <class T> void RangeSet<T>::removeRange(const Range& r) {
00245 if (r.empty()) return;
00246 typename Ranges::iterator i,j;
00247 i = std::lower_bound(ranges.begin(), ranges.end(), r.begin());
00248 if (i == ranges.end() || i->begin() >= r.end())
00249 return;
00250 if (*i == r)
00251 ranges.erase(i);
00252 else if (i->strictContains(r)) {
00253 Range i1(i->begin(), r.begin());
00254 Range i2(r.end(), i->end());
00255 *i = i2;
00256 ranges.insert(i, i1);
00257 } else {
00258 if (i->begin() < r.begin()) {
00259 i->end(r.begin());
00260 ++i;
00261 }
00262 for (j = i; j != ranges.end() && r.contains(*j); ++j)
00263 ;
00264 if (j != ranges.end() && j->end() > r.end())
00265 j->begin(r.end());
00266 ranges.erase(i,j);
00267 }
00268 }
00269
00270 template <class T> void RangeSet<T>::removeSet(const RangeSet& r) {
00271 std::for_each(
00272 r.ranges.begin(), r.ranges.end(),
00273 boost::bind(&RangeSet<T>::removeRange, this, _1));
00274 }
00275
00276 template <class T> Range<T> RangeSet<T>::toRange() const {
00277 assert(contiguous());
00278 return empty() ? Range() : ranges.front();
00279 }
00280
00281 template <class T> void RangeSet<T>::iterator::increment() {
00282 assert(ranges && iter != ranges->end());
00283 if (!iter->contains(++value)) {
00284 ++iter;
00285 if (iter == ranges->end())
00286 *this=iterator();
00287 else
00288 value=iter->begin();
00289 }
00290 }
00291
00292 template <class T> bool RangeSet<T>::operator==(const RangeSet<T>& r) const {
00293 return ranges.size() == r.ranges.size() && std::equal(ranges.begin(), ranges.end(), r.ranges.begin());
00294 }
00295
00296 template <class T> typename RangeSet<T>::iterator RangeSet<T>::begin() const {
00297 return empty() ? end() : iterator(ranges, ranges.begin(), front());
00298 }
00299
00300 template <class T> typename RangeSet<T>::iterator RangeSet<T>::end() const {
00301 return iterator();
00302 }
00303
00304 template <class T> bool RangeSet<T>::iterator::equal(const iterator& i) const {
00305 return ranges==i.ranges && (ranges==0 || value==i.value);
00306 }
00307
00308 template <class T> Range<T> RangeSet<T>::rangeContaining(const T& t) const {
00309 typename Ranges::const_iterator i =
00310 std::lower_bound(ranges.begin(), ranges.end(), t);
00311 return (i != ranges.end() && i->contains(t)) ? *i : Range(t,t);
00312 }
00313
00314
00315 }
00316
00317
00318 #endif