#include <KDTreeLinkerAlgo.h>

Public Member Functions
void	build (std::vector< KDTreeNodeInfo > &eltList, const KDTreeBox &region)

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

void	clear ()

void	clear ()

bool	empty ()

	KDTreeLinkerAlgo ()

	KDTreeLinkerAlgo ()

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

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

int	size ()

	~KDTreeLinkerAlgo ()

	~KDTreeLinkerAlgo ()

Private Member Functions
void	addSubtree (const KDTreeNode *current, std::vector< KDTreeNodeInfo > &recHits)

void	clearTree ()

void	clearTree ()

KDTreeNode *	getNextNode ()

int	medianSearch (std::vector< KDTreeNodeInfo > &eltList, 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)

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	swap (KDTreeNodeInfo &e1, KDTreeNodeInfo &e2)

Private Attributes
std::vector< DATA > *	closestNeighbour

std::vector< KDTreeNodeInfo < DATA > > *	initialEltList

KDTreeNode *	nodePool_

KDTreeNodes< DATA >	nodePool_

int	nodePoolPos_

int	nodePoolSize_

KDTreeNode *	root_

Detailed Description

template<typename DATA>
class KDTreeLinkerAlgo< DATA >

Definition at line 10 of file KDTreeLinkerAlgo.h.

Constructor & Destructor Documentation

template<typename DATA >

KDTreeLinkerAlgo< DATA >::KDTreeLinkerAlgo ( )

Definition at line 3 of file KDTreeLinkerAlgo.cc.

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

template<typename DATA >

KDTreeLinkerAlgo< DATA >::~KDTreeLinkerAlgo ( )

Definition at line 11 of file KDTreeLinkerAlgo.cc.

References KDTreeLinkerAlgo< DATA >::clear().

 {
   clear();
 }

template<typename DATA>

KDTreeLinkerAlgo< DATA >::KDTreeLinkerAlgo ( )

template<typename DATA>

KDTreeLinkerAlgo< DATA >::~KDTreeLinkerAlgo ( )

Member Function Documentation

template<typename DATA>

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

private

Definition at line 209 of file KDTreeLinkerAlgo.cc.

References KDTreeNode::left, KDTreeNode::rh, and KDTreeNode::right.

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

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

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

Definition at line 17 of file KDTreeLinkerAlgo.cc.

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

Referenced by KDTreeLinkerTrackEcal::buildTree(), KDTreeLinkerTrackHcal::buildTree(), KDTreeLinkerPSEcal::buildTree(), MultiHitGeneratorFromChi2::hitSets(), PixelTripletLargeTipGenerator::hitTriplets(), PixelTripletHLTGenerator::hitTriplets(), and QuadrupletSeedMerger::mergeTriplets().

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

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

template<typename DATA >

void KDTreeLinkerAlgo< DATA >::clear ( void )

Definition at line 235 of file KDTreeLinkerAlgo.cc.

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

Referenced by KDTreeLinkerPSEcal::clear(), KDTreeLinkerTrackEcal::clear(), KDTreeLinkerTrackHcal::clear(), and KDTreeLinkerAlgo< DATA >::~KDTreeLinkerAlgo().

 {
   if (root_)
     clearTree();
 }

template<typename DATA>

void KDTreeLinkerAlgo< DATA >::clear ( )

template<typename DATA>

void KDTreeLinkerAlgo< DATA >::clearTree ( )

private

template<typename DATA >

void KDTreeLinkerAlgo< DATA >::clearTree ( )

private

Definition at line 225 of file KDTreeLinkerAlgo.cc.

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

Referenced by KDTreeLinkerAlgo< DATA >::clear().

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

template<typename DATA>

bool KDTreeLinkerAlgo< DATA >::empty ( void )

inline

Definition at line 31 of file KDTreeLinkerAlgo.h.

References KDTreeLinkerAlgo< DATA >::nodePool_.

31 {return nodePool_.empty();}

KDTreeLinkerAlgo::nodePool_

KDTreeNode * nodePool_

Definition: KDTreeLinkerAlgo.h:35

template<typename DATA>

KDTreeNode * KDTreeLinkerAlgo< DATA >::getNextNode ( )

private

Definition at line 243 of file KDTreeLinkerAlgo.cc.

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

Referenced by KDTreeLinkerAlgo< DATA >::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>

