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

//////////////////////////////////////////////////////////////////////
// Author: Henrik Tydesjo                                           //
// This class implements the use of a map of integers.              //
// The values are kept in a binary tree, which is automatically     //
// reordered to be more balanced when the tree height gets too large//
//////////////////////////////////////////////////////////////////////  

#include "AliITSIntMap.h"
#include "AliITSIntMapNode.h"
#include <TMath.h>
#include <TError.h>

AliITSIntMap::AliITSIntMap():
  fNrEntries(0),
  fRoot(NULL),
  fFastAccess(kFALSE),
  fFastAccessSerialize(kFALSE),
  fFastAccessArray(NULL),
  fDummyIndex(0)
{}

AliITSIntMap::AliITSIntMap(AliITSIntMapNode* root, UInt_t nrEntries):
  fNrEntries(nrEntries),
  fRoot(root),
  fFastAccess(kFALSE),
  fFastAccessSerialize(kFALSE),
  fFastAccessArray(NULL),
  fDummyIndex(0)
{}

AliITSIntMap::AliITSIntMap(const AliITSIntMap& imap):
  fNrEntries(0),
  fRoot(NULL),
  fFastAccess(kFALSE),
  fFastAccessSerialize(kFALSE),
  fFastAccessArray(NULL),
  fDummyIndex(0)
{
  // copy constructor
  *this = imap;
}

AliITSIntMap::~AliITSIntMap() {
  Clear();
}

AliITSIntMap& AliITSIntMap::operator=(const AliITSIntMap& imap) {
  // assignment operator
  if (this!=&imap) {
    this->Clear();
    fRoot = CloneNode(imap.fRoot);
    fFastAccess=kFALSE;
    fFastAccessSerialize=kFALSE;
    fFastAccessArray=NULL;
    fDummyIndex=0;
  }
  return *this;
}

void AliITSIntMap::Clear() {
  // clear the whole map
  ClearFastAccess();
  ClearNode(fRoot);
}

void AliITSIntMap::ClearNode(AliITSIntMapNode* &node) {
  // clear this node and all children nodes
  if (node==NULL) return;
  ClearNode(node->Left());
  ClearNode(node->Right());
  delete node;
  fNrEntries--;
  node = NULL;
  fFastAccess=kFALSE;
  fFastAccessSerialize=kFALSE;
}

AliITSIntMap* AliITSIntMap::Clone() const {
  // returns a clone of the map
  AliITSIntMapNode* newRoot;
  newRoot = CloneNode(fRoot);
  AliITSIntMap* newMap = new AliITSIntMap(newRoot,fNrEntries);
  return newMap;
}

AliITSIntMapNode* AliITSIntMap::CloneNode(AliITSIntMapNode* node) const {
  if (node==NULL) return NULL;
  else return new AliITSIntMapNode(node->Key(),node->Val(),CloneNode(node->Left()),CloneNode(node->Right()));
}

Bool_t AliITSIntMap::Insert(Int_t key, Int_t val) {
  // insert a new node into the map (returns true if the node was not present before)
  UInt_t entriesBefore = fNrEntries;
  InsertNode(key,val,fRoot,0);
  if (fNrEntries>entriesBefore) return kTRUE;
  else return kFALSE;
}

void AliITSIntMap::InsertNode(Int_t key, Int_t val, AliITSIntMapNode* &node, UInt_t height) {
  // method to insert a node in the tree (used recursively)
  height++;
  if (node==NULL) {
    node = new AliITSIntMapNode(key,val,NULL,NULL);
    fNrEntries++;
    fFastAccess=kFALSE;
    fFastAccessSerialize=kFALSE;
    UInt_t balanceHeight = (UInt_t) (TMath::Log(fNrEntries+1)/TMath::Log(2)+1);
    if ( (height-balanceHeight)*(height-balanceHeight) > fNrEntries ) {
      Balance();
    }
  }
  else if (key < node->Key()) {
    InsertNode(key,val,node->Left(),height);
  }
  else if (key > node->Key()) {
    InsertNode(key,val,node->Right(),height);
  }
  else { // (key==node->Key()): do nothing (avoid duplicates)
    //    Warning("AliITSIntMap::InsertNode","Node with key %d already in map. Not inserted.",key);
  }
}

