[u/mrichter/AliRoot.git] / RAW / AliTPCHuffman.cxx

/**************************************************************************
 * Copyright(c) 1998-2003, ALICE Experiment at CERN, All rights reserved. *
 *                                                                        *
 * Author: The ALICE Off-line Project.                                    *
 * Contributors are mentioned in the code where appropriate.              *
 *                                                                        *
 * Permission to use, copy, modify and distribute this software and its   *
 * documentation strictly for non-commercial purposes is hereby granted   *
 * without fee, provided that the above copyright notice appears in all   *
 * copies and that both the copyright notice and this permission notice   *
 * appear in the supporting documentation. The authors make no claims     *
 * about the suitability of this software for any purpose. It is          *
 * provided "as is" without express or implied warranty.                  *
 **************************************************************************/
/* $Id:*/
////////////////////////////////////////////////
//  Huffman classes for set:TPC               //
////////////////////////////////////////////////
//This file contains two classes and it implements 
//the Huffman algorithm for creating tables
//used in the compression phase.
//The class AliTPCHNode represents a node of the Huffman tree, while
//the class AliTPCHTable represents a compression table

#include <TObjArray.h>
#include <Riostream.h>
#include <TMath.h>
#include "AliTPCBuffer160.h"
#include "AliTPCHuffman.h"

ClassImp(AliTPCHNode)

AliTPCHNode::AliTPCHNode(){
  //Constructor
  fLeft=0;
  fRight=0;
}

//////////////////////////////////////////////////////////////////////////////

AliTPCHNode::AliTPCHNode(Int_t sym, Double_t freq){
  //Standard constructor
  fSymbol=sym;
  fFrequency=freq;
  fLeft=0;
  fRight=0;
}

//////////////////////////////////////////////////////////////////////////////

AliTPCHNode::AliTPCHNode(const AliTPCHNode &source)
  :TObject(source){
  //Copy Constructor 
  if(&source == this) return;
  this->fSymbol = source.fSymbol;
  this->fFrequency = source.fFrequency;
  this->fLeft = source.fLeft;
  this->fRight = source.fRight;
  return;
}

//////////////////////////////////////////////////////////////////////////////

AliTPCHNode& AliTPCHNode::operator=(const AliTPCHNode &source){
  //Assignment operator
  if(&source == this) return *this;
  this->fSymbol = source.fSymbol;
  this->fFrequency = source.fFrequency;
  this->fLeft = source.fLeft;
  this->fRight = source.fRight;
  return *this;
}

//////////////////////////////////////////////////////////////////////////////

Int_t AliTPCHNode::Compare(const TObject *obj)const{
  //Function called by Sort method of TObjArray
  AliTPCHNode *node=(AliTPCHNode *)obj;
  Double_t f=fFrequency;
  Double_t fo=node->fFrequency;
  if (f<fo) return 1;
  else if (f>fo) return -1;
  else return 0;
}

//////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////

ClassImp(AliTPCHTable)
  
AliTPCHTable::AliTPCHTable(){
  //Constructor
  fCodeLen=0;
  fCode=0;
  fHNodes=0;
  fNnodes=0;
  fNum=0;
  fVerbose=0;
}

//////////////////////////////////////////////////////////////////////////////

AliTPCHTable::AliTPCHTable(Int_t size){
  //Initialization
  fSize=size;
  fCodeLen = new UChar_t[fSize]; 
  fCode = new Double_t[fSize]; 
  fHNodes = new TObjArray;
  fNnodes=0;
  fNum=0;
  fVerbose=0;
  fSym= new Short_t[fSize];
  for (Short_t i=0;i<fSize;i++) {
    fSym[i]=i;
  }//end for
  ClearTable(); 
}

//////////////////////////////////////////////////////////////////////////////

AliTPCHTable::AliTPCHTable(const AliTPCHTable &source)
  :TObject(source){
  //Copy Constructor 
  if(&source == this) return;
  this->fSize = source.fSize;
  this->fCodeLen = source.fCodeLen;
  this->fCode = source.fCode;
  this->fSym = source.fSym;
  this->fHNodes = source.fHNodes;
  this->fNnodes = source.fNnodes;
  this->fNum=source.fNum;
  this->fVerbose=source.fVerbose;
  return;
}

