CMS 3D CMS Logo

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
List of all members | Public Member Functions | Private Member Functions | Private Attributes
FKDTree< TYPE, numberOfDimensions > Class Template Reference

#include <FKDTree.h>

Public Member Functions

void build (std::vector< FKDPoint< TYPE, numberOfDimensions > > &points)
 
bool empty ()
 
 FKDTree ()
 
void search (const FKDPoint< TYPE, numberOfDimensions > &minPoint, const FKDPoint< TYPE, numberOfDimensions > &maxPoint, std::vector< unsigned int > &foundPoints)
 
std::size_t size () const
 

Private Member Functions

void add_at_position (const FKDPoint< TYPE, numberOfDimensions > &point, const unsigned int position)
 
void add_at_position (FKDPoint< TYPE, numberOfDimensions > &&point, const unsigned int position)
 
bool intersects (unsigned int index, const FKDPoint< TYPE, numberOfDimensions > &minPoint, const FKDPoint< TYPE, numberOfDimensions > &maxPoint, int dimension) const
 
bool is_in_the_box (unsigned int index, const FKDPoint< TYPE, numberOfDimensions > &minPoint, const FKDPoint< TYPE, numberOfDimensions > &maxPoint) const
 
unsigned int leftSonIndex (unsigned int index) const
 
unsigned int partition_complete_kdtree (unsigned int length)
 
unsigned int rightSonIndex (unsigned int index) const
 

Private Attributes

unsigned int theDepth
 
std::array< std::vector< TYPE >, numberOfDimensions > theDimensions
 
std::vector< unsigned int > theIds
 
std::vector< unsigned int > theIntervalLength
 
std::vector< unsigned int > theIntervalMin
 
unsigned int theNumberOfPoints
 

Detailed Description

template<class TYPE, unsigned int numberOfDimensions>
class FKDTree< TYPE, numberOfDimensions >

Definition at line 35 of file FKDTree.h.

Constructor & Destructor Documentation

◆ FKDTree()

template<class TYPE , unsigned int numberOfDimensions>
FKDTree< TYPE, numberOfDimensions >::FKDTree ( )
inline

Definition at line 37 of file FKDTree.h.

References FKDTree< TYPE, numberOfDimensions >::theDepth, and FKDTree< TYPE, numberOfDimensions >::theNumberOfPoints.

37  {
39  theDepth = 0;
40  }
unsigned int theDepth
Definition: FKDTree.h:237
unsigned int theNumberOfPoints
Definition: FKDTree.h:236

Member Function Documentation

◆ add_at_position() [1/2]

template<class TYPE , unsigned int numberOfDimensions>
void FKDTree< TYPE, numberOfDimensions >::add_at_position ( const FKDPoint< TYPE, numberOfDimensions > &  point,
const unsigned int  position 
)
inlineprivate

Definition at line 224 of file FKDTree.h.

References mps_fire::i, point, position, FKDTree< TYPE, numberOfDimensions >::theDimensions, and FKDTree< TYPE, numberOfDimensions >::theIds.

Referenced by FKDTree< TYPE, numberOfDimensions >::build().

224  {
225  for (unsigned int i = 0; i < numberOfDimensions; ++i)
227  theIds[position] = point.getId();
228  }
std::array< std::vector< TYPE >, numberOfDimensions > theDimensions
Definition: FKDTree.h:240
std::vector< unsigned int > theIds
Definition: FKDTree.h:243
static int position[264][3]
Definition: ReadPGInfo.cc:289
*vegas h *****************************************************used in the default bin number in original ***version of VEGAS is ***a higher bin number might help to derive a more precise ***grade subtle point
Definition: invegas.h:5

◆ add_at_position() [2/2]

template<class TYPE , unsigned int numberOfDimensions>
void FKDTree< TYPE, numberOfDimensions >::add_at_position ( FKDPoint< TYPE, numberOfDimensions > &&  point,
const unsigned int  position 
)
inlineprivate

Definition at line 230 of file FKDTree.h.

