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

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

#ifndef ROOT_TKDTreeBinning
#define ROOT_TKDTreeBinning

// Header file for class TKDTreeBinning
//
//

#include <map>
#include <utility>

#ifndef ROOT_TKDTree
#include "TKDTree.h"
#endif

namespace ROOT {
   namespace Fit {
      class BinData;
   }
}

class TKDTreeBinning : public TObject {
private:
   Double_t** fData; // The data from which a KDTree partition is computed for binning
   std::vector<Double_t> fBinMinEdges; // The minimum values for the bins' edges for each dimension
   std::vector<Double_t> fBinMaxEdges; // The maximum values for the bins' edges for each dimension
   std::vector<UInt_t>   fIndices;     // Index of the bins in the kd-tree (needed when bins are sorted)
   TKDTreeID* fDataBins; // The binning inner structure.
   UInt_t fNBins; // The number of bins
   UInt_t fDim; // The data dimension
   UInt_t fDataSize; // The data size
   std::vector<std::pair<Double_t, Double_t> > fDataThresholds; // Minimum and maximum data values.
   std::vector<std::vector<std::pair<Bool_t, Bool_t> > > fCheckedBinEdges; // Auxiliary structure for readjusting the bin edges. Flags if the bin edge was processed in  the algorithm
   std::vector<std::map<Double_t, std::vector<UInt_t> > > fCommonBinEdges; // Auxiliary structure for readjusting the bin edges. Keeps the common bin boundaries
   Bool_t fIsSorted; // Flags if the bin edges are sorted densitywise (or by bin endges in case of 1-dim )
   Bool_t fIsSortedAsc; // Flags if the bin edges are sorted densitywise (or by bin-edge for 1D) in ascending order
   std::vector<UInt_t> fBinsContent; // Holds the contents of the bins
   struct CompareAsc; // Predicate for ascending sort
   friend struct CompareAsc;
   struct CompareDesc; // Predicate for descending sort
   friend struct CompareDesc;
   TKDTreeBinning(TKDTreeBinning& bins);           // Disallowed copy constructor
   TKDTreeBinning operator=(TKDTreeBinning& bins); // Disallowed assign operator
   void SetData(Double_t* data);
   void SetTreeData();
   void SetBinsEdges();
   void SetBinMinMaxEdges(Double_t* binEdges);
   void SetCommonBinEdges(Double_t* binEdges);
   void SetBinsContent();
   void ReadjustMinBinEdges(Double_t* binEdges);
   void ReadjustMaxBinEdges(Double_t* binEdges);

public:

   // flag bits
   enum {
      kAdjustBinEdges     = BIT(14)  // adjust bin edges to avoid overlapping with data
   };


   TKDTreeBinning(UInt_t dataSize, UInt_t dataDim, Double_t* data, UInt_t nBins = 100, bool adjustBinEdges = false);
   ~TKDTreeBinning();
   void SetNBins(UInt_t bins);
   void SortBinsByDensity(Bool_t sortAsc = kTRUE);
   const Double_t* GetBinsMinEdges() const;
   const Double_t* GetBinsMaxEdges() const;
   std::pair<const Double_t*, const Double_t*> GetBinsEdges() const;
   std::pair<const Double_t*, const Double_t*> GetBinEdges(UInt_t bin) const;
   const Double_t* GetBinMinEdges(UInt_t bin) const;
   const Double_t* GetBinMaxEdges(UInt_t bin) const;
   UInt_t GetNBins() const;
   UInt_t GetDim() const;
   UInt_t GetBinContent(UInt_t bin) const;
   TKDTreeID* GetTree() const;
   const Double_t* GetDimData(UInt_t dim) const;
   Double_t GetDataMin(UInt_t dim) const;
   Double_t GetDataMax(UInt_t dim) const;
   Double_t GetBinDensity(UInt_t bin) const;
   Double_t GetBinVolume(UInt_t bin) const;
   const Double_t* GetBinCenter(UInt_t bin) const;
   const Double_t* GetBinWidth(UInt_t bin) const;
   UInt_t GetBinMaxDensity() const;
   UInt_t GetBinMinDensity() const;
   const Double_t* GetOneDimBinEdges() const;
   const Double_t* SortOneDimBinEdges(Bool_t sortAsc = kTRUE);
   void FillBinData(ROOT::Fit::BinData & data) const;
   UInt_t FindBin(const Double_t * point) const; 

