ROOT logo
// @(#)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.             *
 *************************************************************************/

#include "THnSparse.h"

#include "TAxis.h"
#include "TClass.h"
#include "TDataMember.h"
#include "TDataType.h"

namespace {
//______________________________________________________________________________
//
// THnSparseBinIter iterates over all filled bins of a THnSparse.
//______________________________________________________________________________

   class THnSparseBinIter: public ROOT::THnBaseBinIter {
   public:
      THnSparseBinIter(Bool_t respectAxisRange, const THnSparse* hist):
         ROOT::THnBaseBinIter(respectAxisRange), fHist(hist),
         fNbins(hist->GetNbins()), fIndex(-1) {
         // Construct a THnSparseBinIter
         fCoord = new Int_t[hist->GetNdimensions()];
         fCoord[0] = -1;
      }
      virtual ~THnSparseBinIter() { delete [] fCoord; }

      virtual Int_t GetCoord(Int_t dim) const;
      virtual Long64_t Next(Int_t* coord = 0);

   private:
      THnSparseBinIter(const THnSparseBinIter&); // intentionally unimplemented
      THnSparseBinIter& operator=(const THnSparseBinIter&); // intentionally unimplemented

      const THnSparse* fHist;
      Int_t* fCoord; // coord buffer for fIndex; fCoord[0] == -1 if not yet calculated
      Long64_t fNbins; // number of bins to iterate over
      Long64_t fIndex; // current bin index
   };
}

Int_t THnSparseBinIter::GetCoord(Int_t dim) const
{
   if (fCoord[0] == -1) {
      fHist->GetBinContent(fIndex, fCoord);
   }
   return fCoord[dim];
}

Long64_t THnSparseBinIter::Next(Int_t* coord /*= 0*/)
{
   // Get next bin index (in range if RespectsAxisRange()).
   // If coords != 0, set it to the index's axis coordinates
   // (i.e. coord must point to an array of Int_t[fNdimension]
   if (!fHist) return -1;

   fCoord[0] = -1;
   Int_t* useCoordBuf = fCoord;
   if (coord) {
      useCoordBuf = coord;
      coord[0] = -1;
   }

   do {
      ++fIndex;
      if (fIndex >= fHist->GetNbins()) {
         fHist = 0;
         return -1;
      }
      if (RespectsAxisRange()) {
         fHist->GetBinContent(fIndex, useCoordBuf);
      }
   } while (RespectsAxisRange()
            && !fHist->IsInRange(useCoordBuf)
            && (fHaveSkippedBin = kTRUE /* assignment! */));

   if (coord && coord[0] == -1) {
      if (fCoord[0] == -1) {
         fHist->GetBinContent(fIndex, coord);
      } else {
         memcpy(coord, fCoord, fHist->GetNdimensions() * sizeof(Int_t));
      }
   }

   return fIndex;
}



//______________________________________________________________________________
//
// THnSparseCoordCompression is a class used by THnSparse internally. It
// represents a compacted n-dimensional array of bin coordinates (indices).
// As the total number of bins in each dimension is known by THnSparse, bin
// indices can be compacted to only use the amount of bins needed by the total
// number of bins in each dimension. E.g. for a THnSparse with
// {15, 100, 2, 20, 10, 100} bins per dimension, a bin index will only occupy
// 28 bits (4+7+1+5+4+7), i.e. less than a 32bit integer. The tricky part is
// the fast compression and decompression, the platform-independent storage
// (think of endianness: the bits of the number 0x123456 depend on the
// platform), and the hashing needed by THnSparseArrayChunk.
//______________________________________________________________________________

class THnSparseCoordCompression {
public:
   THnSparseCoordCompression(Int_t dim, const Int_t* nbins);
   THnSparseCoordCompression(const THnSparseCoordCompression& other);
   ~THnSparseCoordCompression();

   THnSparseCoordCompression& operator=(const THnSparseCoordCompression& other);

   ULong64_t GetHashFromBuffer(const Char_t* buf) const;
   Int_t     GetBufferSize() const { return fCoordBufferSize; }
   Int_t     GetNdimensions() const { return fNdimensions; }
   void      SetCoordFromBuffer(const Char_t* buf_in, Int_t* coord_out) const;
   ULong64_t SetBufferFromCoord(const Int_t* coord_in, Char_t* buf_out) const;

protected:
   Int_t     GetNumBits(Int_t n) const {
      // return the number of bits allocated by the number "n"
      Int_t r = (n > 0);
      while (n/=2) ++r;
      return r;
   }
private:
   Int_t  fNdimensions;     // number of dimensions
   Int_t  fCoordBufferSize; // size of coordbuf
   Int_t *fBitOffsets;      //[fNdimensions + 1] bit offset of each axis index
};


//______________________________________________________________________________
//______________________________________________________________________________


//______________________________________________________________________________
THnSparseCoordCompression::THnSparseCoordCompression(Int_t dim, const Int_t* nbins):
   fNdimensions(dim), fCoordBufferSize(0), fBitOffsets(0)
{
   // Initialize a THnSparseCoordCompression object with "dim" dimensions
   // and "bins" holding the number of bins for each dimension; it
   // stores the 

   fBitOffsets = new Int_t[dim + 1];

   int shift = 0;
   for (Int_t i = 0; i < dim; ++i) {
      fBitOffsets[i] = shift;
      shift += GetNumBits(nbins[i] + 2);
   }
   fBitOffsets[dim] = shift;
   fCoordBufferSize = (shift + 7) / 8;
}


//______________________________________________________________________________
THnSparseCoordCompression::THnSparseCoordCompression(const THnSparseCoordCompression& other)
{
   // Construct a THnSparseCoordCompression from another one
   fNdimensions = other.fNdimensions;
   fCoordBufferSize = other.fCoordBufferSize;
   fBitOffsets = new Int_t[fNdimensions + 1];
   memcpy(fBitOffsets, other.fBitOffsets, sizeof(Int_t) * fNdimensions);
}


//______________________________________________________________________________
THnSparseCoordCompression& THnSparseCoordCompression::operator=(const THnSparseCoordCompression& other)
{
   // Set this to other if different.

   if (&other == this) return *this;

   fNdimensions = other.fNdimensions;
   fCoordBufferSize = other.fCoordBufferSize;
   delete [] fBitOffsets;
   fBitOffsets = new Int_t[fNdimensions + 1];
   memcpy(fBitOffsets, other.fBitOffsets, sizeof(Int_t) * fNdimensions);
   return *this;
}


//______________________________________________________________________________
THnSparseCoordCompression::~THnSparseCoordCompression()
{
   // destruct a THnSparseCoordCompression
   delete [] fBitOffsets;
}


//______________________________________________________________________________
void THnSparseCoordCompression::SetCoordFromBuffer(const Char_t* buf_in,
                                                  Int_t* coord_out) const
{
   // Given the compressed coordinate buffer buf_in, calculate ("decompact")
   // the bin coordinates and return them in coord_out.

   for (Int_t i = 0; i < fNdimensions; ++i) {
      const Int_t offset = fBitOffsets[i] / 8;
      Int_t shift = fBitOffsets[i] % 8;
      Int_t nbits = fBitOffsets[i + 1] - fBitOffsets[i];
      const UChar_t* pbuf = (const UChar_t*) buf_in + offset;
      coord_out[i] = *pbuf >> shift;
      Int_t subst = (Int_t) -1;
      subst = subst << nbits;
      nbits -= (8 - shift);
      shift = 8 - shift;
      for (Int_t n = 0; n * 8 < nbits; ++n) {
         ++pbuf;
         coord_out[i] += *pbuf << shift;
         shift += 8;
      }
      coord_out[i] &= ~subst;
   }
}


