From 8953e5bc255b8f36095c6ba284f09fdc506390d5 Mon Sep 17 00:00:00 2001 From: rachytski Date: Fri, 1 Mar 2013 17:57:10 +0300 Subject: added 1D-intervals intersecting and merging functions, and added tests for them. --- base/base_tests/math_test.cpp | 68 ++++++++++++++++++++++++++++++++++++++++ base/math.hpp | 73 +++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 141 insertions(+) (limited to 'base') 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 +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 +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 inline T PowUint(T x, uint64_t n) { -- cgit v1.2.3