host: Create meta_range_t::as_monotonic

In order to perform certain operations (start/stop/step), meta_range_t
objects must be "monotonic", meaning that the subranges composing it
are sorted and non-overlapping. This commit creates a method which
takes a non-monotonic meta_range_t containing no non-continuous
subranges and converts it into a monotonic meta_range_t.

3 files changed, 62 insertions, 1 deletions

diff --git a/host/include/uhd/types/ranges.hpp b/host/include/uhd/types/ranges.hpp
index 05aa0fa7c..72eaa0221 100644
--- a/host/include/uhd/types/ranges.hpp
+++ b/host/include/uhd/types/ranges.hpp
@@ -62,7 +62,7 @@ private:
 /*!
  * A meta-range object holds a list of individual ranges.
  */
-struct UHD_API meta_range_t : std::vector<range_t>
+struct UHD_API meta_range_t : public std::vector<range_t>
 {
     //! A default constructor for an empty meta-range
     meta_range_t(void);
@@ -113,6 +113,18 @@ struct UHD_API meta_range_t : std::vector<range_t>
      */
     double clip(double value, bool clip_step = false) const;
 
+    /*!
+     * A method for converting an arbitrary meta_range_t into a monotonic
+     * meta_range_t which has no overlapping ranges, and where all ranges
+     * are sorted.
+     *
+     * Requires that all subranges have a step size of zero, or else it
+     * throws uhd::value_error.
+     *
+     * \return a monotonic meta_range_t
+     */
+    meta_range_t as_monotonic() const;
+
     //! Convert this meta-range to a printable string
     const std::string to_pp_string(void) const;
 };
diff --git a/host/lib/types/ranges.cpp b/host/lib/types/ranges.cpp
index 16edeccca..5a5beb2e6 100644
--- a/host/lib/types/ranges.cpp
+++ b/host/lib/types/ranges.cpp
@@ -92,6 +92,35 @@ meta_range_t::meta_range_t(double start, double stop, double step)
     /* NOP */
 }
 
+meta_range_t meta_range_t::as_monotonic() const
+{
+    meta_range_t result;
+    for (const auto& range : *this) {
+        if (range.step() != 0.0) {
+            throw uhd::value_error("Cannot monotonize meta_range which contains non-continuous subranges");
+        }
+        result.push_back(range);
+    }
+
+    std::sort(result.begin(), result.end(), [](const range_t& a, const range_t& b) {
+        return a.start() < b.start();
+    });
+
+    // Merge overlapping
+    size_t i = 1;
+    while (i < result.size()) {
+        if (result[i - 1].stop() > result[i].start()) {
+            const auto new_stop = std::max(result[i - 1].stop(), result[i].stop());
+            result[i - 1] = range_t(result[i - 1].start(), new_stop, 0.0);
+            result.erase(result.begin() + i);
+        } else {
+            i++;
+        }
+    }
+
+    return result;
+}
+
 double meta_range_t::start(void) const
 {
     check_meta_range_monotonic(*this);
diff --git a/host/tests/ranges_test.cpp b/host/tests/ranges_test.cpp
index 223560289..126b4c4e9 100644
--- a/host/tests/ranges_test.cpp
+++ b/host/tests/ranges_test.cpp
@@ -90,3 +90,23 @@ BOOST_AUTO_TEST_CASE(test_ranges_compare)
     BOOST_CHECK(range == n_range);
     BOOST_CHECK(range != d_range);
 }
+
+BOOST_AUTO_TEST_CASE(test_meta_range_monotonize)
+{
+    // This meta_range is both not sorted and contains overlapping (and
+    // fully contained) sub-ranges.
+    meta_range_t mr;
+    mr.push_back(range_t(3.0, 4.0));
+    mr.push_back(range_t(1.0, 2.0));
+    mr.push_back(range_t(2.1, 3.1));
+    mr.push_back(range_t(1.4, 1.6));
+
+    meta_range_t monotonic_mr = mr.as_monotonic();
+    BOOST_CHECK(monotonic_mr.start() == 1.0);
+    BOOST_CHECK(monotonic_mr.stop() == 4.0);
+
+    BOOST_CHECK_CLOSE(monotonic_mr.at(0).start(), 1.0, tolerance);
+    BOOST_CHECK_CLOSE(monotonic_mr.at(0).stop(), 2.0, tolerance);
+    BOOST_CHECK_CLOSE(monotonic_mr.at(1).start(), 2.1, tolerance);
+    BOOST_CHECK_CLOSE(monotonic_mr.at(1).stop(), 4.0, tolerance);
+}