New classes and macros for raw data compression and ADC (D.Favretto)
[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>
21#include <iostream.h>
22#include <fstream.h>
23#include "TMath.h"
24#include "AliTPCHuffman.h"
25#include "AliTPCBuffer160.h"
26
27ClassImp(AliTPCHNode)
28
29AliTPCHNode::AliTPCHNode(){
30 // constructor
31 fLeft=0;
32 fRight=0;
33}
34
35//////////////////////////////////////////////////////////////////////////////
36
37AliTPCHNode::AliTPCHNode(Int_t sym, Double_t freq){
38 // standard constructor
39 fSymbol=sym;
40 fFrequency=freq;
41 fLeft=0;
42 fRight=0;
43}
44
45//////////////////////////////////////////////////////////////////////////////
46
47AliTPCHNode::AliTPCHNode(const AliTPCHNode &source){
48 // Copy Constructor
49 if(&source == this) return;
50 this->fSymbol = source.fSymbol;
51 this->fFrequency = source.fFrequency;
52 this->fLeft = source.fLeft;
53 this->fRight = source.fRight;
54 return;
55}
56
57//////////////////////////////////////////////////////////////////////////////
58
59AliTPCHNode& AliTPCHNode::operator=(const AliTPCHNode &source){
60 // Assignment operator
61 if(&source == this) return *this;
62 this->fSymbol = source.fSymbol;
63 this->fFrequency = source.fFrequency;
64 this->fLeft = source.fLeft;
65 this->fRight = source.fRight;
66 return *this;
67}
68
69//////////////////////////////////////////////////////////////////////////////
70
71Int_t AliTPCHNode::Compare(const TObject *obj)const{
72 // function called by Sort method of TObjArray
73 AliTPCHNode *node=(AliTPCHNode *)obj;
74 Double_t f=fFrequency;
75 Double_t fo=node->fFrequency;
76 if (f<fo) return 1;
77 else if (f>fo) return -1;
78 else return 0;
79}
80
81//////////////////////////////////////////////////////////////////////////////
82//////////////////////////////////////////////////////////////////////////////
83//////////////////////////////////////////////////////////////////////////////
84
85ClassImp(AliTPCHTable)
86
87AliTPCHTable::AliTPCHTable(){
88 // constructor
89 fCodeLen=0;
90 fCode=0;
91 fHNodes=0;
92 fNnodes=0;
93 fNum=0;
94 fVerbose=0;
95}
96
97//////////////////////////////////////////////////////////////////////////////
98
99AliTPCHTable::AliTPCHTable(Int_t size){
100 //initialise
101 fSize=size;
102 fCodeLen = new UChar_t[fSize];
103 fCode = new Double_t[fSize];
104 fHNodes = new TObjArray;
105 fNnodes=0;
106 fNum=0;
107 fVerbose=0;
108 fSym= new Short_t[fSize];
109 for (Short_t i=0;i<fSize;i++) {
110 fSym[i]=i;
111 }//end for
112 ClearTable();
113}
114
115//////////////////////////////////////////////////////////////////////////////
116
117AliTPCHTable::AliTPCHTable(const AliTPCHTable &source){
118 // Copy Constructor
119 if(&source == this) return;
120 this->fSize = source.fSize;
121 this->fCodeLen = source.fCodeLen;
122 this->fCode = source.fCode;
123 this->fSym = source.fSym;
124 this->fHNodes = source.fHNodes;
125 this->fNnodes = source.fNnodes;
126 this->fNum=source.fNum;
127 this->fVerbose=source.fVerbose;
128 return;
129}
130
131//////////////////////////////////////////////////////////////////////////////
132
133AliTPCHTable& AliTPCHTable::operator=(const AliTPCHTable &source) {
134 // Assignment operator
135 if(&source == this) return *this;
136 this->fSize = source.fSize;
137 this->fCodeLen = source.fCodeLen;
138 this->fCode = source.fCode;
139 this->fSym = source.fSym;
140 this->fHNodes = source.fHNodes;
141 this->fNnodes = source.fNnodes;
142 this->fNum=source.fNum;
143 this->fVerbose=source.fVerbose;
144 return *this;
145}
146
147//////////////////////////////////////////////////////////////////////////////
148
149AliTPCHTable::~AliTPCHTable(){
150 // HTable
151 if(fVerbose)
152 cout<<"HTable destructor !\n";
153 if (fCodeLen) delete[] fCodeLen;
154 if (fCode) delete [] fCode;
155 if (fHNodes) {
156 fHNodes->Delete(); //Clear out the collection and deletes the removed objects
157 delete fHNodes;
158 }//end if
159}
160
161//////////////////////////////////////////////////////////////////////////////
162
163void AliTPCHTable::SetCodeLen(UChar_t len,Int_t val){
164 fCodeLen[val]=len;
165 return;
166}
167
168//////////////////////////////////////////////////////////////////////////////
169
170void AliTPCHTable::SetCode(Double_t code,Int_t val){
171 fCode[val]=code;
172 return;
173}
174
175//////////////////////////////////////////////////////////////////////////////
176
177void AliTPCHTable::PrintTable()const{
178 cout<<"Table for Huffman coding\n";
179 cout<<" Symbol| Code | Length \n";
180 for (Int_t i=0;i<fSize;i++){
181 if (fCodeLen[i]){
182 cout.width(6);cout<<fSym[i];
183 cout.width(3);cout<<"|";
184 cout.width(6);cout<<hex<<(ULong_t)fCode[i]<<dec;
185 cout.width(5);cout<<"|";
186 cout.width(6);cout<<(ULong_t)fCodeLen[i]<<endl;
187 }//end if
188 }//end for
189}
190
191//////////////////////////////////////////////////////////////////////////////
192
193Bool_t AliTPCHTable::SpanTree(AliTPCHNode *start, ULong_t code, UChar_t len){
194 // span tree
195 //In an Huffman tree any internal node has always two children
196 AliTPCHNode * visited;
197 visited = start;
198 Int_t idx=visited->GetSymbol();
199 if (!visited->GetLeft()) {
200 fCode[idx] = code;
201 fCodeLen[idx] = len;
202 return kTRUE;
203 }//end if
204 SpanTree(visited->GetLeft(), code << 1, len + 1);
205 SpanTree(visited->GetRight(), code << 1 | 0x0001, len + 1);
206 return kTRUE;
207}
208
209//////////////////////////////////////////////////////////////////////////////
210
211void AliTPCHTable::ResetHNodes(){
212 // Reset number of HNodes and the HNodes array
213 if (fHNodes) fHNodes->Clear();
214 if (fNnodes) fNnodes=0;
215}
216
217//////////////////////////////////////////////////////////////////////////////
218
219void AliTPCHTable::ClearTable(){
220 // Clear the table
221 memset(fCodeLen,0,sizeof(UChar_t)*fSize);
222 memset(fCode,0,sizeof(Double_t)*fSize);
223}
224
225//////////////////////////////////////////////////////////////////////////////
226
227Int_t AliTPCHTable::GetFrequencies(const char *fname){
228 AliTPCBuffer160 buff(fname,0);
229 ULong_t NumberOfWords=0;
230 Int_t Val;
231 while((Val=buff.GetNext())!=-1){
232 fCode[Val]++;
233 fNum++;
234 NumberOfWords++;
235 }
236 cout<<"Total number of words: "<<NumberOfWords<<endl;
237 //Print out the frequencies
238 /*
239 for (Int_t i=0;i<fSize;i++){
240 if (fCode[i])cout<<"Symbol: "<<i<<" Freq: "<<fCode[i]<<endl;
241 }
242 cout<<endl;
243 */
244 return 0;
245}
246
247Int_t AliTPCHTable::SetValFrequency(const Int_t Val,Double_t Value){
248 fCode[Val]=Value;
249 fNum=1;
250 return 0;
251}
252
253//////////////////////////////////////////////////////////////////////////////
254
255Int_t AliTPCHTable::SetFrequency(const Int_t Val){
256 fCode[Val]++;
257 fNum++;
258 return 0;
259}
260
261//////////////////////////////////////////////////////////////////////////////
262
263Int_t AliTPCHTable::StoreFrequencies(const char *fname){
264 ofstream ftxt(fname);
265 for (Int_t i=0;i<fSize;i++){
266 ftxt<<(ULong_t)fCode[i]<<endl;
267 }
268 ftxt.close();
269 return 0;
270}
271
272//////////////////////////////////////////////////////////////////////////////
273
274void AliTPCHTable::CompleteTable(Int_t k){
275 Int_t max;
276 ULong_t val;
277 switch(k){
278 case 0:
279 max=700;
280 val=1;
281 break;
282 case 1:
283 max=445;
284 val=1;
285 break;
286 default:
287 max=fSize;
288 val=1;
289 break;
290 }//end switch
291
292 for(Int_t i=0;i<max;i++){
293 if(fCode[i]==0.0)fCode[i]=val;
294 }
295 return;
296}
297
298//////////////////////////////////////////////////////////////////////////////
299
300Double_t AliTPCHTable::GetEntropy()const{
301 Double_t entropy=0;
302 Double_t prob=0;
303 for (Int_t i=0;i<fSize;i++){
304 if (fCode[i]){
305 prob=fCode[i]/(Double_t)fNum;
306 entropy+=prob*(TMath::Log2(prob));
307 }
308 }
309 return -entropy;
310}
311
312//////////////////////////////////////////////////////////////////////////////
313
314Int_t AliTPCHTable::BuildHTable(){
315 // build Htable
316 if(GetWordsNumber()){
317 for (Int_t i=0; i< fSize; i++) {
318 if (fCode[i] > 0.){
319 fNnodes++;
320 //cout<< "Symbol:"<<i<<" Freq:"<<fCode[i]<<endl;
321 fHNodes->Add(new AliTPCHNode(i,fCode[i]));
322 }//end if
323 }//end for
324 Int_t nentries=fHNodes->GetEntriesFast();
325 //cout<<"Number of symbols: "<<nentries<<endl;
326 Int_t nindex=nentries-1;
327 while (nindex > 0){
328 fHNodes->Sort(nindex+1);
329 AliTPCHNode *aux = new AliTPCHNode(0,0);
330 AliTPCHNode *node= (AliTPCHNode*)fHNodes->UncheckedAt(nindex-1);
331 AliTPCHNode *node1= (AliTPCHNode*)fHNodes->UncheckedAt(nindex);
332
333 aux->SetLeft(node);
334 aux->SetRight(node1);
335 aux->SetFrequency(node->GetFrequency() + node1->GetFrequency());
336 fHNodes->RemoveAt(nindex-1);
337 fHNodes->AddAt(aux,nindex-1);
338 nindex--;
339 }//end while
340 ClearTable();
341 AliTPCHNode *start= (AliTPCHNode*)fHNodes->UncheckedAt(0);
342 SpanTree(start,0,0);
343 }//end if
344 else{
345 cout<<"Table contains 0 elements\n";
346 }//end else
347 return 0;
348}
349
350//////////////////////////////////////////////////////////////////////////////