[u/mrichter/AliRoot.git] / TPC / 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.                  *
 **************************************************************************/

////////////////////////////////////////////////
//  Huffman classes for set:TPC               //
////////////////////////////////////////////////

#include <TObjArray.h>
#include "Riostream.h"
#include "TMath.h"
#include "AliTPCHuffman.h"
#include "AliTPCBuffer160.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){
  //     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){
  //initialise
  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){
  //     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
  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){
  fCodeLen[val]=len;
  return;
}

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

void AliTPCHTable::SetCode(Double_t code,Int_t val){
  fCode[val]=code;
  return;
}

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

void AliTPCHTable::PrintTable()const{
  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<<(ULong_t)fCode[i]<<dec;
      cout.width(5);cout<<"|";
      cout.width(6);cout<<(ULong_t)fCodeLen[i]<<endl;  
    }//end if
  }//end for
}

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

Bool_t AliTPCHTable::SpanTree(AliTPCHNode *start, ULong_t code, UChar_t len){
  // span 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){
  AliTPCBuffer160 buff(fname,0);
  ULong_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(const Int_t Val,Double_t Value){
  fCode[Val]=Value;
  fNum=1;
  return 0;
}

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

Int_t AliTPCHTable::SetFrequency(const Int_t Val){
  fCode[Val]++;
  fNum++;
  return 0;
}

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

Int_t AliTPCHTable::StoreFrequencies(const char *fname){
  ofstream ftxt(fname);  
  for (Int_t i=0;i<fSize;i++){
    ftxt<<(ULong_t)fCode[i]<<endl;
  }
  ftxt.close();
  return 0;
}

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

void AliTPCHTable::CompleteTable(Int_t k){
  Int_t max;
  ULong_t val;
  switch(k){
  case 0:
    max=700;
    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{
  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(){
  // build Htable
  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
	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	**************************************************************************/
	15
	16	////////////////////////////////////////////////
	17	// Huffman classes for set:TPC //
	18	////////////////////////////////////////////////
	19
	20	#include <TObjArray.h>
	21	#include "Riostream.h"
	22	#include "TMath.h"
	23	#include "AliTPCHuffman.h"
	24	#include "AliTPCBuffer160.h"
	25
	26	ClassImp(AliTPCHNode)
	27
	28	AliTPCHNode::AliTPCHNode(){
	29	// constructor
	30	fLeft=0;
	31	fRight=0;
	32	}
	33
	34	//////////////////////////////////////////////////////////////////////////////
	35
	36	AliTPCHNode::AliTPCHNode(Int_t sym, Double_t freq){
	37	// standard constructor
	38	fSymbol=sym;
	39	fFrequency=freq;
	40	fLeft=0;
	41	fRight=0;
	42	}
	43
	44	//////////////////////////////////////////////////////////////////////////////
	45
	46	AliTPCHNode::AliTPCHNode(const AliTPCHNode &source){
	47	// Copy Constructor
	48	if(&source == this) return;
	49	this->fSymbol = source.fSymbol;
	50	this->fFrequency = source.fFrequency;
	51	this->fLeft = source.fLeft;
	52	this->fRight = source.fRight;
	53	return;
	54	}
	55
	56	//////////////////////////////////////////////////////////////////////////////
	57
	58	AliTPCHNode& AliTPCHNode::operator=(const AliTPCHNode &source){
	59	// Assignment operator
	60	if(&source == this) return *this;
	61	this->fSymbol = source.fSymbol;
	62	this->fFrequency = source.fFrequency;
	63	this->fLeft = source.fLeft;
	64	this->fRight = source.fRight;
	65	return *this;
	66	}
	67
	68	//////////////////////////////////////////////////////////////////////////////
	69
	70	Int_t AliTPCHNode::Compare(const TObject *obj)const{
	71	// function called by Sort method of TObjArray
	72	AliTPCHNode node=(AliTPCHNode )obj;
	73	Double_t f=fFrequency;
	74	Double_t fo=node->fFrequency;
	75	if (f<fo) return 1;
	76	else if (f>fo) return -1;
	77	else return 0;
	78	}
	79
	80	//////////////////////////////////////////////////////////////////////////////
	81	//////////////////////////////////////////////////////////////////////////////
	82	//////////////////////////////////////////////////////////////////////////////
	83
	84	ClassImp(AliTPCHTable)
	85
	86	AliTPCHTable::AliTPCHTable(){
	87	// constructor
	88	fCodeLen=0;
	89	fCode=0;
	90	fHNodes=0;
	91	fNnodes=0;
	92	fNum=0;
	93	fVerbose=0;
	94	}
	95
	96	//////////////////////////////////////////////////////////////////////////////
	97
	98	AliTPCHTable::AliTPCHTable(Int_t size){
	99	//initialise
	100	fSize=size;
	101	fCodeLen = new UChar_t[fSize];
	102	fCode = new Double_t[fSize];
	103	fHNodes = new TObjArray;
	104	fNnodes=0;
	105	fNum=0;
	106	fVerbose=0;
	107	fSym= new Short_t[fSize];
	108	for (Short_t i=0;i<fSize;i++) {
	109	fSym[i]=i;
	110	}//end for
	111	ClearTable();
	112	}
	113
	114	//////////////////////////////////////////////////////////////////////////////
	115
	116	AliTPCHTable::AliTPCHTable(const AliTPCHTable &source){
	117	// Copy Constructor
	118	if(&source == this) return;
	119	this->fSize = source.fSize;
	120	this->fCodeLen = source.fCodeLen;
	121	this->fCode = source.fCode;
	122	this->fSym = source.fSym;
	123	this->fHNodes = source.fHNodes;
	124	this->fNnodes = source.fNnodes;
	125	this->fNum=source.fNum;
	126	this->fVerbose=source.fVerbose;
	127	return;
	128	}
	129
	130	//////////////////////////////////////////////////////////////////////////////
	131
	132	AliTPCHTable& AliTPCHTable::operator=(const AliTPCHTable &source) {
	133	// Assignment operator
	134	if(&source == this) return *this;
	135	this->fSize = source.fSize;
	136	this->fCodeLen = source.fCodeLen;
	137	this->fCode = source.fCode;
	138	this->fSym = source.fSym;
	139	this->fHNodes = source.fHNodes;
	140	this->fNnodes = source.fNnodes;
	141	this->fNum=source.fNum;
	142	this->fVerbose=source.fVerbose;
	143	return *this;
	144	}
	145
	146	//////////////////////////////////////////////////////////////////////////////
	147
	148	AliTPCHTable::~AliTPCHTable(){
	149	// HTable
	150	if(fVerbose)
	151	cout<<"HTable destructor !\n";
	152	if (fCodeLen) delete[] fCodeLen;
	153	if (fCode) delete [] fCode;
	154	if (fHNodes) {
	155	fHNodes->Delete(); //Clear out the collection and deletes the removed objects
	156	delete fHNodes;
	157	}//end if
	158	}
	159
	160	//////////////////////////////////////////////////////////////////////////////
	161
	162	void AliTPCHTable::SetCodeLen(UChar_t len,Int_t val){
	163	fCodeLen[val]=len;
	164	return;
	165	}
	166
	167	//////////////////////////////////////////////////////////////////////////////
	168
	169	void AliTPCHTable::SetCode(Double_t code,Int_t val){
	170	fCode[val]=code;
	171	return;
	172	}
	173
	174	//////////////////////////////////////////////////////////////////////////////
	175
	176	void AliTPCHTable::PrintTable()const{
	177	cout<<"Table for Huffman coding\n";
	178	cout<<" Symbol\| Code \| Length \n";
	179	for (Int_t i=0;i<fSize;i++){
	180	if (fCodeLen[i]){
	181	cout.width(6);cout<<fSym[i];
	182	cout.width(3);cout<<"\|";
	183	cout.width(6);cout<<hex<<(ULong_t)fCode[i]<<dec;
	184	cout.width(5);cout<<"\|";
	185	cout.width(6);cout<<(ULong_t)fCodeLen[i]<<endl;
	186	}//end if
	187	}//end for
	188	}
	189
	190	//////////////////////////////////////////////////////////////////////////////
	191
	192	Bool_t AliTPCHTable::SpanTree(AliTPCHNode *start, ULong_t code, UChar_t len){
	193	// span tree
	194	//In an Huffman tree any internal node has always two children
	195	AliTPCHNode * visited;
	196	visited = start;
	197	Int_t idx=visited->GetSymbol();
	198	if (!visited->GetLeft()) {
	199	fCode[idx] = code;
	200	fCodeLen[idx] = len;
	201	return kTRUE;
	202	}//end if
	203	SpanTree(visited->GetLeft(), code << 1, len + 1);
	204	SpanTree(visited->GetRight(), code << 1 \| 0x0001, len + 1);
	205	return kTRUE;
	206	}
	207
	208	//////////////////////////////////////////////////////////////////////////////
	209
	210	void AliTPCHTable::ResetHNodes(){
	211	// Reset number of HNodes and the HNodes array
	212	if (fHNodes) fHNodes->Clear();
	213	if (fNnodes) fNnodes=0;
	214	}
	215
	216	//////////////////////////////////////////////////////////////////////////////
	217
	218	void AliTPCHTable::ClearTable(){
	219	// Clear the table
	220	memset(fCodeLen,0,sizeof(UChar_t)*fSize);
	221	memset(fCode,0,sizeof(Double_t)*fSize);
	222	}
	223
	224	//////////////////////////////////////////////////////////////////////////////
	225
	226	Int_t AliTPCHTable::GetFrequencies(const char *fname){
	227	AliTPCBuffer160 buff(fname,0);
	228	ULong_t NumberOfWords=0;
	229	Int_t Val;
	230	while((Val=buff.GetNext())!=-1){
	231	fCode[Val]++;
	232	fNum++;
	233	NumberOfWords++;
	234	}
	235	cout<<"Total number of words: "<<NumberOfWords<<endl;
	236	//Print out the frequencies
	237	/*
	238	for (Int_t i=0;i<fSize;i++){
	239	if (fCode[i])cout<<"Symbol: "<<i<<" Freq: "<<fCode[i]<<endl;
	240	}
	241	cout<<endl;
	242	*/
	243	return 0;
	244	}
	245
	246	Int_t AliTPCHTable::SetValFrequency(const Int_t Val,Double_t Value){
	247	fCode[Val]=Value;
	248	fNum=1;
	249	return 0;
	250	}
	251
	252	//////////////////////////////////////////////////////////////////////////////
	253
	254	Int_t AliTPCHTable::SetFrequency(const Int_t Val){
	255	fCode[Val]++;
	256	fNum++;
	257	return 0;
	258	}
	259
	260	//////////////////////////////////////////////////////////////////////////////
	261
	262	Int_t AliTPCHTable::StoreFrequencies(const char *fname){
	263	ofstream ftxt(fname);
	264	for (Int_t i=0;i<fSize;i++){
	265	ftxt<<(ULong_t)fCode[i]<<endl;
	266	}
	267	ftxt.close();
	268	return 0;
	269	}
	270
	271	//////////////////////////////////////////////////////////////////////////////
	272
	273	void AliTPCHTable::CompleteTable(Int_t k){
	274	Int_t max;
	275	ULong_t val;
	276	switch(k){
	277	case 0:
	278	max=700;
	279	val=1;
	280	break;
	281	case 1:
	282	max=445;
	283	val=1;
	284	break;
	285	default:
	286	max=fSize;
	287	val=1;
	288	break;
	289	}//end switch
	290
	291	for(Int_t i=0;i<max;i++){
	292	if(fCode[i]==0.0)fCode[i]=val;
	293	}
	294	return;
	295	}
	296
	297	//////////////////////////////////////////////////////////////////////////////
	298
	299	Double_t AliTPCHTable::GetEntropy()const{
	300	Double_t entropy=0;
	301	Double_t prob=0;
	302	for (Int_t i=0;i<fSize;i++){
	303	if (fCode[i]){
	304	prob=fCode[i]/(Double_t)fNum;
	305	entropy+=prob*(TMath::Log2(prob));
	306	}
	307	}
	308	return -entropy;
	309	}
	310
	311	//////////////////////////////////////////////////////////////////////////////
	312
	313	Int_t AliTPCHTable::BuildHTable(){
	314	// build Htable
	315	if(GetWordsNumber()){
	316	for (Int_t i=0; i< fSize; i++) {
	317	if (fCode[i] > 0.){
	318	fNnodes++;
	319	//cout<< "Symbol:"<<i<<" Freq:"<<fCode[i]<<endl;
	320	fHNodes->Add(new AliTPCHNode(i,fCode[i]));
	321	}//end if
	322	}//end for
	323	Int_t nentries=fHNodes->GetEntriesFast();
	324	//cout<<"Number of symbols: "<<nentries<<endl;
	325	Int_t nindex=nentries-1;
	326	while (nindex > 0){
	327	fHNodes->Sort(nindex+1);
	328	AliTPCHNode *aux = new AliTPCHNode(0,0);
	329	AliTPCHNode node= (AliTPCHNode)fHNodes->UncheckedAt(nindex-1);
	330	AliTPCHNode node1= (AliTPCHNode)fHNodes->UncheckedAt(nindex);
	331
	332	aux->SetLeft(node);
	333	aux->SetRight(node1);
	334	aux->SetFrequency(node->GetFrequency() + node1->GetFrequency());
	335	fHNodes->RemoveAt(nindex-1);
	336	fHNodes->AddAt(aux,nindex-1);
	337	nindex--;
	338	}//end while
	339	ClearTable();
	340	AliTPCHNode start= (AliTPCHNode)fHNodes->UncheckedAt(0);
	341	SpanTree(start,0,0);
	342	}//end if
	343	else{
	344	cout<<"Table contains 0 elements\n";
	345	}//end else
	346	return 0;
	347	}
	348
	349	//////////////////////////////////////////////////////////////////////////////