1 /**************************************************************************
2 * Copyright(c) 2006-2008, ALICE Experiment at CERN, All rights reserved. *
4 * Author: The ALICE Off-line Project. *
5 * Contributors are mentioned in the code where appropriate. *
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 ////////////////////////////////////////////////
17 // RawData classes for set:ITS //
19 ////////////////////////////////////////////////
21 #include <TObjArray.h>
22 #include <Riostream.h>
23 #include "AliITSHuffman.h"
25 ClassImp(AliITSHuffman)
27 //_____________________________________________________________________________
29 AliITSHuffman::AliITSHNode::AliITSHNode():
36 // default constructor
38 //_____________________________________________________________________________
40 AliITSHuffman::AliITSHNode::AliITSHNode(UChar_t sym, ULong_t freq):
47 // standard constructor
50 //__________________________________________________________________________
51 AliITSHuffman::AliITSHNode::AliITSHNode(const AliITSHNode &source):
53 fSymbol(source.fSymbol),
54 fFrequency(source.fFrequency),
56 fRight(source.fRight),
57 fFather(source.fFather) {
62 //_________________________________________________________________________
63 AliITSHuffman::AliITSHNode&
64 AliITSHuffman::AliITSHNode::operator=(const AliITSHuffman::AliITSHNode &source) {
65 // Assignment operator
66 if(&source == this) return *this;
67 this->fSymbol = source.fSymbol;
68 this->fFrequency = source.fFrequency;
69 this->fLeft = source.fLeft;
70 this->fRight = source.fRight;
71 this->fFather = source.fFather;
75 //____________________________________________
76 Int_t AliITSHuffman::AliITSHNode::Compare(const TObject *obj) const
78 // function called by Sort method of TObjArray
80 AliITSHNode *node=(AliITSHNode *)obj;
82 ULong_t fo=node->fFrequency;
84 else if (f<fo) return -1;
89 //_____________________________________________________________________________
91 AliITSHuffman::AliITSHuffman():
100 // default constructor
103 //_____________________________________________________________________________
105 AliITSHuffman::AliITSHuffman(Int_t size):
115 // Creates the look-up table for the 1D compression
120 fCodeLen = new UChar_t[fSize];
121 fCode = new ULong_t[fSize];
122 fHNodes = new TObjArray;
124 fSym= new Short_t[fSize];
125 for (Short_t i=0;i<fSize;i++) {
132 //__________________________________________________________________________
133 AliITSHuffman::AliITSHuffman(const AliITSHuffman &source) :
136 fCodeLen(source.fCodeLen),
139 fHNodes(source.fHNodes),
140 fNnodes(source.fNnodes)
145 //_________________________________________________________________________
147 AliITSHuffman::operator=(const AliITSHuffman &source) {
148 // Assignment operator
149 if(&source == this) return *this;
150 this->fSize = source.fSize;
151 this->fCodeLen = source.fCodeLen;
152 this->fCode = source.fCode;
153 this->fSym = source.fSym;
154 this->fHNodes = source.fHNodes;
155 this->fNnodes = source.fNnodes;
159 //_____________________________________________________________________________
160 void AliITSHuffman::GetFrequencies(Int_t len, UChar_t *stream)
163 printf("Get Frequencies: sym %p \n",(void*)fSym);
165 // use temporarily the fCode array to store the frequencies
166 for (Int_t i=0; i< len; i++) {
167 Int_t idx=TMath::BinarySearch(fSize,fSym,(Short_t)stream[i]);
168 if (idx == (Int_t)stream[i]) fCode[idx]++;
170 if(idx==134) cout<< "idx fCode[idx] "<<idx<<" "<<fCode[idx]<<endl;
171 //printf("idx,fCode[i] %d %d\n",idx,(Int_t)fCode[idx]);
178 //_____________________________________________________________________________
179 void AliITSHuffman::BuildHTable()
183 for (Int_t i=0; i< fSize; i++) {
184 //printf("i,fCode[i] %d %d\n",i,(Int_t)fCode[i]);
187 cout<< "i fCode[i] fNnodes "<<i<<" "<<fCode[i]<<" "<<fNnodes<<endl;
188 //printf("i, fCode[i] fNnodes %d %d %d\n",i,fCode[i],fNnodes);
189 fHNodes->Add(new AliITSHuffman::AliITSHNode((UChar_t)i,fCode[i]));
193 Int_t nentries=fHNodes->GetEntriesFast();
194 Int_t nindex=nentries-1;
195 printf("nentries fNnodes nindex %d %d %d\n",nentries,fNnodes,nindex);
200 fHNodes->Sort(nindex);
201 AliITSHNode *aux = new AliITSHNode(0,0);
202 AliITSHNode *node= (AliITSHNode*)fHNodes->UncheckedAt(nindex-1);
203 AliITSHNode *node1= (AliITSHNode*)fHNodes->UncheckedAt(nindex);
205 aux->SetRight(node1);
206 aux->SetFrequency(node->GetFrequency() + node1->GetFrequency());
207 printf("symbol symbol1 freq freq1 %d %d %d %d\n",(int)node->GetSymbol(),(int)node1->GetSymbol(),(int)node->GetFrequency(),(int)node1->GetFrequency());
208 cout << "aux - frequency "<< (Int_t)(aux->GetFrequency()) <<endl;
209 fHNodes->RemoveAt(nindex-1);
210 fHNodes->AddAt(aux,nindex-1);
212 printf("nindex, obj at nindex %d %p \n",nindex,(void*)fHNodes->UncheckedAt(nindex));
218 AliITSHNode *start= (AliITSHNode*)fHNodes->UncheckedAt(0);
221 // check the Huffman table
223 cout << "...Done, Huffman Table is: \n";
224 for (int c=0; c <= 255; c++) {
225 if (fCodeLen[c] > 0) cout << "Symbol " << c << " Coded as " << fCode[c] << " and long " << (int) fCodeLen[c] << " bits.\n";
230 //_____________________________________________________________________________
231 AliITSHuffman::~AliITSHuffman()
234 printf("HTable destructor !\n");
235 if (fCodeLen) delete[] fCodeLen;
236 if (fCode) delete [] fCode;
244 //____________________________________________
245 Bool_t AliITSHuffman::SpanTree(AliITSHNode *start, ULong_t code, UChar_t len)
248 AliITSHNode * visited;
251 printf("outside: code, len %d %d\n",(int)code,(int)len);
253 Int_t idx=(Int_t)visited->GetSymbol();
254 if (!visited->GetLeft()) {
257 printf("idx, fCode[idx], fCodeLen[idx] %d %d %d\n",idx,(int)fCode[idx],
264 if (SpanTree(visited->GetLeft(), code << 1, len + 1)) {
265 printf("code, len %d %d\n",(int)code,(int)len);
266 if (visited->GetRight())
267 SpanTree(visited->GetRight(), code << 1 | 0x01, len + 1);
272 //____________________________________________
273 void AliITSHuffman::ResetHNodes()
276 // Reset number of HNodes and the HNodes array
278 if (fHNodes) fHNodes->Clear();
279 if (fNnodes) fNnodes=0;
283 //_____________________________________________________________________________
284 void AliITSHuffman::ClearTable()
287 memset(fCodeLen,0,sizeof(UChar_t)*fSize);
288 memset(fCode,0,sizeof(ULong_t)*fSize);