// @(#)root/mathcore:$Id$
// Authors: B. Rabacal   11/2010

/**********************************************************************
 *                                                                    *
 * Copyright (c) 2010 , LCG ROOT MathLib Team                         *
 *                                                                    *
 *                                                                    *
 **********************************************************************/

// implementation file for class TKDTreeBinning
//

#include <algorithm>
#include <limits>
#include <cmath>

#include "TKDTreeBinning.h"

#include "Fit/BinData.h"
#include "TRandom.h"

ClassImp(TKDTreeBinning)

//________________________________________________________________________________________________
// Begin_Html
// <center><h2>TKDTreeBinning - A class providing multidimensional binning</h2></center>
// The class implements multidimensional binning by constructing a TKDTree inner structure from the
// data which is used as the bins.
// The bins are retrieved as two double*, one for the minimum bin edges,
// the other as the maximum bin edges. For one dimension one of these is enough to correctly define the bins.
// For the multidimensional case both minimum and maximum ones are necessary for the bins to be well defined.
// The bin edges of d-dimensional data is a d-tet of the bin's thresholds. For example if d=3 the minimum bin
// edges of bin b is of the form of the following array: {xbmin, ybmin, zbmin}.
// You also have the possibility to sort the bins by their density.
// <br>
// Details of usage can be found in $ROOTSYS/tutorials/math/kdTreeBinning.C and more information on
// the embedded TKDTree can be found in http://root.cern.ch/lxr/source/math/mathcore/src/TKDTree.cxx or
// http://root.cern.ch/lxr/source/math/mathcore/inc/TKDTree.h.
// End_Html

struct TKDTreeBinning::CompareAsc {
   // Boolean functor whose predicate depends on the bin's density. Used for ascending sort.
   CompareAsc(const TKDTreeBinning* treebins) : bins(treebins) {}
   Bool_t operator()(UInt_t bin1, UInt_t bin2) {
      return bins->GetBinDensity(bin1) < bins->GetBinDensity(bin2);
   }
   const TKDTreeBinning* bins;
};

struct TKDTreeBinning::CompareDesc {
   // Boolean functor whose predicate depends on the bin's density. Used for descending sort.
   CompareDesc(const TKDTreeBinning* treebins) : bins(treebins) {}
   Bool_t operator()(UInt_t bin1, UInt_t bin2) {
      return bins->GetBinDensity(bin1) > bins->GetBinDensity(bin2);
   }
   const TKDTreeBinning* bins;
};

TKDTreeBinning::TKDTreeBinning(UInt_t dataSize, UInt_t dataDim, Double_t* data, UInt_t nBins, bool adjustBinEdges)
// Class's constructor taking the size of the data points, dimension, a data array and the number
// of bins (default = 100). It is reccomended to have the number of bins as an exact divider of
// the data size.
// The data array must be organized with a stride=1 for the points and = N (the dataSize) for the dimension.
//
// Thus data[] = x1,x2,x3,......xN, y1,y2,y3......yN, z1,z2,...........zN,....
//
// Note that the passed dataSize is not the size of the array but is the number of points (N)
// The size of the array must be at least  dataDim*dataSize
//
: fData(0), fBinMinEdges(std::vector<Double_t>()), fBinMaxEdges(std::vector<Double_t>()), fDataBins((TKDTreeID*)0), fDim(dataDim),
fDataSize(dataSize), fDataThresholds(std::vector<std::pair<Double_t, Double_t> >(fDim, std::make_pair(0., 0.))),
fIsSorted(kFALSE), fIsSortedAsc(kFALSE), fBinsContent(std::vector<UInt_t>()) {
   if (adjustBinEdges) SetBit(kAdjustBinEdges);
   if (data) {
      SetData(data);
      SetNBins(nBins);
   } else {
      if (!fData)
         this->Warning("TKDTreeBinning", "Data is nil. Nothing is built.");
   }
}

TKDTreeBinning::~TKDTreeBinning() {
   // Class's destructor
   if (fData)     delete[] fData;
   if (fDataBins) delete   fDataBins;
}

void TKDTreeBinning::SetNBins(UInt_t bins) {
   // Sets binning inner structure
   fNBins = bins;
   if (fDim && fNBins && fDataSize) {
      if (fDataSize / fNBins) {
         Bool_t remainingData = fDataSize % fNBins;
         if (remainingData) {
            fNBins += 1;
            this->Info("SetNBins", "Number of bins is not enough to hold the data. Extra bin added.");
         }
         fDataBins = new TKDTreeID(fDataSize, fDim, fDataSize / (fNBins - remainingData)); // TKDTree input is data size, data dimension and the content size of bins ("bucket" size)
         SetTreeData();
         fDataBins->Build();
         SetBinsEdges();
         SetBinsContent();
      } else {
         fDataBins = (TKDTreeID*)0;
         this->Warning("SetNBins", "Number of bins is bigger than data size. Nothing is built.");
      }
   } else {
      fDataBins = (TKDTreeID*)0;
      if (!fDim)
         this->Warning("SetNBins", "Data dimension is nil. Nothing is built.");
      if (!fNBins)
         this->Warning("SetNBins", "Number of bins is nil. Nothing is built.");
      if (!fDataSize)
         this->Warning("SetNBins", "Data size is nil. Nothing is built.");
   }
}

