1. Improved implementation of AliITSIntMap and AliITSOnlineCalibrationSPDhandler...

[u/mrichter/AliRoot.git] / ITS / AliITSIntMap.h

diff --git a/ITS/AliITSIntMap.h b/ITS/AliITSIntMap.h
index d7f7ccc1f3bd1fd60ea1442c8a861cc2437d5319..9a8f9f83514a549482e5f86f9c4288eae3ae7833 100644 (file)
--- a/ITS/AliITSIntMap.h
+++ b/ITS/AliITSIntMap.h
@@ -4,8 +4,7 @@
 //////////////////////////////////////////////////////////////////////
 // Author: Henrik Tydesjo                                           //
 // This class implements the use of a map of integers.              //
-// For simplicity, this version is just a sorted linked list,       //
-// but it may be rewritten later for better performance if required.//
+//                                                                  //
 //////////////////////////////////////////////////////////////////////  
 
 #include <Rtypes.h>
@@ -16,22 +15,53 @@ class AliITSIntMap {
 
  public:
   AliITSIntMap();
+  AliITSIntMap(AliITSIntMapNode* root, UInt_t nrEntries);
   AliITSIntMap(const AliITSIntMap& imap);
   virtual ~AliITSIntMap();
   AliITSIntMap& operator=(const AliITSIntMap& imap);
 
   void               Clear();
+  AliITSIntMap*      Clone() const;
   Bool_t             Insert(Int_t key, Int_t val);
   Bool_t             Remove(Int_t key);
+  Bool_t             Pop(Int_t& key, Int_t& val);
   AliITSIntMapNode*  Find(Int_t key) const;
-  Int_t              GetKey(UInt_t index) const;
-  Int_t              GetVal(UInt_t index) const;
+  Int_t              GetVal(Int_t key) const;
+
   UInt_t             GetNrEntries() const {return fNrEntries;}
+  Int_t              GetKeyIndex(UInt_t index);
+  Int_t              GetValIndex(UInt_t index);
+
   void               PrintEntries() const;
+  void               Balance();
+  void               PrepareSerialize() {InitFastAccessSerialize();}
+  UInt_t             GetTreeHeight() const;
 
  private:
-  UInt_t             fNrEntries;   // nr of entries in map
-  AliITSIntMapNode*  fFirst;       // link to first node of map
+  UInt_t             fNrEntries;          // nr of entries in map
+  AliITSIntMapNode*  fRoot;               // link to first node of tree
+  Bool_t             fFastAccess;         // is the array below initialized (key ordered)?
+  Bool_t             fFastAccessSerialize;// is fast access array initialized (tree ordered)?
+  AliITSIntMapNode** fFastAccessArray;    // array of pointers to nodes
+  UInt_t             fDummyIndex;         // dummy index used when traversing tree
+
+  void               ClearNode(AliITSIntMapNode* &node); // delete this node and all below
+  AliITSIntMapNode*  CloneNode(AliITSIntMapNode* node) const;
+  void               InsertNode(Int_t key, Int_t val, AliITSIntMapNode* &node, UInt_t height);
+  void               RemoveNode(Int_t key, AliITSIntMapNode* &node);
+  AliITSIntMapNode*  FindNode(Int_t key, AliITSIntMapNode* node, UInt_t height) const;
+  AliITSIntMapNode*  FindNodeIndex(UInt_t index, AliITSIntMapNode* node) const;
+  AliITSIntMapNode*  FindMinNode(AliITSIntMapNode* node) const;
+  AliITSIntMapNode*  FindMaxNode(AliITSIntMapNode* node) const;
+  void               PrintNode(AliITSIntMapNode* node) const;
+  UInt_t             GetTreeHeightNode(AliITSIntMapNode* node) const;
+
+  AliITSIntMapNode*  BalanceNode(Int_t lowInd, Int_t highInd);
+  void               ClearFastAccess();
+  void               InitFastAccess();
+  void               InitFastAccessNode(AliITSIntMapNode* node);
+  void               InitFastAccessSerialize();
+  void               InitFastAccessSerializeNode(AliITSIntMapNode* node);
 
 };