fix coding convention violations
[u/mrichter/AliRoot.git] / RAW / AliTPCHTable.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 <TMath.h>
27 #include "AliTPCBuffer160.h"
28 #include "AliTPCHNode.h"
29 #include "AliTPCHTable.h"
30
31 ClassImp(AliTPCHTable)
32   
33 AliTPCHTable::AliTPCHTable(){
34   //Constructor
35   fCodeLen=0;
36   fCode=0;
37   fHNodes=0;
38   fNnodes=0;
39   fNum=0;
40   fVerbose=0;
41 }
42
43 //////////////////////////////////////////////////////////////////////////////
44
45 AliTPCHTable::AliTPCHTable(Int_t size){
46   //Initialization
47   fSize=size;
48   fCodeLen = new UChar_t[fSize]; 
49   fCode = new Double_t[fSize]; 
50   fHNodes = new TObjArray;
51   fNnodes=0;
52   fNum=0;
53   fVerbose=0;
54   fSym= new Short_t[fSize];
55   for (Short_t i=0;i<fSize;i++) {
56     fSym[i]=i;
57   }//end for
58   ClearTable(); 
59 }
60
61 //////////////////////////////////////////////////////////////////////////////
62
63 AliTPCHTable::AliTPCHTable(const AliTPCHTable &source)
64   :TObject(source){
65   //Copy Constructor 
66   if(&source == this) return;
67   this->fSize = source.fSize;
68   this->fCodeLen = source.fCodeLen;
69   this->fCode = source.fCode;
70   this->fSym = source.fSym;
71   this->fHNodes = source.fHNodes;
72   this->fNnodes = source.fNnodes;
73   this->fNum=source.fNum;
74   this->fVerbose=source.fVerbose;
75   return;
76 }
77
78 //////////////////////////////////////////////////////////////////////////////
79
80 AliTPCHTable& AliTPCHTable::operator=(const AliTPCHTable &source) {
81   //Assignment operator
82   if(&source == this) return *this;
83   this->fSize = source.fSize;
84   this->fCodeLen = source.fCodeLen;
85   this->fCode = source.fCode;
86   this->fSym = source.fSym;
87   this->fHNodes = source.fHNodes;
88   this->fNnodes = source.fNnodes;
89   this->fNum=source.fNum;
90   this->fVerbose=source.fVerbose;
91   return *this;
92 }
93
94 //////////////////////////////////////////////////////////////////////////////
95
96 AliTPCHTable::~AliTPCHTable(){
97   //HTable destructor
98   if(fVerbose)
99     cout<<"HTable destructor !\n";
100   if (fCodeLen) delete[] fCodeLen;
101   if (fCode) delete [] fCode;
102   if (fHNodes) {
103     fHNodes->Delete(); //Clear out the collection and deletes the removed objects
104     delete fHNodes;
105   }//end if
106 }
107
108 //////////////////////////////////////////////////////////////////////////////
109
110 void AliTPCHTable::SetCodeLen(UChar_t len,Int_t val){
111   //Sets codelength of "val" to the variable "len"
112   fCodeLen[val]=len;
113   return;
114 }
115
116 //////////////////////////////////////////////////////////////////////////////
117
118 void AliTPCHTable::SetCode(Double_t code,Int_t val){
119   //Sets the binary code of the variable "val"
120   fCode[val]=code;
121   return;
122 }
123
124 //////////////////////////////////////////////////////////////////////////////
125
126 void AliTPCHTable::PrintTable()const{
127   //This method prints a table
128   cout<<"Table for Huffman coding\n";
129   cout<<"  Symbol|   Code   |   Length \n";
130   for (Int_t i=0;i<fSize;i++){
131     if (fCodeLen[i]){
132       cout.width(6);cout<<fSym[i];
133       cout.width(3);cout<<"|";
134       cout.width(6);cout<<hex<<(UInt_t)fCode[i]<<dec;
135       cout.width(5);cout<<"|";
136       cout.width(6);cout<<(UInt_t)fCodeLen[i]<<endl;  
137     }//end if
138   }//end for
139 }
140
141 //////////////////////////////////////////////////////////////////////////////
142
143 Bool_t AliTPCHTable::SpanTree(AliTPCHNode *start, UInt_t code, UChar_t len){
144   //Hoffman codes are generated spanning the Huffman tree
145   //In an Huffman tree any internal node has always two children
146   AliTPCHNode * visited;
147   visited = start;
148   Int_t idx=visited->GetSymbol();
149   if (!visited->GetLeft()) {
150     fCode[idx] = code; 
151     fCodeLen[idx] = len;
152     return kTRUE;
153   }//end if
154   SpanTree(visited->GetLeft(), code << 1, len + 1);
155   SpanTree(visited->GetRight(), code << 1 | 0x0001, len + 1);
156   return kTRUE;
157 }
158
159 //////////////////////////////////////////////////////////////////////////////
160
161 void AliTPCHTable::ResetHNodes(){
162   //Reset number of HNodes and the HNodes array 
163   if (fHNodes)  fHNodes->Clear();
164   if (fNnodes)  fNnodes=0;
165 }
166
167 //////////////////////////////////////////////////////////////////////////////
168
169 void AliTPCHTable::ClearTable(){
170   //Clear the table
171   memset(fCodeLen,0,sizeof(UChar_t)*fSize);
172   memset(fCode,0,sizeof(Double_t)*fSize);
173 }
174
175 //////////////////////////////////////////////////////////////////////////////
176
177 Int_t  AliTPCHTable::GetFrequencies(const char *fname){
178   //It fills the "fCode" array with the frequencies of the symbols read from the file
179   AliTPCBuffer160 buff(fname,0);
180   UInt_t numberOfWords=0;
181   Int_t val;
182   while((val=buff.GetNext())!=-1){
183     fCode[val]++;
184     fNum++;
185     numberOfWords++;
186   }
187   cout<<"Total number of words: "<<numberOfWords<<endl;
188   //Print out the frequencies 
189   /*
190     for (Int_t i=0;i<fSize;i++){
191     if (fCode[i])cout<<"Symbol: "<<i<<" Freq: "<<fCode[i]<<endl;
192     }
193     cout<<endl;
194   */
195   return 0;
196 }
197
198 Int_t AliTPCHTable::SetValFrequency(Int_t Val,Double_t Value){
199   //This method sets to "Value" the frequency of the symbol "Val"
200   fCode[Val]=Value;
201   fNum=1;
202   return 0;
203 }
204
205 //////////////////////////////////////////////////////////////////////////////
206
207 Int_t AliTPCHTable::SetFrequency(Int_t Val){
208   //It increments by one the frequency of the symbol "Val" whose frequency is 
209   //stored in the fCode array
210   fCode[Val]++;
211   fNum++;
212   return 0;
213 }
214
215 //////////////////////////////////////////////////////////////////////////////
216
217 Int_t AliTPCHTable::NormalizeFrequencies(){
218   //This method normalized the frequencies
219   //Frequencies normalization
220   Double_t sum=0.;
221   for (Int_t i=0; i< fSize; i++) {
222     sum+=fCode[i];
223   }//end for 
224   if (fVerbose){
225     cout<<"Frequency sum: "<<sum<<endl;
226   }//end if
227   if(sum!=0.){
228     for (Int_t i=0; i< fSize; i++) {
229       fCode[i]/=sum;
230       if ((fCode[i]!=0.) && (fCode[i]<10e-20))cout<<"Frequency value very small !!! "<<fCode[i]<<endl;
231     }//end for 
232   }
233   return 0;
234 }
235 //////////////////////////////////////////////////////////////////////////////
236 Int_t AliTPCHTable::StoreFrequencies(const char *fname)const{
237   //It stores the frequencies in a text file
238   ofstream ftxt(fname);  
239   for (Int_t i=0;i<fSize;i++){
240     ftxt<<fCode[i]<<endl;
241   }
242   ftxt.close();
243   return 0;
244 }
245
246 //////////////////////////////////////////////////////////////////////////////
247
248 void AliTPCHTable::CompleteTable(Int_t k){
249   //According to the kind of table (0..4) it associates a dummy frequency (1) to 
250   //every symbols whose real frequency is zero, in a given range 0..max
251   Int_t max;
252   UInt_t val;
253   switch(k){
254   case 0:
255     max=fSize;
256     val=1;
257     break;
258   case 1:
259     max=445;
260     val=1;
261     break;
262   default:
263     max=fSize;
264     val=1;
265     break;
266   }//end switch
267
268   for(Int_t i=0;i<max;i++){
269     if(fCode[i]==0.0)fCode[i]=val;
270   }
271   return;
272 }
273
274 //////////////////////////////////////////////////////////////////////////////
275
276 Double_t  AliTPCHTable::GetEntropy()const{
277   //This method calculates the value of the entropy 
278   Double_t entropy=0;
279   Double_t prob=0;
280   for (Int_t i=0;i<fSize;i++){
281     if (fCode[i]){
282       prob=fCode[i]/(Double_t)fNum;
283       entropy+=prob*(TMath::Log2(prob));
284     }
285   }
286   return -entropy;
287 }
288
289 //////////////////////////////////////////////////////////////////////////////
290
291 Int_t AliTPCHTable::BuildHTable(){
292   //It builds a Huffman tree 
293   if(GetWordsNumber()){
294     for (Int_t i=0; i< fSize; i++) {
295       if (fCode[i] > 0.){
296         fNnodes++;
297         //cout<< "Symbol:"<<i<<" Freq:"<<fCode[i]<<endl;
298         fHNodes->Add(new AliTPCHNode(i,fCode[i]));
299       }//end if
300     }//end for
301     Int_t nentries=fHNodes->GetEntriesFast();  
302     //cout<<"Number of symbols: "<<nentries<<endl;
303     Int_t nindex=nentries-1;  
304     while (nindex > 0){
305       fHNodes->Sort(nindex+1);
306       AliTPCHNode *aux = new AliTPCHNode(0,0);
307       AliTPCHNode *node= (AliTPCHNode*)fHNodes->UncheckedAt(nindex-1);
308       AliTPCHNode *node1= (AliTPCHNode*)fHNodes->UncheckedAt(nindex);
309       
310       aux->SetLeft(node);
311       aux->SetRight(node1);
312       aux->SetFrequency(node->GetFrequency() + node1->GetFrequency());
313       fHNodes->RemoveAt(nindex-1);
314       fHNodes->AddAt(aux,nindex-1);
315       nindex--;
316     }//end while
317     ClearTable();  
318     AliTPCHNode *start= (AliTPCHNode*)fHNodes->UncheckedAt(0);
319     SpanTree(start,0,0);
320   }//end if
321   else{
322     cout<<"Table contains 0 elements\n";
323   }//end else
324   return 0;
325 }
326 //////////////////////////////////////////////////////////////////////////////