KDTreeLinkerAlgo< DATA, DIM > Class Template Reference

#include <KDTreeLinkerAlgoT.h>

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

Private Member Functions
void	addSubtree (const KDTreeNode *current, std::vector< KDTreeNodeInfo > &recHits)
void	addSubtree (const KDTreeNodeT< DATA, DIM > *current)
void	clearTree ()
void	clearTree ()
void	clearTree ()
KDTreeNode *	getNextNode ()
KDTreeNodeT< DATA, DIM > *	getNextNode ()
int	medianSearch (std::vector< KDTreeNodeInfo > &eltList, int low, int high, int treeDepth)
int	medianSearch (int low, int high, int treeDepth)
int	medianSearch (int low, int high, int treeDepth)
KDTreeNode *	recBuild (std::vector< KDTreeNodeInfo > &eltList, int low, int hight, int depth, const KDTreeBox &region)
int	recBuild (int low, int hight, int depth)
KDTreeNodeT< DATA, DIM > *	recBuild (int low, int hight, int depth, const KDTreeBoxT< DIM > &region)
void	recSearch (int current, float dimCurrMin, float dimCurrMax, float dimOtherMin, float dimOtherMax)
void	recSearch (const KDTreeNode *current, const KDTreeBox &trackBox, std::vector< KDTreeNodeInfo > &recHits)
void	recSearch (const KDTreeNodeT< DATA, DIM > *current, const KDTreeBoxT< DIM > &trackBox)
void	swap (KDTreeNodeInfo &e1, KDTreeNodeInfo &e2)

Private Attributes
std::vector< DATA > *	closestNeighbour
std::vector< KDTreeNodeInfoT< DATA, DIM > > *	closestNeighbour
std::vector< KDTreeNodeInfo< DATA > > *	initialEltList
std::vector< KDTreeNodeInfoT< DATA, DIM > > *	initialEltList
KDTreeNode *	nodePool_
KDTreeNodes< DATA >	nodePool_
KDTreeNodeT< DATA, DIM > *	nodePool_
int	nodePoolPos_
int	nodePoolSize_
KDTreeNode *	root_
KDTreeNodeT< DATA, DIM > *	root_

Detailed Description

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

Definition at line 13 of file KDTreeLinkerAlgoT.h.

Constructor & Destructor Documentation

template<typename DATA >

KDTreeLinkerAlgo< DATA >::KDTreeLinkerAlgo

(

)

Definition at line 239 of file KDTreeLinkerAlgoT.h.

Referenced by KDTreeLinkerAlgo< DATA, DIM >::recSearch().

  : root_ (0),
    nodePool_(0),
    nodePoolSize_(-1),
    nodePoolPos_(-1)
{
}

template<typename DATA >

KDTreeLinkerAlgo< DATA >::~KDTreeLinkerAlgo

(

)

Definition at line 248 of file KDTreeLinkerAlgoT.h.

References KDTreeLinkerAlgo< DATA, DIM >::clear().

Referenced by KDTreeLinkerAlgo< DATA, DIM >::recSearch().

{
  clear();
}

template<typename DATA, unsigned DIM = 2>

KDTreeLinkerAlgo< DATA, DIM >::KDTreeLinkerAlgo

(

)

template<typename DATA, unsigned DIM = 2>

KDTreeLinkerAlgo< DATA, DIM >::~KDTreeLinkerAlgo

(

)

template<typename DATA, unsigned DIM = 2>

KDTreeLinkerAlgo< DATA, DIM >::KDTreeLinkerAlgo

(

)

template<typename DATA, unsigned DIM = 2>

KDTreeLinkerAlgo< DATA, DIM >::~KDTreeLinkerAlgo

(

)

Member Function Documentation

template<typename DATA, unsigned DIM = 2>

void KDTreeLinkerAlgo< DATA, DIM >::addSubtree ( const KDTreeNode *  current, std::vector< KDTreeNodeInfo > &  recHits  )

private

Definition at line 209 of file KDTreeLinkerAlgo.cc.

