]>
Commit | Line | Data |
---|---|---|
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 | 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 |