void TKDTreeBinning::SortBinsByDensity(Bool_t sortAsc) {
   // Sorts bins by their density
   if (fDim == 1) {
      // in one dim they are already sorted (no need to do anything)
      return;
   } else {
      std::vector<UInt_t> indices(fNBins);        // vector for indices (for the inverse transformation)
      for (UInt_t i = 0; i < fNBins; ++i)
         indices[i] = i;
      if (sortAsc) {
         std::sort(indices.begin(), indices.end(), CompareAsc(this));
         fIsSortedAsc = kTRUE;
      } else {
         std::sort(indices.begin(), indices.end(), CompareDesc(this));
         fIsSortedAsc = kFALSE;
      }
      std::vector<Double_t> binMinEdges(fNBins * fDim);
      std::vector<Double_t> binMaxEdges(fNBins * fDim);
      std::vector<UInt_t> binContent(fNBins );    // reajust also content (not needed bbut better in general!)
      fIndices.resize(fNBins);     
      for (UInt_t i = 0; i < fNBins; ++i) {
         for (UInt_t j = 0; j < fDim; ++j) {
            binMinEdges[i * fDim + j] = fBinMinEdges[indices[i] * fDim + j];
            binMaxEdges[i * fDim + j] = fBinMaxEdges[indices[i] * fDim + j];
         }
         binContent[i] = fBinsContent[indices[i]];
         fIndices[indices[i]] = i; 
      }
      fBinMinEdges.swap(binMinEdges);
      fBinMaxEdges.swap(binMaxEdges);
      fBinsContent.swap(binContent);

      // not needed anymore if readjusting bin content all the time
      // re-adjust content of extra bins if exists
      // since it is different than the others
      // if ( fDataSize % fNBins != 0) {
      //    UInt_t k = 0;
      //    Bool_t found = kFALSE;
      //    while (!found) {
      //       if (indices[k] == fNBins - 1) {
      //          found = kTRUE;
      //          break;
      //       }
      //       ++k;
      //    }
      //    fBinsContent[fNBins - 1] = fDataBins->GetBucketSize();
      //    fBinsContent[k] = fDataSize % fNBins-1;
      // }

      fIsSorted = kTRUE;
    }
}

void TKDTreeBinning::SetData(Double_t* data) {
   // Sets the data and finds minimum and maximum by dimensional coordinate
   fData = new Double_t*[fDim];
   for (UInt_t i = 0; i < fDim; ++i) {
      fData[i] = &data[i * fDataSize];
      fDataThresholds[i] = std::make_pair(*std::min_element(fData[i], fData[i] + fDataSize), *std::max_element(fData[i], fData[i] + fDataSize));
   }
}

void TKDTreeBinning::SetTreeData() {
   // Sets the data for constructing the kD-tree
   for (UInt_t i = 0; i < fDim; ++i)
      fDataBins->SetData(i, fData[i]);
}

void TKDTreeBinning::SetBinsContent() {
   // Sets the bins' content
   fBinsContent.reserve(fNBins);
   for (UInt_t i = 0; i < fNBins; ++i)
      fBinsContent[i] = fDataBins->GetBucketSize();
   if ( fDataSize % fNBins != 0 )
      fBinsContent[fNBins - 1] = fDataSize % (fNBins-1);
}

void TKDTreeBinning::SetBinsEdges() {
   // Sets the bins' edges
   //Double_t* rawBinEdges = fDataBins->GetBoundaryExact(fDataBins->GetNNodes());
   Double_t* rawBinEdges = fDataBins->GetBoundary(fDataBins->GetNNodes());
   fCheckedBinEdges = std::vector<std::vector<std::pair<Bool_t, Bool_t> > >(fDim, std::vector<std::pair<Bool_t, Bool_t> >(fNBins, std::make_pair(kFALSE, kFALSE)));
   fCommonBinEdges = std::vector<std::map<Double_t, std::vector<UInt_t> > >(fDim, std::map<Double_t, std::vector<UInt_t> >());
   SetCommonBinEdges(rawBinEdges);
   if (TestBit(kAdjustBinEdges) ) {
      ReadjustMinBinEdges(rawBinEdges);
      ReadjustMaxBinEdges(rawBinEdges);
   }
   SetBinMinMaxEdges(rawBinEdges);
   fCommonBinEdges.clear();
   fCheckedBinEdges.clear();
}

void TKDTreeBinning::SetBinMinMaxEdges(Double_t* binEdges) {
   // Sets the bins' minimum and maximum edges
   fBinMinEdges.reserve(fNBins * fDim);
   fBinMaxEdges.reserve(fNBins * fDim);
   for (UInt_t i = 0; i < fNBins; ++i) {
      for (UInt_t j = 0; j < fDim; ++j) {
         fBinMinEdges.push_back(binEdges[(i * fDim + j) * 2]);
         fBinMaxEdges.push_back(binEdges[(i * fDim + j) * 2 + 1]);
      }
   }
}

void TKDTreeBinning::SetCommonBinEdges(Double_t* binEdges) {
   // Sets indexing on the bin edges which have common boundaries
   for (UInt_t i = 0; i < fDim; ++i) {
      for (UInt_t j = 0; j < fNBins; ++j) {
         Double_t binEdge = binEdges[(j * fDim + i) * 2];
         if(fCommonBinEdges[i].find(binEdge) == fCommonBinEdges[i].end()) {
            std::vector<UInt_t> commonBinEdges;
            for (UInt_t k = 0; k < fNBins; ++k) {
               UInt_t minBinEdgePos = (k * fDim + i) * 2;
               if (std::fabs(binEdge - binEdges[minBinEdgePos]) < std::numeric_limits<Double_t>::epsilon())
                  commonBinEdges.push_back(minBinEdgePos);
               UInt_t maxBinEdgePos = ++minBinEdgePos;
               if (std::fabs(binEdge - binEdges[maxBinEdgePos]) < std::numeric_limits<Double_t>::epsilon())
                  commonBinEdges.push_back(maxBinEdgePos);
            }
            fCommonBinEdges[i][binEdge] = commonBinEdges;
         }
      }
   }
}

void TKDTreeBinning::ReadjustMinBinEdges(Double_t* binEdges) {
   // Readjusts the bins' minimum edge by shifting it slightly lower
   // to avoid overlapping with the data
   for (UInt_t i = 0; i < fDim; ++i) {
      for (UInt_t j = 0; j < fNBins; ++j) {
         if (!fCheckedBinEdges[i][j].first) {
            Double_t binEdge = binEdges[(j * fDim + i) * 2];
            Double_t adjustedBinEdge = binEdge;
            double eps = -10*std::numeric_limits<Double_t>::epsilon();
            if (adjustedBinEdge != 0)
               adjustedBinEdge *= (1. + eps);
            else
               adjustedBinEdge += eps;

            for (UInt_t k = 0; k < fCommonBinEdges[i][binEdge].size(); ++k) {
               UInt_t binEdgePos = fCommonBinEdges[i][binEdge][k];
               Bool_t isMinBinEdge = binEdgePos % 2 == 0;
               UInt_t bin = isMinBinEdge ? (binEdgePos / 2 - i) / fDim : ((binEdgePos - 1) / 2 - i) / fDim;
               binEdges[binEdgePos] = adjustedBinEdge;
               if (isMinBinEdge)
                  fCheckedBinEdges[i][bin].first = kTRUE;
               else
                  fCheckedBinEdges[i][bin].second = kTRUE;
            }
         }
      }
   }
}

