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   void               PrepareSerializeOrdered() {InitFastAccess();}
  39   UInt_t             GetTreeHeight() const;
  40
  41  private:
  42   UInt_t             fNrEntries;          // nr of entries in map
  43   AliITSIntMapNode*  fRoot;               // link to first node of tree
  44   Bool_t             fFastAccess;         // is fast access array initialized (key ordered)?
  45   Bool_t             fFastAccessSerialize;// is fast access array initialized (tree ordered)?
  46   AliITSIntMapNode** fFastAccessArray;    // array of pointers to nodes
  47   UInt_t             fDummyIndex;         // dummy index used when traversing tree
  48
  49   void               ClearNode(AliITSIntMapNode* &node); // delete this node and all below
  50   AliITSIntMapNode*  CloneNode(AliITSIntMapNode* node) const;
  51   void               InsertNode(Int_t key, Int_t val, AliITSIntMapNode* &node, UInt_t height);
  52   void               RemoveNode(Int_t key, AliITSIntMapNode* &node);
  53   AliITSIntMapNode*  FindNode(Int_t key, AliITSIntMapNode* node, UInt_t height) const;
  54   AliITSIntMapNode*  FindNodeIndex(UInt_t index, AliITSIntMapNode* node) const;
  55   AliITSIntMapNode*  FindMinNode(AliITSIntMapNode* node) const;
  56   AliITSIntMapNode*  FindMaxNode(AliITSIntMapNode* node) const;
  57   void               PrintNode(AliITSIntMapNode* node) const;
  58   UInt_t             GetTreeHeightNode(AliITSIntMapNode* node) const;
  59
  60   AliITSIntMapNode*  BalanceNode(Int_t lowInd, Int_t highInd);
  61   void               ClearFastAccess();
  62   void               InitFastAccess();
  63   void               InitFastAccessNode(AliITSIntMapNode* node);
  64   void               InitFastAccessSerialize();
  65   void               InitFastAccessSerializeNode(AliITSIntMapNode* node);
  66
  67 };
  68
  69 #endif