src: split RTree::Search definition into own file

9 files changed, 105 insertions, 103 deletions

diff --git a/editor/draw.cpp b/editor/draw.cpp
index 39f1b9fe..ab9cb7ee 100644
--- a/editor/draw.cpp
+++ b/editor/draw.cpp
@@ -12,7 +12,7 @@
 #include <Magnum/Math/Color.h>
 #include <Magnum/Math/Vector3.h>
 #include <Magnum/GL/Renderer.h>
-#include "src/RTree.hpp"
+#include "src/RTree-search.hpp"
 
 namespace floormat {
 
diff --git a/src/RTree-search.hpp b/src/RTree-search.hpp
new file mode 100644
index 00000000..4b824cd6
--- /dev/null
+++ b/src/RTree-search.hpp
@@ -0,0 +1,72 @@
+#pragma once
+#include "compat/assert.hpp"
+#include "RTree.h"
+
+RTREE_TEMPLATE
+template<typename F>
+int RTREE_QUAL::Search(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], F&& callback) const
+{
+#ifndef FM_NO_DEBUG
+  for(int index=0; index<NUMDIMS; ++index)
+  {
+    fm_assert(a_min[index] <= a_max[index]);
+  }
+#endif
+
+  Rect rect;
+
+  for(int axis=0; axis<NUMDIMS; ++axis)
+  {
+    rect.m_min[axis] = a_min[axis];
+    rect.m_max[axis] = a_max[axis];
+  }
+
+  // NOTE: May want to return search result another way, perhaps returning the number of found elements here.
+
+  int foundCount = 0;
+  Search(m_root, &rect, foundCount, callback);
+
+  return foundCount;
+}
+
+// Search in an index tree or subtree for all data retangles that overlap the argument rectangle.
+RTREE_TEMPLATE
+template<typename F>
+bool RTREE_QUAL::Search(Node* a_node, Rect* a_rect, int& a_foundCount, F&& callback) const
+{
+  fm_assert(a_node);
+  fm_assert(a_node->m_level >= 0);
+  fm_assert(a_rect);
+
+  if(a_node->IsInternalNode())
+  {
+    // This is an internal node in the tree
+    for(int index=0; index < a_node->m_count; ++index)
+    {
+      if(Overlap(a_rect, &a_node->m_branch[index].m_rect))
+      {
+        if(!Search(a_node->m_branch[index].m_child, a_rect, a_foundCount, callback))
+        {
+          // The callback indicated to stop searching
+          return false;
+        }
+      }
+    }
+  }
+  else
+  {
+    // This is a leaf node
+    for(int index=0; index < a_node->m_count; ++index)
+    {
+      if(Overlap(a_rect, &a_node->m_branch[index].m_rect))
+      {
+        ++a_foundCount;
+        const Rect& r = a_node->m_branch[index].m_rect;
+        if(!callback(a_node->m_branch[index].m_data, r))
+          return false; // Don't continue searching
+      }
+    }
+  }
+
+  return true; // Continue searching
+}
diff --git a/src/RTree.cpp b/src/RTree.cpp
index 40343e31..f77d0697 100644
--- a/src/RTree.cpp
+++ b/src/RTree.cpp
@@ -1,4 +1,4 @@
-#define RTREE_NO_EXTERN_TEMPLATE_POOL
+#define RTREE_NO_EXTERN_TEMPLATE
 #include "RTree.hpp"
 
 //#define RTREE_POOL_DEBUG
@@ -70,10 +70,11 @@ template<typename T> void rtree_pool<T>::free(T* ptr)
     free_list = n;
 }
 
-using my_rtree = RTree<uint64_t, float, 2, float>;
-template struct rtree_pool<my_rtree::Node>;
-template struct rtree_pool<my_rtree::ListNode>;
-
 } // namespace floormat::detail
 
+using my_rtree = RTree<floormat::uint64_t, float, 2, float>;
+template struct floormat::detail::rtree_pool<my_rtree::Node>;
+template struct floormat::detail::rtree_pool<my_rtree::ListNode>;
+template<> floormat::detail::rtree_pool<my_rtree::Node> my_rtree::node_pool = {}; // NOLINT
+template<> floormat::detail::rtree_pool<my_rtree::ListNode> my_rtree::list_node_pool = {}; // NOLINT
 template class RTree<floormat::uint64_t, float, 2, float>;
