1 #ifndef QPID_RANGESET_H
2 #define QPID_RANGESET_H
26 #include <boost/iterator/iterator_facade.hpp>
27 #include <boost/operators.hpp>
28 #include <boost/bind.hpp>
44 explicit Range(
const T& t) : begin_(t), end_(t) { ++end_; }
45 Range(
const T& b,
const T& e) : begin_(b), end_(e) { assert(b <= e); }
47 T
begin()
const {
return begin_; }
49 T
end()
const {
return end_; }
53 T
last()
const { assert(!
empty()); T ret=end_;
return --ret; }
55 void begin(
const T& t) { begin_ = t; }
56 void end(
const T& t) { end_ = t; }
57 size_t size()
const {
return end_ - begin_; }
58 bool empty()
const {
return begin_ == end_; }
60 bool contains(
const T& x)
const {
return begin_ <= x && x < end_; }
61 bool contains(
const Range& r)
const {
return begin_ <= r.begin_ && r.end_ <= end_; }
66 bool operator<(
const T& t)
const {
return end_ < t; }
67 bool operator<(const Range<T>& r)
const {
return end_ < r.begin_; }
71 return std::max(begin_, r.begin_) <= std::min(end_, r.end_);
77 begin_ = std::min(begin_, r.begin_);
78 end_ = std::max(end_, r.end_);
81 operator bool()
const {
return !
empty(); }
83 template <
class S>
void serialize(S& s) { s(begin_)(end_); }
97 : boost::additive1<RangeSet<T>,
98 boost::additive2<RangeSet<T>, Range<T>,
99 boost::additive2<RangeSet<T>, T> > >
108 boost::forward_traversal_tag>
114 typedef typename Ranges::const_iterator RangesIter;
116 : ranges(&r), iter(i), value(t) {}
119 bool equal(
const iterator& i)
const;
120 const T& dereference()
const {
return value; }
122 const Ranges* ranges;
127 friend class boost::iterator_core_access;
160 T
front()
const {
return ranges.front().begin(); }
161 T
back()
const {
return ranges.back().end(); }
177 bool empty()
const {
return ranges.empty(); }
185 template <
class S>
void serialize(S& s) { s.split(*
this); s(ranges.begin(), ranges.end()); }
190 static size_t accumulateSize(
size_t s,
const Range<T>& r) {
return s+r.
size(); }
193 template <
class U>
friend std::ostream& operator<<(std::ostream& o, const RangeSet<U>& r);
199 std::ostream& operator<<(std::ostream& o, const Range<T>& r) {
200 return o <<
"[" << r.begin() <<
"," << r.end() <<
")";
204 std::ostream& operator<<(std::ostream& o, const RangeSet<T>& rs) {
205 std::ostream_iterator<Range<T> > i(o,
" ");
207 std::copy(rs.ranges.begin(), rs.ranges.end(), i);
213 typename Ranges::const_iterator i =
214 std::lower_bound(ranges.begin(), ranges.end(),
Range<T>(t));
215 return i != ranges.end() && i->contains(t);
220 typename Ranges::const_iterator i =
221 std::lower_bound(ranges.begin(), ranges.end(), r);
222 return i != ranges.end() && i->contains(r);
226 if (r.
empty())
return;
227 typename Ranges::iterator i = std::lower_bound(ranges.begin(), ranges.end(), r);
228 if (i == ranges.end() || !i->touching(r))
232 typename Ranges::iterator j = i;
233 while (++j != ranges.end() && i->touching(*j))
242 std::for_each(s.ranges.begin(), s.ranges.end(),
247 if (r.
empty())
return;
248 typename Ranges::iterator i,j;
249 i = std::lower_bound(ranges.begin(), ranges.end(), r);
250 if (i == ranges.end() || i->begin() >= r.
end())
254 else if (i->strictContains(r)) {
258 ranges.insert(i, i1);
260 if (i->begin() < r.
begin()) {
264 for (j = i; j != ranges.end() && r.
contains(*j); ++j)
266 if (j != ranges.end() && r.
end() > j->begin())
274 r.ranges.begin(), r.ranges.end(),
279 assert(contiguous());
280 return empty() ?
Range<T>() : ranges.front();
284 assert(ranges && iter != ranges->end());
285 if (!iter->contains(++value)) {
287 if (iter == ranges->end())
295 return ranges.size() == r.ranges.size() && std::equal(ranges.begin(), ranges.end(), r.ranges.begin());
307 return ranges==i.ranges && (ranges==0 || value==i.value);
311 typename Ranges::const_iterator i =
312 std::lower_bound(ranges.begin(), ranges.end(),
Range<T>(t));
313 return (i != ranges.end() && i->contains(t)) ? *i :
Range<T>(t,t);
317 if (ranges.empty())
return 0;
318 return ranges.back().last() - ranges.front().first();