Rewrite feature covering. Use a simpler approach and remove stream optimizer.

6 files changed, 56 insertions, 612 deletions

diff --git a/geometry/covering.hpp b/geometry/covering.hpp
index c774191275..f7fd6869af 100644
--- a/geometry/covering.hpp
+++ b/geometry/covering.hpp
@@ -3,31 +3,26 @@
 #include "../base/assert.hpp"
 #include "../base/base.hpp"
 #include "../base/logging.hpp"
-#include "../base/set_operations.hpp"
-#include "../base/stl_add.hpp"
+#include "../base/math.hpp"
 #include "../std/algorithm.hpp"
-#include "../std/array.hpp"
-#include "../std/functional.hpp"
-#include "../std/iterator.hpp"
-#include "../std/map.hpp"
-#include "../std/queue.hpp"
 #include "../std/utility.hpp"
 #include "../std/vector.hpp"
 
 namespace covering
 {
 
-enum CellTriangleIntersection
+enum CellObjectIntersection
 {
-  CELL_TRIANGLE_NO_INTERSECTION = 0,
-  CELL_TRIANGLE_INTERSECT = 1,
-  CELL_INSIDE_TRIANGLE = 2,
-  TRIANGLE_INSIDE_CELL = 3
+  CELL_OBJECT_NO_INTERSECTION = 0,
+  CELL_OBJECT_INTERSECT = 1,
+  CELL_INSIDE_OBJECT = 2,
+  OBJECT_INSIDE_CELL = 3
 };
 
 template <class CellIdT>
-CellTriangleIntersection IntersectCellWithTriangle(
-    CellIdT const cell, m2::PointD const & a, m2::PointD const & b, m2::PointD const & c)
+inline CellObjectIntersection IntersectCellWithLine(CellIdT const cell,
+                                                    m2::PointD const & a,
+                                                    m2::PointD const & b)
 {
   pair<uint32_t, uint32_t> const xy = cell.XY();
   uint32_t const r = cell.Radius();
@@ -39,308 +34,66 @@ CellTriangleIntersection IntersectCellWithTriangle(
     m2::PointD(xy.first + r, xy.second - r)
   };
   for (int i = 0; i < 4; ++i)
-  {
-    m2::PointD const & p1 = cellCorners[i];
-    m2::PointD const & p2 = cellCorners[i == 0 ? 3 : i - 1];
-    if (m2::SegmentsIntersect(a, b, p1, p2)) return CELL_TRIANGLE_INTERSECT;
-    if (m2::SegmentsIntersect(b, c, p1, p2)) return CELL_TRIANGLE_INTERSECT;
-    if (m2::SegmentsIntersect(c, a, p1, p2)) return CELL_TRIANGLE_INTERSECT;
-  }
+    if (m2::SegmentsIntersect(a, b, cellCorners[i], cellCorners[i == 0 ? 3 : i - 1]))
+      return CELL_OBJECT_INTERSECT;
   if (xy.first - r <= a.x && a.x <= xy.first + r && xy.second - r <= a.y && a.y <= xy.second + r)
-    return TRIANGLE_INSIDE_CELL;
-  if (m2::IsPointStrictlyInsideTriangle(cellCorners[0], a, b, c))
-    return CELL_INSIDE_TRIANGLE;
-  return CELL_TRIANGLE_NO_INTERSECTION;
+    return OBJECT_INSIDE_CELL;
+  return CELL_OBJECT_NO_INTERSECTION;
 }
 
-template <class CellIdT, typename F>
-void CoverTriangle(m2::PointD const & a, m2::PointD const & b, m2::PointD const & c,
-                   F const & output, uint8_t const level = CellIdT::DEPTH_LEVELS - 1,
-                   CellIdT const startCell = CellIdT::Root())
+template <class CellIdT>
+CellObjectIntersection IntersectCellWithTriangle(
+    CellIdT const cell, m2::PointD const & a, m2::PointD const & b, m2::PointD const & c)
 {
-  ASSERT_LESS_OR_EQUAL(startCell.Level(), level, (a, b, c));
-  CellTriangleIntersection intersection = IntersectCellWithTriangle(startCell, a, b, c);
-
-  if (intersection == CELL_TRIANGLE_NO_INTERSECTION)
-    return;
-
-  if (startCell.Level() == level || intersection == CELL_INSIDE_TRIANGLE)
-  {
-    output(startCell);
-    return;
-  }
-
-  for (uint8_t child = 0; child < 4; ++child)
-    CoverTriangle(a, b, c, output, level, startCell.Child(child));
+  CellObjectIntersection const i1 = IntersectCellWithLine(cell, a, b);
+  if (i1 == CELL_OBJECT_INTERSECT)
+    return CELL_OBJECT_INTERSECT;
+  CellObjectIntersection const i2 = IntersectCellWithLine(cell, b, c);
+  if (i2 == CELL_OBJECT_INTERSECT)
+    return CELL_OBJECT_INTERSECT;
+  CellObjectIntersection const i3 = IntersectCellWithLine(cell, c, a);
+  if (i3 == CELL_OBJECT_INTERSECT)
+    return CELL_OBJECT_INTERSECT;
+  ASSERT_EQUAL(i1, i2, (cell, a, b, c));
+  ASSERT_EQUAL(i2, i3, (cell, a, b, c));
+  ASSERT_EQUAL(i3, i1, (cell, a, b, c));
+  return i1;
 }
 
-template <class CellIdT>
-class Covering
+template <class CellIdT, typename IntersectF>
+void CoverObject(IntersectF const & intersect, uint64_t cellPenaltyArea, vector<CellIdT> & out,
+                 CellIdT cell = CellIdT::Root())
 {
-public:
-  typedef CellIdT CellId;
-  typedef typename CellId::LessQueueOrder LessQueueOrder;
-
-  Covering() : m_Size(0) {}
-
-  explicit Covering(CellId cell) : m_Size(1)
-  {
-    m_Covering[cell.Level()].push_back(cell);
-  }
-
-  explicit Covering(vector<CellId> const & v, int64_t minId = 0)
-  {
-    for (size_t i = 0; i < v.size(); ++i)
-      m_Covering[v[i].Level()].push_back(v[i]);
-    Sort();
-    Unique();
-    RemoveDuplicateChildren();
-    RemoveFullSquares(minId);
-    m_Size = CalculateSize();
-  }
-
-  // Cover triangle.
-  Covering(m2::PointD const & a, m2::PointD const & b, m2::PointD const & c,
-           int level = CellId::DEPTH_LEVELS - 1)
-  {
-    // TODO: ASSERT(a != b), ASSERT(b != c), ASSERT(a != c) ?
-    ASSERT(0 <= level && level <= CellId::DEPTH_LEVELS, (level, CellId::Root()));
-    CoverTriangleInfo info;
-    info.m_pCovering = this;
-    info.m_A = a;
-    info.m_B = b;
-    info.m_C = c;
-    info.m_Level = level;
-    CoverTriangleImpl(info, CellId::Root());
-    Sort();
-    RemoveFullSquares();
-    m_Size = CalculateSize();
-  }
-
-  size_t Size() const
-  {
-    ASSERT_EQUAL(m_Size, CalculateSize(), ());
-    return m_Size;
-  }
-
-  void Append(Covering<CellId> const & c)
-  {
-    AppendWithoutNormalize(c);
-    RemoveDuplicateChildren();
-    RemoveFullSquares();
-    m_Size = CalculateSize();
-  }
-
-  void OutputToVector(vector<CellId> & result) const
-  {
-    for (int level = 0; level < CellId::DEPTH_LEVELS; ++level)
-        result.insert(result.end(), m_Covering[level].begin(), m_Covering[level].end());
-  }
-
-  void OutputToVector(vector<int64_t> & result) const
-  {
-    for (int level = 0; level < CellId::DEPTH_LEVELS; ++level)
-      for (size_t i = 0; i < m_Covering[level].size(); ++i)
-        result.push_back(m_Covering[level][i].ToInt64());
-  }
-
-  void Simplify(int64_t minId = 0)
-  {
-    int cellsSimplified = 0;
-    int const initialSize = m_Size;
-    for (int level = CellId::DEPTH_LEVELS - 1; level > 1; --level)
-    {
-      if (m_Covering[level].size() >= 2)
-      {
-        int const initialLevelSize = static_cast<int>(m_Covering[level].size());
-        SimplifyLevel(level, minId);
-        cellsSimplified += initialLevelSize - static_cast<int>(m_Covering[level].size());
-        if (cellsSimplified > initialSize / 2)
-          break;
-      }
-    }
-    RemoveDuplicateChildren();
-    RemoveFullSquares(minId);
-    m_Size = CalculateSize();
-  }
-
-private:
-
-  void SimplifyLevel(int level, int64_t minId)
-  {
-    map<CellId, uint32_t, LessQueueOrder> parentCellCounts;
-    typedef typename vector<CellId>::const_iterator ConstIteartor;
-    for (ConstIteartor it = m_Covering[level].begin(); it != m_Covering[level].end(); ++it)
-      if (it->Parent().ToInt64() >= minId)
-        ++parentCellCounts[it->Parent()];
-
-    vector<CellId> parentCells, childCells;
-    for (ConstIteartor it = m_Covering[level].begin(); it != m_Covering[level].end(); ++it)
-    {
-      if (parentCellCounts[it->Parent()] > 1)
-        parentCells.push_back(it->Parent());
-      else
-        childCells.push_back(*it);
-    }
-    ASSERT(IsSorted(parentCells.begin(), parentCells.end(), LessQueueOrder()), (parentCells));
-    ASSERT(IsSorted(childCells.begin(), childCells.end(), LessQueueOrder()), (childCells));
-    m_Covering[level].swap(childCells);
-    parentCells.erase(unique(parentCells.begin(), parentCells.end()), parentCells.end());
-    AppendToVector(m_Covering[level - 1], parentCells);
-  }
-
-  static void AppendToVector(vector<CellId> & a, vector<CellId> const & b)
-  {
-    ASSERT(IsSortedAndUnique(a.begin(), a.end(), LessQueueOrder()), (a));
-    ASSERT(IsSortedAndUnique(b.begin(), b.end(), LessQueueOrder()), (b));
-    vector<CellId> merged;
-    set_union(a.begin(), a.end(), b.begin(), b.end(), back_inserter(merged), LessQueueOrder());
-    a.swap(merged);
-  }
-
-  template <typename CompareT>
-  struct CompareCellsAtLevel
-  {
-    explicit CompareCellsAtLevel(int level) : m_Level(level) {}
-
-    bool operator() (CellId id1, CellId id2) const
-    {
-      return m_Comp(id1.AncestorAtLevel(m_Level), id2.AncestorAtLevel(m_Level));
-    }
-
-    CompareT m_Comp;
-    int m_Level;
-  };
-
-  void AppendWithoutNormalize(Covering const & c)
-  {
-    for (int level = CellId::DEPTH_LEVELS - 1; level >= 0; --level)
-      AppendToVector(m_Covering[level], c.m_Covering[level]);
-  }
-
-  void Sort()
-  {
-    for (int level = 0; level < CellId::DEPTH_LEVELS; ++level)
-      sort(m_Covering[level].begin(), m_Covering[level].end(), LessQueueOrder());
-  }
-
-  void Unique()
-  {
-    for (int level = 0; level < CellId::DEPTH_LEVELS; ++level)
-    {
-      vector<CellId> & covering = m_Covering[level];
-      ASSERT(IsSorted(covering.begin(), covering.end(), LessQueueOrder()), (covering));
-      covering.erase(unique(covering.begin(), covering.end()), covering.end());
-    }
-  }
+  uint64_t const cellArea = my::sq(uint64_t(1 << (CellIdT::DEPTH_LEVELS - 1 - cell.Level())));
+  CellObjectIntersection const intersection = intersect(cell);
 
-  void RemoveDuplicateChildren()
-  {
-    RemoveDuplicateChildrenImpl();
-#ifdef DEBUG
-    // Assert that all duplicate children were removed.
-    vector<int64_t> v1, v2;
-    OutputToVector(v1);
-    RemoveDuplicateChildrenImpl();
-    OutputToVector(v2);
-    ASSERT_EQUAL(v1, v2, ());
-#endif
-  }
-
-  void RemoveDuplicateChildrenImpl()
-  {
-    for (int parentLevel = 0; parentLevel < static_cast<int>(m_Covering.size()) - 1; ++parentLevel)
-    {
-      if (m_Covering[parentLevel].empty())
-        continue;
-      for (int childLevel = parentLevel + 1; childLevel < static_cast<int>(m_Covering.size());
-           ++childLevel)
-      {
-        vector<CellId> substracted;
-        CompareCellsAtLevel<LessQueueOrder> comparator(parentLevel);
-        ASSERT(IsSorted(m_Covering[childLevel].begin(), m_Covering[childLevel].end(), comparator),
-               (m_Covering[childLevel]));
-        ASSERT(IsSorted(m_Covering[parentLevel].begin(), m_Covering[parentLevel].end(), comparator),
-               (m_Covering[parentLevel]));
-        SetDifferenceUnlimited(m_Covering[childLevel].begin(), m_Covering[childLevel].end(),
-                               m_Covering[parentLevel].begin(), m_Covering[parentLevel].end(),
-                               back_inserter(substracted), comparator);
-        m_Covering[childLevel].swap(substracted);
-      }
-    }
-  }
-
-  void RemoveFullSquares(int64_t minId = 0)
-  {
-    vector<CellId> cellsToAppend;
-    for (int level = m_Covering.size() - 1; level >= 0; --level)
-    {
-      // a -> b + parents
-      vector<CellId> const & a = m_Covering[level];
-      vector<CellId> b;
-      vector<CellId> parents;
-      b.reserve(a.size());
-      for (size_t i = 0; i < a.size(); ++i)
-      {
-        if (i + 3 < a.size())
-        {
-          CellId const parent = a[i].Parent();
-          if (parent == a[i+1].Parent() &&
-              parent == a[i+2].Parent() &&
-              parent == a[i+3].Parent() &&
-              parent.ToInt64() >= minId)
-          {
-            parents.push_back(parent);
-            i += 3;
-            continue;
-          }
-        }
-        b.push_back(a[i]);
-      }
-      m_Covering[level].swap(b);
-      if (level > 0)
-        AppendToVector(m_Covering[level - 1], parents);
-    }
-  }
-
-  size_t CalculateSize() const
+  if (intersection == CELL_OBJECT_NO_INTERSECTION)
+    return;
+  if (intersection == CELL_INSIDE_OBJECT ||
+      cell.Level() == CellIdT::DEPTH_LEVELS - 1 ||
+      cellPenaltyArea >= cellArea)
   {
-    size_t size = 0;
-    for (int level = 0; level < CellId::DEPTH_LEVELS; ++level)
-      size += m_Covering[level].size();
-    return size;
+    out.push_back(cell);
+    return;
   }
 
-  struct CoverTriangleInfo
-  {
-    m2::PointD m_A, m_B, m_C;
-    int m_Level;
-    Covering<CellId> * m_pCovering;
-  };
-
-  static void CoverTriangleImpl(CoverTriangleInfo const & info, CellId const cell)
-  {
-    ASSERT_LESS_OR_EQUAL(cell.Level(), info.m_Level, (info.m_A, info.m_B, info.m_C));
-    CellTriangleIntersection intersection =
-        IntersectCellWithTriangle(cell, info.m_A, info.m_B, info.m_C);
-
-    if (intersection == CELL_TRIANGLE_NO_INTERSECTION)
-      return;
+  vector<CellIdT> subdiv;
+  for (uint8_t i = 0; i < 4; ++i)
+    CoverObject(intersect, cellPenaltyArea, subdiv, cell.Child(i));
 
-    if (cell.Level() == info.m_Level || intersection == CELL_INSIDE_TRIANGLE)
-    {
-      info.m_pCovering->m_Covering[cell.Level()].push_back(cell);
-      return;
-    }
 
-    for (uint8_t child = 0; child < 4; ++child)
-      CoverTriangleImpl(info, cell.Child(child));
-  }
+  uint64_t subdivArea = 0;
+  for (size_t i = 0; i < subdiv.size(); ++i)
+    subdivArea += my::sq(uint64_t(1 << (CellIdT::DEPTH_LEVELS - 1 - subdiv[i].Level())));
 
+  ASSERT(!subdiv.empty(), (cellPenaltyArea, out, cell));
 
-  array<vector<CellId>, CellId::DEPTH_LEVELS> m_Covering; // Covering by level.
-  size_t m_Size;
-};
+  if (subdiv.empty() ||
+      cellPenaltyArea * (int(subdiv.size()) - 1) >= cellArea - subdivArea)
+    out.push_back(cell);
+  else
+    out.insert(out.end(), subdiv.begin(), subdiv.end());
+}
 
 
-}
+} // namespace covering
diff --git a/geometry/covering_stream_optimizer.hpp b/geometry/covering_stream_optimizer.hpp
deleted file mode 100644
index c167588751..0000000000
--- a/geometry/covering_stream_optimizer.hpp
+++ /dev/null
@@ -1,121 +0,0 @@
-#pragma once
-#include "covering.hpp"
-#include "../base/assert.hpp"
-#include "../base/logging.hpp"
-#include "../std/algorithm.hpp"
-#include "../std/deque.hpp"
-#include "../std/iterator.hpp"
-#include "../std/map.hpp"
-#include "../std/utility.hpp"
-
-namespace covering
-{
-
-template <class CellIdT, typename ValueT, typename SinkT>
-class CoveringStreamOptimizer
-{
-public:
-  typedef CellIdT CellId;
-
-  CoveringStreamOptimizer(SinkT & sink, uint32_t windowSize, uint32_t maxDuplicates)
-    : m_Sink(sink), m_WindowSize(windowSize), m_MaxDuplicates(maxDuplicates),
-    m_LastPopped(0), m_LastPushed(0)
-  {
-    CHECK_GREATER_OR_EQUAL(windowSize, maxDuplicates, ());
-  }
-
-  ~CoveringStreamOptimizer()
-  {
-    Flush();
-  }
-
-  void Add(int64_t id, ValueT value)
-  {
-    CHECK_LESS_OR_EQUAL(m_LastPushed, id, (value));
-    m_LastPushed = id;
-    m_Buffer.push_back(make_pair(id, value));
-    if (++m_ValueCounts[value] >= m_MaxDuplicates && m_Buffer.size() >= m_WindowSize)
-      ProcessWindow(value);
-    while (m_Buffer.size() >= m_WindowSize)
-      PopFront();
-  }
-
-  void Flush()
-  {
-    while (!m_Buffer.empty())
-      PopFront();
-  }
-
-  static void Optimize(vector<int64_t> & ids, int64_t minId)
-  {
-    CHECK_GREATER(ids.size(), 2, (minId, ids));
-    CHECK(IsSortedAndUnique(ids.begin(), ids.end()), (minId, ids));
-    CHECK_GREATER_OR_EQUAL(ids[0], minId, (minId, ids));
-
-    vector<CellId> cells(ids.size(), CellId(""));
-    for (size_t i = 0; i < ids.size(); ++i)
-      cells[i] = CellId::FromInt64(ids[i]);
-    covering::Covering<CellId> covering(cells, minId);
-    covering.Simplify(minId);
-
-    vector<int64_t> res;
-    covering.OutputToVector(res);
-    sort(res.begin(), res.end());
-
-    CHECK(IsSortedAndUnique(res.begin(), res.end()), (minId, ids, res));
-    CHECK_GREATER_OR_EQUAL(res[0], minId, (minId, ids, res));
-
-    ids.swap(res);
-  }
-
-private:
-  void PopFront()
-  {
-    CHECK_LESS_OR_EQUAL(m_LastPopped, m_Buffer.front().first, ());
-    m_LastPopped = m_Buffer.front().first;
-    m_Sink(m_Buffer.front().first, m_Buffer.front().second);
-    typename map<ValueT, uint32_t>::iterator it = m_ValueCounts.find(m_Buffer.front().second);
-    CHECK(it != m_ValueCounts.end(), (m_Buffer.front().second))
-    CHECK_GREATER(it->second, 0, (m_Buffer.front().second));
-    if (--(it->second) == 0)
-      m_ValueCounts.erase(it);
-    m_Buffer.pop_front();
-  }
-
-  void ProcessWindow(ValueT value)
-  {
-    CHECK(IsSortedAndUnique(m_Buffer.begin(), m_Buffer.end()), ());
-    vector<pair<int64_t, ValueT> > others;
-    vector<int64_t> ids;
-    for (typename BufferType::const_iterator it = m_Buffer.begin(); it != m_Buffer.end(); ++it)
-    {
-      if (it->second == value)
-        ids.push_back(it->first);
-      else
-        others.push_back(*it);
-    }
-    CHECK_GREATER_OR_EQUAL(ids.size(), m_MaxDuplicates, ());
-    Optimize(ids, m_LastPopped);
-    CHECK(IsSortedAndUnique(ids.begin(), ids.end()), (ids));
-    vector<pair<int64_t, ValueT> > optimized(ids.size(), make_pair(0LL, value));
-    for (size_t i = 0; i < ids.size(); ++i)
-      optimized[i].first = ids[i];
-    CHECK(IsSortedAndUnique(others.begin(), others.end()), (others));
-    CHECK(IsSortedAndUnique(optimized.begin(), optimized.end()), (optimized));
-    m_Buffer.clear();
-    set_union(others.begin(), others.end(),
-              optimized.begin(), optimized.end(),
-              back_inserter(m_Buffer));
-    m_ValueCounts[value] = optimized.size();
-  }
-
-  SinkT & m_Sink;
-  uint32_t const m_WindowSize;
-  uint32_t const m_MaxDuplicates;
-  typedef deque<pair<int64_t, ValueT> > BufferType;
-  BufferType m_Buffer;
-  map<ValueT, uint32_t> m_ValueCounts;
-  int64_t m_LastPopped, m_LastPushed;
-};
-
-}
diff --git a/geometry/geometry.pro b/geometry/geometry.pro
index ede136c5d9..345ae13e50 100644
--- a/geometry/geometry.pro
+++ b/geometry/geometry.pro
@@ -23,7 +23,6 @@ HEADERS += \
   cellid.hpp \
   rect_intersect.hpp \
   covering.hpp \