diff --git a/src/RTree.h b/src/RTree.h
index 3ceb64ac..95784409 100644
--- a/src/RTree.h
+++ b/src/RTree.h
@@ -20,9 +20,17 @@
 //#define RTREE_DONT_USE_MEMPOOLS // This version does not contain a fixed memory allocator, fill in lines with EXAMPLE to implement one.
 #define RTREE_USE_SPHERICAL_VOLUME // Better split classification, may be slower on some systems
 
-namespace floormat::detail { template<typename T> struct rtree_pool; }
+#ifdef RTREE_STDIO
+// Fwd decl
+class RTFileStream;  // File I/O helper class, look below for implementation and notes.
+#endif
 
-template<typename T> struct floormat::detail::rtree_pool final
+#define RTREE_TEMPLATE template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
+#define RTREE_QUAL RTree<DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES>
+
+namespace floormat::detail {
+
+template<typename T> struct rtree_pool final
 {
     rtree_pool() noexcept;
     rtree_pool(const rtree_pool&) = delete;
@@ -44,10 +52,7 @@ private:
     node_u* free_list = nullptr;
 };
 
-#ifdef RTREE_STDIO
-// Fwd decl
-class RTFileStream;  // File I/O helper class, look below for implementation and notes.
-#endif
+} // namespace floormat::detail
 
 /// \class RTree
 /// Implementation of RTree, a multidimensional bounding rectangle tree.
@@ -234,8 +239,8 @@ public:
     Node* m_node;                                 ///< Node
   };
 
-  floormat::detail::rtree_pool<Node> node_pool;
-  floormat::detail::rtree_pool<ListNode> list_node_pool;
+  static floormat::detail::rtree_pool<Node> node_pool;
+  static floormat::detail::rtree_pool<ListNode> list_node_pool;
 
 protected:
   /// Variables for finding a split partition
@@ -302,10 +307,12 @@ public:
   void ListTree(std::vector<Rect>& vec, std::vector<Node*>& temp) const;
 };
 
-extern template class RTree<floormat::uint64_t, float, 2, float>;
+
+#ifndef RTREE_NO_EXTERN_TEMPLATE
 extern template struct floormat::detail::rtree_pool<RTree<floormat::uint64_t, float, 2, float>::Node>;
 extern template struct floormat::detail::rtree_pool<RTree<floormat::uint64_t, float, 2, float>::ListNode>;
-
+extern template class RTree<floormat::uint64_t, float, 2, float>;
+#endif
 //#undef RTREE_TEMPLATE
 //#undef RTREE_QUAL
 
diff --git a/src/RTree.hpp b/src/RTree.hpp
index 046c5e1d..de175fbd 100644
--- a/src/RTree.hpp
+++ b/src/RTree.hpp
@@ -1,6 +1,7 @@
 #pragma once
 
 #include "RTree.h"
+#include "RTree-search.hpp"
 
 #include <math.h>
 #include <stdlib.h>
@@ -13,8 +14,6 @@
 #pragma GCC diagnostic ignored "-Wzero-as-null-pointer-constant"
 #endif
 
-#define RTREE_TEMPLATE template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
-#define RTREE_QUAL RTree<DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES>
 #undef _DEBUG
 #ifndef FM_NO_DEBUG
 #define _DEBUG
@@ -31,14 +30,10 @@
   #define Max std::max
 #endif //Max
 
-namespace floormat::detail {
-
-
-#ifndef RTREE_NO_EXTERN_TEMPLATE_POOL
-extern template struct rtree_pool<RTree<std::uint64_t, float, 2, float>::Node>;
-extern template struct rtree_pool<RTree<std::uint64_t, float, 2, float>::ListNode>;
+#ifndef RTREE_NO_EXTERN_TEMPLATE
+extern template struct floormat::detail::rtree_pool<RTree<floormat::uint64_t, float, 2, float>::Node>;
+extern template struct floormat::detail::rtree_pool<RTree<floormat::uint64_t, float, 2, float>::ListNode>;
 #endif
-} // namespace floormat::detail
 
 #ifdef RTREE_STDIO
 // Because there is not stream support, this is a quick and dirty file I/O helper.