void TKDTreeBinning::ReadjustMaxBinEdges(Double_t* binEdges) {
   // Readjusts the bins' maximum edge
   // and shift it sligtly higher
   for (UInt_t i = 0; i < fDim; ++i) {
      for (UInt_t j = 0; j < fNBins; ++j) {
         if (!fCheckedBinEdges[i][j].second) {
            Double_t& binEdge = binEdges[(j * fDim + i) * 2 + 1];
            double eps = 10*std::numeric_limits<Double_t>::epsilon();
            if (binEdge != 0)
               binEdge *= (1. + eps);
            else
               binEdge += eps;


         }
      }
   }
}

const Double_t* TKDTreeBinning::GetBinsMinEdges() const {
   // Returns the bins' minimum edges
   if (fDataBins)
      return &fBinMinEdges[0];
   this->Warning("GetBinsMinEdges", "Binning kd-tree is nil. No bin edges retrieved.");
   this->Info("GetBinsMinEdges", "Returning null pointer.");
   return (Double_t*)0;
}

const Double_t* TKDTreeBinning::GetBinsMaxEdges() const {
   // Returns the bins' maximum edges
   if (fDataBins)
      return &fBinMaxEdges[0];
   this->Warning("GetBinsMaxEdges", "Binning kd-tree is nil. No bin edges retrieved.");
   this->Info("GetBinsMaxEdges", "Returning null pointer.");
   return (Double_t*)0;
}

std::pair<const Double_t*, const Double_t*> TKDTreeBinning::GetBinsEdges() const {
   // Returns the bins' edges
   if (fDataBins)
      return std::make_pair(GetBinsMinEdges(), GetBinsMaxEdges());
   this->Warning("GetBinsEdges", "Binning kd-tree is nil. No bin edges retrieved.");
   this->Info("GetBinsEdges", "Returning null pointer pair.");
   return std::make_pair((Double_t*)0, (Double_t*)0);
}

const Double_t* TKDTreeBinning::GetBinMinEdges(UInt_t bin) const {
   // Returns the bin's minimum edges. 'bin' is between 0 and fNBins - 1
   if (fDataBins)
      if (bin < fNBins)
         return &fBinMinEdges[bin * fDim];
      else
         this->Warning("GetBinMinEdges", "No such bin. 'bin' is between 0 and %d", fNBins - 1);
   else
      this->Warning("GetBinMinEdges", "Binning kd-tree is nil. No bin edges retrieved.");
   this->Info("GetBinMinEdges", "Returning null pointer.");
   return (Double_t*)0;
}

const Double_t* TKDTreeBinning::GetBinMaxEdges(UInt_t bin) const {
   // Returns the bin's maximum edges. 'bin' is between 0 and fNBins - 1
   if (fDataBins)
      if (bin < fNBins)
         return &fBinMaxEdges[bin * fDim];
      else
         this->Warning("GetBinMaxEdges", "No such bin. 'bin' is between 0 and %d", fNBins - 1);
   else
      this->Warning("GetBinMaxEdges", "Binning kd-tree is nil. No bin edges retrieved.");
   this->Info("GetBinMaxEdges", "Returning null pointer.");
   return (Double_t*)0;
}

std::pair<const Double_t*, const Double_t*> TKDTreeBinning::GetBinEdges(UInt_t bin) const {
   // Returns the bin's edges. 'bin' is between 0 and fNBins - 1
   if (fDataBins)
      if (bin < fNBins)
         return std::make_pair(GetBinMinEdges(bin), GetBinMaxEdges(bin));
      else
         this->Warning("GetBinEdges", "No such bin. 'bin' is between 0 and %d", fNBins - 1);
   else
      this->Warning("GetBinEdges", "Binning kd-tree is nil. No bin edges retrieved.");
   this->Info("GetBinEdges", "Returning null pointer pair.");
   return std::make_pair((Double_t*)0, (Double_t*)0);
}

UInt_t TKDTreeBinning::GetNBins() const {
   // Returns the number of bins
   return fNBins;
}

UInt_t TKDTreeBinning::GetDim() const {
   // Returns the number of dimensions
   return fDim;
}

UInt_t TKDTreeBinning::GetBinContent(UInt_t bin) const {
   // Returns the number of points in bin. 'bin' is between 0 and fNBins - 1
   if(bin <= fNBins - 1)
         return fBinsContent[bin];
   this->Warning("GetBinContent", "No such bin. Returning 0.");
   this->Info("GetBinContent", "'bin' is between 0 and %d.", fNBins - 1);
   return 0;
}


TKDTreeID* TKDTreeBinning::GetTree() const {
   // Returns the kD-Tree structure of the binning
   if (fDataBins)
      return fDataBins;
   this->Warning("GetTree", "Binning kd-tree is nil. No embedded kd-tree retrieved. Returning null pointer.");
   return (TKDTreeID*)0;
}

const Double_t* TKDTreeBinning::GetDimData(UInt_t dim) const {
   // Returns the data in the dim coordinate. 'dim' is between 0 and fDim - 1
   if(dim < fDim)
      return fData[dim];
   this->Warning("GetDimData", "No such dimensional coordinate. No coordinate data retrieved. Returning null pointer.");
   this->Info("GetDimData", "'dim' is between 0 and %d.", fDim - 1);
   return 0;
}

Double_t TKDTreeBinning::GetDataMin(UInt_t dim) const {
   // Returns the data minimum in the dim coordinate. 'dim' is between 0 and fDim - 1
   if(dim < fDim)
      return fDataThresholds[dim].first;
   this->Warning("GetDataMin", "No such dimensional coordinate. No coordinate data minimum retrieved. Returning +inf.");
   this->Info("GetDataMin", "'dim' is between 0 and %d.", fDim - 1);
   return std::numeric_limits<Double_t>::infinity();
}

Double_t TKDTreeBinning::GetDataMax(UInt_t dim) const {
   // Returns the data maximum in the dim coordinate. 'dim' is between 0 and fDim - 1
   if(dim < fDim)
      return fDataThresholds[dim].second;
   this->Warning("GetDataMax", "No such dimensional coordinate. No coordinate data maximum retrieved. Returning -inf.");
   this->Info("GetDataMax", "'dim' is between 0 and %d.", fDim - 1);
   return -1 * std::numeric_limits<Double_t>::infinity();
}

