1 #ifndef KDTreeLinkerAlgoTemplated_h
2 #define KDTreeLinkerAlgoTemplated_h
12 template <
typename DATA>
28 std::vector<DATA> &resRecHitList);
61 float dimCurrMin,
float dimCurrMax,
62 float dimOtherMin,
float dimOtherMax);
71 template <
typename DATA >
77 initialEltList = &eltList;
79 size_t size = initialEltList->size();
80 nodePool_.build(size);
83 int root = recBuild(0, size, 0);
91 template <
typename DATA >
97 int nbrElts = high - low;
98 int median = (nbrElts & 1) ? nbrElts / 2
114 while ((*initialEltList)[
i].dim[1] < elt.
dim[1]) i++;
115 while ((*initialEltList)[
j].dim[1] > elt.
dim[1]) j--;
117 while ((*initialEltList)[
i].dim[0] < elt.
dim[0]) i++;
118 while ((*initialEltList)[
j].dim[0] > elt.
dim[0]) j--;
122 std::swap((*initialEltList)[i], (*initialEltList)[j]);
127 if (j < median) l =
i;
128 if (i > median) m =
j;
136 template <
typename DATA >
144 closestNeighbour = 0;
149 template <
typename DATA >
152 float dimCurrMin,
float dimCurrMax,
153 float dimOtherMin,
float dimOtherMax)
160 int right = nodePool_.right[
current];
161 if(nodePool_.isLeaf(right)) {
162 float dimCurr = nodePool_.median[
current];
169 if((dimCurr >= dimCurrMin) & (dimCurr <= dimCurrMax)) {
170 float dimOther = nodePool_.dimOther[
current];
171 if((dimOther >= dimOtherMin) & (dimOther <= dimOtherMax)) {
172 closestNeighbour->push_back(nodePool_.data[current]);
178 float median = nodePool_.median[
current];
180 bool goLeft = (dimCurrMin <= median);
181 bool goRight = (dimCurrMax >= median);
186 if(goLeft & goRight) {
187 int left = current+1;
188 recSearch(left, dimCurrMin, dimCurrMax, dimOtherMin, dimOtherMax);
205 template <
typename DATA>
210 template <
typename DATA>
217 template <
typename DATA>
224 template <
typename DATA>
232 template <
typename DATA>
238 int portionSize = high - low;
239 int dimIndex = depth&1;
241 if (portionSize == 1) {
242 int leaf = nodePool_.getNextNode();
244 nodePool_.right[
leaf] = 0;
245 nodePool_.median[
leaf] = info.
dim[dimIndex];
246 nodePool_.dimOther[
leaf] = info.
dim[1-dimIndex];
254 int medianId = medianSearch(low, high, depth);
255 float medianVal = (*initialEltList)[medianId].dim[dimIndex];
258 int nodeInd = nodePool_.getNextNode();
259 nodePool_.median[nodeInd] = medianVal;
265 int left = recBuild(low, medianId, depth);
266 assert(nodeInd+1 == left);
267 nodePool_.right[nodeInd] = recBuild(medianId, high, depth);
void recSearch(const KDTreeNode *current, const KDTreeBox &trackBox, std::vector< KDTreeNodeInfo > &recHits)
void build(std::vector< KDTreeNodeInfo > &eltList, const KDTreeBox ®ion)
int medianSearch(std::vector< KDTreeNodeInfo > &eltList, int low, int high, int treeDepth)
std::vector< DATA > * closestNeighbour
std::vector< KDTreeNodeInfo< DATA > > * initialEltList
KDTreeNodes< DATA > nodePool_
void search(const KDTreeBox &searchBox, std::vector< KDTreeNodeInfo > &resRecHitList)
void swap(edm::DataFrameContainer &lhs, edm::DataFrameContainer &rhs)
void clear(CLHEP::HepGenMatrix &m)
Helper function: Reset all elements of a matrix to 0.
KDTreeNode * recBuild(std::vector< KDTreeNodeInfo > &eltList, int low, int hight, int depth, const KDTreeBox ®ion)
tuple size
Write out results.
string root
initialization