References mps_fire::i, point, position, FKDTree< TYPE, numberOfDimensions >::theDimensions, and FKDTree< TYPE, numberOfDimensions >::theIds.

230  {
231  for (unsigned int i = 0; i < numberOfDimensions; ++i)
233  theIds[position] = point.getId();
234  }
std::array< std::vector< TYPE >, numberOfDimensions > theDimensions
Definition: FKDTree.h:240
std::vector< unsigned int > theIds
Definition: FKDTree.h:243
static int position[264][3]
Definition: ReadPGInfo.cc:289
*vegas h *****************************************************used in the default bin number in original ***version of VEGAS is ***a higher bin number might help to derive a more precise ***grade subtle point
Definition: invegas.h:5

◆ build()

template<class TYPE , unsigned int numberOfDimensions>
void FKDTree< TYPE, numberOfDimensions >::build ( std::vector< FKDPoint< TYPE, numberOfDimensions > > &  points)
inline

Definition at line 109 of file FKDTree.h.

References a, FKDTree< TYPE, numberOfDimensions >::add_at_position(), b, LEDCalibrationChannels::depth, pat::helper::ParametrizationHelper::dimension(), mps_fire::i, trklet::ilog2(), HLT_2023v12_cff::maxDepth, FKDTree< TYPE, numberOfDimensions >::partition_complete_kdtree(), hiPixelPairStep_cff::points, FKDTree< TYPE, numberOfDimensions >::theDepth, FKDTree< TYPE, numberOfDimensions >::theDimensions, FKDTree< TYPE, numberOfDimensions >::theIds, FKDTree< TYPE, numberOfDimensions >::theIntervalLength, FKDTree< TYPE, numberOfDimensions >::theIntervalMin, and FKDTree< TYPE, numberOfDimensions >::theNumberOfPoints.

Referenced by psClasses.BuildThread::run().

109  {
110  // initialization of the data members
111  theNumberOfPoints = points.size();
115  for (unsigned int i = 0; i < numberOfDimensions; ++i)
117  theIds.resize(theNumberOfPoints);
118 
119  // building is done by reordering elements in a partition starting at theIntervalMin
120  // for a number of elements theIntervalLength
121  unsigned int dimension;
122  theIntervalMin[0] = 0;
124 
125  // building for each level starts here
126  for (unsigned int depth = 0; depth < theDepth; ++depth) {
127  // A heapified left-balanced tree can be represented in memory as an array.
128  // Each level contains a power of two number of elements and starts from element 2^depth -1
129  dimension = depth % numberOfDimensions;
130  unsigned int firstIndexInDepth = (1 << depth) - 1;
131  unsigned int maxDepth = (1 << depth);
132  for (unsigned int indexInDepth = 0; indexInDepth < maxDepth; ++indexInDepth) {
133  unsigned int indexInArray = firstIndexInDepth + indexInDepth;
134  unsigned int leftSonIndexInArray = 2 * indexInArray + 1;
135  unsigned int rightSonIndexInArray = leftSonIndexInArray + 1;
136 
137  // partitioning is done by choosing the pivotal element that keeps the tree heapified
138  // and left-balanced
139  unsigned int whichElementInInterval = partition_complete_kdtree(theIntervalLength[indexInArray]);
140  // the elements have been partitioned in two unsorted subspaces (one containing the elements
141  // smaller than the pivot, the other containing those greater than the pivot)
142  std::nth_element(points.begin() + theIntervalMin[indexInArray],
143  points.begin() + theIntervalMin[indexInArray] + whichElementInInterval,
144  points.begin() + theIntervalMin[indexInArray] + theIntervalLength[indexInArray],
146  const FKDPoint<TYPE, numberOfDimensions>& b) -> bool {
147  if (a[dimension] == b[dimension])
148  return a.getId() < b.getId();
149  else
150  return a[dimension] < b[dimension];
151  });
152  // the element is placed in its final position in the internal array representation
153  // of the tree
154  add_at_position(points[theIntervalMin[indexInArray] + whichElementInInterval], indexInArray);
155  if (leftSonIndexInArray < theNumberOfPoints) {
156  theIntervalMin[leftSonIndexInArray] = theIntervalMin[indexInArray];
157  theIntervalLength[leftSonIndexInArray] = whichElementInInterval;
158  }
159 
160  if (rightSonIndexInArray < theNumberOfPoints) {
161  theIntervalMin[rightSonIndexInArray] = theIntervalMin[indexInArray] + whichElementInInterval + 1;
162  theIntervalLength[rightSonIndexInArray] = (theIntervalLength[indexInArray] - 1 - whichElementInInterval);
163  }
164  }
165  }
166  // the last level of the tree may not be complete and needs special treatment
167  dimension = theDepth % numberOfDimensions;
168  unsigned int firstIndexInDepth = (1 << theDepth) - 1;
169  for (unsigned int indexInArray = firstIndexInDepth; indexInArray < theNumberOfPoints; ++indexInArray) {
170  add_at_position(points[theIntervalMin[indexInArray]], indexInArray);
171  }
172  }
std::array< std::vector< TYPE >, numberOfDimensions > theDimensions
Definition: FKDTree.h:240
unsigned int theDepth
Definition: FKDTree.h:237
std::vector< unsigned int > theIds
Definition: FKDTree.h:243
std::vector< unsigned int > theIntervalMin
Definition: FKDTree.h:242
int ilog2(double factor)
Definition: Util.h:104
unsigned int partition_complete_kdtree(unsigned int length)
Definition: FKDTree.h:187
unsigned int theNumberOfPoints
Definition: FKDTree.h:236
void add_at_position(const FKDPoint< TYPE, numberOfDimensions > &point, const unsigned int position)
Definition: FKDTree.h:224
double b
Definition: hdecay.h:118
double a
Definition: hdecay.h:119
std::vector< unsigned int > theIntervalLength
Definition: FKDTree.h:241
uint32_t dimension(pat::CandKinResolution::Parametrization parametrization)
Returns the number of free parameters in a parametrization (3 or 4)

