Replace "MergeSorted" with better one "AccumulateIntervals".

4 files changed, 172 insertions, 4 deletions

diff --git a/base/base_tests/math_test.cpp b/base/base_tests/math_test.cpp
index 2668fd7aab..2f483a03d7 100644
--- a/base/base_tests/math_test.cpp
+++ b/base/base_tests/math_test.cpp
@@ -139,6 +139,7 @@ UNIT_TEST(IsIntersect_Intervals)
   TEST(!my::IsIntersect(0, 100, -50, -20), ());
 }
 
+/*
 UNIT_TEST(MergeInterval_Simple)
 {
   int x0, x1;
@@ -206,3 +207,4 @@ UNIT_TEST(MergeSorted_NullArray)
   k = my::MergeSorted(b, 0, a, ARRAY_SIZE(a), c, ARRAY_SIZE(c));
   TEST(std::equal(c, c + k, etalon), ());
 }
+*/
diff --git a/base/base_tests/stl_add_test.cpp b/base/base_tests/stl_add_test.cpp
index 212dd3c1f7..094ed9f5af 100644
--- a/base/base_tests/stl_add_test.cpp
+++ b/base/base_tests/stl_add_test.cpp
@@ -85,3 +85,110 @@ UNIT_TEST(STLAdd_RemoveIfKeepValid)
     TEST_EQUAL(v.size(), 4, ());
   }
 }
