Commiting the new analysis examples
[u/mrichter/AliRoot.git] / ITS / AliITSIntMap.h
CommitLineData
b15de2d2 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. //
53ae21ce 7// //
b15de2d2 8//////////////////////////////////////////////////////////////////////
9
10#include <Rtypes.h>
11
12class AliITSIntMapNode;
13
14class 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();}
38 UInt_t GetTreeHeight() const;
b15de2d2 39
40 private:
53ae21ce 41 UInt_t fNrEntries; // nr of entries in map
42 AliITSIntMapNode* fRoot; // link to first node of tree
43 Bool_t fFastAccess; // is the array below initialized (key ordered)?
44 Bool_t fFastAccessSerialize;// is fast access array initialized (tree ordered)?
45 AliITSIntMapNode** fFastAccessArray; // array of pointers to nodes
46 UInt_t fDummyIndex; // dummy index used when traversing tree
47
48 void ClearNode(AliITSIntMapNode* &node); // delete this node and all below
49 AliITSIntMapNode* CloneNode(AliITSIntMapNode* node) const;
50 void InsertNode(Int_t key, Int_t val, AliITSIntMapNode* &node, UInt_t height);
51 void RemoveNode(Int_t key, AliITSIntMapNode* &node);
52 AliITSIntMapNode* FindNode(Int_t key, AliITSIntMapNode* node, UInt_t height) const;
53 AliITSIntMapNode* FindNodeIndex(UInt_t index, AliITSIntMapNode* node) const;
54 AliITSIntMapNode* FindMinNode(AliITSIntMapNode* node) const;
55 AliITSIntMapNode* FindMaxNode(AliITSIntMapNode* node) const;
56 void PrintNode(AliITSIntMapNode* node) const;
57 UInt_t GetTreeHeightNode(AliITSIntMapNode* node) const;
58
59 AliITSIntMapNode* BalanceNode(Int_t lowInd, Int_t highInd);
60 void ClearFastAccess();
61 void InitFastAccess();
62 void InitFastAccessNode(AliITSIntMapNode* node);
63 void InitFastAccessSerialize();
64 void InitFastAccessSerializeNode(AliITSIntMapNode* node);
b15de2d2 65
66};
67
68#endif