]>
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 | **************************************************************************/ | |
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 | 25 | ClassImp(AliITSHuffman) |
b0f5e3fc | 26 | |
27 | //_____________________________________________________________________________ | |
28 | ||
2574db5e | 29 | AliITSHuffman::AliITSHNode::AliITSHNode(): |
30 | TObject(), | |
31 | fSymbol(), | |
32 | fFrequency(0), | |
33 | fLeft(), | |
34 | fRight(), | |
35 | fFather() { | |
36 | // default constructor | |
b0f5e3fc | 37 | } |
38 | //_____________________________________________________________________________ | |
39 | ||
2574db5e | 40 | AliITSHuffman::AliITSHNode::AliITSHNode(UChar_t sym, ULong_t freq): |
41 | TObject(), | |
42 | fSymbol(sym), | |
43 | fFrequency(freq), | |
44 | fLeft(), | |
45 | fRight(), | |
46 | fFather() { | |
e8189707 | 47 | // standard constructor |
b0f5e3fc | 48 | } |
49 | ||
50 | //__________________________________________________________________________ | |
2574db5e | 51 | AliITSHuffman::AliITSHNode::AliITSHNode(const AliITSHNode &source): |
52 | TObject(source), | |
53 | fSymbol(source.fSymbol), | |
54 | fFrequency(source.fFrequency), | |
55 | fLeft(source.fLeft), | |
56 | fRight(source.fRight), | |
57 | fFather(source.fFather) { | |
b0f5e3fc | 58 | // Copy Constructor |
b0f5e3fc | 59 | return; |
60 | } | |
61 | ||
62 | //_________________________________________________________________________ | |
2574db5e | 63 | AliITSHuffman::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 | 76 | Int_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 | 91 | AliITSHuffman::AliITSHuffman(): |
92 | TObject(), | |
93 | fSize(0), | |
94 | fCodeLen(), | |
95 | fCode(), | |
96 | fSym(), | |
97 | fHNodes(), | |
98 | fNnodes(0) | |
b0f5e3fc | 99 | { |
2574db5e | 100 | // default constructor |
b0f5e3fc | 101 | |
102 | } | |
103 | //_____________________________________________________________________________ | |
104 | ||
2574db5e | 105 | AliITSHuffman::AliITSHuffman(Int_t size): |
106 | TObject(), | |
107 | fSize(size), | |
108 | fCodeLen(), | |
109 | fCode(), | |
110 | fSym(), | |
111 | fHNodes(), | |
112 | fNnodes(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 | 133 | AliITSHuffman::AliITSHuffman(const AliITSHuffman &source) : |
134 | TObject(source), | |
135 | fSize(source.fSize), | |
136 | fCodeLen(source.fCodeLen), | |
137 | fCode(source.fCode), | |
138 | fSym(source.fSym), | |
139 | fHNodes(source.fHNodes), | |
140 | fNnodes(source.fNnodes) | |
141 | { | |
b0f5e3fc | 142 | // Copy Constructor |
b0f5e3fc | 143 | } |
144 | ||
145 | //_________________________________________________________________________ | |
2574db5e | 146 | AliITSHuffman& |
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 | 160 | void 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 | 179 | void 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 | 231 | AliITSHuffman::~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 | 245 | Bool_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 | 273 | void 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 | 284 | void AliITSHuffman::ClearTable() |
b0f5e3fc | 285 | { |
286 | // clear | |
287 | memset(fCodeLen,0,sizeof(UChar_t)*fSize); | |
288 | memset(fCode,0,sizeof(ULong_t)*fSize); | |
289 | } | |
290 |