[u/mrichter/AliRoot.git] / ITS / AliITSHuffman.cxx

/**************************************************************************
 * Copyright(c) 2006-2008, ALICE Experiment at CERN, All rights reserved. *
 *                                                                        *
 * Author: The ALICE Off-line Project.                                    *
 * Contributors are mentioned in the code where appropriate.              *
 *                                                                        *
 * Permission to use, copy, modify and distribute this software and its   *
 * documentation strictly for non-commercial purposes is hereby granted   *
 * without fee, provided that the above copyright notice appears in all   *
 * copies and that both the copyright notice and this permission notice   *
 * appear in the supporting documentation. The authors make no claims     *
 * about the suitability of this software for any purpose. It is          *
 * provided "as is" without express or implied warranty.                  *
 **************************************************************************/

/* $Id$ */

////////////////////////////////////////////////
//                                            //
//  RawData classes for set:ITS               //
//                                            //
////////////////////////////////////////////////

#include <TMath.h>
#include <TObjArray.h>
#include <Riostream.h>

#include "AliITSHuffman.h"

ClassImp(AliITSHuffman)

//_____________________________________________________________________________

  AliITSHuffman::AliITSHNode::AliITSHNode(): 
TObject(),
fSymbol(),
fFrequency(0),
fLeft(),
fRight(),
fFather() {
  // default constructor
}
//_____________________________________________________________________________

AliITSHuffman::AliITSHNode::AliITSHNode(UChar_t sym, ULong_t freq):
TObject(),
fSymbol(sym),
fFrequency(freq),
fLeft(),
fRight(),
fFather() {
  // standard constructor
}

//__________________________________________________________________________
AliITSHuffman::AliITSHNode::AliITSHNode(const AliITSHNode &source): 
TObject(source),
fSymbol(source.fSymbol),
fFrequency(source.fFrequency),
fLeft(source.fLeft),
fRight(source.fRight),
fFather(source.fFather) {
  //     Copy Constructor 
  return;
}

//_________________________________________________________________________
AliITSHuffman::AliITSHNode& 
  AliITSHuffman::AliITSHNode::operator=(const AliITSHuffman::AliITSHNode &source) {
  //    Assignment operator
  if(&source == this) return *this;
  this->fSymbol = source.fSymbol;
  this->fFrequency = source.fFrequency;
  this->fLeft = source.fLeft;
  this->fRight = source.fRight;
  this->fFather = source.fFather;
  return *this;
}

//____________________________________________
Int_t AliITSHuffman::AliITSHNode::Compare(const TObject *obj) const
{
  // function called by Sort method of TObjArray

         AliITSHNode *node=(AliITSHNode *)obj;
	 ULong_t f=fFrequency;
         ULong_t fo=node->fFrequency;
         if (f>fo) return 1;
         else if (f<fo) return -1;
         else return 0;
}


//_____________________________________________________________________________

AliITSHuffman::AliITSHuffman():
TObject(),
fSize(0),
fCodeLen(),
fCode(),
fSym(),
fHNodes(),
fNnodes(0)
{
  // default constructor
   
}
//_____________________________________________________________________________

AliITSHuffman::AliITSHuffman(Int_t size):
TObject(),
fSize(size),
fCodeLen(),
fCode(),
fSym(),
fHNodes(),
fNnodes(0)
{
  //
  // Creates the look-up table for the 1D compression
  //

  //initialise

  fCodeLen = new UChar_t[fSize]; 
  fCode = new ULong_t[fSize]; 
  fHNodes = new TObjArray;
  fNnodes=0;
  fSym= new Short_t[fSize];
  for (Short_t i=0;i<fSize;i++) {
       fSym[i]=i;
  }
  ClearTable(); 

}

//__________________________________________________________________________
AliITSHuffman::AliITSHuffman(const AliITSHuffman &source) : 
TObject(source),
fSize(source.fSize),
fCodeLen(source.fCodeLen),
fCode(source.fCode),
fSym(source.fSym),
fHNodes(source.fHNodes),
fNnodes(source.fNnodes)
{
  //     Copy Constructor 
}

//_________________________________________________________________________
AliITSHuffman& 
  AliITSHuffman::operator=(const AliITSHuffman &source) {
  //    Assignment operator
  if(&source == this) return *this;
  this->fSize = source.fSize;
  this->fCodeLen = source.fCodeLen;
  this->fCode = source.fCode;
  this->fSym = source.fSym;
  this->fHNodes = source.fHNodes;
  this->fNnodes = source.fNnodes;
  return *this;
}

