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