   ClassDef(TKDTreeBinning, 1)

};

#endif // ROOT_TKDTreeBinning

 TKDTreeBinning.h:1
 TKDTreeBinning.h:2
 TKDTreeBinning.h:3
 TKDTreeBinning.h:4
 TKDTreeBinning.h:5
 TKDTreeBinning.h:6
 TKDTreeBinning.h:7
 TKDTreeBinning.h:8
 TKDTreeBinning.h:9
 TKDTreeBinning.h:10
 TKDTreeBinning.h:11
 TKDTreeBinning.h:12
 TKDTreeBinning.h:13
 TKDTreeBinning.h:14
 TKDTreeBinning.h:15
 TKDTreeBinning.h:16
 TKDTreeBinning.h:17
 TKDTreeBinning.h:18
 TKDTreeBinning.h:19
 TKDTreeBinning.h:20
 TKDTreeBinning.h:21
 TKDTreeBinning.h:22
 TKDTreeBinning.h:23
 TKDTreeBinning.h:24
 TKDTreeBinning.h:25
 TKDTreeBinning.h:26
 TKDTreeBinning.h:27
 TKDTreeBinning.h:28
 TKDTreeBinning.h:29
 TKDTreeBinning.h:30
 TKDTreeBinning.h:31
 TKDTreeBinning.h:32
 TKDTreeBinning.h:33
 TKDTreeBinning.h:34
 TKDTreeBinning.h:35
 TKDTreeBinning.h:36
 TKDTreeBinning.h:37
 TKDTreeBinning.h:38
 TKDTreeBinning.h:39
 TKDTreeBinning.h:40
 TKDTreeBinning.h:41
 TKDTreeBinning.h:42
 TKDTreeBinning.h:43
 TKDTreeBinning.h:44
 TKDTreeBinning.h:45
 TKDTreeBinning.h:46
 TKDTreeBinning.h:47
 TKDTreeBinning.h:48
 TKDTreeBinning.h:49
 TKDTreeBinning.h:50
 TKDTreeBinning.h:51
 TKDTreeBinning.h:52
 TKDTreeBinning.h:53
 TKDTreeBinning.h:54
 TKDTreeBinning.h:55
 TKDTreeBinning.h:56
 TKDTreeBinning.h:57
 TKDTreeBinning.h:58
 TKDTreeBinning.h:59
 TKDTreeBinning.h:60
 TKDTreeBinning.h:61
 TKDTreeBinning.h:62
 TKDTreeBinning.h:63
 TKDTreeBinning.h:64
 TKDTreeBinning.h:65
 TKDTreeBinning.h:66
 TKDTreeBinning.h:67
 TKDTreeBinning.h:68
 TKDTreeBinning.h:69
 TKDTreeBinning.h:70
 TKDTreeBinning.h:71
 TKDTreeBinning.h:72
 TKDTreeBinning.h:73
 TKDTreeBinning.h:74
 TKDTreeBinning.h:75
 TKDTreeBinning.h:76
 TKDTreeBinning.h:77
 TKDTreeBinning.h:78
 TKDTreeBinning.h:79
 TKDTreeBinning.h:80
 TKDTreeBinning.h:81
 TKDTreeBinning.h:82
 TKDTreeBinning.h:83
 TKDTreeBinning.h:84
 TKDTreeBinning.h:85
 TKDTreeBinning.h:86
 TKDTreeBinning.h:87
 TKDTreeBinning.h:88
 TKDTreeBinning.h:89
 TKDTreeBinning.h:90
 TKDTreeBinning.h:91
 TKDTreeBinning.h:92
 TKDTreeBinning.h:93
 TKDTreeBinning.h:94
 TKDTreeBinning.h:95
 TKDTreeBinning.h:96
 TKDTreeBinning.h:97
 TKDTreeBinning.h:98
 TKDTreeBinning.h:99
 TKDTreeBinning.h:100
 TKDTreeBinning.h:101
 TKDTreeBinning.h:102
 TKDTreeBinning.h:103