CMS 3D CMS Logo
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Pages
List of all members | Public Member Functions | Private Member Functions | Private Attributes
KDTreeLinkerAlgo< DATA > Class Template Reference

#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.

4  : root_ (0),
5  nodePool_(0),
6  nodePoolSize_(-1),
7  nodePoolPos_(-1)
8 {
9 }
KDTreeLinkerAlgo::nodePool_
KDTreeNode * nodePool_
Definition: KDTreeLinkerAlgo.h:35
KDTreeLinkerAlgo::root_
KDTreeNode * root_
Definition: KDTreeLinkerAlgo.h:32
template<typename DATA >
KDTreeLinkerAlgo< DATA >::~KDTreeLinkerAlgo ( )

Definition at line 11 of file KDTreeLinkerAlgo.cc.

References KDTreeLinkerAlgo< DATA >::clear().

12 {
13  clear();
14 }
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 assert(), KDTreeNode::left, KDTreeNode::rh, and KDTreeNode::right.

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

211 {
212  // By construction, current can't be null
213  assert(current != 0);
214 
215  if ((current->left == 0) && (current->right == 0)) // leaf
216  recHits.push_back(current->rh);
217  else { // node
218  addSubtree(current->left, recHits);
219  addSubtree(current->right, recHits);
220  }
221 }
assert
assert(m_qm.get())
KDTreeLinkerAlgo::addSubtree
void addSubtree(const KDTreeNode *current, std::vector< KDTreeNodeInfo > &recHits)
Definition: KDTreeLinkerAlgo.cc:209
KDTreeNode::right
KDTreeNode * right
Definition: KDTreeLinkerTools.h:70
KDTreeNode::left
KDTreeNode * left
Definition: KDTreeLinkerTools.h:70
KDTreeNode::rh
KDTreeNodeInfo rh
Definition: KDTreeLinkerTools.h:67
HLT_50nsGRun_cff.recHits
tuple recHits
Definition: HLT_50nsGRun_cff.py:48207
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(), HLT_50nsGRun_cff::region, and KDTreeLinkerAlgo< DATA >::root_.

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

19 {
20  if (eltList.size()) {
21  nodePoolSize_ = eltList.size() * 2 - 1;
22  nodePool_ = new KDTreeNode[nodePoolSize_];
23 
24  // Here we build the KDTree
25  root_ = recBuild(eltList, 0, eltList.size(), 0, region);
26  }
27 }
KDTreeLinkerAlgo::recBuild
KDTreeNode * recBuild(std::vector< KDTreeNodeInfo > &eltList, int low, int hight, int depth, const KDTreeBox &region)
Definition: KDTreeLinkerAlgo.cc:31
HLT_50nsGRun_cff.region
tuple region
Definition: HLT_50nsGRun_cff.py:48209
KDTreeLinkerAlgo::nodePool_
KDTreeNode * nodePool_
Definition: KDTreeLinkerAlgo.h:35
KDTreeLinkerAlgo::root_
KDTreeNode * root_
Definition: KDTreeLinkerAlgo.h:32
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().

236 {
237  if (root_)
238  clearTree();
239 }
KDTreeLinkerAlgo::root_
KDTreeNode * root_
Definition: KDTreeLinkerAlgo.h:32
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().

226 {
227  delete[] nodePool_;
228  nodePool_ = 0;
229  root_ = 0;
230  nodePoolSize_ = -1;
231  nodePoolPos_ = -1;
232 }
KDTreeLinkerAlgo::nodePool_
KDTreeNode * nodePool_
Definition: KDTreeLinkerAlgo.h:35
KDTreeLinkerAlgo::root_
KDTreeNode * root_
Definition: KDTreeLinkerAlgo.h:32
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 assert(), KDTreeLinkerAlgo< DATA >::nodePool_, KDTreeLinkerAlgo< DATA >::nodePoolPos_, and KDTreeLinkerAlgo< DATA >::nodePoolSize_.

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

244 {
245  ++nodePoolPos_;
246 
247  // The tree size is exactly 2 * nbrElts - 1 and this is the total allocated memory.
248  // If we have used more than that....there is a big problem.
249  assert(nodePoolPos_ < nodePoolSize_);
250 
251  return &(nodePool_[nodePoolPos_]);
252 }
assert
assert(m_qm.get())
KDTreeLinkerAlgo::nodePool_
KDTreeNode * nodePool_
Definition: KDTreeLinkerAlgo.h:35
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 assert(), KDTreeNodeInfo< DATA >::dim1, KDTreeNodeInfo< DATA >::dim2, i, j, prof2calltree::l, contentValuesFiles::m, and KDTreeLinkerAlgo< DATA >::swap().

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

