KDTreeLinkerAlgo< DATA, DIM > Class Template Reference

#include <KDTreeLinkerAlgo.h>

Public Member Functions
void	build (std::vector< KDTreeNodeInfo< DATA, DIM > > &eltList, const KDTreeBox< DIM > &region)
void	clear ()
bool	empty ()
void	search (const KDTreeBox< DIM > &searchBox, std::vector< DATA > &resRecHitList)
int	size ()
	~KDTreeLinkerAlgo ()

Private Member Functions
void	clearTree ()
int	medianSearch (int low, int high, int treeDepth) const
int	recBuild (int low, int hight, int depth)
void	recSearch (int current, const KDTreeBox< DIM > &trackBox, int depth=0) const

Private Attributes
std::vector< DATA > *	closestNeighbour
std::vector< KDTreeNodeInfo < DATA, DIM > > *	initialEltList
KDTreeNodes< DATA, DIM >	nodePool_

Detailed Description

template<typename DATA, unsigned int DIM = 2>
class KDTreeLinkerAlgo< DATA, DIM >

Definition at line 102 of file KDTreeLinkerAlgo.h.

Constructor & Destructor Documentation

template<typename DATA, unsigned int DIM = 2>

KDTreeLinkerAlgo< DATA, DIM >::~KDTreeLinkerAlgo ( )

inline

Definition at line 105 of file KDTreeLinkerAlgo.h.

{ clear(); }

Member Function Documentation

template<typename DATA, unsigned int DIM>

void KDTreeLinkerAlgo< DATA, DIM >::build	(	std::vector< KDTreeNodeInfo< DATA, DIM > > &	eltList,
		const KDTreeBox< DIM > &	region
	)

Definition at line 147 of file KDTreeLinkerAlgo.h.

References cms::cuda::assert(), and findQualityFiles::size.

Referenced by KDTreeLinkerTrackEcal::buildTree(), KDTreeLinkerTrackHcal::buildTree(), KDTreeLinkerPSEcal::buildTree(), HGCalImagingAlgo::findAndAssignClusters(), HGCalImagingAlgo::makeClusters(), and psClasses.BuildThread::run().

                                                                      {
  if (!eltList.empty()) {
    initialEltList = &eltList;

    size_t size = initialEltList->size();
    nodePool_.build(size);

    // Here we build the KDTree
    int root = recBuild(0, size, 0);
    assert(root == 0);

    initialEltList = nullptr;
  }
}

template<typename DATA, unsigned int DIM = 2>

void KDTreeLinkerAlgo< DATA, DIM >::clear ( void  )

inline

Definition at line 122 of file KDTreeLinkerAlgo.h.

Referenced by KDTreeLinkerPSEcal::clear(), KDTreeLinkerTrackEcal::clear(), KDTreeLinkerTrackHcal::clear(), HGCalImagingAlgo::findAndAssignClusters(), BeautifulSoup.Tag::setString(), and KDTreeLinkerAlgo< reco::PFRecHit const * >::~KDTreeLinkerAlgo().

{ clearTree(); }

template<typename DATA, unsigned int DIM = 2>

void KDTreeLinkerAlgo< DATA, DIM >::clearTree ( )

inlineprivate

Definition at line 141 of file KDTreeLinkerAlgo.h.

Referenced by KDTreeLinkerAlgo< reco::PFRecHit const * >::clear().

{ nodePool_.clear(); }

template<typename DATA, unsigned int DIM = 2>

bool KDTreeLinkerAlgo< DATA, DIM >::empty ( )

inline

Definition at line 115 of file KDTreeLinkerAlgo.h.

{ return nodePool_.empty(); }

template<typename DATA , unsigned int DIM>

int KDTreeLinkerAlgo< DATA, DIM >::medianSearch ( int  low, int  high, int  treeDepth  ) const

private

Definition at line 165 of file KDTreeLinkerAlgo.h.

References DIM, KDTreeNodeInfo< DATA, DIM >::dims, mps_fire::i, dqmiolumiharvest::j, cmsLHEtoEOSManager::l, visualization-live-secondInstance_cfg::m, median(), and std::swap().

                                                                                    {
  int nbrElts = high - low;
  int median = (nbrElts & 1) ? nbrElts / 2 : nbrElts / 2 - 1;
  median += low;

  int l = low;
  int m = high - 1;

  while (l < m) {
    KDTreeNodeInfo<DATA, DIM> elt = (*initialEltList)[median];
    int i = l;
    int j = m;

    do {
      // The even depth is associated to dim1 dimension
      // The odd one to dim2 dimension
      const unsigned thedim = treeDepth % DIM;
      while ((*initialEltList)[i].dims[thedim] < elt.dims[thedim])
        ++i;
      while ((*initialEltList)[j].dims[thedim] > elt.dims[thedim])
        --j;

      if (i <= j) {
        std::swap((*initialEltList)[i], (*initialEltList)[j]);
        i++;
        j--;
      }
    } while (i <= j);
    if (j < median)
      l = i;
    if (i > median)
      m = j;
  }

  return median;
}

template<typename DATA , unsigned int DIM>

int KDTreeLinkerAlgo< DATA, DIM >::recBuild ( int  low, int  hight, int  depth  )

private

Definition at line 259 of file KDTreeLinkerAlgo.h.

