CPU and Memory tests, coding violations fixed, library
authorabercuci <abercuci@f7af4fe6-9843-0410-8265-dc069ae4e863>
Tue, 23 Oct 2007 10:02:55 +0000 (10:02 +0000)
committerabercuci <abercuci@f7af4fe6-9843-0410-8265-dc069ae4e863>
Tue, 23 Oct 2007 10:02:55 +0000 (10:02 +0000)
name modified

STAT/TKDInterpolator.cxx
STAT/TKDInterpolator.h
STAT/TKDTree.cxx
STAT/TKDTree.h
STAT/libSTAT.pkg [new file with mode: 0644]

index d8b6b90..1d64336 100644 (file)
@@ -1,23 +1,21 @@
 #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) | ...
 //
@@ -32,9 +30,8 @@ TKDInterpolator::TKDNodeInfo::TKDNodeInfo(const Int_t dim):
        fNDim(dim)
        ,fRefPoint(0x0)
        ,fRefValue(0.)
-       ,fCov()
-       ,fPar()
-       ,fPDFstatus(kFALSE)
+       ,fCov(0x0)
+       ,fPar(0x0)
 {
        if(fNDim) Build(dim);
 }
@@ -43,22 +40,70 @@ TKDInterpolator::TKDNodeInfo::TKDNodeInfo(const Int_t 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()
@@ -67,6 +112,7 @@ TKDInterpolator::TKDInterpolator() : TKDTreeIF()
        ,fStatus(4)
        ,fLambda(0)
        ,fDepth(-1)
+       ,fAlpha(.5)
        ,fRefPoints(0x0)
        ,fBuffer(0x0)
        ,fKDhelper(0x0)
@@ -78,18 +124,19 @@ TKDInterpolator::TKDInterpolator() : TKDTreeIF()
 
 //_________________________________________________________________
 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();
 }
 
@@ -101,6 +148,7 @@ TKDInterpolator::TKDInterpolator(TTree *t, const Char_t *var, const Char_t *cut,
        ,fStatus(4)
        ,fLambda(0)
        ,fDepth(-1)
+       ,fAlpha(.5)
        ,fRefPoints(0x0)
        ,fBuffer(0x0)
        ,fKDhelper(0x0)
@@ -124,12 +172,12 @@ TKDInterpolator::TKDInterpolator(TTree *t, const Char_t *var, const Char_t *cut,
                        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;
@@ -138,7 +186,6 @@ TKDInterpolator::TKDInterpolator(TTree *t, const Char_t *var, const Char_t *cut,
                for(int ip=0; ip<fNpoints; ip++) fData[idim][ip] = (Float_t)v[ip];
        }
        TKDTreeIF::Build();
-       fNTNodes = GetNTerminalNodes();
        Build();
 }
 
@@ -163,12 +210,15 @@ void TKDInterpolator::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;
@@ -176,11 +226,15 @@ void TKDInterpolator::Build()
                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;
                }
        }
@@ -193,37 +247,43 @@ void TKDInterpolator::Build()
        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.
 //
@@ -235,7 +295,7 @@ Double_t TKDInterpolator::Eval(const Double_t *point, Double_t &result, Double_t
        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];