-  covering_stream_optimizer.hpp \
   packer.hpp \
   pointu_to_uint64.hpp \
   simplification.hpp \
diff --git a/geometry/geometry_tests/covering_stream_optimizer_test.cpp b/geometry/geometry_tests/covering_stream_optimizer_test.cpp
deleted file mode 100644
index 5df567c940..0000000000
--- a/geometry/geometry_tests/covering_stream_optimizer_test.cpp
+++ /dev/null
@@ -1,63 +0,0 @@
-#include "../../testing/testing.hpp"
-#include "../cellid.hpp"
-#include "../covering.hpp"
-#include "../covering_stream_optimizer.hpp"
-#include "../../base/macros.hpp"
-
-typedef m2::CellId<5> CellId;
-
-namespace
-{
-  struct TestSink
-  {
-    vector<pair<int64_t, int> > & m_Res;
-
-    TestSink(vector<pair<int64_t, int> > & res) : m_Res(res) {}
-
-    void operator() (int64_t cell, int value) const
-    {
-      m_Res.push_back(make_pair(cell, value));
-    }
-  };
-}
-
-UNIT_TEST(CoveringStreamOptimizer_Smoke)
-{
-  // my::g_LogLevel = LDEBUG;
-  vector<pair<int64_t, int> > res1;
-  TestSink sink(res1);
-  covering::CoveringStreamOptimizer<CellId, int, TestSink> optimizer(sink, 5, 4);
-  optimizer.Add(CellId("01").ToInt64(), 1);
-  optimizer.Add(CellId("01").ToInt64(), 2);
-  optimizer.Add(CellId("0200").ToInt64(), 1);
-  optimizer.Add(CellId("0201").ToInt64(), 1);
-  optimizer.Add(CellId("0202").ToInt64(), 1);
-  optimizer.Add(CellId("021").ToInt64(), 1);
-  optimizer.Add(CellId("022").ToInt64(), 1);
-  optimizer.Flush();
-  vector<pair<CellId, int> > e, res;
-  for (size_t i = 0; i < res1.size(); ++i)
-    res.push_back(make_pair(CellId::FromInt64(res1[i].first), res1[i].second));
-  e.push_back(make_pair(CellId("01"), 1));
-  e.push_back(make_pair(CellId("01"), 2));
-  e.push_back(make_pair(CellId("02"), 1));
-  TEST_EQUAL(e, res, ());
-}
-
-UNIT_TEST(CoveringStreamOptimizer_MinId1)
-{
-  int64_t const minId = 72200890973LL;
-  int64_t ids[] = { 72200890973, 72200890995, 72200891005, 72200891011, 72200891013,
-                    72200891014, 72200891015, 72200891036, 72200896894, 72200896902 };
-  vector<int64_t> idsV(&ids[0], &ids[0] + ARRAY_SIZE(ids));
-  covering::CoveringStreamOptimizer<m2::CellId<19>, int, TestSink>::Optimize(idsV, minId);
-}
-
-UNIT_TEST(CoveringStreamOptimizer_MinId2)
-{
-  int64_t const minId = 72200890973LL;
-  int64_t ids[] = { 72200890973, 72200890994, 72200891015, 72200891036};
-  vector<int64_t> idsV(&ids[0], &ids[0] + ARRAY_SIZE(ids));
-  covering::CoveringStreamOptimizer<m2::CellId<19>, int, TestSink>::Optimize(idsV, minId);
-}
-
diff --git a/geometry/geometry_tests/covering_test.cpp b/geometry/geometry_tests/covering_test.cpp
index 5f41c0eff8..d69e4899c6 100644
--- a/geometry/geometry_tests/covering_test.cpp
+++ b/geometry/geometry_tests/covering_test.cpp
@@ -1,127 +1,4 @@
 #include "../../testing/testing.hpp"