//______________________________________________________________________________
ULong64_t THnSparseCoordCompression::SetBufferFromCoord(const Int_t* coord_in,
                                                       Char_t* buf_out) const
{
   // Given the cbin coordinates coord_in, calculate ("compact")
   // the bin coordinates and return them in buf_in.
   // Return the hash value.

   if (fCoordBufferSize <= 8) {
      ULong64_t l64buf = 0;
      for (Int_t i = 0; i < fNdimensions; ++i) {
         l64buf += ((ULong64_t)((UInt_t)coord_in[i])) << fBitOffsets[i];
      }
      memcpy(buf_out, &l64buf, sizeof(Long64_t));
      return l64buf;
   }

   // else: doesn't fit into a Long64_t:
   memset(buf_out, 0, fCoordBufferSize);
   for (Int_t i = 0; i < fNdimensions; ++i) {
      const Int_t offset = fBitOffsets[i] / 8;
      const Int_t shift = fBitOffsets[i] % 8;
      ULong64_t val = coord_in[i];

      Char_t* pbuf = buf_out + offset;
      *pbuf += 0xff & (val << shift);
      val = val >> (8 - shift);
      while (val) {
         ++pbuf;
         *pbuf += 0xff & val;
         val = val >> 8;
      }
   }

   return GetHashFromBuffer(buf_out);
}

/*
//______________________________________________________________________________
ULong64_t THnSparseCoordCompression::GetHashFromCoords(const Int_t* coord) const
{
   // Calculate hash from bin indexes.

   // Bins are addressed in two different modes, depending
   // on whether the compact bin index fits into a Long64_t or not.
   // If it does, we can use it as a "perfect hash" for the TExMap.
   // If not we build a hash from the compact bin index, and use that
   // as the TExMap's hash.

   if (fCoordBufferSize <= 8) {
      // fits into a Long64_t
      ULong64_t hash1 = 0;
      for (Int_t i = 0; i < fNdimensions; ++i) {
         hash1 += coord[i] << fBitOffsets[i];
      }
      return hash1;
   }

   // else: doesn't fit into a Long64_t:
   memset(coord, 0, fCoordBufferSize);
   for (Int_t i = 0; i < fNdimensions; ++i) {
      const Int_t offset = fBitOffsets[i] / 8;
      const Int_t shift = fBitOffsets[i] % 8;
      ULong64_t val = coord[i];

      Char_t* pbuf = fCoordBuffer + offset;
      *pbuf += 0xff & (val << shift);
      val = val >> (8 - shift);
      while (val) {
         ++pbuf;
         *pbuf += 0xff & val;
         val = val >> 8;
      }
   }

   ULong64_t hash = 5381;
   Char_t* str = fCoordBuffer;
   while (str - fCoordBuffer < fCoordBufferSize) {
      hash *= 5;
      hash += *(str++);
   }
   return hash;
}
*/


//______________________________________________________________________________
ULong64_t THnSparseCoordCompression::GetHashFromBuffer(const Char_t* buf) const
{
   // Calculate hash from compact bin index.

   // Bins are addressed in two different modes, depending
   // on whether the compact bin index fits into a Long64_t or not.
   // If it does, we can use it as a "perfect hash" for the TExMap.
   // If not we build a hash from the compact bin index, and use that
   // as the TExMap's hash.

   if (fCoordBufferSize <= 8) {
      // fits into a Long64_t
      ULong64_t hash1 = 0;
      memcpy(&hash1, buf, fCoordBufferSize);
      return hash1;
   }

   // else: doesn't fit into a Long64_t:
   ULong64_t hash = 5381;
   const Char_t* str = buf;
   while (str - buf < fCoordBufferSize) {
      hash *= 5;
      hash += *(str++);
   }
   return hash;
}




//______________________________________________________________________________
//
// THnSparseCompactBinCoord is a class used by THnSparse internally. It
// maps between an n-dimensional array of bin coordinates (indices) and
// its compact version, the THnSparseCoordCompression.
//______________________________________________________________________________

class THnSparseCompactBinCoord: public THnSparseCoordCompression {
public:
   THnSparseCompactBinCoord(Int_t dim, const Int_t* nbins);
   ~THnSparseCompactBinCoord();
   Int_t*    GetCoord() { return fCurrentBin; }
   const Char_t*   GetBuffer() const { return fCoordBuffer; }
   ULong64_t GetHash() const { return fHash; }
   void UpdateCoord() {
      fHash = SetBufferFromCoord(fCurrentBin, fCoordBuffer);
   }
   void      SetCoord(const Int_t* coord) {
      memcpy(fCurrentBin, coord, sizeof(Int_t) * GetNdimensions());
      fHash = SetBufferFromCoord(coord, fCoordBuffer);
   }
   void      SetBuffer(const Char_t* buf) {
      memcpy(fCoordBuffer, buf, GetBufferSize());
      fHash = GetHashFromBuffer(fCoordBuffer);
   }

private:
   // intentionally not implemented
   THnSparseCompactBinCoord(const THnSparseCompactBinCoord&);
   // intentionally not implemented
   THnSparseCompactBinCoord& operator=(const THnSparseCompactBinCoord&);

private:
   ULong64_t fHash;      // hash for current coordinates; 0 if not calculated
   Char_t *fCoordBuffer; // compact buffer of coordinates
   Int_t *fCurrentBin;   // current coordinates
};


//______________________________________________________________________________
//______________________________________________________________________________


//______________________________________________________________________________
THnSparseCompactBinCoord::THnSparseCompactBinCoord(Int_t dim, const Int_t* nbins):
   THnSparseCoordCompression(dim, nbins),
   fHash(0), fCoordBuffer(0), fCurrentBin(0)
{
   // Initialize a THnSparseCompactBinCoord object with "dim" dimensions
   // and "bins" holding the number of bins for each dimension.

   fCurrentBin = new Int_t[dim];
   size_t bufAllocSize = GetBufferSize();
   if (bufAllocSize < sizeof(Long64_t))
      bufAllocSize = sizeof(Long64_t);
   fCoordBuffer = new Char_t[bufAllocSize];
}


//______________________________________________________________________________
THnSparseCompactBinCoord::~THnSparseCompactBinCoord()
{
   // destruct a THnSparseCompactBinCoord

   delete [] fCoordBuffer;
   delete [] fCurrentBin;
}

//______________________________________________________________________________
//
// THnSparseArrayChunk is used internally by THnSparse.
//
// THnSparse stores its (dynamic size) array of bin coordinates and their
// contents (and possibly errors) in a TObjArray of THnSparseArrayChunk. Each
// of the chunks holds an array of THnSparseCompactBinCoord and the content
// (a TArray*), which is created outside (by the templated derived classes of
// THnSparse) and passed in at construction time.
//______________________________________________________________________________


ClassImp(THnSparseArrayChunk);

//______________________________________________________________________________
THnSparseArrayChunk::THnSparseArrayChunk(Int_t coordsize, bool errors, TArray* cont):
      fCoordinateAllocationSize(-1), fSingleCoordinateSize(coordsize), fCoordinatesSize(0),
      fCoordinates(0), fContent(cont),
      fSumw2(0)
{
   // (Default) initialize a chunk. Takes ownership of cont (~THnSparseArrayChunk deletes it),
   // and create an ArrayF for errors if "errors" is true.

   fCoordinateAllocationSize = fSingleCoordinateSize * cont->GetSize();
   fCoordinates = new Char_t[fCoordinateAllocationSize];
   if (errors) Sumw2();
}

//______________________________________________________________________________
THnSparseArrayChunk::~THnSparseArrayChunk()
{
   // Destructor
   delete fContent;
   delete [] fCoordinates;
   delete fSumw2;
}

//______________________________________________________________________________
void THnSparseArrayChunk::AddBin(Int_t idx, const Char_t* coordbuf)
{
   // Create a new bin in this chunk

   // When streaming out only the filled chunk is saved.
   // When reading back only the memory needed for that filled part gets
   // allocated. We need to check whether the allowed chunk size is
   // bigger than the allocated size. If fCoordinateAllocationSize is
   // set to -1 this chunk has been allocated by the  streamer and the
   // buffer allocation size is defined by [fCoordinatesSize]. In that
   // case we need to compare fCoordinatesSize to
   // fSingleCoordinateSize * fContent->GetSize()
   // to determine whether we need to expand the buffer.
   if (fCoordinateAllocationSize == -1 && fContent) {
      Int_t chunksize = fSingleCoordinateSize * fContent->GetSize();
      if (fCoordinatesSize < chunksize) {
         // need to re-allocate:
         Char_t *newcoord = new Char_t[chunksize];
         memcpy(newcoord, fCoordinates, fCoordinatesSize);
         delete [] fCoordinates;
         fCoordinates = newcoord;
      }
      fCoordinateAllocationSize = chunksize;
   }

   memcpy(fCoordinates + idx * fSingleCoordinateSize, coordbuf, fSingleCoordinateSize);
   fCoordinatesSize += fSingleCoordinateSize;
}