//_____________________________________________________________________________
void AliITSHuffman::GetFrequencies(Int_t len, UChar_t *stream)
{
  // get frequencies
  printf("Get Frequencies: sym %p \n",(void*)fSym);

  // use temporarily the fCode array to store the frequencies
  for (Int_t i=0; i< len; i++) {
      Int_t idx=TMath::BinarySearch(fSize,fSym,(Short_t)stream[i]);
      if (idx == (Int_t)stream[i]) fCode[idx]++;
      // test
      if(idx==134) cout<< "idx fCode[idx]  "<<idx<<" "<<fCode[idx]<<endl;
      //printf("idx,fCode[i] %d %d\n",idx,(Int_t)fCode[idx]);
  }


}


//_____________________________________________________________________________
void AliITSHuffman::BuildHTable()
{
  // build Htable

  for (Int_t i=0; i< fSize; i++) {
    //printf("i,fCode[i] %d %d\n",i,(Int_t)fCode[i]);
     if (fCode[i] > 0) {
        fNnodes++;
        cout<< "i fCode[i] fNnodes "<<i<<" "<<fCode[i]<<" "<<fNnodes<<endl;
	//printf("i, fCode[i] fNnodes %d %d %d\n",i,fCode[i],fNnodes);
        fHNodes->Add(new AliITSHuffman::AliITSHNode((UChar_t)i,fCode[i]));
     }
  }

  Int_t nentries=fHNodes->GetEntriesFast();
  Int_t nindex=nentries-1;  
  printf("nentries fNnodes nindex %d %d %d\n",nentries,fNnodes,nindex);

  while (nindex > 0) 
    {

     fHNodes->Sort(nindex);
     AliITSHNode *aux = new AliITSHNode(0,0);
     AliITSHNode *node= (AliITSHNode*)fHNodes->UncheckedAt(nindex-1);
     AliITSHNode *node1= (AliITSHNode*)fHNodes->UncheckedAt(nindex);
     aux->SetLeft(node);
     aux->SetRight(node1);
     aux->SetFrequency(node->GetFrequency() + node1->GetFrequency());
     printf("symbol symbol1 freq freq1 %d %d %d %d\n",(int)node->GetSymbol(),(int)node1->GetSymbol(),(int)node->GetFrequency(),(int)node1->GetFrequency());
     cout << "aux - frequency "<< (Int_t)(aux->GetFrequency()) <<endl;
     fHNodes->RemoveAt(nindex-1);
     fHNodes->AddAt(aux,nindex-1);
     nindex--;
     printf("nindex, obj at nindex %d %p \n",nindex,(void*)fHNodes->UncheckedAt(nindex));

    }

    ClearTable();

    AliITSHNode *start= (AliITSHNode*)fHNodes->UncheckedAt(0);
    SpanTree(start,0,0);
    
    // check the Huffman table

    cout << "...Done, Huffman Table is: \n";
    for (int c=0; c <= 255; c++) {
      if (fCodeLen[c] > 0) cout << "Symbol " << c << " Coded as " << fCode[c] << " and long " << (int) fCodeLen[c] << " bits.\n"; 
    }

}

//_____________________________________________________________________________
AliITSHuffman::~AliITSHuffman()
{
  // HTable
    printf("HTable destructor !\n");
    if (fCodeLen) delete[] fCodeLen;
    if (fCode) delete [] fCode;
    if (fHNodes) {
      fHNodes->Delete();
      delete fHNodes;
    }
}


//____________________________________________
Bool_t AliITSHuffman::SpanTree(AliITSHNode *start, ULong_t code, UChar_t len)
{
  // span tree
  AliITSHNode * visited;
  visited = start;

  printf("outside: code, len %d %d\n",(int)code,(int)len);

  Int_t idx=(Int_t)visited->GetSymbol();
  if (!visited->GetLeft()) {
	fCode[idx] = code; 
	fCodeLen[idx] = len;
        printf("idx, fCode[idx], fCodeLen[idx] %d %d %d\n",idx,(int)fCode[idx],
              (int)fCodeLen[idx]);
	return kTRUE;
  }

// reccursive stuff

  if (SpanTree(visited->GetLeft(), code << 1, len + 1)) {
          printf("code, len %d %d\n",(int)code,(int)len);
	  if (visited->GetRight()) 
                  SpanTree(visited->GetRight(), code << 1 | 0x01, len + 1);
  }
  return kTRUE;
}

//____________________________________________
void AliITSHuffman::ResetHNodes()
{
    //
    // Reset number of HNodes and the HNodes array 
    //
	if (fHNodes)  fHNodes->Clear();
	if (fNnodes)  fNnodes=0;

}

//_____________________________________________________________________________
void AliITSHuffman::ClearTable()
{
  // clear
    memset(fCodeLen,0,sizeof(UChar_t)*fSize);
    memset(fCode,0,sizeof(ULong_t)*fSize);
}
Commit	Line	Data
	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