References KDTreeLinkerAlgo< DATA, DIM >::addSubtree(), KDTreeLinkerAlgo< DATA, DIM >::clear(), KDTreeLinkerAlgo< DATA, DIM >::clearTree(), KDTreeLinkerAlgo< DATA, DIM >::getNextNode(), KDTreeNode::left, KDTreeLinkerAlgo< DATA, DIM >::nodePool_, KDTreeLinkerAlgo< DATA, DIM >::nodePoolPos_, KDTreeLinkerAlgo< DATA, DIM >::nodePoolSize_, KDTreeNode::rh, KDTreeNode::right, and KDTreeLinkerAlgo< DATA, DIM >::root_.

{
  // By construction, current can't be null
  assert(current != 0);

  if ((current->left == 0) && (current->right == 0)) // leaf
    recHits.push_back(current->rh);
  else { // node
    addSubtree(current->left, recHits);
    addSubtree(current->right, recHits);
  }
}

template<typename DATA , unsigned DIM>

void KDTreeLinkerAlgo< DATA, DIM >::addSubtree ( const KDTreeNodeT< DATA, DIM > *  current )

private

Definition at line 222 of file KDTreeLinkerAlgoT.h.

References KDTreeLinkerAlgo< DATA, DIM >::closestNeighbour, KDTreeNodeT< DATA, DIM >::info, KDTreeNodeT< DATA, DIM >::left, and KDTreeNodeT< DATA, DIM >::right.

Referenced by KDTreeLinkerAlgo< DATA, DIM >::addSubtree(), and KDTreeLinkerAlgo< DATA, DIM >::recSearch().

{
  // By construction, current can't be null
  // assert(current != 0);

  if ((current->left == 0) && (current->right == 0)) // leaf
    closestNeighbour->push_back(current->info);
  else { // node
    addSubtree(current->left);
    addSubtree(current->right);
  }
}

template<typename DATA >

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

Definition at line 17 of file KDTreeLinkerAlgo.cc.

References KDTreeLinkerAlgo< DATA, DIM >::nodePool_, KDTreeLinkerAlgo< DATA, DIM >::nodePoolSize_, KDTreeLinkerAlgo< DATA, DIM >::recBuild(), and KDTreeLinkerAlgo< DATA, DIM >::root_.

{
  if (eltList.size()) {
    nodePoolSize_ = eltList.size() * 2 - 1;
    nodePool_ = new KDTreeNode[nodePoolSize_];

    // Here we build the KDTree
    root_ = recBuild(eltList, 0, eltList.size(), 0, region);
  }
}

template<typename DATA , unsigned DIM>

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

Definition at line 86 of file KDTreeLinkerAlgoT.h.

References KDTreeLinkerAlgo< DATA, DIM >::initialEltList, KDTreeLinkerAlgo< DATA, DIM >::nodePool_, KDTreeLinkerAlgo< DATA, DIM >::nodePoolSize_, KDTreeLinkerAlgo< DATA, DIM >::recBuild(), KDTreeLinkerAlgo< DATA, DIM >::root_, and KDTreeLinkerAlgo< DATA, DIM >::size().

Referenced by KDTreeLinkerTrackEcal::buildTree(), KDTreeLinkerTrackHcal::buildTree(), KDTreeLinkerPSEcal::buildTree(), HGCalImagingAlgo::findAndAssignClusters(), and QuadrupletSeedMerger::mergeTriplets().

{
  if (eltList.size()) {
    initialEltList = &eltList;
    
    size_t size = initialEltList->size();
    nodePoolSize_ = size * 2 - 1;
    nodePool_ = new KDTreeNodeT<DATA,DIM>[nodePoolSize_];
    
    // Here we build the KDTree
    root_ = recBuild(0, size, 0, region);
    
    initialEltList = 0;
  }
}

template<typename DATA, unsigned DIM = 2>

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

template<typename DATA, unsigned DIM = 2>

void KDTreeLinkerAlgo< DATA, DIM >::clear

(

)

template<typename DATA >

void KDTreeLinkerAlgo< DATA >::clear

(

void

)

Definition at line 267 of file KDTreeLinkerAlgoT.h.

References KDTreeLinkerAlgo< DATA, DIM >::clearTree(), and KDTreeLinkerAlgo< DATA, DIM >::root_.

