CMS 3D CMS Logo
List of all members | Public Member Functions | Private Member Functions | Private Attributes
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().

240  : root_ (nullptr),
241  nodePool_(nullptr),
242  nodePoolSize_(-1),
243  nodePoolPos_(-1)
244 {
245 }
KDTreeLinkerAlgo::nodePool_
KDTreeNodeT< DATA, DIM > * nodePool_
Definition: KDTreeLinkerAlgoT.h:45
KDTreeLinkerAlgo::root_
KDTreeNodeT< DATA, DIM > * root_
Definition: KDTreeLinkerAlgoT.h:42
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().

249 {
250  clear();
251 }
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_.

211 {
212  // By construction, current can't be null
213  assert(current != nullptr);
214 
215  if ((current->left == nullptr) && (current->right == nullptr)) // leaf
216  recHits.push_back(current->rh);
217  else { // node
218  addSubtree(current->left, recHits);
219  addSubtree(current->right, recHits);
220  }
221 }
KDTreeLinkerAlgo::addSubtree
void addSubtree(const KDTreeNodeT< DATA, DIM > *current)
Definition: KDTreeLinkerAlgoT.h:222
KDTreeNode::right
KDTreeNode * right
Definition: KDTreeLinkerTools.h:70
KDTreeNode::left
KDTreeNode * left
Definition: KDTreeLinkerTools.h:70
KDTreeNode::rh
KDTreeNodeInfo rh
Definition: KDTreeLinkerTools.h:67
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().

223 {
224  // By construction, current can't be null
225  // assert(current != 0);
226 
227  if ((current->left == nullptr) && (current->right == nullptr)) // leaf
228  closestNeighbour->push_back(current->info);
229  else { // node
230  addSubtree(current->left);
231  addSubtree(current->right);
232  }
233 }
KDTreeNodeT::right
KDTreeNodeT< DATA, DIM > * right
Definition: KDTreeLinkerToolsT.h:64
KDTreeNodeT::left
KDTreeNodeT< DATA, DIM > * left
Definition: KDTreeLinkerToolsT.h:64
KDTreeLinkerAlgo::addSubtree
void addSubtree(const KDTreeNodeT< DATA, DIM > *current)
Definition: KDTreeLinkerAlgoT.h:222
KDTreeNodeT::info
KDTreeNodeInfoT< DATA, DIM > info
Definition: KDTreeLinkerToolsT.h:61
KDTreeLinkerAlgo::closestNeighbour
std::vector< KDTreeNodeInfoT< DATA, DIM > > * closestNeighbour
Definition: KDTreeLinkerAlgoT.h:51
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_.