//______________________________________________________________________________
void THnSparseArrayChunk::Sumw2()
{
   // Turn on support of errors
   if (!fSumw2)
      fSumw2 = new TArrayD(fContent->GetSize());
}



//______________________________________________________________________________
//
//
//    Efficient multidimensional histogram.
//
// Use a THnSparse instead of TH1 / TH2 / TH3 / array for histogramming when
// only a small fraction of bins is filled. A 10-dimensional histogram with 10
// bins per dimension has 10^10 bins; in a naive implementation this will not
// fit in memory. THnSparse only allocates memory for the bins that have
// non-zero bin content instead, drastically reducing both the memory usage
// and the access time.
//
// To construct a THnSparse object you must use one of its templated, derived
// classes:
// THnSparseD (typedef for THnSparseT<ArrayD>): bin content held by a Double_t,
// THnSparseF (typedef for THnSparseT<ArrayF>): bin content held by a Float_t,
// THnSparseL (typedef for THnSparseT<ArrayL>): bin content held by a Long_t,
// THnSparseI (typedef for THnSparseT<ArrayI>): bin content held by an Int_t,
// THnSparseS (typedef for THnSparseT<ArrayS>): bin content held by a Short_t,
// THnSparseC (typedef for THnSparseT<ArrayC>): bin content held by a Char_t,
//
// They take name and title, the number of dimensions, and for each dimension
// the number of bins, the minimal, and the maximal value on the dimension's
// axis. A TH2 h("h","h",10, 0., 10., 20, -5., 5.) would correspond to
//   Int_t bins[2] = {10, 20};
//   Double_t xmin[2] = {0., -5.};
//   Double_t xmax[2] = {10., 5.};
//   THnSparse hs("hs", "hs", 2, bins, min, max);
//
// * Filling
// A THnSparse is filled just like a regular histogram, using
// THnSparse::Fill(x, weight), where x is a n-dimensional Double_t value.
// To take errors into account, Sumw2() must be called before filling the
// histogram.
// Bins are allocated as needed; the status of the allocation can be observed
// by GetSparseFractionBins(), GetSparseFractionMem().
//
// * Fast Bin Content Access
// When iterating over a THnSparse one should only look at filled bins to save
// processing time. The number of filled bins is returned by
// THnSparse::GetNbins(); the bin content for each (linear) bin number can
// be retrieved by THnSparse::GetBinContent(linidx, (Int_t*)coord).
// After the call, coord will contain the bin coordinate of each axis for the bin
// with linear index linidx. A possible call would be
//   cout << hs.GetBinContent(0, coord);
//   cout <<" is the content of bin [x = " << coord[0] "
//        << " | y = " << coord[1] << "]" << endl;
//
// * Efficiency
// TH1 and TH2 are generally faster than THnSparse for one and two dimensional
// distributions. THnSparse becomes competitive for a sparsely filled TH3
// with large numbers of bins per dimension. The tutorial hist/sparsehist.C
// shows the turning point. On a AMD64 with 8GB memory, THnSparse "wins"
// starting with a TH3 with 30 bins per dimension. Using a THnSparse for a
// one-dimensional histogram is only reasonable if it has a huge number of bins.
//
// * Projections
// The dimensionality of a THnSparse can be reduced by projecting it to
// 1, 2, 3, or n dimensions, which can be represented by a TH1, TH2, TH3, or
// a THnSparse. See the Projection() members. To only project parts of the
// histogram, call
//   THnSparse::GetAxis(12)->SetRange(from_bin, to_bin);
//
// * Internal Representation
// An entry for a filled bin consists of its n-dimensional coordinates and
// its bin content. The coordinates are compacted to use as few bits as
// possible; e.g. a histogram with 10 bins in x and 20 bins in y will only
// use 4 bits for the x representation and 5 bits for the y representation.
// This is handled by the internal class THnSparseCompactBinCoord.
// Bin data (content and coordinates) are allocated in chunks of size
// fChunkSize; this parameter can be set when constructing a THnSparse. Each
// chunk is represented by an object of class THnSparseArrayChunk.
//
// Translation from an n-dimensional bin coordinate to the linear index within
// the chunks is done by GetBin(). It creates a hash from the compacted bin
// coordinates (the hash of a bin coordinate is the compacted coordinate itself
// if it takes less than 8 bytes, the size of a Long64_t.
// This hash is used to lookup the linear index in the TExMap member fBins;
// the coordinates of the entry fBins points to is compared to the coordinates
// passed to GetBin(). If they do not match, these two coordinates have the same
// hash - which is extremely unlikely but (for the case where the compact bin
// coordinates are larger than 4 bytes) possible. In this case, fBinsContinued
// contains a chain of linear indexes with the same hash. Iterating through this
// chain and comparing each bin coordinates with the one passed to GetBin() will
// retrieve the matching bin.


ClassImp(THnSparse);

//______________________________________________________________________________
THnSparse::THnSparse():
   fChunkSize(1024), fFilledBins(0), fCompactCoord(0)
{
   // Construct an empty THnSparse.
   fBinContent.SetOwner();
}

//______________________________________________________________________________
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):
   THnBase(name, title, dim, nbins, xmin, xmax),
   fChunkSize(chunksize), fFilledBins(0), fCompactCoord(0)
{
   // Construct a THnSparse with "dim" dimensions,
   // with chunksize as the size of the chunks.
   // "nbins" holds the number of bins for each dimension;
   // "xmin" and "xmax" the minimal and maximal value for each dimension.
   // The arrays "xmin" and "xmax" can be NULL; in that case SetBinEdges()
   // must be called for each dimension.

   fCompactCoord = new THnSparseCompactBinCoord(dim, nbins);
   fBinContent.SetOwner();
}

//______________________________________________________________________________
THnSparse::~THnSparse() {
   // Destruct a THnSparse

   delete fCompactCoord;
}

//______________________________________________________________________________
void THnSparse::AddBinContent(Long64_t bin, Double_t v)
{
   // Add "v" to the content of bin with index "bin"

   THnSparseArrayChunk* chunk = GetChunk(bin / fChunkSize);
   bin %= fChunkSize;
   v += chunk->fContent->GetAt(bin);
   return chunk->fContent->SetAt(v, bin);
}

//______________________________________________________________________________
THnSparseArrayChunk* THnSparse::AddChunk()
{
   // Create a new chunk of bin content
   THnSparseArrayChunk* chunk =
      new THnSparseArrayChunk(GetCompactCoord()->GetBufferSize(),
                              GetCalculateErrors(), GenerateArray());
   fBinContent.AddLast(chunk);
   return chunk;
}

//______________________________________________________________________________
void THnSparse::InitStorage(Int_t* nbins, Int_t chunkSize)
{
   // Initialize the storage of a histogram created via Init()
   fChunkSize = chunkSize;
   fCompactCoord = new THnSparseCompactBinCoord(fNdimensions, nbins);
}

//______________________________________________________________________________
void THnSparse::FillExMap()
{
   //We have been streamed; set up fBins
   TIter iChunk(&fBinContent);
   THnSparseArrayChunk* chunk = 0;
   THnSparseCoordCompression compactCoord(*GetCompactCoord());
   Long64_t idx = 0;
   if (2 * GetNbins() > fBins.Capacity())
      fBins.Expand(3 * GetNbins());
   while ((chunk = (THnSparseArrayChunk*) iChunk())) {
      const Int_t chunkSize = chunk->GetEntries();
      Char_t* buf = chunk->fCoordinates;
      const Int_t singleCoordSize = chunk->fSingleCoordinateSize;
      const Char_t* endbuf = buf + singleCoordSize * chunkSize;
      for (; buf < endbuf; buf += singleCoordSize, ++idx) {
         Long64_t hash = compactCoord.GetHashFromBuffer(buf);
         Long64_t linidx = fBins.GetValue(hash);
         if (linidx) {
            Long64_t nextidx = linidx;
            while (nextidx) {
               // must be a collision, so go to fBinsContinued.
               linidx = nextidx;
               nextidx = fBinsContinued.GetValue(linidx);
            }
            fBinsContinued.Add(linidx, idx + 1);
         } else {
            fBins.Add(hash, idx + 1);
         }
      }
   }
}