Bool_t AliITSIntMap::Remove(Int_t key) {
  // remove a node from the map (returns true if the node was found)
  UInt_t entriesBefore = fNrEntries;
  RemoveNode(key,fRoot);
  if (fNrEntries<entriesBefore) return kTRUE;
  else return kFALSE;
}

void AliITSIntMap::RemoveNode(Int_t key, AliITSIntMapNode* &node) {
  // method to remove a node in the tree (used recursively)
  if (node == NULL) return;   // node not found; do nothing
  if (key < node->Key()) {
    RemoveNode(key,node->Left());
  }
  else if (key > node->Key()) {
    RemoveNode(key,node->Right());
  }
  else if (node->Left()!=NULL && node->Right()!=NULL) { // Two children
    if (fNrEntries%2==0) { // for better balance, remove from left or right sub tree
      AliITSIntMapNode* moveNode = FindMinNode(node->Right());
      node->SetKey(moveNode->Key());
      node->SetVal(moveNode->Val());
      RemoveNode(moveNode->Key(),node->Right());
    }
    else {
      AliITSIntMapNode* moveNode = FindMaxNode(node->Left());
      node->SetKey(moveNode->Key());
      node->SetVal(moveNode->Val());
      RemoveNode(moveNode->Key(),node->Left());
    }
  }
  else {
    AliITSIntMapNode* oldNode = node;
    node = (node->Left()!=NULL) ? node->Left() : node->Right();
    fNrEntries--;
    delete oldNode;
    fFastAccess=kFALSE;
    fFastAccessSerialize=kFALSE;
  }
}

Bool_t AliITSIntMap::Pop(Int_t& key, Int_t& val) {
  // removes one entry (root) from tree, giving its key,val pair
  if (fRoot!=NULL) {
    key = fRoot->Key();
    val = fRoot->Val();
    return Remove(key);
  }
  else return kFALSE;
}

AliITSIntMapNode* AliITSIntMap::FindMinNode(AliITSIntMapNode* node) const {
  // returns the node with smallest key in the sub tree starting from node
  if (node==NULL) return NULL;
  else if (node->Left()==NULL) return node;
  else return FindMinNode(node->Left());
}

AliITSIntMapNode* AliITSIntMap::FindMaxNode(AliITSIntMapNode* node) const {
  // returns the node with largest key in the sub tree starting from node
  if (node==NULL) return NULL;
  else if (node->Right()==NULL) return node;
  else return FindMaxNode(node->Right());
}

AliITSIntMapNode* AliITSIntMap::Find(Int_t key) const {
  // finds a node and returns it (returns NULL if not found)
  return FindNode(key,fRoot,0);
}

AliITSIntMapNode*  AliITSIntMap::FindNode(Int_t key, AliITSIntMapNode* node, UInt_t height) const {
  // method to find a node in the tree (used recursively)
  if (node==NULL) return NULL;
  height++;
  if (key<node->Key()) return FindNode(key,node->Left(),height);
  else if (key>node->Key()) return FindNode(key,node->Right(),height);
  else { // Match
//    //*** balance if height too high. const above have to be removed if this is needed ***
//    UInt_t balanceHeight = (UInt_t) (TMath::Log(fNrEntries+1)/TMath::Log(2)+1);
//    if ( (height-balanceHeight)*(height-balanceHeight) > fNrEntries ) {
//      Balance();
//    }
    return node;
  }
}

Int_t AliITSIntMap::GetVal(Int_t key) const {
  // returns the value for the node with key
  AliITSIntMapNode* node = Find(key);
  if (node!=NULL) {
    return node->Val();
  }
  else {
    Warning("AliITSIntMap::GetVal","Node with key %d not found in map. Returning -999.",key);
    return -999;
  }
}

void AliITSIntMap::Balance() {
  // method to balance the tree
  //  printf("balance H=%d --> ",GetTreeHeight());
  if (fNrEntries==0) return;
  if (!fFastAccess) InitFastAccess();
  fRoot = BalanceNode(0,fNrEntries-1);
  //  printf("H=%d\n",GetTreeHeight());
}

