// @(#)root/tree:$Name:  $:$Id: TEntryListBlock.h,v 1.3 2006/10/31 15:18:33 brun Exp $
// Author: Anna Kreshuk 27/10/2006

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

//////////////////////////////////////////////////////////////////////////
// TEntryListBlock
//
// Used internally in TEntryList to store the entry numbers. 
//
// There are 2 ways to represent entry numbers in a TEntryListBlock:
// 1) as bits, where passing entry numbers are assigned 1, not passing - 0
// 2) as a simple array of entry numbers
// In both cases, a UShort_t* is used. The second option is better in case
// less than 1/16 of entries passes the selection, and the representation can be
// changed by calling OptimizeStorage() function. 
// When the block is being filled, it's always stored as bits, and the OptimizeStorage()
// function is called by TEntryList when it starts filling the next block. If
// Enter() or Remove() is called after OptimizeStorage(), representation is 
// again changed to 1).
//
// Operations on blocks (see also function comments):
// - Merge() - adds all entries from one block to the other. If the first block 
//             uses array representation, it's changed to bits representation only
//             if the total number of passing entries is still less than kBlockSize
// - GetEntry(n) - returns n-th non-zero entry.
// - Next()      - return next non-zero entry. In case of representation 1), Next()
//                 is faster than GetEntry()
//
//////////////////////////////////////////////////////////////////////////

#ifndef ROOT_TEntryListBlock
#define ROOT_TEntryListBlock

#ifndef ROOT_TObject
#include "TObject.h"
#endif

class TEntryListBlock:public TObject 
{
 protected:
   Int_t    fNPassed;    //number of entries in the entry list 
   Int_t    fN;          //size of fIndices for I/O  =fNPassed for list, fBlockSize for bits
   UShort_t *fIndices;   //[fN]
   Int_t    fType;       //0 - bits, 1 - list
   Bool_t   fPassing;    //1 - stores entries that belong to the list
                         //0 - stores entries that don't belong to the list (not there yet)
   UShort_t fCurrent;    //! to fasten Enter() and Contains() in list mode
   Int_t    fLastIndexQueried; //! to optimize GetEntry() in a loop
   Int_t    fLastIndexReturned; //! to optimize GetEntry() in a loop

   void Transform(Bool_t dir, UShort_t *indexnew);

 public:

   enum { kBlockSize = 4000 }; //size of the block, 4000 UShort_ts
   TEntryListBlock();
   TEntryListBlock(const TEntryListBlock &eblock);
   ~TEntryListBlock();

   Bool_t  Enter(Int_t entry);
   Bool_t  Remove(Int_t entry);
   Int_t   Contains(Int_t entry);
   void    OptimizeStorage();
   Int_t   Merge(TEntryListBlock *block);
   Int_t   Next();
   Int_t   GetEntry(Int_t entry);
   void    ResetIndices() {fLastIndexQueried = -1, fLastIndexReturned = -1;}
   Int_t   GetType() { return fType; }
   Int_t   GetNPassed() { return fNPassed; }
   virtual void Print(const Option_t *option = "") const;
   void    PrintWithShift(Int_t shift) const;

   ClassDef(TEntryListBlock, 1) //Used internally in TEntryList to store the entry numbers

};

#endif