//______________________________________________________________________________
void THnSparse::Reserve(Long64_t nbins) {
   // Initialize storage for nbins
   if (!fBins.GetSize() && fBinContent.GetSize()) {
      FillExMap();
   }
   if (2 * nbins > fBins.Capacity()) {
      fBins.Expand(3 * nbins);
   }
}

//______________________________________________________________________________
Long64_t THnSparse::GetBin(const Double_t* x, Bool_t allocate /* = kTRUE */)
{
   // Get the bin index for the n dimensional tuple x,
   // allocate one if it doesn't exist yet and "allocate" is true.

   THnSparseCompactBinCoord* cc = GetCompactCoord();
   Int_t *coord = cc->GetCoord();
   for (Int_t i = 0; i < fNdimensions; ++i)
      coord[i] = GetAxis(i)->FindBin(x[i]);
   cc->UpdateCoord();

   return GetBinIndexForCurrentBin(allocate);
}


//______________________________________________________________________________
Long64_t THnSparse::GetBin(const char* name[], Bool_t allocate /* = kTRUE */)
{
   // Get the bin index for the n dimensional tuple addressed by "name",
   // allocate one if it doesn't exist yet and "allocate" is true.

   THnSparseCompactBinCoord* cc = GetCompactCoord();
   Int_t *coord = cc->GetCoord();
   for (Int_t i = 0; i < fNdimensions; ++i)
      coord[i] = GetAxis(i)->FindBin(name[i]);
   cc->UpdateCoord();

   return GetBinIndexForCurrentBin(allocate);
}

//______________________________________________________________________________
Long64_t THnSparse::GetBin(const Int_t* coord, Bool_t allocate /*= kTRUE*/)
{
   // Get the bin index for the n dimensional coordinates coord,
   // allocate one if it doesn't exist yet and "allocate" is true.
   GetCompactCoord()->SetCoord(coord);
   return GetBinIndexForCurrentBin(allocate);
}

//______________________________________________________________________________
Double_t THnSparse::GetBinContent(Long64_t idx, Int_t* coord /* = 0 */) const
{
   // Return the content of the filled bin number "idx".
   // If coord is non-null, it will contain the bin's coordinates for each axis
   // that correspond to the bin.

   if (idx >= 0) {
      THnSparseArrayChunk* chunk = GetChunk(idx / fChunkSize);
      idx %= fChunkSize;
      if (chunk && chunk->fContent->GetSize() > idx) {
         if (coord) {
            THnSparseCompactBinCoord* cc = GetCompactCoord();
            Int_t sizeCompact = cc->GetBufferSize();
            cc->SetCoordFromBuffer(chunk->fCoordinates + idx * sizeCompact,
                                                  coord);
                                                                               
         }
         return chunk->fContent->GetAt(idx);
      }
   }
   if (coord)
      memset(coord, -1, sizeof(Int_t) * fNdimensions);
   return 0.;
}

//______________________________________________________________________________
Double_t THnSparse::GetBinError2(Long64_t linidx) const {
   // Get square of the error of bin addressed by linidx as
   // BEGIN_LATEX #sum weight^{2}
   // END_LATEX
   // If errors are not enabled (via Sumw2() or CalculateErrors())
   // return contents.

   if (!GetCalculateErrors())
      return GetBinContent(linidx);

   if (linidx < 0) return 0.;
   THnSparseArrayChunk* chunk = GetChunk(linidx / fChunkSize);
   linidx %= fChunkSize;
   if (!chunk || chunk->fContent->GetSize() < linidx)
      return 0.;

   return chunk->fSumw2->GetAt(linidx);
}


//______________________________________________________________________________
Long64_t THnSparse::GetBinIndexForCurrentBin(Bool_t allocate)
{
   // Return the index for fCurrentBinIndex.
   // If it doesn't exist then return -1, or allocate a new bin if allocate is set

   THnSparseCompactBinCoord* cc = GetCompactCoord();
   ULong64_t hash = cc->GetHash();
   if (fBinContent.GetSize() && !fBins.GetSize())
      FillExMap();
   Long64_t linidx = (Long64_t) fBins.GetValue(hash);
   while (linidx) {
      // fBins stores index + 1!
      THnSparseArrayChunk* chunk = GetChunk((linidx - 1)/ fChunkSize);
      if (chunk->Matches((linidx - 1) % fChunkSize, cc->GetBuffer()))
         return linidx - 1; // we store idx+1, 0 is "TExMap: not found"

      Long64_t nextlinidx = fBinsContinued.GetValue(linidx);
      if (!nextlinidx) break;

      linidx = nextlinidx;
   }
   if (!allocate) return -1;

   ++fFilledBins;

   // allocate bin in chunk
   THnSparseArrayChunk *chunk = (THnSparseArrayChunk*) fBinContent.Last();
   Long64_t newidx = chunk ? ((Long64_t) chunk->GetEntries()) : -1;
   if (!chunk || newidx == (Long64_t)fChunkSize) {
      chunk = AddChunk();
      newidx = 0;
   }
   chunk->AddBin(newidx, cc->GetBuffer());

   // store translation between hash and bin
   newidx += (fBinContent.GetEntriesFast() - 1) * fChunkSize;
   if (!linidx) {
      // fBins didn't find it
      if (2 * GetNbins() > fBins.Capacity())
         fBins.Expand(3 * GetNbins());
      fBins.Add(hash, newidx + 1);
   } else {
      // fBins contains one, but it's the wrong one;
      // add entry to fBinsContinued.
      fBinsContinued.Add(linidx, newidx + 1);
   }
   return newidx;
}

//______________________________________________________________________________
THnSparseCompactBinCoord* THnSparse::GetCompactCoord() const
{
   // Return THnSparseCompactBinCoord object.

   if (!fCompactCoord) {
      Int_t *bins = new Int_t[fNdimensions];
      for (Int_t d = 0; d < fNdimensions; ++d)
         bins[d] = GetAxis(d)->GetNbins();
      const_cast<THnSparse*>(this)->fCompactCoord
         = new THnSparseCompactBinCoord(fNdimensions, bins);
      delete [] bins;
   }
   return fCompactCoord;
}

//______________________________________________________________________________
Double_t THnSparse::GetSparseFractionBins() const {
   // Return the amount of filled bins over all bins

   Double_t nbinsTotal = 1.;
   for (Int_t d = 0; d < fNdimensions; ++d)
      nbinsTotal *= GetAxis(d)->GetNbins() + 2;
   return fFilledBins / nbinsTotal;
}

//______________________________________________________________________________
Double_t THnSparse::GetSparseFractionMem() const {
   // Return the amount of used memory over memory that would be used by a
   // non-sparse n-dimensional histogram. The value is approximate.

   Int_t arrayElementSize = 0;
   if (fFilledBins) {
      TClass* clArray = GetChunk(0)->fContent->IsA();
      TDataMember* dm = clArray ? clArray->GetDataMember("fArray") : 0;
      arrayElementSize = dm ? dm->GetDataType()->Size() : 0;
   }
   if (!arrayElementSize) {
      Warning("GetSparseFractionMem", "Cannot determine type of elements!");
      return -1.;
   }

   Double_t sizePerChunkElement = arrayElementSize + GetCompactCoord()->GetBufferSize();
   if (fFilledBins && GetChunk(0)->fSumw2)
      sizePerChunkElement += sizeof(Double_t); /* fSumw2 */

   Double_t size = 0.;
   size += fBinContent.GetEntries() * (GetChunkSize() * sizePerChunkElement + sizeof(THnSparseArrayChunk));
   size += + 3 * sizeof(Long64_t) * fBins.GetSize() /* TExMap */;

   Double_t nbinsTotal = 1.;
   for (Int_t d = 0; d < fNdimensions; ++d)
      nbinsTotal *= GetAxis(d)->GetNbins() + 2;

   return size / nbinsTotal / arrayElementSize;
}

//______________________________________________________________________________
ROOT::THnBaseBinIter* THnSparse::CreateIter(Bool_t respectAxisRange) const
{
   // Create an iterator over all filled bins of a THnSparse.
   // Use THnIter instead.
   return new THnSparseBinIter(respectAxisRange, this);
}

