diff options
Diffstat (limited to 'libs')
-rw-r--r-- | libs/evoral/evoral/Range.hpp | 69 | ||||
-rw-r--r-- | libs/evoral/test/RangeTest.cpp | 63 | ||||
-rw-r--r-- | libs/evoral/test/RangeTest.hpp | 5 |
3 files changed, 120 insertions, 17 deletions
diff --git a/libs/evoral/evoral/Range.hpp b/libs/evoral/evoral/Range.hpp index bc353a47d7..02d92100b9 100644 --- a/libs/evoral/evoral/Range.hpp +++ b/libs/evoral/evoral/Range.hpp @@ -139,7 +139,6 @@ public: return _list.empty (); } -private: void coalesce () { if (!_dirty) { return; @@ -164,6 +163,8 @@ private: _dirty = false; } + +private: List _list; bool _dirty; @@ -178,37 +179,71 @@ struct RangeMove { T to; ///< new start of the range }; +/** Subtract the ranges in `sub' from that in `range', + * returning the result. + */ template<typename T> RangeList<T> subtract (Range<T> range, RangeList<T> sub) { + /* Start with the input range */ RangeList<T> result; + result.add (range); if (sub.empty ()) { - result.add (range); return result; } - - T x = range.from; typename RangeList<T>::List s = sub.get (); + + /* The basic idea here is to keep a list of the result ranges, and subtract + the bits of `sub' from them one by one. + */ for (typename RangeList<T>::List::const_iterator i = s.begin(); i != s.end(); ++i) { - if (coverage (range.from, range.to, i->from, i->to) == OverlapNone) { - continue; - } - - Range<T> clamped (std::max (range.from, i->from), std::min (range.to, i->to)); - - if (clamped.from != x) { - result.add (Range<T> (x, clamped.from - 1)); + /* Here's where we'll put the new current result after subtracting *i from it */ + RangeList<T> new_result; + + typename RangeList<T>::List r = result.get (); + + /* Work on all parts of the current result using this range *i */ + for (typename RangeList<T>::List::const_iterator j = r.begin(); j != r.end(); ++j) { + + switch (coverage (j->from, j->to, i->from, i->to)) { + case OverlapNone: + /* The thing we're subtracting does not overlap this bit of the result, + so pass it through. + */ + new_result.add (*j); + break; + case OverlapInternal: + /* Internal overlap of the thing we're subtracting from this bit of the result, + so we might end up with two bits left over. + */ + if (j->from < (i->from - 1)) { + new_result.add (Range<T> (j->from, i->from - 1)); + } + if (j->to != i->to) { + new_result.add (Range<T> (i->to, j->to)); + } + break; + case OverlapStart: + /* The bit we're subtracting overlaps the start of the bit of the result */ + new_result.add (Range<T> (i->to, j->to - 1)); + break; + case OverlapEnd: + /* The bit we're subtracting overlaps the end of the bit of the result */ + new_result.add (Range<T> (j->from, i->from - 1)); + break; + case OverlapExternal: + /* total overlap of the bit we're subtracting with the result bit, so the + result bit is completely removed; do nothing */ + break; + } } - - x = clamped.to; - } - if (s.back().to < range.to) { - result.add (Range<T> (x, range.to)); + new_result.coalesce (); + result = new_result; } return result; diff --git a/libs/evoral/test/RangeTest.cpp b/libs/evoral/test/RangeTest.cpp index ff9856a9b6..07decbf2c9 100644 --- a/libs/evoral/test/RangeTest.cpp +++ b/libs/evoral/test/RangeTest.cpp @@ -1,5 +1,6 @@ #include "RangeTest.hpp" #include "evoral/Range.hpp" +#include <stdlib.h> CPPUNIT_TEST_SUITE_REGISTRATION (RangeTest); @@ -24,6 +25,7 @@ RangeTest::coalesceTest () CPPUNIT_ASSERT_EQUAL (8, i->to); } +/* Basic subtraction of a few smaller ranges from a larger one */ void RangeTest::subtractTest1 () { @@ -51,6 +53,7 @@ RangeTest::subtractTest1 () CPPUNIT_ASSERT_EQUAL (10, i->to); } +/* Test subtraction of a range B from a range A, where A and B do not overlap */ void RangeTest::subtractTest2 () { @@ -69,6 +72,7 @@ RangeTest::subtractTest2 () CPPUNIT_ASSERT_EQUAL (10, i->to); } +/* Test subtraction of B from A, where B entirely overlaps A */ void RangeTest::subtractTest3 () { @@ -82,3 +86,62 @@ RangeTest::subtractTest3 () RangeList<int>::List s = sheila.get (); CPPUNIT_ASSERT_EQUAL (size_t (0), s.size ()); } + +/* A bit like subtractTest1, except some of the ranges + we are subtracting overlap. +*/ +void +RangeTest::subtractTest4 () +{ + Range<int> fred (0, 10); + + RangeList<int> jim; + jim.add (Range<int> (2, 4)); + jim.add (Range<int> (7, 8)); + jim.add (Range<int> (8, 9)); + + RangeList<int> sheila = subtract (fred, jim); + + RangeList<int>::List s = sheila.get (); + CPPUNIT_ASSERT_EQUAL (size_t (3), s.size ()); + + RangeList<int>::List::iterator i = s.begin (); + CPPUNIT_ASSERT_EQUAL (0, i->from); + CPPUNIT_ASSERT_EQUAL (1, i->to); + + ++i; + CPPUNIT_ASSERT_EQUAL (4, i->from); + CPPUNIT_ASSERT_EQUAL (6, i->to); + + ++i; + CPPUNIT_ASSERT_EQUAL (9, i->from); + CPPUNIT_ASSERT_EQUAL (10, i->to); +} + +/* A bit like subtractTest1, except some of the ranges + we are subtracting overlap the start / end of the + initial range. +*/ +void +RangeTest::subtractTest5 () +{ + Range<int> fred (1, 12); + + RangeList<int> jim; + jim.add (Range<int> (0, 4)); + jim.add (Range<int> (6, 7)); + jim.add (Range<int> (9, 42)); + + RangeList<int> sheila = subtract (fred, jim); + + RangeList<int>::List s = sheila.get (); + CPPUNIT_ASSERT_EQUAL (size_t (2), s.size ()); + + RangeList<int>::List::iterator i = s.begin (); + CPPUNIT_ASSERT_EQUAL (4, i->from); + CPPUNIT_ASSERT_EQUAL (5, i->to); + + ++i; + CPPUNIT_ASSERT_EQUAL (7, i->from); + CPPUNIT_ASSERT_EQUAL (8, i->to); +} diff --git a/libs/evoral/test/RangeTest.hpp b/libs/evoral/test/RangeTest.hpp index 6b65ad02d2..892347b3b0 100644 --- a/libs/evoral/test/RangeTest.hpp +++ b/libs/evoral/test/RangeTest.hpp @@ -6,7 +6,10 @@ class RangeTest : public CppUnit::TestFixture CPPUNIT_TEST_SUITE (RangeTest); CPPUNIT_TEST (coalesceTest); CPPUNIT_TEST (subtractTest1); + CPPUNIT_TEST (subtractTest2); CPPUNIT_TEST (subtractTest3); + CPPUNIT_TEST (subtractTest4); + CPPUNIT_TEST (subtractTest5); CPPUNIT_TEST_SUITE_END (); public: @@ -14,6 +17,8 @@ public: void subtractTest1 (); void subtractTest2 (); void subtractTest3 (); + void subtractTest4 (); + void subtractTest5 (); }; |