// @(#)root/hist:$Id$
// Author: Axel Naumann (2007-09-11)

/*************************************************************************
 * Copyright (C) 1995-2012, 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_THnBase
#include "THnBase.h"
#endif
#ifndef ROOT_TExMap
#include "TExMap.h"
#endif
#ifndef ROOT_THnSparse_Internal
#include "THnSparse_Internal.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 THnSparseCompactBinCoord;

class THnSparse: public THnBase {
 private:
   Int_t      fChunkSize;    // number of entries for each chunk
   Long64_t   fFilledBins;   // number of filled bins
   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)
   THnSparseCompactBinCoord *fCompactCoord; //! compact coordinate

   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);
   THnSparseCompactBinCoord* GetCompactCoord() const;
   THnSparseArrayChunk* GetChunk(Int_t idx) const {
      return (THnSparseArrayChunk*) fBinContent[idx]; }

   THnSparseArrayChunk* AddChunk();
   void Reserve(Long64_t nbins);
   void FillExMap();
   virtual TArray* GenerateArray() const = 0;
   Long64_t GetBinIndexForCurrentBin(Bool_t allocate);
   void FillBin(Long64_t bin, Double_t w) {
      // Increment the bin content of "bin" by "w",
      // return the bin index.
      THnSparseArrayChunk* chunk = GetChunk(bin / fChunkSize);
      chunk->AddBinContent(bin % fChunkSize, w);
      FillBinBase(w);
   }
   void InitStorage(Int_t* nbins, Int_t chunkSize);

 public:
   virtual ~THnSparse();

   static THnSparse* CreateSparse(const char* name, const char* title,
                                  const TH1* h1, Int_t chunkSize = 1024 * 16) {
      return (THnSparse*) CreateHnAny(name, title, h1, kTRUE /*sparse*/,
                                       chunkSize);
   }
   static THnSparse* CreateSparse(const char* name, const char* title,
                                  const THnBase* hn, Int_t chunkSize = 1024 * 16) {
      return (THnSparse*) CreateHnAny(name, title, hn, kTRUE /*sparse*/,
                                       chunkSize);
   }

   Int_t GetChunkSize() const { return fChunkSize; }
   Int_t GetNChunks() const { return fBinContent.GetEntriesFast(); }

   ROOT::THnBaseBinIter* CreateIter(Bool_t respectAxisRange) const;

   Long64_t GetNbins() const { return fFilledBins; }
   void SetFilledBins(Long64_t nbins) { fFilledBins = nbins; }

   Long64_t GetBin(const Int_t* idx) const { return const_cast<THnSparse*>(this)->GetBin(idx, kFALSE); }
   Long64_t GetBin(const Double_t* x) const { return const_cast<THnSparse*>(this)->GetBin(x, kFALSE); }
   Long64_t GetBin(const char* name[]) const { return const_cast<THnSparse*>(this)->GetBin(name, kFALSE); }
   Long64_t GetBin(const Int_t* idx, Bool_t allocate = kTRUE);
   Long64_t GetBin(const Double_t* x, Bool_t allocate = kTRUE);
   Long64_t GetBin(const char* name[], Bool_t allocate = kTRUE);

   void SetBinContent(const Int_t* idx, Double_t v) {
      // Forwards to THnBase::SetBinContent().
      // Non-virtual, CINT-compatible replacement of a using declaration.
      THnBase::SetBinContent(idx, v);
   }
   void SetBinContent(Long64_t bin, Double_t v);
   void SetBinError2(Long64_t bin, Double_t e2);
   void AddBinContent(const Int_t* idx, Double_t v = 1.) {
      // Forwards to THnBase::SetBinContent().
      // Non-virtual, CINT-compatible replacement of a using declaration.
      THnBase::AddBinContent(idx, v);
   }
   void AddBinContent(Long64_t bin, Double_t v = 1.);
   void AddBinError2(Long64_t bin, Double_t e2);

   Double_t GetBinContent(const Int_t *idx) const {
      // Forwards to THnBase::GetBinContent() overload.
      // Non-virtual, CINT-compatible replacement of a using declaration.
      return THnBase::GetBinContent(idx);
   }
   Double_t GetBinContent(Long64_t bin, Int_t* idx = 0) const;
   Double_t GetBinError2(Long64_t linidx) const;

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

   TH1D*      Projection(Int_t xDim, Option_t* option = "") const{
      // Forwards to THnBase::Projection().
      // Non-virtual, as a CINT-compatible replacement of a using
      // declaration.
      return THnBase::Projection(xDim, option);
   }

   TH2D*      Projection(Int_t yDim, Int_t xDim,
                         Option_t* option = "") const {
      // Forwards to THnBase::Projection().
      // Non-virtual, as a CINT-compatible replacement of a using
      // declaration.
      return THnBase::Projection(yDim, xDim, option);
   }

   TH3D*      Projection(Int_t xDim, Int_t yDim, Int_t zDim,
                         Option_t* option = "") const {
      // Forwards to THnBase::Projection().
      // Non-virtual, as a CINT-compatible replacement of a using
      // declaration.
      return THnBase::Projection(xDim, yDim, zDim, option);
   }

   THnSparse* Projection(Int_t ndim, const Int_t* dim,
                         Option_t* option = "") const {
      return (THnSparse*) ProjectionND(ndim, dim, option);
   }

   THnSparse* Rebin(Int_t group) const {
      return (THnSparse*) RebinBase(group);
   }
   THnSparse* Rebin(const Int_t* group) const {
      return (THnSparse*) RebinBase(group);
   }

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

   ClassDef(THnSparse, 3); // 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_t
//   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