Double_t TKDTreeBinning::GetBinDensity(UInt_t bin) const {
   // Returns the density in bin. 'bin' is between 0 and fNBins - 1
   if(bin < fNBins) {
      Double_t volume = GetBinVolume(bin);
      if (!volume)
         this->Warning("GetBinDensity", "Volume is null. Returning -1.");
      return GetBinContent(bin) / volume;
   }
   this->Warning("GetBinDensity", "No such bin. Returning -1.");
   this->Info("GetBinDensity", "'bin' is between 0 and %d.", fNBins - 1);
   return -1.;
}

Double_t TKDTreeBinning::GetBinVolume(UInt_t bin) const {
   // Returns the (hyper)volume of bin. 'bin' is between 0 and fNBins - 1
   if(bin < fNBins) {
      std::pair<const Double_t*, const Double_t*> binEdges = GetBinEdges(bin);
      Double_t volume = 1.;
      for (UInt_t i = 0; i < fDim; ++i) {
         volume *= (binEdges.second[i] - binEdges.first[i]);
      }
      return volume;
   }
   this->Warning("GetBinVolume", "No such bin. Returning 0.");
   this->Info("GetBinVolume", "'bin' is between 0 and %d.", fNBins - 1);
   return 0.;
}

const double * TKDTreeBinning::GetOneDimBinEdges() const  {
   // Returns the minimum edges for one dimensional binning only.
   // size of the vector is fNBins + 1 is the vector has been sorted in increasing bin edges
   // N.B : if one does not call SortOneDimBinEdges the bins are not ordered
   if (fDim == 1) {
      // no need to sort here because vector is already sorted in one dim
      return &fBinMinEdges.front();
   }
   this->Warning("GetOneDimBinEdges", "Data is multidimensional. No sorted bin edges retrieved. Returning null pointer.");
   this->Info("GetOneDimBinEdges", "This method can only be invoked if the data is a one dimensional set");
   return 0;
}

const Double_t * TKDTreeBinning::SortOneDimBinEdges(Bool_t sortAsc) {
   if (fDim != 1) {
      this->Warning("SortOneDimBinEdges", "Data is multidimensional. Cannot sorted bin edges. Returning null pointer.");
      this->Info("SortOneDimBinEdges", "This method can only be invoked if the data is a one dimensional set");
      return 0;
   }
   // order bins by increasing (or decreasing ) x positions
   std::vector<UInt_t> indices(fNBins);
   TMath::Sort( fNBins, &fBinMinEdges[0], &indices[0], !sortAsc );

   std::vector<Double_t> binMinEdges(fNBins );
   std::vector<Double_t> binMaxEdges(fNBins );
   std::vector<UInt_t> binContent(fNBins );    // reajust also content (not needed but better in general!)
   fIndices.resize( fNBins );
   for (UInt_t i = 0; i < fNBins; ++i) {
      binMinEdges[i ] = fBinMinEdges[indices[i] ];
      binMaxEdges[i ] = fBinMaxEdges[indices[i] ];
      binContent[i] = fBinsContent[indices[i] ];
      fIndices[indices[i] ] = i;  // for the inverse transformation
   }
   fBinMinEdges.swap(binMinEdges);
   fBinMaxEdges.swap(binMaxEdges);
   fBinsContent.swap(binContent);

   fIsSorted = kTRUE; 

   // Add also the upper(lower) edge to the min (max) list
   if (sortAsc) {
      fBinMinEdges.push_back(fBinMaxEdges.back());
      fIsSortedAsc = kTRUE; 
      return &fBinMinEdges[0];
   }
   fBinMaxEdges.push_back(fBinMinEdges.back());
   return &fBinMaxEdges[0];

}


const Double_t* TKDTreeBinning::GetBinCenter(UInt_t bin) const {
   // Returns the geometric center of of the bin. 'bin' is between 0 and fNBins - 1
   if(bin < fNBins) {
      Double_t* result = new Double_t[fDim];
      std::pair<const Double_t*, const Double_t*> binEdges = GetBinEdges(bin);
      for (UInt_t i = 0; i < fDim; ++i) {
         result[i] = (binEdges.second[i] + binEdges.first[i]) / 2.;
      }
      return result;
   }
   this->Warning("GetBinCenter", "No such bin. Returning null pointer.");
   this->Info("GetBinCenter", "'bin' is between 0 and %d.", fNBins - 1);
   return 0;
}

const Double_t* TKDTreeBinning::GetBinWidth(UInt_t bin) const {
   // Returns the geometric center of of the bin. 'bin' is between 0 and fNBins - 1
   if(bin < fNBins) {
      Double_t* result = new Double_t[fDim];
      std::pair<const Double_t*, const Double_t*> binEdges = GetBinEdges(bin);
      for (UInt_t i = 0; i < fDim; ++i) {
         result[i] = (binEdges.second[i] - binEdges.first[i]);
      }
      return result;
   }
   this->Warning("GetBinWidth", "No such bin. Returning null pointer.");
   this->Info("GetBinWidth", "'bin' is between 0 and %d.", fNBins - 1);
   return 0;
}

UInt_t TKDTreeBinning::GetBinMaxDensity() const {
   // Return the bin with maximum density
   if (fIsSorted) {
      if (fIsSortedAsc)
         return fNBins - 1;
      else return 0;
   }
   UInt_t* indices = new UInt_t[fNBins];
   for (UInt_t i = 0; i < fNBins; ++i)
      indices[i] = i;
   UInt_t result = *std::max_element(indices, indices + fNBins, CompareAsc(this));
   delete [] indices;
   return  result;
}

UInt_t TKDTreeBinning::GetBinMinDensity() const {
   // Return the bin with minimum density
   if (fIsSorted) {
      if (!fIsSortedAsc)
         return fNBins - 1;
      else return 0;
   }
   UInt_t* indices = new UInt_t[fNBins];
   for (UInt_t i = 0; i < fNBins; ++i)
      indices[i] = i;
   UInt_t result = *std::min_element(indices, indices + fNBins, CompareAsc(this));
   delete [] indices;
   return result;
}

