Additional protection
[u/mrichter/AliRoot.git] / RAW / AliTPCHuffman.cxx
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 /* $Id:*/
16 ////////////////////////////////////////////////
17 //  Huffman classes for set:TPC               //
18 ////////////////////////////////////////////////
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
25 #include <TObjArray.h>
26 #include <Riostream.h>
27 #include <TMath.h>
28 #include "AliTPCBuffer160.h"
29 #include "AliTPCHuffman.h"
30
31 ClassImp(AliTPCHNode)
32
33 AliTPCHNode::AliTPCHNode(){
34   //Constructor
35   fLeft=0;
36   fRight=0;
37 }
38
39 //////////////////////////////////////////////////////////////////////////////
40
41 AliTPCHNode::AliTPCHNode(Int_t sym, Double_t freq){
42   //Standard constructor
43   fSymbol=sym;
44   fFrequency=freq;
45   fLeft=0;
46   fRight=0;
47 }
48
49 //////////////////////////////////////////////////////////////////////////////
50
51 AliTPCHNode::AliTPCHNode(const AliTPCHNode &source)
52   :TObject(source){
53   //Copy Constructor 
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){
65   //Assignment operator
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{
77   //Function called by Sort method of TObjArray
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(){
93   //Constructor
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){
105   //Initialization
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
122 AliTPCHTable::AliTPCHTable(const AliTPCHTable &source)
123   :TObject(source){
124   //Copy Constructor 
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) {
140   //Assignment operator
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(){
156   //HTable destructor
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){
170   //Sets codelength of "val" to the variable "len"
171   fCodeLen[val]=len;
172   return;
173 }
174
175 //////////////////////////////////////////////////////////////////////////////
176
177 void AliTPCHTable::SetCode(Double_t code,Int_t val){
178   //Sets the binary code of the variable "val"
179   fCode[val]=code;
180   return;
181 }
182
183 //////////////////////////////////////////////////////////////////////////////
184
185 void AliTPCHTable::PrintTable()const{
186   //This method prints a table
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<<"|";
193       cout.width(6);cout<<hex<<(UInt_t)fCode[i]<<dec;
194       cout.width(5);cout<<"|";
195       cout.width(6);cout<<(UInt_t)fCodeLen[i]<<endl;  
196     }//end if
197   }//end for
198 }
199
200 //////////////////////////////////////////////////////////////////////////////
201
202 Bool_t AliTPCHTable::SpanTree(AliTPCHNode *start, UInt_t code, UChar_t len){
203   //Hoffman codes are generated spanning the Huffman tree
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(){
221   //Reset number of HNodes and the HNodes array 
222   if (fHNodes)  fHNodes->Clear();
223   if (fNnodes)  fNnodes=0;
224 }
225
226 //////////////////////////////////////////////////////////////////////////////
227
228 void AliTPCHTable::ClearTable(){
229   //Clear the table
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){
237   //It fills the "fCode" array with the frequencies of the symbols read from the file
238   AliTPCBuffer160 buff(fname,0);
239   UInt_t numberOfWords=0;
240   Int_t val;
241   while((val=buff.GetNext())!=-1){
242     fCode[val]++;
243     fNum++;
244     numberOfWords++;
245   }
246   cout<<"Total number of words: "<<numberOfWords<<endl;
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
257 Int_t AliTPCHTable::SetValFrequency(Int_t Val,Double_t Value){
258   //This method sets to "Value" the frequency of the symbol "Val"
259   fCode[Val]=Value;
260   fNum=1;
261   return 0;
262 }
263
264 //////////////////////////////////////////////////////////////////////////////
265
266 Int_t AliTPCHTable::SetFrequency(Int_t Val){
267   //It increments by one the frequency of the symbol "Val" whose frequency is 
268   //stored in the fCode array
269   fCode[Val]++;
270   fNum++;
271   return 0;
272 }
273
274 //////////////////////////////////////////////////////////////////////////////
275
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 //////////////////////////////////////////////////////////////////////////////
295 Int_t AliTPCHTable::StoreFrequencies(const char *fname)const{
296   //It stores the frequencies in a text file
297   ofstream ftxt(fname);  
298   for (Int_t i=0;i<fSize;i++){
299     ftxt<<fCode[i]<<endl;
300   }
301   ftxt.close();
302   return 0;
303 }
304
305 //////////////////////////////////////////////////////////////////////////////
306
307 void AliTPCHTable::CompleteTable(Int_t k){
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
310   Int_t max;
311   UInt_t val;
312   switch(k){
313   case 0:
314     max=fSize;
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{
336   //This method calculates the value of the entropy 
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(){
351   //It builds a Huffman tree 
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 }
385 //////////////////////////////////////////////////////////////////////////////