|
|
|
#include <KDTreeLinkerAlgo.h>
Public Member Functions | |
| void | build (std::vector< KDTreeNodeInfo > &eltList, const KDTreeBox ®ion) |
| void | build (std::vector< KDTreeNodeInfo< DATA > > &eltList, const KDTreeBox ®ion) |
| void | clear () |
| void | clear () |
| bool | empty () |
| KDTreeLinkerAlgo () | |
| KDTreeLinkerAlgo () | |
| void | search (const KDTreeBox &searchBox, std::vector< KDTreeNodeInfo< DATA > > &resRecHitList) |
| void | search (const KDTreeBox &searchBox, std::vector< KDTreeNodeInfo > &resRecHitList) |
| int | size () |
| ~KDTreeLinkerAlgo () | |
| ~KDTreeLinkerAlgo () | |
Private Member Functions | |
| void | addSubtree (const KDTreeNode *current, std::vector< KDTreeNodeInfo > &recHits) |
| void | addSubtree (const KDTreeNode< DATA > *current) |
| void | clearTree () |
| void | clearTree () |
| KDTreeNode< DATA > * | getNextNode () |
| KDTreeNode * | getNextNode () |
| int | medianSearch (int low, int high, int treeDepth) |
| 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 ®ion) |
| KDTreeNode< DATA > * | recBuild (int low, int hight, int depth, const KDTreeBox ®ion) |
| void | recSearch (const KDTreeNode *current, const KDTreeBox &trackBox, std::vector< KDTreeNodeInfo > &recHits) |
| void | recSearch (const KDTreeNode< DATA > *current, const KDTreeBox &trackBox) |
| void | swap (KDTreeNodeInfo &e1, KDTreeNodeInfo &e2) |
| void | swap (KDTreeNodeInfo< DATA > &e1, KDTreeNodeInfo< DATA > &e2) |
Private Attributes | |
| std::vector< KDTreeNodeInfo < DATA > > * | closestNeighbour |
| std::vector< KDTreeNodeInfo < DATA > > * | initialEltList |
| KDTreeNode< DATA > * | nodePool_ |
| KDTreeNode * | nodePool_ |
| int | nodePoolPos_ |
| int | nodePoolSize_ |
| KDTreeNode * | root_ |
| KDTreeNode< DATA > * | root_ |
Definition at line 10 of file KDTreeLinkerAlgo.h.
| KDTreeLinkerAlgo< DATA >::KDTreeLinkerAlgo | ( | ) |
Definition at line 3 of file KDTreeLinkerAlgo.cc.
: root_ (0), nodePool_(0), nodePoolSize_(-1), nodePoolPos_(-1) { }
| KDTreeLinkerAlgo< DATA >::~KDTreeLinkerAlgo | ( | ) |
Definition at line 11 of file KDTreeLinkerAlgo.cc.
References KDTreeLinkerAlgo< DATA >::clear().
{
clear();
}
| KDTreeLinkerAlgo< DATA >::KDTreeLinkerAlgo | ( | ) |
| KDTreeLinkerAlgo< DATA >::~KDTreeLinkerAlgo | ( | ) |
| void KDTreeLinkerAlgo< DATA >::addSubtree | ( | const KDTreeNode * | current, |
| std::vector< KDTreeNodeInfo > & | recHits | ||
| ) | [private] |
Definition at line 209 of file KDTreeLinkerAlgo.cc.
References KDTreeNode< DATA >::left, KDTreeNode< DATA >::rh, and KDTreeNode< DATA >::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);
}
}
| void KDTreeLinkerAlgo< DATA >::addSubtree | ( | const KDTreeNode< DATA > * | current | ) | [private] |
Definition at line 232 of file KDTreeLinkerAlgo.h.
References KDTreeNode< DATA >::info, KDTreeNode< DATA >::left, and KDTreeNode< DATA >::right.
{
// 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);
}
}
| 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 KDTreeLinkerTrackHcal::buildTree(), KDTreeLinkerPSEcal::buildTree(), and KDTreeLinkerTrackEcal::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< DATA >::build | ( | std::vector< KDTreeNodeInfo< DATA > > & | eltList, |
| const KDTreeBox & | region | ||
| ) |
Definition at line 86 of file KDTreeLinkerAlgo.h.
References sistrip::root_, and findQualityFiles::size.
{
if (eltList.size()) {
initialEltList = &eltList;
size_t size = initialEltList->size();
nodePoolSize_ = size * 2 - 1;
nodePool_ = new KDTreeNode<DATA>[nodePoolSize_];
// Here we build the KDTree
root_ = recBuild(0, size, 0, region);
initialEltList = 0;
}
}
| 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(), KDTreeLinkerTrackHcal::clear(), KDTreeLinkerTrackEcal::clear(), and KDTreeLinkerAlgo< DATA >::~KDTreeLinkerAlgo().
| void KDTreeLinkerAlgo< DATA >::clear | ( | ) |
| void KDTreeLinkerAlgo< DATA >::clearTree | ( | ) | [private] |
| 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;
}
| bool KDTreeLinkerAlgo< DATA >::empty | ( | void | ) | [inline] |
Definition at line 32 of file KDTreeLinkerAlgo.h.
References KDTreeLinkerAlgo< DATA >::nodePoolPos_.
{ return nodePoolPos_ + 1;}
| KDTreeNode< DATA > * 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_]);
}
| KDTreeNode<DATA>* KDTreeLinkerAlgo< DATA >::getNextNode | ( | ) | [private] |
| int KDTreeLinkerAlgo< DATA >::medianSearch | ( | int | low, |
| int | high, | ||
| int | treeDepth | ||
| ) | [private] |
Definition at line 106 of file KDTreeLinkerAlgo.h.
References KDTreeNodeInfo< DATA >::dim1, KDTreeNodeInfo< DATA >::dim2, i, j, prof2calltree::l, m, and 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<DATA> elt = initialEltList->at(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->at(i).dim2 < elt.dim2) i++;
while (initialEltList->at(j).dim2 > elt.dim2) j--;
} else {
while (initialEltList->at(i).dim1 < elt.dim1) i++;
while (initialEltList->at(j).dim1 > elt.dim1) j--;
}
if (i <= j){
swap(initialEltList->at(i), initialEltList->at(j));
i++;
j--;
}
} while (i <= j);
if (j < median) l = i;
if (i > median) m = j;
}
return median;
}
| 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, prof2calltree::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;
}
| 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< DATA >::left, KDTreeLinkerAlgo< DATA >::medianSearch(), python::Node::node, KDTreeNode< DATA >::right, and KDTreeNode< DATA >::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;
}
}
| KDTreeNode< DATA > * KDTreeLinkerAlgo< DATA >::recBuild | ( | int | low, |
| int | hight, | ||
| int | depth, | ||
| const KDTreeBox & | region | ||
| ) | [private] |
Definition at line 300 of file KDTreeLinkerAlgo.h.
References KDTreeBox::dim1max, KDTreeBox::dim1min, KDTreeBox::dim2max, KDTreeBox::dim2min, python::Node::leaf, KDTreeNode< DATA >::left, python::Node::node, KDTreeNode< DATA >::right, and KDTreeNode< DATA >::setAttributs().
{
int portionSize = high - low;
// By construction, portionSize > 0 can't happend.
assert(portionSize > 0);
if (portionSize == 1) { // Leaf case
KDTreeNode<DATA> *leaf = getNextNode();
leaf->setAttributs(region, initialEltList->at(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
KDTreeNode<DATA> *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 = initialEltList->at(medianId).dim2;
leftRegion.dim2max = medianVal;
rightRegion.dim2min = medianVal;
} else {
double medianVal = initialEltList->at(medianId).dim1;
leftRegion.dim1max = medianVal;
rightRegion.dim1min = 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;
}
}
| 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< DATA >::left, KDTreeNode< DATA >::region, KDTreeNode< DATA >::rh, and KDTreeNode< DATA >::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);
}
}
}
| void KDTreeLinkerAlgo< DATA >::recSearch | ( | const KDTreeNode< DATA > * | current, |
| const KDTreeBox & | trackBox | ||
| ) | [private] |
Definition at line 177 of file KDTreeLinkerAlgo.h.
References KDTreeBox::dim1max, KDTreeBox::dim1min, KDTreeBox::dim2max, KDTreeBox::dim2min, KDTreeNode< DATA >::info, KDTreeNode< DATA >::left, KDTreeNode< DATA >::region, and KDTreeNode< DATA >::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->info.dim1 >= trackBox.dim1min) && (current->info.dim1 <= trackBox.dim1max) &&
(current->info.dim2 >= trackBox.dim2min) && (current->info.dim2 <= trackBox.dim2max))
closestNeighbour->push_back(current->info);
} 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);
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);
}
//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);
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);
}
}
}
| void KDTreeLinkerAlgo< DATA >::search | ( | const KDTreeBox & | searchBox, |
| std::vector< KDTreeNodeInfo< DATA > > & | resRecHitList | ||
| ) |
Definition at line 164 of file KDTreeLinkerAlgo.h.
References sistrip::root_.
{
if (root_) {
closestNeighbour = &recHits;
recSearch(root_, trackBox);
closestNeighbour = 0;
}
}
| 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 KDTreeLinkerTrackHcal::searchLinks(), KDTreeLinkerTrackEcal::searchLinks(), and KDTreeLinkerPSEcal::searchLinks().
| int KDTreeLinkerAlgo< DATA >::size | ( | void | ) | [inline] |
Definition at line 36 of file KDTreeLinkerAlgo.h.
:
// The KDTree root
| void KDTreeLinkerAlgo< DATA >::swap | ( | KDTreeNodeInfo< DATA > & | e1, |
| KDTreeNodeInfo< DATA > & | e2 | ||
| ) | [private] |
| 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;
}
std::vector<KDTreeNodeInfo<DATA> >* KDTreeLinkerAlgo< DATA >::closestNeighbour [private] |
Definition at line 50 of file KDTreeLinkerAlgo.h.
std::vector<KDTreeNodeInfo<DATA> >* KDTreeLinkerAlgo< DATA >::initialEltList [private] |
Definition at line 51 of file KDTreeLinkerAlgo.h.
KDTreeNode<DATA>* KDTreeLinkerAlgo< DATA >::nodePool_ [private] |
Definition at line 46 of file KDTreeLinkerAlgo.h.
KDTreeNode* KDTreeLinkerAlgo< DATA >::nodePool_ [private] |
Definition at line 35 of file KDTreeLinkerAlgo.h.
Referenced by KDTreeLinkerAlgo< DATA >::build(), KDTreeLinkerAlgo< DATA >::clearTree(), and KDTreeLinkerAlgo< DATA >::getNextNode().
int KDTreeLinkerAlgo< DATA >::nodePoolPos_ [private] |
Definition at line 37 of file KDTreeLinkerAlgo.h.
Referenced by KDTreeLinkerAlgo< DATA >::clearTree(), KDTreeLinkerAlgo< DATA >::empty(), and KDTreeLinkerAlgo< DATA >::getNextNode().
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().
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().
KDTreeNode<DATA>* KDTreeLinkerAlgo< DATA >::root_ [private] |
Definition at line 43 of file KDTreeLinkerAlgo.h.
1.7.3