-#include "../cellid.hpp"
 #include "../covering.hpp"
-#include "../point2d.hpp"
-#include "../../base/stl_add.hpp"
 
-typedef m2::CellId<5> CellId;
-
-UNIT_TEST(CoverTriangle_Simple)
-{
-  vector<CellId> v;
-  covering::Covering<CellId> c(m2::PointD(3*2, 3*2), m2::PointD(4*2, 12*2), m2::PointD(14*2, 3*2));
-  c.OutputToVector(v);
-  vector<CellId> e;
-  e.push_back(CellId("03"));
-  e.push_back(CellId("003"));
-  e.push_back(CellId("012"));
-  e.push_back(CellId("013"));
-  e.push_back(CellId("102"));
-  e.push_back(CellId("103"));
-  e.push_back(CellId("112"));
-  e.push_back(CellId("120"));
-  e.push_back(CellId("121"));
-  e.push_back(CellId("122"));
-  e.push_back(CellId("210"));
-  e.push_back(CellId("211"));
-  e.push_back(CellId("212"));
-  e.push_back(CellId("0211"));
-  e.push_back(CellId("0213"));
-  e.push_back(CellId("0231"));
-  e.push_back(CellId("0233"));
-  e.push_back(CellId("1130"));
-  e.push_back(CellId("1132"));
-  e.push_back(CellId("1230"));
-  e.push_back(CellId("1300"));
-  e.push_back(CellId("2011"));
-  e.push_back(CellId("2013"));
-  e.push_back(CellId("2031"));
-  e.push_back(CellId("2033"));
-  e.push_back(CellId("2130"));
-  e.push_back(CellId("2211"));
-  e.push_back(CellId("2300"));
-  e.push_back(CellId("3000"));
-  TEST_EQUAL(v, e, ());
-}
-
-UNIT_TEST(CoverTriangle_TriangleInsideCell)
-{
-  vector<CellId> v;
-  covering::Covering<CellId> c(m2::PointD(0.1, 0.1), m2::PointD(0.2, 0.2), m2::PointD(0.2, 0.4));
-  c.OutputToVector(v);
-  vector<CellId> e;
-  e.push_back(CellId("0000"));
-  TEST_EQUAL(v, e, ());
-}
-
-UNIT_TEST(Covering_Append_Simple)
-{
-  vector<CellId> v1, v2, v3;
-
-  v1.push_back(CellId("012"));
-  v2.push_back(CellId("0123"));
-  v3.push_back(CellId("012"));
-
-  v1.push_back(CellId("023"));
-  v2.push_back(CellId("023"));
-  v3.push_back(CellId("023"));
-
-  v1.push_back(CellId("130"));
-  v1.push_back(CellId("131"));
-  v2.push_back(CellId("133"));
-  v1.push_back(CellId("1320"));
-  v1.push_back(CellId("1321"));
-  v2.push_back(CellId("1322"));
-  v2.push_back(CellId("1323"));
-  v3.push_back(CellId("13"));
-
-  covering::Covering<CellId> c1(v1);
-  c1.Append(covering::Covering<CellId>(v2));
-  vector<CellId> v4;
-  c1.OutputToVector(v4);
-  sort(v4.begin(), v4.end(), CellId::LessStackOrder());
-  TEST_EQUAL(v3, v4, ());
-}
-
-UNIT_TEST(IntersectCellWithTriangle_EmptyTriangle)
-{
-  m2::PointU pt(27, 31);
-  TEST_EQUAL(covering::CELL_TRIANGLE_NO_INTERSECTION,
-             covering::IntersectCellWithTriangle(CellId("0"), pt, pt, pt), ());
-  TEST_EQUAL(covering::CELL_TRIANGLE_NO_INTERSECTION,
-             covering::IntersectCellWithTriangle(CellId("1"), pt, pt, pt), ());
-  TEST_EQUAL(covering::CELL_TRIANGLE_NO_INTERSECTION,
-             covering::IntersectCellWithTriangle(CellId("2"), pt, pt, pt), ());
-  TEST_EQUAL(covering::TRIANGLE_INSIDE_CELL,
-             covering::IntersectCellWithTriangle(CellId("3"), pt, pt, pt), ());
-}
-
-UNIT_TEST(Covering_EmptyTriangle)
-{
-  m2::PointU pt(27, 31);
-  CellId const expectedCellId = CellId::FromXY(pt.x, pt.y);
-  TEST_GREATER(expectedCellId.ToInt64(), 5, ());
-  covering::Covering<CellId> covering(pt, pt, pt);
-  vector<CellId> ids;
-  covering.OutputToVector(ids);
-  TEST_EQUAL(ids, vector<CellId>(1, expectedCellId), ());
-}
-
-UNIT_TEST(Covering_Simplify_Smoke)
-{
-  vector<CellId> v;
-  v.push_back(CellId("03"));
-  v.push_back(CellId("020"));
-  v.push_back(CellId("021"));
-  v.push_back(CellId("022"));
-  v.push_back(CellId("0012"));
-  covering::Covering<CellId> covering(v);
-  v.clear();
-  covering.Simplify();
-  covering.OutputToVector(v);
-  vector<CellId> e;
-  e.push_back(CellId("02"));
-  e.push_back(CellId("03"));
-  e.push_back(CellId("0012"));
-  TEST_EQUAL(v, e, ());
-}
+// TODO: Add covering unit tests here.
diff --git a/geometry/geometry_tests/geometry_tests.pro b/geometry/geometry_tests/geometry_tests.pro
index 86f598ecd5..51bc49822b 100644
--- a/geometry/geometry_tests/geometry_tests.pro
+++ b/geometry/geometry_tests/geometry_tests.pro
@@ -26,7 +26,6 @@ SOURCES += \
   packer_test.cpp \
   segments_intersect_test.cpp \
   covering_test.cpp \
-  covering_stream_optimizer_test.cpp \
   pointu_to_uint64_test.cpp \
   simplification_test.cpp \
   transformations_test.cpp \