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