Referenced by KDTreeLinkerAlgo< DATA, DIM >::addSubtree(), KDTreeLinkerPSEcal::clear(), KDTreeLinkerTrackHcal::clear(), KDTreeLinkerTrackEcal::clear(), HGCalImagingAlgo::findAndAssignClusters(), KDTreeLinkerAlgo< DATA, DIM >::recSearch(), KDTreeLinkerAlgo< DATA, DIM >::size(), and KDTreeLinkerAlgo< DATA, DIM >::~KDTreeLinkerAlgo().

{
  if (root_)
    clearTree();
}

template<typename DATA, unsigned DIM = 2>

void KDTreeLinkerAlgo< DATA, DIM >::clear

(

)

template<typename DATA, unsigned DIM = 2>

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

private

template<typename DATA, unsigned DIM = 2>

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

private

template<typename DATA >

void KDTreeLinkerAlgo< DATA >::clearTree ( )

private

Definition at line 256 of file KDTreeLinkerAlgoT.h.

References KDTreeLinkerAlgo< DATA, DIM >::nodePool_, KDTreeLinkerAlgo< DATA, DIM >::nodePoolPos_, KDTreeLinkerAlgo< DATA, DIM >::nodePoolSize_, and KDTreeLinkerAlgo< DATA, DIM >::root_.

Referenced by KDTreeLinkerAlgo< DATA, DIM >::addSubtree(), KDTreeLinkerAlgo< DATA, DIM >::clear(), and KDTreeLinkerAlgo< DATA, DIM >::recSearch().

{
  delete[] nodePool_;
  nodePool_ = 0;
  root_ = 0;
  nodePoolSize_ = -1;
  nodePoolPos_ = -1;
}

template<typename DATA, unsigned DIM = 2>

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

inline

Definition at line 31 of file KDTreeLinkerAlgo.h.

References KDTreeLinkerAlgo< DATA, DIM >::nodePool_.

{return nodePool_.empty();}

template<typename DATA, unsigned DIM = 2>

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

inline

Definition at line 31 of file KDTreeLinkerAlgoT.h.

References KDTreeLinkerAlgo< DATA, DIM >::nodePoolPos_.

Referenced by KDTreeLinkerAlgo< DATA, DIM >::search().

{return nodePoolPos_ == -1;}

template<typename DATA, unsigned DIM = 2>

KDTreeNode* KDTreeLinkerAlgo< DATA, DIM >::getNextNode ( )

private

template<typename DATA , unsigned DIM>

KDTreeNode * KDTreeLinkerAlgo< DATA, DIM >::getNextNode ( )

private

Definition at line 276 of file KDTreeLinkerAlgoT.h.

References KDTreeLinkerAlgo< DATA, DIM >::nodePool_, and KDTreeLinkerAlgo< DATA, DIM >::nodePoolPos_.

Referenced by KDTreeLinkerAlgo< DATA, DIM >::addSubtree(), and KDTreeLinkerAlgo< DATA, DIM >::recBuild().

{
  ++nodePoolPos_;

  // The tree size is exactly 2 * nbrElts - 1 and this is the total allocated memory.
  // If we have used more than that....there is a big problem.
  // assert(nodePoolPos_ < nodePoolSize_);

  return &(nodePool_[nodePoolPos_]);
}

template<typename DATA, unsigned DIM = 2>

int KDTreeLinkerAlgo< DATA, DIM >::medianSearch ( std::vector< KDTreeNodeInfo > &  eltList, int  low, int  high, int  treeDepth  )

private

Definition at line 90 of file KDTreeLinkerAlgo.cc.

References KDTreeNodeInfo< DATA >::dim1, KDTreeNodeInfo< DATA >::dim2, i, j, checklumidiff::l, funct::m, and KDTreeLinkerAlgo< DATA, DIM >::swap().

