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.

            {
    theNumberOfPoints = 0;
    theDepth = 0;
  }

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

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.

                                                                                                     {
    for (unsigned int i = 0; i < numberOfDimensions; ++i)
      theDimensions[i][position] = point[i];
    theIds[position] = point.getId();
  }

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

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

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.

                                                                                                {
    for (unsigned int i = 0; i < numberOfDimensions; ++i)
      theDimensions[i][position] = point[i];
    theIds[position] = point.getId();
  }

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

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.

                                                                     {
    // initialization of the data members
    theNumberOfPoints = points.size();
    theDepth = ilog2(theNumberOfPoints);
    theIntervalLength.resize(theNumberOfPoints, 0);
    theIntervalMin.resize(theNumberOfPoints, 0);
    for (unsigned int i = 0; i < numberOfDimensions; ++i)
      theDimensions[i].resize(theNumberOfPoints);
    theIds.resize(theNumberOfPoints);
 
    // building is done by reordering elements in a partition starting at theIntervalMin
    // for a number of elements theIntervalLength
    unsigned int dimension;
    theIntervalMin[0] = 0;
    theIntervalLength[0] = theNumberOfPoints;
 
    // building for each level starts here
    for (unsigned int depth = 0; depth < theDepth; ++depth) {
      // A heapified left-balanced tree can be represented in memory as an array.
      // Each level contains a power of two number of elements and starts from element 2^depth -1
      dimension = depth % numberOfDimensions;
      unsigned int firstIndexInDepth = (1 << depth) - 1;
      unsigned int maxDepth = (1 << depth);
      for (unsigned int indexInDepth = 0; indexInDepth < maxDepth; ++indexInDepth) {
        unsigned int indexInArray = firstIndexInDepth + indexInDepth;
        unsigned int leftSonIndexInArray = 2 * indexInArray + 1;
        unsigned int rightSonIndexInArray = leftSonIndexInArray + 1;
 
        // partitioning is done by choosing the pivotal element that keeps the tree heapified
        // and left-balanced
        unsigned int whichElementInInterval = partition_complete_kdtree(theIntervalLength[indexInArray]);
        // the elements have been partitioned in two unsorted subspaces (one containing the elements
        // smaller than the pivot, the other containing those greater than the pivot)
        std::nth_element(points.begin() + theIntervalMin[indexInArray],
                         points.begin() + theIntervalMin[indexInArray] + whichElementInInterval,
                         points.begin() + theIntervalMin[indexInArray] + theIntervalLength[indexInArray],
                         [dimension](const FKDPoint<TYPE, numberOfDimensions>& a,
                                     const FKDPoint<TYPE, numberOfDimensions>& b) -> bool {
                           if (a[dimension] == b[dimension])
                             return a.getId() < b.getId();
                           else
                             return a[dimension] < b[dimension];
                         });
        // the element is placed in its final position in the internal array representation
        // of the tree
        add_at_position(points[theIntervalMin[indexInArray] + whichElementInInterval], indexInArray);
        if (leftSonIndexInArray < theNumberOfPoints) {
          theIntervalMin[leftSonIndexInArray] = theIntervalMin[indexInArray];
          theIntervalLength[leftSonIndexInArray] = whichElementInInterval;
        }
 
        if (rightSonIndexInArray < theNumberOfPoints) {
          theIntervalMin[rightSonIndexInArray] = theIntervalMin[indexInArray] + whichElementInInterval + 1;
          theIntervalLength[rightSonIndexInArray] = (theIntervalLength[indexInArray] - 1 - whichElementInInterval);
        }
      }
    }
    // the last level of the tree may not be complete and needs special treatment
    dimension = theDepth % numberOfDimensions;
    unsigned int firstIndexInDepth = (1 << theDepth) - 1;
    for (unsigned int indexInArray = firstIndexInDepth; indexInArray < theNumberOfPoints; ++indexInArray) {
      add_at_position(points[theIntervalMin[indexInArray]], indexInArray);
    }
  }

References a, FKDTree< TYPE, numberOfDimensions >::add_at_position(), b, LEDCalibrationChannels::depth, pat::helper::ParametrizationHelper::dimension(), mps_fire::i, HLT_2018_cff::maxDepth, FKDTree< TYPE, numberOfDimensions >::partition_complete_kdtree(), HLT_2018_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().

empty()

template<class TYPE , unsigned int numberOfDimensions>

bool FKDTree< TYPE, numberOfDimensions >::empty ( )

inline

Definition at line 42 of file FKDTree.h.

{ return theNumberOfPoints == 0; }

References FKDTree< TYPE, numberOfDimensions >::theNumberOfPoints.

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.

                                       {
    return (theDimensions[dimension][index] <= maxPoint[dimension] &&
            theDimensions[dimension][index] >= minPoint[dimension]);
  }

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

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

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.

                                                                               {
    for (unsigned int i = 0; i < numberOfDimensions; ++i) {
      if ((theDimensions[i][index] <= maxPoint[i] && theDimensions[i][index] >= minPoint[i]) == false)
        return false;
    }
    return true;
  }

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

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

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.

