]> git.uio.no Git - u/mrichter/AliRoot.git/blob - ITS/AliITSHuffman.cxx
New ITS code for new structure and simulations.
[u/mrichter/AliRoot.git] / ITS / AliITSHuffman.cxx
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
15 ClassImp(AliITSHNode)
16
17 //_____________________________________________________________________________
18
19 AliITSHNode::AliITSHNode()
20 {
21   // constructor
22     fLeft=0;
23     fRight=0;
24     fFather=0;
25 }
26 //_____________________________________________________________________________
27
28 AliITSHNode::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 //__________________________________________________________________________
39 AliITSHNode::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 //_________________________________________________________________________
51 AliITSHNode& 
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 //____________________________________________
64 Int_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
78 ClassImp(AliITSHTable)
79
80 //_____________________________________________________________________________
81
82 AliITSHTable::AliITSHTable()
83 {
84   // constructor
85     fCodeLen=0;
86     fCode=0;
87     fHNodes=0;
88     fNnodes=0;
89    
90 }
91 //_____________________________________________________________________________
92
93 AliITSHTable::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 //__________________________________________________________________________
115 AliITSHTable::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 //_________________________________________________________________________
128 AliITSHTable& 
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 //_____________________________________________________________________________
142 void 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 //_____________________________________________________________________________
162 void 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 //_____________________________________________________________________________
216 AliITSHTable::~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 //____________________________________________
227 Bool_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 //____________________________________________
255 void 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 //_____________________________________________________________________________
266 void AliITSHTable::Clear()
267 {
268   // clear
269     memset(fCodeLen,0,sizeof(UChar_t)*fSize);
270     memset(fCode,0,sizeof(ULong_t)*fSize);
271 }
272
273 //___________________________________________________________________________
274 void 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