//////////////////////////////////////////////////////////////////////////////

AliTPCHTable& AliTPCHTable::operator=(const AliTPCHTable &source) {
  //Assignment operator
  if(&source == this) return *this;
  this->fSize = source.fSize;
  this->fCodeLen = source.fCodeLen;
  this->fCode = source.fCode;
  this->fSym = source.fSym;
  this->fHNodes = source.fHNodes;
  this->fNnodes = source.fNnodes;
  this->fNum=source.fNum;
  this->fVerbose=source.fVerbose;
  return *this;
}

//////////////////////////////////////////////////////////////////////////////

AliTPCHTable::~AliTPCHTable(){
  //HTable destructor
  if(fVerbose)
    cout<<"HTable destructor !\n";
  if (fCodeLen) delete[] fCodeLen;
  if (fCode) delete [] fCode;
  if (fHNodes) {
    fHNodes->Delete(); //Clear out the collection and deletes the removed objects
    delete fHNodes;
  }//end if
}

//////////////////////////////////////////////////////////////////////////////

void AliTPCHTable::SetCodeLen(UChar_t len,Int_t val){
  //Sets codelength of "val" to the variable "len"
  fCodeLen[val]=len;
  return;
}

//////////////////////////////////////////////////////////////////////////////

void AliTPCHTable::SetCode(Double_t code,Int_t val){
  //Sets the binary code of the variable "val"
  fCode[val]=code;
  return;
}

//////////////////////////////////////////////////////////////////////////////

void AliTPCHTable::PrintTable()const{
  //This method prints a table
  cout<<"Table for Huffman coding\n";
  cout<<"  Symbol|   Code   |   Length \n";
  for (Int_t i=0;i<fSize;i++){
    if (fCodeLen[i]){
      cout.width(6);cout<<fSym[i];
      cout.width(3);cout<<"|";
      cout.width(6);cout<<hex<<(UInt_t)fCode[i]<<dec;
      cout.width(5);cout<<"|";
      cout.width(6);cout<<(UInt_t)fCodeLen[i]<<endl;  
    }//end if
  }//end for
}

//////////////////////////////////////////////////////////////////////////////

Bool_t AliTPCHTable::SpanTree(AliTPCHNode *start, UInt_t code, UChar_t len){
  //Hoffman codes are generated spanning the Huffman tree
  //In an Huffman tree any internal node has always two children
  AliTPCHNode * visited;
  visited = start;
  Int_t idx=visited->GetSymbol();
  if (!visited->GetLeft()) {
    fCode[idx] = code; 
    fCodeLen[idx] = len;
    return kTRUE;
  }//end if
  SpanTree(visited->GetLeft(), code << 1, len + 1);
  SpanTree(visited->GetRight(), code << 1 | 0x0001, len + 1);
  return kTRUE;
}

//////////////////////////////////////////////////////////////////////////////

void AliTPCHTable::ResetHNodes(){
  //Reset number of HNodes and the HNodes array 
  if (fHNodes)  fHNodes->Clear();
  if (fNnodes)  fNnodes=0;
}

//////////////////////////////////////////////////////////////////////////////

void AliTPCHTable::ClearTable(){
  //Clear the table
  memset(fCodeLen,0,sizeof(UChar_t)*fSize);
  memset(fCode,0,sizeof(Double_t)*fSize);
}

//////////////////////////////////////////////////////////////////////////////

Int_t  AliTPCHTable::GetFrequencies(const char *fname){
  //It fills the "fCode" array with the frequencies of the symbols read from the file
  AliTPCBuffer160 buff(fname,0);
  UInt_t numberOfWords=0;
  Int_t val;
  while((val=buff.GetNext())!=-1){
    fCode[val]++;
    fNum++;
    numberOfWords++;
  }
  cout<<"Total number of words: "<<numberOfWords<<endl;
  //Print out the frequencies 
  /*
    for (Int_t i=0;i<fSize;i++){
    if (fCode[i])cout<<"Symbol: "<<i<<" Freq: "<<fCode[i]<<endl;
    }
    cout<<endl;
  */
  return 0;
}