94 {
95  //We should have at least 1 element to calculate the median...
96  assert(low < high);
97 
98  int nbrElts = high - low;
99  int median = (nbrElts & 1) ? nbrElts / 2
100  : nbrElts / 2 - 1;
101  median += low;
102 
103  int l = low;
104  int m = high - 1;
105 
106  while (l < m) {
107  KDTreeNodeInfo elt = eltList[median];
108  int i = l;
109  int j = m;
110 
111  do {
112 
113  // The even depth is associated to dim1 dimension
114  // The odd one to dim2 dimension
115  if (treeDepth & 1) {
116  while (eltList[i].dim2 < elt.dim2) i++;
117  while (eltList[j].dim2 > elt.dim2) j--;
118  } else {
119  while (eltList[i].dim1 < elt.dim1) i++;
120  while (eltList[j].dim1 > elt.dim1) j--;
121  }
122 
123  if (i <= j){
124  swap(eltList[i], eltList[j]);
125  i++;
126  j--;
127  }
128  } while (i <= j);
129  if (j < median) l = i;
130  if (i > median) m = j;
131  }
132 
133  return median;
134 }
i
int i
Definition: DBlmapReader.cc:9
assert
assert(m_qm.get())
j
int j
Definition: DBlmapReader.cc:9
KDTreeLinkerAlgo::swap
void swap(KDTreeNodeInfo &e1, KDTreeNodeInfo &e2)
Definition: KDTreeLinkerAlgo.cc:137
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, prof2calltree::l, contentValuesFiles::m, and std::swap().

96 {
97  int nbrElts = high - low;
98  int median = (nbrElts & 1) ? nbrElts / 2
99  : nbrElts / 2 - 1;
100  median += low;
101 
102  int l = low;
103  int m = high - 1;
104 
105  while (l < m) {
106  KDTreeNodeInfo<DATA> elt = (*initialEltList)[median];
107  int i = l;
108  int j = m;
109 
110  do {
111  // The even depth is associated to dim1 dimension
112  // The odd one to dim2 dimension
113  if (treeDepth & 1) {
114  while ((*initialEltList)[i].dim[1] < elt.dim[1]) i++;
115  while ((*initialEltList)[j].dim[1] > elt.dim[1]) j--;
116  } else {
117  while ((*initialEltList)[i].dim[0] < elt.dim[0]) i++;
118  while ((*initialEltList)[j].dim[0] > elt.dim[0]) j--;
119  }
120 
121  if (i <= j){
122  std::swap((*initialEltList)[i], (*initialEltList)[j]);
123  i++;
124  j--;
125  }
126  } while (i <= j);
127  if (j < median) l = i;
128  if (i > median) m = j;
129  }
130 
131  return median;
132 }
i
int i
Definition: DBlmapReader.cc:9
KDTreeLinkerAlgo::initialEltList
std::vector< KDTreeNodeInfo< DATA > > * initialEltList
Definition: KDTreeLinkerAlgo.h:45
std::swap
void swap(edm::DataFrameContainer &lhs, edm::DataFrameContainer &rhs)
Definition: DataFrameContainer.h:223
j
int j
Definition: DBlmapReader.cc:9
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 assert(), HLT_25ns14e33_v1_cff::depth, KDTreeBox::dim1max, KDTreeBox::dim1min, KDTreeBox::dim2max, KDTreeBox::dim2min, KDTreeLinkerAlgo< DATA >::getNextNode(), python.Node::leaf, KDTreeNode::left, KDTreeLinkerAlgo< DATA >::medianSearch(), python.Node::node, HLT_50nsGRun_cff::region, KDTreeNode::right, and KDTreeNode::setAttributs().

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