References cms::cuda::assert(), KDTreeNodeInfo< DATA, DIM >::data, HLT_FULL_cff::depth, DIM, KDTreeNodeInfo< DATA, DIM >::dims, mps_fire::i, and info().

                                                                      {
  int portionSize = high - low;

  if (portionSize == 1) {  // Leaf case
    int leaf = nodePool_.getNextNode();
    const KDTreeNodeInfo<DATA, DIM> &info = (*initialEltList)[low];
    nodePool_.right[leaf] = 0;
    for (unsigned i = 0; i < DIM; ++i) {
      nodePool_.dims[i][leaf] = info.dims[i];
    }
    nodePool_.data[leaf] = info.data;
    return leaf;

  } else {  // Node case

    // The even depth is associated to dim1 dimension
    // The odd one to dim2 dimension
    int medianId = medianSearch(low, high, depth);
    int dimIndex = depth % DIM;
    float medianVal = (*initialEltList)[medianId].dims[dimIndex];

    // We create the node
    int nodeInd = nodePool_.getNextNode();

    ++depth;
    ++medianId;

    // We recursively build the son nodes
    int left = recBuild(low, medianId, depth);
    assert(nodeInd + 1 == left);
    int right = recBuild(medianId, high, depth);
    nodePool_.right[nodeInd] = right;

    nodePool_.dims[dimIndex][nodeInd] = medianVal;

    return nodeInd;
  }
}

template<typename DATA , unsigned int DIM>

void KDTreeLinkerAlgo< DATA, DIM >::recSearch ( int  current, const KDTreeBox< DIM > &  trackBox, int  depth = 0  ) const

private

Definition at line 212 of file KDTreeLinkerAlgo.h.

References HLT_FULL_cff::depth, DIM, KDTreeBox< DIM >::dimmax, KDTreeBox< DIM >::dimmin, mps_fire::i, and median().

                                                                                                        {
  // Iterate until leaf is found, or there are no children in the
  // search window. If search has to proceed on both children, proceed
  // the search to left child via recursion. Swap search window
  // dimension on alternate levels.
  while (true) {
    const int dimIndex = depth % DIM;
    int right = nodePool_.right[current];
    if (nodePool_.isLeaf(right)) {
      // If point inside the rectangle/area
      // Use intentionally bit-wise & instead of logical && for better
      // performance. It is faster to always do all comparisons than to
      // allow use of branches to not do some if any of the first ones
      // is false.
      bool isInside = true;
      for (unsigned i = 0; i < DIM; ++i) {
        float dimCurr = nodePool_.dims[i][current];
        isInside &= (dimCurr >= trackBox.dimmin[i]) & (dimCurr <= trackBox.dimmax[i]);
      }
      if (isInside) {
        closestNeighbour->push_back(nodePool_.data[current]);
      }
      break;
    } else {
      float median = nodePool_.dims[dimIndex][current];

      bool goLeft = (trackBox.dimmin[dimIndex] <= median);
      bool goRight = (trackBox.dimmax[dimIndex] >= median);

      ++depth;
      if (goLeft & goRight) {
        int left = current + 1;
        recSearch(left, trackBox, depth);
        // continue with right
        current = right;
      } else if (goLeft) {
        ++current;
      } else if (goRight) {
        current = right;
      } else {
        break;
      }
    }
  }
}

template<typename DATA, unsigned int DIM>

void KDTreeLinkerAlgo< DATA, DIM >::search	(	const KDTreeBox< DIM > &	searchBox,
		std::vector< DATA > &	resRecHitList
	)

Definition at line 203 of file KDTreeLinkerAlgo.h.

References relativeConstraints::empty, and HLT_FULL_cff::recHits.

Referenced by HGCalImagingAlgo::calculateLocalDensity(), HGCalImagingAlgo::findAndAssignClusters(), BeautifulSoup.SoupStrainer::search(), KDTreeLinkerPSEcal::searchLinks(), KDTreeLinkerTrackHcal::searchLinks(), and KDTreeLinkerTrackEcal::searchLinks().

                                                                                                 {
  if (!empty()) {
    closestNeighbour = &recHits;
    recSearch(0, trackBox, 0);
    closestNeighbour = nullptr;
  }
}

template<typename DATA, unsigned int DIM = 2>

int KDTreeLinkerAlgo< DATA, DIM >::size ( void  )

inline

Definition at line 119 of file KDTreeLinkerAlgo.h.

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

{ return nodePool_.size(); }

Member Data Documentation

template<typename DATA, unsigned int DIM = 2>

std::vector<DATA>* KDTreeLinkerAlgo< DATA, DIM >::closestNeighbour

private

Definition at line 128 of file KDTreeLinkerAlgo.h.

template<typename DATA, unsigned int DIM = 2>

std::vector<KDTreeNodeInfo<DATA, DIM> >* KDTreeLinkerAlgo< DATA, DIM >::initialEltList

private

Definition at line 129 of file KDTreeLinkerAlgo.h.

template<typename DATA, unsigned int DIM = 2>

KDTreeNodes<DATA, DIM> KDTreeLinkerAlgo< DATA, DIM >::nodePool_

private

Definition at line 126 of file KDTreeLinkerAlgo.h.

Referenced by KDTreeLinkerAlgo< reco::PFRecHit const * >::clearTree(), KDTreeLinkerAlgo< reco::PFRecHit const * >::empty(), and KDTreeLinkerAlgo< reco::PFRecHit const * >::size().