]>
Commit | Line | Data |
---|---|---|
416d7e17 | 1 | #ifndef ALIITSINTMAP_H |
2 | #define ALIITSINTMAP_H | |
b15de2d2 | 3 | |
4 | ////////////////////////////////////////////////////////////////////// | |
5 | // Author: Henrik Tydesjo // | |
6 | // This class implements the use of a map of integers. // | |
53ae21ce | 7 | // // |
b15de2d2 | 8 | ////////////////////////////////////////////////////////////////////// |
9 | ||
10 | #include <Rtypes.h> | |
11 | ||
12 | class AliITSIntMapNode; | |
13 | ||
14 | class AliITSIntMap { | |
15 | ||
16 | public: | |
17 | AliITSIntMap(); | |
53ae21ce | 18 | AliITSIntMap(AliITSIntMapNode* root, UInt_t nrEntries); |
b15de2d2 | 19 | AliITSIntMap(const AliITSIntMap& imap); |
20 | virtual ~AliITSIntMap(); | |
21 | AliITSIntMap& operator=(const AliITSIntMap& imap); | |
22 | ||
23 | void Clear(); | |
53ae21ce | 24 | AliITSIntMap* Clone() const; |
b15de2d2 | 25 | Bool_t Insert(Int_t key, Int_t val); |
26 | Bool_t Remove(Int_t key); | |
53ae21ce | 27 | Bool_t Pop(Int_t& key, Int_t& val); |
b15de2d2 | 28 | AliITSIntMapNode* Find(Int_t key) const; |
53ae21ce | 29 | Int_t GetVal(Int_t key) const; |
30 | ||
b15de2d2 | 31 | UInt_t GetNrEntries() const {return fNrEntries;} |
53ae21ce | 32 | Int_t GetKeyIndex(UInt_t index); |
33 | Int_t GetValIndex(UInt_t index); | |
34 | ||
b15de2d2 | 35 | void PrintEntries() const; |
53ae21ce | 36 | void Balance(); |
37 | void PrepareSerialize() {InitFastAccessSerialize();} | |
6727e2db | 38 | void PrepareSerializeOrdered() {InitFastAccess();} |
53ae21ce | 39 | UInt_t GetTreeHeight() const; |
b15de2d2 | 40 | |
41 | private: | |
53ae21ce | 42 | UInt_t fNrEntries; // nr of entries in map |
43 | AliITSIntMapNode* fRoot; // link to first node of tree | |
6727e2db | 44 | Bool_t fFastAccess; // is fast access array initialized (key ordered)? |
53ae21ce | 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); | |
b15de2d2 | 66 | |
67 | }; | |
68 | ||
69 | #endif |