ITS/AliITSHuffman.cxx

   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  **************************************************************************/
  15
  16 /* $Id$ */
  17
  18 ////////////////////////////////////////////////
  19 //                                            //
  20 //  RawData classes for set:ITS               //
  21 //                                            //
  22 ////////////////////////////////////////////////
  23
  24 #include <TMath.h>
  25 #include <TObjArray.h>
  26 #include <Riostream.h>
  27
  28 #include "AliITSHuffman.h"
  29
  30 ClassImp(AliITSHuffman)
  31
  32 //_____________________________________________________________________________
  33
  34   AliITSHuffman::AliITSHNode::AliITSHNode():
  35 TObject(),
  36 fSymbol(),
  37 fFrequency(0),
  38 fLeft(),
  39 fRight(),
  40 fFather() {
  41   // default constructor
  42 }
  43 //_____________________________________________________________________________
  44
  45 AliITSHuffman::AliITSHNode::AliITSHNode(UChar_t sym, ULong_t freq):
  46 TObject(),
  47 fSymbol(sym),
  48 fFrequency(freq),
  49 fLeft(),
  50 fRight(),
  51 fFather() {
  52   // standard constructor
  53 }
  54
  55 //__________________________________________________________________________
  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) {
  63   //     Copy Constructor
  64   return;
  65 }
  66
  67 //_________________________________________________________________________
  68 AliITSHuffman::AliITSHNode&
  69   AliITSHuffman::AliITSHNode::operator=(const AliITSHuffman::AliITSHNode &source) {
  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 //____________________________________________
  81 Int_t AliITSHuffman::AliITSHNode::Compare(const TObject *obj) const
  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 }
  92
  93
  94 //_____________________________________________________________________________
  95
  96 AliITSHuffman::AliITSHuffman():
  97 TObject(),
  98 fSize(0),
  99 fCodeLen(),
 100 fCode(),
 101 fSym(),
 102 fHNodes(),
 103 fNnodes(0)
 104 {
 105   // default constructor
 106
 107 }
 108 //_____________________________________________________________________________
 109
 110 AliITSHuffman::AliITSHuffman(Int_t size):
 111 TObject(),
 112 fSize(size),
 113 fCodeLen(),
 114 fCode(),
 115 fSym(),
 116 fHNodes(),
 117 fNnodes(0)
 118 {
 119   //
 120   // Creates the look-up table for the 1D compression
 121   //
 122
 123   //initialise
 124
 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];
 130   for (Short_t i=0;i<fSize;i++) {
 131        fSym[i]=i;
 132   }
 133   ClearTable();
 134
 135 }
 136
 137 //__________________________________________________________________________
 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 {
 147   //     Copy Constructor
 148 }
 149
 150 //_________________________________________________________________________
 151 AliITSHuffman&
 152   AliITSHuffman::operator=(const AliITSHuffman &source) {
 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 //_____________________________________________________________________________
 165 void AliITSHuffman::GetFrequencies(Int_t len, UChar_t *stream)
 166 {
 167   // get frequencies
 168   printf("Get Frequencies: sym %p \n",(void*)fSym);
 169
 170   // use temporarily the fCode array to store the frequencies
 171   for (Int_t i=0; i< len; i++) {
 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 //_____________________________________________________________________________
 184 void AliITSHuffman::BuildHTable()
 185 {
 186   // build Htable
 187
 188   for (Int_t i=0; i< fSize; i++) {
 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);
 194         fHNodes->Add(new AliITSHuffman::AliITSHNode((UChar_t)i,fCode[i]));
 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);
 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;
 214      fHNodes->RemoveAt(nindex-1);
 215      fHNodes->AddAt(aux,nindex-1);
 216      nindex--;
 217      printf("nindex, obj at nindex %d %p \n",nindex,(void*)fHNodes->UncheckedAt(nindex));
 218
 219     }
 220
 221     ClearTable();
 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";
 229     for (int c=0; c <= 255; c++) {
 230       if (fCodeLen[c] > 0) cout << "Symbol " << c << " Coded as " << fCode[c] << " and long " << (int) fCodeLen[c] << " bits.\n";
 231     }
 232
 233 }
 234
 235 //_____________________________________________________________________________
 236 AliITSHuffman::~AliITSHuffman()
 237 {
 238   // HTable
 239     printf("HTable destructor !\n");
 240     if (fCodeLen) delete[] fCodeLen;
 241     if (fCode) delete [] fCode;
 242     if (fHNodes) {
 243       fHNodes->Delete();
 244       delete fHNodes;
 245     }
 246 }
 247
 248
 249 //____________________________________________
 250 Bool_t AliITSHuffman::SpanTree(AliITSHNode *start, ULong_t code, UChar_t len)
 251 {
 252   // span tree
 253   AliITSHNode * visited;
 254   visited = start;
 255
 256   printf("outside: code, len %d %d\n",(int)code,(int)len);
 257
 258   Int_t idx=(Int_t)visited->GetSymbol();
 259   if (!visited->GetLeft()) {
 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
 269   if (SpanTree(visited->GetLeft(), code << 1, len + 1)) {
 270           printf("code, len %d %d\n",(int)code,(int)len);
 271           if (visited->GetRight())
 272                   SpanTree(visited->GetRight(), code << 1 | 0x01, len + 1);
 273   }
 274   return kTRUE;
 275 }
 276
 277 //____________________________________________
 278 void AliITSHuffman::ResetHNodes()
 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 //_____________________________________________________________________________
 289 void AliITSHuffman::ClearTable()
 290 {
 291   // clear
 292     memset(fCodeLen,0,sizeof(UChar_t)*fSize);
 293     memset(fCode,0,sizeof(ULong_t)*fSize);
 294 }
 295