AliITSIntMapNode* AliITSIntMap::BalanceNode(Int_t lowInd, Int_t highInd) {
  // balances the tree by selecting the center of an index range 
  // (used recursively)
  if (lowInd>highInd) return NULL;
  Int_t thisInd = lowInd+(highInd-lowInd)/2;
  fFastAccessArray[thisInd]->Left() = BalanceNode(lowInd,thisInd-1);
  fFastAccessArray[thisInd]->Right() = BalanceNode(thisInd+1,highInd);
  return fFastAccessArray[thisInd];
}

void AliITSIntMap::ClearFastAccess(){
  // clears the fast access array of pointers
  if (fFastAccessArray!=NULL) {
    delete [] fFastAccessArray;
    fFastAccessArray=NULL;
  }
  fFastAccess=kFALSE;
  fFastAccessSerialize=kFALSE;
}

void AliITSIntMap::InitFastAccess(){
  // initializes the fast access array
  if (fFastAccess) return;
  ClearFastAccess();
  if (fNrEntries>0) {
    fFastAccessArray = new AliITSIntMapNode*[fNrEntries];
    fDummyIndex=0;
    InitFastAccessNode(fRoot);
    fFastAccess=kTRUE;
  }
}

void AliITSIntMap::InitFastAccessNode(AliITSIntMapNode* node) {
  // initializes the fast access array starting from node (used recursively)
  if (node==NULL) return;
  InitFastAccessNode(node->Left());
  fFastAccessArray[fDummyIndex++] = node;
  InitFastAccessNode(node->Right());
}

void AliITSIntMap::InitFastAccessSerialize(){
  // initializes the fast access array
  if (fFastAccessSerialize) return;
  ClearFastAccess();
  if (fNrEntries>0) {
    fFastAccessArray = new AliITSIntMapNode*[fNrEntries];
    fDummyIndex=0;
    InitFastAccessSerializeNode(fRoot);
    fFastAccessSerialize=kTRUE;
  }
}

void AliITSIntMap::InitFastAccessSerializeNode(AliITSIntMapNode* node) {
  // initializes the fast access array for tree ordering starting from node (used recursively)
  if (node==NULL) return;
  fFastAccessArray[fDummyIndex++] = node;
  InitFastAccessSerializeNode(node->Left());
  InitFastAccessSerializeNode(node->Right());
}

Int_t AliITSIntMap::GetKeyIndex(UInt_t index) {
  // returns the key of the node at position 'index' in the map
  // returns -1 if out of bounds
  if (index<fNrEntries) {
    if (!fFastAccess && !fFastAccessSerialize) InitFastAccess();
    return fFastAccessArray[index]->Key();
  }
  return -1;
}

Int_t AliITSIntMap::GetValIndex(UInt_t index) {
  // returns the value of the node at position 'index' in the map
  // returns -1 if out of bounds
  if (index<fNrEntries) {
    if (!fFastAccess && !fFastAccessSerialize) InitFastAccess();
    return fFastAccessArray[index]->Val();
  }
  return -1;
}

AliITSIntMapNode* AliITSIntMap::FindNodeIndex(UInt_t index, AliITSIntMapNode* node) const {
  // method to find the index:th node in the tree (used recursively)
  // this method should not be needed anymore, since GetKeyIndex/GetValIndex is faster
  static UInt_t fTmpInd;
  if (node==fRoot) fTmpInd=0;
  if (node->Left()!=NULL) {
    AliITSIntMapNode* tmpResult = FindNodeIndex(index,node->Left());
    if (tmpResult != NULL) {
      return tmpResult;
    }
  }
  if (fTmpInd==index) return node;
  fTmpInd++;
  if (node->Right()!=NULL) {
    AliITSIntMapNode* tmpResult = FindNodeIndex(index,node->Right());
    if (tmpResult != NULL) {
      return tmpResult;
    }
  }
  return NULL;
}

void AliITSIntMap::PrintEntries() const {
  // prints all the entries (key,value pairs) of the map
  printf("*** Map Entries: (key , value)***\n");
  PrintNode(fRoot);
  printf("*********************************\n");
}

void AliITSIntMap::PrintNode(AliITSIntMapNode* node) const {
  // method to print node entry (key,value) (used recursively)
  if (node==NULL) return;
  if (node->Left()!=NULL) PrintNode(node->Left());
  printf("%d , %d\n",node->Key(),node->Val());
  if (node->Right()!=NULL) PrintNode(node->Right());
}