{
  //We should have at least 1 element to calculate the median...
  assert(low < high);

  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 elt = eltList[median];
    int i = l;
    int j = m;

    do {

      // The even depth is associated to dim1 dimension
      // The odd one to dim2 dimension
      if (treeDepth & 1) {
    while (eltList[i].dim2 < elt.dim2) i++;
    while (eltList[j].dim2 > elt.dim2) j--;
      } else {
    while (eltList[i].dim1 < elt.dim1) i++;
    while (eltList[j].dim1 > elt.dim1) j--;
      }

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

  return median;
}

template<typename DATA, unsigned DIM = 2>

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

private

template<typename DATA >

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

private

Definition at line 106 of file KDTreeLinkerAlgoT.h.

References DIM, KDTreeNodeInfoT< DATA, DIM >::dims, i, KDTreeLinkerAlgo< DATA, DIM >::initialEltList, j, checklumidiff::l, funct::m, and std::swap().

Referenced by KDTreeLinkerAlgo< DATA, DIM >::recBuild().

{
  //We should have at least 1 element to calculate the median...
  //assert(low < high);

  const int nbrElts = high - low;  
  int median = nbrElts/2 - ( 1 - 1*(nbrElts&1) );
  median += low;

  int l = low;
  int m = high - 1;
  
  while (l < m) {
    KDTreeNodeInfoT<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 DIM = 2>

KDTreeNode * KDTreeLinkerAlgo< DATA, DIM >::recBuild ( std::vector< KDTreeNodeInfo > &  eltList, int  low, int  hight, int  depth, const KDTreeBox &  region  )

private

Definition at line 31 of file KDTreeLinkerAlgo.cc.

References particleFlowClusterECALTimeSelected_cfi::depth, KDTreeBox::dim1max, KDTreeBox::dim1min, KDTreeBox::dim2max, KDTreeBox::dim2min, KDTreeLinkerAlgo< DATA, DIM >::getNextNode(), KDTreeNode::left, KDTreeLinkerAlgo< DATA, DIM >::medianSearch(), KDTreeLinkerAlgo< DATA, DIM >::recBuild(), KDTreeNode::right, and KDTreeNode::setAttributs().

{
  int portionSize = high - low;

  // By construction, portionSize > 0 can't happend.
  assert(portionSize > 0);

  if (portionSize == 1) { // Leaf case
   
    KDTreeNode *leaf = getNextNode();
    leaf->setAttributs(region, eltList[low]);
    return leaf;

  } else { // Node case
    
    // The even depth is associated to dim1 dimension
    // The odd one to dim2 dimension
    int medianId = medianSearch(eltList, low, high, depth);

    // We create the node
    KDTreeNode *node = getNextNode();
    node->setAttributs(region);


    // Here we split into 2 halfplanes the current plane
    KDTreeBox leftRegion = region;
    KDTreeBox rightRegion = region;
    if (depth & 1) {

      double medianVal = eltList[medianId].dim2;
      leftRegion.dim2max = medianVal;
      rightRegion.dim2min = medianVal;

    } else {

      double medianVal = eltList[medianId].dim1;
      leftRegion.dim1max = medianVal;
      rightRegion.dim1min = medianVal;

    }

    ++depth;
    ++medianId;

    // We recursively build the son nodes
    node->left = recBuild(eltList, low, medianId, depth, leftRegion);
    node->right = recBuild(eltList, medianId, high, depth, rightRegion);

    return node;
  }
}

template<typename DATA >

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

private

Definition at line 234 of file KDTreeLinkerAlgo.h.

References KDTreeNodeInfo< DATA >::data, particleFlowClusterECALTimeSelected_cfi::depth, KDTreeNodeInfo< DATA >::dim, info(), KDTreeLinkerAlgo< DATA, DIM >::medianSearch(), KDTreeLinkerAlgo< DATA, DIM >::nodePool_, and KDTreeLinkerAlgo< DATA, DIM >::recBuild().

{
  int portionSize = high - low;
  int dimIndex = depth&1;

  if (portionSize == 1) { // Leaf case
    int leaf = nodePool_.getNextNode();
    const KDTreeNodeInfo<DATA>& info = (*initialEltList)[low];
    nodePool_.right[leaf] = 0;
    nodePool_.median[leaf] = info.dim[dimIndex]; // dimCurrent
    nodePool_.dimOther[leaf] = info.dim[1-dimIndex];
    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);
    float medianVal = (*initialEltList)[medianId].dim[dimIndex];

    // We create the node
    int nodeInd = nodePool_.getNextNode();
    nodePool_.median[nodeInd] = medianVal;

    ++depth;
    ++medianId;

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

    return nodeInd;
  }
}

template<typename DATA , unsigned DIM>

KDTreeNodeT< DATA, DIM > * KDTreeLinkerAlgo< DATA, DIM >::recBuild ( int  low, int  hight, int  depth, const KDTreeBoxT< DIM > &  region  )

private

Definition at line 290 of file KDTreeLinkerAlgoT.h.

References particleFlowClusterECALTimeSelected_cfi::depth, DIM, KDTreeBoxT< DIM >::dimmax, KDTreeBoxT< DIM >::dimmin, KDTreeLinkerAlgo< DATA, DIM >::getNextNode(), KDTreeLinkerAlgo< DATA, DIM >::initialEltList, KDTreeNodeT< DATA, DIM >::left, KDTreeLinkerAlgo< DATA, DIM >::medianSearch(), KDTreeNodeT< DATA, DIM >::right, and KDTreeNodeT< DATA, DIM >::setAttributs().

Referenced by KDTreeLinkerAlgo< DATA, DIM >::build(), and KDTreeLinkerAlgo< DATA, DIM >::recBuild().

{
  int portionSize = high - low;

  // By construction, portionSize > 0 can't happend.
  // assert(portionSize > 0);

  if (portionSize == 1) { // Leaf case
   
    KDTreeNodeT<DATA,DIM> *leaf = getNextNode();
    leaf->setAttributs(region, (*initialEltList)[low]);
    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);

    // We create the node
    KDTreeNodeT<DATA,DIM> *node = getNextNode();
    node->setAttributs(region);


    // Here we split into 2 halfplanes the current plane
    KDTreeBoxT<DIM> leftRegion = region;
    KDTreeBoxT<DIM> rightRegion = region;
    unsigned thedim = depth % DIM;
    auto medianVal = (*initialEltList)[medianId].dims[thedim];
    leftRegion.dimmax[thedim] = medianVal;
    rightRegion.dimmin[thedim] = medianVal;    

    ++depth;
    ++medianId;

    // We recursively build the son nodes
    node->left = recBuild(low, medianId, depth, leftRegion);
    node->right = recBuild(medianId, high, depth, rightRegion);

    return node;
  }
}

template<typename DATA, unsigned DIM = 2>

void KDTreeLinkerAlgo< DATA, DIM >::recSearch ( const KDTreeNode *  current, const KDTreeBox &  trackBox, std::vector< KDTreeNodeInfo > &  recHits  )

private

Definition at line 154 of file KDTreeLinkerAlgo.cc.

References KDTreeLinkerAlgo< DATA, DIM >::addSubtree(), KDTreeNodeInfo< DATA >::dim1, KDTreeBox::dim1max, KDTreeBox::dim1min, KDTreeNodeInfo< DATA >::dim2, KDTreeBox::dim2max, KDTreeBox::dim2min, KDTreeNode::left, KDTreeLinkerAlgo< DATA, DIM >::recSearch(), KDTreeNode::region, KDTreeNode::rh, and KDTreeNode::right.

{
  // By construction, current can't be null
  assert(current != 0);

  // By Construction, a node can't have just 1 son.
  assert (!(((current->left == 0) && (current->right != 0)) ||
        ((current->left != 0) && (current->right == 0))));
    
  if ((current->left == 0) && (current->right == 0)) {//leaf case
  
    // If point inside the rectangle/area
    if ((current->rh.dim1 >= trackBox.dim1min) && (current->rh.dim1 <= trackBox.dim1max) &&
    (current->rh.dim2 >= trackBox.dim2min) && (current->rh.dim2 <= trackBox.dim2max))
      recHits.push_back(current->rh);

  } else {

    //if region( v->left ) is fully contained in the rectangle
    if ((current->left->region.dim1min >= trackBox.dim1min) && 
    (current->left->region.dim1max <= trackBox.dim1max) &&
    (current->left->region.dim2min >= trackBox.dim2min) && 
    (current->left->region.dim2max <= trackBox.dim2max))
      addSubtree(current->left, recHits);
    
    else { //if region( v->left ) intersects the rectangle
      
      if (!((current->left->region.dim1min >= trackBox.dim1max) || 
        (current->left->region.dim1max <= trackBox.dim1min) ||
        (current->left->region.dim2min >= trackBox.dim2max) || 
        (current->left->region.dim2max <= trackBox.dim2min)))
    recSearch(current->left, trackBox, recHits);
    }
    
    //if region( v->right ) is fully contained in the rectangle
    if ((current->right->region.dim1min >= trackBox.dim1min) && 
    (current->right->region.dim1max <= trackBox.dim1max) &&
    (current->right->region.dim2min >= trackBox.dim2min) && 
    (current->right->region.dim2max <= trackBox.dim2max))
      addSubtree(current->right, recHits);

    else { //if region( v->right ) intersects the rectangle
     
      if (!((current->right->region.dim1min >= trackBox.dim1max) || 
        (current->right->region.dim1max <= trackBox.dim1min) ||
        (current->right->region.dim2min >= trackBox.dim2max) || 
        (current->right->region.dim2max <= trackBox.dim2min)))
    recSearch(current->right, trackBox, recHits);
    } 
  }
}

template<typename DATA >

void KDTreeLinkerAlgo< DATA >::recSearch ( int  current, float  dimCurrMin, float  dimCurrMax, float  dimOtherMin, float  dimOtherMax  )

private

Definition at line 151 of file KDTreeLinkerAlgo.h.

References KDTreeLinkerAlgo< DATA, DIM >::clear(), KDTreeLinkerAlgo< DATA, DIM >::clearTree(), KDTreeLinkerAlgo< DATA, DIM >::closestNeighbour, KDTreeLinkerAlgo< DATA, DIM >::KDTreeLinkerAlgo(), KDTreeLinkerAlgo< DATA, DIM >::nodePool_, KDTreeLinkerAlgo< DATA, DIM >::recSearch(), std::swap(), and KDTreeLinkerAlgo< DATA, DIM >::~KDTreeLinkerAlgo().

{
  // 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) {
    int right = nodePool_.right[current];
    if(nodePool_.isLeaf(right)) {
      float dimCurr = nodePool_.median[current];

      // 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.
      if((dimCurr >= dimCurrMin) & (dimCurr <= dimCurrMax)) {
        float dimOther = nodePool_.dimOther[current];
        if((dimOther >= dimOtherMin) & (dimOther <= dimOtherMax)) {
          closestNeighbour->push_back(nodePool_.data[current]);
        }
      }
      break;
    }
    else {
      float median = nodePool_.median[current];

      bool goLeft = (dimCurrMin <= median);
      bool goRight = (dimCurrMax >= median);

      // Swap dimension for the next search level
      std::swap(dimCurrMin, dimOtherMin);
      std::swap(dimCurrMax, dimOtherMax);
      if(goLeft & goRight) {
        int left = current+1;
        recSearch(left, dimCurrMin, dimCurrMax, dimOtherMin, dimOtherMax);
        // continue with right
        current = right;
      }
      else if(goLeft) {
        ++current;
      }
      else if(goRight) {
        current = right;
      }
      else {
        break;
      }
    }
  }
}

