Correct formula for phi, in case of current local X <0, in GetLocalXat and GetPhiZat
[u/mrichter/AliRoot.git] / ITS / AliITSHuffman.cxx
CommitLineData
2574db5e 1/**************************************************************************
2 * Copyright(c) 2006-2008, ALICE Experiment at CERN, All rights reserved. *
3 * *
4 * Author: The ALICE Off-line Project. *
5 * Contributors are mentioned in the code where appropriate. *
6 * *
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 **************************************************************************/
090026bf 15
16/* $Id$ */
17
b0f5e3fc 18////////////////////////////////////////////////
2574db5e 19// //
b0f5e3fc 20// RawData classes for set:ITS //
2574db5e 21// //
b0f5e3fc 22////////////////////////////////////////////////
23
090026bf 24#include <TMath.h>
92c19c36 25#include <TObjArray.h>
4ae5bbc4 26#include <Riostream.h>
090026bf 27
b0f5e3fc 28#include "AliITSHuffman.h"
b0f5e3fc 29
2574db5e 30ClassImp(AliITSHuffman)
b0f5e3fc 31
32//_____________________________________________________________________________
33
2574db5e 34 AliITSHuffman::AliITSHNode::AliITSHNode():
35TObject(),
36fSymbol(),
37fFrequency(0),
38fLeft(),
39fRight(),
40fFather() {
41 // default constructor
b0f5e3fc 42}
43//_____________________________________________________________________________
44
2574db5e 45AliITSHuffman::AliITSHNode::AliITSHNode(UChar_t sym, ULong_t freq):
46TObject(),
47fSymbol(sym),
48fFrequency(freq),
49fLeft(),
50fRight(),
51fFather() {
e8189707 52 // standard constructor
b0f5e3fc 53}
54
55//__________________________________________________________________________
2574db5e 56AliITSHuffman::AliITSHNode::AliITSHNode(const AliITSHNode &source):
57TObject(source),
58fSymbol(source.fSymbol),
59fFrequency(source.fFrequency),
60fLeft(source.fLeft),
61fRight(source.fRight),
62fFather(source.fFather) {
b0f5e3fc 63 // Copy Constructor
b0f5e3fc 64 return;
65}
66
67//_________________________________________________________________________
2574db5e 68AliITSHuffman::AliITSHNode&
69 AliITSHuffman::AliITSHNode::operator=(const AliITSHuffman::AliITSHNode &source) {
b0f5e3fc 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;
77 return *this;
78}
79
80//____________________________________________
2574db5e 81Int_t AliITSHuffman::AliITSHNode::Compare(const TObject *obj) const
b0f5e3fc 82{
83 // function called by Sort method of TObjArray
84
85 AliITSHNode *node=(AliITSHNode *)obj;
86 ULong_t f=fFrequency;
87 ULong_t fo=node->fFrequency;
88 if (f>fo) return 1;
89 else if (f<fo) return -1;
90 else return 0;
91}
b0f5e3fc 92
93
b0f5e3fc 94//_____________________________________________________________________________
95
2574db5e 96AliITSHuffman::AliITSHuffman():
97TObject(),
98fSize(0),
99fCodeLen(),
100fCode(),
101fSym(),
102fHNodes(),
103fNnodes(0)
b0f5e3fc 104{
2574db5e 105 // default constructor
b0f5e3fc 106
107}
108//_____________________________________________________________________________
109
2574db5e 110AliITSHuffman::AliITSHuffman(Int_t size):
111TObject(),
112fSize(size),
113fCodeLen(),
114fCode(),
115fSym(),
116fHNodes(),
117fNnodes(0)
b0f5e3fc 118{
119 //
120 // Creates the look-up table for the 1D compression
121 //
122
123 //initialise
124
b0f5e3fc 125 fCodeLen = new UChar_t[fSize];
126 fCode = new ULong_t[fSize];
127 fHNodes = new TObjArray;
128 fNnodes=0;
129 fSym= new Short_t[fSize];
e8189707 130 for (Short_t i=0;i<fSize;i++) {
b0f5e3fc 131 fSym[i]=i;
132 }
e8189707 133 ClearTable();
b0f5e3fc 134
135}
136
137//__________________________________________________________________________
2574db5e 138AliITSHuffman::AliITSHuffman(const AliITSHuffman &source) :
139TObject(source),
140fSize(source.fSize),
141fCodeLen(source.fCodeLen),
142fCode(source.fCode),
143fSym(source.fSym),
144fHNodes(source.fHNodes),
145fNnodes(source.fNnodes)
146{
b0f5e3fc 147 // Copy Constructor
b0f5e3fc 148}
149
150//_________________________________________________________________________
2574db5e 151AliITSHuffman&
152 AliITSHuffman::operator=(const AliITSHuffman &source) {
b0f5e3fc 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;
161 return *this;
162}
163
164//_____________________________________________________________________________
2574db5e 165void AliITSHuffman::GetFrequencies(Int_t len, UChar_t *stream)
b0f5e3fc 166{
167 // get frequencies
e81f4d4f 168 printf("Get Frequencies: sym %p \n",(void*)fSym);
b0f5e3fc 169
170 // use temporarily the fCode array to store the frequencies
e8189707 171 for (Int_t i=0; i< len; i++) {
b0f5e3fc 172 Int_t idx=TMath::BinarySearch(fSize,fSym,(Short_t)stream[i]);
173 if (idx == (Int_t)stream[i]) fCode[idx]++;
174 // test
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]);
177 }
178
179
180}
181
182
183//_____________________________________________________________________________
2574db5e 184void AliITSHuffman::BuildHTable()
b0f5e3fc 185{
186 // build Htable
187
e8189707 188 for (Int_t i=0; i< fSize; i++) {
b0f5e3fc 189 //printf("i,fCode[i] %d %d\n",i,(Int_t)fCode[i]);
190 if (fCode[i] > 0) {
191 fNnodes++;
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);
2574db5e 194 fHNodes->Add(new AliITSHuffman::AliITSHNode((UChar_t)i,fCode[i]));
b0f5e3fc 195 }
196 }
197
198 Int_t nentries=fHNodes->GetEntriesFast();
199 Int_t nindex=nentries-1;
200 printf("nentries fNnodes nindex %d %d %d\n",nentries,fNnodes,nindex);
201
202 while (nindex > 0)
203 {
204
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);
2574db5e 209 aux->SetLeft(node);
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;
b0f5e3fc 214 fHNodes->RemoveAt(nindex-1);
215 fHNodes->AddAt(aux,nindex-1);
216 nindex--;
e81f4d4f 217 printf("nindex, obj at nindex %d %p \n",nindex,(void*)fHNodes->UncheckedAt(nindex));
b0f5e3fc 218
219 }
220
e8189707 221 ClearTable();
b0f5e3fc 222
223 AliITSHNode *start= (AliITSHNode*)fHNodes->UncheckedAt(0);
224 SpanTree(start,0,0);
225
226 // check the Huffman table
227
228 cout << "...Done, Huffman Table is: \n";
e8189707 229 for (int c=0; c <= 255; c++) {
b0f5e3fc 230 if (fCodeLen[c] > 0) cout << "Symbol " << c << " Coded as " << fCode[c] << " and long " << (int) fCodeLen[c] << " bits.\n";
231 }
232
233}
234
235//_____________________________________________________________________________
2574db5e 236AliITSHuffman::~AliITSHuffman()
b0f5e3fc 237{
238 // HTable
239 printf("HTable destructor !\n");
240 if (fCodeLen) delete[] fCodeLen;
241 if (fCode) delete [] fCode;
e73fe7f3 242 if (fHNodes) {
243 fHNodes->Delete();
244 delete fHNodes;
245 }
b0f5e3fc 246}
247
248
249//____________________________________________
2574db5e 250Bool_t AliITSHuffman::SpanTree(AliITSHNode *start, ULong_t code, UChar_t len)
b0f5e3fc 251{
252 // span tree
253 AliITSHNode * visited;
254 visited = start;
255
256 printf("outside: code, len %d %d\n",(int)code,(int)len);
257
2574db5e 258 Int_t idx=(Int_t)visited->GetSymbol();
259 if (!visited->GetLeft()) {
b0f5e3fc 260 fCode[idx] = code;
261 fCodeLen[idx] = len;
262 printf("idx, fCode[idx], fCodeLen[idx] %d %d %d\n",idx,(int)fCode[idx],
263 (int)fCodeLen[idx]);
264 return kTRUE;
265 }
266
267// reccursive stuff
268
2574db5e 269 if (SpanTree(visited->GetLeft(), code << 1, len + 1)) {
b0f5e3fc 270 printf("code, len %d %d\n",(int)code,(int)len);
2574db5e 271 if (visited->GetRight())
272 SpanTree(visited->GetRight(), code << 1 | 0x01, len + 1);
b0f5e3fc 273 }
274 return kTRUE;
275}
276
277//____________________________________________
2574db5e 278void AliITSHuffman::ResetHNodes()
b0f5e3fc 279{
280 //
281 // Reset number of HNodes and the HNodes array
282 //
283 if (fHNodes) fHNodes->Clear();
284 if (fNnodes) fNnodes=0;
285
286}
287
288//_____________________________________________________________________________
2574db5e 289void AliITSHuffman::ClearTable()
b0f5e3fc 290{
291 // clear
292 memset(fCodeLen,0,sizeof(UChar_t)*fSize);
293 memset(fCode,0,sizeof(ULong_t)*fSize);
294}
295