store also difference in local Y
[u/mrichter/AliRoot.git] / ITS / AliITSIntMap.h
CommitLineData
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
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();}
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