template<typename DATA , unsigned DIM>

void KDTreeLinkerAlgo< DATA, DIM >::recSearch ( const KDTreeNodeT< DATA, DIM > *  current, const KDTreeBoxT< DIM > &  trackBox  )

private

Definition at line 162 of file KDTreeLinkerAlgoT.h.

References KDTreeLinkerAlgo< DATA, DIM >::addSubtree(), KDTreeLinkerAlgo< DATA, DIM >::closestNeighbour, DIM, KDTreeBoxT< DIM >::dimmax, KDTreeBoxT< DIM >::dimmin, i, KDTreeNodeT< DATA, DIM >::info, KDTreeNodeT< DATA, DIM >::left, and KDTreeNodeT< DATA, DIM >::right.

Referenced by KDTreeLinkerAlgo< DATA, DIM >::recSearch(), and KDTreeLinkerAlgo< DATA, DIM >::search().

{
  /*
  // By construction, current can't be null
  assert(current != 0);

  // By Construction, a node can't have just 1 son.
  assert (!(((current->left == 0) && (current->right != 0)) ||
        ((current->left != 0) && (current->right == 0))));
  */
    
  if ((current->left == 0) && (current->right == 0)) {//leaf case
  
    // If point inside the rectangle/area
    bool isInside = true;
    for( unsigned i = 0; i < DIM; ++i ) {
      const auto thedim = current->info.dims[i];
      isInside *= thedim >= trackBox.dimmin[i] && thedim <= trackBox.dimmax[i];
    }
    if( isInside ) closestNeighbour->push_back(current->info);

  } else {

    bool isFullyContained = true;
    bool hasIntersection = true;
    //if region( v->left ) is fully contained in the rectangle
    for( unsigned i = 0; i < DIM; ++i ) {
      const auto regionmin = current->left->region.dimmin[i];
      const auto regionmax = current->left->region.dimmax[i];
      isFullyContained *= ( regionmin >= trackBox.dimmin[i] && 
                regionmax <= trackBox.dimmax[i]    );
      hasIntersection *= ( regionmin < trackBox.dimmax[i] && regionmax > trackBox.dimmin[i]);
    }
    if( isFullyContained ) {
      addSubtree(current->left);
    } else if ( hasIntersection ) {
      recSearch(current->left, trackBox); 
    }    
    // reset flags
    isFullyContained = true;
    hasIntersection = true;
    //if region( v->right ) is fully contained in the rectangle
    for( unsigned i = 0; i < DIM; ++i ) {
      const auto regionmin = current->right->region.dimmin[i];
      const auto regionmax = current->right->region.dimmax[i];
      isFullyContained *= ( regionmin >= trackBox.dimmin[i] && 
                regionmax <= trackBox.dimmax[i]    );
      hasIntersection *= ( regionmin < trackBox.dimmax[i] && regionmax > trackBox.dimmin[i]);
    }
    if( isFullyContained ) {
      addSubtree(current->right);
    } else if ( hasIntersection ) {
      recSearch(current->right, trackBox); 
    }    
  }
}

