1 ////////////////////////////////////////////////
2 // RawData classes for set:ITS //
3 ////////////////////////////////////////////////
12 #include "AliITSHuffman.h"
13 #include "AliITSRawData.h"
17 //_____________________________________________________________________________
19 AliITSHNode::AliITSHNode()
26 //_____________________________________________________________________________
28 AliITSHNode::AliITSHNode(UChar_t sym, ULong_t freq)
30 // standard constructor
38 //__________________________________________________________________________
39 AliITSHNode::AliITSHNode(const AliITSHNode &source) : TObject(source){
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;
50 //_________________________________________________________________________
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;
63 //____________________________________________
64 Int_t AliITSHNode::Compare(const TObject *obj) const
66 // function called by Sort method of TObjArray
68 AliITSHNode *node=(AliITSHNode *)obj;
70 ULong_t fo=node->fFrequency;
72 else if (f<fo) return -1;
75 //_____________________________________________________________________________
78 ClassImp(AliITSHTable)
80 //_____________________________________________________________________________
82 AliITSHTable::AliITSHTable()
91 //_____________________________________________________________________________
93 AliITSHTable::AliITSHTable(Int_t size)
96 // Creates the look-up table for the 1D compression
102 fCodeLen = new UChar_t[fSize];
103 fCode = new ULong_t[fSize];
104 fHNodes = new TObjArray;
106 fSym= new Short_t[fSize];
107 for (Short_t i=0;i<fSize;i++) {
114 //__________________________________________________________________________
115 AliITSHTable::AliITSHTable(const AliITSHTable &source) : TObject(source){
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;
127 //_________________________________________________________________________
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;
141 //_____________________________________________________________________________
142 void AliITSHTable::GetFrequencies(Int_t len, UChar_t *stream)
145 printf("Get Frequencies: sym %p \n",fSym);
147 // use temporarily the fCode array to store the frequencies
148 for (Int_t i=0; i< len; i++) {
149 Int_t idx=TMath::BinarySearch(fSize,fSym,(Short_t)stream[i]);
150 if (idx == (Int_t)stream[i]) fCode[idx]++;
152 if(idx==134) cout<< "idx fCode[idx] "<<idx<<" "<<fCode[idx]<<endl;
153 //printf("idx,fCode[i] %d %d\n",idx,(Int_t)fCode[idx]);
160 //_____________________________________________________________________________
161 void AliITSHTable::BuildHTable()
165 for (Int_t i=0; i< fSize; i++) {
166 //printf("i,fCode[i] %d %d\n",i,(Int_t)fCode[i]);
169 cout<< "i fCode[i] fNnodes "<<i<<" "<<fCode[i]<<" "<<fNnodes<<endl;
170 //printf("i, fCode[i] fNnodes %d %d %d\n",i,fCode[i],fNnodes);
171 fHNodes->Add(new AliITSHNode((UChar_t)i,fCode[i]));
175 Int_t nentries=fHNodes->GetEntriesFast();
176 Int_t nindex=nentries-1;
177 printf("nentries fNnodes nindex %d %d %d\n",nentries,fNnodes,nindex);
182 fHNodes->Sort(nindex);
183 AliITSHNode *aux = new AliITSHNode(0,0);
184 AliITSHNode *node= (AliITSHNode*)fHNodes->UncheckedAt(nindex-1);
185 AliITSHNode *node1= (AliITSHNode*)fHNodes->UncheckedAt(nindex);
188 aux->fFrequency = node->fFrequency + node1->fFrequency;
189 printf("symbol symbol1 freq freq1 %d %d %d %d\n",(int)node->fSymbol,(int)node1->fSymbol,(int)node->fFrequency,(int)node1->fFrequency);
190 cout << "aux - frequency "<< (Int_t)(aux->fFrequency) <<endl;
191 fHNodes->RemoveAt(nindex-1);
192 fHNodes->AddAt(aux,nindex-1);
194 printf("nindex, obj at nindex %d %p \n",nindex,(AliITSHNode*)fHNodes->UncheckedAt(nindex));
200 AliITSHNode *start= (AliITSHNode*)fHNodes->UncheckedAt(0);
203 // check the Huffman table
205 cout << "...Done, Huffman Table is: \n";
206 for (int c=0; c <= 255; c++) {
207 if (fCodeLen[c] > 0) cout << "Symbol " << c << " Coded as " << fCode[c] << " and long " << (int) fCodeLen[c] << " bits.\n";
212 //_____________________________________________________________________________
213 AliITSHTable::~AliITSHTable()
216 printf("HTable destructor !\n");
217 if (fCodeLen) delete[] fCodeLen;
218 if (fCode) delete [] fCode;
226 //____________________________________________
227 Bool_t AliITSHTable::SpanTree(AliITSHNode *start, ULong_t code, UChar_t len)
230 AliITSHNode * visited;
233 printf("outside: code, len %d %d\n",(int)code,(int)len);
235 Int_t idx=(Int_t)visited->fSymbol;
236 if (!visited->fLeft) {
239 printf("idx, fCode[idx], fCodeLen[idx] %d %d %d\n",idx,(int)fCode[idx],
246 if (SpanTree(visited->fLeft, code << 1, len + 1)) {
247 printf("code, len %d %d\n",(int)code,(int)len);
249 SpanTree(visited->fRight, code << 1 | 0x01, len + 1);
254 //____________________________________________
255 void AliITSHTable::ResetHNodes()
258 // Reset number of HNodes and the HNodes array
260 if (fHNodes) fHNodes->Clear();
261 if (fNnodes) fNnodes=0;
265 //_____________________________________________________________________________
266 void AliITSHTable::ClearTable()
269 memset(fCodeLen,0,sizeof(UChar_t)*fSize);
270 memset(fCode,0,sizeof(ULong_t)*fSize);