36 {
37  int portionSize = high - low;
38 
39  // By construction, portionSize > 0 can't happend.
40  assert(portionSize > 0);
41 
42  if (portionSize == 1) { // Leaf case
43 
44  KDTreeNode *leaf = getNextNode();
45  leaf->setAttributs(region, eltList[low]);
46  return leaf;
47 
48  } else { // Node case
49 
50  // The even depth is associated to dim1 dimension
51  // The odd one to dim2 dimension
52  int medianId = medianSearch(eltList, low, high, depth);
53 
54  // We create the node
55  KDTreeNode *node = getNextNode();
56  node->setAttributs(region);
57 
58 
59  // Here we split into 2 halfplanes the current plane
60  KDTreeBox leftRegion = region;
61  KDTreeBox rightRegion = region;
62  if (depth & 1) {
63 
64  double medianVal = eltList[medianId].dim2;
65  leftRegion.dim2max = medianVal;
66  rightRegion.dim2min = medianVal;
67 
68  } else {
69 
70  double medianVal = eltList[medianId].dim1;
71  leftRegion.dim1max = medianVal;
72  rightRegion.dim1min = medianVal;
73 
74  }
75 
76  ++depth;
77  ++medianId;
78 
79  // We recursively build the son nodes
80  node->left = recBuild(eltList, low, medianId, depth, leftRegion);
81  node->right = recBuild(eltList, medianId, high, depth, rightRegion);
82 
83  return node;
84  }
85 }
KDTreeNode::setAttributs
void setAttributs(const KDTreeBox &regionBox, const KDTreeNodeInfo &rhinfo)
Definition: KDTreeLinkerTools.h:80
assert
assert(m_qm.get())
KDTreeLinkerAlgo::medianSearch
int medianSearch(std::vector< KDTreeNodeInfo > &eltList, int low, int high, int treeDepth)
Definition: KDTreeLinkerAlgo.cc:90
python.Node.node
tuple node
Definition: Node.py:50
python.Node.leaf
tuple leaf
Definition: Node.py:62
KDTreeLinkerAlgo::recBuild
KDTreeNode * recBuild(std::vector< KDTreeNodeInfo > &eltList, int low, int hight, int depth, const KDTreeBox &region)
Definition: KDTreeLinkerAlgo.cc:31
KDTreeNode::right
KDTreeNode * right
Definition: KDTreeLinkerTools.h:70
KDTreeNode::left
KDTreeNode * left
Definition: KDTreeLinkerTools.h:70
HLT_50nsGRun_cff.region
tuple region
Definition: HLT_50nsGRun_cff.py:48209
HLT_25ns14e33_v1_cff.depth
tuple depth
Definition: HLT_25ns14e33_v1_cff.py:6940
KDTreeLinkerAlgo::getNextNode
KDTreeNode * getNextNode()
Definition: KDTreeLinkerAlgo.cc:243
template<typename DATA >
int KDTreeLinkerAlgo< DATA >::recBuild ( int  low,
int  hight,
int  depth 
)
private

Definition at line 234 of file KDTreeLinkerAlgo.h.

References assert(), KDTreeNodeInfo< DATA >::data, HLT_25ns14e33_v1_cff::depth, KDTreeNodeInfo< DATA >::dim, info(), and python.Node::leaf.

237 {
238  int portionSize = high - low;
239  int dimIndex = depth&1;
240 
241  if (portionSize == 1) { // Leaf case
242  int leaf = nodePool_.getNextNode();
243  const KDTreeNodeInfo<DATA>& info = (*initialEltList)[low];
244  nodePool_.right[leaf] = 0;
245  nodePool_.median[leaf] = info.dim[dimIndex]; // dimCurrent
246  nodePool_.dimOther[leaf] = info.dim[1-dimIndex];
247  nodePool_.data[leaf] = info.data;
248  return leaf;
249 
250  } else { // Node case
251 
252  // The even depth is associated to dim1 dimension
253  // The odd one to dim2 dimension
254  int medianId = medianSearch(low, high, depth);
255  float medianVal = (*initialEltList)[medianId].dim[dimIndex];
256 
257  // We create the node
258  int nodeInd = nodePool_.getNextNode();
259  nodePool_.median[nodeInd] = medianVal;
260 
261  ++depth;
262  ++medianId;
263 
264  // We recursively build the son nodes
265  int left = recBuild(low, medianId, depth);
266  assert(nodeInd+1 == left);
267  nodePool_.right[nodeInd] = recBuild(medianId, high, depth);
268 
269  return nodeInd;
270  }
271 }
info
static const TGPicture * info(bool iBackgroundIsBlack)
Definition: FWCollectionSummaryWidget.cc:170
assert
assert(m_qm.get())
KDTreeLinkerAlgo::medianSearch
int medianSearch(std::vector< KDTreeNodeInfo > &eltList, int low, int high, int treeDepth)
Definition: KDTreeLinkerAlgo.cc:90
python.Node.leaf
tuple leaf
Definition: Node.py:62
KDTreeLinkerAlgo::recBuild
KDTreeNode * recBuild(std::vector< KDTreeNodeInfo > &eltList, int low, int hight, int depth, const KDTreeBox &region)
Definition: KDTreeLinkerAlgo.cc:31
KDTreeNode::right
KDTreeNode * right
Definition: KDTreeLinkerTools.h:70
HLT_25ns14e33_v1_cff.depth
tuple depth
Definition: HLT_25ns14e33_v1_cff.py:6940
KDTreeLinkerAlgo::nodePool_
KDTreeNode * nodePool_
Definition: KDTreeLinkerAlgo.h:35
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().