template<typename DATA, unsigned DIM = 2>

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

Definition at line 146 of file KDTreeLinkerAlgo.cc.

References KDTreeLinkerAlgo< DATA, DIM >::recSearch(), and KDTreeLinkerAlgo< DATA, DIM >::root_.

{
  if (root_)
    recSearch(root_, trackBox, recHits);
}

template<typename DATA , unsigned DIM>

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

Definition at line 149 of file KDTreeLinkerAlgoT.h.

References KDTreeLinkerAlgo< DATA, DIM >::closestNeighbour, KDTreeLinkerAlgo< DATA, DIM >::recSearch(), and KDTreeLinkerAlgo< DATA, DIM >::root_.

Referenced by HGCalImagingAlgo::calculateLocalDensity(), HGCalImagingAlgo::findAndAssignClusters(), QuadrupletSeedMerger::mergeTriplets(), KDTreeLinkerPSEcal::searchLinks(), KDTreeLinkerTrackHcal::searchLinks(), and KDTreeLinkerTrackEcal::searchLinks().

{
  if (root_) {
    closestNeighbour = &recHits;
    recSearch(root_, trackBox);
    closestNeighbour = 0;
  }
}

template<typename DATA >

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

Definition at line 138 of file KDTreeLinkerAlgo.h.