+
+namespace
+{
+  template <class T, size_t N1, size_t N2, size_t N3>
+  void CheckAccumulateIntervals(size_t & idTest,
+                                pair<T, T> (&arr1)[N1],
+                                pair<T, T> (&arr2)[N2],
+                                pair<T, T> (&arr3)[N3])
+  {
+    vector<pair<T, T> > res;
+    AccumulateIntervals1With2(arr1, arr1 + N1, arr2, arr2 + N2, back_inserter(res));
+
+    ++idTest;
+    TEST_EQUAL(N3, res.size(), ("Test", idTest, res));
+    TEST(equal(res.begin(), res.end(), arr3), ("Test", idTest, res));
+  }
+}
+
+UNIT_TEST(STLAdd_AccumulateIntervals)
+{
+  typedef pair<int, int> T;
+  size_t idTest = 0;
+
+  // bound cases
+  {
+    vector<T> res;
+    T arr[] = { T(10, 20) };
+
+    res.clear();
+    AccumulateIntervals1With2(arr, arr + 1, arr, arr, back_inserter(res));
+    TEST_EQUAL(res.size(), 1, ());
+
+    res.clear();
+    AccumulateIntervals1With2(arr, arr, arr, arr + 1, back_inserter(res));
+    TEST_EQUAL(res.size(), 0, ());
+  }
+
+  // check splice overlapped
+  {
+    T arr1[] = { T(10, 20), T(30, 40) };
+    T arr2[] = { T(19, 31) };
+    T res[] = { T(10, 40) };
+    CheckAccumulateIntervals(idTest, arr1, arr2, res);
+  }
+
+  // check skip not overlapped
+  {
+    T arr1[] = { T(10, 20), T(30, 40) };
+    T arr2[] = { T(0, 9), T(21, 29), T(41, 50) };
+    T res[2] = { T(10, 20), T(30, 40) };
+    CheckAccumulateIntervals(idTest, arr1, arr2, res);
+  }
+  {
+    T arr1[] = { T(10, 20), T(30, 40) };
+    T arr2[] = { T(1, 2), T(3, 4), T(5, 6),
+                 T(21, 22), T(23, 24), T(25, 26),
+                 T(41, 42), T(43, 44), T(45, 46)
+               };
+    T res[] = { T(10, 20), T(30, 40) };
+    CheckAccumulateIntervals(idTest, arr1, arr2, res);
+  }
+
+  // check equal bounds
+  {
+    T arr1[] = { T(20, 30) };
+    T arr2[] = { T(10, 20), T(30, 40) };
+    T res[] = { T(20, 30) };
+    CheckAccumulateIntervals(idTest, arr1, arr2, res);
+  }
+  {
+    T arr1[] = { T(10, 20), T(30, 40) };
+    T arr2[] = { T(20, 30) };
+    T res[] = { T(10, 20), T(30, 40) };
+    CheckAccumulateIntervals(idTest, arr1, arr2, res);
+  }
+
+  // check large overlap interval
+  {
+    T arr1[] = { T(10, 20), T(30, 40), T(50, 60) };
+    T arr2[] = { T(0, 100) };
+    T res[] = { T(0, 100) };
+    CheckAccumulateIntervals(idTest, arr1, arr2, res);
+  }
+  {
+    T arr1[] = { T(0, 100) };
+    T arr2[] = { T(10, 20), T(30, 40), T(50, 60) };
+    T res[] = { T(0, 100) };
+    CheckAccumulateIntervals(idTest, arr1, arr2, res);
+  }
+
+  // check splice overlapped
+  {
+    T arr1[] = { T(10, 20), T(30, 40) };
+    T arr2[] = { T(5, 15), T(35, 45) };
+    T res[] = { T(5, 20), T(30, 45) };
+    CheckAccumulateIntervals(idTest, arr1, arr2, res);
+  }
+  {
+    T arr1[] = { T(10, 20), T(30, 40) };
+    T arr2[] = { T(1, 2), T(3, 4), T(5, 15),
+                 T(17, 25), T(26, 27), T(28, 32),
+                 T(38, 45), T(46, 50)
+               };
+    T res[] = { T(5, 25), T(28, 45) };
+    CheckAccumulateIntervals(idTest, arr1, arr2, res);
+  }
+}
diff --git a/base/math.hpp b/base/math.hpp
index 8700fb1c89..06468c0d63 100644
--- a/base/math.hpp
+++ b/base/math.hpp
@@ -107,6 +107,7 @@ 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)
 {
@@ -179,6 +180,7 @@ size_t MergeSorted(T const * a, size_t as, T const * b, size_t bs, T * c, size_t
 
   return k;
 }
+*/
 
 // Computes x^n.
 template <typename T> inline T PowUint(T x, uint64_t n)
diff --git a/base/stl_add.hpp b/base/stl_add.hpp
index c118e6773f..b695a75703 100644
--- a/base/stl_add.hpp
+++ b/base/stl_add.hpp
@@ -3,6 +3,7 @@
 #include "../std/iterator.hpp"
 #include "../std/map.hpp"
 
+
 template <class ContainerT> class BackInsertFunctor
 {
   ContainerT & m_Container;
@@ -168,9 +169,65 @@ template <typename IterT> IterT PrevIterInCycle(IterT it, IterT beg, IterT end)
   return --it;
 }
 
-template <typename KeyT, typename ValueT, typename CompareT, typename AllocatorT>
-ValueT ValueForKey(map<KeyT, ValueT, CompareT, AllocatorT> const & m, KeyT key, ValueT defaultV)
+template <class IterT1, class IterT2, class InsertIterT>
+void AccumulateIntervals1With2(IterT1 b1, IterT1 e1, IterT2 b2, IterT2 e2, InsertIterT res)
 {
-  typename map<KeyT, ValueT, CompareT, AllocatorT>::const_iterator const it = m.find(key);
-  return (it == m.end() ? defaultV : it->second);
+  //typedef typename iterator_traits<InsertIterT>::value_type T;
+  typedef typename iterator_traits<IterT1>::value_type T;
+
+  T prev;
+  bool validPrev = false;
+
+  while (b1 != e1 || b2 != e2)
+  {
+    // Try to continue previous range.
+    if (validPrev)
+    {
+      // add b1 range to prev if needed
+      if (b1 != e1 && b1->first < prev.second)
+      {
+        // correct only second if needed
+        if (prev.second < b1->second)
+          prev.second = b1->second;
+        ++b1;
+        continue;
+      }
+
+      // add b2 range to prev if needed
+      if (b2 != e2 && b2->first < prev.second)
+      {
+        // check that intervals are overlapped
+        if (prev.first < b2->second)
+        {
+          // correct first and second if needed
+          if (b2->first < prev.first)
+            prev.first = b2->first;
+          if (prev.second < b2->second)
+            prev.second = b2->second;
+        }
+
+        ++b2;
+        continue;
+      }
+
+      // if nothing to add - push to results
+      *res++ = prev;
+      validPrev = false;
+    }
+
+    if (b1 != e1)
+    {
+      // start new range
+      prev = *b1++;
+      validPrev = true;
+    }
+    else
+    {
+      // go to exit
+      break;
+    }
+  }
+
+  if (validPrev)
+    *res++ = prev;
 }