//______________________________________________________________________________
void THnSparse::SetBinContent(Long64_t bin, Double_t v)
{
   // Set content of bin with index "bin" to "v"

   THnSparseArrayChunk* chunk = GetChunk(bin / fChunkSize);
   chunk->fContent->SetAt(v, bin % fChunkSize);
   ++fEntries;
}

//______________________________________________________________________________
void THnSparse::SetBinError2(Long64_t bin, Double_t e2)
{
   // Set error of bin with index "bin" to "e", enable errors if needed

   THnSparseArrayChunk* chunk = GetChunk(bin / fChunkSize);
   if (!chunk->fSumw2 ) {
      // if fSumw2 is zero GetCalculateErrors should return false
      if (GetCalculateErrors()) {
         Error("SetBinError", "GetCalculateErrors() logic error!");
      }
      Sumw2(); // enable error calculation
   }

   chunk->fSumw2->SetAt(e2, bin % fChunkSize);
}

//______________________________________________________________________________
void THnSparse::AddBinError2(Long64_t bin, Double_t e2)
{
   // Add "e" to error of bin with index "bin", enable errors if needed

   THnSparseArrayChunk* chunk = GetChunk(bin / fChunkSize);
   if (!chunk->fSumw2 ) {
      // if fSumw2 is zero GetCalculateErrors should return false
      if (GetCalculateErrors()) {
         Error("SetBinError", "GetCalculateErrors() logic error!");
      }
      Sumw2(); // enable error calculation
   }

   (*chunk->fSumw2)[bin % fChunkSize] += e2;
}

//______________________________________________________________________________
void THnSparse::Sumw2()
{
   // Enable calculation of errors

   if (GetCalculateErrors()) return;

   fTsumw2 = 0.;
   TIter iChunk(&fBinContent);
   THnSparseArrayChunk* chunk = 0;
   while ((chunk = (THnSparseArrayChunk*) iChunk()))
      chunk->Sumw2();
}