◆ empty()

template<class TYPE , unsigned int numberOfDimensions>
bool FKDTree< TYPE, numberOfDimensions >::empty ( )
inline

Definition at line 42 of file FKDTree.h.

References FKDTree< TYPE, numberOfDimensions >::theNumberOfPoints.

42 { return theNumberOfPoints == 0; }
unsigned int theNumberOfPoints
Definition: FKDTree.h:236

◆ intersects()

template<class TYPE , unsigned int numberOfDimensions>
bool FKDTree< TYPE, numberOfDimensions >::intersects ( unsigned int  index,
const FKDPoint< TYPE, numberOfDimensions > &  minPoint,
const FKDPoint< TYPE, numberOfDimensions > &  maxPoint,
int  dimension 
) const
inlineprivate

Definition at line 204 of file FKDTree.h.

References pat::helper::ParametrizationHelper::dimension(), and FKDTree< TYPE, numberOfDimensions >::theDimensions.

Referenced by FKDTree< TYPE, numberOfDimensions >::search().

207  {
208  return (theDimensions[dimension][index] <= maxPoint[dimension] &&
209  theDimensions[dimension][index] >= minPoint[dimension]);
210  }
std::array< std::vector< TYPE >, numberOfDimensions > theDimensions
Definition: FKDTree.h:240
uint32_t dimension(pat::CandKinResolution::Parametrization parametrization)
Returns the number of free parameters in a parametrization (3 or 4)

◆ is_in_the_box()

template<class TYPE , unsigned int numberOfDimensions>
bool FKDTree< TYPE, numberOfDimensions >::is_in_the_box ( unsigned int  index,
const FKDPoint< TYPE, numberOfDimensions > &  minPoint,
const FKDPoint< TYPE, numberOfDimensions > &  maxPoint 
) const
inlineprivate

Definition at line 213 of file FKDTree.h.

References mps_fire::i, and FKDTree< TYPE, numberOfDimensions >::theDimensions.

Referenced by FKDTree< TYPE, numberOfDimensions >::search().