{ return 2 * index + 1; }

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

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.

                                                              {
    if (length == 1)
      return 0;
    unsigned int index = 1 << (ilog2(length));
 
    if ((index / 2) - 1 <= length - index)
      return index - 1;
    else
      return length - index / 2;
  }

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

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.

{ 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.

                                                    {
    //going down the FKDTree, one needs track which indices have to be visited in the following level.
    //a custom queue is created, since std::queue is based on lists which are sometimes not performing
    // well on computing accelerators
    // The initial size of the queue has to be a power of two for allowing fast modulo  % operation.
    FQueue<unsigned int> indicesToVisit(16);
 
    //The root element is pushed first
    indicesToVisit.push_back(0);
    unsigned int index;
    bool intersection;
    unsigned int dimension;
    unsigned int numberOfindicesToVisitThisDepth;
    unsigned int numberOfSonsToVisitNext;
    unsigned int firstSonToVisitNext;
 
    //The loop over levels of the FKDTree starts here
    for (unsigned int depth = 0; depth < theDepth + 1; ++depth) {
      // At each level, comparisons are performed for a different dimension in round robin.
      dimension = depth % numberOfDimensions;
      numberOfindicesToVisitThisDepth = indicesToVisit.size();
      // Loop over the nodes to be visit at this level
      for (unsigned int visitedindicesThisDepth = 0; visitedindicesThisDepth < numberOfindicesToVisitThisDepth;
           visitedindicesThisDepth++) {
        index = indicesToVisit[visitedindicesThisDepth];
        // check if the element's dimension lays between the two box borders
        intersection = intersects(index, minPoint, maxPoint, dimension);
        firstSonToVisitNext = leftSonIndex(index);
 
        if (intersection) {
          // Check if the element is contained in the box and push it to the result
          if (is_in_the_box(index, minPoint, maxPoint)) {
            foundPoints.emplace_back(theIds[index]);
          }
          //if the element is between the box borders, both the its sons have to be visited
          numberOfSonsToVisitNext =
              (firstSonToVisitNext < theNumberOfPoints) + ((firstSonToVisitNext + 1) < theNumberOfPoints);
        } else {
          // depending on the position of the element wrt the box, one son will be visited (if it exists)
          firstSonToVisitNext += (theDimensions[dimension][index] < minPoint[dimension]);
 
          numberOfSonsToVisitNext =
              std::min((firstSonToVisitNext < theNumberOfPoints) + ((firstSonToVisitNext + 1) < theNumberOfPoints), 1);
        }
 
        // the indices of the sons to be visited in the next iteration are pushed in the queue
        for (unsigned int whichSon = 0; whichSon < numberOfSonsToVisitNext; ++whichSon) {
          indicesToVisit.push_back(firstSonToVisitNext + whichSon);
        }
      }
      // a new element is popped from the queue
      indicesToVisit.pop_front(numberOfindicesToVisitThisDepth);
    }
  }

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(), 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.

Referenced by BeautifulSoup.SoupStrainer::search().

size()

template<class TYPE , unsigned int numberOfDimensions>

std::size_t FKDTree< TYPE, numberOfDimensions >::size ( void  ) const

inline

Definition at line 174 of file FKDTree.h.

{ return theNumberOfPoints; }

References FKDTree< TYPE, numberOfDimensions >::theNumberOfPoints.

Referenced by ntupleDataFormat._Collection::__iter__(), and ntupleDataFormat._Collection::__len__().

Member Data Documentation

theDepth

template<class TYPE , unsigned int numberOfDimensions>

unsigned int FKDTree< TYPE, numberOfDimensions >::theDepth

private

Definition at line 237 of file FKDTree.h.

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

theDimensions

template<class TYPE , unsigned int numberOfDimensions>

std::array<std::vector<TYPE>, numberOfDimensions> FKDTree< TYPE, numberOfDimensions >::theDimensions

private

Definition at line 240 of file FKDTree.h.

Referenced by FKDTree< TYPE, numberOfDimensions >::add_at_position(), FKDTree< TYPE, numberOfDimensions >::build(), FKDTree< TYPE, numberOfDimensions >::intersects(), FKDTree< TYPE, numberOfDimensions >::is_in_the_box(), and FKDTree< TYPE, numberOfDimensions >::search().

theIds

template<class TYPE , unsigned int numberOfDimensions>

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

private

Definition at line 243 of file FKDTree.h.

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

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

Definition at line 236 of file FKDTree.h.

Referenced by FKDTree< TYPE, numberOfDimensions >::build(), FKDTree< TYPE, numberOfDimensions >::empty(), FKDTree< TYPE, numberOfDimensions >::FKDTree(), FKDTree< TYPE, numberOfDimensions >::search(), and FKDTree< TYPE, numberOfDimensions >::size().