19 {
20  if (!eltList.empty()) {
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
KDTreeNodeT< DATA, DIM > * recBuild(int low, int hight, int depth, const KDTreeBoxT< DIM > &region)
Definition: KDTreeLinkerAlgoT.h:290
KDTreeLinkerAlgo::nodePool_
KDTreeNodeT< DATA, DIM > * nodePool_
Definition: KDTreeLinkerAlgoT.h:45
KDTreeLinkerAlgo::root_
KDTreeNodeT< DATA, DIM > * root_
Definition: KDTreeLinkerAlgoT.h:42
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(), and HGCalImagingAlgo::findAndAssignClusters().

88 {
89  if (!eltList.empty()) {
90  initialEltList = &eltList;
91 
92  size_t size = initialEltList->size();
93  nodePoolSize_ = size * 2 - 1;
94  nodePool_ = new KDTreeNodeT<DATA,DIM>[nodePoolSize_];
95 
96  // Here we build the KDTree
97  root_ = recBuild(0, size, 0, region);
98 
99  initialEltList = nullptr;
100  }
101 }
KDTreeLinkerAlgo::recBuild
KDTreeNodeT< DATA, DIM > * recBuild(int low, int hight, int depth, const KDTreeBoxT< DIM > &region)
Definition: KDTreeLinkerAlgoT.h:290
KDTreeLinkerAlgo::nodePool_
KDTreeNodeT< DATA, DIM > * nodePool_
Definition: KDTreeLinkerAlgoT.h:45
KDTreeLinkerAlgo::root_
KDTreeNodeT< DATA, DIM > * root_
Definition: KDTreeLinkerAlgoT.h:42
KDTreeLinkerAlgo::initialEltList
std::vector< KDTreeNodeInfoT< DATA, DIM > > * initialEltList
Definition: KDTreeLinkerAlgoT.h:52
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().

268 {
269  if (root_)
270  clearTree();
271 }
KDTreeLinkerAlgo::root_
KDTreeNodeT< DATA, DIM > * root_
Definition: KDTreeLinkerAlgoT.h:42
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().

257 {
258  delete[] nodePool_;
259  nodePool_ = nullptr;
260  root_ = nullptr;
261  nodePoolSize_ = -1;
262  nodePoolPos_ = -1;
263 }
KDTreeLinkerAlgo::nodePool_
KDTreeNodeT< DATA, DIM > * nodePool_
Definition: KDTreeLinkerAlgoT.h:45
KDTreeLinkerAlgo::root_
KDTreeNodeT< DATA, DIM > * root_
Definition: KDTreeLinkerAlgoT.h:42
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_.

31 {return nodePool_.empty();}
KDTreeLinkerAlgo::nodePool_
KDTreeNodeT< DATA, DIM > * nodePool_
Definition: KDTreeLinkerAlgoT.h:45
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().

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

277 {
278  ++nodePoolPos_;
279 
280  // The tree size is exactly 2 * nbrElts - 1 and this is the total allocated memory.
281  // If we have used more than that....there is a big problem.
282  // assert(nodePoolPos_ < nodePoolSize_);
283 
284  return &(nodePool_[nodePoolPos_]);
285 }
KDTreeLinkerAlgo::nodePool_
KDTreeNodeT< DATA, DIM > * nodePool_
Definition: KDTreeLinkerAlgoT.h:45
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, mps_fire::i, checklumidiff::l, funct::m, and KDTreeLinkerAlgo< DATA, DIM >::swap().

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 }
mps_fire.i
i
Definition: mps_fire.py:269
KDTreeLinkerAlgo::swap
void swap(KDTreeNodeInfo &e1, KDTreeNodeInfo &e2)
Definition: KDTreeLinkerAlgo.cc:137
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, mps_fire::i, KDTreeLinkerAlgo< DATA, DIM >::initialEltList, checklumidiff::l, funct::m, and std::swap().

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

109 {
110  //We should have at least 1 element to calculate the median...
111  //assert(low < high);
112 
113  const int nbrElts = high - low;
114  int median = nbrElts/2 - ( 1 - 1*(nbrElts&1) );
115  median += low;
116 
117  int l = low;
118  int m = high - 1;
119 
120  while (l < m) {
121  KDTreeNodeInfoT<DATA,DIM> elt = (*initialEltList)[median];
122  int i = l;
123  int j = m;
124 
125  do {
126  // The even depth is associated to dim1 dimension
127  // The odd one to dim2 dimension
128  const unsigned thedim = treeDepth % DIM;
129  while( (*initialEltList)[i].dims[thedim] < elt.dims[thedim] ) ++i;
130  while( (*initialEltList)[j].dims[thedim] > elt.dims[thedim] ) --j;
131 
132  if (i <= j){
133  std::swap((*initialEltList)[i], (*initialEltList)[j]);
134  i++;
135  j--;
136  }
137  } while (i <= j);
138  if (j < median) l = i;
139  if (i > median) m = j;
140  }
141 
142  return median;
143 }
mps_fire.i
i
Definition: mps_fire.py:269
std::swap
void swap(edm::DataFrameContainer &lhs, edm::DataFrameContainer &rhs)
Definition: DataFrameContainer.h:236
KDTreeNodeInfoT::dims
std::array< float, DIM > dims
Definition: KDTreeLinkerToolsT.h:40
DIM
#define DIM
Definition: Vx3DHLTAnalyzer.h:38
KDTreeLinkerAlgo::initialEltList
std::vector< KDTreeNodeInfoT< DATA, DIM > > * initialEltList
Definition: KDTreeLinkerAlgoT.h:52
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 egammaForCoreTracking_cff::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().

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
KDTreeLinkerAlgo::medianSearch
int medianSearch(int low, int high, int treeDepth)
Definition: KDTreeLinkerAlgoT.h:106
KDTreeLinkerAlgo::recBuild
KDTreeNodeT< DATA, DIM > * recBuild(int low, int hight, int depth, const KDTreeBoxT< DIM > &region)
Definition: KDTreeLinkerAlgoT.h:290
KDTreeNode::right
KDTreeNode * right
Definition: KDTreeLinkerTools.h:70
KDTreeNode::left
KDTreeNode * left
Definition: KDTreeLinkerTools.h:70
KDTreeLinkerAlgo::getNextNode
KDTreeNodeT< DATA, DIM > * getNextNode()
Definition: KDTreeLinkerAlgoT.h:276
egammaForCoreTracking_cff.depth
depth
Definition: egammaForCoreTracking_cff.py:29
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, egammaForCoreTracking_cff::depth, KDTreeNodeInfo< DATA >::dim, info(), KDTreeLinkerAlgo< DATA, DIM >::medianSearch(), KDTreeLinkerAlgo< DATA, DIM >::nodePool_, and KDTreeLinkerAlgo< DATA, DIM >::recBuild().

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
KDTreeLinkerAlgo::medianSearch
int medianSearch(int low, int high, int treeDepth)
Definition: KDTreeLinkerAlgoT.h:106
KDTreeLinkerAlgo::recBuild
KDTreeNodeT< DATA, DIM > * recBuild(int low, int hight, int depth, const KDTreeBoxT< DIM > &region)
Definition: KDTreeLinkerAlgoT.h:290
KDTreeLinkerAlgo::nodePool_
KDTreeNodeT< DATA, DIM > * nodePool_
Definition: KDTreeLinkerAlgoT.h:45
egammaForCoreTracking_cff.depth
depth
Definition: egammaForCoreTracking_cff.py:29
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 egammaForCoreTracking_cff::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().

294 {
295  int portionSize = high - low;
296 
297  // By construction, portionSize > 0 can't happend.
298  // assert(portionSize > 0);
299 
300  if (portionSize == 1) { // Leaf case
301 
302  KDTreeNodeT<DATA,DIM> *leaf = getNextNode();
303  leaf->setAttributs(region, (*initialEltList)[low]);
304  return leaf;
305 
306  } else { // Node case
307 
308  // The even depth is associated to dim1 dimension
309  // The odd one to dim2 dimension
310  int medianId = medianSearch(low, high, depth);
311 
312  // We create the node
313  KDTreeNodeT<DATA,DIM> *node = getNextNode();
314  node->setAttributs(region);
315 
316 
317  // Here we split into 2 halfplanes the current plane
318  KDTreeBoxT<DIM> leftRegion = region;
319  KDTreeBoxT<DIM> rightRegion = region;
320  unsigned thedim = depth % DIM;
321  auto medianVal = (*initialEltList)[medianId].dims[thedim];
322  leftRegion.dimmax[thedim] = medianVal;
323  rightRegion.dimmin[thedim] = medianVal;
324 
325  ++depth;
326  ++medianId;
327 
328  // We recursively build the son nodes
329  node->left = recBuild(low, medianId, depth, leftRegion);
330  node->right = recBuild(medianId, high, depth, rightRegion);
331 
332  return node;
333  }
334 }
KDTreeNodeT::right
KDTreeNodeT< DATA, DIM > * right
Definition: KDTreeLinkerToolsT.h:64
KDTreeNodeT::left
KDTreeNodeT< DATA, DIM > * left
Definition: KDTreeLinkerToolsT.h:64
KDTreeBoxT::dimmin
std::array< float, DIM > dimmin
Definition: KDTreeLinkerToolsT.h:14
KDTreeLinkerAlgo::medianSearch
int medianSearch(int low, int high, int treeDepth)
Definition: KDTreeLinkerAlgoT.h:106
KDTreeLinkerAlgo::recBuild
KDTreeNodeT< DATA, DIM > * recBuild(int low, int hight, int depth, const KDTreeBoxT< DIM > &region)
Definition: KDTreeLinkerAlgoT.h:290
KDTreeLinkerAlgo::getNextNode
KDTreeNodeT< DATA, DIM > * getNextNode()
Definition: KDTreeLinkerAlgoT.h:276
DIM
#define DIM
Definition: Vx3DHLTAnalyzer.h:38
KDTreeBoxT::dimmax
std::array< float, DIM > dimmax
Definition: KDTreeLinkerToolsT.h:14
KDTreeNodeT::setAttributs
void setAttributs(const KDTreeBoxT< DIM > &regionBox, const KDTreeNodeInfoT< DATA, DIM > &infoToStore)
Definition: KDTreeLinkerToolsT.h:74
KDTreeLinkerAlgo::initialEltList
std::vector< KDTreeNodeInfoT< DATA, DIM > > * initialEltList
Definition: KDTreeLinkerAlgoT.h:52
egammaForCoreTracking_cff.depth
depth
Definition: egammaForCoreTracking_cff.py:29
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.

157 {
158  // By construction, current can't be null
159  assert(current != nullptr);
160 
161  // By Construction, a node can't have just 1 son.
162  assert (!(((current->left == nullptr) && (current->right != nullptr)) ||
163  ((current->left != nullptr) && (current->right == nullptr))));
164 
165  if ((current->left == nullptr) && (current->right == nullptr)) {//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::addSubtree
void addSubtree(const KDTreeNodeT< DATA, DIM > *current)
Definition: KDTreeLinkerAlgoT.h:222
KDTreeNode::region
KDTreeBox region
Definition: KDTreeLinkerTools.h:73
KDTreeNode::right
KDTreeNode * right
Definition: KDTreeLinkerTools.h:70
KDTreeNode::left
KDTreeNode * left
Definition: KDTreeLinkerTools.h:70
KDTreeLinkerAlgo::recSearch
void recSearch(const KDTreeNodeT< DATA, DIM > *current, const KDTreeBoxT< DIM > &trackBox)
Definition: KDTreeLinkerAlgoT.h:162
KDTreeNode::rh
KDTreeNodeInfo rh
Definition: KDTreeLinkerTools.h:67
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().

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 }
std::swap
void swap(edm::DataFrameContainer &lhs, edm::DataFrameContainer &rhs)
Definition: DataFrameContainer.h:236
KDTreeLinkerAlgo::nodePool_
KDTreeNodeT< DATA, DIM > * nodePool_
Definition: KDTreeLinkerAlgoT.h:45
KDTreeLinkerAlgo::closestNeighbour
std::vector< KDTreeNodeInfoT< DATA, DIM > > * closestNeighbour
Definition: KDTreeLinkerAlgoT.h:51
KDTreeLinkerAlgo::recSearch
void recSearch(const KDTreeNodeT< DATA, DIM > *current, const KDTreeBoxT< DIM > &trackBox)
Definition: KDTreeLinkerAlgoT.h:162
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, mps_fire::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().

164 {
165  /*
166  // By construction, current can't be null
167  assert(current != 0);
168 
169  // By Construction, a node can't have just 1 son.
170  assert (!(((current->left == 0) && (current->right != 0)) ||
171  ((current->left != 0) && (current->right == 0))));
172  */
173 
174  if ((current->left == nullptr) && (current->right == nullptr)) {//leaf case
175 
176  // If point inside the rectangle/area
177  bool isInside = true;
178  for( unsigned i = 0; i < DIM; ++i ) {
179  const auto thedim = current->info.dims[i];
180  isInside *= thedim >= trackBox.dimmin[i] && thedim <= trackBox.dimmax[i];
181  }
182  if( isInside ) closestNeighbour->push_back(current->info);
183 
184  } else {
185 
186  bool isFullyContained = true;
187  bool hasIntersection = true;
188  //if region( v->left ) is fully contained in the rectangle
189  for( unsigned i = 0; i < DIM; ++i ) {
190  const auto regionmin = current->left->region.dimmin[i];
191  const auto regionmax = current->left->region.dimmax[i];
192  isFullyContained *= ( regionmin >= trackBox.dimmin[i] &&
193  regionmax <= trackBox.dimmax[i] );
194  hasIntersection *= ( regionmin < trackBox.dimmax[i] && regionmax > trackBox.dimmin[i]);
195  }
196  if( isFullyContained ) {
197  addSubtree(current->left);
198  } else if ( hasIntersection ) {
199  recSearch(current->left, trackBox);
200  }
201  // reset flags
202  isFullyContained = true;
203  hasIntersection = true;
204  //if region( v->right ) is fully contained in the rectangle
205  for( unsigned i = 0; i < DIM; ++i ) {
206  const auto regionmin = current->right->region.dimmin[i];
207  const auto regionmax = current->right->region.dimmax[i];
208  isFullyContained *= ( regionmin >= trackBox.dimmin[i] &&
209  regionmax <= trackBox.dimmax[i] );
210  hasIntersection *= ( regionmin < trackBox.dimmax[i] && regionmax > trackBox.dimmin[i]);
211  }
212  if( isFullyContained ) {
213  addSubtree(current->right);
214  } else if ( hasIntersection ) {
215  recSearch(current->right, trackBox);
216  }
217  }
218 }
mps_fire.i
i
Definition: mps_fire.py:269
KDTreeNodeT::right
KDTreeNodeT< DATA, DIM > * right
Definition: KDTreeLinkerToolsT.h:64
KDTreeNodeT::left
KDTreeNodeT< DATA, DIM > * left
Definition: KDTreeLinkerToolsT.h:64
KDTreeBoxT::dimmin
std::array< float, DIM > dimmin
Definition: KDTreeLinkerToolsT.h:14
KDTreeLinkerAlgo::addSubtree
void addSubtree(const KDTreeNodeT< DATA, DIM > *current)
Definition: KDTreeLinkerAlgoT.h:222
DIM
#define DIM
Definition: Vx3DHLTAnalyzer.h:38
KDTreeNodeT::info
KDTreeNodeInfoT< DATA, DIM > info
Definition: KDTreeLinkerToolsT.h:61
KDTreeLinkerAlgo::closestNeighbour
std::vector< KDTreeNodeInfoT< DATA, DIM > > * closestNeighbour
Definition: KDTreeLinkerAlgoT.h:51
KDTreeLinkerAlgo::recSearch
void recSearch(const KDTreeNodeT< DATA, DIM > *current, const KDTreeBoxT< DIM > &trackBox)
Definition: KDTreeLinkerAlgoT.h:162
KDTreeBoxT::dimmax
std::array< float, DIM > dimmax
Definition: KDTreeLinkerToolsT.h:14
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_.

148 {
149  if (root_)
150  recSearch(root_, trackBox, recHits);
151 }
KDTreeLinkerAlgo::root_
KDTreeNodeT< DATA, DIM > * root_
Definition: KDTreeLinkerAlgoT.h:42
KDTreeLinkerAlgo::recSearch
void recSearch(const KDTreeNodeT< DATA, DIM > *current, const KDTreeBoxT< DIM > &trackBox)
Definition: KDTreeLinkerAlgoT.h:162
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(), KDTreeLinkerPSEcal::searchLinks(), KDTreeLinkerTrackEcal::searchLinks(), and KDTreeLinkerTrackHcal::searchLinks().

151 {
152  if (root_) {
153  closestNeighbour = &recHits;
154  recSearch(root_, trackBox);
155  closestNeighbour = nullptr;
156  }
157 }
KDTreeLinkerAlgo::root_
KDTreeNodeT< DATA, DIM > * root_
Definition: KDTreeLinkerAlgoT.h:42
KDTreeLinkerAlgo::closestNeighbour
std::vector< KDTreeNodeInfoT< DATA, DIM > > * closestNeighbour
Definition: KDTreeLinkerAlgoT.h:51
KDTreeLinkerAlgo::recSearch
void recSearch(const KDTreeNodeT< DATA, DIM > *current, const KDTreeBoxT< DIM > &trackBox)
Definition: KDTreeLinkerAlgoT.h:162
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().

140 {
141  if (!empty()) {
142  closestNeighbour = &recHits;
143  recSearch(0, trackBox.dim1min, trackBox.dim1max, trackBox.dim2min, trackBox.dim2max);
144  closestNeighbour = nullptr;
145  }
146 }
KDTreeLinkerAlgo::closestNeighbour
std::vector< KDTreeNodeInfoT< DATA, DIM > > * closestNeighbour
Definition: KDTreeLinkerAlgoT.h:51
KDTreeLinkerAlgo::recSearch
void recSearch(const KDTreeNodeT< DATA, DIM > *current, const KDTreeBoxT< DIM > &trackBox)
Definition: KDTreeLinkerAlgoT.h:162
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 ntupleDataFormat._Collection::__iter__(), and ntupleDataFormat._Collection::__len__().

35 { return nodePool_.size();}
KDTreeLinkerAlgo::nodePool_
KDTreeNodeT< DATA, DIM > * nodePool_
Definition: KDTreeLinkerAlgoT.h:45
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 ntupleDataFormat._Collection::__iter__(), ntupleDataFormat._Collection::__len__(), and KDTreeLinkerAlgo< DATA, DIM >::build().

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

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

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

Generated for CMSSW Reference Manual by doxygen 1.8.11