KDTreeLinkerAlgo Class Reference

#include <KDTreeLinkerAlgo.h>

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

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

Private Attributes
KDTreeNode *	nodePool_
int	nodePoolPos_
int	nodePoolSize_
KDTreeNode *	root_

Detailed Description

Definition at line 10 of file KDTreeLinkerAlgo.h.

Constructor & Destructor Documentation

KDTreeLinkerAlgo::KDTreeLinkerAlgo

(

)

Definition at line 3 of file KDTreeLinkerAlgo.cc.

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

KDTreeLinkerAlgo::~KDTreeLinkerAlgo

(

)

Definition at line 11 of file KDTreeLinkerAlgo.cc.

References clear().

{
  clear();
}

Member Function Documentation

void KDTreeLinkerAlgo::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 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);
  }
}

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

Definition at line 17 of file KDTreeLinkerAlgo.cc.

References nodePool_, nodePoolSize_, recBuild(), and root_.

Referenced by KDTreeLinkerTrackEcal::buildTree(), KDTreeLinkerTrackHcal::buildTree(), and KDTreeLinkerPSEcal::buildTree().

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

void KDTreeLinkerAlgo::clear

(

void

)

Definition at line 235 of file KDTreeLinkerAlgo.cc.

References clearTree(), and root_.

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

{
  if (root_)
    clearTree();
}

void KDTreeLinkerAlgo::clearTree ( )

private

Definition at line 225 of file KDTreeLinkerAlgo.cc.

References nodePool_, nodePoolPos_, nodePoolSize_, and root_.

Referenced by clear().

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

KDTreeNode * KDTreeLinkerAlgo::getNextNode ( )

private

Definition at line 243 of file KDTreeLinkerAlgo.cc.

References nodePool_, nodePoolPos_, and nodePoolSize_.

Referenced by 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_]);
}

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

private

Definition at line 90 of file KDTreeLinkerAlgo.cc.

References KDTreeNodeInfo::dim1, KDTreeNodeInfo::dim2, i, j, prof2calltree::l, m, and swap().

Referenced by 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;
}

KDTreeNode * KDTreeLinkerAlgo::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, getNextNode(), python.Node::leaf, KDTreeNode::left, medianSearch(), python.Node::node, KDTreeNode::right, and KDTreeNode::setAttributs().

Referenced by 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;
  }
}

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

private

Definition at line 154 of file KDTreeLinkerAlgo.cc.

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

Referenced by 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);
    } 
  }
}

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

Definition at line 146 of file KDTreeLinkerAlgo.cc.

References recSearch(), and root_.

Referenced by KDTreeLinkerPSEcal::searchLinks(), KDTreeLinkerTrackHcal::searchLinks(), and KDTreeLinkerTrackEcal::searchLinks().

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

void KDTreeLinkerAlgo::swap ( KDTreeNodeInfo &  e1, KDTreeNodeInfo &  e2  )

private

Definition at line 137 of file KDTreeLinkerAlgo.cc.

References tmp.

Referenced by medianSearch().

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

Member Data Documentation

KDTreeNode* KDTreeLinkerAlgo::nodePool_

private

Definition at line 35 of file KDTreeLinkerAlgo.h.

Referenced by build(), clearTree(), and getNextNode().

int KDTreeLinkerAlgo::nodePoolPos_

private

Definition at line 37 of file KDTreeLinkerAlgo.h.

Referenced by clearTree(), and getNextNode().

int KDTreeLinkerAlgo::nodePoolSize_

private

Definition at line 36 of file KDTreeLinkerAlgo.h.

Referenced by build(), clearTree(), and getNextNode().

KDTreeNode* KDTreeLinkerAlgo::root_

private

Definition at line 32 of file KDTreeLinkerAlgo.h.

Referenced by build(), clear(), clearTree(), and search().