1 #ifndef ALI_ITS_INTMAP_H
2 #define ALI_ITS_INTMAP_H
4 //////////////////////////////////////////////////////////////////////
5 // Author: Henrik Tydesjo //
6 // This class implements the use of a map of integers. //
8 //////////////////////////////////////////////////////////////////////
12 class AliITSIntMapNode;
18 AliITSIntMap(AliITSIntMapNode* root, UInt_t nrEntries);
19 AliITSIntMap(const AliITSIntMap& imap);
20 virtual ~AliITSIntMap();
21 AliITSIntMap& operator=(const AliITSIntMap& imap);
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;
31 UInt_t GetNrEntries() const {return fNrEntries;}
32 Int_t GetKeyIndex(UInt_t index);
33 Int_t GetValIndex(UInt_t index);
35 void PrintEntries() const;
37 void PrepareSerialize() {InitFastAccessSerialize();}
38 void PrepareSerializeOrdered() {InitFastAccess();}
39 UInt_t GetTreeHeight() const;
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
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;
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);