215  {
216  for (unsigned int i = 0; i < numberOfDimensions; ++i) {
217  if ((theDimensions[i][index] <= maxPoint[i] && theDimensions[i][index] >= minPoint[i]) == false)
218  return false;
219  }
220  return true;
221  }
std::array< std::vector< TYPE >, numberOfDimensions > theDimensions
Definition: FKDTree.h:240

◆ leftSonIndex()

template<class TYPE , unsigned int numberOfDimensions>
unsigned int FKDTree< TYPE, numberOfDimensions >::leftSonIndex ( unsigned int  index) const
inlineprivate

Definition at line 199 of file FKDTree.h.

Referenced by FKDTree< TYPE, numberOfDimensions >::search().

199 { return 2 * index + 1; }

◆ partition_complete_kdtree()

template<class TYPE , unsigned int numberOfDimensions>
unsigned int FKDTree< TYPE, numberOfDimensions >::partition_complete_kdtree ( unsigned int  length)
inlineprivate

Definition at line 187 of file FKDTree.h.

References trklet::ilog2().

Referenced by FKDTree< TYPE, numberOfDimensions >::build().

187  {
188  if (length == 1)
189  return 0;
190  unsigned int index = 1 << (ilog2(length));
191 
192  if ((index / 2) - 1 <= length - index)
193  return index - 1;
194  else
195  return length - index / 2;
196  }
int ilog2(double factor)
Definition: Util.h:104

◆ rightSonIndex()

template<class TYPE , unsigned int numberOfDimensions>
unsigned int FKDTree< TYPE, numberOfDimensions >::rightSonIndex ( unsigned int  index) const
inlineprivate

Definition at line 201 of file FKDTree.h.

201 { return 2 * index + 2; }

◆ search()

template<class TYPE , unsigned int numberOfDimensions>
void FKDTree< TYPE, numberOfDimensions >::search ( const FKDPoint< TYPE, numberOfDimensions > &  minPoint,
const FKDPoint< TYPE, numberOfDimensions > &  maxPoint,
std::vector< unsigned int > &  foundPoints 
)
inline

Definition at line 50 of file FKDTree.h.

References LEDCalibrationChannels::depth, pat::helper::ParametrizationHelper::dimension(), reco::helper::VirtualJetProducerHelper::intersection(), FKDTree< TYPE, numberOfDimensions >::intersects(), FKDTree< TYPE, numberOfDimensions >::is_in_the_box(), FKDTree< TYPE, numberOfDimensions >::leftSonIndex(), SiStripPI::min, FQueue< T >::pop_front(), FQueue< T >::push_back(), FQueue< T >::size(), FKDTree< TYPE, numberOfDimensions >::theDepth, FKDTree< TYPE, numberOfDimensions >::theDimensions, FKDTree< TYPE, numberOfDimensions >::theIds, and FKDTree< TYPE, numberOfDimensions >::theNumberOfPoints.

