added 1D-intervals intersecting and merging functions, and added tests for them.

2 files changed, 141 insertions, 0 deletions

diff --git a/base/base_tests/math_test.cpp b/base/base_tests/math_test.cpp
index 78be4eccc3..2668fd7aab 100644
--- a/base/base_tests/math_test.cpp
+++ b/base/base_tests/math_test.cpp
@@ -138,3 +138,71 @@ UNIT_TEST(IsIntersect_Intervals)
   TEST(my::IsIntersect(0, 100, -50, 0), ());
   TEST(!my::IsIntersect(0, 100, -50, -20), ());
 }
+
+UNIT_TEST(MergeInterval_Simple)
+{
+  int x0, x1;
+
+  my::Merge(100, 800, 400, 600, x0, x1);
+  TEST((x0 == 100) && (x1 == 800), ());
+
+  my::Merge(100, 800, 50, 600, x0, x1);
+  TEST((x0 == 50) && (x1 == 800), ());
+}
+
+UNIT_TEST(MergeSorted_Simple)
+{
+  double const a [] = {
+    10, 20,
+    30, 40,
+    50, 60
+  };
+
+  double const b [] = {
+    15, 35,
+    70, 80
+  };
+
+  double c[ARRAY_SIZE(a) + ARRAY_SIZE(b)];
+
+  int k;
+
+  double res0[ARRAY_SIZE(a) + ARRAY_SIZE(b)] = {10, 40, 50, 60, 70, 80, 0, 0, 0, 0};
+  k = my::MergeSorted(a, ARRAY_SIZE(a), b, ARRAY_SIZE(b), c, ARRAY_SIZE(c));
+  TEST(std::equal(c, c + k, res0), ());
+
+  double res1[ARRAY_SIZE(a) + ARRAY_SIZE(b)] = {10, 40, 50, 60, 0, 0, 0, 0, 0, 0};
+  k = my::MergeSorted(a, ARRAY_SIZE(a), b, ARRAY_SIZE(b) - 2, c, ARRAY_SIZE(c));
+  TEST(std::equal(c, c + k, res1), ());
+
+  double res2[ARRAY_SIZE(a) + ARRAY_SIZE(b)] = {10, 40, 70, 80, 0, 0, 0, 0, 0, 0};
+  k = my::MergeSorted(a, ARRAY_SIZE(a) - 2, b, ARRAY_SIZE(b), c, ARRAY_SIZE(c));
+  TEST(std::equal(c, c + k, res2), ());
+
+  double res3[ARRAY_SIZE(a) + ARRAY_SIZE(b)] = {10, 40, 0, 0, 0, 0, 0, 0, 0, 0};
+  k = my::MergeSorted(a, ARRAY_SIZE(a) - 2, b, ARRAY_SIZE(b) - 2, c, ARRAY_SIZE(c));
+  TEST(std::equal(c, c + k, res3), ());
+}
+
+UNIT_TEST(MergeSorted_NullArray)
+{
+  double const a [] = {
+    10, 20
+  };
+
+  double const b [] = {
+    0, 0
+  };
+
+  double c [2];
+
+  int k;
+
+  double etalon [2] = {10, 20};
+
+  k = my::MergeSorted(a, ARRAY_SIZE(a), b, 0, c, ARRAY_SIZE(c));
+  TEST(std::equal(c, c + k, etalon), ());
+
+  k = my::MergeSorted(b, 0, a, ARRAY_SIZE(a), c, ARRAY_SIZE(c));
+  TEST(std::equal(c, c + k, etalon), ());
+}
diff --git a/base/math.hpp b/base/math.hpp
index 0fd40a2c25..8700fb1c89 100644
--- a/base/math.hpp
+++ b/base/math.hpp
@@ -107,6 +107,79 @@ bool IsIntersect(T const & x0, T const & x1, T const & x2, T const & x3)
   return !((x1 < x2) || (x3 < x0));
 }
 
+template <typename T>
+void Merge(T const & x0, T const & x1, T const & x2, T const & x3, T & x4, T & x5)
+{
+  ASSERT(IsIntersect(x0, x1, x2, x3), ());
+  x4 = min(x0, x2);
+  x5 = max(x3, x1);
+}
+
+template <typename T>
+size_t MergeSorted(T const * a, size_t as, T const * b, size_t bs, T * c, size_t cs)
+{
+  T const * arrs [] = {a, b};
+  size_t sizes[] = {as, bs};
+  size_t idx[] = {0, 0};
+
+  int i = 0;
+  int j = 1;
+  int k = 0;
+
+  if ((sizes[i] == 0) && (sizes[j] == 0))
+    return 0;
+
+  if ((sizes[i] == 0) && (sizes[j] != 0))
+    swap(i, j);
+
+  while (true)
+  {
+    /// selecting start of new interval
+    if ((idx[j] != sizes[j]) && (arrs[i][idx[i]] > arrs[j][idx[j]]))
+      swap(i, j);
+
+    c[k]     = arrs[i][idx[i]];
+    c[k + 1] = arrs[i][idx[i] + 1];
+
+    idx[i] += 2;
+
+    while (true)
+    {
+      if (idx[j] == sizes[j])
+        break;
+
+      bool merged = false;
+
+      while (IsIntersect(c[k], c[k + 1], arrs[j][idx[j]], arrs[j][idx[j] + 1]))
+      {
+        merged = true;
+        Merge(c[k], c[k + 1], arrs[j][idx[j]], arrs[j][idx[j] + 1], c[k], c[k + 1]);
+        idx[j] += 2;
+        if (idx[j] == sizes[j])
+          break;
+      }
+
+      if (!merged)
+        break;
+
+      swap(i, j);
+    }
+
+    /// here idx[i] and idx[j] should point to intervals that
+    /// aren't overlapping c[k], c[k + 1]
+
+    k += 2;
+
+    if ((idx[i] == sizes[i]) && (idx[j] == sizes[j]))
+      break;
+
+    if (idx[i] == sizes[i])
+      swap(i, j);
+  }
+
+  return k;
+}
+
 // Computes x^n.
 template <typename T> inline T PowUint(T x, uint64_t n)
 {