Improved OverlayTree

3 files changed, 60 insertions, 121 deletions

diff --git a/drape/overlay_tree.cpp b/drape/overlay_tree.cpp
index b00d3cbd29..d9e3367912 100644
--- a/drape/overlay_tree.cpp
+++ b/drape/overlay_tree.cpp
@@ -7,109 +7,60 @@ namespace dp
 
 void OverlayTree::StartOverlayPlacing(ScreenBase const & screen, bool canOverlap)
 {
-  m_modelView = screen;
+  m_traits.m_modelView = screen;
   m_canOverlap = canOverlap;
-  ASSERT(m_tree.empty(), ());
+  ASSERT(IsEmpty(), ());
 }
 
 void OverlayTree::Add(RefPointer<OverlayHandle> handle)
 {
+  ScreenBase const & modelView = GetModelView();
+
   handle->SetIsVisible(m_canOverlap);
-  handle->Update(m_modelView);
+  handle->Update(modelView);
 
   if (!handle->IsValid())
     return;
-
-  m2::RectD pixelRect = handle->GetPixelRect(m_modelView);
   
-  find_result_t elements;
+  m2::RectD const pixelRect = handle->GetPixelRect(modelView);
+
+  typedef buffer_vector<RefPointer<OverlayHandle>, 8> OverlayContainerT;
+  OverlayContainerT elements;
   /*
    * Find elements that already on OverlayTree and it's pixel rect
    * intersect with handle pixel rect ("Intersected elements")
    */
-  FindIntersectedFunctor f(pixelRect, elements);
-  m_tree.for_each(f);
+  ForEachInRect(pixelRect, [&] (RefPointer<OverlayHandle> r)
+  {
+    if (handle->IsIntersect(modelView, *r.GetRaw()))
+      elements.push_back(r);
+  });
 
-  double inputPriority = handle->GetPriority();
+  double const inputPriority = handle->GetPriority();
   /*
    * In this loop we decide which element must be visible
    * If input element "handle" more priority than all "Intersected elements"
    * than we remove all "Intersected elements" and insert input element "handle"
    * But if some of already inserted elements more priority than we don't insert "handle"
    */
-  for (find_result_t::const_iterator it = elements.begin(); it != elements.end(); ++it)
-  {
-    if (inputPriority < (*it)->m_nodeValue->GetPriority())
+  for (OverlayContainerT::const_iterator it = elements.begin(); it != elements.end(); ++it)
+    if (inputPriority < (*it)->GetPriority())
       return;
-  }
 
-  for (find_result_t::const_iterator it = elements.begin(); it != elements.end(); ++it)
-    m_tree.erase(*(*it));
+  for (OverlayContainerT::const_iterator it = elements.begin(); it != elements.end(); ++it)
+    Erase(*it);
 
-  m_tree.insert(Node(handle, pixelRect));
+  BaseT::Add(handle, pixelRect);
 }
 
 void OverlayTree::EndOverlayPlacing()
 {
-  for (tree_t::const_iterator it = m_tree.begin(); it != m_tree.end(); ++it)
+  ForEach([] (RefPointer<OverlayHandle> handle)
   {
-    RefPointer<OverlayHandle> handle = (*it).m_nodeValue;
     handle->SetIsVisible(true);
-  }
-  m_tree.clear();
-}
-
-////////////////////////////////////////////////
-OverlayTree::Node::Node(RefPointer<OverlayHandle> handle,
-                        m2::RectD const & pixelRect)
-  : m_nodeValue(handle)
-{
-  m_pts[0] = pixelRect.minX();
-  m_pts[1] = pixelRect.minY();
-  m_pts[2] = pixelRect.maxX();
-  m_pts[3] = pixelRect.maxY();
-}
-
-OverlayTree::BaseFindFunctor::BaseFindFunctor(m2::RectD const & r)
-  : m_rect(r)
-{
-}
-
-bool OverlayTree::BaseFindFunctor::ScanLeft(size_t plane, Node const & v) const
-{
-  switch (plane & 3)    // % 4
-  {
-  case 2: return m_rect.minX() < v[2];
-  case 3: return m_rect.minY() < v[3];
-  default: return true;
-  }
-}
-
-bool OverlayTree::BaseFindFunctor::ScanRight(size_t plane, Node const & v) const
-{
-  switch (plane & 3)  // % 4
-  {
-  case 0: return m_rect.maxX() > v[0];
-  case 1: return m_rect.maxY() > v[1];
-  default: return true;
-  }
-}
-
-OverlayTree::FindIntersectedFunctor::FindIntersectedFunctor(m2::RectD const & r,
-                                                            find_result_t & intersections)
-  : base_t(r)
-  , m_intersections(intersections)
-{
-}
-
-void OverlayTree::FindIntersectedFunctor::operator()(OverlayTree::Node const & node)
-{
-  m2::RectD const & r = base_t::m_rect;
+  });
 
-  bool isIntersect = !((node.m_pts[2] <= r.minX()) || (node.m_pts[0] >= r.maxX()) ||
-                       (node.m_pts[3] <= r.minY()) || (node.m_pts[1] >= r.maxY()));
-  if (isIntersect)
-    m_intersections.push_back(&node);
+  Clear();
 }
 
 } // namespace dp