@@ -215,34 +210,6 @@ void RTREE_QUAL::Remove(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMD
 
 
 RTREE_TEMPLATE
-template<typename F>
-int RTREE_QUAL::Search(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], F&& callback) const
-{
-#ifdef _DEBUG
-  for(int index=0; index<NUMDIMS; ++index)
-  {
-    ASSERT(a_min[index] <= a_max[index]);
-  }
-#endif //_DEBUG
-
-  Rect rect;
-
-  for(int axis=0; axis<NUMDIMS; ++axis)
-  {
-    rect.m_min[axis] = a_min[axis];
-    rect.m_max[axis] = a_max[axis];
-  }
-
-  // NOTE: May want to return search result another way, perhaps returning the number of found elements here.
-
-  int foundCount = 0;
-  Search(m_root, &rect, foundCount, callback);
-
-  return foundCount;
-}
-
-
-RTREE_TEMPLATE
 int RTREE_QUAL::Count() const
 {
   int count = 0;
@@ -1288,49 +1255,6 @@ void RTREE_QUAL::ReInsert(Node* a_node, ListNode** a_listNode)
 }
 
 
-// Search in an index tree or subtree for all data retangles that overlap the argument rectangle.
-RTREE_TEMPLATE
-template<typename F>
-bool RTREE_QUAL::Search(Node* a_node, Rect* a_rect, int& a_foundCount, F&& callback) const
-{
-  ASSERT(a_node);
-  ASSERT(a_node->m_level >= 0);
-  ASSERT(a_rect);
-
-  if(a_node->IsInternalNode())
-  {
-    // This is an internal node in the tree
-    for(int index=0; index < a_node->m_count; ++index)
-    {
-      if(Overlap(a_rect, &a_node->m_branch[index].m_rect))
-      {
-        if(!Search(a_node->m_branch[index].m_child, a_rect, a_foundCount, callback))
-        {
-          // The callback indicated to stop searching
-          return false;
-        }
-      }
-    }
-  }
-  else
-  {
-    // This is a leaf node
-    for(int index=0; index < a_node->m_count; ++index)
-    {
-      if(Overlap(a_rect, &a_node->m_branch[index].m_rect))
-      {
-        ++a_foundCount;
-        const Rect& r = a_node->m_branch[index].m_rect;
-        if(!callback(a_node->m_branch[index].m_data, r))
-          return false; // Don't continue searching
-      }
-    }
-  }
-
-  return true; // Continue searching
-}
-
-
 RTREE_TEMPLATE
 void RTREE_QUAL::ListTree(std::vector<Rect>& treeList, std::vector<Node*>& toVisit) const
 {
@@ -1486,9 +1410,6 @@ bool RTREE_QUAL::Iterator::FindNextData()
 #undef _DEBUG
 #undef ASSERT
 
-#undef RTREE_QUAL
-#undef RTREE_TEMPLATE
-
 #ifdef __GNUG__
 #pragma GCC diagnostic pop
 #endif
diff --git a/src/character.cpp b/src/character.cpp
index e2888b85..5a021681 100644
--- a/src/character.cpp
+++ b/src/character.cpp
@@ -3,9 +3,10 @@
 #include "loader/loader.hpp"
 #include "src/world.hpp"
 #include "src/entity.hpp"
-#include "src/RTree.hpp"
+#include "src/RTree-search.hpp"
 #include <cmath>
 #include <utility>
+#include <algorithm>
 
 namespace floormat {
 
diff --git a/src/chunk-collision.cpp b/src/chunk-collision.cpp
index 5e0c7a94..438b6a61 100644
--- a/src/chunk-collision.cpp
+++ b/src/chunk-collision.cpp
@@ -1,7 +1,7 @@
 #include "chunk.hpp"
-#include "RTree.hpp"
 #include "tile-atlas.hpp"
 #include "entity.hpp"
+#include "src/RTree-search.hpp"
 #include <bit>
 #include <Corrade/Containers/PairStl.h>
 
diff --git a/src/chunk.hpp b/src/chunk.hpp
index c7183d2c..2fecb6fe 100644
--- a/src/chunk.hpp
+++ b/src/chunk.hpp
@@ -2,12 +2,12 @@
 #include "object-id.hpp"
 #include "tile.hpp"
 #include "tile-iterator.hpp"
+#include "src/RTree.h"
 #include <Corrade/Containers/Array.h>
 #include <type_traits>
 #include <array>
 #include <memory>
 #include <Magnum/GL/Mesh.h>
-#include "RTree.h"
 
 namespace floormat {
 
diff --git a/src/entity.cpp b/src/entity.cpp
index 10dd0ca6..42ae5c4b 100644
--- a/src/entity.cpp
+++ b/src/entity.cpp
@@ -2,7 +2,7 @@
 #include "world.hpp"
 #include "rotation.inl"
 #include "anim-atlas.hpp"
-#include "RTree.hpp"
+#include "src/RTree-search.hpp"
 #include "compat/exception.hpp"
 #include <cmath>
 #include <algorithm>