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 **************************************************************************/
18 ////////////////////////////////////////////////
20 // RawData classes for set:ITS //
22 ////////////////////////////////////////////////
25 #include <TObjArray.h>
26 #include <Riostream.h>
28 #include "AliITSHuffman.h"
30 ClassImp(AliITSHuffman)
32 //_____________________________________________________________________________
34 AliITSHuffman::AliITSHNode::AliITSHNode():
41 // default constructor
43 //_____________________________________________________________________________
45 AliITSHuffman::AliITSHNode::AliITSHNode(UChar_t sym, ULong_t freq):
52 // standard constructor
55 //__________________________________________________________________________
56 AliITSHuffman::AliITSHNode::AliITSHNode(const AliITSHNode &source):
58 fSymbol(source.fSymbol),
59 fFrequency(source.fFrequency),
61 fRight(source.fRight),
62 fFather(source.fFather) {
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;
80 //____________________________________________
81 Int_t AliITSHuffman::AliITSHNode::Compare(const TObject *obj) const
83 // function called by Sort method of TObjArray
85 AliITSHNode *node=(AliITSHNode *)obj;
87 ULong_t fo=node->fFrequency;
89 else if (f<fo) return -1;
94 //_____________________________________________________________________________
96 AliITSHuffman::AliITSHuffman():
105 // default constructor
108 //_____________________________________________________________________________
110 AliITSHuffman::AliITSHuffman(Int_t size):
120 // Creates the look-up table for the 1D compression
125 fCodeLen = new UChar_t[fSize];
126 fCode = new ULong_t[fSize];
127 fHNodes = new TObjArray;
129 fSym= new Short_t[fSize];
130 for (Short_t i=0;i<fSize;i++) {
137 //__________________________________________________________________________
138 AliITSHuffman::AliITSHuffman(const AliITSHuffman &source) :
141 fCodeLen(source.fCodeLen),
144 fHNodes(source.fHNodes),
145 fNnodes(source.fNnodes)
150 //_________________________________________________________________________
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;
164 //_____________________________________________________________________________
165 void AliITSHuffman::GetFrequencies(Int_t len, UChar_t *stream)
168 printf("Get Frequencies: sym %p \n",(void*)fSym);
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]++;
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]);
183 //_____________________________________________________________________________
184 void AliITSHuffman::BuildHTable()
188 for (Int_t i=0; i< fSize; i++) {
189 //printf("i,fCode[i] %d %d\n",i,(Int_t)fCode[i]);
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]));
198 Int_t nentries=fHNodes->GetEntriesFast();
199 Int_t nindex=nentries-1;
200 printf("nentries fNnodes nindex %d %d %d\n",nentries,fNnodes,nindex);
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);
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);
217 printf("nindex, obj at nindex %d %p \n",nindex,(void*)fHNodes->UncheckedAt(nindex));
223 AliITSHNode *start= (AliITSHNode*)fHNodes->UncheckedAt(0);
226 // check the Huffman table
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";
235 //_____________________________________________________________________________
236 AliITSHuffman::~AliITSHuffman()
239 printf("HTable destructor !\n");
240 if (fCodeLen) delete[] fCodeLen;
241 if (fCode) delete [] fCode;
249 //____________________________________________
250 Bool_t AliITSHuffman::SpanTree(AliITSHNode *start, ULong_t code, UChar_t len)
253 AliITSHNode * visited;
256 printf("outside: code, len %d %d\n",(int)code,(int)len);
258 Int_t idx=(Int_t)visited->GetSymbol();
259 if (!visited->GetLeft()) {
262 printf("idx, fCode[idx], fCodeLen[idx] %d %d %d\n",idx,(int)fCode[idx],
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);
277 //____________________________________________
278 void AliITSHuffman::ResetHNodes()
281 // Reset number of HNodes and the HNodes array
283 if (fHNodes) fHNodes->Clear();
284 if (fNnodes) fNnodes=0;
288 //_____________________________________________________________________________
289 void AliITSHuffman::ClearTable()
292 memset(fCodeLen,0,sizeof(UChar_t)*fSize);
293 memset(fCode,0,sizeof(ULong_t)*fSize);