diff --git a/drape/overlay_tree.hpp b/drape/overlay_tree.hpp
index 29344086af..2b7b994690 100644
--- a/drape/overlay_tree.hpp
+++ b/drape/overlay_tree.hpp
@@ -2,65 +2,42 @@
 
 #include "overlay_handle.hpp"
 
-#include "../base/buffer_vector.hpp"
 #include "../geometry/screenbase.hpp"
+#include "../geometry/tree4d.hpp"
 
-#include "../std/kdtree.hpp"
 
 namespace dp
 {
 
-class OverlayTree
+namespace detail
 {
-public:
-  void StartOverlayPlacing(ScreenBase const & screen, bool canOverlap = false);
-  void Add(RefPointer<OverlayHandle> handle);
-  void EndOverlayPlacing();
-
-private:
-  struct Node
-  {
-    typedef double value_type;
-
-    Node(RefPointer<OverlayHandle> handle, m2::RectD const & pixelRect);
-
-    RefPointer<OverlayHandle> m_nodeValue;
-    double m_pts[4];
-
-    double operator[] (size_t i) const { return m_pts[i]; }
-  };
 
+struct OverlayTraits
+{
   ScreenBase m_modelView;
-  typedef KDTree::KDTree<4, Node> tree_t;
-  tree_t m_tree;
-  bool m_canOverlap;
 
-private:
-  typedef buffer_vector<Node const *, 8> find_result_t;
-
-  class BaseFindFunctor
+  inline m2::RectD const LimitRect(RefPointer<OverlayHandle> handle)
   {
-  public:
-    BaseFindFunctor(m2::RectD const & r);
+    return handle->GetPixelRect(m_modelView);
+  }
+};
 
-    bool ScanLeft(size_t plane, Node const & v) const;
-    bool ScanRight(size_t plane, Node const & v) const;
+}
 
-  protected:
-    m2::RectD const & m_rect;
-  };
+class OverlayTree : public m4::Tree<RefPointer<OverlayHandle>, detail::OverlayTraits>
+{
+  typedef m4::Tree<RefPointer<OverlayHandle>, detail::OverlayTraits> BaseT;
 
-  class FindIntersectedFunctor : public BaseFindFunctor
-  {
-    typedef BaseFindFunctor base_t;
-  public:
-    FindIntersectedFunctor(m2::RectD const & r, find_result_t & intersections);
+public:
+  void StartOverlayPlacing(ScreenBase const & screen, bool canOverlap = false);
+  void Add(RefPointer<OverlayHandle> handle);
+  void EndOverlayPlacing();
 
-    void operator()(Node const & node);
+private:
+  ScreenBase const & GetModelView() const { return m_traits.m_modelView; }
 
-  private:
-    find_result_t & m_intersections;
-  };
+private:
+  bool m_canOverlap;
 };
 
 } // namespace dp
diff --git a/geometry/tree4d.hpp b/geometry/tree4d.hpp
index c4ec54fbdf..99629243f7 100644
--- a/geometry/tree4d.hpp
+++ b/geometry/tree4d.hpp
@@ -12,15 +12,15 @@
 namespace m4
 {
   template <typename T>
-  struct Traits
+  struct TraitsDef
   {
-    m2::RectD const LimitRect(T const & t)
+    m2::RectD const LimitRect(T const & t) const
     {
       return t.GetLimitRect();
     }
   };
 
-  template <class T, typename Traits = Traits<T> >
+  template <class T, typename Traits = TraitsDef<T> >
   class Tree
   {
     struct value_t
@@ -53,7 +53,7 @@ namespace m4
       {
         ostringstream out;
 
-        out << m_val.get() << ", ("
+        out << DebugPrint(m_val) << ", ("
             << m_pts[0] << ", "
             << m_pts[1] << ", "
             << m_pts[2] << ", "
@@ -141,13 +141,18 @@ namespace m4
       }
     };
 
+  protected:
+    Traits m_traits;
+    m2::RectD GetLimitRect(T const & t) const { return m_traits.LimitRect(t); }
+
   public:
+    Tree(Traits const & traits = Traits()) : m_traits(traits) {}
 
     typedef T elem_t;
 
     void Add(T const & obj)
     {
-      Add(obj, Traits::LimitRect(obj));
+      Add(obj, GetLimitRect(obj));
     }
 
     void Add(T const & obj, m2::RectD const & rect)
@@ -177,10 +182,16 @@ namespace m4
       m_tree.erase_exact(val);
     }
 
+    void Erase(T const & obj)
+    {
+      value_t val(obj, m_traits.LimitRect(obj));
+      m_tree.erase_exact(val);
+    }
+
     template <class TCompare>
     void ReplaceIf(T const & obj, TCompare comp)
     {
-      ReplaceIf(obj, Traits::LimitRect(obj), comp);
+      ReplaceIf(obj, GetLimitRect(obj), comp);
     }
 
     template <class ToDo>