ROOT logo
// @(#)root/hist:$Id: THnSparse.h 28292 2009-04-20 15:27:12Z moneta $
// Author: Axel Naumann (2007-09-11)

/*************************************************************************
 * Copyright (C) 1995-2007, Rene Brun and Fons Rademakers.               *
 * All rights reserved.                                                  *
 *                                                                       *
 * For the licensing terms see $ROOTSYS/LICENSE.                         *
 * For the list of contributors see $ROOTSYS/README/CREDITS.             *
 *************************************************************************/

#ifndef ROOT_THnSparse
#define ROOT_THnSparse

/*************************************************************************

 THnSparse: histogramming multi-dimensional, sparse distributions in
 a memory-efficient way.

*************************************************************************/


#ifndef ROOT_TExMap
#include "TExMap.h"
#endif
#ifndef ROOT_TNamed
#include "TNamed.h"
#endif
#ifndef ROOT_TObjArray
#include "TObjArray.h"
#endif
#ifndef ROOT_TArrayD
#include "TArrayD.h"
#endif

// needed only for template instantiations of THnSparseT:
#ifndef ROOT_TArrayF
#include "TArrayF.h"
#endif
#ifndef ROOT_TArrayL
#include "TArrayL.h"
#endif
#ifndef ROOT_TArrayI
#include "TArrayI.h"
#endif
#ifndef ROOT_TArrayS
#include "TArrayS.h"
#endif
#ifndef ROOT_TArrayC
#include "TArrayC.h"
#endif

class TAxis;
class TCollection;
class TH1;
class TH1D;
class TH2D;
class TH3D;

class THnSparseArrayChunk: public TObject {
 private:

   THnSparseArrayChunk(const THnSparseArrayChunk&); // Not implemented
   THnSparseArrayChunk& operator=(const THnSparseArrayChunk&); // Not implemented

 public:
   THnSparseArrayChunk():
      fCoordinateAllocationSize(-1), fSingleCoordinateSize(0), fCoordinatesSize(0), fCoordinates(0),
      fContent(0), fSumw2(0) {}

   THnSparseArrayChunk(Int_t coordsize, bool errors, TArray* cont);
   virtual ~THnSparseArrayChunk();

   Int_t    fCoordinateAllocationSize; //! size of the allocated coordinate buffer; -1 means none or fCoordinatesSize
   Int_t    fSingleCoordinateSize; // size of a single bin coordinate
   Int_t    fCoordinatesSize;      // size of the bin coordinate buffer
   Char_t  *fCoordinates;          //[fCoordinatesSize] compact bin coordinate buffer
   TArray  *fContent;              // bin content
   TArrayD *fSumw2;                // bin errors

   void AddBin(ULong_t idx, const Char_t* idxbuf);
   void AddBinContent(ULong_t idx, Double_t v = 1.) {
      fContent->SetAt(v + fContent->GetAt(idx), idx);
      if (fSumw2)
         fSumw2->SetAt(v * v+ fSumw2->GetAt(idx), idx);
   }
   void Sumw2();
   ULong64_t GetEntries() const { return fCoordinatesSize / fSingleCoordinateSize; }
   Bool_t Matches(Int_t idx, const Char_t* idxbuf) const {
      // Check whether bin at idx batches idxbuf.
      // If we don't store indexes we trust the caller that it does match,
      // see comment in THnSparseCompactBinCoord::GetHash().
      return fCoordinatesSize <= 4 ||
         !memcmp(fCoordinates + idx * fSingleCoordinateSize, idxbuf, fSingleCoordinateSize); }

   ClassDef(THnSparseArrayChunk, 1); // chunks of linearized bins
};

class THnSparseCompactBinCoord;

class THnSparse: public TNamed {
 private:
   Int_t      fNdimensions;  // number of dimensions
   Int_t      fChunkSize;    // number of entries for each chunk
   Long64_t   fFilledBins;   // number of filled bins
   TObjArray  fAxes;         // axes of the histogram
   TObjArray  fBinContent;   // array of THnSparseArrayChunk
   TExMap     fBins;         // filled bins
   TExMap     fBinsContinued;// filled bins for non-unique hashes, containing pairs of (bin index 0, bin index 1)
   Double_t   fEntries;      // number of entries, spread over chunks
   Double_t   fTsumw;        // total sum of weights
   Double_t   fTsumw2;       // total sum of weights squared; -1 if no errors are calculated
   TArrayD    fTsumwx;       // total sum of weight*X for each dimension
   TArrayD    fTsumwx2;      // total sum of weight*X*X for each dimension
   THnSparseCompactBinCoord *fCompactCoord; //! compact coordinate
   Double_t  *fIntegral;     //! array with bin weight sums
   enum {
      kNoInt,
      kValidInt,
      kInvalidInt
   } fIntegralStatus;        //! status of integral

