TPC/AliTPCHuffman.cxx

   1 /**************************************************************************
   2  * Copyright(c) 1998-2003, 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 //  Huffman classes for set:TPC               //
  18 ////////////////////////////////////////////////
  19
  20 #include <TObjArray.h>
  21 #include "Riostream.h"
  22 #include "TMath.h"
  23 #include "AliTPCHuffman.h"
  24 #include "AliTPCBuffer160.h"
  25
  26 ClassImp(AliTPCHNode)
  27
  28 AliTPCHNode::AliTPCHNode(){
  29   // constructor
  30   fLeft=0;
  31   fRight=0;
  32 }
  33
  34 //////////////////////////////////////////////////////////////////////////////
  35
  36 AliTPCHNode::AliTPCHNode(Int_t sym, Double_t freq){
  37   // standard constructor
  38   fSymbol=sym;
  39   fFrequency=freq;
  40   fLeft=0;
  41   fRight=0;
  42 }
  43
  44 //////////////////////////////////////////////////////////////////////////////
  45
  46 AliTPCHNode::AliTPCHNode(const AliTPCHNode &source){
  47   //     Copy Constructor
  48   if(&source == this) return;
  49   this->fSymbol = source.fSymbol;
  50   this->fFrequency = source.fFrequency;
  51   this->fLeft = source.fLeft;
  52   this->fRight = source.fRight;
  53   return;
  54 }
  55
  56 //////////////////////////////////////////////////////////////////////////////
  57
  58 AliTPCHNode& AliTPCHNode::operator=(const AliTPCHNode &source){
  59   //    Assignment operator
  60   if(&source == this) return *this;
  61   this->fSymbol = source.fSymbol;
  62   this->fFrequency = source.fFrequency;
  63   this->fLeft = source.fLeft;
  64   this->fRight = source.fRight;
  65   return *this;
  66 }
  67
  68 //////////////////////////////////////////////////////////////////////////////
  69
  70 Int_t AliTPCHNode::Compare(const TObject *obj)const{
  71   // function called by Sort method of TObjArray
  72   AliTPCHNode *node=(AliTPCHNode *)obj;
  73   Double_t f=fFrequency;
  74   Double_t fo=node->fFrequency;
  75   if (f<fo) return 1;
  76   else if (f>fo) return -1;
  77   else return 0;
  78 }
  79
  80 //////////////////////////////////////////////////////////////////////////////
  81 //////////////////////////////////////////////////////////////////////////////
  82 //////////////////////////////////////////////////////////////////////////////
  83
  84 ClassImp(AliTPCHTable)
  85
  86 AliTPCHTable::AliTPCHTable(){
  87   // constructor
  88   fCodeLen=0;
  89   fCode=0;
  90   fHNodes=0;
  91   fNnodes=0;
  92   fNum=0;
  93   fVerbose=0;
  94 }
  95
  96 //////////////////////////////////////////////////////////////////////////////
  97
  98 AliTPCHTable::AliTPCHTable(Int_t size){
  99   //initialise
 100   fSize=size;
 101   fCodeLen = new UChar_t[fSize];
 102   fCode = new Double_t[fSize];
 103   fHNodes = new TObjArray;
 104   fNnodes=0;
 105   fNum=0;
 106   fVerbose=0;
 107   fSym= new Short_t[fSize];
 108   for (Short_t i=0;i<fSize;i++) {
 109     fSym[i]=i;
 110   }//end for
 111   ClearTable();
 112 }
 113
 114 //////////////////////////////////////////////////////////////////////////////
 115
 116 AliTPCHTable::AliTPCHTable(const AliTPCHTable &source){
 117   //     Copy Constructor
 118   if(&source == this) return;
 119   this->fSize = source.fSize;
 120   this->fCodeLen = source.fCodeLen;
 121   this->fCode = source.fCode;
 122   this->fSym = source.fSym;
 123   this->fHNodes = source.fHNodes;
 124   this->fNnodes = source.fNnodes;
 125   this->fNum=source.fNum;
 126   this->fVerbose=source.fVerbose;
 127   return;
 128 }
 129
 130 //////////////////////////////////////////////////////////////////////////////
 131
 132 AliTPCHTable& AliTPCHTable::operator=(const AliTPCHTable &source) {
 133   //    Assignment operator
 134   if(&source == this) return *this;
 135   this->fSize = source.fSize;
 136   this->fCodeLen = source.fCodeLen;
 137   this->fCode = source.fCode;
 138   this->fSym = source.fSym;
 139   this->fHNodes = source.fHNodes;
 140   this->fNnodes = source.fNnodes;
 141   this->fNum=source.fNum;
 142   this->fVerbose=source.fVerbose;
 143   return *this;
 144 }
 145
 146 //////////////////////////////////////////////////////////////////////////////
 147
 148 AliTPCHTable::~AliTPCHTable(){
 149   // HTable
 150   if(fVerbose)
 151     cout<<"HTable destructor !\n";
 152   if (fCodeLen) delete[] fCodeLen;
 153   if (fCode) delete [] fCode;
 154   if (fHNodes) {
 155     fHNodes->Delete(); //Clear out the collection and deletes the removed objects
 156     delete fHNodes;
 157   }//end if
 158 }
 159
 160 //////////////////////////////////////////////////////////////////////////////
 161
 162 void AliTPCHTable::SetCodeLen(UChar_t len,Int_t val){
 163   fCodeLen[val]=len;
 164   return;
 165 }
 166
 167 //////////////////////////////////////////////////////////////////////////////
 168
 169 void AliTPCHTable::SetCode(Double_t code,Int_t val){
 170   fCode[val]=code;
 171   return;
 172 }
 173
 174 //////////////////////////////////////////////////////////////////////////////
 175
 176 void AliTPCHTable::PrintTable()const{
 177   cout<<"Table for Huffman coding\n";
 178   cout<<"  Symbol|   Code   |   Length \n";
 179   for (Int_t i=0;i<fSize;i++){
 180     if (fCodeLen[i]){
 181       cout.width(6);cout<<fSym[i];
 182       cout.width(3);cout<<"|";
 183       cout.width(6);cout<<hex<<(ULong_t)fCode[i]<<dec;
 184       cout.width(5);cout<<"|";
 185       cout.width(6);cout<<(ULong_t)fCodeLen[i]<<endl;
 186     }//end if
 187   }//end for
 188 }
 189
 190 //////////////////////////////////////////////////////////////////////////////
 191
 192 Bool_t AliTPCHTable::SpanTree(AliTPCHNode *start, ULong_t code, UChar_t len){
 193   // span tree
 194   //In an Huffman tree any internal node has always two children
 195   AliTPCHNode * visited;
 196   visited = start;
 197   Int_t idx=visited->GetSymbol();
 198   if (!visited->GetLeft()) {
 199     fCode[idx] = code;
 200     fCodeLen[idx] = len;
 201     return kTRUE;
 202   }//end if
 203   SpanTree(visited->GetLeft(), code << 1, len + 1);
 204   SpanTree(visited->GetRight(), code << 1 | 0x0001, len + 1);
 205   return kTRUE;
 206 }
 207
 208 //////////////////////////////////////////////////////////////////////////////
 209
 210 void AliTPCHTable::ResetHNodes(){
 211   // Reset number of HNodes and the HNodes array
 212   if (fHNodes)  fHNodes->Clear();
 213   if (fNnodes)  fNnodes=0;
 214 }
 215
 216 //////////////////////////////////////////////////////////////////////////////
 217
 218 void AliTPCHTable::ClearTable(){
 219   // Clear the table
 220   memset(fCodeLen,0,sizeof(UChar_t)*fSize);
 221   memset(fCode,0,sizeof(Double_t)*fSize);
 222 }
 223
 224 //////////////////////////////////////////////////////////////////////////////
 225
 226 Int_t  AliTPCHTable::GetFrequencies(const char *fname){
 227   AliTPCBuffer160 buff(fname,0);
 228   ULong_t NumberOfWords=0;
 229   Int_t Val;
 230   while((Val=buff.GetNext())!=-1){
 231     fCode[Val]++;
 232     fNum++;
 233     NumberOfWords++;
 234   }
 235   cout<<"Total number of words: "<<NumberOfWords<<endl;
 236   //Print out the frequencies
 237   /*
 238     for (Int_t i=0;i<fSize;i++){
 239     if (fCode[i])cout<<"Symbol: "<<i<<" Freq: "<<fCode[i]<<endl;
 240     }
 241     cout<<endl;
 242   */
 243   return 0;
 244 }
 245
 246 Int_t AliTPCHTable::SetValFrequency(const Int_t Val,Double_t Value){
 247   fCode[Val]=Value;
 248   fNum=1;
 249   return 0;
 250 }
 251
 252 //////////////////////////////////////////////////////////////////////////////
 253
 254 Int_t AliTPCHTable::SetFrequency(const Int_t Val){
 255   fCode[Val]++;
 256   fNum++;
 257   return 0;
 258 }
 259
 260 //////////////////////////////////////////////////////////////////////////////
 261
 262 Int_t AliTPCHTable::StoreFrequencies(const char *fname){
 263   ofstream ftxt(fname);
 264   for (Int_t i=0;i<fSize;i++){
 265     ftxt<<(ULong_t)fCode[i]<<endl;
 266   }
 267   ftxt.close();
 268   return 0;
 269 }
 270
 271 //////////////////////////////////////////////////////////////////////////////
 272
 273 void AliTPCHTable::CompleteTable(Int_t k){
 274   Int_t max;
 275   ULong_t val;
 276   switch(k){
 277   case 0:
 278     max=700;
 279     val=1;
 280     break;
 281   case 1:
 282     max=445;
 283     val=1;
 284     break;
 285   default:
 286     max=fSize;
 287     val=1;
 288     break;
 289   }//end switch
 290
 291   for(Int_t i=0;i<max;i++){
 292     if(fCode[i]==0.0)fCode[i]=val;
 293   }
 294   return;
 295 }
 296
 297 //////////////////////////////////////////////////////////////////////////////
 298
 299 Double_t  AliTPCHTable::GetEntropy()const{
 300   Double_t entropy=0;
 301   Double_t prob=0;
 302   for (Int_t i=0;i<fSize;i++){
 303     if (fCode[i]){
 304       prob=fCode[i]/(Double_t)fNum;
 305       entropy+=prob*(TMath::Log2(prob));
 306     }
 307   }
 308   return -entropy;
 309 }
 310
 311 //////////////////////////////////////////////////////////////////////////////
 312
 313 Int_t AliTPCHTable::BuildHTable(){
 314   // build Htable
 315   if(GetWordsNumber()){
 316     for (Int_t i=0; i< fSize; i++) {
 317       if (fCode[i] > 0.){
 318         fNnodes++;
 319         //cout<< "Symbol:"<<i<<" Freq:"<<fCode[i]<<endl;
 320         fHNodes->Add(new AliTPCHNode(i,fCode[i]));
 321       }//end if
 322     }//end for
 323     Int_t nentries=fHNodes->GetEntriesFast();
 324     //cout<<"Number of symbols: "<<nentries<<endl;
 325     Int_t nindex=nentries-1;
 326     while (nindex > 0){
 327       fHNodes->Sort(nindex+1);
 328       AliTPCHNode *aux = new AliTPCHNode(0,0);
 329       AliTPCHNode *node= (AliTPCHNode*)fHNodes->UncheckedAt(nindex-1);
 330       AliTPCHNode *node1= (AliTPCHNode*)fHNodes->UncheckedAt(nindex);
 331
 332       aux->SetLeft(node);
 333       aux->SetRight(node1);
 334       aux->SetFrequency(node->GetFrequency() + node1->GetFrequency());
 335       fHNodes->RemoveAt(nindex-1);
 336       fHNodes->AddAt(aux,nindex-1);
 337       nindex--;
 338     }//end while
 339     ClearTable();
 340     AliTPCHNode *start= (AliTPCHNode*)fHNodes->UncheckedAt(0);
 341     SpanTree(start,0,0);
 342   }//end if
 343   else{
 344     cout<<"Table contains 0 elements\n";
 345   }//end else
 346   return 0;
 347 }
 348
 349 //////////////////////////////////////////////////////////////////////////////