#include "TKDInterpolator.h"
#include "TLinearFitter.h"
-#include "TVector.h"
#include "TTree.h"
#include "TH2.h"
#include "TObjArray.h"
#include "TObjString.h"
-#include "TPad.h"
#include "TBox.h"
#include "TGraph.h"
#include "TMarker.h"
-#include "TRandom.h"
-#include "TROOT.h"
+#include "TVectorD.h"
+#include "TMatrixD.h"
ClassImp(TKDInterpolator)
ClassImp(TKDInterpolator::TKDNodeInfo)
/////////////////////////////////////////////////////////////////////
-// Memory setup of protected data memebers
+// Memory setup of protected data members
// fRefPoints : evaluation point of PDF for each terminal node of underlying KD Tree.
// | 1st terminal node (fNDim point coordinates) | 2nd terminal node (fNDim point coordinates) | ...
//
fNDim(dim)
,fRefPoint(0x0)
,fRefValue(0.)
- ,fCov()
- ,fPar()
- ,fPDFstatus(kFALSE)
+ ,fCov(0x0)
+ ,fPar(0x0)
{
if(fNDim) Build(dim);
}
TKDInterpolator::TKDNodeInfo::~TKDNodeInfo()
{
if(fRefPoint) delete [] fRefPoint;
+ if(fCov){
+ delete fPar;
+ delete fCov;
+ }
}
//_________________________________________________________________
void TKDInterpolator::TKDNodeInfo::Build(const Int_t dim)
{
+// Allocate/Reallocate space for this node.
+
if(!dim) return;
fNDim = dim;
Int_t lambda = Int_t(1 + fNDim + .5*fNDim*(fNDim+1));
if(fRefPoint) delete [] fRefPoint;
fRefPoint = new Float_t[fNDim];
- fCov.ResizeTo(lambda, lambda);
- fPar.ResizeTo(lambda);
+ if(fCov){
+ fCov->ResizeTo(lambda, lambda);
+ fPar->ResizeTo(lambda);
+ }
return;
}
+//_________________________________________________________________
+void TKDInterpolator::TKDNodeInfo::Store(const TVectorD &par, const TMatrixD &cov)
+{
+ if(!fCov){
+ fCov = new TMatrixD(cov.GetNrows(), cov.GetNrows());
+ fPar = new TVectorD(par.GetNrows());
+ }
+ (*fPar) = par;
+ (*fCov) = cov;
+}
+
+//_________________________________________________________________
+Double_t TKDInterpolator::TKDNodeInfo::CookPDF(const Double_t *point, Double_t &result, Double_t &error)
+{
+// Recalculate the PDF for one node from the results of interpolation (parameters and covariance matrix)
+
+ if(fNDim>10) return 0.; // support only up to 10 dimensions
+
+ Int_t lambda = 1 + fNDim + (fNDim*(fNDim+1)>>1);
+ Double_t fdfdp[66];
+ Int_t ipar = 0;
+ fdfdp[ipar++] = 1.;
+ for(int idim=0; idim<fNDim; idim++){
+ fdfdp[ipar++] = point[idim];
+ for(int jdim=idim; jdim<fNDim; jdim++) fdfdp[ipar++] = point[idim]*point[jdim];
+ }
+
+ // calculate estimation
+ result =0.; error = 0.;
+ for(int i=0; i<lambda; i++){
+ result += fdfdp[i]*(*fPar)(i);
+ for(int j=0; j<lambda; j++) error += fdfdp[i]*fdfdp[j]*(*fCov)(i,j);
+ }
+ error = TMath::Sqrt(error);
+
+ //printf("TKDNodeInfo::CookPDF() : %6.3f +- %6.3f\n", result, error);
+
+ return 0.;
+}
+
//_________________________________________________________________
TKDInterpolator::TKDInterpolator() : TKDTreeIF()
,fStatus(4)
,fLambda(0)
,fDepth(-1)
+ ,fAlpha(.5)
,fRefPoints(0x0)
,fBuffer(0x0)
,fKDhelper(0x0)
//_________________________________________________________________
TKDInterpolator::TKDInterpolator(Int_t npoints, Int_t ndim, UInt_t bsize, Float_t **data) : TKDTreeIF(npoints, ndim, bsize, data)
- ,fNTNodes(GetNTerminalNodes())
+ ,fNTNodes(GetNTNodes())
,fTNodes(0x0)
,fStatus(4)
,fLambda(0)
,fDepth(-1)
+ ,fAlpha(.5)
,fRefPoints(0x0)
,fBuffer(0x0)
,fKDhelper(0x0)
,fFitter(0x0)
{
-// Wrapper constructor for the similar TKDTree one.
-
+// Wrapper constructor for the TKDTree.
+
Build();
}
,fStatus(4)
,fLambda(0)
,fDepth(-1)
+ ,fAlpha(.5)
,fRefPoints(0x0)
,fBuffer(0x0)
,fKDhelper(0x0)
Warning("TKDInterpolator(TTree*, const Char_t, const Char_t, UInt_t)", Form("Can not access data for keys %s. Key defined on tree :", ((TObjString*)(*vars)[idim])->GetName() ));
TIterator *it = (t->GetListOfLeaves())->MakeIterator();
TObject *o;
- while(o = (*it)()) printf("\t%s\n", o->GetName());
+ while((o = (*it)())) printf("\t%s\n", o->GetName());
continue;
}
if(!fNpoints){
fNpoints = np;
- Info("TKDInterpolator(TTree*, const Char_t, const Char_t, UInt_t)", Form("Allocating %d data points in %d dimensions.", fNpoints, fNDim));
+ //Info("TKDInterpolator(TTree*, const Char_t, const Char_t, UInt_t)", Form("Allocating %d data points in %d dimensions.", fNpoints, fNDim));
fData = new Float_t*[fNDim];
for(int idim=0; idim<fNDim; idim++) fData[idim] = new Float_t[fNpoints];
kDataOwner = kTRUE;
for(int ip=0; ip<fNpoints; ip++) fData[idim][ip] = (Float_t)v[ip];
}
TKDTreeIF::Build();
- fNTNodes = GetNTerminalNodes();
Build();
}
// - estimation points
// - corresponding PDF values
+ fNTNodes = TKDTreeIF::GetNTNodes();
if(!fBoundaries) MakeBoundaries();
- fLambda = 1 + fNDim + fNDim*(fNDim+1)/2;
-
+ fLambda = 1 + fNDim + (fNDim*(fNDim+1)>>1);
+ //printf("after MakeBoundaries() %d\n", memory());
+
// allocate memory for data
fTNodes = new TKDNodeInfo[fNTNodes];
for(int in=0; in<fNTNodes; in++) fTNodes[in].Build(fNDim);
+ //printf("after BuildNodes() %d\n", memory());
Float_t *bounds = 0x0;
Int_t *indexPoints;
fTNodes[inode].fRefValue = Float_t(fBucketSize)/fNpoints;
bounds = GetBoundary(tnode);
for(int idim=0; idim<fNDim; idim++) fTNodes[inode].fRefValue /= (bounds[2*idim+1] - bounds[2*idim]);
-
+
indexPoints = GetPointsIndexes(tnode);
// loop points in this terminal node
for(int idim=0; idim<fNDim; idim++){
- for(int ip = 0; ip<fBucketSize; ip++) fTNodes[inode].fRefPoint[idim] += fData[idim][indexPoints[ip]];
+ fTNodes[inode].fRefPoint[idim] = 0.;
+ for(int ip = 0; ip<fBucketSize; ip++){
+/* printf("\t\tindex[%d] = %d %f\n", ip, indexPoints[ip], fData[idim][indexPoints[ip]]);*/
+ fTNodes[inode].fRefPoint[idim] += fData[idim][indexPoints[ip]];
+ }
fTNodes[inode].fRefPoint[idim] /= fBucketSize;
}
}
bounds = GetBoundary(tnode);
for(int idim=0; idim<fNDim; idim++) fTNodes[inode].fRefValue /= (bounds[2*idim+1] - bounds[2*idim]);
- indexPoints = GetPointsIndexes(tnode);
// loop points in this terminal node
+ indexPoints = GetPointsIndexes(tnode);
for(int idim=0; idim<fNDim; idim++){
+ fTNodes[inode].fRefPoint[idim] = 0.;
for(int ip = 0; ip<counts; ip++) fTNodes[inode].fRefPoint[idim] += fData[idim][indexPoints[ip]];
fTNodes[inode].fRefPoint[idim] /= counts;
}
-
- //GetStatus();
}
//__________________________________________________________________
void TKDInterpolator::GetStatus()
{
+// Prints the status of the interpolator
+
printf("Interpolator Status :\n");
printf(" Method : %s\n", fStatus&1 ? "INT" : "COG");
printf(" Store : %s\n", fStatus&2 ? "YES" : "NO");
printf(" Weights: %s\n", fStatus&4 ? "YES" : "NO");
-
- printf("nnodes %d\n", fNTNodes); //Number of evaluation data points
- printf("nodes 0x%x\n", fTNodes); //[fNTNodes]
+ return;
+
+ printf("fNTNodes %d\n", fNTNodes); //Number of evaluation data points
for(int i=0; i<fNTNodes; i++){
- printf("\t%d ", i);
+ printf("%d ", i);
for(int idim=0; idim<fNDim; idim++) printf("%f ", fTNodes[i].fRefPoint[idim]);
- printf("[%f] %s\n", fTNodes[i].fRefValue, fTNodes[i].fPDFstatus ? "true" : "false");
- for(int ip=0; ip<3; ip++) printf("p%d[%f] ", ip, fTNodes[i].fPar(ip));
+ printf("[%f] %s\n", fTNodes[i].fRefValue, fTNodes[i].fCov ? "true" : "false");
+ printf("Fit parameters : ");
+ if(!fTNodes[i].fPar){
+ printf("Not defined.\n");
+ continue;
+ }
+ for(int ip=0; ip<3; ip++) printf("p%d[%f] ", ip, (*fTNodes[i].fPar)(ip));
printf("\n");
}
}
//_________________________________________________________________
-Double_t TKDInterpolator::Eval(const Double_t *point, Double_t &result, Double_t &error)
+Double_t TKDInterpolator::Eval(const Double_t *point, Double_t &result, Double_t &error, Bool_t force)
{
// Evaluate PDF for "point". The result is returned in "result" and error in "error". The function returns the chi2 of the fit.
//
Float_t pointF[50]; // local Float_t conversion for "point"
for(int idim=0; idim<fNDim; idim++) pointF[idim] = (Float_t)point[idim];
Int_t node = FindNode(pointF) - fNnodes;
- if((fStatus&1) && fTNodes[node].fPDFstatus) return CookPDF(point, node, result, error); // maybe move to TKDNodeInfo
+ if((fStatus&1) && fTNodes[node].fCov && !force) return fTNodes[node].CookPDF(point, result, error);
// Allocate memory
if(!fBuffer) fBuffer = new Double_t[2*fLambda];
fRefPoints[id] = new Float_t[fNTNodes];
for(int in=0; in<fNTNodes; in++) fRefPoints[id][in] = fTNodes[in].fRefPoint[id];
}
+// for(int in=0; in<fNTNodes; in++){
+// printf("%3d ", in);
+// for(int id=0; id<fNDim; id++) printf("%6.3f ", fTNodes[in].fRefPoint[id]/*fRefPoints[id][in]*/);
+// printf("\n");
+// }
fKDhelper = new TKDTreeIF(fNTNodes, fNDim, 30, fRefPoints);
+ fKDhelper->MakeBoundaries();
}
- if(!fFitter) SetIntInterpolation(kFALSE);
+ if(!fFitter) fFitter = new TLinearFitter(fLambda, Form("hyp%d", fLambda-1));
// generate parabolic for nD
//Float_t alpha = Float_t(2*lambda + 1) / fNTNodes; // the bandwidth or smoothing parameter
Int_t *index, // indexes of NN
ipar, // local looping variable
- npoints = Int_t(1.5*fLambda); // number of data points used for interpolation
+ npoints = Int_t((1.+fAlpha)*fLambda); // number of data points used for interpolation
Float_t *dist, // distances of NN
d, // NN normalized distance
w0, // work
w; // tri-cubic weight function
Double_t sig // bucket error
= TMath::Sqrt(1./fBucketSize);
+
do{
// find nearest neighbors
for(int idim=0; idim<fNDim; idim++) pointF[idim] = (Float_t)point[idim];
}
// add points to fitter
fFitter->ClearPoints();
+ TKDNodeInfo *node = 0x0;
for(int in=0; in<npoints; in++){
+ node = &fTNodes[index[in]];
if(fStatus&1){ // INT
- //for(int idim=0; idim<fNDim; idim++) pointF[idim] = fRefPoints[idim][index[in]];
- Float_t *bounds = GetBoundary(FindNode(fTNodes[index[in]].fRefPoint/*pointF*/));
-
+ Float_t *bounds = GetBoundary(FindNode(node->fRefPoint));
ipar = 0;
for(int idim=0; idim<fNDim; idim++){
fBuffer[ipar++] = .5*(bounds[2*idim] + bounds[2*idim+1]);
for(int jdim=idim+1; jdim<fNDim; jdim++) fBuffer[ipar++] = (bounds[2*idim] + bounds[2*idim+1]) * (bounds[2*jdim] + bounds[2*jdim+1]) * .25;
}
} else { // COG
- for(int idim=0; idim<fNDim; idim++) fBuffer[idim] = fTNodes[index[in]].fRefPoint[idim];
+ Float_t *p = node->fRefPoint;
+ ipar = 0;
+ for(int idim=0; idim<fNDim; idim++){
+ fBuffer[ipar++] = p[idim];
+ for(int jdim=idim; jdim<fNDim; jdim++) fBuffer[ipar++] = p[idim]*p[jdim];
+ }
}
// calculate tri-cubic weighting function
//for(int idim=0; idim<fNDim; idim++) printf("%f ", fBuffer[idim]);
//printf("\nd[%f] w[%f] sig[%f]\n", d, w, sig);
- fFitter->AddPoint(fBuffer, fTNodes[index[in]].fRefValue, fTNodes[index[in]].fRefValue*sig/w);
+ fFitter->AddPoint(fBuffer, node->fRefValue, node->fRefValue*sig/w);
}
npoints += 4;
} while(fFitter->Eval());
Double_t chi2 = fFitter->GetChisquare()/(npoints - 4 - fLambda);
// store results
- if(fStatus&2 && fStatus&1){
- fTNodes[node].fPar = par;
- fTNodes[node].fCov = cov;
- fTNodes[node].fPDFstatus = kTRUE;
- }
+ if(fStatus&2 && fStatus&1) fTNodes[node].Store(par, cov);
// Build df/dpi|x values
Double_t *fdfdp = &fBuffer[fLambda];
return chi2;
}
-// //_________________________________________________________________
-// Double_t TKDInterpolator::Eval1(const Double_t *point, Int_t npoints, Double_t &result, Double_t &error)
-// {
-// // Evaluate PDF at k-dimensional position "point". The initial number of
-// // neighbour estimation points is set to "npoints". The default method
-// // used for interpolation is kCOG.
-//
-// // calculate number of parameters in the parabolic expresion
-// Int_t lambda = 1 + fNDim + fNDim*(fNDim+1)/2;
-//
-// if(!fBuffer) fBuffer = new Double_t[lambda-1];
-// if(!fKDhelper) fKDhelper = new TKDTreeIF(GetNTerminalNodes(), fNDim, npoints, fRefPoints);
-//
-// if(!fFitter) fFitter = new TLinearFitter(lambda, Form("hyp%d", fNDim+1));
-// else fFitter->SetFormula(Form("hyp%d", fNDim+1));
-//
-//
-// Float_t pointF[50];
-// for(int idim=0; idim<fNDim; idim++) pointF[idim] = point[idim];
-// Int_t istart = 0;
-// Int_t *index, ipar;
-// Float_t *bounds, *dist, *w = new Float_t[fNDim];
-// Double_t uncertainty = TMath::Sqrt(1./fBucketSize);
-// fFitter->ClearPoints();
-// do{
-// if(!fKDhelper->FindNearestNeighbors(pointF, npoints+1, index, dist)){
-// Error("Eval()", Form("Failed retriving %d neighbours for point:", npoints));
-// for(int idim=0; idim<fNDim; idim++) printf("%f ", point[idim]);
-// printf("\n");
-// return -1;
-// }
-// for(int in=istart; in<npoints; in++){
-// for(int idim=0; idim<fNDim; idim++) w[idim] = fRefPoints[idim][index[in]];
-// bounds = GetBoundary(FindNode(w));
-//
-// ipar = 0;
-// for(int idim=0; idim<fNDim; idim++){
-// fBuffer[ipar++] = .5*(bounds[2*idim] + bounds[2*idim+1]);
-// fBuffer[ipar++] = (bounds[2*idim]*bounds[2*idim] + bounds[2*idim] * bounds[2*idim+1] + bounds[2*idim+1] * bounds[2*idim+1])/3.;
-// for(int jdim=idim+1; jdim<fNDim; jdim++) fBuffer[ipar++] = (bounds[2*idim] + bounds[2*idim+1]) * (bounds[2*jdim] + bounds[2*jdim+1]) * .25;
-// }
-//
-// fFitter->AddPoint(fBuffer, fRefValues[index[in]], fRefValues[index[in]]*uncertainty);
-// }
-// istart = npoints;
-// npoints += 4;
-// } while(fFitter->Eval());
-// delete [] w;
-//
-// // calculate evaluation
-// // fFitter->PrintResults(3);
-// TMatrixD cov(lambda, lambda);
-// TVectorD par(lambda);
-// fFitter->GetCovarianceMatrix(cov);
-// fFitter->GetParameters(par);
-//
-// // Build temporary array to keep values df/dpi|x
-// Double_t f[100];
-// ipar = 0;
-// f[ipar++] = 1.;
-// for(int idim=0; idim<fNDim; idim++){
-// f[ipar++] = point[idim];
-// for(int jdim=idim; jdim<fNDim; jdim++) f[ipar++] = point[idim]*point[jdim];
-// }
-// result =0.; error = 0.;
-// for(int i=0; i<lambda; i++){
-// result += f[i]*par[i];
-// for(int j=0; j<lambda; j++) error += f[i]*f[j]*cov(i,j);
-// }
-// error = TMath::Sqrt(error);
-// Double_t chi2 = fFitter->GetChisquare()/(npoints - 4 - lambda);
-//
-// for(int ipar=0; ipar<lambda; ipar++) printf("%d %8.6e %8.6e\n", ipar, par[ipar], TMath::Sqrt(cov(ipar, ipar)));
-// printf("result %6.3f +- %6.3f [%f]\n", result, error, chi2);
-// return chi2;
-// }
-
-
//_________________________________________________________________
void TKDInterpolator::DrawNodes(UInt_t ax1, UInt_t ax2, Int_t depth)
{
//printf("depth %d nodes %d\n", depth, nnodes);
- TH2 *h2 = 0x0;
- if(!(h2 = (TH2S*)gROOT->FindObject("hNodes"))) h2 = new TH2S("hNodes", "", 100, fRange[2*ax1], fRange[2*ax1+1], 100, fRange[2*ax2], fRange[2*ax2+1]);
+ TH2 *h2 = new TH2S("hNodes", "", 100, fRange[2*ax1], fRange[2*ax1+1], 100, fRange[2*ax2], fRange[2*ax2+1]);
h2->GetXaxis()->SetTitle(Form("x_{%d}", ax1));
h2->GetYaxis()->SetTitle(Form("x_{%d}", ax2));
h2->Draw();
- const Float_t border = 0.;//1.E-4;
- TBox *node_array = new TBox[nnodes], *node;
+ const Float_t kBorder = 0.;//1.E-4;
+ TBox *nodeArray = new TBox[nnodes], *node;
Float_t *bounds = 0x0;
nnodes = 0;
for(int inode = 0; inode <= 2*fNnodes; inode++){
if(!IsTerminal(inode)) continue;
} else if((inode+1) >> depth != 1) continue;
- node = &node_array[nnodes++];
+ node = &nodeArray[nnodes++];
//node = new TBox(bounds[2*ax1]+border, bounds[2*ax2]+border, bounds[2*ax1+1]-border, bounds[2*ax2+1]-border);
node->SetFillStyle(3002);
- node->SetFillColor(50+Int_t(gRandom->Uniform()*50.));
+ node->SetFillColor(50+inode/*Int_t(gRandom->Uniform()*50.)*/);
bounds = GetBoundary(inode);
- node->DrawBox(bounds[2*ax1]+border, bounds[2*ax2]+border, bounds[2*ax1+1]-border, bounds[2*ax2+1]-border);
+ node->DrawBox(bounds[2*ax1]+kBorder, bounds[2*ax2]+kBorder, bounds[2*ax1+1]-kBorder, bounds[2*ax2+1]-kBorder);
}
if(depth != -1) return;
// Draw reference points
- TGraph *ref = new TGraph(GetNTerminalNodes());
+ TGraph *ref = new TGraph(fNTNodes);
ref->SetMarkerStyle(3);
ref->SetMarkerSize(.7);
ref->SetMarkerColor(2);
- for(int inode = 0; inode < GetNTerminalNodes(); inode++) ref->SetPoint(inode, fTNodes[inode].fRefPoint[ax1], fTNodes[inode].fRefPoint[ax2]);
+ for(int inode = 0; inode < fNTNodes; inode++) ref->SetPoint(inode, fTNodes[inode].fRefPoint[ax1], fTNodes[inode].fRefPoint[ax2]);
ref->Draw("p");
return;
}
// This function creates some graphical objects
// but don't delete it. Abusing this function may cause memory leaks !
- if(tnode < 0 || tnode >= GetNTerminalNodes()){
+ if(tnode < 0 || tnode >= fNTNodes){
Warning("DrawNode()", Form("Terminal node %d outside defined range.", tnode));
return;
}
TBox *n = new TBox(bounds[2*ax1], bounds[2*ax2], bounds[2*ax1+1], bounds[2*ax2+1]);
n->SetFillStyle(0);
- if(gPad) gPad->Clear();
g->Draw("ap");
m->Draw();
n->Draw();
//__________________________________________________________________
-void TKDInterpolator::SetIntInterpolation(const Bool_t on)
+void TKDInterpolator::SetInterpolationMethod(const Bool_t on)
{
-// Set interpolation bit to "on" and build/delete memory
+// Set interpolation bit to "on".
if(on) fStatus += fStatus&1 ? 0 : 1;
else fStatus += fStatus&1 ? -1 : 0;
- TString formula;
- if(on) formula = Form("hyp%d", fLambda-1);
- else {
- formula = "1";
- for(int idim=0; idim<fNDim; idim++){
- formula += Form("++x[%d]", idim);
- for(int jdim=idim; jdim<fNDim; jdim++) formula += Form("++x[%d]*x[%d]", idim, jdim);
- }
- }
- if(!fFitter) fFitter = new TLinearFitter(fLambda, formula.Data());
- else fFitter->SetFormula(formula.Data());
}
//_________________________________________________________________
-void TKDInterpolator::SetSetStore(const Bool_t on)
+void TKDInterpolator::SetStore(const Bool_t on)
{
-// Set store bit to "on" and build/delete memory
+// Set store bit to "on"
- if(on){
- fStatus += fStatus&2 ? 0 : 2;
-/* if(!fCov){
- fPDFstatus = new Bool_t[fNTNodes];
- fCov = new TMatrixD[fNTNodes];
- fPar = new TVectorD[fNTNodes];
- for(int i=0; i<fNTNodes; i++){
- fPDFstatus[i] = kFALSE;
- fCov[i].ResizeTo(fLambda, fLambda);
- fPar[i].ResizeTo(fLambda);
- }
- }*/
- } else {
- fStatus += fStatus&2 ? -2 : 0;
-/* if(fCov){
- delete [] fPar;
- delete [] fCov;
- delete [] fPDFstatus;
- }*/
- }
+ if(on) fStatus += fStatus&2 ? 0 : 2;
+ else fStatus += fStatus&2 ? -2 : 0;
}
//_________________________________________________________________
-void TKDInterpolator::SetUseWeights(const Bool_t on)
+void TKDInterpolator::SetWeights(const Bool_t on)
{
+// Set weights bit to "on"
+
if(on) fStatus += fStatus&4 ? 0 : 4;
else fStatus += fStatus&4 ? -4 : 0;
}
-
-
-//_________________________________________________________________
-Double_t TKDInterpolator::CookPDF(const Double_t *point, const Int_t node, Double_t &result, Double_t &error)
-{
-// Recalculate the PDF for one node from the results of interpolation (parameters and covariance matrix)
-
- Info("CookPDF()", Form("Called for node %d", node));
-
- if(!fBuffer) fBuffer = new Double_t[2*fLambda];
- Double_t *fdfdp = &fBuffer[fLambda];
- Int_t ipar = 0;
- fdfdp[ipar++] = 1.;
- for(int idim=0; idim<fNDim; idim++){
- fdfdp[ipar++] = point[idim];
- for(int jdim=idim; jdim<fNDim; jdim++) fdfdp[ipar++] = point[idim]*point[jdim];
- }
-
- // calculate estimation
- result =0.; error = 0.;
- for(int i=0; i<fLambda; i++){
- result += fdfdp[i]*fTNodes[node].fPar(i);
- for(int j=0; j<fLambda; j++) error += fdfdp[i]*fdfdp[j]*fTNodes[node].fCov(i,j);
- }
- error = TMath::Sqrt(error);
- printf("result[CookPDF] %6.3f +- %6.3f\n", result, error);
-
- return 0.;
-}
-
#ifndef ROOT_TKDTree
#include "TKDTree.h"
#endif
-#ifndef ROOT_TVectorD
-#include "TVectorD.h"
-#endif
-#ifndef ROOT_TMatrixD
-#include "TMatrixD.h"
-#endif
+// Non parametric interpolation class based on local polinomial regression.
+// The class can be used to approximate PDF together with TKDTree or for
+// general regression when the data points are given.
+template <typename Value> class TVectorT;
+typedef struct TVectorT<Double_t> TVectorD;
+template <typename Value> class TMatrixT;
+typedef class TMatrixT<Double_t> TMatrixD;
+template <typename Index, typename Value> class TKDTree;
+typedef class TKDTreeIF<Int_t, Float_t> TKDTreeIF;
class TTree;
class TLinearFitter;
class TKDInterpolator : public TKDTreeIF
{
-public:
- struct TKDNodeInfo
- {
- TKDNodeInfo(const Int_t ndim = 0);
- ~TKDNodeInfo();
- void Build(const Int_t ndim);
-
- Int_t fNDim; // data dimension
- Float_t *fRefPoint; //[fNDim] node's COG
- Float_t fRefValue; // measured value for node
- TMatrixD fCov; // interpolator covariance matrix
- TVectorD fPar; // interpolator parameters
- Bool_t fPDFstatus; // status bit for node's PDF
-
- ClassDef(TKDNodeInfo, 1) // node info for interpolator
- };
public:
TKDInterpolator();
TKDInterpolator(TTree *t, const Char_t *var, const Char_t *cut = 0, UInt_t bsize = 100, Long64_t nentries = 1000000000, Long64_t firstentry = 0);
TKDInterpolator(Int_t npoints, Int_t ndim, UInt_t bsize, Float_t **data);
~TKDInterpolator();
- Double_t Eval(const Double_t *point, Double_t &result, Double_t &error);
- inline Bool_t GetCOGPoint(Int_t node, Float_t *coord, Float_t &val, Float_t &error) const ;
+ Double_t Eval(const Double_t *point, Double_t &result, Double_t &error, Bool_t force = kFALSE);
+ Float_t GetAlpha() const {return fAlpha;}
+ inline Bool_t GetCOGPoint(Int_t node, Float_t *coord, Float_t &val, Float_t &error) const;
inline Bool_t GetDataPoint(Int_t n, Float_t *p) const;
TKDTreeIF* GetHelper() {return fKDhelper;}
- inline Bool_t GetIntInterpolation() const {return fStatus&1;}
- inline Bool_t GetSetStore() const {return fStatus&2;}
- inline Bool_t GetUseWeights() const {return fStatus&4;}
+ Bool_t GetInterpolationMethod() const {return fStatus&1;}
+ Int_t GetNTNodes() const {return fNTNodes;}
+ Bool_t GetStore() const {return fStatus&2;}
+ Bool_t GetWeights() const {return fStatus&4;}
void DrawNodes(UInt_t ax1 = 0, UInt_t ax2 = 1, Int_t depth = -1);
void DrawNode(Int_t tnode, UInt_t ax1 = 0, UInt_t ax2 = 1);
void GetStatus();
- void SetIntInterpolation(const Bool_t on = kTRUE);
- void SetSetStore(const Bool_t on = kTRUE);
- void SetUseWeights(const Bool_t on = kTRUE);
+ void SetAlpha(const Float_t a){if(a>0.) fAlpha = a;}
+ void SetInterpolationMethod(const Bool_t on = kTRUE);
+ void SetStore(const Bool_t on = kTRUE);
+ void SetWeights(const Bool_t on = kTRUE);
private:
TKDInterpolator(const TKDInterpolator &);
TKDInterpolator& operator=(const TKDInterpolator &);
void Build();
- Double_t CookPDF(const Double_t *point, const Int_t node, Double_t &result, Double_t &error);
+public:
+ class TKDNodeInfo
+ {
+ public:
+ TKDNodeInfo(const Int_t ndim = 0);
+ virtual ~TKDNodeInfo();
+ void Build(const Int_t ndim);
+ Double_t CookPDF(const Double_t *point, Double_t &result, Double_t &error);
+ void Store(const TVectorD &par, const TMatrixD &cov);
+
+ Int_t fNDim; // data dimension
+ Float_t *fRefPoint; //[fNDim] node's COG
+ Float_t fRefValue; // measured value for node
+ TMatrixD *fCov; // interpolator covariance matrix
+ TVectorD *fPar; // interpolator parameters
+
+ private:
+ TKDNodeInfo(const TKDNodeInfo &);
+ TKDNodeInfo& operator=(const TKDNodeInfo &);
+
+ ClassDef(TKDNodeInfo, 1) // node info for interpolator
+ };
+
protected:
Int_t fNTNodes; //Number of evaluation data points
TKDNodeInfo *fTNodes; //[fNTNodes] interpolation node
-// Float_t *fRefValues; //[fNTNodes]
-// TMatrixD *fCov; //[fNTNodes] cov matrix array for nodes
-// TVectorD *fPar; //[fNTNodes] parameters array for nodes
-// Bool_t *fPDFstatus; //[fNTNodes] status bit for node's PDF
private:
UChar_t fStatus; // status of the interpolator
- Int_t fLambda; // number of parameters in polynom
- Int_t fDepth; //! depth of the KD Tree structure used
+ UChar_t fLambda; // number of parameters in polynom
+ Short_t fDepth; //! depth of the KD Tree structure used
+ Float_t fAlpha; // alpha parameter
Float_t **fRefPoints; //! temporary storage of COG data
Double_t *fBuffer; //! working space [2*fLambda]
TKDTreeIF *fKDhelper; //! kNN finder
Bool_t TKDInterpolator::GetDataPoint(Int_t n, Float_t *p) const
{
if(n < 0 || n >= fNpoints) return kFALSE;
-
+ if(!fData) return kFALSE;
+
for(int i=0; i<fNDim; i++) p[i] = fData[i][n];
return kTRUE;
}
#ifndef R__ALPHA
templateClassImp(TKDTree)
-templateClassImp(TKDNode)
#endif
//////////////////////////////////////////////////////////////////////
// Memory setup of protected data members:
// - after are the terminal nodes
// fNodes : array of primary nodes
///////////////////////////////////////////////////////////////////////
+
+#include "malloc.h"
+int memory()
+{
+ static struct mallinfo debug;
+ debug = mallinfo();
+ //printf("arena[%d] usmblks[%d] uordblks[%d] fordblks[%d]\n", debug.arena, debug.usmblks, debug.uordblks, debug.fordblks);
+ return debug.uordblks;
+}
+
//_________________________________________________________________
template <typename Index, typename Value>
TKDTree<Index, Value>::TKDTree() :
,fNDimm(0)
,fNpoints(0)
,fBucketSize(0)
- ,fNodes(0x0)
+ ,fAxis(0x0)
+ ,fValue(0x0)
,fRange(0x0)
,fData(0x0)
,fBoundaries(0x0)
,fNDimm(2*ndim)
,fNpoints(npoints)
,fBucketSize(bsize)
- ,fNodes(0x0)
+ ,fAxis(0x0)
+ ,fValue(0x0)
,fRange(0x0)
,fData(data) //Columnwise!!!!!
,fBoundaries(0x0)
{
// Allocate data by hand. See TKDTree(TTree*, const Char_t*) for an automatic method.
+ //printf("start building kdTree %d\n", memory());
Build();
+ //printf("finish building kdTree %d\n", memory());
}
//_________________________________________________________________
if (fDistBuffer) delete [] fDistBuffer;
if (fkNNdist) delete [] fkNNdist;
if (fkNN) delete [] fkNN;
- if (fNodes) delete [] fNodes;
+ if (fAxis) delete [] fAxis;
+ if (fValue) delete [] fValue;
if (fIndPoints) delete [] fIndPoints;
if (fRange) delete [] fRange;
if (fBoundaries) delete [] fBoundaries;
fRange = new Value[2*fNDim];
fIndPoints= new Index[fNpoints];
for (Index i=0; i<fNpoints; i++) fIndPoints[i] = i;
- fNodes = new TKDNode<Index, Value>[fNnodes];
+ fAxis = new UChar_t[fNnodes];
+ fValue = new Value[fNnodes];
//
fCrossNode = (1<<(fRowT0+1))-1;
if (fCrossNode<fNnodes) fCrossNode = 2*fCrossNode+1;
Int_t crow = rowStack[currentIndex];
Int_t cpos = posStack[currentIndex];
Int_t cnode = nodeStack[currentIndex];
- TKDNode<Index, Value> * node = &(fNodes[cnode]);
//printf("currentIndex %d npoints %d node %d\n", currentIndex, npoints, cnode);
//
// divide points
maxspread=tempspread;
axspread = idim;
}
- if(cnode==0) {fRange[2*idim] = min; fRange[2*idim+1] = max;}
+ if(cnode) continue;
+ //printf("set %d %6.3f %6.3f\n", idim, min, max);
+ fRange[2*idim] = min; fRange[2*idim+1] = max;
}
array = fData[axspread];
KOrdStat(npoints, array, nleft, fIndPoints+cpos);
- node->fAxis = axspread;
- node->fValue = array[fIndPoints[cpos+nleft]];
+ fAxis[cnode] = axspread;
+ fValue[cnode] = array[fIndPoints[cpos+nleft]];
//printf("Set node %d : ax %d val %f\n", cnode, node->fAxis, node->fValue);
//
//
//_________________________________________________________________
template <typename Index, typename Value>
-Int_t TKDTree<Index, Value>::FindNearestNeighbors(const Value *point, const Int_t k, Index *&in, Value *&d)
+Bool_t TKDTree<Index, Value>::FindNearestNeighbors(const Value *point, const Int_t k, Index *&in, Value *&d)
{
// Find "k" nearest neighbors to "point".
//
// increasing order of the distance to "point" and the maxim distance
// in "d".
//
-// The array "in" is managed internally by the TKDTree.
+// The arrays "in" and "d" are managed internally by the TKDTree.
Index inode = FindNode(point);
if(inode < fNnodes){
fIndBuffer = new Index[fBucketSize];
}
if(fkNNdim < k){
- //if(debug>=1){
+ if(debug>=1){
if(fkNN) printf("Reallocate memory %d -> %d \n", fkNNdim, 2*k);
else printf("Allocate %d memory\n", 2*k);
- //}
+ }
fkNNdim = 2*k;
if(fkNN){
delete [] fkNN;
Index itmp, jtmp; Value ftmp, gtmp;
// calculate number of boundaries with the data domain.
- Index nBounds = 0;
if(!fBoundaries) MakeBoundaries();
Value *bounds = &fBoundaries[inode*2*fNDim];
+ Index nBounds = 0;
for(int idim=0; idim<fNDim; idim++){
- if(bounds[2*idim] == fRange[2*idim]) nBounds++;
- if(bounds[2*idim+1] == fRange[2*idim+1]) nBounds++;
+ if((bounds[2*idim] - fRange[2*idim]) < 1.E-10) nBounds++;
+ if((bounds[2*idim+1] - fRange[2*idim+1]) < 1.E-10) nBounds++;
}
if(debug>=1) printf("Calculate boundaries [nBounds = %d]\n", nBounds);
-
+
+
// traverse tree
- TKDNode<Index, Value> *node;
+ UChar_t ax;
+ Value val, dif;
+ Int_t nAllNodes = fNnodes + GetNTNodes();
Int_t nodeStack[128], nodeIn[128];
Index currentIndex = 0;
nodeStack[0] = inode;
if(debug>=1) printf("Analyse tnode %d entry %d\n", tnode, entry);
// check if node is still eligible
- node = &fNodes[tnode/2 + (tnode%2) - 1];
- if((TMath::Abs(point[node->fAxis] - node->fValue) > fkNNdist[k-1])
- &&
- ((point[node->fAxis] > node->fValue && tnode%2) ||
- (point[node->fAxis] < node->fValue && !tnode%2))) {
- //printf("\tREMOVE NODE %d\n", tnode/2 + (tnode%2) - 1);
+ Int_t inode = (tnode-1)>>1; //tnode/2 + (tnode%2) - 1;
+ ax = fAxis[inode];
+ val = fValue[inode];
+ dif = point[ax] - val;
+ if((TMath::Abs(dif) > fkNNdist[k-1]) &&
+ ((dif > 0. && (tnode&1)) || (dif < 0. && !(tnode&1)))) {
+ if(debug>=1) printf("\tremove %d\n", (tnode-1)>>1);
// mark bound
nBounds++;
}
// register parent
- Int_t parent_node = tnode/2 + (tnode%2) - 1;
- if(parent_node >= 0 && entry != parent_node){
+ Int_t pn = (tnode-1)>>1;//tnode/2 + (tnode%2) - 1;
+ if(pn >= 0 && entry != pn){
// check if parent node is eligible at all
- node = &fNodes[parent_node];
- if(TMath::Abs(point[node->fAxis] - node->fValue) > fkNNdist[k-1]){
+ if(TMath::Abs(point[fAxis[pn]] - fValue[pn]) > fkNNdist[k-1]){
// mark bound
nBounds++;
// end all recursions
if(nBounds==2 * fNDim) break;
}
currentIndex++;
- nodeStack[currentIndex]=tnode/2 + (tnode%2) - 1;
+ nodeStack[currentIndex]=pn;
nodeIn[currentIndex]=tnode;
if(debug>=2) printf("\tregister %d\n", nodeStack[currentIndex]);
}
+ if(IsTerminal(tnode)) continue;
// register children nodes
- Int_t child_node;
+ Int_t cn;
Bool_t kAllow[] = {kTRUE, kTRUE};
- node = &fNodes[tnode];
- if(TMath::Abs(point[node->fAxis] - node->fValue) > fkNNdist[k-1]){
- if(point[node->fAxis] > node->fValue) kAllow[0] = kFALSE;
+ ax = fAxis[tnode];
+ val = fValue[tnode];
+ if(TMath::Abs(point[ax] - val) > fkNNdist[k-1]){
+ if(point[ax] > val) kAllow[0] = kFALSE;
else kAllow[1] = kFALSE;
}
for(int ic=1; ic<=2; ic++){
if(!kAllow[ic-1]) continue;
- child_node = (tnode*2)+ic;
- if(child_node < fNnodes + GetNTerminalNodes() && entry != child_node){
+ cn = (tnode<<1)+ic;
+ if(cn < nAllNodes && entry != cn){
currentIndex++;
- nodeStack[currentIndex] = child_node;
+ nodeStack[currentIndex] = cn;
nodeIn[currentIndex]=tnode;
if(debug>=2) printf("\tregister %d\n", nodeStack[currentIndex]);
}
in = fkNN;
d = fkNNdist;
- return nCalculations; //kTRUE;
+ return kTRUE;
}
Index TKDTree<Index, Value>::FindNode(const Value * point){
//
// find the terminal node to which point belongs
-
+
Index stackNode[128], inode;
Int_t currentIndex =0;
stackNode[0] = 0;
- //
while (currentIndex>=0){
inode = stackNode[currentIndex];
- currentIndex--;
if (IsTerminal(inode)) return inode;
- TKDNode<Index, Value> & node = fNodes[inode];
- if (point[node.fAxis]<=node.fValue){
+ currentIndex--;
+ if (point[fAxis[inode]]<=fValue[inode]){
currentIndex++;
- stackNode[currentIndex]=(inode*2)+1;
+ stackNode[currentIndex]=(inode<<1)+1;
}
- if (point[node.fAxis]>=node.fValue){
+ if (point[fAxis[inode]]>=fValue[inode]){
currentIndex++;
- stackNode[currentIndex]=(inode*2)+2;
+ stackNode[currentIndex]=(inode+1)<<1;
}
}
continue;
}
- TKDNode<Index, Value> & node = fNodes[inode];
- if (point[node.fAxis]<=node.fValue){
+ if (point[fAxis[inode]]<=fValue[inode]){
currentIndex++;
stackNode[currentIndex]=(inode*2)+1;
}
- if (point[node.fAxis]>=node.fValue){
+ if (point[fAxis[inode]]>=fValue[inode]){
currentIndex++;
stackNode[currentIndex]=(inode*2)+2;
}
currentIndex--;
if (!IsTerminal(inode)){
// not terminal
- TKDNode<Index, Value> * node = &(fNodes[inode]);
- if (point[node->fAxis] - delta[node->fAxis] < node->fValue) {
+ //TKDNode<Index, Value> * node = &(fNodes[inode]);
+ if (point[fAxis[inode]] - delta[fAxis[inode]] < fValue[inode]) {
currentIndex++;
stackNode[currentIndex]= (inode*2)+1;
}
- if (point[node->fAxis] + delta[node->fAxis] >= node->fValue){
+ if (point[fAxis[inode]] + delta[fAxis[inode]] >= fValue[inode]){
currentIndex++;
stackNode[currentIndex]= (inode*2)+2;
}
}
}
//
- TKDNode<Index, Value> * node = &(fNodes[inode]);
- if (point[node->fAxis] - delta[node->fAxis] < node->fValue) {
+ // TKDNode<Index, Value> * node = &(fNodes[inode]);
+ if (point[fAxis[inode]] - delta[fAxis[inode]] < fValue[inode]) {
currentIndex++;
stackNode[currentIndex]= (inode<<1)+1;
- if (point[node->fAxis] + delta[node->fAxis] > node->fValue)
- stackStatus[currentIndex]= status | (1<<(2*node->fAxis));
+ if (point[fAxis[inode]] + delta[fAxis[inode]] > fValue[inode])
+ stackStatus[currentIndex]= status | (1<<(2*fAxis[inode]));
}
- if (point[node->fAxis] + delta[node->fAxis] >= node->fValue){
+ if (point[fAxis[inode]] + delta[fAxis[inode]] >= fValue[inode]){
currentIndex++;
stackNode[currentIndex]= (inode<<1)+2;
- if (point[node->fAxis] - delta[node->fAxis]<node->fValue)
- stackStatus[currentIndex]= status | (1<<(2*node->fAxis+1));
+ if (point[fAxis[inode]] - delta[fAxis[inode]]<fValue[inode])
+ stackStatus[currentIndex]= status | (1<<(2*fAxis[inode]+1));
}
}
if (fData){
// Build boundaries for each node.
- if(range) memcpy(fRange, range, 2*fNDim*sizeof(Value));
+ if(range) memcpy(fRange, range, fNDimm*sizeof(Value));
// total number of nodes including terminal nodes
- Int_t totNodes = fNnodes + GetNTerminalNodes();
- fBoundaries = new Value[totNodes*2*fNDim];
- Info("MakeBoundaries(Value*)", Form("Allocate boundaries for %d nodes", totNodes));
+ Int_t totNodes = fNnodes + GetNTNodes();
+ fBoundaries = new Value[totNodes*fNDimm];
+ //Info("MakeBoundaries(Value*)", Form("Allocate boundaries for %d nodes", totNodes));
+
// loop
- Int_t child_index;
+ Value *tbounds = 0x0, *cbounds = 0x0;
+ Int_t cn;
for(int inode=fNnodes-1; inode>=0; inode--){
- memcpy(&fBoundaries[inode*2*fNDim], fRange, 2*fNDim*sizeof(Value));
+ tbounds = &fBoundaries[inode*fNDimm];
+ memcpy(tbounds, fRange, fNDimm*sizeof(Value));
// check left child node
- child_index = 2*inode+1;
- if(IsTerminal(child_index)) CookBoundaries(inode, kTRUE);
- for(int idim=0; idim<fNDim; idim++) fBoundaries[2*fNDim*inode+2*idim] = fBoundaries[2*fNDim*child_index+2*idim];
+ cn = (inode<<1)+1;
+ if(IsTerminal(cn)) CookBoundaries(inode, kTRUE);
+ cbounds = &fBoundaries[fNDimm*cn];
+ for(int idim=0; idim<fNDim; idim++) tbounds[idim<<1] = cbounds[idim<<1];
// check right child node
- child_index = 2*inode+2;
- if(IsTerminal(child_index)) CookBoundaries(inode, kFALSE);
- for(int idim=0; idim<fNDim; idim++) fBoundaries[2*fNDim*inode+2*idim+1] = fBoundaries[2*fNDim*child_index+2*idim+1];
+ cn = (inode+1)<<1;
+ if(IsTerminal(cn)) CookBoundaries(inode, kFALSE);
+ cbounds = &fBoundaries[fNDimm*cn];
+ for(int idim=0; idim<fNDim; idim++) tbounds[(idim<<1)+1] = cbounds[(idim<<1)+1];
}
}
//_________________________________________________________________
template <typename Index, typename Value>
-void TKDTree<Index, Value>::CookBoundaries(Int_t parent_node, Bool_t LEFT)
+void TKDTree<Index, Value>::CookBoundaries(const Int_t node, Bool_t LEFT)
{
// define index of this terminal node
- Int_t index = 2 * parent_node + (LEFT ? 1 : 2);
+ Int_t index = (node<<1) + (LEFT ? 1 : 2);
+ //Info("CookBoundaries()", Form("Node %d", index));
// build and initialize boundaries for this node
- //printf("\tAllocate terminal node %d\n", index);
- memcpy(&fBoundaries[2*fNDim*index], fRange, 2*fNDim*sizeof(Value));
+ Value *tbounds = &fBoundaries[fNDimm*index];
+ memcpy(tbounds, fRange, fNDimm*sizeof(Value));
Bool_t flag[256]; // cope with up to 128 dimensions
- memset(flag, kFALSE, 2*fNDim);
+ memset(flag, kFALSE, fNDimm);
Int_t nvals = 0;
// recurse parent nodes
- TKDNode<Index, Value> *node = 0x0;
- while(parent_node >= 0 && nvals < 2 * fNDim){
- node = &(fNodes[parent_node]);
+ Int_t pn = node;
+ while(pn >= 0 && nvals < fNDimm){
if(LEFT){
- if(!flag[2*node->fAxis+1]) {
- fBoundaries[2*fNDim*index+2*node->fAxis+1] = node->fValue;
- flag[2*node->fAxis+1] = kTRUE;
+ index = (fAxis[pn]<<1)+1;
+ if(!flag[index]) {
+ tbounds[index] = fValue[pn];
+ flag[index] = kTRUE;
nvals++;
}
} else {
- if(!flag[2*node->fAxis]) {
- fBoundaries[2*fNDim*index+2*node->fAxis] = node->fValue;
- flag[2*node->fAxis] = kTRUE;
+ index = fAxis[pn]<<1;
+ if(!flag[index]) {
+ tbounds[index] = fValue[pn];
+ flag[index] = kTRUE;
nvals++;
}
}
- LEFT = parent_node%2;
- parent_node = parent_node/2 + (parent_node%2) - 1;
+ LEFT = pn&1;
+ pn = (pn - 1)>>1;
}
}
#include "TMath.h"
-template <typename Index, typename Value>
-struct TKDNode{
- Char_t fAxis;
- Value fValue;
-
- ClassDef(TKDNode, 1) // TKDTree node structure
-};
+Int_t memory();
+
template <typename Index, typename Value> class TKDTree : public TObject
{
~TKDTree();
// getters
- inline Index* GetPointsIndexes(Int_t node) const {
+ inline Index* GetPointsIndexes(Int_t node) const {
if(node < fNnodes) return 0x0;
Int_t offset = (node >= fCrossNode) ? (node-fCrossNode)*fBucketSize : fOffset+(node-fNnodes)*fBucketSize;
return &fIndPoints[offset];
}
- inline Char_t GetNodeAxis(Int_t id) const {return (id < 0 || id >= fNnodes) ? 0 : fNodes[id].fAxis;}
- inline Value GetNodeValue(Int_t id) const {return (id < 0 || id >= fNnodes) ? 0 : fNodes[id].fValue;}
- inline Int_t GetNNodes() const {return fNnodes;}
- inline Int_t GetNTerminalNodes() const {return fNpoints/fBucketSize + ((fNpoints%fBucketSize)?1:0);}
- inline Value* GetBoundaries();
- inline Value* GetBoundary(const Int_t node);
- static Int_t GetIndex(Int_t row, Int_t collumn){return collumn+(1<<row);}
- static inline void GetCoord(Int_t index, Int_t &row, Int_t &collumn){for (row=0; index>=(16<<row);row+=4); for (; index>=(2<<row);row++);collumn= index-(1<<row);};
- Int_t FindNearestNeighbors(const Value *point, const Int_t kNN, Index *&i, Value *&d);
- Index FindNode(const Value * point);
- void FindPoint(Value * point, Index &index, Int_t &iter);
- void FindInRangeA(Value * point, Value * delta, Index *res , Index &npoints,Index & iter, Int_t bnode);
- void FindInRangeB(Value * point, Value * delta, Index *res , Index &npoints,Index & iter, Int_t bnode);
- inline void FindBNodeA(Value * point, Value * delta, Int_t &inode);
- inline Bool_t IsTerminal(Index inode){return (inode>=fNnodes);}
+ inline UChar_t GetNodeAxis(Int_t id) const {return (id < 0 || id >= fNnodes) ? 0 : fAxis[id];}
+ inline Value GetNodeValue(Int_t id) const {return (id < 0 || id >= fNnodes) ? 0 : fValue[id];}
+ inline Int_t GetNNodes() const {return fNnodes;}
+ inline Int_t GetNTNodes() const {return fNpoints/fBucketSize + ((fNpoints%fBucketSize)?1:0);}
+ inline Value* GetBoundaries();
+ inline Value* GetBoundary(const Int_t node);
+ static Int_t GetIndex(Int_t row, Int_t collumn){return collumn+(1<<row);}
+ static inline void GetCoord(Int_t index, Int_t &row, Int_t &collumn){for (row=0; index>=(16<<row);row+=4); for (; index>=(2<<row);row++);collumn= index-(1<<row);};
+ Bool_t FindNearestNeighbors(const Value *point, const Int_t kNN, Index *&i, Value *&d);
+ Index FindNode(const Value * point);
+ void FindPoint(Value * point, Index &index, Int_t &iter);
+ void FindInRangeA(Value * point, Value * delta, Index *res , Index &npoints,Index & iter, Int_t bnode);
+ void FindInRangeB(Value * point, Value * delta, Index *res , Index &npoints,Index & iter, Int_t bnode);
+ inline void FindBNodeA(Value * point, Value * delta, Int_t &inode);
+ inline Bool_t IsTerminal(Index inode){return (inode>=fNnodes);}
Value KOrdStat(Index ntotal, Value *a, Index k, Index *index);
void MakeBoundaries(Value *range = 0x0);
void SetData(Index npoints, Index ndim, UInt_t bsize, Value **data);
private:
TKDTree(const TKDTree &); // not implemented
TKDTree<Index, Value>& operator=(const TKDTree<Index, Value>&); // not implemented
- void CookBoundaries(Int_t parent_node, Bool_t left);
+ void CookBoundaries(const Int_t node, Bool_t left);
protected:
Index fNDimm; // dummy 2*fNDim
Index fNpoints; // number of multidimensional points
Index fBucketSize; // limit statistic for nodes
- TKDNode<Index, Value> *fNodes; //[fNnodes] nodes descriptors array
+ UChar_t *fAxis; //[fNnodes] nodes cutting axis
+ Value *fValue; //[fNnodes] nodes cutting value
Value *fRange; //[fNDimm] range of data for each dimension
Value **fData; //! data points
Value *fBoundaries;//! nodes boundaries - check class doc
//
inode =0;
for (;inode<fNnodes;){
- TKDNode<Index, Value> & node = fNodes[inode];
- if (TMath::Abs(point[node.fAxis] - node.fValue)<delta[node.fAxis]) break;
- inode = (point[node.fAxis] < node.fValue) ? (inode*2)+1: (inode*2)+2;
+ if (TMath::Abs(point[fAxis[inode]] - fValue[inode])<delta[fAxis[inode]]) break;
+ inode = (point[fAxis[inode]] < fValue[inode]) ? (inode*2)+1: (inode*2)+2;
}
}
--- /dev/null
+SRCS= TKDTree.cxx TKDInterpolator.cxx TKDSpline.cxx
+
+HDRS= $(SRCS:.cxx=.h)
+
+DHDR:=StatLinkDef.h
git://git.uio.no / u / mrichter / AliRoot.git / commitdiff