   THnSparse(const THnSparse&); // Not implemented
   THnSparse& operator=(const THnSparse&); // Not implemented

 protected:

   THnSparse();
   THnSparse(const char* name, const char* title, Int_t dim,
             const Int_t* nbins, const Double_t* xmin, const Double_t* xmax,
             Int_t chunksize);
   Int_t GetChunkSize() const { return fChunkSize; }
   THnSparseCompactBinCoord* GetCompactCoord() const;
   THnSparseArrayChunk* GetChunk(Int_t idx) const {
      return (THnSparseArrayChunk*) fBinContent[idx]; }

   THnSparseArrayChunk* AddChunk();
   virtual TArray* GenerateArray() const = 0;
   Long_t GetBinIndexForCurrentBin(Bool_t allocate);
   Long_t Fill(Long_t bin, Double_t w) {
      // Increment the bin content of "bin" by "w",
      // return the bin index.
      fEntries += 1;
      if (GetCalculateErrors()) {
         fTsumw += w;
         fTsumw2 += w*w;
      }
      fIntegralStatus = kInvalidInt;
      THnSparseArrayChunk* chunk = GetChunk(bin / fChunkSize);
      chunk->AddBinContent(bin % fChunkSize, w);
      return bin;
   }
   THnSparse* CloneEmpty(const char* name, const char* title,
                         const TObjArray* axes, Int_t chunksize,
                         Bool_t keepTargetAxis) const;

   Bool_t CheckConsistency(const THnSparse *h, const char *tag) const;
   Bool_t IsInRange(Int_t *coord) const;
   TH1* CreateHist(const char* name, const char* title,
                   const TObjArray* axes, Bool_t keepTargetAxis) const;
   TObject* ProjectionAny(Int_t ndim, const Int_t* dim,
                          Bool_t wantSparse, Option_t* option = "") const;

 public:
   virtual ~THnSparse();

   Int_t  GetNChunks() const { return fBinContent.GetEntriesFast(); }
   TObjArray* GetListOfAxes() { return &fAxes; }
   TAxis* GetAxis(Int_t dim) const { return (TAxis*)fAxes[dim]; }

   Long_t Fill(const Double_t *x, Double_t w = 1.) {
      if (GetCalculateErrors()) {
         for (Int_t d = 0; d < fNdimensions; ++d) {
            const Double_t xd = x[d];
            fTsumwx[d]  += w * xd;
            fTsumwx2[d] += w * xd * xd;
         }
      }
      return Fill(GetBin(x), w);
   }
   Long_t Fill(const char* name[], Double_t w = 1.) {
      return Fill(GetBin(name), w);
   }

   Double_t GetEntries() const { return fEntries; }
   Double_t GetWeightSum() const { return fTsumw; }
   Long64_t GetNbins() const { return fFilledBins; }
   Int_t    GetNdimensions() const { return fNdimensions; }
   Bool_t   GetCalculateErrors() const { return fTsumw2 >= 0.; }
   void     CalculateErrors(Bool_t calc = kTRUE) {
      // Calculate errors (or not if "calc" == kFALSE)
      if (calc) Sumw2();
      else fTsumw2 = -1.;
   }

   Long_t GetBin(const Int_t* idx, Bool_t allocate = kTRUE);
   Long_t GetBin(const Double_t* x, Bool_t allocate = kTRUE);
   Long_t GetBin(const char* name[], Bool_t allocate = kTRUE);

   void SetBinEdges(Int_t idim, const Double_t* bins);
   void SetBinContent(const Int_t* x, Double_t v);
   void SetBinError(const Int_t* x, Double_t e);
   void AddBinContent(const Int_t* x, Double_t v = 1.);
   void SetEntries(Double_t entries) { fEntries = entries; }