//______________________________________________________________________________
void THnSparse::Reset(Option_t *option /*= ""*/)
{
   // Clear the histogram
   fFilledBins = 0;
   fBins.Delete();
   fBinsContinued.Clear();
   fBinContent.Delete();
   ResetBase(option);
}

 THnSparse.cxx:1
 THnSparse.cxx:2
 THnSparse.cxx:3
 THnSparse.cxx:4
 THnSparse.cxx:5
 THnSparse.cxx:6
 THnSparse.cxx:7
 THnSparse.cxx:8
 THnSparse.cxx:9
 THnSparse.cxx:10
 THnSparse.cxx:11
 THnSparse.cxx:12
 THnSparse.cxx:13
 THnSparse.cxx:14
 THnSparse.cxx:15
 THnSparse.cxx:16
 THnSparse.cxx:17
 THnSparse.cxx:18
 THnSparse.cxx:19
 THnSparse.cxx:20
 THnSparse.cxx:21
 THnSparse.cxx:22
 THnSparse.cxx:23
 THnSparse.cxx:24
 THnSparse.cxx:25
 THnSparse.cxx:26
 THnSparse.cxx:27
 THnSparse.cxx:28
 THnSparse.cxx:29
 THnSparse.cxx:30
 THnSparse.cxx:31
 THnSparse.cxx:32
 THnSparse.cxx:33
 THnSparse.cxx:34
 THnSparse.cxx:35
 THnSparse.cxx:36
 THnSparse.cxx:37
 THnSparse.cxx:38
 THnSparse.cxx:39
 THnSparse.cxx:40
 THnSparse.cxx:41
 THnSparse.cxx:42
 THnSparse.cxx:43
 THnSparse.cxx:44
 THnSparse.cxx:45
 THnSparse.cxx:46
 THnSparse.cxx:47
 THnSparse.cxx:48
 THnSparse.cxx:49
 THnSparse.cxx:50
 THnSparse.cxx:51
 THnSparse.cxx:52
 THnSparse.cxx:53
 THnSparse.cxx:54
 THnSparse.cxx:55
 THnSparse.cxx:56
 THnSparse.cxx:57
 THnSparse.cxx:58
 THnSparse.cxx:59
 THnSparse.cxx:60
 THnSparse.cxx:61
 THnSparse.cxx:62
 THnSparse.cxx:63
 THnSparse.cxx:64
 THnSparse.cxx:65
 THnSparse.cxx:66
 THnSparse.cxx:67
 THnSparse.cxx:68
 THnSparse.cxx:69
 THnSparse.cxx:70
 THnSparse.cxx:71
 THnSparse.cxx:72
 THnSparse.cxx:73
 THnSparse.cxx:74
 THnSparse.cxx:75
 THnSparse.cxx:76
 THnSparse.cxx:77
 THnSparse.cxx:78
 THnSparse.cxx:79
 THnSparse.cxx:80
 THnSparse.cxx:81
 THnSparse.cxx:82
 THnSparse.cxx:83
 THnSparse.cxx:84
 THnSparse.cxx:85
 THnSparse.cxx:86
 THnSparse.cxx:87
 THnSparse.cxx:88
 THnSparse.cxx:89
 THnSparse.cxx:90
 THnSparse.cxx:91
 THnSparse.cxx:92
 THnSparse.cxx:93
 THnSparse.cxx:94
 THnSparse.cxx:95
 THnSparse.cxx:96
 THnSparse.cxx:97
 THnSparse.cxx:98
 THnSparse.cxx:99
 THnSparse.cxx:100
 THnSparse.cxx:101
 THnSparse.cxx:102
 THnSparse.cxx:103
 THnSparse.cxx:104
 THnSparse.cxx:105
 THnSparse.cxx:106
 THnSparse.cxx:107
 THnSparse.cxx:108
 THnSparse.cxx:109
 THnSparse.cxx:110
 THnSparse.cxx:111
 THnSparse.cxx:112
 THnSparse.cxx:113
 THnSparse.cxx:114
 THnSparse.cxx:115
 THnSparse.cxx:116
 THnSparse.cxx:117
 THnSparse.cxx:118
 THnSparse.cxx:119
 THnSparse.cxx:120
 THnSparse.cxx:121
 THnSparse.cxx:122
 THnSparse.cxx:123
 THnSparse.cxx:124
 THnSparse.cxx:125
 THnSparse.cxx:126
 THnSparse.cxx:127
 THnSparse.cxx:128
 THnSparse.cxx:129
 THnSparse.cxx:130
 THnSparse.cxx:131
 THnSparse.cxx:132
 THnSparse.cxx:133
 THnSparse.cxx:134
 THnSparse.cxx:135
 THnSparse.cxx:136
 THnSparse.cxx:137
 THnSparse.cxx:138
 THnSparse.cxx:139
 THnSparse.cxx:140
 THnSparse.cxx:141
 THnSparse.cxx:142
 THnSparse.cxx:143
 THnSparse.cxx:144
 THnSparse.cxx:145
 THnSparse.cxx:146
 THnSparse.cxx:147
 THnSparse.cxx:148
 THnSparse.cxx:149
 THnSparse.cxx:150
 THnSparse.cxx:151
 THnSparse.cxx:152
 THnSparse.cxx:153
 THnSparse.cxx:154
 THnSparse.cxx:155
 THnSparse.cxx:156
 THnSparse.cxx:157
 THnSparse.cxx:158
 THnSparse.cxx:159
 THnSparse.cxx:160
 THnSparse.cxx:161
 THnSparse.cxx:162
 THnSparse.cxx:163
 THnSparse.cxx:164
 THnSparse.cxx:165
 THnSparse.cxx:166
 THnSparse.cxx:167
 THnSparse.cxx:168
 THnSparse.cxx:169
 THnSparse.cxx:170
 THnSparse.cxx:171
 THnSparse.cxx:172
 THnSparse.cxx:173
 THnSparse.cxx:174
 THnSparse.cxx:175
 THnSparse.cxx:176
 THnSparse.cxx:177
 THnSparse.cxx:178
 THnSparse.cxx:179
 THnSparse.cxx:180
 THnSparse.cxx:181
 THnSparse.cxx:182
 THnSparse.cxx:183
 THnSparse.cxx:184
 THnSparse.cxx:185
 THnSparse.cxx:186
 THnSparse.cxx:187
 THnSparse.cxx:188
 THnSparse.cxx:189
 THnSparse.cxx:190
 THnSparse.cxx:191
 THnSparse.cxx:192
 THnSparse.cxx:193
 THnSparse.cxx:194
 THnSparse.cxx:195
 THnSparse.cxx:196
 THnSparse.cxx:197
 THnSparse.cxx:198
 THnSparse.cxx:199
 THnSparse.cxx:200
 THnSparse.cxx:201
 THnSparse.cxx:202
 THnSparse.cxx:203
 THnSparse.cxx:204
 THnSparse.cxx:205
 THnSparse.cxx:206
 THnSparse.cxx:207
 THnSparse.cxx:208
 THnSparse.cxx:209
 THnSparse.cxx:210
 THnSparse.cxx:211
 THnSparse.cxx:212
 THnSparse.cxx:213
 THnSparse.cxx:214
 THnSparse.cxx:215
 THnSparse.cxx:216
 THnSparse.cxx:217
 THnSparse.cxx:218
 THnSparse.cxx:219
 THnSparse.cxx:220
 THnSparse.cxx:221
 THnSparse.cxx:222
 THnSparse.cxx:223
 THnSparse.cxx:224
 THnSparse.cxx:225
 THnSparse.cxx:226
 THnSparse.cxx:227
 THnSparse.cxx:228
 THnSparse.cxx:229
 THnSparse.cxx:230
 THnSparse.cxx:231
 THnSparse.cxx:232
 THnSparse.cxx:233
 THnSparse.cxx:234
 THnSparse.cxx:235
 THnSparse.cxx:236
 THnSparse.cxx:237
 THnSparse.cxx:238
 THnSparse.cxx:239
 THnSparse.cxx:240
 THnSparse.cxx:241
 THnSparse.cxx:242
 THnSparse.cxx:243
 THnSparse.cxx:244
 THnSparse.cxx:245
 THnSparse.cxx:246
 THnSparse.cxx:247
 THnSparse.cxx:248
 THnSparse.cxx:249
 THnSparse.cxx:250
 THnSparse.cxx:251
 THnSparse.cxx:252
 THnSparse.cxx:253
 THnSparse.cxx:254
 THnSparse.cxx:255
 THnSparse.cxx:256
 THnSparse.cxx:257
 THnSparse.cxx:258
 THnSparse.cxx:259
 THnSparse.cxx:260
 THnSparse.cxx:261
 THnSparse.cxx:262
 THnSparse.cxx:263
 THnSparse.cxx:264
 THnSparse.cxx:265
 THnSparse.cxx:266
 THnSparse.cxx:267
 THnSparse.cxx:268
 THnSparse.cxx:269
 THnSparse.cxx:270
 THnSparse.cxx:271
 THnSparse.cxx:272
 THnSparse.cxx:273
 THnSparse.cxx:274
 THnSparse.cxx:275
 THnSparse.cxx:276
 THnSparse.cxx:277
 THnSparse.cxx:278
 THnSparse.cxx:279
 THnSparse.cxx:280
 THnSparse.cxx:281
 THnSparse.cxx:282
 THnSparse.cxx:283
 THnSparse.cxx:284
 THnSparse.cxx:285
 THnSparse.cxx:286
 THnSparse.cxx:287
 THnSparse.cxx:288
 THnSparse.cxx:289
 THnSparse.cxx:290
 THnSparse.cxx:291
 THnSparse.cxx:292
 THnSparse.cxx:293
 THnSparse.cxx:294
 THnSparse.cxx:295
 THnSparse.cxx:296
 THnSparse.cxx:297
 THnSparse.cxx:298
 THnSparse.cxx:299
 THnSparse.cxx:300
 THnSparse.cxx:301
 THnSparse.cxx:302
 THnSparse.cxx:303
 THnSparse.cxx:304
 THnSparse.cxx:305
 THnSparse.cxx:306
 THnSparse.cxx:307
 THnSparse.cxx:308
 THnSparse.cxx:309
 THnSparse.cxx:310
 THnSparse.cxx:311
 THnSparse.cxx:312
 THnSparse.cxx:313
 THnSparse.cxx:314
 THnSparse.cxx:315
 THnSparse.cxx:316
 THnSparse.cxx:317
 THnSparse.cxx:318
 THnSparse.cxx:319
 THnSparse.cxx:320
 THnSparse.cxx:321
 THnSparse.cxx:322
 THnSparse.cxx:323
 THnSparse.cxx:324
 THnSparse.cxx:325
 THnSparse.cxx:326
 THnSparse.cxx:327
 THnSparse.cxx:328
 THnSparse.cxx:329
 THnSparse.cxx:330
 THnSparse.cxx:331
 THnSparse.cxx:332
 THnSparse.cxx:333
 THnSparse.cxx:334
 THnSparse.cxx:335
 THnSparse.cxx:336
 THnSparse.cxx:337
 THnSparse.cxx:338
 THnSparse.cxx:339
 THnSparse.cxx:340
 THnSparse.cxx:341
 THnSparse.cxx:342
 THnSparse.cxx:343
 THnSparse.cxx:344
 THnSparse.cxx:345
 THnSparse.cxx:346
 THnSparse.cxx:347
 THnSparse.cxx:348
 THnSparse.cxx:349
 THnSparse.cxx:350
 THnSparse.cxx:351
 THnSparse.cxx:352
 THnSparse.cxx:353
 THnSparse.cxx:354
 THnSparse.cxx:355
 THnSparse.cxx:356
 THnSparse.cxx:357
 THnSparse.cxx:358
 THnSparse.cxx:359
 THnSparse.cxx:360
 THnSparse.cxx:361
 THnSparse.cxx:362
 THnSparse.cxx:363
 THnSparse.cxx:364
 THnSparse.cxx:365
 THnSparse.cxx:366
 THnSparse.cxx:367
 THnSparse.cxx:368
 THnSparse.cxx:369
 THnSparse.cxx:370
 THnSparse.cxx:371
 THnSparse.cxx:372
 THnSparse.cxx:373
 THnSparse.cxx:374
 THnSparse.cxx:375
 THnSparse.cxx:376
 THnSparse.cxx:377
 THnSparse.cxx:378
 THnSparse.cxx:379
 THnSparse.cxx:380
 THnSparse.cxx:381
 THnSparse.cxx:382
 THnSparse.cxx:383
 THnSparse.cxx:384
 THnSparse.cxx:385
 THnSparse.cxx:386
 THnSparse.cxx:387
 THnSparse.cxx:388
 THnSparse.cxx:389
 THnSparse.cxx:390
 THnSparse.cxx:391
 THnSparse.cxx:392
 THnSparse.cxx:393
 THnSparse.cxx:394
 THnSparse.cxx:395
 THnSparse.cxx:396
 THnSparse.cxx:397
 THnSparse.cxx:398
 THnSparse.cxx:399
 THnSparse.cxx:400
 THnSparse.cxx:401
 THnSparse.cxx:402
 THnSparse.cxx:403
 THnSparse.cxx:404
 THnSparse.cxx:405
 THnSparse.cxx:406
 THnSparse.cxx:407
 THnSparse.cxx:408
 THnSparse.cxx:409
 THnSparse.cxx:410
 THnSparse.cxx:411
 THnSparse.cxx:412
 THnSparse.cxx:413
 THnSparse.cxx:414
 THnSparse.cxx:415
 THnSparse.cxx:416
 THnSparse.cxx:417
 THnSparse.cxx:418
 THnSparse.cxx:419
 THnSparse.cxx:420
 THnSparse.cxx:421
 THnSparse.cxx:422
 THnSparse.cxx:423
 THnSparse.cxx:424
 THnSparse.cxx:425
 THnSparse.cxx:426
 THnSparse.cxx:427
 THnSparse.cxx:428
 THnSparse.cxx:429
 THnSparse.cxx:430
 THnSparse.cxx:431
 THnSparse.cxx:432
 THnSparse.cxx:433
 THnSparse.cxx:434
 THnSparse.cxx:435
 THnSparse.cxx:436
 THnSparse.cxx:437
 THnSparse.cxx:438
 THnSparse.cxx:439
 THnSparse.cxx:440
 THnSparse.cxx:441
 THnSparse.cxx:442
 THnSparse.cxx:443
 THnSparse.cxx:444
 THnSparse.cxx:445
 THnSparse.cxx:446
 THnSparse.cxx:447
 THnSparse.cxx:448
 THnSparse.cxx:449
 THnSparse.cxx:450
 THnSparse.cxx:451
 THnSparse.cxx:452
 THnSparse.cxx:453
 THnSparse.cxx:454
 THnSparse.cxx:455
 THnSparse.cxx:456
 THnSparse.cxx:457
 THnSparse.cxx:458
 THnSparse.cxx:459
 THnSparse.cxx:460
 THnSparse.cxx:461
 THnSparse.cxx:462
 THnSparse.cxx:463
 THnSparse.cxx:464
 THnSparse.cxx:465
 THnSparse.cxx:466
 THnSparse.cxx:467
 THnSparse.cxx:468
 THnSparse.cxx:469
 THnSparse.cxx:470
 THnSparse.cxx:471
 THnSparse.cxx:472
 THnSparse.cxx:473
 THnSparse.cxx:474
 THnSparse.cxx:475
 THnSparse.cxx:476
 THnSparse.cxx:477
 THnSparse.cxx:478
 THnSparse.cxx:479
 THnSparse.cxx:480
 THnSparse.cxx:481
 THnSparse.cxx:482
 THnSparse.cxx:483
 THnSparse.cxx:484
 THnSparse.cxx:485
 THnSparse.cxx:486
 THnSparse.cxx:487
 THnSparse.cxx:488
 THnSparse.cxx:489
 THnSparse.cxx:490
 THnSparse.cxx:491
 THnSparse.cxx:492
 THnSparse.cxx:493
 THnSparse.cxx:494
 THnSparse.cxx:495
 THnSparse.cxx:496
 THnSparse.cxx:497
 THnSparse.cxx:498
 THnSparse.cxx:499
 THnSparse.cxx:500
 THnSparse.cxx:501
 THnSparse.cxx:502
 THnSparse.cxx:503
 THnSparse.cxx:504
 THnSparse.cxx:505
 THnSparse.cxx:506
 THnSparse.cxx:507
 THnSparse.cxx:508
 THnSparse.cxx:509
 THnSparse.cxx:510
 THnSparse.cxx:511
 THnSparse.cxx:512
 THnSparse.cxx:513
 THnSparse.cxx:514
 THnSparse.cxx:515
 THnSparse.cxx:516
 THnSparse.cxx:517
 THnSparse.cxx:518
 THnSparse.cxx:519
 THnSparse.cxx:520
 THnSparse.cxx:521
 THnSparse.cxx:522
 THnSparse.cxx:523
 THnSparse.cxx:524
 THnSparse.cxx:525
 THnSparse.cxx:526
 THnSparse.cxx:527
 THnSparse.cxx:528
 THnSparse.cxx:529
 THnSparse.cxx:530
 THnSparse.cxx:531
 THnSparse.cxx:532
 THnSparse.cxx:533
 THnSparse.cxx:534
 THnSparse.cxx:535
 THnSparse.cxx:536
 THnSparse.cxx:537
 THnSparse.cxx:538
 THnSparse.cxx:539
 THnSparse.cxx:540
 THnSparse.cxx:541
 THnSparse.cxx:542
 THnSparse.cxx:543
 THnSparse.cxx:544
 THnSparse.cxx:545
 THnSparse.cxx:546
 THnSparse.cxx:547
 THnSparse.cxx:548
 THnSparse.cxx:549
 THnSparse.cxx:550
 THnSparse.cxx:551
 THnSparse.cxx:552
 THnSparse.cxx:553
 THnSparse.cxx:554
 THnSparse.cxx:555
 THnSparse.cxx:556
 THnSparse.cxx:557
 THnSparse.cxx:558
 THnSparse.cxx:559
 THnSparse.cxx:560
 THnSparse.cxx:561
 THnSparse.cxx:562
 THnSparse.cxx:563
 THnSparse.cxx:564
 THnSparse.cxx:565
 THnSparse.cxx:566
 THnSparse.cxx:567
 THnSparse.cxx:568
 THnSparse.cxx:569
 THnSparse.cxx:570
 THnSparse.cxx:571
 THnSparse.cxx:572
 THnSparse.cxx:573
 THnSparse.cxx:574
 THnSparse.cxx:575
 THnSparse.cxx:576
 THnSparse.cxx:577
 THnSparse.cxx:578
 THnSparse.cxx:579
 THnSparse.cxx:580
 THnSparse.cxx:581
 THnSparse.cxx:582
 THnSparse.cxx:583
 THnSparse.cxx:584
 THnSparse.cxx:585
 THnSparse.cxx:586
 THnSparse.cxx:587
 THnSparse.cxx:588
 THnSparse.cxx:589
 THnSparse.cxx:590
 THnSparse.cxx:591
 THnSparse.cxx:592
 THnSparse.cxx:593
 THnSparse.cxx:594
 THnSparse.cxx:595
 THnSparse.cxx:596
 THnSparse.cxx:597
 THnSparse.cxx:598
 THnSparse.cxx:599
 THnSparse.cxx:600
 THnSparse.cxx:601
 THnSparse.cxx:602
 THnSparse.cxx:603
 THnSparse.cxx:604
 THnSparse.cxx:605
 THnSparse.cxx:606
 THnSparse.cxx:607
 THnSparse.cxx:608
 THnSparse.cxx:609
 THnSparse.cxx:610
 THnSparse.cxx:611
 THnSparse.cxx:612
 THnSparse.cxx:613
 THnSparse.cxx:614
 THnSparse.cxx:615
 THnSparse.cxx:616
 THnSparse.cxx:617
 THnSparse.cxx:618
 THnSparse.cxx:619
 THnSparse.cxx:620
 THnSparse.cxx:621
 THnSparse.cxx:622
 THnSparse.cxx:623
 THnSparse.cxx:624
 THnSparse.cxx:625
 THnSparse.cxx:626
 THnSparse.cxx:627
 THnSparse.cxx:628
 THnSparse.cxx:629
 THnSparse.cxx:630
 THnSparse.cxx:631
 THnSparse.cxx:632
 THnSparse.cxx:633
 THnSparse.cxx:634
 THnSparse.cxx:635
 THnSparse.cxx:636
 THnSparse.cxx:637
 THnSparse.cxx:638
 THnSparse.cxx:639
 THnSparse.cxx:640
 THnSparse.cxx:641
 THnSparse.cxx:642
 THnSparse.cxx:643
 THnSparse.cxx:644
 THnSparse.cxx:645
 THnSparse.cxx:646
 THnSparse.cxx:647
 THnSparse.cxx:648
 THnSparse.cxx:649
 THnSparse.cxx:650
 THnSparse.cxx:651
 THnSparse.cxx:652
 THnSparse.cxx:653
 THnSparse.cxx:654
 THnSparse.cxx:655
 THnSparse.cxx:656
 THnSparse.cxx:657
 THnSparse.cxx:658
 THnSparse.cxx:659
 THnSparse.cxx:660
 THnSparse.cxx:661
 THnSparse.cxx:662
 THnSparse.cxx:663
 THnSparse.cxx:664
 THnSparse.cxx:665
 THnSparse.cxx:666
 THnSparse.cxx:667
 THnSparse.cxx:668
 THnSparse.cxx:669
 THnSparse.cxx:670
 THnSparse.cxx:671
 THnSparse.cxx:672
 THnSparse.cxx:673
 THnSparse.cxx:674
 THnSparse.cxx:675
 THnSparse.cxx:676
 THnSparse.cxx:677
 THnSparse.cxx:678
 THnSparse.cxx:679
 THnSparse.cxx:680
 THnSparse.cxx:681
 THnSparse.cxx:682
 THnSparse.cxx:683
 THnSparse.cxx:684
 THnSparse.cxx:685
 THnSparse.cxx:686
 THnSparse.cxx:687
 THnSparse.cxx:688
 THnSparse.cxx:689
 THnSparse.cxx:690
 THnSparse.cxx:691
 THnSparse.cxx:692
 THnSparse.cxx:693
 THnSparse.cxx:694
 THnSparse.cxx:695
 THnSparse.cxx:696
 THnSparse.cxx:697
 THnSparse.cxx:698
 THnSparse.cxx:699
 THnSparse.cxx:700
 THnSparse.cxx:701
 THnSparse.cxx:702
 THnSparse.cxx:703
 THnSparse.cxx:704
 THnSparse.cxx:705
 THnSparse.cxx:706
 THnSparse.cxx:707
 THnSparse.cxx:708
 THnSparse.cxx:709
 THnSparse.cxx:710
 THnSparse.cxx:711
 THnSparse.cxx:712
 THnSparse.cxx:713
 THnSparse.cxx:714
 THnSparse.cxx:715
 THnSparse.cxx:716
 THnSparse.cxx:717
 THnSparse.cxx:718
 THnSparse.cxx:719
 THnSparse.cxx:720
 THnSparse.cxx:721
 THnSparse.cxx:722
 THnSparse.cxx:723
 THnSparse.cxx:724
 THnSparse.cxx:725
 THnSparse.cxx:726
 THnSparse.cxx:727
 THnSparse.cxx:728
 THnSparse.cxx:729
 THnSparse.cxx:730
 THnSparse.cxx:731
 THnSparse.cxx:732
 THnSparse.cxx:733
 THnSparse.cxx:734
 THnSparse.cxx:735
 THnSparse.cxx:736
 THnSparse.cxx:737
 THnSparse.cxx:738
 THnSparse.cxx:739
 THnSparse.cxx:740
 THnSparse.cxx:741
 THnSparse.cxx:742
 THnSparse.cxx:743
 THnSparse.cxx:744
 THnSparse.cxx:745
 THnSparse.cxx:746
 THnSparse.cxx:747
 THnSparse.cxx:748
 THnSparse.cxx:749
 THnSparse.cxx:750
 THnSparse.cxx:751
 THnSparse.cxx:752
 THnSparse.cxx:753
 THnSparse.cxx:754
 THnSparse.cxx:755
 THnSparse.cxx:756
 THnSparse.cxx:757
 THnSparse.cxx:758
 THnSparse.cxx:759
 THnSparse.cxx:760
 THnSparse.cxx:761
 THnSparse.cxx:762
 THnSparse.cxx:763
 THnSparse.cxx:764
 THnSparse.cxx:765
 THnSparse.cxx:766
 THnSparse.cxx:767
 THnSparse.cxx:768
 THnSparse.cxx:769
 THnSparse.cxx:770
 THnSparse.cxx:771
 THnSparse.cxx:772
 THnSparse.cxx:773
 THnSparse.cxx:774
 THnSparse.cxx:775
 THnSparse.cxx:776
 THnSparse.cxx:777
 THnSparse.cxx:778
 THnSparse.cxx:779
 THnSparse.cxx:780
 THnSparse.cxx:781
 THnSparse.cxx:782
 THnSparse.cxx:783
 THnSparse.cxx:784
 THnSparse.cxx:785
 THnSparse.cxx:786
 THnSparse.cxx:787
 THnSparse.cxx:788
 THnSparse.cxx:789
 THnSparse.cxx:790
 THnSparse.cxx:791
 THnSparse.cxx:792
 THnSparse.cxx:793
 THnSparse.cxx:794
 THnSparse.cxx:795
 THnSparse.cxx:796
 THnSparse.cxx:797
 THnSparse.cxx:798
 THnSparse.cxx:799
 THnSparse.cxx:800
 THnSparse.cxx:801
 THnSparse.cxx:802
 THnSparse.cxx:803
 THnSparse.cxx:804
 THnSparse.cxx:805
 THnSparse.cxx:806
 THnSparse.cxx:807
 THnSparse.cxx:808
 THnSparse.cxx:809
 THnSparse.cxx:810
 THnSparse.cxx:811
 THnSparse.cxx:812
 THnSparse.cxx:813
 THnSparse.cxx:814
 THnSparse.cxx:815
 THnSparse.cxx:816
 THnSparse.cxx:817
 THnSparse.cxx:818
 THnSparse.cxx:819
 THnSparse.cxx:820
 THnSparse.cxx:821
 THnSparse.cxx:822
 THnSparse.cxx:823
 THnSparse.cxx:824
 THnSparse.cxx:825
 THnSparse.cxx:826
 THnSparse.cxx:827
 THnSparse.cxx:828
 THnSparse.cxx:829
 THnSparse.cxx:830
 THnSparse.cxx:831
 THnSparse.cxx:832
 THnSparse.cxx:833
 THnSparse.cxx:834
 THnSparse.cxx:835
 THnSparse.cxx:836
 THnSparse.cxx:837
 THnSparse.cxx:838
 THnSparse.cxx:839
 THnSparse.cxx:840
 THnSparse.cxx:841
 THnSparse.cxx:842
 THnSparse.cxx:843
 THnSparse.cxx:844
 THnSparse.cxx:845
 THnSparse.cxx:846
 THnSparse.cxx:847
 THnSparse.cxx:848
 THnSparse.cxx:849
 THnSparse.cxx:850
 THnSparse.cxx:851
 THnSparse.cxx:852
 THnSparse.cxx:853
 THnSparse.cxx:854
 THnSparse.cxx:855
 THnSparse.cxx:856
 THnSparse.cxx:857
 THnSparse.cxx:858
 THnSparse.cxx:859
 THnSparse.cxx:860
 THnSparse.cxx:861
 THnSparse.cxx:862
 THnSparse.cxx:863
 THnSparse.cxx:864
 THnSparse.cxx:865
 THnSparse.cxx:866
 THnSparse.cxx:867
 THnSparse.cxx:868
 THnSparse.cxx:869
 THnSparse.cxx:870
 THnSparse.cxx:871
 THnSparse.cxx:872
 THnSparse.cxx:873
 THnSparse.cxx:874
 THnSparse.cxx:875
 THnSparse.cxx:876
 THnSparse.cxx:877
 THnSparse.cxx:878
 THnSparse.cxx:879
 THnSparse.cxx:880
 THnSparse.cxx:881
 THnSparse.cxx:882
 THnSparse.cxx:883
 THnSparse.cxx:884
 THnSparse.cxx:885
 THnSparse.cxx:886
 THnSparse.cxx:887
 THnSparse.cxx:888
 THnSparse.cxx:889
 THnSparse.cxx:890
 THnSparse.cxx:891
 THnSparse.cxx:892
 THnSparse.cxx:893
 THnSparse.cxx:894
 THnSparse.cxx:895
 THnSparse.cxx:896
 THnSparse.cxx:897
 THnSparse.cxx:898
 THnSparse.cxx:899
 THnSparse.cxx:900
 THnSparse.cxx:901
 THnSparse.cxx:902
 THnSparse.cxx:903
 THnSparse.cxx:904
 THnSparse.cxx:905
 THnSparse.cxx:906
 THnSparse.cxx:907
 THnSparse.cxx:908
 THnSparse.cxx:909
 THnSparse.cxx:910
 THnSparse.cxx:911
 THnSparse.cxx:912
 THnSparse.cxx:913
 THnSparse.cxx:914
 THnSparse.cxx:915
 THnSparse.cxx:916
 THnSparse.cxx:917
 THnSparse.cxx:918
 THnSparse.cxx:919
 THnSparse.cxx:920
 THnSparse.cxx:921
 THnSparse.cxx:922
 THnSparse.cxx:923
 THnSparse.cxx:924
 THnSparse.cxx:925
 THnSparse.cxx:926
 THnSparse.cxx:927
 THnSparse.cxx:928
 THnSparse.cxx:929
 THnSparse.cxx:930
 THnSparse.cxx:931
 THnSparse.cxx:932
 THnSparse.cxx:933
 THnSparse.cxx:934
 THnSparse.cxx:935
 THnSparse.cxx:936
 THnSparse.cxx:937
 THnSparse.cxx:938
 THnSparse.cxx:939
 THnSparse.cxx:940
 THnSparse.cxx:941
 THnSparse.cxx:942
 THnSparse.cxx:943
 THnSparse.cxx:944
 THnSparse.cxx:945
 THnSparse.cxx:946
 THnSparse.cxx:947
 THnSparse.cxx:948
 THnSparse.cxx:949
 THnSparse.cxx:950
 THnSparse.cxx:951
 THnSparse.cxx:952
 THnSparse.cxx:953
 THnSparse.cxx:954