fix coding convention violations
[u/mrichter/AliRoot.git] / RAW / AliTPCHTable.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 <TMath.h>
2e9f335b 27#include "AliTPCBuffer160.h"
bea6b2a4 28#include "AliTPCHNode.h"
29#include "AliTPCHTable.h"
2e9f335b 30
31ClassImp(AliTPCHTable)
32
33AliTPCHTable::AliTPCHTable(){
a79660fb 34 //Constructor
2e9f335b 35 fCodeLen=0;
36 fCode=0;
37 fHNodes=0;
38 fNnodes=0;
39 fNum=0;
40 fVerbose=0;
41}
42
43//////////////////////////////////////////////////////////////////////////////
44
45AliTPCHTable::AliTPCHTable(Int_t size){
a79660fb 46 //Initialization
2e9f335b 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
b66321bb 63AliTPCHTable::AliTPCHTable(const AliTPCHTable &source)
64 :TObject(source){
a79660fb 65 //Copy Constructor
2e9f335b 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
80AliTPCHTable& AliTPCHTable::operator=(const AliTPCHTable &source) {
a79660fb 81 //Assignment operator
2e9f335b 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
96AliTPCHTable::~AliTPCHTable(){
a79660fb 97 //HTable destructor
2e9f335b 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
110void AliTPCHTable::SetCodeLen(UChar_t len,Int_t val){
a79660fb 111 //Sets codelength of "val" to the variable "len"
2e9f335b 112 fCodeLen[val]=len;
113 return;
114}
115
116//////////////////////////////////////////////////////////////////////////////
117
118void AliTPCHTable::SetCode(Double_t code,Int_t val){
a79660fb 119 //Sets the binary code of the variable "val"
2e9f335b 120 fCode[val]=code;
121 return;
122}
123
124//////////////////////////////////////////////////////////////////////////////
125
126void AliTPCHTable::PrintTable()const{
a79660fb 127 //This method prints a table
2e9f335b 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<<"|";
0b3c7dfc 134 cout.width(6);cout<<hex<<(UInt_t)fCode[i]<<dec;
2e9f335b 135 cout.width(5);cout<<"|";
0b3c7dfc 136 cout.width(6);cout<<(UInt_t)fCodeLen[i]<<endl;
2e9f335b 137 }//end if
138 }//end for
139}
140
141//////////////////////////////////////////////////////////////////////////////
142
0b3c7dfc 143Bool_t AliTPCHTable::SpanTree(AliTPCHNode *start, UInt_t code, UChar_t len){
a79660fb 144 //Hoffman codes are generated spanning the Huffman tree
2e9f335b 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
161void AliTPCHTable::ResetHNodes(){
a79660fb 162 //Reset number of HNodes and the HNodes array
2e9f335b 163 if (fHNodes) fHNodes->Clear();
164 if (fNnodes) fNnodes=0;
165}
166
167//////////////////////////////////////////////////////////////////////////////
168
169void AliTPCHTable::ClearTable(){
a79660fb 170 //Clear the table
2e9f335b 171 memset(fCodeLen,0,sizeof(UChar_t)*fSize);
172 memset(fCode,0,sizeof(Double_t)*fSize);
173}
174
175//////////////////////////////////////////////////////////////////////////////
176
177Int_t AliTPCHTable::GetFrequencies(const char *fname){
a79660fb 178 //It fills the "fCode" array with the frequencies of the symbols read from the file
2e9f335b 179 AliTPCBuffer160 buff(fname,0);
0b3c7dfc 180 UInt_t numberOfWords=0;
a79660fb 181 Int_t val;
182 while((val=buff.GetNext())!=-1){
183 fCode[val]++;
2e9f335b 184 fNum++;
a79660fb 185 numberOfWords++;
2e9f335b 186 }
a79660fb 187 cout<<"Total number of words: "<<numberOfWords<<endl;
2e9f335b 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
09f6432c 198Int_t AliTPCHTable::SetValFrequency(Int_t Val,Double_t Value){
a79660fb 199 //This method sets to "Value" the frequency of the symbol "Val"
2e9f335b 200 fCode[Val]=Value;
201 fNum=1;
202 return 0;
203}
204
205//////////////////////////////////////////////////////////////////////////////
206
09f6432c 207Int_t AliTPCHTable::SetFrequency(Int_t Val){
a79660fb 208 //It increments by one the frequency of the symbol "Val" whose frequency is
209 //stored in the fCode array
2e9f335b 210 fCode[Val]++;
211 fNum++;
212 return 0;
213}
214
215//////////////////////////////////////////////////////////////////////////////
216
9f992f70 217Int_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//////////////////////////////////////////////////////////////////////////////
a79660fb 236Int_t AliTPCHTable::StoreFrequencies(const char *fname)const{
237 //It stores the frequencies in a text file
2e9f335b 238 ofstream ftxt(fname);
239 for (Int_t i=0;i<fSize;i++){
9f992f70 240 ftxt<<fCode[i]<<endl;
2e9f335b 241 }
242 ftxt.close();
243 return 0;
244}
245
246//////////////////////////////////////////////////////////////////////////////
247
248void AliTPCHTable::CompleteTable(Int_t k){
a79660fb 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
2e9f335b 251 Int_t max;
0b3c7dfc 252 UInt_t val;
2e9f335b 253 switch(k){
254 case 0:
c9bd9d3d 255 max=fSize;
2e9f335b 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
276Double_t AliTPCHTable::GetEntropy()const{
a79660fb 277 //This method calculates the value of the entropy
2e9f335b 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
291Int_t AliTPCHTable::BuildHTable(){
a79660fb 292 //It builds a Huffman tree
2e9f335b 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}
2e9f335b 326//////////////////////////////////////////////////////////////////////////////