Int_t AliTPCHTable::SetValFrequency(Int_t Val,Double_t Value){
  //This method sets to "Value" the frequency of the symbol "Val"
  fCode[Val]=Value;
  fNum=1;
  return 0;
}

//////////////////////////////////////////////////////////////////////////////

Int_t AliTPCHTable::SetFrequency(Int_t Val){
  //It increments by one the frequency of the symbol "Val" whose frequency is 
  //stored in the fCode array
  fCode[Val]++;
  fNum++;
  return 0;
}

//////////////////////////////////////////////////////////////////////////////

Int_t AliTPCHTable::NormalizeFrequencies(){
  //This method normalized the frequencies
  //Frequencies normalization
  Double_t sum=0.;
  for (Int_t i=0; i< fSize; i++) {
    sum+=fCode[i];
  }//end for 
  if (fVerbose){
    cout<<"Frequency sum: "<<sum<<endl;
  }//end if
  if(sum!=0.){
    for (Int_t i=0; i< fSize; i++) {
      fCode[i]/=sum;
      if ((fCode[i]!=0.) && (fCode[i]<10e-20))cout<<"Frequency value very small !!! "<<fCode[i]<<endl;
    }//end for 
  }
  return 0;
}
//////////////////////////////////////////////////////////////////////////////
Int_t AliTPCHTable::StoreFrequencies(const char *fname)const{
  //It stores the frequencies in a text file
  ofstream ftxt(fname);  
  for (Int_t i=0;i<fSize;i++){
    ftxt<<fCode[i]<<endl;
  }
  ftxt.close();
  return 0;
}

//////////////////////////////////////////////////////////////////////////////

void AliTPCHTable::CompleteTable(Int_t k){
  //According to the kind of table (0..4) it associates a dummy frequency (1) to 
  //every symbols whose real frequency is zero, in a given range 0..max
  Int_t max;
  UInt_t val;
  switch(k){
  case 0:
    max=fSize;
    val=1;
    break;
  case 1:
    max=445;
    val=1;
    break;
  default:
    max=fSize;
    val=1;
    break;
  }//end switch

  for(Int_t i=0;i<max;i++){
    if(fCode[i]==0.0)fCode[i]=val;
  }
  return;
}

//////////////////////////////////////////////////////////////////////////////

Double_t  AliTPCHTable::GetEntropy()const{
  //This method calculates the value of the entropy 
  Double_t entropy=0;
  Double_t prob=0;
  for (Int_t i=0;i<fSize;i++){
    if (fCode[i]){
      prob=fCode[i]/(Double_t)fNum;
      entropy+=prob*(TMath::Log2(prob));
    }
  }
  return -entropy;
}

//////////////////////////////////////////////////////////////////////////////

Int_t AliTPCHTable::BuildHTable(){
  //It builds a Huffman tree 
  if(GetWordsNumber()){
    for (Int_t i=0; i< fSize; i++) {
      if (fCode[i] > 0.){
	fNnodes++;
	//cout<< "Symbol:"<<i<<" Freq:"<<fCode[i]<<endl;
	fHNodes->Add(new AliTPCHNode(i,fCode[i]));
      }//end if
    }//end for
    Int_t nentries=fHNodes->GetEntriesFast();  
    //cout<<"Number of symbols: "<<nentries<<endl;
    Int_t nindex=nentries-1;  
    while (nindex > 0){
      fHNodes->Sort(nindex+1);
      AliTPCHNode *aux = new AliTPCHNode(0,0);
      AliTPCHNode *node= (AliTPCHNode*)fHNodes->UncheckedAt(nindex-1);
      AliTPCHNode *node1= (AliTPCHNode*)fHNodes->UncheckedAt(nindex);
      
      aux->SetLeft(node);
      aux->SetRight(node1);
      aux->SetFrequency(node->GetFrequency() + node1->GetFrequency());
      fHNodes->RemoveAt(nindex-1);
      fHNodes->AddAt(aux,nindex-1);
      nindex--;
    }//end while
    ClearTable();  
    AliTPCHNode *start= (AliTPCHNode*)fHNodes->UncheckedAt(0);
    SpanTree(start,0,0);
  }//end if
  else{
    cout<<"Table contains 0 elements\n";
  }//end else
  return 0;
}
//////////////////////////////////////////////////////////////////////////////
Commit	Line	Data
2e9f335b	1	/**************************************************************************
	2	* Copyright(c) 1998-2003, ALICE Experiment at CERN, All rights reserved. *
	3	* *
	4	* Author: The ALICE Off-line Project. *
	5	* Contributors are mentioned in the code where appropriate. *
	6	* *
	7	* Permission to use, copy, modify and distribute this software and its *
	8	* documentation strictly for non-commercial purposes is hereby granted *
	9	* without fee, provided that the above copyright notice appears in all *
	10	* copies and that both the copyright notice and this permission notice *
	11	* appear in the supporting documentation. The authors make no claims *
	12	* about the suitability of this software for any purpose. It is *
	13	* provided "as is" without express or implied warranty. *
	14	**************************************************************************/
