Changing once more (hopefully we get it correct this time...) the logic to trig the...
[u/mrichter/AliRoot.git] / 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