UInt_t AliITSIntMap::GetTreeHeight() const {
  // returns the height of the tree
  return GetTreeHeightNode(fRoot);
}

UInt_t AliITSIntMap::GetTreeHeightNode(AliITSIntMapNode* node) const {
  // returns tree height for the sub tree starting from node (used recursively)
  if (node==NULL) return 0;
  UInt_t leftH = GetTreeHeightNode(node->Left());
  UInt_t rightH = GetTreeHeightNode(node->Right());
  if (leftH>=rightH) return leftH+1;
  else               return rightH+1;
}
Commit	Line	Data
b15de2d2	1	//////////////////////////////////////////////////////////////////////
	2	// Author: Henrik Tydesjo //
	3	// This class implements the use of a map of integers. //
53ae21ce	4	// The values are kept in a binary tree, which is automatically //
53ae21ce	5	// reordered to be more balanced when the tree height gets too large//
b15de2d2	6	//////////////////////////////////////////////////////////////////////
	7
	8	#include "AliITSIntMap.h"
	9	#include "AliITSIntMapNode.h"
53ae21ce	10	#include <TMath.h>
53ae21ce	11	#include <TError.h>
b15de2d2	12
	13	AliITSIntMap::AliITSIntMap():
	14	fNrEntries(0),
53ae21ce	15	fRoot(NULL),
	16	fFastAccess(kFALSE),
	17	fFastAccessSerialize(kFALSE),
	18	fFastAccessArray(NULL),
	19	fDummyIndex(0)
	20	{}
	21
	22	AliITSIntMap::AliITSIntMap(AliITSIntMapNode* root, UInt_t nrEntries):
	23	fNrEntries(nrEntries),
	24	fRoot(root),
	25	fFastAccess(kFALSE),
	26	fFastAccessSerialize(kFALSE),
	27	fFastAccessArray(NULL),
	28	fDummyIndex(0)
b15de2d2	29	{}
	30
	31	AliITSIntMap::AliITSIntMap(const AliITSIntMap& imap):
	32	fNrEntries(0),
53ae21ce	33	fRoot(NULL),
	34	fFastAccess(kFALSE),
	35	fFastAccessSerialize(kFALSE),
	36	fFastAccessArray(NULL),
	37	fDummyIndex(0)
b15de2d2	38	{
b15de2d2	39	// copy constructor
53ae21ce	40	*this = imap;
b15de2d2	41	}
b15de2d2	42
53ae21ce	43	AliITSIntMap::~AliITSIntMap() {
	44	Clear();
	45	}
