Apache Qpid - AMQP Messaging for Java JMS, C++, Python, Ruby, and .NET Apache Qpid Documentation
RangeSet.h
Go to the documentation of this file.
1 #ifndef QPID_RANGESET_H
2 #define QPID_RANGESET_H
3 
4 /*
5  *
6  * Licensed to the Apache Software Foundation (ASF) under one
7  * or more contributor license agreements. See the NOTICE file
8  * distributed with this work for additional information
9  * regarding copyright ownership. The ASF licenses this file
10  * to you under the Apache License, Version 2.0 (the
11  * "License"); you may not use this file except in compliance
12  * with the License. You may obtain a copy of the License at
13  *
14  * http://www.apache.org/licenses/LICENSE-2.0
15  *
16  * Unless required by applicable law or agreed to in writing,
17  * software distributed under the License is distributed on an
18  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
19  * KIND, either express or implied. See the License for the
20  * specific language governing permissions and limitations
21  * under the License.
22  *
23  */
24 
25 #include "qpid/InlineVector.h"
26 #include <boost/iterator/iterator_facade.hpp>
27 #include <boost/operators.hpp>
28 #include <boost/bind.hpp>
29 #include <algorithm>
30 #include <numeric>
31 
32 namespace qpid {
33 
38 template <class T>
39 class Range {
40  public:
41  static Range makeClosed(const T& first, T last) { return Range(first, ++last); }
42 
43  Range() : begin_(), end_() {}
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); }
46 
47  T begin() const { return begin_; }
49  T end() const { return end_; }
50 
51  T first() const { assert(!empty()); return begin_; }
53  T last() const { assert(!empty()); T ret=end_; return --ret; }
54 
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_; }
59 
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_; }
62  bool strictContains(const Range& r) const { return begin_ < r.begin_ && r.end_ < end_; }
63 
64  bool operator==(const Range& x) { return begin_ == x.begin_ && end_== x.end_; }
65 
66  bool operator<(const T& t) const { return end_ < t; }
67  bool operator<(const Range<T>& r) const { return end_ < r.begin_; }
68 
70  bool touching(const Range& r) const {
71  return std::max(begin_, r.begin_) <= std::min(end_, r.end_);
72  }
73 
75  void merge(const Range& r) {
76  assert(touching(r));
77  begin_ = std::min(begin_, r.begin_);
78  end_ = std::max(end_, r.end_);
79  }
80 
81  operator bool() const { return !empty(); }
82 
83  template <class S> void serialize(S& s) { s(begin_)(end_); }
84 
85  private:
86  T begin_, end_;
87 };
88 
89 
95 template <class T>
96 class RangeSet
97  : boost::additive1<RangeSet<T>,
98  boost::additive2<RangeSet<T>, Range<T>,
99  boost::additive2<RangeSet<T>, T> > >
100 {
101  typedef InlineVector<Range<T>, 3> Ranges; // TODO aconway 2008-04-21: what's the optimial inlined value?
102 
103  public:
104 
105  class iterator : public boost::iterator_facade<
106  iterator,
107  const T,
108  boost::forward_traversal_tag>
109  {
110  public:
111  iterator() : ranges(), iter(), value() {}
112 
113  private:
114  typedef typename Ranges::const_iterator RangesIter;
115  iterator(const Ranges& r, const RangesIter& i, const T& t)
116  : ranges(&r), iter(i), value(t) {}
117 
118  void increment();
119  bool equal(const iterator& i) const;
120  const T& dereference() const { return value; }
121 
122  const Ranges* ranges;
123  RangesIter iter;
124  T value;
125 
126  friend class RangeSet<T>;
127  friend class boost::iterator_core_access;
128  };
129 
131 
132  RangeSet() {}
133  explicit RangeSet(const Range<T>& r) { *this += r; }
134  RangeSet(const T& a, const T& b) { *this += Range<T>(a,b); }
135 
136  bool contiguous() const { return ranges.size() <= 1; }
137 
138  bool contains(const T& t) const;
139  bool contains(const Range<T>&) const;
140 
142  Range<T> toRange() const;
143 
144  bool operator==(const RangeSet<T>&) const;
145 
146  void addRange (const Range<T>&);
147  void addSet (const RangeSet<T>&);
148 
149  RangeSet<T>& operator+=(const T& t) { return *this += Range<T>(t); }
150  RangeSet<T>& operator+=(const Range<T>& r) { addRange(r); return *this; }
151  RangeSet<T>& operator+=(const RangeSet<T>& s) { addSet(s); return *this; }
152 
153  void removeRange (const Range<T>&);
154  void removeSet (const RangeSet<T>&);
155 
156  RangeSet<T>& operator-=(const T& t) { return *this -= Range<T>(t); }
157  RangeSet<T>& operator-=(const Range<T>& r) { removeRange(r); return *this; }
158  RangeSet<T>& operator-=(const RangeSet<T>& s) { removeSet(s); return *this; }
159 
160  T front() const { return ranges.front().begin(); }
161  T back() const { return ranges.back().end(); }
162 
163  // Iterate over elements in the set.
164  iterator begin() const;
165  iterator end() const;
166 
167  // Iterate over ranges in the set.
168  typedef typename Ranges::const_iterator RangeIterator;
169  RangeIterator rangesBegin() const { return ranges.begin(); }
170  RangeIterator rangesEnd() const { return ranges.end(); }
171  size_t rangesSize() const { return ranges.size(); }
172 
173  // The difference between the start and end of this range set
174  uint32_t span() const;
175 
176  size_t size() const;
177  bool empty() const { return ranges.empty(); }
178  void clear() { ranges.clear(); }
179 
183  Range<T> rangeContaining(const T&) const;
184 
185  template <class S> void serialize(S& s) { s.split(*this); s(ranges.begin(), ranges.end()); }
186  template <class S> void encode(S& s) const { s(uint16_t(ranges.size()*sizeof(Range<T>))); }
187  template <class S> void decode(S& s) { uint16_t sz; s(sz); ranges.resize(sz/sizeof(Range<T>)); }
188 
189  private:
190  static size_t accumulateSize(size_t s, const Range<T>& r) { return s+r.size(); }
191  Ranges ranges;
192 
193  template <class U> friend std::ostream& operator<<(std::ostream& o, const RangeSet<U>& r);
194 
195  friend class iterator;
196 };
197 
198 template <class T>
199 std::ostream& operator<<(std::ostream& o, const Range<T>& r) {
200  return o << "[" << r.begin() << "," << r.end() << ")";
201 }
202 
203 template <class T>
204 std::ostream& operator<<(std::ostream& o, const RangeSet<T>& rs) {
205  std::ostream_iterator<Range<T> > i(o, " ");
206  o << "{ ";
207  std::copy(rs.ranges.begin(), rs.ranges.end(), i);
208  return o << "}";
209 }
210 
211 template <class T>
212 bool RangeSet<T>::contains(const T& t) const {
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);
216 }
217 
218 template <class T>
219 bool RangeSet<T>::contains(const Range<T>& r) const {
220  typename Ranges::const_iterator i =
221  std::lower_bound(ranges.begin(), ranges.end(), r);
222  return i != ranges.end() && i->contains(r);
223 }
224 
225 template <class T> void RangeSet<T>::addRange(const Range<T>& 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))
229  ranges.insert(i, r); // No overlap
230  else {
231  i->merge(r);
232  typename Ranges::iterator j = i;
233  while (++j != ranges.end() && i->touching(*j))
234  i->merge(*j);
235  ranges.erase(i+1,j);
236  }
237 }
238 
239 
240 template <class T> void RangeSet<T>::addSet(const RangeSet<T>& s) {
241  typedef RangeSet<T>& (RangeSet<T>::*RangeSetRangeOp)(const Range<T>&);
242  std::for_each(s.ranges.begin(), s.ranges.end(),
243  boost::bind((RangeSetRangeOp)&RangeSet<T>::operator+=, this, _1));
244 }
245 
246 template <class T> void RangeSet<T>::removeRange(const Range<T>& r) {
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())
251  return; // Outside of set
252  if (*i == r) // Erase i
253  ranges.erase(i);
254  else if (i->strictContains(r)) { // Split i
255  Range<T> i1(i->begin(), r.begin());
256  Range<T> i2(r.end(), i->end());
257  *i = i2;
258  ranges.insert(i, i1);
259  } else {
260  if (i->begin() < r.begin()) { // Truncate i
261  i->end(r.begin());
262  ++i;
263  }
264  for (j = i; j != ranges.end() && r.contains(*j); ++j)
265  ; // Ranges to erase.
266  if (j != ranges.end() && r.end() > j->begin())
267  j->begin(r.end()); // Truncate j
268  ranges.erase(i,j);
269  }
270 }
271 
272 template <class T> void RangeSet<T>::removeSet(const RangeSet<T>& r) {
273  std::for_each(
274  r.ranges.begin(), r.ranges.end(),
275  boost::bind(&RangeSet<T>::removeRange, this, _1));
276 }
277 
278 template <class T> Range<T> RangeSet<T>::toRange() const {
279  assert(contiguous());
280  return empty() ? Range<T>() : ranges.front();
281 }
282 
283 template <class T> void RangeSet<T>::iterator::increment() {
284  assert(ranges && iter != ranges->end());
285  if (!iter->contains(++value)) {
286  ++iter;
287  if (iter == ranges->end())
288  *this=iterator(); // end() iterator
289  else
290  value=iter->begin();
291  }
292 }
293 
294 template <class T> bool RangeSet<T>::operator==(const RangeSet<T>& r) const {
295  return ranges.size() == r.ranges.size() && std::equal(ranges.begin(), ranges.end(), r.ranges.begin());
296 }
297 
298 template <class T> typename RangeSet<T>::iterator RangeSet<T>::begin() const {
299  return empty() ? end() : iterator(ranges, ranges.begin(), front());
300 }
301 
302 template <class T> typename RangeSet<T>::iterator RangeSet<T>::end() const {
303  return iterator();
304 }
305 
306 template <class T> bool RangeSet<T>::iterator::equal(const iterator& i) const {
307  return ranges==i.ranges && (ranges==0 || value==i.value);
308 }
309 
310 template <class T> Range<T> RangeSet<T>::rangeContaining(const T& t) const {
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);
314 }
315 
316 template <class T> uint32_t RangeSet<T>::span() const {
317  if (ranges.empty()) return 0;
318  return ranges.back().last() - ranges.front().first();
319 }
320 
321 template <class T> size_t RangeSet<T>::size() const {
322  return std::accumulate(rangesBegin(), rangesEnd(), 0, &RangeSet<T>::accumulateSize);
323 }
324 
325 } // namespace qpid
326 
327 
328 #endif

Qpid C++ API Reference
Generated on Wed Nov 7 2012 for Qpid C++ Client API by doxygen 1.8.1.1