According to my lords holy command I enacted his graces order of moving all peasants and lordlings, big and small, young and old, to our common land and inner sanctuary to be safe from outer threats by those usurpers.

1 files changed, 326 insertions, 0 deletions

diff --git a/src/core/RangeSet.hpp b/src/core/RangeSet.hpp
new file mode 100644
index 0000000..841d476
--- /dev/null
+++ b/src/core/RangeSet.hpp
@@ -0,0 +1,326 @@
+/*
+    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 _OUSIA_MODEL_RANGE_SET_HPP_
+#define _OUSIA_MODEL_RANGE_SET_HPP_
+
+#include <limits>
+#include <set>
+
+namespace ousia {
+namespace model {
+/**
+ * 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 overlaps 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 overlaps(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> typeRange()
+	{
+		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> typeRangeUntil(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> typeRangeFrom(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 overlaps
+	 * 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->overlaps(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->overlaps(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 /* _OUSIA_MODEL_RANGE_SET_HPP_ */
+