int KDTreeLinkerAlgo< DATA >::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, ConfigFiles::l, m, and KDTreeLinkerAlgo< DATA >::swap().

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

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

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

private

Definition at line 93 of file KDTreeLinkerAlgo.h.

References KDTreeNodeInfo< DATA >::dim, i, j, ConfigFiles::l, m, 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> elt = (*initialEltList)[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 ((*initialEltList)[i].dim[1] < elt.dim[1]) i++;
     while ((*initialEltList)[j].dim[1] > elt.dim[1]) j--;
       } else {
     while ((*initialEltList)[i].dim[0] < elt.dim[0]) i++;
     while ((*initialEltList)[j].dim[0] > elt.dim[0]) 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>

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

private

Definition at line 31 of file KDTreeLinkerAlgo.cc.

References KDTreeBox::dim1max, KDTreeBox::dim1min, KDTreeBox::dim2max, KDTreeBox::dim2min, KDTreeLinkerAlgo< DATA >::getNextNode(), python.Node::leaf, KDTreeNode::left, KDTreeLinkerAlgo< DATA >::medianSearch(), python.Node::node, KDTreeNode::right, and KDTreeNode::setAttributs().

Referenced by KDTreeLinkerAlgo< DATA >::build().

 {
   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, KDTreeNodeInfo< DATA >::dim, info(), and python.Node::leaf.

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

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

private

Definition at line 151 of file KDTreeLinkerAlgo.h.

References cond::rpcobimon::current, and std::swap().

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

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

private

Definition at line 154 of file KDTreeLinkerAlgo.cc.

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

Referenced by KDTreeLinkerAlgo< DATA >::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
     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 >::search	(	const KDTreeBox &	searchBox,
		std::vector< KDTreeNodeInfo > &	resRecHitList
	)

Definition at line 146 of file KDTreeLinkerAlgo.cc.

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

Referenced by MultiHitGeneratorFromChi2::hitSets(), PixelTripletLargeTipGenerator::hitTriplets(), PixelTripletHLTGenerator::hitTriplets(), QuadrupletSeedMerger::mergeTriplets(), KDTreeLinkerPSEcal::searchLinks(), KDTreeLinkerTrackHcal::searchLinks(), and KDTreeLinkerTrackEcal::searchLinks().

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

template<typename DATA >

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

Definition at line 138 of file KDTreeLinkerAlgo.h.

References KDTreeBox::dim1max, KDTreeBox::dim1min, KDTreeBox::dim2max, KDTreeBox::dim2min, and relativeConstraints::empty.

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

template<typename DATA>

int KDTreeLinkerAlgo< DATA >::size ( void )

inline

Definition at line 35 of file KDTreeLinkerAlgo.h.

References KDTreeLinkerAlgo< DATA >::nodePool_.

35 { return nodePool_.size();}

KDTreeLinkerAlgo::nodePool_

KDTreeNode * nodePool_

Definition: KDTreeLinkerAlgo.h:35

template<typename DATA>

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

private

Definition at line 137 of file KDTreeLinkerAlgo.cc.

References tmp.

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

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

Member Data Documentation

template<typename DATA>

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

private

Definition at line 44 of file KDTreeLinkerAlgo.h.

template<typename DATA>

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

private

Definition at line 45 of file KDTreeLinkerAlgo.h.

template<typename DATA>

KDTreeNode* KDTreeLinkerAlgo< DATA >::nodePool_

private

Definition at line 35 of file KDTreeLinkerAlgo.h.

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

template<typename DATA>

KDTreeNodes<DATA> KDTreeLinkerAlgo< DATA >::nodePool_

private

Definition at line 42 of file KDTreeLinkerAlgo.h.

template<typename DATA>

int KDTreeLinkerAlgo< DATA >::nodePoolPos_

private

Definition at line 37 of file KDTreeLinkerAlgo.h.

Referenced by KDTreeLinkerAlgo< DATA >::clearTree(), and KDTreeLinkerAlgo< DATA >::getNextNode().

template<typename DATA>

int KDTreeLinkerAlgo< DATA >::nodePoolSize_

private

Definition at line 36 of file KDTreeLinkerAlgo.h.

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

template<typename DATA>

KDTreeNode* KDTreeLinkerAlgo< DATA >::root_

private

Definition at line 32 of file KDTreeLinkerAlgo.h.

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

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<typename DATA> class KDTreeLinkerAlgo< DATA >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename DATA>
class KDTreeLinkerAlgo< DATA >