void TKDTreeBinning::FillBinData(ROOT::Fit::BinData & data) const {
   // Fill the bin data set with the result of the TKDTree binning
   if (!fDataBins) return;
   data.Initialize(fNBins, fDim);
   for (unsigned int i = 0; i < fNBins; ++i) {
      data.Add( GetBinMinEdges(i), GetBinDensity(i), std::sqrt(double(GetBinContent(i) ))/ GetBinVolume(i) );
      data.AddBinUpEdge(GetBinMaxEdges(i) );
   }
}

UInt_t TKDTreeBinning::FindBin(const Double_t * point) const {
   // find the corresponding bin index given a point

   Int_t inode = fDataBins->FindNode(point); 
   // find node return the index in the total nodes and the bins are only the terminal ones
   // so we subtract all the non-terminal nodes
   inode -= fDataBins->GetNNodes(); 
   R__ASSERT( inode >= 0); 
   UInt_t bin = inode;

   if (!fIsSorted) return  bin;
   //return std::distance(fIndices.begin(), std::find(fIndices.begin(), fIndices.end(), bin ) ); 
   return fIndices[bin];
} 
 TKDTreeBinning.cxx:1
 TKDTreeBinning.cxx:2
 TKDTreeBinning.cxx:3
 TKDTreeBinning.cxx:4
 TKDTreeBinning.cxx:5
 TKDTreeBinning.cxx:6
 TKDTreeBinning.cxx:7
 TKDTreeBinning.cxx:8
 TKDTreeBinning.cxx:9
 TKDTreeBinning.cxx:10
 TKDTreeBinning.cxx:11
 TKDTreeBinning.cxx:12
 TKDTreeBinning.cxx:13
 TKDTreeBinning.cxx:14
 TKDTreeBinning.cxx:15
 TKDTreeBinning.cxx:16
 TKDTreeBinning.cxx:17
 TKDTreeBinning.cxx:18
 TKDTreeBinning.cxx:19
 TKDTreeBinning.cxx:20
 TKDTreeBinning.cxx:21
 TKDTreeBinning.cxx:22
 TKDTreeBinning.cxx:23
 TKDTreeBinning.cxx:24
 TKDTreeBinning.cxx:25
 TKDTreeBinning.cxx:26
 TKDTreeBinning.cxx:27
 TKDTreeBinning.cxx:28
 TKDTreeBinning.cxx:29
 TKDTreeBinning.cxx:30
 TKDTreeBinning.cxx:31
 TKDTreeBinning.cxx:32
 TKDTreeBinning.cxx:33
 TKDTreeBinning.cxx:34
 TKDTreeBinning.cxx:35
 TKDTreeBinning.cxx:36
 TKDTreeBinning.cxx:37
 TKDTreeBinning.cxx:38
 TKDTreeBinning.cxx:39
 TKDTreeBinning.cxx:40
 TKDTreeBinning.cxx:41
 TKDTreeBinning.cxx:42
 TKDTreeBinning.cxx:43
 TKDTreeBinning.cxx:44
 TKDTreeBinning.cxx:45
 TKDTreeBinning.cxx:46
 TKDTreeBinning.cxx:47
 TKDTreeBinning.cxx:48
 TKDTreeBinning.cxx:49
 TKDTreeBinning.cxx:50
 TKDTreeBinning.cxx:51
 TKDTreeBinning.cxx:52
 TKDTreeBinning.cxx:53
 TKDTreeBinning.cxx:54
 TKDTreeBinning.cxx:55
 TKDTreeBinning.cxx:56
 TKDTreeBinning.cxx:57
 TKDTreeBinning.cxx:58
 TKDTreeBinning.cxx:59
 TKDTreeBinning.cxx:60
 TKDTreeBinning.cxx:61
 TKDTreeBinning.cxx:62
 TKDTreeBinning.cxx:63
 TKDTreeBinning.cxx:64
 TKDTreeBinning.cxx:65
 TKDTreeBinning.cxx:66
 TKDTreeBinning.cxx:67
 TKDTreeBinning.cxx:68
 TKDTreeBinning.cxx:69
 TKDTreeBinning.cxx:70
 TKDTreeBinning.cxx:71
 TKDTreeBinning.cxx:72
 TKDTreeBinning.cxx:73
 TKDTreeBinning.cxx:74
 TKDTreeBinning.cxx:75
 TKDTreeBinning.cxx:76
 TKDTreeBinning.cxx:77
 TKDTreeBinning.cxx:78
 TKDTreeBinning.cxx:79
 TKDTreeBinning.cxx:80
 TKDTreeBinning.cxx:81
 TKDTreeBinning.cxx:82
 TKDTreeBinning.cxx:83
 TKDTreeBinning.cxx:84
 TKDTreeBinning.cxx:85
 TKDTreeBinning.cxx:86
 TKDTreeBinning.cxx:87
 TKDTreeBinning.cxx:88
 TKDTreeBinning.cxx:89
 TKDTreeBinning.cxx:90
 TKDTreeBinning.cxx:91
 TKDTreeBinning.cxx:92
 TKDTreeBinning.cxx:93
 TKDTreeBinning.cxx:94
 TKDTreeBinning.cxx:95
 TKDTreeBinning.cxx:96
 TKDTreeBinning.cxx:97
 TKDTreeBinning.cxx:98
 TKDTreeBinning.cxx:99
 TKDTreeBinning.cxx:100
 TKDTreeBinning.cxx:101
 TKDTreeBinning.cxx:102
 TKDTreeBinning.cxx:103
 TKDTreeBinning.cxx:104
 TKDTreeBinning.cxx:105
 TKDTreeBinning.cxx:106
 TKDTreeBinning.cxx:107
 TKDTreeBinning.cxx:108
 TKDTreeBinning.cxx:109
 TKDTreeBinning.cxx:110
 TKDTreeBinning.cxx:111
 TKDTreeBinning.cxx:112
 TKDTreeBinning.cxx:113
 TKDTreeBinning.cxx:114
 TKDTreeBinning.cxx:115
 TKDTreeBinning.cxx:116
 TKDTreeBinning.cxx:117
 TKDTreeBinning.cxx:118
 TKDTreeBinning.cxx:119
 TKDTreeBinning.cxx:120
 TKDTreeBinning.cxx:121
 TKDTreeBinning.cxx:122
 TKDTreeBinning.cxx:123
 TKDTreeBinning.cxx:124
 TKDTreeBinning.cxx:125
 TKDTreeBinning.cxx:126
 TKDTreeBinning.cxx:127
 TKDTreeBinning.cxx:128
 TKDTreeBinning.cxx:129
 TKDTreeBinning.cxx:130
 TKDTreeBinning.cxx:131
 TKDTreeBinning.cxx:132
 TKDTreeBinning.cxx:133
 TKDTreeBinning.cxx:134
 TKDTreeBinning.cxx:135
 TKDTreeBinning.cxx:136
 TKDTreeBinning.cxx:137
 TKDTreeBinning.cxx:138
 TKDTreeBinning.cxx:139
 TKDTreeBinning.cxx:140
 TKDTreeBinning.cxx:141
 TKDTreeBinning.cxx:142
 TKDTreeBinning.cxx:143
 TKDTreeBinning.cxx:144
 TKDTreeBinning.cxx:145
 TKDTreeBinning.cxx:146
 TKDTreeBinning.cxx:147
 TKDTreeBinning.cxx:148
 TKDTreeBinning.cxx:149
 TKDTreeBinning.cxx:150
 TKDTreeBinning.cxx:151
 TKDTreeBinning.cxx:152
 TKDTreeBinning.cxx:153
 TKDTreeBinning.cxx:154
 TKDTreeBinning.cxx:155
 TKDTreeBinning.cxx:156
 TKDTreeBinning.cxx:157
 TKDTreeBinning.cxx:158
 TKDTreeBinning.cxx:159
 TKDTreeBinning.cxx:160
 TKDTreeBinning.cxx:161
 TKDTreeBinning.cxx:162
 TKDTreeBinning.cxx:163
 TKDTreeBinning.cxx:164
 TKDTreeBinning.cxx:165
 TKDTreeBinning.cxx:166
 TKDTreeBinning.cxx:167
 TKDTreeBinning.cxx:168
 TKDTreeBinning.cxx:169
 TKDTreeBinning.cxx:170
 TKDTreeBinning.cxx:171
 TKDTreeBinning.cxx:172
 TKDTreeBinning.cxx:173
 TKDTreeBinning.cxx:174
 TKDTreeBinning.cxx:175
 TKDTreeBinning.cxx:176
 TKDTreeBinning.cxx:177
 TKDTreeBinning.cxx:178
 TKDTreeBinning.cxx:179
 TKDTreeBinning.cxx:180
 TKDTreeBinning.cxx:181
 TKDTreeBinning.cxx:182
 TKDTreeBinning.cxx:183
 TKDTreeBinning.cxx:184
 TKDTreeBinning.cxx:185
 TKDTreeBinning.cxx:186
 TKDTreeBinning.cxx:187
 TKDTreeBinning.cxx:188
 TKDTreeBinning.cxx:189
 TKDTreeBinning.cxx:190
 TKDTreeBinning.cxx:191
 TKDTreeBinning.cxx:192
 TKDTreeBinning.cxx:193
 TKDTreeBinning.cxx:194
 TKDTreeBinning.cxx:195
 TKDTreeBinning.cxx:196
 TKDTreeBinning.cxx:197
 TKDTreeBinning.cxx:198
 TKDTreeBinning.cxx:199
 TKDTreeBinning.cxx:200
 TKDTreeBinning.cxx:201
 TKDTreeBinning.cxx:202
 TKDTreeBinning.cxx:203
 TKDTreeBinning.cxx:204
 TKDTreeBinning.cxx:205
 TKDTreeBinning.cxx:206
 TKDTreeBinning.cxx:207
 TKDTreeBinning.cxx:208
 TKDTreeBinning.cxx:209
 TKDTreeBinning.cxx:210
 TKDTreeBinning.cxx:211
 TKDTreeBinning.cxx:212
 TKDTreeBinning.cxx:213
 TKDTreeBinning.cxx:214
 TKDTreeBinning.cxx:215
 TKDTreeBinning.cxx:216
 TKDTreeBinning.cxx:217
 TKDTreeBinning.cxx:218
 TKDTreeBinning.cxx:219
 TKDTreeBinning.cxx:220
 TKDTreeBinning.cxx:221
 TKDTreeBinning.cxx:222
 TKDTreeBinning.cxx:223
 TKDTreeBinning.cxx:224
 TKDTreeBinning.cxx:225
 TKDTreeBinning.cxx:226
 TKDTreeBinning.cxx:227
 TKDTreeBinning.cxx:228
 TKDTreeBinning.cxx:229
 TKDTreeBinning.cxx:230
 TKDTreeBinning.cxx:231
 TKDTreeBinning.cxx:232
 TKDTreeBinning.cxx:233
 TKDTreeBinning.cxx:234
 TKDTreeBinning.cxx:235
 TKDTreeBinning.cxx:236
 TKDTreeBinning.cxx:237
 TKDTreeBinning.cxx:238
 TKDTreeBinning.cxx:239
 TKDTreeBinning.cxx:240
 TKDTreeBinning.cxx:241
 TKDTreeBinning.cxx:242
 TKDTreeBinning.cxx:243
 TKDTreeBinning.cxx:244
 TKDTreeBinning.cxx:245
 TKDTreeBinning.cxx:246
 TKDTreeBinning.cxx:247
 TKDTreeBinning.cxx:248
 TKDTreeBinning.cxx:249
 TKDTreeBinning.cxx:250
 TKDTreeBinning.cxx:251
 TKDTreeBinning.cxx:252
 TKDTreeBinning.cxx:253
 TKDTreeBinning.cxx:254
 TKDTreeBinning.cxx:255
 TKDTreeBinning.cxx:256
 TKDTreeBinning.cxx:257
 TKDTreeBinning.cxx:258
 TKDTreeBinning.cxx:259
 TKDTreeBinning.cxx:260
 TKDTreeBinning.cxx:261
 TKDTreeBinning.cxx:262
 TKDTreeBinning.cxx:263
 TKDTreeBinning.cxx:264
 TKDTreeBinning.cxx:265
 TKDTreeBinning.cxx:266
 TKDTreeBinning.cxx:267
 TKDTreeBinning.cxx:268
 TKDTreeBinning.cxx:269
 TKDTreeBinning.cxx:270
 TKDTreeBinning.cxx:271
 TKDTreeBinning.cxx:272
 TKDTreeBinning.cxx:273
 TKDTreeBinning.cxx:274
 TKDTreeBinning.cxx:275
 TKDTreeBinning.cxx:276
 TKDTreeBinning.cxx:277
 TKDTreeBinning.cxx:278
 TKDTreeBinning.cxx:279
 TKDTreeBinning.cxx:280
 TKDTreeBinning.cxx:281
 TKDTreeBinning.cxx:282
 TKDTreeBinning.cxx:283
 TKDTreeBinning.cxx:284
 TKDTreeBinning.cxx:285
 TKDTreeBinning.cxx:286
 TKDTreeBinning.cxx:287
 TKDTreeBinning.cxx:288
 TKDTreeBinning.cxx:289
 TKDTreeBinning.cxx:290
 TKDTreeBinning.cxx:291
 TKDTreeBinning.cxx:292
 TKDTreeBinning.cxx:293
 TKDTreeBinning.cxx:294
 TKDTreeBinning.cxx:295
 TKDTreeBinning.cxx:296
 TKDTreeBinning.cxx:297
 TKDTreeBinning.cxx:298
 TKDTreeBinning.cxx:299
 TKDTreeBinning.cxx:300
 TKDTreeBinning.cxx:301
 TKDTreeBinning.cxx:302
 TKDTreeBinning.cxx:303
 TKDTreeBinning.cxx:304
 TKDTreeBinning.cxx:305
 TKDTreeBinning.cxx:306
 TKDTreeBinning.cxx:307
 TKDTreeBinning.cxx:308
 TKDTreeBinning.cxx:309
 TKDTreeBinning.cxx:310
 TKDTreeBinning.cxx:311
 TKDTreeBinning.cxx:312
 TKDTreeBinning.cxx:313
 TKDTreeBinning.cxx:314
 TKDTreeBinning.cxx:315
 TKDTreeBinning.cxx:316
 TKDTreeBinning.cxx:317
 TKDTreeBinning.cxx:318
 TKDTreeBinning.cxx:319
 TKDTreeBinning.cxx:320
 TKDTreeBinning.cxx:321
 TKDTreeBinning.cxx:322
 TKDTreeBinning.cxx:323
 TKDTreeBinning.cxx:324
 TKDTreeBinning.cxx:325
 TKDTreeBinning.cxx:326
 TKDTreeBinning.cxx:327
 TKDTreeBinning.cxx:328
 TKDTreeBinning.cxx:329
 TKDTreeBinning.cxx:330
 TKDTreeBinning.cxx:331
 TKDTreeBinning.cxx:332
 TKDTreeBinning.cxx:333
 TKDTreeBinning.cxx:334
 TKDTreeBinning.cxx:335
 TKDTreeBinning.cxx:336
 TKDTreeBinning.cxx:337
 TKDTreeBinning.cxx:338
 TKDTreeBinning.cxx:339
 TKDTreeBinning.cxx:340
 TKDTreeBinning.cxx:341
 TKDTreeBinning.cxx:342
 TKDTreeBinning.cxx:343
 TKDTreeBinning.cxx:344
 TKDTreeBinning.cxx:345
 TKDTreeBinning.cxx:346
 TKDTreeBinning.cxx:347
 TKDTreeBinning.cxx:348
 TKDTreeBinning.cxx:349
 TKDTreeBinning.cxx:350
 TKDTreeBinning.cxx:351
 TKDTreeBinning.cxx:352
 TKDTreeBinning.cxx:353
 TKDTreeBinning.cxx:354
 TKDTreeBinning.cxx:355
 TKDTreeBinning.cxx:356
 TKDTreeBinning.cxx:357
 TKDTreeBinning.cxx:358
 TKDTreeBinning.cxx:359
 TKDTreeBinning.cxx:360
 TKDTreeBinning.cxx:361
 TKDTreeBinning.cxx:362
 TKDTreeBinning.cxx:363
 TKDTreeBinning.cxx:364
 TKDTreeBinning.cxx:365
 TKDTreeBinning.cxx:366
 TKDTreeBinning.cxx:367
 TKDTreeBinning.cxx:368
 TKDTreeBinning.cxx:369
 TKDTreeBinning.cxx:370
 TKDTreeBinning.cxx:371
 TKDTreeBinning.cxx:372
 TKDTreeBinning.cxx:373
 TKDTreeBinning.cxx:374
 TKDTreeBinning.cxx:375
 TKDTreeBinning.cxx:376
 TKDTreeBinning.cxx:377
 TKDTreeBinning.cxx:378
 TKDTreeBinning.cxx:379
 TKDTreeBinning.cxx:380
 TKDTreeBinning.cxx:381
 TKDTreeBinning.cxx:382
 TKDTreeBinning.cxx:383
 TKDTreeBinning.cxx:384
 TKDTreeBinning.cxx:385
 TKDTreeBinning.cxx:386
 TKDTreeBinning.cxx:387
 TKDTreeBinning.cxx:388
 TKDTreeBinning.cxx:389
 TKDTreeBinning.cxx:390
 TKDTreeBinning.cxx:391
 TKDTreeBinning.cxx:392
 TKDTreeBinning.cxx:393
 TKDTreeBinning.cxx:394
 TKDTreeBinning.cxx:395
 TKDTreeBinning.cxx:396
 TKDTreeBinning.cxx:397
 TKDTreeBinning.cxx:398
 TKDTreeBinning.cxx:399
 TKDTreeBinning.cxx:400
 TKDTreeBinning.cxx:401
 TKDTreeBinning.cxx:402
 TKDTreeBinning.cxx:403
 TKDTreeBinning.cxx:404
 TKDTreeBinning.cxx:405
 TKDTreeBinning.cxx:406
 TKDTreeBinning.cxx:407
 TKDTreeBinning.cxx:408
 TKDTreeBinning.cxx:409
 TKDTreeBinning.cxx:410
 TKDTreeBinning.cxx:411
 TKDTreeBinning.cxx:412
 TKDTreeBinning.cxx:413
 TKDTreeBinning.cxx:414
 TKDTreeBinning.cxx:415
 TKDTreeBinning.cxx:416
 TKDTreeBinning.cxx:417
 TKDTreeBinning.cxx:418
 TKDTreeBinning.cxx:419
 TKDTreeBinning.cxx:420
 TKDTreeBinning.cxx:421
 TKDTreeBinning.cxx:422
 TKDTreeBinning.cxx:423
 TKDTreeBinning.cxx:424
 TKDTreeBinning.cxx:425
 TKDTreeBinning.cxx:426
 TKDTreeBinning.cxx:427
 TKDTreeBinning.cxx:428
 TKDTreeBinning.cxx:429
 TKDTreeBinning.cxx:430
 TKDTreeBinning.cxx:431
 TKDTreeBinning.cxx:432
 TKDTreeBinning.cxx:433
 TKDTreeBinning.cxx:434
 TKDTreeBinning.cxx:435
 TKDTreeBinning.cxx:436
 TKDTreeBinning.cxx:437
 TKDTreeBinning.cxx:438
 TKDTreeBinning.cxx:439
 TKDTreeBinning.cxx:440
 TKDTreeBinning.cxx:441
 TKDTreeBinning.cxx:442
 TKDTreeBinning.cxx:443
 TKDTreeBinning.cxx:444
 TKDTreeBinning.cxx:445
 TKDTreeBinning.cxx:446
 TKDTreeBinning.cxx:447
 TKDTreeBinning.cxx:448
 TKDTreeBinning.cxx:449
 TKDTreeBinning.cxx:450
 TKDTreeBinning.cxx:451
 TKDTreeBinning.cxx:452
 TKDTreeBinning.cxx:453
 TKDTreeBinning.cxx:454
 TKDTreeBinning.cxx:455
 TKDTreeBinning.cxx:456
 TKDTreeBinning.cxx:457
 TKDTreeBinning.cxx:458
 TKDTreeBinning.cxx:459
 TKDTreeBinning.cxx:460
 TKDTreeBinning.cxx:461
 TKDTreeBinning.cxx:462
 TKDTreeBinning.cxx:463
 TKDTreeBinning.cxx:464
 TKDTreeBinning.cxx:465
 TKDTreeBinning.cxx:466
 TKDTreeBinning.cxx:467
 TKDTreeBinning.cxx:468
 TKDTreeBinning.cxx:469
 TKDTreeBinning.cxx:470
 TKDTreeBinning.cxx:471
 TKDTreeBinning.cxx:472
 TKDTreeBinning.cxx:473
 TKDTreeBinning.cxx:474
 TKDTreeBinning.cxx:475
 TKDTreeBinning.cxx:476
 TKDTreeBinning.cxx:477
 TKDTreeBinning.cxx:478
 TKDTreeBinning.cxx:479
 TKDTreeBinning.cxx:480
 TKDTreeBinning.cxx:481
 TKDTreeBinning.cxx:482
 TKDTreeBinning.cxx:483
 TKDTreeBinning.cxx:484
 TKDTreeBinning.cxx:485
 TKDTreeBinning.cxx:486
 TKDTreeBinning.cxx:487
 TKDTreeBinning.cxx:488
 TKDTreeBinning.cxx:489
 TKDTreeBinning.cxx:490
 TKDTreeBinning.cxx:491
 TKDTreeBinning.cxx:492
 TKDTreeBinning.cxx:493
 TKDTreeBinning.cxx:494
 TKDTreeBinning.cxx:495
 TKDTreeBinning.cxx:496
 TKDTreeBinning.cxx:497
 TKDTreeBinning.cxx:498
 TKDTreeBinning.cxx:499
 TKDTreeBinning.cxx:500
 TKDTreeBinning.cxx:501
 TKDTreeBinning.cxx:502
 TKDTreeBinning.cxx:503
 TKDTreeBinning.cxx:504
 TKDTreeBinning.cxx:505
 TKDTreeBinning.cxx:506
 TKDTreeBinning.cxx:507
 TKDTreeBinning.cxx:508
 TKDTreeBinning.cxx:509
 TKDTreeBinning.cxx:510
 TKDTreeBinning.cxx:511
 TKDTreeBinning.cxx:512
 TKDTreeBinning.cxx:513
 TKDTreeBinning.cxx:514
 TKDTreeBinning.cxx:515
 TKDTreeBinning.cxx:516
 TKDTreeBinning.cxx:517
 TKDTreeBinning.cxx:518
 TKDTreeBinning.cxx:519
 TKDTreeBinning.cxx:520
 TKDTreeBinning.cxx:521
 TKDTreeBinning.cxx:522
 TKDTreeBinning.cxx:523
 TKDTreeBinning.cxx:524
 TKDTreeBinning.cxx:525
 TKDTreeBinning.cxx:526
 TKDTreeBinning.cxx:527
 TKDTreeBinning.cxx:528
 TKDTreeBinning.cxx:529
 TKDTreeBinning.cxx:530
 TKDTreeBinning.cxx:531
 TKDTreeBinning.cxx:532
 TKDTreeBinning.cxx:533
 TKDTreeBinning.cxx:534
 TKDTreeBinning.cxx:535
 TKDTreeBinning.cxx:536
 TKDTreeBinning.cxx:537
 TKDTreeBinning.cxx:538
 TKDTreeBinning.cxx:539
 TKDTreeBinning.cxx:540
 TKDTreeBinning.cxx:541
 TKDTreeBinning.cxx:542
 TKDTreeBinning.cxx:543
 TKDTreeBinning.cxx:544
 TKDTreeBinning.cxx:545
 TKDTreeBinning.cxx:546
 TKDTreeBinning.cxx:547
 TKDTreeBinning.cxx:548
 TKDTreeBinning.cxx:549
 TKDTreeBinning.cxx:550
 TKDTreeBinning.cxx:551
 TKDTreeBinning.cxx:552
 TKDTreeBinning.cxx:553
 TKDTreeBinning.cxx:554
 TKDTreeBinning.cxx:555
 TKDTreeBinning.cxx:556
 TKDTreeBinning.cxx:557
 TKDTreeBinning.cxx:558
 TKDTreeBinning.cxx:559
 TKDTreeBinning.cxx:560
 TKDTreeBinning.cxx:561
 TKDTreeBinning.cxx:562
 TKDTreeBinning.cxx:563
 TKDTreeBinning.cxx:564
 TKDTreeBinning.cxx:565
 TKDTreeBinning.cxx:566
 TKDTreeBinning.cxx:567
 TKDTreeBinning.cxx:568
 TKDTreeBinning.cxx:569
 TKDTreeBinning.cxx:570
 TKDTreeBinning.cxx:571
 TKDTreeBinning.cxx:572
 TKDTreeBinning.cxx:573
 TKDTreeBinning.cxx:574
 TKDTreeBinning.cxx:575
 TKDTreeBinning.cxx:576
 TKDTreeBinning.cxx:577