Fixes for Coverity warnings (M. van Leeuwen)
[u/mrichter/AliRoot.git] / ITS / AliITSHuffman.cxx
1 /**************************************************************************
2  * Copyright(c) 2006-2008, 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 /* $Id$ */
17
18 ////////////////////////////////////////////////
19 //                                            //
20 //  RawData classes for set:ITS               //
21 //                                            //
22 ////////////////////////////////////////////////
23
24 #include <TMath.h>
25 #include <TObjArray.h>
26 #include <Riostream.h>
27
28 #include "AliITSHuffman.h"
29
30 ClassImp(AliITSHuffman)
31
32 //_____________________________________________________________________________
33
34   AliITSHuffman::AliITSHNode::AliITSHNode(): 
35 TObject(),
36 fSymbol(),
37 fFrequency(0),
38 fLeft(),
39 fRight(),
40 fFather() {
41   // default constructor
42 }
43 //_____________________________________________________________________________
44
45 AliITSHuffman::AliITSHNode::AliITSHNode(UChar_t sym, ULong_t freq):
46 TObject(),
47 fSymbol(sym),
48 fFrequency(freq),
49 fLeft(),
50 fRight(),
51 fFather() {
52   // standard constructor
53 }
54
55 //__________________________________________________________________________
56 AliITSHuffman::AliITSHNode::AliITSHNode(const AliITSHNode &source): 
57 TObject(source),
58 fSymbol(source.fSymbol),
59 fFrequency(source.fFrequency),
60 fLeft(source.fLeft),
61 fRight(source.fRight),
62 fFather(source.fFather) {
63   //     Copy Constructor 
64   return;
65 }
66
67 //_________________________________________________________________________
68 AliITSHuffman::AliITSHNode& 
69   AliITSHuffman::AliITSHNode::operator=(const AliITSHuffman::AliITSHNode &source) {
70   //    Assignment operator
71   if(&source == this) return *this;
72   this->fSymbol = source.fSymbol;
73   this->fFrequency = source.fFrequency;
74   this->fLeft = source.fLeft;
75   this->fRight = source.fRight;
76   this->fFather = source.fFather;
77   return *this;
78 }
79
80 //____________________________________________
81 Int_t AliITSHuffman::AliITSHNode::Compare(const TObject *obj) const
82 {
83   // function called by Sort method of TObjArray
84
85          AliITSHNode *node=(AliITSHNode *)obj;
86          ULong_t f=fFrequency;
87          ULong_t fo=node->fFrequency;
88          if (f>fo) return 1;
89          else if (f<fo) return -1;
90          else return 0;
91 }
92
93
94 //_____________________________________________________________________________
95
96 AliITSHuffman::AliITSHuffman():
97 TObject(),
98 fSize(0),
99 fCodeLen(),
100 fCode(),
101 fSym(),
102 fHNodes(),
103 fNnodes(0)
104 {
105   // default constructor
106    
107 }
108 //_____________________________________________________________________________
109
110 AliITSHuffman::AliITSHuffman(Int_t size):
111 TObject(),
112 fSize(size),
113 fCodeLen(),
114 fCode(),
115 fSym(),
116 fHNodes(),
117 fNnodes(0)
118 {
119   //
120   // Creates the look-up table for the 1D compression
121   //
122
123   //initialise
124
125   fCodeLen = new UChar_t[fSize]; 
126   fCode = new ULong_t[fSize]; 
127   fHNodes = new TObjArray;
128   fNnodes=0;
129   fSym= new Short_t[fSize];
130   for (Short_t i=0;i<fSize;i++) {
131        fSym[i]=i;
132   }
133   ClearTable(); 
134
135 }
136
137 //__________________________________________________________________________
138 AliITSHuffman::AliITSHuffman(const AliITSHuffman &source) : 
139 TObject(source),
140 fSize(source.fSize),
141 fCodeLen(source.fCodeLen),
142 fCode(source.fCode),
143 fSym(source.fSym),
144 fHNodes(source.fHNodes),
145 fNnodes(source.fNnodes)
146 {
147   //     Copy Constructor 
148 }
149
150 //_________________________________________________________________________
151 AliITSHuffman& 
152   AliITSHuffman::operator=(const AliITSHuffman &source) {
153   //    Assignment operator
154   if(&source == this) return *this;
155   this->fSize = source.fSize;
156   this->fCodeLen = source.fCodeLen;
157   this->fCode = source.fCode;
158   this->fSym = source.fSym;
159   this->fHNodes = source.fHNodes;
160   this->fNnodes = source.fNnodes;
161   return *this;
162 }
163
164 //_____________________________________________________________________________
165 void AliITSHuffman::GetFrequencies(Int_t len, UChar_t *stream)
166 {
167   // get frequencies
168   printf("Get Frequencies: sym %p \n",(void*)fSym);
169
170   // use temporarily the fCode array to store the frequencies
171   for (Int_t i=0; i< len; i++) {
172       Int_t idx=TMath::BinarySearch(fSize,fSym,(Short_t)stream[i]);
173       if (idx == (Int_t)stream[i]) fCode[idx]++;
174       // test
175       if(idx==134) cout<< "idx fCode[idx]  "<<idx<<" "<<fCode[idx]<<endl;
176       //printf("idx,fCode[i] %d %d\n",idx,(Int_t)fCode[idx]);
177   }
178
179
180 }
181
182
183 //_____________________________________________________________________________
184 void AliITSHuffman::BuildHTable()
185 {
186   // build Htable
187
188   for (Int_t i=0; i< fSize; i++) {
189     //printf("i,fCode[i] %d %d\n",i,(Int_t)fCode[i]);
190      if (fCode[i] > 0) {
191         fNnodes++;
192         cout<< "i fCode[i] fNnodes "<<i<<" "<<fCode[i]<<" "<<fNnodes<<endl;
193         //printf("i, fCode[i] fNnodes %d %d %d\n",i,fCode[i],fNnodes);
194         fHNodes->Add(new AliITSHuffman::AliITSHNode((UChar_t)i,fCode[i]));
195      }
196   }
197
198   Int_t nentries=fHNodes->GetEntriesFast();
199   Int_t nindex=nentries-1;  
200   printf("nentries fNnodes nindex %d %d %d\n",nentries,fNnodes,nindex);
201
202   while (nindex > 0) 
203     {
204
205      fHNodes->Sort(nindex);
206      AliITSHNode *aux = new AliITSHNode(0,0);
207      AliITSHNode *node= (AliITSHNode*)fHNodes->UncheckedAt(nindex-1);
208      AliITSHNode *node1= (AliITSHNode*)fHNodes->UncheckedAt(nindex);
209      aux->SetLeft(node);
210      aux->SetRight(node1);
211      aux->SetFrequency(node->GetFrequency() + node1->GetFrequency());
212      printf("symbol symbol1 freq freq1 %d %d %d %d\n",(int)node->GetSymbol(),(int)node1->GetSymbol(),(int)node->GetFrequency(),(int)node1->GetFrequency());
213      cout << "aux - frequency "<< (Int_t)(aux->GetFrequency()) <<endl;
214      fHNodes->RemoveAt(nindex-1);
215      fHNodes->AddAt(aux,nindex-1);
216      nindex--;
217      printf("nindex, obj at nindex %d %p \n",nindex,(void*)fHNodes->UncheckedAt(nindex));
218
219     }
220
221     ClearTable();
222
223     AliITSHNode *start= (AliITSHNode*)fHNodes->UncheckedAt(0);
224     SpanTree(start,0,0);
225     
226     // check the Huffman table
227
228     cout << "...Done, Huffman Table is: \n";
229     for (int c=0; c <= 255; c++) {
230       if (fCodeLen[c] > 0) cout << "Symbol " << c << " Coded as " << fCode[c] << " and long " << (int) fCodeLen[c] << " bits.\n"; 
231     }
232
233 }
234
235 //_____________________________________________________________________________
236 AliITSHuffman::~AliITSHuffman()
237 {
238   // HTable
239     printf("HTable destructor !\n");
240     if (fCodeLen) delete[] fCodeLen;
241     if (fCode) delete [] fCode;
242     if (fHNodes) {
243       fHNodes->Delete();
244       delete fHNodes;
245     }
246 }
247
248
249 //____________________________________________
250 Bool_t AliITSHuffman::SpanTree(AliITSHNode *start, ULong_t code, UChar_t len)
251 {
252   // span tree
253   AliITSHNode * visited;
254   visited = start;
255
256   printf("outside: code, len %d %d\n",(int)code,(int)len);
257
258   Int_t idx=(Int_t)visited->GetSymbol();
259   if (!visited->GetLeft()) {
260         fCode[idx] = code; 
261         fCodeLen[idx] = len;
262         printf("idx, fCode[idx], fCodeLen[idx] %d %d %d\n",idx,(int)fCode[idx],
263               (int)fCodeLen[idx]);
264         return kTRUE;
265   }
266
267 // reccursive stuff
268
269   if (SpanTree(visited->GetLeft(), code << 1, len + 1)) {
270           printf("code, len %d %d\n",(int)code,(int)len);
271           if (visited->GetRight()) 
272                   SpanTree(visited->GetRight(), code << 1 | 0x01, len + 1);
273   }
274   return kTRUE;
275 }
276
277 //____________________________________________
278 void AliITSHuffman::ResetHNodes()
279 {
280     //
281     // Reset number of HNodes and the HNodes array 
282     //
283         if (fHNodes)  fHNodes->Clear();
284         if (fNnodes)  fNnodes=0;
285
286 }
287
288 //_____________________________________________________________________________
289 void AliITSHuffman::ClearTable()
290 {
291   // clear
292     memset(fCodeLen,0,sizeof(UChar_t)*fSize);
293     memset(fCode,0,sizeof(ULong_t)*fSize);
294 }
295