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