154 {
155  // Iterate until leaf is found, or there are no children in the
156  // search window. If search has to proceed on both children, proceed
157  // the search to left child via recursion. Swap search window
158  // dimension on alternate levels.
159  while(true) {
160  int right = nodePool_.right[current];
161  if(nodePool_.isLeaf(right)) {
162  float dimCurr = nodePool_.median[current];
163 
164  // If point inside the rectangle/area
165  // Use intentionally bit-wise & instead of logical && for better
166  // performance. It is faster to always do all comparisons than to
167  // allow use of branches to not do some if any of the first ones
168  // is false.
169  if((dimCurr >= dimCurrMin) & (dimCurr <= dimCurrMax)) {
170  float dimOther = nodePool_.dimOther[current];
171  if((dimOther >= dimOtherMin) & (dimOther <= dimOtherMax)) {
172  closestNeighbour->push_back(nodePool_.data[current]);
173  }
174  }
175  break;
176  }
177  else {
178  float median = nodePool_.median[current];
179 
180  bool goLeft = (dimCurrMin <= median);
181  bool goRight = (dimCurrMax >= median);
182 
183  // Swap dimension for the next search level
184  std::swap(dimCurrMin, dimOtherMin);
185  std::swap(dimCurrMax, dimOtherMax);
186  if(goLeft & goRight) {
187  int left = current+1;
188  recSearch(left, dimCurrMin, dimCurrMax, dimOtherMin, dimOtherMax);
189  // continue with right
190  current = right;
191  }
192  else if(goLeft) {
193  ++current;
194  }
195  else if(goRight) {
196  current = right;
197  }
198  else {
199  break;
200  }
201  }
202  }
203 }
KDTreeLinkerAlgo::recSearch
void recSearch(const KDTreeNode *current, const KDTreeBox &trackBox, std::vector< KDTreeNodeInfo > &recHits)
Definition: KDTreeLinkerAlgo.cc:154
KDTreeLinkerAlgo::closestNeighbour
std::vector< DATA > * closestNeighbour
Definition: KDTreeLinkerAlgo.h:44
std::swap
void swap(edm::DataFrameContainer &lhs, edm::DataFrameContainer &rhs)
Definition: DataFrameContainer.h:223
KDTreeNode::right
KDTreeNode * right
Definition: KDTreeLinkerTools.h:70
KDTreeLinkerAlgo::nodePool_
KDTreeNode * nodePool_
Definition: KDTreeLinkerAlgo.h:35
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(), assert(), 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().

