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 38 of file FKDTree.h.

Constructor & Destructor Documentation

template<class TYPE , unsigned int numberOfDimensions>

FKDTree< TYPE, numberOfDimensions >::FKDTree ( )

inline

Definition at line 43 of file FKDTree.h.

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

        {
            theNumberOfPoints = 0;
            theDepth = 0;
        }

Member Function Documentation

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 273 of file FKDTree.h.

References FKDPoint< TYPE, numberOfDimensions >::getId(), mps_fire::i, position, FKDTree< TYPE, numberOfDimensions >::theDimensions, and FKDTree< TYPE, numberOfDimensions >::theIds.

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

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

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 281 of file FKDTree.h.

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

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

template<class TYPE , unsigned int numberOfDimensions>

void FKDTree< TYPE, numberOfDimensions >::build ( std::vector< FKDPoint< TYPE, numberOfDimensions > > &  points )

inline

Definition at line 133 of file FKDTree.h.

References a, FKDTree< TYPE, numberOfDimensions >::add_at_position(), b, egammaForCoreTracking_cff::depth, pat::helper::ParametrizationHelper::dimension(), mps_fire::i, CMSBoostedTauSeedingParameters_cfi::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().

        {
            // 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);
            }

        }

template<class TYPE , unsigned int numberOfDimensions>

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

inline

Definition at line 49 of file FKDTree.h.

References FKDTree< TYPE, numberOfDimensions >::theNumberOfPoints.

Referenced by Vispa.Gui.VispaWidget.TextField::setAutosizeFont(), and Vispa.Gui.VispaWidget.TextField::setAutotruncate().

        {
            return theNumberOfPoints == 0;
        }

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 252 of file FKDTree.h.

References FKDTree< TYPE, numberOfDimensions >::theDimensions.

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

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

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 260 of file FKDTree.h.

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

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

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

template<class TYPE , unsigned int numberOfDimensions>

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

inlineprivate

Definition at line 241 of file FKDTree.h.

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

        {
            return 2 * index + 1;
        }

template<class TYPE , unsigned int numberOfDimensions>

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

inlineprivate

Definition at line 228 of file FKDTree.h.

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

        {
            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;
        }

template<class TYPE , unsigned int numberOfDimensions>

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

inlineprivate

Definition at line 246 of file FKDTree.h.

        {
            return 2 * index + 2;
        }

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 60 of file FKDTree.h.

References egammaForCoreTracking_cff::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().

        {
            //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);
            }

        }

template<class TYPE , unsigned int numberOfDimensions>

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

inline

Definition at line 212 of file FKDTree.h.

References FKDTree< TYPE, numberOfDimensions >::theNumberOfPoints.

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

        {
            return theNumberOfPoints;
        }

Member Data Documentation

template<class TYPE , unsigned int numberOfDimensions>

unsigned int FKDTree< TYPE, numberOfDimensions >::theDepth

private

Definition at line 290 of file FKDTree.h.

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

template<class TYPE , unsigned int numberOfDimensions>

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

private

Definition at line 293 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().

template<class TYPE , unsigned int numberOfDimensions>

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

private

Definition at line 296 of file FKDTree.h.

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

template<class TYPE , unsigned int numberOfDimensions>

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

private

Definition at line 294 of file FKDTree.h.

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

template<class TYPE , unsigned int numberOfDimensions>

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

private

Definition at line 295 of file FKDTree.h.

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

template<class TYPE , unsigned int numberOfDimensions>

unsigned int FKDTree< TYPE, numberOfDimensions >::theNumberOfPoints

private

Definition at line 289 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().