References KDTreeLinkerAlgo< DATA, DIM >::closestNeighbour, KDTreeBox::dim1max, KDTreeBox::dim1min, KDTreeBox::dim2max, KDTreeBox::dim2min, KDTreeLinkerAlgo< DATA, DIM >::empty(), and KDTreeLinkerAlgo< DATA, DIM >::recSearch().

{
  if (!empty()) {
    closestNeighbour = &recHits;
    recSearch(0, trackBox.dim1min, trackBox.dim1max, trackBox.dim2min, trackBox.dim2max);
    closestNeighbour = 0;
  }
}

template<typename DATA, unsigned DIM = 2>

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

inline

Definition at line 35 of file KDTreeLinkerAlgo.h.

References KDTreeLinkerAlgo< DATA, DIM >::clear(), and KDTreeLinkerAlgo< DATA, DIM >::nodePool_.

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

{ return nodePool_.size();}

template<typename DATA, unsigned DIM = 2>

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

inline

Definition at line 35 of file KDTreeLinkerAlgoT.h.

References KDTreeLinkerAlgo< DATA, DIM >::clear(), and KDTreeLinkerAlgo< DATA, DIM >::nodePoolPos_.

Referenced by ntuple._Collection::__iter__(), ntuple._Collection::__len__(), and KDTreeLinkerAlgo< DATA, DIM >::build().

{ return nodePoolPos_ + 1;}

template<typename DATA, unsigned DIM = 2>

void KDTreeLinkerAlgo< DATA, DIM >::swap ( KDTreeNodeInfo &  e1, KDTreeNodeInfo &  e2  )

private

Definition at line 137 of file KDTreeLinkerAlgo.cc.