   Double_t GetBinContent(const Int_t *idx) const;
   Double_t GetBinContent(Long64_t bin, Int_t* idx = 0) const;
   Double_t GetBinError(const Int_t *idx) const;
   Double_t GetBinError(Long64_t linidx) const;

   Double_t GetSparseFractionBins() const;
   Double_t GetSparseFractionMem() const;

   Double_t GetSumw() const  { return fTsumw; }
   Double_t GetSumw2() const { return fTsumw2; }
   Double_t GetSumwx(Int_t dim) const  { return fTsumwx[dim]; }
   Double_t GetSumwx2(Int_t dim) const { return fTsumwx2[dim]; }

   TH1D*      Projection(Int_t xDim, Option_t* option = "") const;
   TH2D*      Projection(Int_t xDim, Int_t yDim,
                         Option_t* option = "") const;
   TH3D*      Projection(Int_t xDim, Int_t yDim, Int_t zDim,
                         Option_t* option = "") const;
   THnSparse* Projection(Int_t ndim, const Int_t* dim,
                         Option_t* option = "") const;

   THnSparse* Rebin(Int_t group) const;
   THnSparse* Rebin(const Int_t* group) const;

   Long64_t   Merge(TCollection* list);

   void Scale(Double_t c);
   void Add(const THnSparse* h, Double_t c=1.);
   void Multiply(const THnSparse* h);
   void Divide(const THnSparse* h);
   void Divide(const THnSparse* h1, const THnSparse* h2, Double_t c1 = 1., Double_t c2 = 1., Option_t* option="");
   void RebinnedAdd(const THnSparse* h, Double_t c=1.);

   void Reset(Option_t* option = "");
   void Sumw2();

   Double_t ComputeIntegral();
   void GetRandom(Double_t *rand, Bool_t subBinRandom = kTRUE);

   //void Draw(Option_t* option = "");

   ClassDef(THnSparse, 1); // Interfaces of sparse n-dimensional histogram
};



//______________________________________________________________________________
//
// Templated implementation of the abstract base THnSparse.
// All functionality and the interfaces to be used are in THnSparse!
//
// THnSparse does not know how to store any bin content itself. Instead, this
// is delegated to the derived, templated class: the template parameter decides
// what the format for the bin content is. In fact it even defines the array
// itself; possible implementations probably derive from TArray.
//
// Typedefs exist for template parematers with ROOT's generic types:
//
//   Templated name        Typedef       Bin content type
//   THnSparseT<TArrayC>   THnSparseC    Char_r
//   THnSparseT<TArrayS>   THnSparseS    Short_t
//   THnSparseT<TArrayI>   THnSparseI    Int_t
//   THnSparseT<TArrayL>   THnSparseL    Long_t
//   THnSparseT<TArrayF>   THnSparseF    Float_t
//   THnSparseT<TArrayD>   THnSparseD    Double_t
//
// We recommend to use THnSparseC wherever possible, and to map its value space
// of 256 possible values to e.g. float values outside the class. This saves an
// enourmous amount of memory. Only if more than 256 values need to be
// distinguished should e.g. THnSparseS or even THnSparseF be chosen.
//
// Implementation detail: the derived, templated class is kept extremely small
// on purpose. That way the (templated thus inlined) uses of this class will
// only create a small amount of machine code, in contrast to e.g. STL.
//______________________________________________________________________________

template <class CONT>
class THnSparseT: public THnSparse {
 public:
   THnSparseT() {}
   THnSparseT(const char* name, const char* title, Int_t dim,
              const Int_t* nbins, const Double_t* xmin = 0,
              const Double_t* xmax = 0, Int_t chunksize = 1024 * 16):
      THnSparse(name, title, dim, nbins, xmin, xmax, chunksize) {}

   TArray* GenerateArray() const { return new CONT(GetChunkSize()); }
 private:
   ClassDef(THnSparseT, 1); // Sparse n-dimensional histogram with templated content
};

typedef THnSparseT<TArrayD> THnSparseD;
typedef THnSparseT<TArrayF> THnSparseF;
typedef THnSparseT<TArrayL> THnSparseL;
typedef THnSparseT<TArrayI> THnSparseI;
typedef THnSparseT<TArrayS> THnSparseS;
typedef THnSparseT<TArrayC> THnSparseC;