52  {
53  //going down the FKDTree, one needs track which indices have to be visited in the following level.
54  //a custom queue is created, since std::queue is based on lists which are sometimes not performing
55  // well on computing accelerators
56  // The initial size of the queue has to be a power of two for allowing fast modulo % operation.
57  FQueue<unsigned int> indicesToVisit(16);
58 
59  //The root element is pushed first
60  indicesToVisit.push_back(0);
61  unsigned int index;
62  bool intersection;
63  unsigned int dimension;
64  unsigned int numberOfindicesToVisitThisDepth;
65  unsigned int numberOfSonsToVisitNext;
66  unsigned int firstSonToVisitNext;
67 
68  //The loop over levels of the FKDTree starts here
69  for (unsigned int depth = 0; depth < theDepth + 1; ++depth) {
70  // At each level, comparisons are performed for a different dimension in round robin.
71  dimension = depth % numberOfDimensions;
72  numberOfindicesToVisitThisDepth = indicesToVisit.size();
73  // Loop over the nodes to be visit at this level
74  for (unsigned int visitedindicesThisDepth = 0; visitedindicesThisDepth < numberOfindicesToVisitThisDepth;
75  visitedindicesThisDepth++) {
76  index = indicesToVisit[visitedindicesThisDepth];
77  // check if the element's dimension lays between the two box borders
78  intersection = intersects(index, minPoint, maxPoint, dimension);
79  firstSonToVisitNext = leftSonIndex(index);
80 
81  if (intersection) {
82  // Check if the element is contained in the box and push it to the result
83  if (is_in_the_box(index, minPoint, maxPoint)) {
84  foundPoints.emplace_back(theIds[index]);
85  }
86  //if the element is between the box borders, both the its sons have to be visited
87  numberOfSonsToVisitNext =
88  (firstSonToVisitNext < theNumberOfPoints) + ((firstSonToVisitNext + 1) < theNumberOfPoints);
89  } else {
90  // depending on the position of the element wrt the box, one son will be visited (if it exists)
91  firstSonToVisitNext += (theDimensions[dimension][index] < minPoint[dimension]);
92 
93  numberOfSonsToVisitNext =
94  std::min((firstSonToVisitNext < theNumberOfPoints) + ((firstSonToVisitNext + 1) < theNumberOfPoints), 1);
95  }
96 
97  // the indices of the sons to be visited in the next iteration are pushed in the queue
98  for (unsigned int whichSon = 0; whichSon < numberOfSonsToVisitNext; ++whichSon) {
99  indicesToVisit.push_back(firstSonToVisitNext + whichSon);
100  }
101  }
102  // a new element is popped from the queue
103  indicesToVisit.pop_front(numberOfindicesToVisitThisDepth);
104  }
105  }
std::array< std::vector< TYPE >, numberOfDimensions > theDimensions
Definition: FKDTree.h:240
unsigned int theDepth
Definition: FKDTree.h:237
std::vector< unsigned int > theIds
Definition: FKDTree.h:243
Definition: FQueue.h:7
unsigned int theNumberOfPoints
Definition: FKDTree.h:236
bool intersects(unsigned int index, const FKDPoint< TYPE, numberOfDimensions > &minPoint, const FKDPoint< TYPE, numberOfDimensions > &maxPoint, int dimension) const
Definition: FKDTree.h:204
unsigned int leftSonIndex(unsigned int index) const
Definition: FKDTree.h:199
uint32_t dimension(pat::CandKinResolution::Parametrization parametrization)
Returns the number of free parameters in a parametrization (3 or 4)
bool is_in_the_box(unsigned int index, const FKDPoint< TYPE, numberOfDimensions > &minPoint, const FKDPoint< TYPE, numberOfDimensions > &maxPoint) const
Definition: FKDTree.h:213

◆ size()

template<class TYPE , unsigned int numberOfDimensions>
std::size_t FKDTree< TYPE, numberOfDimensions >::size ( void  ) const
inline

Member Data Documentation

◆ theDepth

template<class TYPE , unsigned int numberOfDimensions>
unsigned int FKDTree< TYPE, numberOfDimensions >::theDepth
private

◆ theDimensions

template<class TYPE , unsigned int numberOfDimensions>
std::array<std::vector<TYPE>, numberOfDimensions> FKDTree< TYPE, numberOfDimensions >::theDimensions
private

◆ theIds

template<class TYPE , unsigned int numberOfDimensions>
std::vector<unsigned int> FKDTree< TYPE, numberOfDimensions >::theIds
private

◆ theIntervalLength

template<class TYPE , unsigned int numberOfDimensions>
std::vector<unsigned int> FKDTree< TYPE, numberOfDimensions >::theIntervalLength
private

Definition at line 241 of file FKDTree.h.

Referenced by FKDTree< TYPE, numberOfDimensions >::build().

◆ theIntervalMin

template<class TYPE , unsigned int numberOfDimensions>
std::vector<unsigned int> FKDTree< TYPE, numberOfDimensions >::theIntervalMin
private

Definition at line 242 of file FKDTree.h.

Referenced by FKDTree< TYPE, numberOfDimensions >::build().

◆ theNumberOfPoints

template<class TYPE , unsigned int numberOfDimensions>
unsigned int FKDTree< TYPE, numberOfDimensions >::theNumberOfPoints
private