From 366916dc747b462858252271a6993d244f59768a Mon Sep 17 00:00:00 2001 From: Alan Conway Date: Wed, 15 Jul 2009 16:45:21 +0000 Subject: Merge branch 'move_public_h_to_include' into trunk git-svn-id: https://svn.apache.org/repos/asf/qpid/trunk/qpid@794325 13f79535-47bb-0310-9956-ffa450edef68 --- cpp/src/qpid/RangeSet.h | 330 ------------------------------------------------ 1 file changed, 330 deletions(-) delete mode 100644 cpp/src/qpid/RangeSet.h (limited to 'cpp/src/qpid/RangeSet.h') diff --git a/cpp/src/qpid/RangeSet.h b/cpp/src/qpid/RangeSet.h deleted file mode 100644 index 1ba4fbbcef..0000000000 --- a/cpp/src/qpid/RangeSet.h +++ /dev/null @@ -1,330 +0,0 @@ -#ifndef QPID_RANGESET_H -#define QPID_RANGESET_H - -/* - * - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - * - */ - -#include "qpid/InlineVector.h" -#include -#include -#include -#include -#include - -namespace qpid { - -/** A range of values, used in RangeSet. - * Range(begin, end) includes begin but excludes end. - * Range::makeClosed(first,last) includes both first and last. - */ -template -class Range { - public: - static Range makeClosed(const T& first, T last) { return Range(first, ++last); } - - Range() : begin_(), end_() {} - explicit Range(const T& t) : begin_(t), end_(t) { ++end_; } - Range(const T& b, const T& e) : begin_(b), end_(e) { assert(b <= e); } - - T begin() const { return begin_; } - /** End of _open_ range, i.e. !contains(end()) */ - T end() const { return end_; } - - T first() const { assert(!empty()); return begin_; } - /** Last in closed range, i.e. contains(end()) */ - T last() const { assert(!empty()); T ret=end_; return --ret; } - - void begin(const T& t) { begin_ = t; } - void end(const T& t) { end_ = t; } - size_t size() const { return end_ - begin_; } - bool empty() const { return begin_ == end_; } - - bool contains(const T& x) const { return begin_ <= x && x < end_; } - bool contains(const Range& r) const { return begin_ <= r.begin_ && r.end_ <= end_; } - bool strictContains(const Range& r) const { return begin_ < r.begin_ && r.end_ < end_; } - - bool operator==(const Range& x) { return begin_ == x.begin_ && end_== x.end_; } - - bool operator<(const T& t) const { return end_ < t; } - bool operator<(const Range& r) const { return end_ < r.begin_; } - - /** touching ranges can be merged into a single range. */ - bool touching(const Range& r) const { - return std::max(begin_, r.begin_) <= std::min(end_, r.end_); - } - - /** @pre touching */ - void merge(const Range& r) { - assert(touching(r)); - begin_ = std::min(begin_, r.begin_); - end_ = std::max(end_, r.end_); - } - - operator bool() const { return !empty(); } - - template void serialize(S& s) { s(begin_)(end_); } - - private: - T begin_, end_; -}; - - -/** - * A set implemented as a list of [begin, end) ranges. - * T must be LessThanComparable and Incrementable. - * RangeSet only provides const iterators. - */ -template -class RangeSet - : boost::additive1, - boost::additive2, Range, - boost::additive2, T> > > -{ - typedef InlineVector, 3> Ranges; // TODO aconway 2008-04-21: what's the optimial inlined value? - - public: - - class iterator : public boost::iterator_facade< - iterator, - const T, - boost::forward_traversal_tag> - { - public: - iterator() : ranges(), iter(), value() {} - - private: - typedef typename Ranges::const_iterator RangesIter; - iterator(const Ranges& r, const RangesIter& i, const T& t) - : ranges(&r), iter(i), value(t) {} - - void increment(); - bool equal(const iterator& i) const; - const T& dereference() const { return value; } - - const Ranges* ranges; - RangesIter iter; - T value; - - friend class RangeSet; - friend class boost::iterator_core_access; - }; - - typedef iterator const_iterator; - - RangeSet() {} - explicit RangeSet(const Range& r) { *this += r; } - RangeSet(const T& a, const T& b) { *this += Range(a,b); } - - bool contiguous() const { return ranges.size() <= 1; } - - bool contains(const T& t) const; - bool contains(const Range&) const; - - /**@pre contiguous() */ - Range toRange() const; - - bool operator==(const RangeSet&) const; - - void addRange (const Range&); - void addSet (const RangeSet&); - - RangeSet& operator+=(const T& t) { return *this += Range(t); } - RangeSet& operator+=(const Range& r) { addRange(r); return *this; } - RangeSet& operator+=(const RangeSet& s) { addSet(s); return *this; } - - void removeRange (const Range&); - void removeSet (const RangeSet&); - - RangeSet& operator-=(const T& t) { return *this -= Range(t); } - RangeSet& operator-=(const Range& r) { removeRange(r); return *this; } - RangeSet& operator-=(const RangeSet& s) { removeSet(s); return *this; } - - T front() const { return ranges.front().begin(); } - T back() const { return ranges.back().end(); } - - // Iterate over elements in the set. - iterator begin() const; - iterator end() const; - - // Iterate over ranges in the set. - typedef typename Ranges::const_iterator RangeIterator; - RangeIterator rangesBegin() const { return ranges.begin(); } - RangeIterator rangesEnd() const { return ranges.end(); } - size_t rangesSize() const { return ranges.size(); } - - // The difference between the start and end of this range set - uint32_t span() const; - - size_t size() const; - bool empty() const { return ranges.empty(); } - void clear() { ranges.clear(); } - - /** Return the largest contiguous range containing x. - * Returns the empty range [x,x) if x is not in the set. - */ - Range rangeContaining(const T&) const; - - template void serialize(S& s) { s.split(*this); s(ranges.begin(), ranges.end()); } - template void encode(S& s) const { s(uint16_t(ranges.size()*sizeof(Range))); } - template void decode(S& s) { uint16_t sz; s(sz); ranges.resize(sz/sizeof(Range)); } - - private: - static size_t accumulateSize(size_t s, const Range& r) { return s+r.size(); } - Ranges ranges; - - template friend std::ostream& operator<<(std::ostream& o, const RangeSet& r); - - friend class iterator; -}; - -template -std::ostream& operator<<(std::ostream& o, const Range& r) { - return o << "[" << r.begin() << "," << r.end() << ")"; -} - -template -std::ostream& operator<<(std::ostream& o, const RangeSet& rs) { - std::ostream_iterator > i(o, " "); - o << "{ "; - std::copy(rs.ranges.begin(), rs.ranges.end(), i); - return o << "}"; -} - -template -bool RangeSet::contains(const T& t) const { - typename Ranges::const_iterator i = - std::lower_bound(ranges.begin(), ranges.end(), Range(t)); - return i != ranges.end() && i->contains(t); -} - -template -bool RangeSet::contains(const Range& r) const { - typename Ranges::const_iterator i = - std::lower_bound(ranges.begin(), ranges.end(), r); - return i != ranges.end() && i->contains(r); -} - -template void RangeSet::addRange(const Range& r) { - if (r.empty()) return; - typename Ranges::iterator i = - std::lower_bound(ranges.begin(), ranges.end(), r); - if (i == ranges.end() || !i->touching(r)) - ranges.insert(i, r); - else { - i->merge(r); - typename Ranges::iterator j = i; - if (++j != ranges.end() && i->touching(*j)) { - i->merge(*j); - ranges.erase(j); - } - } -} - - -template void RangeSet::addSet(const RangeSet& s) { - typedef RangeSet& (RangeSet::*RangeSetRangeOp)(const Range&); - std::for_each(s.ranges.begin(), s.ranges.end(), - boost::bind((RangeSetRangeOp)&RangeSet::operator+=, this, _1)); -} - -template void RangeSet::removeRange(const Range& r) { - if (r.empty()) return; - typename Ranges::iterator i,j; - i = std::lower_bound(ranges.begin(), ranges.end(), r); - if (i == ranges.end() || i->begin() >= r.end()) - return; // Outside of set - if (*i == r) // Erase i - ranges.erase(i); - else if (i->strictContains(r)) { // Split i - Range i1(i->begin(), r.begin()); - Range i2(r.end(), i->end()); - *i = i2; - ranges.insert(i, i1); - } else { - if (i->begin() < r.begin()) { // Truncate i - i->end(r.begin()); - ++i; - } - for (j = i; j != ranges.end() && r.contains(*j); ++j) - ; // Ranges to erase. - if (j != ranges.end() && j->end() > r.end()) - j->begin(r.end()); // Truncate j - ranges.erase(i,j); - } -} - -template void RangeSet::removeSet(const RangeSet& r) { - std::for_each( - r.ranges.begin(), r.ranges.end(), - boost::bind(&RangeSet::removeRange, this, _1)); -} - -template Range RangeSet::toRange() const { - assert(contiguous()); - return empty() ? Range() : ranges.front(); -} - -template void RangeSet::iterator::increment() { - assert(ranges && iter != ranges->end()); - if (!iter->contains(++value)) { - ++iter; - if (iter == ranges->end()) - *this=iterator(); // end() iterator - else - value=iter->begin(); - } -} - -template bool RangeSet::operator==(const RangeSet& r) const { - return ranges.size() == r.ranges.size() && std::equal(ranges.begin(), ranges.end(), r.ranges.begin()); -} - -template typename RangeSet::iterator RangeSet::begin() const { - return empty() ? end() : iterator(ranges, ranges.begin(), front()); -} - -template typename RangeSet::iterator RangeSet::end() const { - return iterator(); -} - -template bool RangeSet::iterator::equal(const iterator& i) const { - return ranges==i.ranges && (ranges==0 || value==i.value); -} - -template Range RangeSet::rangeContaining(const T& t) const { - typename Ranges::const_iterator i = - std::lower_bound(ranges.begin(), ranges.end(), Range(t)); - return (i != ranges.end() && i->contains(t)) ? *i : Range(t,t); -} - -template uint32_t RangeSet::span() const { - if (ranges.empty()) return 0; - return ranges.back().last() - ranges.front().first(); -} - -template size_t RangeSet::size() const { - return std::accumulate(rangesBegin(), rangesEnd(), 0, &RangeSet::accumulateSize); -} - -} // namespace qpid - - -#endif /*!QPID_RANGESET_H*/ -- cgit v1.2.1