Add support for 64 bits
[u/mrichter/AliRoot.git] / RAW / AliTPCHuffman.cxx
CommitLineData
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>
27#include <TMath.h>
2e9f335b 28#include "AliTPCBuffer160.h"
b62e2a95 29#include "AliTPCHuffman.h"
2e9f335b 30
31ClassImp(AliTPCHNode)
32
33AliTPCHNode::AliTPCHNode(){
a79660fb 34 //Constructor
2e9f335b 35 fLeft=0;
36 fRight=0;
37}
38
39//////////////////////////////////////////////////////////////////////////////
40
41AliTPCHNode::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 51AliTPCHNode::AliTPCHNode(const AliTPCHNode &source)
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
64AliTPCHNode& 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
76Int_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
90ClassImp(AliTPCHTable)
91
92AliTPCHTable::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
104AliTPCHTable::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 122AliTPCHTable::AliTPCHTable(const AliTPCHTable &source)
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
139AliTPCHTable& 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
155AliTPCHTable::~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
169void 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
177void 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
185void 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 202Bool_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
220void 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
228void 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
236Int_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
257Int_t AliTPCHTable::SetValFrequency(const 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
266Int_t AliTPCHTable::SetFrequency(const Int_t Val){
a79660fb 267 //It increments by one the frequency of the symbol "Val" whose frequency is
268 //stored in the fCode array
2e9f335b 269 fCode[Val]++;
270 fNum++;
271 return 0;
272}
273
274//////////////////////////////////////////////////////////////////////////////
275
9f992f70 276Int_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 295Int_t AliTPCHTable::StoreFrequencies(const char *fname)const{
296 //It stores the frequencies in a text file
2e9f335b 297 ofstream ftxt(fname);
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
307void AliTPCHTable::CompleteTable(Int_t k){
a79660fb 308 //According to the kind of table (0..4) it associates a dummy frequency (1) to
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){
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
335Double_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
350Int_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//////////////////////////////////////////////////////////////////////////////