b15de2d2	46
	47	AliITSIntMap& AliITSIntMap::operator=(const AliITSIntMap& imap) {
	48	// assignment operator
	49	if (this!=&imap) {
	50	this->Clear();
53ae21ce	51	fRoot = CloneNode(imap.fRoot);
	52	fFastAccess=kFALSE;
	53	fFastAccessSerialize=kFALSE;
	54	fFastAccessArray=NULL;
	55	fDummyIndex=0;
b15de2d2	56	}
	57	return *this;
	58	}
	59
	60	void AliITSIntMap::Clear() {
	61	// clear the whole map
53ae21ce	62	ClearFastAccess();
	63	ClearNode(fRoot);
	64	}
	65
	66	void AliITSIntMap::ClearNode(AliITSIntMapNode* &node) {
	67	// clear this node and all children nodes
	68	if (node==NULL) return;
	69	ClearNode(node->Left());
	70	ClearNode(node->Right());
	71	delete node;
	72	fNrEntries--;
	73	node = NULL;
	74	fFastAccess=kFALSE;
	75	fFastAccessSerialize=kFALSE;
	76	}
	77
	78	AliITSIntMap* AliITSIntMap::Clone() const {
	79	// returns a clone of the map
	80	AliITSIntMapNode* newRoot;
	81	newRoot = CloneNode(fRoot);
	82	AliITSIntMap* newMap = new AliITSIntMap(newRoot,fNrEntries);
	83	return newMap;
	84	}
	85
	86	AliITSIntMapNode* AliITSIntMap::CloneNode(AliITSIntMapNode* node) const {
	87	if (node==NULL) return NULL;
	88	else return new AliITSIntMapNode(node->Key(),node->Val(),CloneNode(node->Left()),CloneNode(node->Right()));
b15de2d2	89	}
	90
	91	Bool_t AliITSIntMap::Insert(Int_t key, Int_t val) {
	92	// insert a new node into the map (returns true if the node was not present before)
53ae21ce	93	UInt_t entriesBefore = fNrEntries;
	94	InsertNode(key,val,fRoot,0);
	95	if (fNrEntries>entriesBefore) return kTRUE;
	96	else return kFALSE;
	97	}
	98
	99	void AliITSIntMap::InsertNode(Int_t key, Int_t val, AliITSIntMapNode* &node, UInt_t height) {
	100	// method to insert a node in the tree (used recursively)
	101	height++;
	102	if (node==NULL) {
	103	node = new AliITSIntMapNode(key,val,NULL,NULL);
b15de2d2	104	fNrEntries++;
53ae21ce	105	fFastAccess=kFALSE;
53ae21ce	106	fFastAccessSerialize=kFALSE;
52da6fa6	107	UInt_t balanceHeight = (UInt_t) (TMath::Log(fNrEntries+1)/TMath::Log(2)+1);
53ae21ce	108	if ( (height-balanceHeight)*(height-balanceHeight) > fNrEntries ) {
53ae21ce	109	Balance();
b15de2d2	110	}
b15de2d2	111	}
53ae21ce	112	else if (key < node->Key()) {
	113	InsertNode(key,val,node->Left(),height);
	114	}
	115	else if (key > node->Key()) {
	116	InsertNode(key,val,node->Right(),height);
	117	}
	118	else { // (key==node->Key()): do nothing (avoid duplicates)
3479cee3	119	// Warning("AliITSIntMap::InsertNode","Node with key %d already in map. Not inserted.",key);
53ae21ce	120	}
b15de2d2	121	}
	122
	123	Bool_t AliITSIntMap::Remove(Int_t key) {
	124	// remove a node from the map (returns true if the node was found)
53ae21ce	125	UInt_t entriesBefore = fNrEntries;
	126	RemoveNode(key,fRoot);
	127	if (fNrEntries<entriesBefore) return kTRUE;
	128	else return kFALSE;
	129	}
	130
	131	void AliITSIntMap::RemoveNode(Int_t key, AliITSIntMapNode* &node) {
	132	// method to remove a node in the tree (used recursively)
	133	if (node == NULL) return; // node not found; do nothing
	134	if (key < node->Key()) {
	135	RemoveNode(key,node->Left());
	136	}
	137	else if (key > node->Key()) {
	138	RemoveNode(key,node->Right());
	139	}
	140	else if (node->Left()!=NULL && node->Right()!=NULL) { // Two children
	141	if (fNrEntries%2==0) { // for better balance, remove from left or right sub tree
	142	AliITSIntMapNode* moveNode = FindMinNode(node->Right());
	143	node->SetKey(moveNode->Key());
	144	node->SetVal(moveNode->Val());
	145	RemoveNode(moveNode->Key(),node->Right());
b15de2d2	146	}
53ae21ce	147	else {
	148	AliITSIntMapNode* moveNode = FindMaxNode(node->Left());
	149	node->SetKey(moveNode->Key());
	150	node->SetVal(moveNode->Val());
	151	RemoveNode(moveNode->Key(),node->Left());
b15de2d2	152	}
b15de2d2	153	}
53ae21ce	154	else {
	155	AliITSIntMapNode* oldNode = node;
	156	node = (node->Left()!=NULL) ? node->Left() : node->Right();
	157	fNrEntries--;
	158	delete oldNode;
	159	fFastAccess=kFALSE;
	160	fFastAccessSerialize=kFALSE;
	161	}
	162	}
	163
	164	Bool_t AliITSIntMap::Pop(Int_t& key, Int_t& val) {
	165	// removes one entry (root) from tree, giving its key,val pair
	166	if (fRoot!=NULL) {
	167	key = fRoot->Key();
	168	val = fRoot->Val();
	169	return Remove(key);
	170	}
	171	else return kFALSE;
	172	}
	173
	174	AliITSIntMapNode* AliITSIntMap::FindMinNode(AliITSIntMapNode* node) const {
	175	// returns the node with smallest key in the sub tree starting from node
	176	if (node==NULL) return NULL;
	177	else if (node->Left()==NULL) return node;
	178	else return FindMinNode(node->Left());
	179	}
	180
	181	AliITSIntMapNode* AliITSIntMap::FindMaxNode(AliITSIntMapNode* node) const {
	182	// returns the node with largest key in the sub tree starting from node
	183	if (node==NULL) return NULL;
	184	else if (node->Right()==NULL) return node;
	185	else return FindMaxNode(node->Right());
b15de2d2	186	}
	187
	188	AliITSIntMapNode* AliITSIntMap::Find(Int_t key) const {
	189	// finds a node and returns it (returns NULL if not found)
53ae21ce	190	return FindNode(key,fRoot,0);
	191	}
	192
	193	AliITSIntMapNode* AliITSIntMap::FindNode(Int_t key, AliITSIntMapNode* node, UInt_t height) const {
	194	// method to find a node in the tree (used recursively)
	195	if (node==NULL) return NULL;
	196	height++;
	197	if (key<node->Key()) return FindNode(key,node->Left(),height);
	198	else if (key>node->Key()) return FindNode(key,node->Right(),height);
	199	else { // Match
	200	// //* balance if height too high. const above have to be removed if this is needed *
52da6fa6	201	// UInt_t balanceHeight = (UInt_t) (TMath::Log(fNrEntries+1)/TMath::Log(2)+1);
53ae21ce	202	// if ( (height-balanceHeight)*(height-balanceHeight) > fNrEntries ) {
	203	// Balance();
	204	// }
	205	return node;
	206	}
	207	}
	208
	209	Int_t AliITSIntMap::GetVal(Int_t key) const {
	210	// returns the value for the node with key
	211	AliITSIntMapNode* node = Find(key);
	212	if (node!=NULL) {
	213	return node->Val();
	214	}
	215	else {
	216	Warning("AliITSIntMap::GetVal","Node with key %d not found in map. Returning -999.",key);
	217	return -999;
	218	}
	219	}
	220
	221	void AliITSIntMap::Balance() {
	222	// method to balance the tree
	223	// printf("balance H=%d --> ",GetTreeHeight());
	224	if (fNrEntries==0) return;
	225	if (!fFastAccess) InitFastAccess();
	226	fRoot = BalanceNode(0,fNrEntries-1);
	227	// printf("H=%d\n",GetTreeHeight());
	228	}
	229
	230	AliITSIntMapNode* AliITSIntMap::BalanceNode(Int_t lowInd, Int_t highInd) {
	231	// balances the tree by selecting the center of an index range
	232	// (used recursively)
	233	if (lowInd>highInd) return NULL;
	234	Int_t thisInd = lowInd+(highInd-lowInd)/2;
	235	fFastAccessArray[thisInd]->Left() = BalanceNode(lowInd,thisInd-1);
	236	fFastAccessArray[thisInd]->Right() = BalanceNode(thisInd+1,highInd);
	237	return fFastAccessArray[thisInd];
	238	}
	239
	240	void AliITSIntMap::ClearFastAccess(){
	241	// clears the fast access array of pointers
	242	if (fFastAccessArray!=NULL) {
	243	delete [] fFastAccessArray;
	244	fFastAccessArray=NULL;
	245	}
	246	fFastAccess=kFALSE;
	247	fFastAccessSerialize=kFALSE;
	248	}
	249
	250	void AliITSIntMap::InitFastAccess(){
	251	// initializes the fast access array
6727e2db	252	if (fFastAccess) return;
53ae21ce	253	ClearFastAccess();
b15de2d2	254	if (fNrEntries>0) {
53ae21ce	255	fFastAccessArray = new AliITSIntMapNode*[fNrEntries];
	256	fDummyIndex=0;
	257	InitFastAccessNode(fRoot);
	258	fFastAccess=kTRUE;
	259	}
	260	}
	261
	262	void AliITSIntMap::InitFastAccessNode(AliITSIntMapNode* node) {
	263	// initializes the fast access array starting from node (used recursively)
	264	if (node==NULL) return;
	265	InitFastAccessNode(node->Left());
	266	fFastAccessArray[fDummyIndex++] = node;
	267	InitFastAccessNode(node->Right());
	268	}
	269
	270	void AliITSIntMap::InitFastAccessSerialize(){
	271	// initializes the fast access array
6727e2db	272	if (fFastAccessSerialize) return;
53ae21ce	273	ClearFastAccess();
	274	if (fNrEntries>0) {
	275	fFastAccessArray = new AliITSIntMapNode*[fNrEntries];
	276	fDummyIndex=0;
	277	InitFastAccessSerializeNode(fRoot);
	278	fFastAccessSerialize=kTRUE;
b15de2d2	279	}
b15de2d2	280	}
b15de2d2	281
53ae21ce	282	void AliITSIntMap::InitFastAccessSerializeNode(AliITSIntMapNode* node) {
	283	// initializes the fast access array for tree ordering starting from node (used recursively)
	284	if (node==NULL) return;
	285	fFastAccessArray[fDummyIndex++] = node;
	286	InitFastAccessSerializeNode(node->Left());
	287	InitFastAccessSerializeNode(node->Right());
	288	}
	289
	290	Int_t AliITSIntMap::GetKeyIndex(UInt_t index) {
b15de2d2	291	// returns the key of the node at position 'index' in the map
b15de2d2	292	// returns -1 if out of bounds
53ae21ce	293	if (index<fNrEntries) {
	294	if (!fFastAccess && !fFastAccessSerialize) InitFastAccess();
	295	return fFastAccessArray[index]->Key();
b15de2d2	296	}
53ae21ce	297	return -1;
b15de2d2	298	}
b15de2d2	299
53ae21ce	300	Int_t AliITSIntMap::GetValIndex(UInt_t index) {
b15de2d2	301	// returns the value of the node at position 'index' in the map
b15de2d2	302	// returns -1 if out of bounds
53ae21ce	303	if (index<fNrEntries) {
	304	if (!fFastAccess && !fFastAccessSerialize) InitFastAccess();
	305	return fFastAccessArray[index]->Val();
	306	}
	307	return -1;
	308	}
	309
	310	AliITSIntMapNode* AliITSIntMap::FindNodeIndex(UInt_t index, AliITSIntMapNode* node) const {
	311	// method to find the index:th node in the tree (used recursively)
	312	// this method should not be needed anymore, since GetKeyIndex/GetValIndex is faster
	313	static UInt_t fTmpInd;
	314	if (node==fRoot) fTmpInd=0;
	315	if (node->Left()!=NULL) {
	316	AliITSIntMapNode* tmpResult = FindNodeIndex(index,node->Left());
	317	if (tmpResult != NULL) {
	318	return tmpResult;
b15de2d2	319	}
b15de2d2	320	}
53ae21ce	321	if (fTmpInd==index) return node;
	322	fTmpInd++;
	323	if (node->Right()!=NULL) {
	324	AliITSIntMapNode* tmpResult = FindNodeIndex(index,node->Right());
	325	if (tmpResult != NULL) {
	326	return tmpResult;
	327	}
b15de2d2	328	}
53ae21ce	329	return NULL;
b15de2d2	330	}
	331
	332	void AliITSIntMap::PrintEntries() const {
	333	// prints all the entries (key,value pairs) of the map
	334	printf("* Map Entries: (key , value)*\n");
53ae21ce	335	PrintNode(fRoot);
b15de2d2	336	printf("*********************************\n");
b15de2d2	337	}
53ae21ce	338
	339	void AliITSIntMap::PrintNode(AliITSIntMapNode* node) const {
	340	// method to print node entry (key,value) (used recursively)
	341	if (node==NULL) return;
	342	if (node->Left()!=NULL) PrintNode(node->Left());
	343	printf("%d , %d\n",node->Key(),node->Val());
	344	if (node->Right()!=NULL) PrintNode(node->Right());
	345	}
	346
	347	UInt_t AliITSIntMap::GetTreeHeight() const {
	348	// returns the height of the tree
	349	return GetTreeHeightNode(fRoot);
	350	}
	351
	352	UInt_t AliITSIntMap::GetTreeHeightNode(AliITSIntMapNode* node) const {
	353	// returns tree height for the sub tree starting from node (used recursively)
	354	if (node==NULL) return 0;
	355	UInt_t leftH = GetTreeHeightNode(node->Left());
	356	UInt_t rightH = GetTreeHeightNode(node->Right());
	357	if (leftH>=rightH) return leftH+1;
	358	else return rightH+1;
	359	}