Add kdtree++ and tree4d as 4-dimensional tree by object's limit rect.

4 files changed, 151 insertions, 2 deletions

diff --git a/geometry/geometry.pro b/geometry/geometry.pro
index cfad199ced..eaeb7e42b8 100644
--- a/geometry/geometry.pro
+++ b/geometry/geometry.pro
@@ -27,4 +27,4 @@ HEADERS += \
   pointu_to_uint64.hpp \
   simplification.hpp \
   transformations.hpp \
-
+  tree4d.hpp \
diff --git a/geometry/geometry_tests/geometry_tests.pro b/geometry/geometry_tests/geometry_tests.pro
index 6be20bb494..322c5d1cb8 100644
--- a/geometry/geometry_tests/geometry_tests.pro
+++ b/geometry/geometry_tests/geometry_tests.pro
@@ -28,4 +28,4 @@ SOURCES += \
   pointu_to_uint64_test.cpp \
   simplification_test.cpp \
   transformations_test.cpp \
-
+  tree_test.cpp \
diff --git a/geometry/geometry_tests/tree_test.cpp b/geometry/geometry_tests/tree_test.cpp
new file mode 100644
index 0000000000..69a67cf3e0
--- /dev/null
+++ b/geometry/geometry_tests/tree_test.cpp
@@ -0,0 +1,43 @@
+#include "../../base/SRC_FIRST.hpp"
+
+#include "../../testing/testing.hpp"
+
+#include "../tree4d.hpp"
+
+namespace
+{
+  struct simple_traits
+  {
+    static m2::RectD GetLimitRect(m2::RectD const & r) { return r; }
+  };
+
+  typedef m4::Tree<m2::RectD, simple_traits> tree_t;
+
+  bool compare_true(m2::RectD const &, m2::RectD const &) { return true; }
+}
+
+UNIT_TEST(Tree4D_Smoke)
+{
+  tree_t theTree;
+
+  m2::RectD arr[] = {
+    m2::RectD(0, 0, 1, 1),
+    m2::RectD(1, 1, 2, 2),
+    m2::RectD(2, 2, 3, 3)
+  };
+
+  for (size_t i = 0; i < ARRAY_SIZE(arr); ++i)
+    theTree.ReplaceIf(arr[i], &compare_true);
+
+  vector<m2::RectD> test;
+  theTree.ForEach(MakeBackInsertFunctor(test));
+  TEST_EQUAL(3, test.size(), ());
+
+  m2::RectD const replaceR(0.5, 0.5, 2.5, 2.5);
+  theTree.ReplaceIf(replaceR, &compare_true);
+
+  test.clear();
+  theTree.ForEach(MakeBackInsertFunctor(test));
+  TEST_EQUAL(1, test.size(), ());
+  TEST_EQUAL(test[0], replaceR, ());
+}
diff --git a/geometry/tree4d.hpp b/geometry/tree4d.hpp
new file mode 100644
index 0000000000..7e22ed290f
--- /dev/null
+++ b/geometry/tree4d.hpp
@@ -0,0 +1,106 @@
+#pragma once
+
+#include "rect2d.hpp"
+#include "point2d.hpp"
+
+#include "../base/stl_add.hpp"
+
+#include "../std/kdtree.hpp"
+
+
+namespace m4
+{
+  template <class T, class TTraits>
+  class Tree
+  {
+    struct value_t
+    {
+      T m_val;
+      double m_pts[4];
+
+      typedef double value_type;
+
+      value_t(T const & t, m2::RectD const & r) : m_val(t)
+      {
+        m_pts[0] = r.minX();
+        m_pts[1] = r.minY();
+        m_pts[2] = r.maxX();
+        m_pts[3] = r.maxY();
+      }
+
+      bool IsIntersect(m2::RectD const & r) const
+      {
+        return !((m_pts[2] <= r.minX()) || (m_pts[0] >= r.maxX()) ||
+                 (m_pts[3] <= r.minY()) || (m_pts[1] >= r.maxY()));
+      }
+
+      double operator[](size_t i) const { return m_pts[i]; }
+    };
+
+    typedef KDTree::KDTree<4, value_t> tree_t;
+    typedef typename tree_t::_Region_ region_t;
+    tree_t m_tree;
+
+  public:
+
+    template <class TCompare>
+    void ReplaceIf(T const & obj, TCompare comp)
+    {
+      m2::RectD const rect = TTraits::GetLimitRect(obj);
+
+      region_t rgn;
+      for (size_t i = 0; i < 4; ++i)
+      {
+        if (i % 2 == 0)
+        {
+          rgn._M_low_bounds[i] = rect.minX();
+          rgn._M_high_bounds[i] = rect.maxX();
+        }
+        else
+        {
+          rgn._M_low_bounds[i] = rect.minY();
+          rgn._M_high_bounds[i] = rect.maxY();
+        }
+      }
+
+      typedef vector<value_t const *> store_vec_t;
+      store_vec_t isect;
+
+      class insert_if_intersect
+      {
+        store_vec_t & m_isect;
+        m2::RectD const & m_rect;
+
+      public:
+        insert_if_intersect(store_vec_t & isect, m2::RectD const & r)
+          : m_isect(isect), m_rect(r)
+        {
+        }
+
+        void operator() (value_t const & v)
+        {
+          if (v.IsIntersect(m_rect))
+            m_isect.push_back(&v);
+        }
+      };
+
+      m_tree.visit_within_range(rgn, insert_if_intersect(isect, rect));
+
+      for (size_t i = 0; i < isect.size(); ++i)
+        if (!comp(obj, isect[i]->m_val))
+          return;
+
+      for (store_vec_t::const_iterator i = isect.begin(); i != isect.end(); ++i)
+        m_tree.erase(**i);
+
+      m_tree.insert(value_t(obj, rect));
+    }
+
+    template <class ToDo>
+    void ForEach(ToDo toDo) const
+    {
+      for (tree_t::const_iterator i = m_tree.begin(); i != m_tree.end(); ++i)
+        toDo((*i).m_val);
+    }
+  };
+}