]>
Commit | Line | Data |
---|---|---|
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 | 30 | ClassImp(AliITSHuffman) |
b0f5e3fc | 31 | |
32 | //_____________________________________________________________________________ | |
33 | ||
2574db5e | 34 | AliITSHuffman::AliITSHNode::AliITSHNode(): |
35 | TObject(), | |
36 | fSymbol(), | |
37 | fFrequency(0), | |
38 | fLeft(), | |
39 | fRight(), | |
40 | fFather() { | |
41 | // default constructor | |
b0f5e3fc | 42 | } |
43 | //_____________________________________________________________________________ | |
44 | ||
2574db5e | 45 | AliITSHuffman::AliITSHNode::AliITSHNode(UChar_t sym, ULong_t freq): |
46 | TObject(), | |
47 | fSymbol(sym), | |
48 | fFrequency(freq), | |
49 | fLeft(), | |
50 | fRight(), | |
51 | fFather() { | |
e8189707 | 52 | // standard constructor |
b0f5e3fc | 53 | } |
54 | ||
55 | //__________________________________________________________________________ | |
2574db5e | 56 | AliITSHuffman::AliITSHNode::AliITSHNode(const AliITSHNode &source): |
57 | TObject(source), | |
58 | fSymbol(source.fSymbol), | |
59 | fFrequency(source.fFrequency), | |
60 | fLeft(source.fLeft), | |
61 | fRight(source.fRight), | |
62 | fFather(source.fFather) { | |
b0f5e3fc | 63 | // Copy Constructor |
b0f5e3fc | 64 | return; |
65 | } | |
66 | ||
67 | //_________________________________________________________________________ | |
2574db5e | 68 | AliITSHuffman::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 | 81 | Int_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 | 96 | AliITSHuffman::AliITSHuffman(): |
97 | TObject(), | |
98 | fSize(0), | |
99 | fCodeLen(), | |
100 | fCode(), | |
101 | fSym(), | |
102 | fHNodes(), | |
103 | fNnodes(0) | |
b0f5e3fc | 104 | { |
2574db5e | 105 | // default constructor |
b0f5e3fc | 106 | |
107 | } | |
108 | //_____________________________________________________________________________ | |
109 | ||
2574db5e | 110 | AliITSHuffman::AliITSHuffman(Int_t size): |
111 | TObject(), | |
112 | fSize(size), | |
113 | fCodeLen(), | |
114 | fCode(), | |
115 | fSym(), | |
116 | fHNodes(), | |
117 | fNnodes(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 | 138 | AliITSHuffman::AliITSHuffman(const AliITSHuffman &source) : |
139 | TObject(source), | |
140 | fSize(source.fSize), | |
141 | fCodeLen(source.fCodeLen), | |
142 | fCode(source.fCode), | |
143 | fSym(source.fSym), | |
144 | fHNodes(source.fHNodes), | |
145 | fNnodes(source.fNnodes) | |
146 | { | |
b0f5e3fc | 147 | // Copy Constructor |
b0f5e3fc | 148 | } |
149 | ||
150 | //_________________________________________________________________________ | |
2574db5e | 151 | AliITSHuffman& |
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 | 165 | void 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 | 184 | void 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 | 236 | AliITSHuffman::~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 | 250 | Bool_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 | 278 | void 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 | 289 | void AliITSHuffman::ClearTable() |
b0f5e3fc | 290 | { |
291 | // clear | |
292 | memset(fCodeLen,0,sizeof(UChar_t)*fSize); | |
293 | memset(fCode,0,sizeof(ULong_t)*fSize); | |
294 | } | |
295 |