a79660fb	15	/* $Id:*/
2e9f335b	16	////////////////////////////////////////////////
	17	// Huffman classes for set:TPC //
	18	////////////////////////////////////////////////
a79660fb	19	//This file contains two classes and it implements
	20	//the Huffman algorithm for creating tables
	21	//used in the compression phase.
	22	//The class AliTPCHNode represents a node of the Huffman tree, while
	23	//the class AliTPCHTable represents a compression table
	24
2e9f335b	25	#include <TObjArray.h>
b62e2a95	26	#include <Riostream.h>
b62e2a95	27	#include <TMath.h>
2e9f335b	28	#include "AliTPCBuffer160.h"
b62e2a95	29	#include "AliTPCHuffman.h"
2e9f335b	30
	31	ClassImp(AliTPCHNode)
	32
	33	AliTPCHNode::AliTPCHNode(){
a79660fb	34	//Constructor
2e9f335b	35	fLeft=0;
	36	fRight=0;
	37	}
	38
	39	//////////////////////////////////////////////////////////////////////////////
	40
	41	AliTPCHNode::AliTPCHNode(Int_t sym, Double_t freq){
a79660fb	42	//Standard constructor
2e9f335b	43	fSymbol=sym;
	44	fFrequency=freq;
	45	fLeft=0;
	46	fRight=0;
	47	}
	48
	49	//////////////////////////////////////////////////////////////////////////////
	50
b66321bb	51	AliTPCHNode::AliTPCHNode(const AliTPCHNode &source)
b66321bb	52	:TObject(source){
a79660fb	53	//Copy Constructor
2e9f335b	54	if(&source == this) return;
	55	this->fSymbol = source.fSymbol;
	56	this->fFrequency = source.fFrequency;
	57	this->fLeft = source.fLeft;
	58	this->fRight = source.fRight;
	59	return;
	60	}
	61
	62	//////////////////////////////////////////////////////////////////////////////
	63
	64	AliTPCHNode& AliTPCHNode::operator=(const AliTPCHNode &source){
a79660fb	65	//Assignment operator
2e9f335b	66	if(&source == this) return *this;
	67	this->fSymbol = source.fSymbol;
	68	this->fFrequency = source.fFrequency;
	69	this->fLeft = source.fLeft;
	70	this->fRight = source.fRight;
	71	return *this;
	72	}
	73
	74	//////////////////////////////////////////////////////////////////////////////
	75
	76	Int_t AliTPCHNode::Compare(const TObject *obj)const{
a79660fb	77	//Function called by Sort method of TObjArray
2e9f335b	78	AliTPCHNode node=(AliTPCHNode )obj;
	79	Double_t f=fFrequency;
	80	Double_t fo=node->fFrequency;
	81	if (f<fo) return 1;
	82	else if (f>fo) return -1;
	83	else return 0;
	84	}
	85
	86	//////////////////////////////////////////////////////////////////////////////
	87	//////////////////////////////////////////////////////////////////////////////
	88	//////////////////////////////////////////////////////////////////////////////
	89
	90	ClassImp(AliTPCHTable)
	91
	92	AliTPCHTable::AliTPCHTable(){
a79660fb	93	//Constructor
2e9f335b	94	fCodeLen=0;
	95	fCode=0;
	96	fHNodes=0;
	97	fNnodes=0;
	98	fNum=0;
	99	fVerbose=0;
	100	}
	101
	102	//////////////////////////////////////////////////////////////////////////////
	103
	104	AliTPCHTable::AliTPCHTable(Int_t size){
a79660fb	105	//Initialization
2e9f335b	106	fSize=size;
	107	fCodeLen = new UChar_t[fSize];
	108	fCode = new Double_t[fSize];
	109	fHNodes = new TObjArray;
	110	fNnodes=0;
	111	fNum=0;
	112	fVerbose=0;
	113	fSym= new Short_t[fSize];
	114	for (Short_t i=0;i<fSize;i++) {
	115	fSym[i]=i;
	116	}//end for
	117	ClearTable();
	118	}
	119
	120	//////////////////////////////////////////////////////////////////////////////
	121