#endif //  ROOT_THnSparse
 THnSparse.h:1
 THnSparse.h:2
 THnSparse.h:3
 THnSparse.h:4
 THnSparse.h:5
 THnSparse.h:6
 THnSparse.h:7
 THnSparse.h:8
 THnSparse.h:9
 THnSparse.h:10
 THnSparse.h:11
 THnSparse.h:12
 THnSparse.h:13
 THnSparse.h:14
 THnSparse.h:15
 THnSparse.h:16
 THnSparse.h:17
 THnSparse.h:18
 THnSparse.h:19
 THnSparse.h:20
 THnSparse.h:21
 THnSparse.h:22
 THnSparse.h:23
 THnSparse.h:24
 THnSparse.h:25
 THnSparse.h:26
 THnSparse.h:27
 THnSparse.h:28
 THnSparse.h:29
 THnSparse.h:30
 THnSparse.h:31
 THnSparse.h:32
 THnSparse.h:33
 THnSparse.h:34
 THnSparse.h:35
 THnSparse.h:36
 THnSparse.h:37
 THnSparse.h:38
 THnSparse.h:39
 THnSparse.h:40
 THnSparse.h:41
 THnSparse.h:42
 THnSparse.h:43
 THnSparse.h:44
 THnSparse.h:45
 THnSparse.h:46
 THnSparse.h:47
 THnSparse.h:48
 THnSparse.h:49
 THnSparse.h:50
 THnSparse.h:51
 THnSparse.h:52
 THnSparse.h:53
 THnSparse.h:54
 THnSparse.h:55
 THnSparse.h:56
 THnSparse.h:57
 THnSparse.h:58
 THnSparse.h:59
 THnSparse.h:60
 THnSparse.h:61
 THnSparse.h:62
 THnSparse.h:63
 THnSparse.h:64
 THnSparse.h:65
 THnSparse.h:66
 THnSparse.h:67
 THnSparse.h:68
 THnSparse.h:69
 THnSparse.h:70
 THnSparse.h:71
 THnSparse.h:72
 THnSparse.h:73
 THnSparse.h:74
 THnSparse.h:75
 THnSparse.h:76
 THnSparse.h:77
 THnSparse.h:78
 THnSparse.h:79
 THnSparse.h:80
 THnSparse.h:81
 THnSparse.h:82
 THnSparse.h:83
 THnSparse.h:84
 THnSparse.h:85
 THnSparse.h:86
 THnSparse.h:87
 THnSparse.h:88
 THnSparse.h:89
 THnSparse.h:90
 THnSparse.h:91
 THnSparse.h:92
 THnSparse.h:93
 THnSparse.h:94
 THnSparse.h:95
 THnSparse.h:96
 THnSparse.h:97
 THnSparse.h:98
 THnSparse.h:99
 THnSparse.h:100
 THnSparse.h:101
 THnSparse.h:102
 THnSparse.h:103
 THnSparse.h:104
 THnSparse.h:105
 THnSparse.h:106
 THnSparse.h:107
 THnSparse.h:108
 THnSparse.h:109
 THnSparse.h:110
 THnSparse.h:111
 THnSparse.h:112
 THnSparse.h:113
 THnSparse.h:114
 THnSparse.h:115
 THnSparse.h:116
 THnSparse.h:117
 THnSparse.h:118
 THnSparse.h:119
 THnSparse.h:120
 THnSparse.h:121
 THnSparse.h:122
 THnSparse.h:123
 THnSparse.h:124
 THnSparse.h:125
 THnSparse.h:126
 THnSparse.h:127
 THnSparse.h:128
 THnSparse.h:129
 THnSparse.h:130
 THnSparse.h:131
 THnSparse.h:132
 THnSparse.h:133
 THnSparse.h:134
 THnSparse.h:135
 THnSparse.h:136
 THnSparse.h:137
 THnSparse.h:138
 THnSparse.h:139
 THnSparse.h:140
 THnSparse.h:141
 THnSparse.h:142
 THnSparse.h:143
 THnSparse.h:144
 THnSparse.h:145
 THnSparse.h:146
 THnSparse.h:147
 THnSparse.h:148
 THnSparse.h:149
 THnSparse.h:150
 THnSparse.h:151
 THnSparse.h:152
 THnSparse.h:153
 THnSparse.h:154
 THnSparse.h:155
 THnSparse.h:156
 THnSparse.h:157
 THnSparse.h:158
 THnSparse.h:159
 THnSparse.h:160
 THnSparse.h:161
 THnSparse.h:162
 THnSparse.h:163
 THnSparse.h:164
 THnSparse.h:165
 THnSparse.h:166
 THnSparse.h:167
 THnSparse.h:168
 THnSparse.h:169
 THnSparse.h:170
 THnSparse.h:171
 THnSparse.h:172
 THnSparse.h:173
 THnSparse.h:174
 THnSparse.h:175
 THnSparse.h:176
 THnSparse.h:177
 THnSparse.h:178
 THnSparse.h:179
 THnSparse.h:180
 THnSparse.h:181
 THnSparse.h:182
 THnSparse.h:183
 THnSparse.h:184
 THnSparse.h:185
 THnSparse.h:186
 THnSparse.h:187
 THnSparse.h:188
 THnSparse.h:189
 THnSparse.h:190
 THnSparse.h:191
 THnSparse.h:192
 THnSparse.h:193
 THnSparse.h:194
 THnSparse.h:195
 THnSparse.h:196
 THnSparse.h:197
 THnSparse.h:198
 THnSparse.h:199
 THnSparse.h:200
 THnSparse.h:201
 THnSparse.h:202
 THnSparse.h:203
 THnSparse.h:204
 THnSparse.h:205
 THnSparse.h:206
 THnSparse.h:207
 THnSparse.h:208
 THnSparse.h:209
 THnSparse.h:210
 THnSparse.h:211
 THnSparse.h:212
 THnSparse.h:213
 THnSparse.h:214
 THnSparse.h:215
 THnSparse.h:216
 THnSparse.h:217
 THnSparse.h:218
 THnSparse.h:219
 THnSparse.h:220
 THnSparse.h:221
 THnSparse.h:222
 THnSparse.h:223
 THnSparse.h:224
 THnSparse.h:225
 THnSparse.h:226
 THnSparse.h:227
 THnSparse.h:228
 THnSparse.h:229
 THnSparse.h:230
 THnSparse.h:231
 THnSparse.h:232
 THnSparse.h:233
 THnSparse.h:234
 THnSparse.h:235
 THnSparse.h:236
 THnSparse.h:237
 THnSparse.h:238
 THnSparse.h:239
 THnSparse.h:240
 THnSparse.h:241
 THnSparse.h:242
 THnSparse.h:243
 THnSparse.h:244
 THnSparse.h:245
 THnSparse.h:246
 THnSparse.h:247
 THnSparse.h:248
 THnSparse.h:249
 THnSparse.h:250
 THnSparse.h:251
 THnSparse.h:252
 THnSparse.h:253
 THnSparse.h:254
 THnSparse.h:255
 THnSparse.h:256
 THnSparse.h:257
 THnSparse.h:258
 THnSparse.h:259
 THnSparse.h:260
 THnSparse.h:261
 THnSparse.h:262
 THnSparse.h:263
 THnSparse.h:264
 THnSparse.h:265
 THnSparse.h:266
 THnSparse.h:267
 THnSparse.h:268
 THnSparse.h:269
 THnSparse.h:270
 THnSparse.h:271
 THnSparse.h:272
 THnSparse.h:273
 THnSparse.h:274
 THnSparse.h:275
 THnSparse.h:276
 THnSparse.h:277
 THnSparse.h:278
 THnSparse.h:279
 THnSparse.h:280
 THnSparse.h:281
 THnSparse.h:282
 THnSparse.h:283
 THnSparse.h:284
 THnSparse.h:285
 THnSparse.h:286
 THnSparse.h:287
 THnSparse.h:288
 THnSparse.h:289
 THnSparse.h:290
 THnSparse.h:291
 THnSparse.h:292
 THnSparse.h:293
 THnSparse.h:294
 THnSparse.h:295
 THnSparse.h:296
 THnSparse.h:297
 THnSparse.h:298
 THnSparse.h:299
 THnSparse.h:300
 THnSparse.h:301
 THnSparse.h:302
 THnSparse.h:303