ITS/AliITSHuffman.cxx

   1 ////////////////////////////////////////////////
   2 //  RawData classes for set:ITS               //
   3 ////////////////////////////////////////////////
   4
   5 #include <TMath.h>
   6 #include <TObjArray.h>
   7 #include <iostream.h>
   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 {
  30   // standard constructor
  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 //____________________________________________
  64 Int_t AliITSHNode::Compare(const TObject *obj) const
  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];
 107   for (Short_t i=0;i<fSize;i++) {
 108        fSym[i]=i;
 109   }
 110   ClearTable();
 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
 148   for (Int_t i=0; i< len; i++) {
 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
 165   for (Int_t i=0; i< fSize; i++) {
 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
 198     ClearTable();
 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";
 206     for (int c=0; c <= 255; c++) {
 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;
 219     if (fHNodes) {
 220       fHNodes->Delete();
 221       delete fHNodes;
 222     }
 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 //_____________________________________________________________________________
 266 void AliITSHTable::ClearTable()
 267 {
 268   // clear
 269     memset(fCodeLen,0,sizeof(UChar_t)*fSize);
 270     memset(fCode,0,sizeof(ULong_t)*fSize);
 271 }
 272