File indexing completed on 2025-01-18 09:58:46
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
0018
0019
0020
0021
0022
0023
0024
0025
0026
0027
0028
0029
0030
0031
0032
0033
0034 #ifndef G4Octree_hh
0035 #define G4Octree_hh 1
0036 #include <array>
0037 #include <vector>
0038 #include <algorithm>
0039 #include <type_traits>
0040 #include <utility>
0041 #include <iterator>
0042 #include <iostream>
0043 #include <typeinfo>
0044 #include <list>
0045 #include "G4ThreeVector.hh"
0046 #include "G4DNABoundingBox.hh"
0047 #include "G4Allocator.hh"
0048
0049
0050
0051
0052
0053 const size_t max_per_node = 2;
0054 const size_t max_depth = 100;
0055
0056 template <typename Iterator, class Extractor,typename Point = G4ThreeVector>
0057 class G4Octree {
0058 public:
0059 G4Octree();
0060 G4Octree(Iterator,Iterator);
0061 G4Octree(Iterator,Iterator, Extractor);
0062
0063 using tree_type = G4Octree<Iterator,Extractor,Point>;
0064
0065
0066 G4Octree(tree_type && rhs);
0067 void swap(tree_type& rhs);
0068
0069 tree_type& operator = (tree_type rhs);
0070 tree_type& operator = (tree_type && rhs);
0071
0072 ~G4Octree();
0073
0074 size_t size() const;
0075
0076 template <typename OutPutContainer>
0077 void radiusNeighbors(const Point& query, const G4double& radius, OutPutContainer& resultIndices) const;
0078
0079 void *operator new(size_t);
0080 void operator delete(void *);
0081
0082 private:
0083 enum NodeTypes
0084 {
0085 DEFAULT,
0086 LEAF,
0087 MAX_DEPTH_LEAF,
0088 INTERNAL
0089 };
0090
0091 class Node;
0092
0093 using NodeVector = std::vector<std::pair<Iterator,Point>>;
0094 using childNodeArray = std::array<Node*,8>;
0095 struct LeafValues
0096 {
0097 std::array<std::pair<Iterator,Point>,
0098 max_per_node> values_;
0099 size_t size_;
0100 };
0101
0102 class Node
0103 {
0104 public:
0105 Node(const NodeVector& input_values);
0106 Node(const NodeVector& input_values,
0107 const G4DNABoundingBox& box,
0108 size_t current_depth);
0109 Node() = default;
0110 Node(const Node&) = delete;
0111 ~Node();
0112 template <typename OutPutContainer>
0113 G4bool radiusNeighbors(const Point& query, G4double radius,
0114 OutPutContainer& resultIndices) const;
0115 private:
0116 void* fpValue;
0117 G4DNABoundingBox fBigVolume;
0118 NodeTypes fNodeType;
0119
0120 void init_max_depth_leaf(const NodeVector& input_values);
0121 void init_leaf(const NodeVector& input_values);
0122 void init_internal(
0123 const NodeVector& input_values,
0124 size_t current_depth);
0125 struct InnerIterator
0126 {
0127 using wrapped_type = typename NodeVector::const_iterator;
0128 wrapped_type it__;
0129 InnerIterator(wrapped_type it):it__(it)
0130 {}
0131 Point operator*() const
0132 {
0133 return ((*it__).second);
0134 }
0135 InnerIterator& operator++()
0136 {
0137 ++it__;
0138 return *this;
0139 }
0140 InnerIterator operator++(G4int)
0141 {
0142 InnerIterator other = *this;
0143 ++it__;
0144 return other;
0145 }
0146
0147 G4bool operator==(const InnerIterator& rhs) const
0148 {
0149 return this->it__ == rhs.it__;
0150 }
0151
0152 G4bool operator!=(const InnerIterator& rhs) const
0153 {
0154 return !operator==(rhs);
0155 }
0156 };
0157 };
0158 private:
0159 Extractor functor_;
0160 Node* head_;
0161 size_t size_;
0162 G4ThreadLocalStatic G4Allocator<tree_type>* fgAllocator;
0163
0164 };
0165
0166 #include "G4Octree.icc"
0167 #endif