| Geant4 Cross Reference |
1 //
2 // ********************************************************************
3 // * License and Disclaimer *
4 // * *
5 // * The Geant4 software is copyright of the Copyright Holders of *
6 // * the Geant4 Collaboration. It is provided under the terms and *
7 // * conditions of the Geant4 Software License, included in the file *
8 // * LICENSE and available at http://cern.ch/geant4/license . These *
9 // * include a list of copyright holders. *
10 // * *
11 // * Neither the authors of this software system, nor their employing *
12 // * institutes,nor the agencies providing financial support for this *
13 // * work make any representation or warranty, express or implied, *
14 // * regarding this software system or assume any liability for its *
15 // * use. Please see the license in the file LICENSE and URL above *
16 // * for the full disclaimer and the limitation of liability. *
17 // * *
18 // * This code implementation is the result of the scientific and *
19 // * technical work of the GEANT4 collaboration. *
20 // * By using, copying, modifying or distributing the software (or *
21 // * any work based on the software) you agree to acknowledge its *
22 // * use in resulting scientific publications, and indicate your *
23 // * acceptance of all terms of the Geant4 Software license. *
24 // ********************************************************************
25 //
26 //
27 /*
28 * G4Octree.cc
29 *
30 * Created on: Feb 15, 2019
31 * Author: HoangTran
32 */
33
34 #ifndef G4Octree_hh
35 #define G4Octree_hh 1
36 #include <array>
37 #include <vector>
38 #include <algorithm>
39 #include <type_traits>
40 #include <utility>
41 #include <iterator>
42 #include <iostream>
43 #include <typeinfo>
44 #include <list>
45 #include "G4ThreeVector.hh"
46 #include "G4DNABoundingBox.hh"
47 #include "G4Allocator.hh"
48
49 //using std::vector;
50 //using std::array;
51 //using namespace std;
52
53 const size_t max_per_node = 2;
54 const size_t max_depth = 100;
55
56 template <typename Iterator, class Extractor,typename Point = G4ThreeVector>
57 class G4Octree {
58 public:
59 G4Octree();
60 G4Octree(Iterator,Iterator);
61 G4Octree(Iterator,Iterator, Extractor);
62
63 using tree_type = G4Octree<Iterator,Extractor,Point>;
64
65 //G4Octree(const tree_type& rhs);
66 G4Octree(tree_type && rhs);
67 void swap(tree_type& rhs);
68
69 tree_type& operator = (tree_type rhs);
70 tree_type& operator = (tree_type && rhs);
71
72 ~G4Octree();
73
74 size_t size() const;
75
76 template <typename OutPutContainer>
77 void radiusNeighbors(const Point& query, const G4double& radius, OutPutContainer& resultIndices) const;
78
79 void *operator new(size_t);
80 void operator delete(void *);
81
82 private:
83 enum NodeTypes
84 {
85 DEFAULT,
86 LEAF,
87 MAX_DEPTH_LEAF,
88 INTERNAL
89 };
90
91 class Node;
92
93 using NodeVector = std::vector<std::pair<Iterator,Point>>;
94 using childNodeArray = std::array<Node*,8>;
95 struct LeafValues
96 {
97 std::array<std::pair<Iterator,Point>,
98 max_per_node> values_;
99 size_t size_;
100 };
101
102 class Node
103 {
104 public:
105 Node(const NodeVector& input_values);
106 Node(const NodeVector& input_values,
107 const G4DNABoundingBox& box,
108 size_t current_depth);
109 Node() = default;
110 Node(const Node&) = delete;
111 ~Node();
112 template <typename OutPutContainer>
113 G4bool radiusNeighbors(const Point& query, G4double radius,
114 OutPutContainer& resultIndices) const;
115 private:
116 void* fpValue;
117 G4DNABoundingBox fBigVolume;
118 NodeTypes fNodeType;
119
120 void init_max_depth_leaf(const NodeVector& input_values);
121 void init_leaf(const NodeVector& input_values);
122 void init_internal(
123 const NodeVector& input_values,
124 size_t current_depth);
125 struct InnerIterator
126 {
127 using wrapped_type = typename NodeVector::const_iterator;
128 wrapped_type it__;
129 InnerIterator(wrapped_type it):it__(it)
130 {}
131 Point operator*() const
132 {
133 return ((*it__).second);
134 }
135 InnerIterator& operator++()
136 {
137 ++it__;
138 return *this;
139 }
140 InnerIterator operator++(G4int)
141 {
142 InnerIterator other = *this;
143 ++it__;
144 return other;
145 }
146
147 G4bool operator==(const InnerIterator& rhs) const
148 {
149 return this->it__ == rhs.it__;
150 }
151
152 G4bool operator!=(const InnerIterator& rhs) const
153 {
154 return !operator==(rhs);
155 }
156 };
157 };
158 private:
159 Extractor functor_;
160 Node* head_;
161 size_t size_;
162 G4ThreadLocalStatic G4Allocator<tree_type>* fgAllocator;
163
164 };
165 //....oooOO0OOooo........oooOO0OOooo........oooOO0OOooo........oooOO0OOooo....
166 #include "G4Octree.icc"
167 #endif
168