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 //                                            //
  17 //  RawData classes for set:ITS               //
  18 //                                            //
  19 ////////////////////////////////////////////////
  20
  21 #include <TObjArray.h>
  22 #include <Riostream.h>
  23 #include "AliITSHuffman.h"
  24
  25 ClassImp(AliITSHuffman)
  26
  27 //_____________________________________________________________________________
  28
  29   AliITSHuffman::AliITSHNode::AliITSHNode():
  30 TObject(),
  31 fSymbol(),
  32 fFrequency(0),
  33 fLeft(),
  34 fRight(),
  35 fFather() {
  36   // default constructor
  37 }
  38 //_____________________________________________________________________________
  39
  40 AliITSHuffman::AliITSHNode::AliITSHNode(UChar_t sym, ULong_t freq):
  41 TObject(),
  42 fSymbol(sym),
  43 fFrequency(freq),
  44 fLeft(),
  45 fRight(),
  46 fFather() {
  47   // standard constructor
  48 }
  49
  50 //__________________________________________________________________________
  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) {
  58   //     Copy Constructor
  59   return;
  60 }
  61
  62 //_________________________________________________________________________
  63 AliITSHuffman::AliITSHNode&
  64   AliITSHuffman::AliITSHNode::operator=(const AliITSHuffman::AliITSHNode &source) {
  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 //____________________________________________
  76 Int_t AliITSHuffman::AliITSHNode::Compare(const TObject *obj) const
  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 }
  87
  88
  89 //_____________________________________________________________________________
  90
  91 AliITSHuffman::AliITSHuffman():
  92 TObject(),
  93 fSize(0),
  94 fCodeLen(),
  95 fCode(),
  96 fSym(),
  97 fHNodes(),
  98 fNnodes(0)
  99 {
 100   // default constructor
 101
 102 }
 103 //_____________________________________________________________________________
 104
 105 AliITSHuffman::AliITSHuffman(Int_t size):
 106 TObject(),
 107 fSize(size),
 108 fCodeLen(),
 109 fCode(),
 110 fSym(),
 111 fHNodes(),
 112 fNnodes(0)
 113 {
 114   //
 115   // Creates the look-up table for the 1D compression
 116   //
 117
 118   //initialise
 119
 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];
 125   for (Short_t i=0;i<fSize;i++) {
 126        fSym[i]=i;
 127   }
 128   ClearTable();
 129
 130 }
 131
 132 //__________________________________________________________________________
 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 {
 142   //     Copy Constructor
 143 }
 144
 145 //_________________________________________________________________________
 146 AliITSHuffman&
 147   AliITSHuffman::operator=(const AliITSHuffman &source) {
 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 //_____________________________________________________________________________
 160 void AliITSHuffman::GetFrequencies(Int_t len, UChar_t *stream)
 161 {
 162   // get frequencies
 163   printf("Get Frequencies: sym %p \n",(void*)fSym);
 164
 165   // use temporarily the fCode array to store the frequencies
 166   for (Int_t i=0; i< len; i++) {
 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 //_____________________________________________________________________________
 179 void AliITSHuffman::BuildHTable()
 180 {
 181   // build Htable
 182
 183   for (Int_t i=0; i< fSize; i++) {
 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);
 189         fHNodes->Add(new AliITSHuffman::AliITSHNode((UChar_t)i,fCode[i]));
 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);
 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;
 209      fHNodes->RemoveAt(nindex-1);
 210      fHNodes->AddAt(aux,nindex-1);
 211      nindex--;
 212      printf("nindex, obj at nindex %d %p \n",nindex,(void*)fHNodes->UncheckedAt(nindex));
 213
 214     }
 215
 216     ClearTable();
 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";
 224     for (int c=0; c <= 255; c++) {
 225       if (fCodeLen[c] > 0) cout << "Symbol " << c << " Coded as " << fCode[c] << " and long " << (int) fCodeLen[c] << " bits.\n";
 226     }
 227
 228 }
 229
 230 //_____________________________________________________________________________
 231 AliITSHuffman::~AliITSHuffman()
 232 {
 233   // HTable
 234     printf("HTable destructor !\n");
 235     if (fCodeLen) delete[] fCodeLen;
 236     if (fCode) delete [] fCode;
 237     if (fHNodes) {
 238       fHNodes->Delete();
 239       delete fHNodes;
 240     }
 241 }
 242
 243
 244 //____________________________________________
 245 Bool_t AliITSHuffman::SpanTree(AliITSHNode *start, ULong_t code, UChar_t len)
 246 {
 247   // span tree
 248   AliITSHNode * visited;
 249   visited = start;
 250
 251   printf("outside: code, len %d %d\n",(int)code,(int)len);
 252
 253   Int_t idx=(Int_t)visited->GetSymbol();
 254   if (!visited->GetLeft()) {
 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
 264   if (SpanTree(visited->GetLeft(), code << 1, len + 1)) {
 265           printf("code, len %d %d\n",(int)code,(int)len);
 266           if (visited->GetRight())
 267                   SpanTree(visited->GetRight(), code << 1 | 0x01, len + 1);
 268   }
 269   return kTRUE;
 270 }
 271
 272 //____________________________________________
 273 void AliITSHuffman::ResetHNodes()
 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 //_____________________________________________________________________________
 284 void AliITSHuffman::ClearTable()
 285 {
 286   // clear
 287     memset(fCodeLen,0,sizeof(UChar_t)*fSize);
 288     memset(fCode,0,sizeof(ULong_t)*fSize);
 289 }
 290