157 {
158  // By construction, current can't be null
159  assert(current != 0);
160 
161  // By Construction, a node can't have just 1 son.
162  assert (!(((current->left == 0) && (current->right != 0)) ||
163  ((current->left != 0) && (current->right == 0))));
164 
165  if ((current->left == 0) && (current->right == 0)) {//leaf case
166 
167  // If point inside the rectangle/area
168  if ((current->rh.dim1 >= trackBox.dim1min) && (current->rh.dim1 <= trackBox.dim1max) &&
169  (current->rh.dim2 >= trackBox.dim2min) && (current->rh.dim2 <= trackBox.dim2max))
170  recHits.push_back(current->rh);
171 
172  } else {
173 
174  //if region( v->left ) is fully contained in the rectangle
175  if ((current->left->region.dim1min >= trackBox.dim1min) &&
176  (current->left->region.dim1max <= trackBox.dim1max) &&
177  (current->left->region.dim2min >= trackBox.dim2min) &&
178  (current->left->region.dim2max <= trackBox.dim2max))
179  addSubtree(current->left, recHits);
180 
181  else { //if region( v->left ) intersects the rectangle
182 
183  if (!((current->left->region.dim1min >= trackBox.dim1max) ||
184  (current->left->region.dim1max <= trackBox.dim1min) ||
185  (current->left->region.dim2min >= trackBox.dim2max) ||
186  (current->left->region.dim2max <= trackBox.dim2min)))
187  recSearch(current->left, trackBox, recHits);
188  }
189 
190  //if region( v->right ) is fully contained in the rectangle
191  if ((current->right->region.dim1min >= trackBox.dim1min) &&
192  (current->right->region.dim1max <= trackBox.dim1max) &&
193  (current->right->region.dim2min >= trackBox.dim2min) &&
194  (current->right->region.dim2max <= trackBox.dim2max))
195  addSubtree(current->right, recHits);
196 
197  else { //if region( v->right ) intersects the rectangle
198 
199  if (!((current->right->region.dim1min >= trackBox.dim1max) ||
200  (current->right->region.dim1max <= trackBox.dim1min) ||
201  (current->right->region.dim2min >= trackBox.dim2max) ||
202  (current->right->region.dim2max <= trackBox.dim2min)))
203  recSearch(current->right, trackBox, recHits);
204  }
205  }
206 }
KDTreeLinkerAlgo::recSearch
void recSearch(const KDTreeNode *current, const KDTreeBox &trackBox, std::vector< KDTreeNodeInfo > &recHits)
Definition: KDTreeLinkerAlgo.cc:154
assert
assert(m_qm.get())
KDTreeLinkerAlgo::addSubtree
void addSubtree(const KDTreeNode *current, std::vector< KDTreeNodeInfo > &recHits)
Definition: KDTreeLinkerAlgo.cc:209
KDTreeNode::region
KDTreeBox region
Definition: KDTreeLinkerTools.h:73
KDTreeNode::right
KDTreeNode * right
Definition: KDTreeLinkerTools.h:70
KDTreeNode::left
KDTreeNode * left
Definition: KDTreeLinkerTools.h:70
KDTreeNode::rh
KDTreeNodeInfo rh
Definition: KDTreeLinkerTools.h:67
HLT_50nsGRun_cff.recHits
tuple recHits
Definition: HLT_50nsGRun_cff.py:48207
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().

148 {
149  if (root_)
150  recSearch(root_, trackBox, recHits);
151 }
KDTreeLinkerAlgo::recSearch
void recSearch(const KDTreeNode *current, const KDTreeBox &trackBox, std::vector< KDTreeNodeInfo > &recHits)
Definition: KDTreeLinkerAlgo.cc:154
KDTreeLinkerAlgo::root_
KDTreeNode * root_
Definition: KDTreeLinkerAlgo.h:32
HLT_50nsGRun_cff.recHits
tuple recHits
Definition: HLT_50nsGRun_cff.py:48207
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, relativeConstraints::empty, and HLT_50nsGRun_cff::recHits.

140 {
141  if (!empty()) {
142  closestNeighbour = &recHits;
143  recSearch(0, trackBox.dim1min, trackBox.dim1max, trackBox.dim2min, trackBox.dim2max);
144  closestNeighbour = 0;
145  }
146 }
KDTreeLinkerAlgo::recSearch
void recSearch(const KDTreeNode *current, const KDTreeBox &trackBox, std::vector< KDTreeNodeInfo > &recHits)
Definition: KDTreeLinkerAlgo.cc:154
KDTreeLinkerAlgo::closestNeighbour
std::vector< DATA > * closestNeighbour
Definition: KDTreeLinkerAlgo.h:44
HLT_50nsGRun_cff.recHits
tuple recHits
Definition: HLT_50nsGRun_cff.py:48207
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().

139 {
140  KDTreeNodeInfo tmp = e1;
141  e1 = e2;
142  e2 = tmp;
143 }
tmp
std::vector< std::vector< double > > tmp
Definition: MVATrainer.cc:100

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().

Generated for CMSSW Reference Manual by doxygen 1.8.5