include/root/TEntryListBlock.h

0001 // @(#)root/tree:$Id$
0002 // Author: Anna Kreshuk 27/10/2006
0003
0004 /*************************************************************************
0005  * Copyright (C) 1995-2006, Rene Brun and Fons Rademakers.               *
0006  * All rights reserved.                                                  *
0007  *                                                                       *
0008  * For the licensing terms see $ROOTSYS/LICENSE.                         *
0009  * For the list of contributors see $ROOTSYS/README/CREDITS.             *
0010  *************************************************************************/
0011
0012 //////////////////////////////////////////////////////////////////////////
0013 // TEntryListBlock
0014 //
0015 // Used internally in TEntryList to store the entry numbers.
0016 //
0017 // There are 2 ways to represent entry numbers in a TEntryListBlock:
0018 // 1) as bits, where passing entry numbers are assigned 1, not passing - 0
0019 // 2) as a simple array of entry numbers
0020 // In both cases, a UShort_t* is used. The second option is better in case
0021 // less than 1/16 of entries passes the selection, and the representation can be
0022 // changed by calling OptimizeStorage() function.
0023 // When the block is being filled, it's always stored as bits, and the OptimizeStorage()
0024 // function is called by TEntryList when it starts filling the next block. If
0025 // Enter() or Remove() is called after OptimizeStorage(), representation is
0026 // again changed to 1).
0027 //
0028 // Operations on blocks (see also function comments):
0029 // - Merge() - adds all entries from one block to the other. If the first block
0030 //             uses array representation, it's changed to bits representation only
0031 //             if the total number of passing entries is still less than kBlockSize
0032 // - GetEntry(n) - returns n-th non-zero entry.
0033 // - Next()      - return next non-zero entry. In case of representation 1), Next()
0034 //                 is faster than GetEntry()
0035 //
0036 //////////////////////////////////////////////////////////////////////////
0037
0038 #ifndef ROOT_TEntryListBlock
0039 #define ROOT_TEntryListBlock
0040
0041 #include "TObject.h"
0042
0043 class TEntryListBlock:public TObject
0044 {
0045  protected:
0046    Int_t    fNPassed;           ///< number of entries in the entry list (if fPassing=0 - number of entries
0047                                 ///< not in the entry list
0048    Int_t    fN;                 ///< size of fIndices for I/O  =fNPassed for list, fBlockSize for bits
0049    UShort_t *fIndices;          ///<[fN]
0050    Int_t    fType;              ///<0 - bits, 1 - list
0051    bool     fPassing;           ///<1 - stores entries that belong to the list
0052                                 ///<0 - stores entries that don't belong to the list
0053    UShort_t fCurrent;           ///<! to fasten  Contains() in list mode
0054    Int_t    fLastIndexQueried;  ///<! to optimize GetEntry() in a loop
0055    Int_t    fLastIndexReturned; ///<! to optimize GetEntry() in a loop
0056
0057    void Transform(bool dir, UShort_t *indexnew);
0058
0059  public:
0060
0061    enum { kBlockSize = 4000 }; //size of the block, 4000 UShort_ts
0062    TEntryListBlock();
0063    TEntryListBlock(const TEntryListBlock &eblock);
0064    ~TEntryListBlock() override;
0065    TEntryListBlock &operator=(const TEntryListBlock &rhs);
0066
0067    bool    Enter(Int_t entry);
0068    bool    Remove(Int_t entry);
0069    Int_t   Contains(Int_t entry);
0070    void    OptimizeStorage();
0071    Int_t   Merge(TEntryListBlock *block);
0072    Int_t   Next();
0073    Int_t   GetEntry(Int_t entry);
0074    void    ResetIndices() {fLastIndexQueried = -1, fLastIndexReturned = -1;}
0075    Int_t   GetType() { return fType; }
0076    Int_t   GetNPassed();
0077    void Print(const Option_t *option = "") const override;
0078    void    PrintWithShift(Int_t shift) const;
0079
0080    ClassDefOverride(TEntryListBlock, 1) //Used internally in TEntryList to store the entry numbers
0081
0082 };
0083
0084 #endif