diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/model/RangeSet.hpp | 324 |
1 files changed, 324 insertions, 0 deletions
diff --git a/src/model/RangeSet.hpp b/src/model/RangeSet.hpp new file mode 100644 index 0000000..3768431 --- /dev/null +++ b/src/model/RangeSet.hpp @@ -0,0 +1,324 @@ +/* + Ousía + Copyright (C) 2014 Benjamin Paaßen, Andreas Stöckel + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. +*/ + +#ifndef _RANGE_SET_HPP_ +#define _RANGE_SET_HPP_ + +#include <limits> + +namespace ousia { + +/** + * The Range structure represents an interval of numerical values of type T. + */ +template <typename T> +struct Range { + /** + * Start is the start value of the range. + */ + T start; + + /** + * End is the end value of the range (inclusively). + */ + T end; + + /** + * Default constructor of the range class. The range is initialized as + * invalid, with start being set to the maximum possible value of the + * numerical type T, and end being set to the minimum possible value. + */ + Range() : + start(std::numeric_limits<T>::max()), + end(std::numeric_limits<T>::min()) + { + // Do nothing here + } + + /** + * Copies the given start and end value. The given values are not checked + * for validity. Use the "isValid" + * + * @param start is the minimum value the range still covers. + * @param end is the maximum value the range still covers. + */ + Range(const T &start, const T &end) : + start(start), end(end) + { + // Do nothing here + } + + /** + * Creates a range that covers exactly one element, namely the value given + * as parameter n. + */ + Range(const T &n) : + start(n), end(n) + { + // Do nothing here + } + + /** + * Returns true if this range is valid, e.g. its start value is smaller or + * equal to its end value. + * + * @return true if start is smaller or equal to end, false otherwise. + */ + bool isValid() const + { + return start <= end; + } + + /** + * Checks whether the given value lies inside the range. + * + * @param v is the value that is being checked. + * @return true if the value lies within the range, false otherwise. + */ + bool inRange(T v) const + { + return (v >= start) && (v <= end); + } + + /** + * Checks whether the given range overlapps with another range. Not that + * this check is only meaningful if both ranges are valid. + * + * @param r is the range that should be checked for overlapping with this + * range. + */ + bool overlapps(const Range<T> &r) const + { + return (((r.start >= start) || (r.end >= start)) + && ((r.start <= end) || (r.end <= end))); + } + + /** + * Returns true if the two given ranges are neighbours (their limits only + * differ in the smallest representable difference between them). + */ + bool neighbours(const Range<T> &r) const + { + constexpr T eps = std::numeric_limits<T>::is_integer + ? 1 : std::numeric_limits<T>::epsilon(); + return ((r.start > end) && ((r.start - eps) <= end)) + || ((r.end < start) && ((r.end + eps) >= start)); + } + + /** + * Checks whether the given range completely covers this range. + */ + bool coveredBy(const Range<T> &r) const + { + return (r.start <= start) && (r.end >= end); + } + + /** + * Checks whether this range completely covers the given range. + */ + bool covers(const Range<T> &r) const + { + return r.coveredBy(*this); + } + + /** + * Calculates the union of the two ranges -- not that this operation is only + * valid if the ranges overlapp. Use the RangeSet class if you cannot + * guarantee that. + */ + Range<T> merge(const Range<T> &r) const + { + return Range(std::min(start, r.start), std::max(end, r.end)); + } + + /** + * Returns a range that represents the spans the complete set defined by the + * given type T. + */ + static Range<T> hull() + { + return Range(std::numeric_limits<T>::min(), + std::numeric_limits<T>::max()); + } + + /** + * Returns a range that represents the spans the complete set defined by the + * given type T up to a given value. + * + * @param till is the value up to which the range should be defined (till is + * included in the set). + */ + static Range<T> hullUntil(const T &till) + { + return Range(std::numeric_limits<T>::min(), till); + } + + /** + * Returns a range that represents the spans the complete set defined by the + * given type T up to a given value. + * + * @param from is the value from which the range should be defined (from is + * included in the set). + */ + static Range<T> hullFrom(const T &from) + { + return Range(from, std::numeric_limits<T>::max()); + } +}; + +/** + * RangeComp is a comperator used to order to sort the ranges within the + * ranges list. Sorts by the start element. + */ +template<typename T> +struct RangeComp { + bool operator() (const Range<T>& lhs, const Range<T>& rhs) const + { + return lhs.start < rhs.start; + } +}; + +/** + * RangeSet represents a set of ranges of the given numerical type and is thus + * capable of representing any possible subset of the given numerical type T. + */ +template<typename T> +class RangeSet { + +protected: + /** + * Set of ranges used internally. + */ + std::set<Range<T>, RangeComp<T>> ranges; + + /** + * Returns an iterator to the first element in the ranges list that overlapps + * with the given range. + * + * @param r is the range for which the first overlapping element should be + * found. + * @return an iterator pointing to the first overlapping element or to the + * end of the list if no such element was found. + */ + typename std::set<Range<T>, RangeComp<T>>::iterator firstOverlapping( + const Range<T> &r, const bool allowNeighbours) + { + // Find the element with the next larger start value compared to the + // start value given in r. + auto it = ranges.upper_bound(r); + + // Go back one element + if (it != ranges.begin()) { + it--; + } + + // Iterate until an overlapping element is found + while (!(it->overlapps(r) || (allowNeighbours && it->neighbours(r))) + && (it != ranges.end())) { + it++; + } + return it; + } + +public: + /** + * Calculates the union of this range set and the given range. + * + * @param range is the range that should be merged into this range set. + */ + void merge(Range<T> r) + { + // Calculate a new range that covers both the new range and all old + // ranges in the set -- delete all old elements on the way + auto it = firstOverlapping(r, true); + while ((it->overlapps(r) || it->neighbours(r)) && it != ranges.end()) { + r = r.merge(*it); + it = ranges.erase(it); + } + + // Insert the new range + ranges.insert(r); + } + + /** + * Calculates the union of this range set and the given range set. + * + * @param ranges is another range set for which the union with this set + * should be calculated. + */ + void merge(const RangeSet<T> &s) + { + for (Range<T> &r : s.ranges) { + merge(r); + } + } + + /** + * Checks whether this range set S contains the given range R: + * S u R = R + * (The intersection between R and S equals the given range) + * + * @param r is the range for which the containment should be checked. + * @return true if the above condition is met, false otherwise. + */ + bool contains(const Range<T> &r) + { + auto it = firstOverlapping(r, false); + if (it != ranges.end()) { + return (*it).covers(r); + } + return false; + } + + /** + * Checks whether this range set S1 contains the given range set S2: + * + * @param s is the range for which the containment should be checked. + * @return true if the above condition is met, false otherwise. + */ + bool contains(const RangeSet<T> &s) + { + bool res = true; + for (Range<T> &r : s.ranges) { + res = res && contains(r); + } + return res; + } + + /** + * Empties the set. + */ + void clear() + { + ranges.clear(); + } + + /** + * Returns the current list of ranges as a const reference. + */ + const std::set<Range<T>, RangeComp<T>>& getRanges() + { + return this->ranges; + } + +}; + +} + +#endif /* _RANGE_SET_HPP_ */ + |