Belle II Software development
QuadTreeNode.h
1/**************************************************************************
2 * basf2 (Belle II Analysis Software Framework) *
3 * Author: The Belle II Collaboration *
4 * *
5 * See git log for contributors and copyright holders. *
6 * This file is licensed under LGPL-3.0, see LICENSE.md. *
7 **************************************************************************/
8#pragma once
9
10
11#include <framework/logging/Logger.h>
12
13#include <vector>
14
15namespace Belle2 {
20 namespace TrackFindingCDC {
21
28 template<typename AX, typename AY, class AItem>
30
31 public:
34
36 using XSpan = std::array<AX, 2>;
37
39 using YSpan = std::array<AY, 2>;
40
42 using XBinBounds = std::array<AX, 4>;
43
45 using YBinBounds = std::array<AY, 4>;
46
48 using Children = std::vector<This>;
49
56 // cppcheck-suppress passedByValue
57 QuadTreeNode(XSpan xSpan, YSpan ySpan, int level, This* parent)
58 : m_xBinBounds {
59 xSpan[0],
60 xSpan[0] + (xSpan[1] - xSpan[0]) / 2,
61 xSpan[1] - (xSpan[1] - xSpan[0]) / 2,
62 xSpan[1]
63 }
64 , m_yBinBounds({
65 ySpan[0],
66 ySpan[0] + (ySpan[1] - ySpan[0]) / 2,
67 ySpan[1] - (ySpan[1] - ySpan[0]) / 2,
68 ySpan[1]
69 })
70 , m_parent(level > 0 ? parent : nullptr)
71 , m_level(level)
72 , m_filled(false)
73 {
74 B2ASSERT("QuadTree datastructure only supports levels < 255", level < 255);
75 }
76
78 void insertItem(AItem* item)
79 {
80 m_items.push_back(item);
81 }
82
84 void reserveItems(int nItems)
85 {
86 m_items.reserve(nItems);
87 }
88
90 std::vector<AItem*>& getItems()
91 {
92 return m_items;
93 }
94
96 int getNItems() const
97 {
98 return m_items.size();
99 }
100
103 {
104 m_items.clear();
105 }
106
109 {
110 return m_children;
111 }
112
118 {
119 // automatically removes all lower level objects
120 m_children.clear();
121 m_filled = false;
122 }
123
125 int getLevel() const
126 {
127 return m_level;
128 }
129
131 bool checkFilled() const
132 {
133 return m_filled;
134 }
135
138 {
139 m_filled = true;
140 }
141
144 {
145 return m_parent;
146 }
147
149 constexpr int getXNbins() const
150 {
151 return m_xBinBounds.size() / 2;
152 }
153
155 AX getXMin() const
156 {
157 return m_xBinBounds.front();
158 }
159
161 AX getXMax() const
162 {
163 return m_xBinBounds.back();
164 }
165
167 AX getXBinWidth(int iBin)
168 {
169 return std::abs(getXUpperBound(iBin) - getXLowerBound(iBin));
170 }
171
173 AX getXLowerBound(int iBin) const
174 {
175 return m_xBinBounds[2 * iBin];
176 }
177
179 AX getXUpperBound(int iBin) const
180 {
181 return m_xBinBounds[2 * iBin + 1];
182 }
183
185 constexpr int getYNbins() const
186 {
187 return m_yBinBounds.size() / 2;
188 }
189
191 AY getYMin() const
192 {
193 return m_yBinBounds.front();
194 }
195
197 AY getYMax() const
198 {
199 return m_yBinBounds.back();
200 }
201
203 AY getYBinWidth(int iBin)
204 {
205 return std::abs(getYUpperBound(iBin) - getYLowerBound(iBin));
206 }
207
208 AY getYLowerBound(int iBin) const
209 {
210 return m_yBinBounds[2 * iBin];
211 }
212
214 AY getYUpperBound(int iBin) const
215 {
216 return m_yBinBounds[2 * iBin + 1];
217 }
218
219 private:
222
224 std::vector<AItem*> m_items;
225
227 std::vector<This> m_children;
228
231
234
237
240 };
241 }
243}
void clearChildren()
Clear items which the node holds and destroy all children below this node.
Children & getChildren()
Returns the children structure of this node.
std::vector< AItem * > & getItems()
Get items from node.
AY getYBinWidth(int iBin)
Getter for the width of the iBin bin in "r" direction.
AX getXMax() const
Get maximal "Theta" value of the node.
bool m_filled
Is the node has been filled with items.
void insertItem(AItem *item)
Insert item into node.
std::vector< This > Children
Type of the child node structure for this node.
This * getParent() const
Return pointer to the parent of the node.
AY getYMax() const
Get maximal "r" value of the node.
std::array< AY, 4 > YBinBounds
Type to store the minimum and maximum of the two bins in Y direction.
std::array< AX, 4 > XBinBounds
Type to store the minimum and maximum of the two bins in X direction.
void reserveItems(int nItems)
Reserve memory for holding items.
int m_level
Level of node in the tree.
std::array< AY, 2 > YSpan
Type for a span in the Y direction that is covered by the tree.
void setFilled()
Set status of node to "filled" (children nodes has been filled)
AY getYMin() const
Get minimal "r" value of the node.
int getLevel() const
Returns level of the node in tree (i.e., how much ancestors the node has)
AX getXLowerBound(int iBin) const
Get lower "Theta" value of given bin.
void clearItems()
Clear items which the node holds.
QuadTreeNode(XSpan xSpan, YSpan ySpan, int level, This *parent)
Constructor setting up the potential division points.
AY getYUpperBound(int iBin) const
Get upper "r" value of given bin.
std::array< AX, 2 > XSpan
Type for a span in the X direction that is covered by the tree.
This * m_parent
Pointer to the parent node.
AY getYLowerBound(int iBin) const
Get lower "r" value of given bin.
bool checkFilled() const
Check whether node has been processed, i.e.
int getNItems() const
Check if the node passes threshold on number of hits.
QuadTreeNode< AX, AY, AItem > This
Type of this class.
AX getXBinWidth(int iBin)
Getter for the width of the iBin bin in "Theta" direction.
constexpr int getXNbins() const
Get number of bins in "Theta" direction.
constexpr int getYNbins() const
Get number of bins in "r" direction.
AX getXMin() const
Get minimal "Theta" value of the node.
AX getXUpperBound(int iBin) const
Get upper "Theta" value of given bin.
Abstract base class for different kinds of events.