Line data    Source code

       1             : #ifndef ALIITSINTMAP_H
       2             : #define ALIITSINTMAP_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        1920 :   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           0 :   void               PrepareSerialize() {InitFastAccessSerialize();}
      38           0 :   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