273template <
typename Index,
typename Value>
287 ,fBoundaries(nullptr)
295template <
typename Index,
typename Value>
309 ,fBoundaries(nullptr)
347template <
typename Index,
typename Value>
361 ,fBoundaries(nullptr)
376template <
typename Index,
typename Value>
379 if (fAxis)
delete [] fAxis;
380 if (fValue)
delete [] fValue;
381 if (fIndPoints)
delete [] fIndPoints;
382 if (fRange)
delete [] fRange;
383 if (fBoundaries)
delete [] fBoundaries;
414template <
typename Index,
typename Value>
418 fNNodes = fNPoints/fBucketSize-1;
419 if (fNPoints%fBucketSize) fNNodes++;
420 fTotalNodes = fNNodes + fNPoints/fBucketSize + ((fNPoints%fBucketSize)?1:0);
423 for ( ;(fNNodes+1)>(1<<fRowT0);fRowT0++) {}
435 fRange =
new Value[2*fNDim];
436 fIndPoints=
new Index[fNPoints];
437 for (Index i=0; i<fNPoints; i++) fIndPoints[i] = i;
439 fValue =
new Value[fNNodes];
441 fCrossNode = (1<<(fRowT0+1))-1;
442 if (fCrossNode<fNNodes) fCrossNode = 2*fCrossNode+1;
446 Int_t filled = ((1<<fRowT0)-
over)*fBucketSize;
447 fOffset = fNPoints-filled;
513 fRange[2*
idim] = min; fRange[2*
idim+1] = max;
546template <
typename Index,
typename Value>
551 Error(
"FindNearestNeighbors",
"Working arrays must be allocated by the user!");
555 dist[i]=std::numeric_limits<Value>::max();
558 MakeBoundariesExact();
559 UpdateNearestNeighbors(0, point,
kNN,
ind, dist);
566template <
typename Index,
typename Value>
571 DistanceToNode(point,
inode, min, max);
572 if (min > dist[
kNN-1]){
576 if (IsTerminal(
inode)) {
601 UpdateNearestNeighbors(GetLeft(
inode), point,
kNN,
ind, dist);
602 UpdateNearestNeighbors(GetRight(
inode), point,
kNN,
ind, dist);
604 UpdateNearestNeighbors(GetRight(
inode), point,
kNN,
ind, dist);
605 UpdateNearestNeighbors(GetLeft(
inode), point,
kNN,
ind, dist);
613template <
typename Index,
typename Value>
638template <
typename Index,
typename Value>
675template <
typename Index,
typename Value>
706template <
typename Index,
typename Value>
717 if (IsTerminal(
inode)){
725 if (
indexIP>=fNPoints)
continue;
752template <
typename Index,
typename Value>
755 MakeBoundariesExact();
756 UpdateRange(0, point,
range, res);
762template <
typename Index,
typename Value>
766 DistanceToNode(point,
inode, min, max);
778 res.push_back(fIndPoints[
ipoint]);
781 res.push_back(fIndPoints[
ipoint]);
787 if (IsTerminal(
inode)){
793 d = Distance(point, fIndPoints[
ipoint]);
795 res.push_back(fIndPoints[
ipoint]);
802 UpdateRange(GetLeft(
inode),point,
range, res);
803 UpdateRange(GetRight(
inode),point,
range, res);
805 UpdateRange(GetLeft(
inode),point,
range, res);
806 UpdateRange(GetRight(
inode),point,
range, res);
815template <
typename Index,
typename Value>
818 if (!IsTerminal(node)){
819 printf(
"GetPointsIndexes() only for terminal nodes, use GetNodePointsIndexes() instead\n");
822 Int_t offset = (node >= fCrossNode) ? (node-fCrossNode)*fBucketSize : fOffset+(node-fNNodes)*fBucketSize;
823 return &fIndPoints[
offset];
844template <
typename Index,
typename Value>
848 if (IsTerminal(node)){
850 Index
offset = (node >= fCrossNode) ? (node-fCrossNode)*fBucketSize : fOffset+(node-fNNodes)*fBucketSize;
880 GetNodePointsIndexes(fTotalNodes-1,
f1,
l1, f2,
l2);
898template <
typename Index,
typename Value>
901 if (IsTerminal(
inode)){
903 if (
inode!=fTotalNodes-1)
return fBucketSize;
905 if (fOffset%fBucketSize==0)
return fBucketSize;
906 else return fOffset%fBucketSize;
921template <
typename Index,
typename Value>
946template <
typename Index,
typename Value>
949 if (fAxis || fValue) {
950 Error(
"SetData",
"The tree has already been built, no updates possible");
955 fData =
new Value*[fNDim];
966template <
typename Index,
typename Value>
983template <
typename Index,
typename Value>
1037template <
typename Index,
typename Value>
1043 Int_t totNodes = fNNodes + fNPoints/fBucketSize + ((fNPoints%fBucketSize)?1:0);
1057 if(IsTerminal(cn)) CookBoundaries(
inode,
kTRUE);
1058 cbounds = &fBoundaries[fNDimm*cn];
1064 cbounds = &fBoundaries[fNDimm*cn];
1072template <
typename Index,
typename Value>
1087 while(
pn >= 0 &&
nvals < fNDimm){
1117template <
typename Index,
typename Value>
1127 fBoundaries =
new Value[fTotalNodes*fNDimm];
1133 min[
idim]= std::numeric_limits<Value>::max();
1134 max[
idim]=-std::numeric_limits<Value>::max();
1159 left = GetLeft(
inode)*fNDimm;
1160 right = GetRight(
inode)*fNDimm;
1176template <
typename Index,
typename Value>
1179 for (;
inode<fNNodes;){
1188template <
typename Index,
typename Value>
1191 if(!fBoundaries) MakeBoundaries();
1199template <
typename Index,
typename Value>
1202 if(!fBoundaries) MakeBoundariesExact();
1209template <
typename Index,
typename Value>
1212 if(!fBoundaries) MakeBoundaries();
1213 return &fBoundaries[node*2*fNDim];
1219template <
typename Index,
typename Value>
1222 if(!fBoundaries) MakeBoundariesExact();
1223 return &fBoundaries[node*2*fNDim];
int Int_t
Signed integer 4 bytes (int)
unsigned char UChar_t
Unsigned Character 1 byte (unsigned char)
float Float_t
Float 4 bytes (float)
#define templateClassImp(name)
ROOT::Detail::TRangeCast< T, true > TRangeDynCast
TRangeDynCast is an adapter class that allows the typed iteration through a TCollection.
void Info(const char *location, const char *msgfmt,...)
Use this function for informational messages.
void Error(const char *location, const char *msgfmt,...)
Use this function in case an error occurred.
void Warning(const char *location, const char *msgfmt,...)
Use this function in warning situations.
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void data
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t Float_t Float_t Float_t Int_t Int_t UInt_t UInt_t Rectangle_t Int_t Int_t Window_t TString Int_t GCValues_t GetPrimarySelectionOwner GetDisplay GetScreen GetColormap GetNativeEvent const char const char dpyName wid window const char font_name cursor keysym reg const char only_if_exist regb h Point_t winding char text const char depth char const char Int_t count const char ColorStruct_t color const char Pixmap_t Pixmap_t PictureAttributes_t attr const char char ret_data h unsigned char height h offset
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t index
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t points
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t Float_t Float_t Float_t Int_t Int_t UInt_t UInt_t Rectangle_t Int_t Int_t Window_t TString Int_t GCValues_t GetPrimarySelectionOwner GetDisplay GetScreen GetColormap GetNativeEvent const char const char dpyName wid window const char font_name cursor keysym reg const char only_if_exist regb h Point_t winding char text const char depth char const char Int_t count const char ColorStruct_t color const char Pixmap_t Pixmap_t PictureAttributes_t attr const char char ret_data h unsigned char height h Atom_t Int_t ULong_t ULong_t unsigned char prop_list Atom_t Atom_t Atom_t Time_t type
TKDTreeIF * TKDTreeTestBuild()
TKDTree< Int_t, Float_t > TKDTreeIF
R__EXTERN TRandom * gRandom
char * Form(const char *fmt,...)
Formats a string in a circular formatting buffer.
Class implementing a kd-tree.
void FindPoint(Value *point, Index &index, Int_t &iter)
find the index of point works only if we keep fData pointers
void SetData(Index npoints, Index ndim, UInt_t bsize, Value **data)
Set the data array. See the constructor function comments for details.
~TKDTree() override
Destructor By default, the original data is not owned by kd-tree and is not deleted with it.
void GetNodePointsIndexes(Int_t node, Int_t &first1, Int_t &last1, Int_t &first2, Int_t &last2) const
Return the indices of points in that node Indices are returned as the first and last value of the par...
Value * GetBoundaryExact(const Int_t node)
Get a boundary.
void FindBNodeA(Value *point, Value *delta, Int_t &inode)
find the smallest node covering the full range - start
void UpdateRange(Index inode, Value *point, Value range, std::vector< Index > &res)
Internal recursive function with the implementation of range searches.
Index FindNode(const Value *point) const
returns the index of the terminal node to which point belongs (index in the fAxis,...
Value KOrdStat(Index ntotal, Value *a, Index k, Index *index) const
copy of the TMath::KOrdStat because I need an Index work array
Value * GetBoundariesExact()
Get the boundaries.
void MakeBoundariesExact()
Build boundaries for each node.
void CookBoundaries(const Int_t node, Bool_t left)
define index of this terminal node
void MakeBoundaries(Value *range=nullptr)
Build boundaries for each node.
void UpdateNearestNeighbors(Index inode, const Value *point, Int_t kNN, Index *ind, Value *dist)
Update the nearest neighbors values by examining the node inode.
Double_t Distance(const Value *point, Index ind, Int_t type=2) const
Find the distance between point of the first argument and the point at index value ind Type argument ...
Index * GetPointsIndexes(Int_t node) const
return the indices of the points in that terminal node for all the nodes except last,...
void Spread(Index ntotal, Value *a, Index *index, Value &min, Value &max) const
Calculate spread of the array a.
void Build()
Build the kd-tree.
void DistanceToNode(const Value *point, Index inode, Value &min, Value &max, Int_t type=2)
Find the minimal and maximal distance from a given point to a given node.
TKDTree()
Default constructor. Nothing is built.
void FindInRange(Value *point, Value range, std::vector< Index > &res)
Find all points in the sphere of a given radius "range" around the given point 1st argument - the poi...
Index GetNPointsNode(Int_t node) const
Get number of points in this node for all the terminal nodes except last, the size is fBucketSize for...
Value * GetBoundaries()
Get the boundaries.
Value * GetBoundary(const Int_t node)
Get a boundary.
void FindNearestNeighbors(const Value *point, Int_t k, Index *ind, Value *dist)
Find kNN nearest neighbors to the point in the first argument Returns 1 on success,...
kNN::Event describes point in input variable vector-space, with additional functionality like distanc...
Mother of all ROOT objects.
Double_t Rndm() override
Machine independent random number generator.
Short_t Max(Short_t a, Short_t b)
Returns the largest of a and b.
Double_t Sqrt(Double_t x)
Returns the square root of x.
Short_t Min(Short_t a, Short_t b)
Returns the smallest of a and b.
Short_t Abs(Short_t d)
Returns the absolute value of parameter Short_t d.
static uint64_t sum(uint64_t i)