summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--CMakeLists.txt62
-rw-r--r--src/model/RangeSet.hpp324
-rw-r--r--test/model/RangeSet.cpp220
3 files changed, 594 insertions, 12 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt
index e6a6ae4..8c9956a 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -1,28 +1,61 @@
+# 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/>.
+
+################################################################################
+# Basic Project Definitions and Dependencies #
+################################################################################
+
PROJECT(basicwriter)
CMAKE_MINIMUM_REQUIRED(VERSION 2.8.9)
SET(CMAKE_AUTOMOC ON)
FIND_PACKAGE(Qt5Widgets REQUIRED)
-# Enable C++11 and all warnings
-SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wall -pedantic -std=c++11")
-
# Option for enabling testing. Turn on with 'cmake -Dtest=ON'.
OPTION(test "Build all tests." OFF) # Makes boolean 'test' available.
+# Enable C++11 and all warnings
+SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -g -O0 -Wall -pedantic -std=c++11")
+
+################################################################################
+# Inclusion of gtest #
+################################################################################
+
# Unit test handling
-if(test)
+IF(test)
# Compile gtest
- add_subdirectory(lib/gtest-1.7.0)
+ ADD_SUBDIRECTORY(lib/gtest-1.7.0)
# Enable testing and declare some variables used for compiling the test cases
- enable_testing()
- set(GTEST_INCLUDE_DIR ${gtest_SOURCE_DIR}/include ${gtest_SOURCE_DIR})
- set(GTEST_LIBRARIES gtest gtest_main)
-endif()
+ ENABLE_TESTING()
+ SET(GTEST_INCLUDE_DIR ${gtest_SOURCE_DIR}/include ${gtest_SOURCE_DIR})
+ SET(GTEST_LIBRARIES gtest gtest_main)
+ENDIF()
-INCLUDE_DIRECTORIES(src/)
+################################################################################
+# Commands for building Ousía #
+################################################################################
+
+# Includ directories
+INCLUDE_DIRECTORIES(
+ src/
+)
+# ousia_core library (containing the code of the most important data structures
+# and deduction algorithms)
ADD_LIBRARY(ousia_core
src/model/GraphNode
src/model/domain/Structure
@@ -34,17 +67,21 @@ ADD_LIBRARY(ousia_core
src/model/types/Value
)
+# Definition of the main program
ADD_EXECUTABLE(ousia
src/main
)
+# Link the ousia executable against ousia_core
TARGET_LINK_LIBRARIES(ousia
ousia_core
)
+# Link the ousia executable against the Widgets module of Qt5
QT5_USE_MODULES(ousia Widgets)
-if(test)
+# If testing is enabled, build the unit tests
+IF(test)
# Include the gtest include files and the src directory
INCLUDE_DIRECTORIES(
${GTEST_INCLUDE_DIR}
@@ -53,6 +90,7 @@ if(test)
# Add all unit test files
ADD_EXECUTABLE(ousia_test
+ test/model/RangeSet
test/model/GraphNode
test/model/domain/Layer
)
@@ -64,5 +102,5 @@ if(test)
# Register the unit test
ADD_TEST(ousia_test ousia_test)
-endif()
+ENDIF()
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_ */
+
diff --git a/test/model/RangeSet.cpp b/test/model/RangeSet.cpp
new file mode 100644
index 0000000..f3aa209
--- /dev/null
+++ b/test/model/RangeSet.cpp
@@ -0,0 +1,220 @@
+/*
+ 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/>.
+*/
+
+#include <gtest/gtest.h>
+
+#include <model/RangeSet.hpp>
+
+namespace ousia {
+
+TEST(Range, IsValid)
+{
+ ASSERT_FALSE(Range<int>().isValid());
+ ASSERT_TRUE(Range<int>(10).isValid());
+ ASSERT_TRUE(Range<int>(10, 20).isValid());
+ ASSERT_FALSE(Range<int>(20, 10).isValid());
+}
+
+TEST(Range, InRange)
+{
+ Range<int> r(10, 20);
+ ASSERT_FALSE(r.inRange(0));
+ ASSERT_FALSE(r.inRange(21));
+ ASSERT_TRUE(r.inRange(10));
+ ASSERT_TRUE(r.inRange(20));
+ ASSERT_TRUE(r.inRange(15));
+}
+
+TEST(Range, Overlapps)
+{
+ ASSERT_FALSE(Range<int>(10, 20).overlapps(Range<int>(0, 9)));
+ ASSERT_FALSE(Range<int>(10, 20).overlapps(Range<int>(21, 30)));
+ ASSERT_TRUE(Range<int>(10, 20).overlapps(Range<int>(0, 10)));
+ ASSERT_TRUE(Range<int>(10, 20).overlapps(Range<int>(20, 30)));
+ ASSERT_TRUE(Range<int>(10, 20).overlapps(Range<int>(5, 15)));
+ ASSERT_TRUE(Range<int>(10, 20).overlapps(Range<int>(15, 25)));
+ ASSERT_TRUE(Range<int>(10, 20).overlapps(Range<int>(15, 19)));
+ ASSERT_TRUE(Range<int>(10, 20).overlapps(Range<int>(15, 15)));
+ ASSERT_TRUE(Range<int>(10, 20).overlapps(Range<int>(10, 20)));
+ ASSERT_TRUE(Range<int>(10, 20).overlapps(Range<int>(0, 30)));
+}
+
+TEST(Range, CoveredBy)
+{
+ ASSERT_FALSE(Range<int>(10, 20).coveredBy(Range<int>(0, 9)));
+ ASSERT_FALSE(Range<int>(10, 20).coveredBy(Range<int>(21, 30)));
+ ASSERT_FALSE(Range<int>(10, 20).coveredBy(Range<int>(0, 10)));
+ ASSERT_FALSE(Range<int>(10, 20).coveredBy(Range<int>(20, 30)));
+ ASSERT_FALSE(Range<int>(10, 20).coveredBy(Range<int>(5, 15)));
+ ASSERT_FALSE(Range<int>(10, 20).coveredBy(Range<int>(15, 25)));
+ ASSERT_FALSE(Range<int>(10, 20).coveredBy(Range<int>(15, 19)));
+ ASSERT_FALSE(Range<int>(10, 20).coveredBy(Range<int>(15, 15)));
+ ASSERT_TRUE(Range<int>(10, 20).coveredBy(Range<int>(10, 20)));
+ ASSERT_TRUE(Range<int>(10, 20).coveredBy(Range<int>(0, 30)));
+}
+
+TEST(Range, Covers)
+{
+ ASSERT_FALSE(Range<int>(10, 20).covers(Range<int>(0, 9)));
+ ASSERT_FALSE(Range<int>(10, 20).covers(Range<int>(21, 30)));
+ ASSERT_FALSE(Range<int>(10, 20).covers(Range<int>(0, 10)));
+ ASSERT_FALSE(Range<int>(10, 20).covers(Range<int>(20, 30)));
+ ASSERT_FALSE(Range<int>(10, 20).covers(Range<int>(5, 15)));
+ ASSERT_FALSE(Range<int>(10, 20).covers(Range<int>(15, 25)));
+ ASSERT_TRUE(Range<int>(10, 20).covers(Range<int>(15, 19)));
+ ASSERT_TRUE(Range<int>(10, 20).covers(Range<int>(15, 15)));
+ ASSERT_TRUE(Range<int>(10, 20).covers(Range<int>(10, 20)));
+ ASSERT_FALSE(Range<int>(10, 20).covers(Range<int>(0, 30)));
+}
+
+TEST(RangeSet, Neighbours)
+{
+ ASSERT_TRUE(Range<int>(10, 19).neighbours(Range<int>(20, 30)));
+ ASSERT_TRUE(Range<int>(20, 29).neighbours(Range<int>(10, 19)));
+}
+
+TEST(Range, Merge)
+{
+ Range<int> r1(10, 20);
+ Range<int> r2(15, 25);
+ Range<int> r3(5, 15);
+ Range<int> rM = r1.merge(r2).merge(r3);
+ ASSERT_EQ(rM.start, 5);
+ ASSERT_EQ(rM.end, 25);
+}
+
+TEST(RangeSet, Merge)
+{
+ RangeSet<int> s;
+ auto &ranges = s.getRanges();
+
+ // Insert some non-overlapping elements into the range. We expect these to
+ // be just inserted into the ranges.
+ s.merge(Range<int>( 0, 10));
+ s.merge(Range<int>(20, 30));
+ s.merge(Range<int>(40, 50));
+ s.merge(Range<int>(60, 70));
+ {
+ ASSERT_EQ(ranges.size(), 4);
+
+ auto it = ranges.begin();
+ ASSERT_EQ((*it).start, 0);
+ ASSERT_EQ((*it).end, 10);
+
+ it++;
+ ASSERT_EQ((*it).start, 20);
+ ASSERT_EQ((*it).end, 30);
+
+ it++;
+ ASSERT_EQ((*it).start, 40);
+ ASSERT_EQ((*it).end, 50);
+
+ it++;
+ ASSERT_EQ((*it).start, 60);
+ ASSERT_EQ((*it).end, 70);
+ }
+
+ // Now insert an element which spans the second and third element
+ s.merge(Range<int>(15, 55));
+ {
+ ASSERT_EQ(ranges.size(), 3);
+
+ auto it = ranges.begin();
+ ASSERT_EQ((*it).start, 0);
+ ASSERT_EQ((*it).end, 10);
+
+ it++;
+ ASSERT_EQ((*it).start, 15);
+ ASSERT_EQ((*it).end, 55);
+
+ it++;
+ ASSERT_EQ((*it).start, 60);
+ ASSERT_EQ((*it).end, 70);
+ }
+
+ // Now insert an element which expands the first element
+ s.merge(Range<int>(-10, 11));
+ {
+ ASSERT_EQ(ranges.size(), 3);
+
+ auto it = ranges.begin();
+ ASSERT_EQ((*it).start, -10);
+ ASSERT_EQ((*it).end, 11);
+
+ it++;
+ ASSERT_EQ((*it).start, 15);
+ ASSERT_EQ((*it).end, 55);
+
+ it++;
+ ASSERT_EQ((*it).start, 60);
+ ASSERT_EQ((*it).end, 70);
+ }
+
+ // Now insert an element which merges the last two elements
+ s.merge(Range<int>(13, 70));
+ {
+ ASSERT_EQ(ranges.size(), 2);
+
+ auto it = ranges.begin();
+ ASSERT_EQ((*it).start, -10);
+ ASSERT_EQ((*it).end, 11);
+
+ it++;
+ ASSERT_EQ((*it).start, 13);
+ ASSERT_EQ((*it).end, 70);
+ }
+
+ // Now insert an element which merges the remaining elements
+ s.merge(Range<int>(-9, 12));
+ {
+ ASSERT_EQ(ranges.size(), 1);
+
+ auto it = ranges.begin();
+ ASSERT_EQ((*it).start, -10);
+ ASSERT_EQ((*it).end, 70);
+ }
+
+}
+
+TEST(RangeSet, Contains)
+{
+ RangeSet<int> s;
+
+ // Insert some non-overlapping elements into the range. We expect these to
+ // be just inserted into the ranges.
+ s.merge(Range<int>( 0, 10));
+ s.merge(Range<int>(20, 30));
+ s.merge(Range<int>(40, 50));
+ s.merge(Range<int>(60, 70));
+ s.merge(Range<int>(71));
+ s.merge(Range<int>(72));
+ s.merge(Range<int>(73));
+ s.merge(Range<int>(74));
+
+ ASSERT_TRUE(s.contains(60));
+ ASSERT_TRUE(s.contains(0));
+ ASSERT_TRUE(s.contains(25));
+ ASSERT_TRUE(s.contains(73));
+ ASSERT_TRUE(s.contains(Range<int>(25, 30)));
+ ASSERT_FALSE(s.contains(Range<int>(25, 35)));
+ ASSERT_TRUE(s.contains(Range<int>(0, 10)));
+ ASSERT_TRUE(s.contains(Range<int>(70, 74)));
+}
+
+}
+
generated by cgit v1.2.3 (git 2.39.1) at 2025-05-01 07:24:20 +0000