b66321bb	122	AliTPCHTable::AliTPCHTable(const AliTPCHTable &source)
b66321bb	123	:TObject(source){
a79660fb	124	//Copy Constructor
2e9f335b	125	if(&source == this) return;
	126	this->fSize = source.fSize;
	127	this->fCodeLen = source.fCodeLen;
	128	this->fCode = source.fCode;
	129	this->fSym = source.fSym;
	130	this->fHNodes = source.fHNodes;
	131	this->fNnodes = source.fNnodes;
	132	this->fNum=source.fNum;
	133	this->fVerbose=source.fVerbose;
	134	return;
	135	}
	136
	137	//////////////////////////////////////////////////////////////////////////////
	138
	139	AliTPCHTable& AliTPCHTable::operator=(const AliTPCHTable &source) {
a79660fb	140	//Assignment operator
2e9f335b	141	if(&source == this) return *this;
	142	this->fSize = source.fSize;
	143	this->fCodeLen = source.fCodeLen;
	144	this->fCode = source.fCode;
	145	this->fSym = source.fSym;
	146	this->fHNodes = source.fHNodes;
	147	this->fNnodes = source.fNnodes;
	148	this->fNum=source.fNum;
	149	this->fVerbose=source.fVerbose;
	150	return *this;
	151	}
	152
	153	//////////////////////////////////////////////////////////////////////////////
	154
	155	AliTPCHTable::~AliTPCHTable(){
a79660fb	156	//HTable destructor
2e9f335b	157	if(fVerbose)
	158	cout<<"HTable destructor !\n";
	159	if (fCodeLen) delete[] fCodeLen;
	160	if (fCode) delete [] fCode;
	161	if (fHNodes) {
	162	fHNodes->Delete(); //Clear out the collection and deletes the removed objects
	163	delete fHNodes;
	164	}//end if
	165	}
	166
	167	//////////////////////////////////////////////////////////////////////////////
	168
	169	void AliTPCHTable::SetCodeLen(UChar_t len,Int_t val){
a79660fb	170	//Sets codelength of "val" to the variable "len"
2e9f335b	171	fCodeLen[val]=len;
	172	return;
	173	}
	174
	175	//////////////////////////////////////////////////////////////////////////////
	176
	177	void AliTPCHTable::SetCode(Double_t code,Int_t val){
a79660fb	178	//Sets the binary code of the variable "val"
2e9f335b	179	fCode[val]=code;
	180	return;
	181	}
	182
	183	//////////////////////////////////////////////////////////////////////////////
	184
	185	void AliTPCHTable::PrintTable()const{
a79660fb	186	//This method prints a table
2e9f335b	187	cout<<"Table for Huffman coding\n";
	188	cout<<" Symbol\| Code \| Length \n";
	189	for (Int_t i=0;i<fSize;i++){
	190	if (fCodeLen[i]){
	191	cout.width(6);cout<<fSym[i];
	192	cout.width(3);cout<<"\|";
0b3c7dfc	193	cout.width(6);cout<<hex<<(UInt_t)fCode[i]<<dec;
2e9f335b	194	cout.width(5);cout<<"\|";
0b3c7dfc	195	cout.width(6);cout<<(UInt_t)fCodeLen[i]<<endl;
2e9f335b	196	}//end if
	197	}//end for
	198	}
	199
	200	//////////////////////////////////////////////////////////////////////////////
	201