References reco::e1, reco::e2, and tmp.

Referenced by KDTreeLinkerAlgo< DATA, DIM >::medianSearch().

{
  KDTreeNodeInfo tmp = e1;
  e1 = e2;
  e2 = tmp;
}

Member Data Documentation

template<typename DATA, unsigned DIM = 2>

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

private

Definition at line 44 of file KDTreeLinkerAlgo.h.

template<typename DATA, unsigned DIM = 2>

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

private

Definition at line 51 of file KDTreeLinkerAlgoT.h.

Referenced by KDTreeLinkerAlgo< DATA, DIM >::addSubtree(), KDTreeLinkerAlgo< DATA, DIM >::recSearch(), and KDTreeLinkerAlgo< DATA, DIM >::search().

template<typename DATA, unsigned DIM = 2>

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

private

Definition at line 45 of file KDTreeLinkerAlgo.h.

template<typename DATA, unsigned DIM = 2>

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

private

Definition at line 52 of file KDTreeLinkerAlgoT.h.

Referenced by KDTreeLinkerAlgo< DATA, DIM >::build(), KDTreeLinkerAlgo< DATA, DIM >::medianSearch(), and KDTreeLinkerAlgo< DATA, DIM >::recBuild().

template<typename DATA, unsigned DIM = 2>

KDTreeNode* KDTreeLinkerAlgo< DATA, DIM >::nodePool_

private

Definition at line 35 of file KDTreeLinkerAlgo.h.

template<typename DATA, unsigned DIM = 2>

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

private

Definition at line 42 of file KDTreeLinkerAlgo.h.

template<typename DATA, unsigned DIM = 2>

KDTreeNodeT<DATA,DIM>* KDTreeLinkerAlgo< DATA, DIM >::nodePool_

private

Definition at line 45 of file KDTreeLinkerAlgoT.h.

Referenced by KDTreeLinkerAlgo< DATA, DIM >::addSubtree(), KDTreeLinkerAlgo< DATA, DIM >::build(), KDTreeLinkerAlgo< DATA, DIM >::clearTree(), KDTreeLinkerAlgo< DATA, DIM >::empty(), KDTreeLinkerAlgo< DATA, DIM >::getNextNode(), KDTreeLinkerAlgo< DATA, DIM >::recBuild(), KDTreeLinkerAlgo< DATA, DIM >::recSearch(), and KDTreeLinkerAlgo< DATA, DIM >::size().

template<typename DATA, unsigned DIM = 2>

int KDTreeLinkerAlgo< DATA, DIM >::nodePoolPos_

private

Definition at line 47 of file KDTreeLinkerAlgoT.h.

Referenced by KDTreeLinkerAlgo< DATA, DIM >::addSubtree(), KDTreeLinkerAlgo< DATA, DIM >::clearTree(), KDTreeLinkerAlgo< DATA, DIM >::empty(), KDTreeLinkerAlgo< DATA, DIM >::getNextNode(), and KDTreeLinkerAlgo< DATA, DIM >::size().

template<typename DATA, unsigned DIM = 2>

int KDTreeLinkerAlgo< DATA, DIM >::nodePoolSize_

private

Definition at line 46 of file KDTreeLinkerAlgoT.h.

Referenced by KDTreeLinkerAlgo< DATA, DIM >::addSubtree(), KDTreeLinkerAlgo< DATA, DIM >::build(), and KDTreeLinkerAlgo< DATA, DIM >::clearTree().

template<typename DATA, unsigned DIM = 2>

KDTreeNode* KDTreeLinkerAlgo< DATA, DIM >::root_

private

Definition at line 32 of file KDTreeLinkerAlgo.h.

template<typename DATA, unsigned DIM = 2>

KDTreeNodeT<DATA,DIM>* KDTreeLinkerAlgo< DATA, DIM >::root_

private

Definition at line 42 of file KDTreeLinkerAlgoT.h.

Referenced by KDTreeLinkerAlgo< DATA, DIM >::addSubtree(), KDTreeLinkerAlgo< DATA, DIM >::build(), KDTreeLinkerAlgo< DATA, DIM >::clear(), KDTreeLinkerAlgo< DATA, DIM >::clearTree(), and KDTreeLinkerAlgo< DATA, DIM >::search().