@@ -245,9 +305,15 @@ Double_t TKDInterpolator::Eval(const Double_t *point, Double_t &result, Double_t
                        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
@@ -257,13 +323,14 @@ Double_t TKDInterpolator::Eval(const Double_t *point, Double_t &result, Double_t
 
        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];
@@ -275,11 +342,11 @@ Double_t TKDInterpolator::Eval(const Double_t *point, Double_t &result, Double_t
                }
                // 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]);
@@ -287,7 +354,12 @@ Double_t TKDInterpolator::Eval(const Double_t *point, Double_t &result, Double_t
                                        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
@@ -298,7 +370,7 @@ Double_t TKDInterpolator::Eval(const Double_t *point, Double_t &result, Double_t
                         
                        //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());
@@ -311,11 +383,7 @@ Double_t TKDInterpolator::Eval(const Double_t *point, Double_t &result, Double_t
        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];
@@ -337,84 +405,6 @@ Double_t TKDInterpolator::Eval(const Double_t *point, Double_t &result, Double_t
        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)
 {
@@ -440,14 +430,13 @@ 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++){
@@ -455,21 +444,21 @@ void TKDInterpolator::DrawNodes(UInt_t ax1, UInt_t ax2, Int_t depth)
                        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;
 }
@@ -483,7 +472,7 @@ void TKDInterpolator::DrawNode(Int_t tnode, UInt_t ax1, UInt_t ax2)
 // 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;
        }
@@ -509,7 +498,6 @@ void TKDInterpolator::DrawNode(Int_t tnode, UInt_t ax1, UInt_t ax2)
        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();
@@ -519,86 +507,29 @@ void TKDInterpolator::DrawNode(Int_t tnode, UInt_t ax1, UInt_t ax2)
 
 
 //__________________________________________________________________
-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.;
-}
-
index bd91349..85ecbb4 100644 (file)
@@ -4,73 +4,82 @@
 #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
@@ -94,7 +103,8 @@ Bool_t       TKDInterpolator::GetCOGPoint(Int_t node, Float_t *coord, Float_t &val, Fl
 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;
 }
index 84ebccc..aba2ba7 100644 (file)
@@ -5,7 +5,6 @@
 
 #ifndef R__ALPHA
 templateClassImp(TKDTree)
-templateClassImp(TKDNode)
 #endif
 //////////////////////////////////////////////////////////////////////
 // Memory setup of protected data members:
@@ -30,6 +29,16 @@ templateClassImp(TKDNode)
 //      - 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() :
@@ -40,7 +49,8 @@ TKDTree<Index, Value>::TKDTree() :
        ,fNDimm(0)
        ,fNpoints(0)
        ,fBucketSize(0)
-       ,fNodes(0x0)
+       ,fAxis(0x0)
+       ,fValue(0x0)
        ,fRange(0x0)
        ,fData(0x0)
        ,fBoundaries(0x0)
@@ -68,7 +78,8 @@ TKDTree<Index, Value>::TKDTree(Index npoints, Index ndim, UInt_t bsize, Value **
        ,fNDimm(2*ndim)
        ,fNpoints(npoints)
        ,fBucketSize(bsize)
-       ,fNodes(0x0)
+       ,fAxis(0x0)
+       ,fValue(0x0)
        ,fRange(0x0)
        ,fData(data) //Columnwise!!!!!
        ,fBoundaries(0x0)
@@ -84,7 +95,9 @@ TKDTree<Index, Value>::TKDTree(Index npoints, Index ndim, UInt_t bsize, Value **
 {
 // 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());
 }
 
 //_________________________________________________________________
@@ -95,7 +108,8 @@ TKDTree<Index, Value>::~TKDTree()
        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;
@@ -138,7 +152,8 @@ void TKDTree<Index, Value>::Build(){
        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;
@@ -180,7 +195,6 @@ void TKDTree<Index, Value>::Build(){
                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
@@ -215,12 +229,14 @@ void TKDTree<Index, Value>::Build(){
                                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);
                //
                //
@@ -249,7 +265,7 @@ void TKDTree<Index, Value>::Build(){
 
 //_________________________________________________________________
 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".
 //
@@ -258,7 +274,7 @@ Int_t       TKDTree<Index, Value>::FindNearestNeighbors(const Value *point, const Int_
 // 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){
@@ -275,10 +291,10 @@ Int_t     TKDTree<Index, Value>::FindNearestNeighbors(const Value *point, const Int_
                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; 
@@ -292,17 +308,20 @@ Int_t     TKDTree<Index, Value>::FindNearestNeighbors(const Value *point, const Int_
        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;
@@ -314,12 +333,13 @@ Int_t     TKDTree<Index, Value>::FindNearestNeighbors(const Value *point, const Int_
                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++;
@@ -374,36 +394,37 @@ Int_t     TKDTree<Index, Value>::FindNearestNeighbors(const Value *point, const Int_
                }
                
                // 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]);
                        }
@@ -413,7 +434,7 @@ Int_t       TKDTree<Index, Value>::FindNearestNeighbors(const Value *point, const Int_
        in = fkNN;
        d  = fkNNdist;
        
-       return nCalculations; //kTRUE;
+       return kTRUE;
 }
 
 
@@ -423,24 +444,22 @@ template <typename  Index, typename Value>
 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;
                }
        }
        
@@ -481,12 +500,11 @@ void TKDTree<Index, Value>::FindPoint(Value * point, Index &index, Int_t &iter){
                        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;
                }
@@ -520,12 +538,12 @@ void TKDTree<Index, Value>::FindInRangeA(Value * point, Value * delta, Index *re
     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;
       }
@@ -608,18 +626,18 @@ void TKDTree<Index, Value>::FindInRangeB(Value * point, Value * delta, Index *re
       }
     }
     //
-    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){
@@ -735,62 +753,69 @@ void TKDTree<Index, Value>::MakeBoundaries(Value *range)
 // 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;
        }
 }
 
index fb9866f..4edad19 100644 (file)
@@ -7,13 +7,8 @@
 
 #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
 {
@@ -27,26 +22,26 @@ public:
        ~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);
@@ -58,7 +53,7 @@ protected:
 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:
@@ -68,7 +63,8 @@ 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
@@ -102,9 +98,8 @@ void TKDTree<Index, Value>::FindBNodeA(Value *point, Value *delta, Int_t &inode)
   //
   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;
   }
 }
 
diff --git a/STAT/libSTAT.pkg b/STAT/libSTAT.pkg
new file mode 100644 (file)
index 0000000..2335dfd
--- /dev/null
@@ -0,0 +1,5 @@
+SRCS=  TKDTree.cxx TKDInterpolator.cxx TKDSpline.cxx
+
+HDRS= $(SRCS:.cxx=.h)
+
+DHDR:=StatLinkDef.h