ITS/AliITSIntMap.h

   1 #ifndef ALI_ITS_INTMAP_H
   2 #define ALI_ITS_INTMAP_H
   3
   4 //////////////////////////////////////////////////////////////////////
   5 // Author: Henrik Tydesjo                                           //
   6 // This class implements the use of a map of integers.              //
   7 //                                                                  //
   8 //////////////////////////////////////////////////////////////////////
   9
  10 #include <Rtypes.h>
  11
  12 class AliITSIntMapNode;
  13
  14 class AliITSIntMap {
  15
  16  public:
  17   AliITSIntMap();
  18   AliITSIntMap(AliITSIntMapNode* root, UInt_t nrEntries);
  19   AliITSIntMap(const AliITSIntMap& imap);
  20   virtual ~AliITSIntMap();
  21   AliITSIntMap& operator=(const AliITSIntMap& imap);
  22
  23   void               Clear();
  24   AliITSIntMap*      Clone() const;
  25   Bool_t             Insert(Int_t key, Int_t val);
  26   Bool_t             Remove(Int_t key);
  27   Bool_t             Pop(Int_t& key, Int_t& val);
  28   AliITSIntMapNode*  Find(Int_t key) const;
  29   Int_t              GetVal(Int_t key) const;
  30
  31   UInt_t             GetNrEntries() const {return fNrEntries;}
  32   Int_t              GetKeyIndex(UInt_t index);
  33   Int_t              GetValIndex(UInt_t index);
  34
  35   void               PrintEntries() const;
  36   void               Balance();
  37   void               PrepareSerialize() {InitFastAccessSerialize();}
  38   UInt_t             GetTreeHeight() const;
  39
  40  private:
  41   UInt_t             fNrEntries;          // nr of entries in map
  42   AliITSIntMapNode*  fRoot;               // link to first node of tree
  43   Bool_t             fFastAccess;         // is the array below initialized (key ordered)?
  44   Bool_t             fFastAccessSerialize;// is fast access array initialized (tree ordered)?
  45   AliITSIntMapNode** fFastAccessArray;    // array of pointers to nodes
  46   UInt_t             fDummyIndex;         // dummy index used when traversing tree
  47
  48   void               ClearNode(AliITSIntMapNode* &node); // delete this node and all below
  49   AliITSIntMapNode*  CloneNode(AliITSIntMapNode* node) const;
  50   void               InsertNode(Int_t key, Int_t val, AliITSIntMapNode* &node, UInt_t height);
  51   void               RemoveNode(Int_t key, AliITSIntMapNode* &node);
  52   AliITSIntMapNode*  FindNode(Int_t key, AliITSIntMapNode* node, UInt_t height) const;
  53   AliITSIntMapNode*  FindNodeIndex(UInt_t index, AliITSIntMapNode* node) const;
  54   AliITSIntMapNode*  FindMinNode(AliITSIntMapNode* node) const;
  55   AliITSIntMapNode*  FindMaxNode(AliITSIntMapNode* node) const;
  56   void               PrintNode(AliITSIntMapNode* node) const;
  57   UInt_t             GetTreeHeightNode(AliITSIntMapNode* node) const;
  58
  59   AliITSIntMapNode*  BalanceNode(Int_t lowInd, Int_t highInd);
  60   void               ClearFastAccess();
  61   void               InitFastAccess();
  62   void               InitFastAccessNode(AliITSIntMapNode* node);
  63   void               InitFastAccessSerialize();
  64   void               InitFastAccessSerializeNode(AliITSIntMapNode* node);
  65
  66 };
  67
  68 #endif