Corrected size of array ppcon (icc)
[u/mrichter/AliRoot.git] / TPC / 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 **************************************************************************/
15
16////////////////////////////////////////////////
17// Huffman classes for set:TPC //
18////////////////////////////////////////////////
19
20#include <TObjArray.h>
0f0615a3 21#include "Riostream.h"
2e9f335b 22#include "TMath.h"
23#include "AliTPCHuffman.h"
24#include "AliTPCBuffer160.h"
25
26ClassImp(AliTPCHNode)
27
28AliTPCHNode::AliTPCHNode(){
29 // constructor
30 fLeft=0;
31 fRight=0;
32}
33
34//////////////////////////////////////////////////////////////////////////////
35
36AliTPCHNode::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
46AliTPCHNode::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
58AliTPCHNode& 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
70Int_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
84ClassImp(AliTPCHTable)
85
86AliTPCHTable::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
98AliTPCHTable::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
116AliTPCHTable::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
132AliTPCHTable& 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
148AliTPCHTable::~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
162void AliTPCHTable::SetCodeLen(UChar_t len,Int_t val){
163 fCodeLen[val]=len;
164 return;
165}
166
167//////////////////////////////////////////////////////////////////////////////
168
169void AliTPCHTable::SetCode(Double_t code,Int_t val){
170 fCode[val]=code;
171 return;
172}
173
174//////////////////////////////////////////////////////////////////////////////
175
176void 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
192Bool_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
210void 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
218void 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
226Int_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
246Int_t AliTPCHTable::SetValFrequency(const Int_t Val,Double_t Value){
247 fCode[Val]=Value;
248 fNum=1;
249 return 0;
250}
251
252//////////////////////////////////////////////////////////////////////////////
253
254Int_t AliTPCHTable::SetFrequency(const Int_t Val){
255 fCode[Val]++;
256 fNum++;
257 return 0;
258}
259
260//////////////////////////////////////////////////////////////////////////////
261
262Int_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
273void 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
299Double_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
313Int_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//////////////////////////////////////////////////////////////////////////////