0b3c7dfc	202	Bool_t AliTPCHTable::SpanTree(AliTPCHNode *start, UInt_t code, UChar_t len){
a79660fb	203	//Hoffman codes are generated spanning the Huffman tree
2e9f335b	204	//In an Huffman tree any internal node has always two children
	205	AliTPCHNode * visited;
	206	visited = start;
	207	Int_t idx=visited->GetSymbol();
	208	if (!visited->GetLeft()) {
	209	fCode[idx] = code;
	210	fCodeLen[idx] = len;
	211	return kTRUE;
	212	}//end if
	213	SpanTree(visited->GetLeft(), code << 1, len + 1);
	214	SpanTree(visited->GetRight(), code << 1 \| 0x0001, len + 1);
	215	return kTRUE;
	216	}
	217
	218	//////////////////////////////////////////////////////////////////////////////
	219
	220	void AliTPCHTable::ResetHNodes(){
a79660fb	221	//Reset number of HNodes and the HNodes array
2e9f335b	222	if (fHNodes) fHNodes->Clear();
	223	if (fNnodes) fNnodes=0;
	224	}
	225
	226	//////////////////////////////////////////////////////////////////////////////
	227
	228	void AliTPCHTable::ClearTable(){
a79660fb	229	//Clear the table
2e9f335b	230	memset(fCodeLen,0,sizeof(UChar_t)*fSize);
	231	memset(fCode,0,sizeof(Double_t)*fSize);
	232	}
	233
	234	//////////////////////////////////////////////////////////////////////////////
	235
	236	Int_t AliTPCHTable::GetFrequencies(const char *fname){
a79660fb	237	//It fills the "fCode" array with the frequencies of the symbols read from the file
2e9f335b	238	AliTPCBuffer160 buff(fname,0);
0b3c7dfc	239	UInt_t numberOfWords=0;
a79660fb	240	Int_t val;
	241	while((val=buff.GetNext())!=-1){
	242	fCode[val]++;
2e9f335b	243	fNum++;
a79660fb	244	numberOfWords++;
2e9f335b	245	}
a79660fb	246	cout<<"Total number of words: "<<numberOfWords<<endl;
2e9f335b	247	//Print out the frequencies
	248	/*
	249	for (Int_t i=0;i<fSize;i++){
	250	if (fCode[i])cout<<"Symbol: "<<i<<" Freq: "<<fCode[i]<<endl;
	251	}
	252	cout<<endl;
	253	*/
	254	return 0;
	255	}
	256
09f6432c	257	Int_t AliTPCHTable::SetValFrequency(Int_t Val,Double_t Value){
a79660fb	258	//This method sets to "Value" the frequency of the symbol "Val"
2e9f335b	259	fCode[Val]=Value;
	260	fNum=1;
	261	return 0;
	262	}
	263
	264	//////////////////////////////////////////////////////////////////////////////
	265
09f6432c	266	Int_t AliTPCHTable::SetFrequency(Int_t Val){
a79660fb	267	//It increments by one the frequency of the symbol "Val" whose frequency is
a79660fb	268	//stored in the fCode array
2e9f335b	269	fCode[Val]++;
	270	fNum++;
	271	return 0;
	272	}
	273
	274	//////////////////////////////////////////////////////////////////////////////
	275
9f992f70	276	Int_t AliTPCHTable::NormalizeFrequencies(){
	277	//This method normalized the frequencies
	278	//Frequencies normalization
	279	Double_t sum=0.;
	280	for (Int_t i=0; i< fSize; i++) {
	281	sum+=fCode[i];
	282	}//end for
	283	if (fVerbose){
	284	cout<<"Frequency sum: "<<sum<<endl;
	285	}//end if
	286	if(sum!=0.){
	287	for (Int_t i=0; i< fSize; i++) {
	288	fCode[i]/=sum;
	289	if ((fCode[i]!=0.) && (fCode[i]<10e-20))cout<<"Frequency value very small !!! "<<fCode[i]<<endl;
	290	}//end for
	291	}
	292	return 0;
	293	}
	294	//////////////////////////////////////////////////////////////////////////////
