Quick Links: ROOT Homepage Class Index Class Hierarchy

Source: header file source file inheritance tree (.pdf)

Sections: class description function members data members class charts

class AliITSIntMap

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

Function Members (Methods)

public:

	AliITSIntMap()
	AliITSIntMap(const AliITSIntMap& imap)
	AliITSIntMap(AliITSIntMapNode* root, UInt_t nrEntries)
virtual	~AliITSIntMap()
void	Balance()
void	Clear()
AliITSIntMap*	Clone() const
AliITSIntMapNode*	Find(Int_t key) const
Int_t	GetKeyIndex(UInt_t index)
UInt_t	GetNrEntries() const
UInt_t	GetTreeHeight() const
Int_t	GetVal(Int_t key) const
Int_t	GetValIndex(UInt_t index)
Bool_t	Insert(Int_t key, Int_t val)
AliITSIntMap&	operator=(const AliITSIntMap& imap)
Bool_t	Pop(Int_t& key, Int_t& val)
void	PrepareSerialize()
void	PrepareSerializeOrdered()
void	PrintEntries() const
Bool_t	Remove(Int_t key)

private:

AliITSIntMapNode*	BalanceNode(Int_t lowInd, Int_t highInd)
void	ClearFastAccess()
void	ClearNode(AliITSIntMapNode*& node)
AliITSIntMapNode*	CloneNode(AliITSIntMapNode* node) const
AliITSIntMapNode*	FindMaxNode(AliITSIntMapNode* node) const
AliITSIntMapNode*	FindMinNode(AliITSIntMapNode* node) const
AliITSIntMapNode*	FindNode(Int_t key, AliITSIntMapNode* node, UInt_t height) const
AliITSIntMapNode*	FindNodeIndex(UInt_t index, AliITSIntMapNode* node) const
UInt_t	GetTreeHeightNode(AliITSIntMapNode* node) const
void	InitFastAccess()
void	InitFastAccessNode(AliITSIntMapNode* node)
void	InitFastAccessSerialize()
void	InitFastAccessSerializeNode(AliITSIntMapNode* node)
void	InsertNode(Int_t key, Int_t val, AliITSIntMapNode*& node, UInt_t height)
void	PrintNode(AliITSIntMapNode* node) const
void	RemoveNode(Int_t key, AliITSIntMapNode*& node)

Data Members

private:

UInt_t	fDummyIndex	dummy index used when traversing tree
Bool_t	fFastAccess	is fast access array initialized (key ordered)?
AliITSIntMapNode**	fFastAccessArray	array of pointers to nodes
Bool_t	fFastAccessSerialize	is fast access array initialized (tree ordered)?
UInt_t	fNrEntries	nr of entries in map
AliITSIntMapNode*	fRoot	link to first node of tree

Class Charts

Inheritance Chart:

AliITSIntMap

Function documentation

AliITSIntMap()

{}

AliITSIntMap(AliITSIntMapNode* root, UInt_t nrEntries)

{}

AliITSIntMap(const AliITSIntMap& imap)

 copy constructor

~AliITSIntMap()

AliITSIntMap& operator=(const AliITSIntMap& imap)

 assignment operator

void Clear()

 clear the whole map

void ClearNode(AliITSIntMapNode*& node)

 clear this node and all children nodes

AliITSIntMap* Clone() const

 returns a clone of the map

AliITSIntMapNode* CloneNode(AliITSIntMapNode* node) const

Bool_t Insert(Int_t key, Int_t val)

 insert a new node into the map (returns true if the node was not present before)

void InsertNode(Int_t key, Int_t val, AliITSIntMapNode*& node, UInt_t height)

 method to insert a node in the tree (used recursively)

Bool_t Remove(Int_t key)

 remove a node from the map (returns true if the node was found)

void RemoveNode(Int_t key, AliITSIntMapNode*& node)

 method to remove a node in the tree (used recursively)

Bool_t Pop(Int_t& key, Int_t& val)

 removes one entry (root) from tree, giving its key,val pair

AliITSIntMapNode* FindMinNode(AliITSIntMapNode* node) const

 returns the node with smallest key in the sub tree starting from node

AliITSIntMapNode* FindMaxNode(AliITSIntMapNode* node) const

 returns the node with largest key in the sub tree starting from node

AliITSIntMapNode* Find(Int_t key) const

 finds a node and returns it (returns NULL if not found)

AliITSIntMapNode* FindNode(Int_t key, AliITSIntMapNode* node, UInt_t height) const

 method to find a node in the tree (used recursively)

Int_t GetVal(Int_t key) const

 returns the value for the node with key

void Balance()

 method to balance the tree
  printf("balance H=%d --> ",GetTreeHeight());

AliITSIntMapNode* BalanceNode(Int_t lowInd, Int_t highInd)

 balances the tree by selecting the center of an index range
 (used recursively)

void ClearFastAccess()

 clears the fast access array of pointers

void InitFastAccess()

 initializes the fast access array

void InitFastAccessNode(AliITSIntMapNode* node)

 initializes the fast access array starting from node (used recursively)

void InitFastAccessSerialize()

 initializes the fast access array

void InitFastAccessSerializeNode(AliITSIntMapNode* node)

 initializes the fast access array for tree ordering starting from node (used recursively)

Int_t GetKeyIndex(UInt_t index)

 returns the key of the node at position 'index' in the map
 returns -1 if out of bounds

Int_t GetValIndex(UInt_t index)

 returns the value of the node at position 'index' in the map
 returns -1 if out of bounds

AliITSIntMapNode* 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

void PrintEntries() const

 prints all the entries (key,value pairs) of the map

void PrintNode(AliITSIntMapNode* node) const

 method to print node entry (key,value) (used recursively)

UInt_t GetTreeHeight() const

 returns the height of the tree

UInt_t GetTreeHeightNode(AliITSIntMapNode* node) const

 returns tree height for the sub tree starting from node (used recursively)

UInt_t GetNrEntries() const

{return fNrEntries;}

void PrepareSerialize()

{InitFastAccessSerialize();}

void PrepareSerializeOrdered()

{InitFastAccess();}