a79660fb	295	Int_t AliTPCHTable::StoreFrequencies(const char *fname)const{
a79660fb	296	//It stores the frequencies in a text file
2e9f335b	297	ofstream ftxt(fname);
2e9f335b	298	for (Int_t i=0;i<fSize;i++){
9f992f70	299	ftxt<<fCode[i]<<endl;
2e9f335b	300	}
	301	ftxt.close();
	302	return 0;
	303	}
	304
	305	//////////////////////////////////////////////////////////////////////////////
	306
	307	void AliTPCHTable::CompleteTable(Int_t k){
a79660fb	308	//According to the kind of table (0..4) it associates a dummy frequency (1) to
a79660fb	309	//every symbols whose real frequency is zero, in a given range 0..max
2e9f335b	310	Int_t max;
0b3c7dfc	311	UInt_t val;
2e9f335b	312	switch(k){
2e9f335b	313	case 0:
c9bd9d3d	314	max=fSize;
2e9f335b	315	val=1;
	316	break;
	317	case 1:
	318	max=445;
	319	val=1;
	320	break;
	321	default:
	322	max=fSize;
	323	val=1;
	324	break;
	325	}//end switch
	326
	327	for(Int_t i=0;i<max;i++){
	328	if(fCode[i]==0.0)fCode[i]=val;
	329	}
	330	return;
	331	}
	332
	333	//////////////////////////////////////////////////////////////////////////////
	334
	335	Double_t AliTPCHTable::GetEntropy()const{
a79660fb	336	//This method calculates the value of the entropy
2e9f335b	337	Double_t entropy=0;
	338	Double_t prob=0;
	339	for (Int_t i=0;i<fSize;i++){
	340	if (fCode[i]){
	341	prob=fCode[i]/(Double_t)fNum;
	342	entropy+=prob*(TMath::Log2(prob));
	343	}
	344	}
	345	return -entropy;
	346	}
	347
	348	//////////////////////////////////////////////////////////////////////////////
	349
	350	Int_t AliTPCHTable::BuildHTable(){
a79660fb	351	//It builds a Huffman tree
2e9f335b	352	if(GetWordsNumber()){
	353	for (Int_t i=0; i< fSize; i++) {
	354	if (fCode[i] > 0.){
	355	fNnodes++;
	356	//cout<< "Symbol:"<<i<<" Freq:"<<fCode[i]<<endl;
	357	fHNodes->Add(new AliTPCHNode(i,fCode[i]));
	358	}//end if
	359	}//end for
	360	Int_t nentries=fHNodes->GetEntriesFast();
	361	//cout<<"Number of symbols: "<<nentries<<endl;
	362	Int_t nindex=nentries-1;
	363	while (nindex > 0){
	364	fHNodes->Sort(nindex+1);
	365	AliTPCHNode *aux = new AliTPCHNode(0,0);
	366	AliTPCHNode node= (AliTPCHNode)fHNodes->UncheckedAt(nindex-1);
	367	AliTPCHNode node1= (AliTPCHNode)fHNodes->UncheckedAt(nindex);
	368
	369	aux->SetLeft(node);
	370	aux->SetRight(node1);
	371	aux->SetFrequency(node->GetFrequency() + node1->GetFrequency());
	372	fHNodes->RemoveAt(nindex-1);
	373	fHNodes->AddAt(aux,nindex-1);
	374	nindex--;
	375	}//end while
	376	ClearTable();
	377	AliTPCHNode start= (AliTPCHNode)fHNodes->UncheckedAt(0);
	378	SpanTree(start,0,0);
	379	}//end if
	380	else{
	381	cout<<"Table contains 0 elements\n";
	382	}//end else
	383	return 0;
	384	}
2e9f335b	385	//////////////////////////////////////////////////////////////////////////////