[u/mrichter/AliRoot.git] / HLT / BASE / AliHLTHuffman.cxx

// $Id$
//**************************************************************************
//* This file is property of and copyright by the ALICE HLT Project        *
//* ALICE Experiment at CERN, All rights reserved.                         *
//*                                                                        *
//* Primary Authors: Thorsten Kollegger <kollegge@ikf.uni-frankfurt.de>    *
//*                  for The ALICE HLT Project.                            *
//*                                                                        *
//* 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.                  *
//**************************************************************************

/// @file   AliHLTHuffman.cxx
/// @author Thorsten Kollegger, Matthias Richter
/// @date   2011-08-14
/// @brief  Huffman code generator/encoder/decoder

#include "AliHLTHuffman.h"

#include <iostream>
#include <set>
#include <bitset>
#include <algorithm>

AliHLTHuffmanNode::AliHLTHuffmanNode() 
	: TObject()
	, fValue(-1)
	, fWeight(0.)
{
        // nop
}

AliHLTHuffmanNode::AliHLTHuffmanNode(const AliHLTHuffmanNode& other)
	: TObject()
	, fValue(other.GetValue())
	, fWeight(other.GetWeight())
{
}

AliHLTHuffmanNode& AliHLTHuffmanNode::operator =(const AliHLTHuffmanNode& other) {
        /// assignment operator
	this->fValue = other.fValue;
	this->fWeight = other.fWeight;
	return *this;
}

AliHLTHuffmanNode::~AliHLTHuffmanNode() {
}

void AliHLTHuffmanNode::AssignCode() {
        /// assign code to this node loop to right and left nodes
	if (GetLeftChild()) {
		// shift current bit pattern to left and add one
		std::bitset < 64 > v = (this->GetBinaryCode() << 1);
		v.set(0);
		GetLeftChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
		GetLeftChild()->AssignCode();
	}
	if (GetRightChild()) {
		std::bitset < 64 > v = (this->GetBinaryCode() << 1);
		v.reset(0);
		GetRightChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
		GetRightChild()->AssignCode();
	}
}

void AliHLTHuffmanNode::Print(Option_t* /*option*/) const {
        /// print info
	std::cout << "value=" << GetValue() << ", weight=" << GetWeight() << ", length="
			<< GetBinaryCodeLength() << ", code=" << GetBinaryCode().to_string()
			<< std::endl;
	if (GetLeftChild()) {
		GetLeftChild()->Print();
	}
	if (GetRightChild()) {
		GetRightChild()->Print();
	}
}

ClassImp(AliHLTHuffmanNode)

///////////////////////////////////////////////////////////////////////////////////////////////

AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode() 
	: AliHLTHuffmanNode()
	, fBinaryCodeLength(0)
	, fBinaryCode(0)
	, fLeft(NULL)
	, fRight(NULL)
{
        // nop
}

AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode(const AliHLTHuffmanTreeNode& other)
	: AliHLTHuffmanNode()
	, fBinaryCodeLength(other.fBinaryCodeLength)
	, fBinaryCode(other.fBinaryCode)
	, fLeft(other.GetLeftChild())
	, fRight(other.GetRightChild())
{

}

AliHLTHuffmanTreeNode& AliHLTHuffmanTreeNode::operator =(const AliHLTHuffmanTreeNode& other)
{
        /// assignment operator
        if (&other==this) return *this;
	this->fBinaryCodeLength = other.GetBinaryCodeLength();
	this->fBinaryCode = other.GetBinaryCode();
	this->fLeft = other.GetLeftChild();
	this->fRight = other.GetRightChild();
	AliHLTHuffmanNode::operator=(other);
	return *this;
}

AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode(AliHLTHuffmanNode* l, AliHLTHuffmanNode* r)
	: AliHLTHuffmanNode()
	, fBinaryCodeLength(0)
	, fBinaryCode(0)
	, fLeft(l)
	, fRight(r) {
	if (l && r) {
		SetWeight(l->GetWeight() + r->GetWeight());
	} else if (l && !r) {
		SetWeight(l->GetWeight());
	} else if (!l && r) {
		SetWeight(r->GetWeight());
	}
}

AliHLTHuffmanTreeNode::~AliHLTHuffmanTreeNode() 
{
        // nop
}

ClassImp(AliHLTHuffmanTreeNode)

///////////////////////////////////////////////////////////////////////////////////////////////

AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode() 
	: AliHLTHuffmanNode()
	, fBinaryCodeLength(0)
	, fBinaryCode(0)
	, fLeft(NULL)
	, fRight(NULL)
{
        // nop
}

AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode(const AliHLTHuffmanLeaveNode& other)
	: AliHLTHuffmanNode()
	, fBinaryCodeLength(other.fBinaryCodeLength)
	, fBinaryCode(other.fBinaryCode)
	, fLeft(other.GetLeftChild())
	, fRight(other.GetRightChild())
{

}

AliHLTHuffmanLeaveNode& AliHLTHuffmanLeaveNode::operator =(const AliHLTHuffmanLeaveNode& other)
{
        /// assignment operator
        if (&other==this) return *this;
	this->fBinaryCodeLength = other.GetBinaryCodeLength();
	this->fBinaryCode = other.GetBinaryCode();
	this->fLeft = other.GetLeftChild();
	this->fRight = other.GetRightChild();
	AliHLTHuffmanNode::operator=(other);
	return *this;
}

AliHLTHuffmanLeaveNode::~AliHLTHuffmanLeaveNode() 
{
        // nop
}

ClassImp(AliHLTHuffmanLeaveNode)

///////////////////////////////////////////////////////////////////////////////////////////////

AliHLTHuffman::AliHLTHuffman()
	: TNamed()
	, fMaxBits(0)
	, fMaxValue(0)
	, fNodes(0)
	, fHuffTopNode(NULL)
{
        /// nop
}

AliHLTHuffman::AliHLTHuffman(const AliHLTHuffman& other)
	: TNamed()
	, AliHLTLogging()
	, fMaxBits(other.fMaxBits)
	, fMaxValue(other.fMaxValue)
	, fNodes(other.fNodes)
	, fHuffTopNode(NULL) {
        /// nop
}

AliHLTHuffman::AliHLTHuffman(const char* name, UInt_t maxBits)
        : TNamed(name, name)
	, fMaxBits(maxBits)
	, fMaxValue((((AliHLTUInt64_t) 1) << maxBits) - 1)
	, fNodes((((AliHLTUInt64_t) 1) << maxBits))
	, fHuffTopNode(NULL)
 {
        /// standard constructor
	for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
		fNodes[i].SetValue(i);
	}
}

AliHLTHuffman::~AliHLTHuffman() {
        /// destructor, nop
}

const std::bitset<64>& AliHLTHuffman::Encode(const AliHLTUInt64_t v, AliHLTUInt64_t& codeLength) const {
        /// encode a value
	codeLength = 0;
	if (v <= fMaxValue) {
		// valid symbol/value
		if (fHuffTopNode) {
			// huffman code has been generated
			codeLength = fNodes[v].GetBinaryCodeLength();
			return fNodes[v].GetBinaryCode();
		} else {
		  HLTError("encoder '%s' does not seem to be initialized", GetName());
		}
	} else {
	  HLTError("encoder %s: value %llu exceeds range of %d bits", GetName(), v, GetMaxBits());
	}

	static const std::bitset<64> dummy;
	return dummy;
}

Bool_t AliHLTHuffman::Decode(std::bitset<64> bits, AliHLTUInt64_t& value) const {
	// TODO: check decoding logic, righ now it is just as written
	AliHLTHuffmanNode* currNode = fHuffTopNode;
	if (!currNode) return kFALSE;
	if (currNode->GetValue() >= 0) {
		// handle case with just one node - also quite unlikely
		value = currNode->GetValue();
		return kTRUE;
	}
	while (currNode) {
		if (bits[0] && currNode->GetLeftChild()) {
			// follow left branch
			currNode = currNode->GetLeftChild();
			bits >>= 1;
			if (currNode->GetValue() >= 0) {
				value = currNode->GetValue();
				return kTRUE;
			}
		}
		if (!bits[0] && currNode->GetRightChild()) {
			currNode = currNode->GetRightChild();
			bits >>= 1;
			if (currNode->GetValue() >= 0) {
				value = currNode->GetValue();
				return kTRUE;
			}
		}
	}
	value = ((AliHLTUInt64_t)1) << 63;
	return kFALSE;
}

Bool_t AliHLTHuffman::AddTrainingValue(const AliHLTUInt64_t value,
		const Float_t weight) {
	if (value > fMaxValue) {
		/* TODO: ERROR message */
		return kFALSE;
	}
	fNodes[value].AddWeight(weight);
	return kTRUE;
}

Bool_t AliHLTHuffman::GenerateHuffmanTree() {
	// insert pointer to nodes into ordered structure to build tree
	std::multiset<AliHLTHuffmanNode*, AliHLTHuffmanNode::less> nodeCollection;
	//	std::copy(fNodes.begin(), fNodes.end(),
	//			std::inserter(freq_coll, freq_coll.begin()));
	for (std::vector<AliHLTHuffmanLeaveNode>::iterator i = fNodes.begin(); i
			!= fNodes.end(); ++i) {
		nodeCollection.insert(&(*i));
	}
	while (nodeCollection.size() > 1) {
		// insert new node into structure, combining the two with lowest probability
		nodeCollection.insert(
				new AliHLTHuffmanTreeNode(*nodeCollection.begin(),
						*++nodeCollection.begin()));
		nodeCollection.erase(nodeCollection.begin());
		nodeCollection.erase(nodeCollection.begin());
	}
	//assign value
	fHuffTopNode = *nodeCollection.begin();
	fHuffTopNode->AssignCode();
	return kTRUE;
}

void AliHLTHuffman::Print(Option_t* option) const {
        std::cout << GetName() << endl;
        bool bPrintShort=strcmp(option, "short")==0;
	if (fHuffTopNode && !bPrintShort) {
		std::cout << "Huffman tree:" << endl;
		fHuffTopNode->Print();
	}
	Double_t uncompressedSize = 0;
	Double_t compressedSize = 0;
	Double_t totalWeight = 0;
	if (!bPrintShort)
	  std::cout << std::endl << "Huffman codes:" << std::endl;
	for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
	  if (!bPrintShort) fNodes[i].Print();
		totalWeight += fNodes[i].GetWeight();
		uncompressedSize += fNodes[i].GetWeight() * fMaxBits;
		compressedSize += fNodes[i].GetWeight()
				* fNodes[i].GetBinaryCodeLength();
	}
	if (uncompressedSize > 0) {
		std::cout << "compression ratio: " << compressedSize
				/ uncompressedSize << std::endl;
		std::cout << "<bits> uncompressed: " << uncompressedSize / totalWeight
				<< std::endl;
		std::cout << "<bits> compressed:   " << compressedSize / totalWeight
				<< std::endl;
	}
}

AliHLTHuffman& AliHLTHuffman::operator =(const AliHLTHuffman& other) {
	fMaxValue = other.fMaxValue;
	fNodes = other.fNodes;
	fHuffTopNode = NULL;
	return *this;
}

ClassImp(AliHLTHuffman)
Commit	Line	Data
6a1b3945	1	// $Id$
	2	//**************************************************************************
	3	//* This file is property of and copyright by the ALICE HLT Project *
	4	//* ALICE Experiment at CERN, All rights reserved. *
	5	//* *
	6	//* Primary Authors: Thorsten Kollegger <kollegge@ikf.uni-frankfurt.de> *
	7	//* for The ALICE HLT Project. *
	8	//* *
	9	//* Permission to use, copy, modify and distribute this software and its *
	10	//* documentation strictly for non-commercial purposes is hereby granted *
	11	//* without fee, provided that the above copyright notice appears in all *
	12	//* copies and that both the copyright notice and this permission notice *
	13	//* appear in the supporting documentation. The authors make no claims *
	14	//* about the suitability of this software for any purpose. It is *
	15	//* provided "as is" without express or implied warranty. *
	16	//**************************************************************************
	17
	18	/// @file AliHLTHuffman.cxx
	19	/// @author Thorsten Kollegger, Matthias Richter
	20	/// @date 2011-08-14
	21	/// @brief Huffman code generator/encoder/decoder
	22
	23	#include "AliHLTHuffman.h"
	24
	25	#include <iostream>
	26	#include <set>
	27	#include <bitset>
	28	#include <algorithm>
	29
	30	AliHLTHuffmanNode::AliHLTHuffmanNode()
	31	: TObject()
	32	, fValue(-1)
	33	, fWeight(0.)
	34	{
	35	// nop
	36	}
	37
	38	AliHLTHuffmanNode::AliHLTHuffmanNode(const AliHLTHuffmanNode& other)
	39	: TObject()
	40	, fValue(other.GetValue())
	41	, fWeight(other.GetWeight())
	42	{
	43	}
	44
	45	AliHLTHuffmanNode& AliHLTHuffmanNode::operator =(const AliHLTHuffmanNode& other) {
	46	/// assignment operator
	47	this->fValue = other.fValue;
	48	this->fWeight = other.fWeight;
	49	return *this;
	50	}
	51
	52	AliHLTHuffmanNode::~AliHLTHuffmanNode() {
	53	}
	54
	55	void AliHLTHuffmanNode::AssignCode() {
	56	/// assign code to this node loop to right and left nodes
	57	if (GetLeftChild()) {
	58	// shift current bit pattern to left and add one
	59	std::bitset < 64 > v = (this->GetBinaryCode() << 1);
	60	v.set(0);
	61	GetLeftChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
	62	GetLeftChild()->AssignCode();
	63	}
	64	if (GetRightChild()) {
65	std::bitset < 64 > v = (this->GetBinaryCode() << 1);
66	v.reset(0);
67	GetRightChild()->SetBinaryCode(this->GetBinaryCodeLength() + 1, v);
68	GetRightChild()->AssignCode();
69	}
70	}
71
72	void AliHLTHuffmanNode::Print(Option_t* /option/) const {
73	/// print info
74	std::cout << "value=" << GetValue() << ", weight=" << GetWeight() << ", length="
75	<< GetBinaryCodeLength() << ", code=" << GetBinaryCode().to_string()
76	<< std::endl;
77	if (GetLeftChild()) {
78	GetLeftChild()->Print();
79	}
80	if (GetRightChild()) {
81	GetRightChild()->Print();
82	}
83	}
84
85	ClassImp(AliHLTHuffmanNode)
86
87	///////////////////////////////////////////////////////////////////////////////////////////////
88
89	AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode()
90	: AliHLTHuffmanNode()
91	, fBinaryCodeLength(0)
92	, fBinaryCode(0)
93	, fLeft(NULL)
94	, fRight(NULL)
95	{
96	// nop
97	}
98
99	AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode(const AliHLTHuffmanTreeNode& other)
100	: AliHLTHuffmanNode()
101	, fBinaryCodeLength(other.fBinaryCodeLength)
102	, fBinaryCode(other.fBinaryCode)
103	, fLeft(other.GetLeftChild())
104	, fRight(other.GetRightChild())
105	{
106
107	}
108
109	AliHLTHuffmanTreeNode& AliHLTHuffmanTreeNode::operator =(const AliHLTHuffmanTreeNode& other)
110	{
111	/// assignment operator
112	if (&other==this) return *this;
113	this->fBinaryCodeLength = other.GetBinaryCodeLength();
114	this->fBinaryCode = other.GetBinaryCode();
115	this->fLeft = other.GetLeftChild();
116	this->fRight = other.GetRightChild();
117	AliHLTHuffmanNode::operator=(other);
118	return *this;
119	}
120
121	AliHLTHuffmanTreeNode::AliHLTHuffmanTreeNode(AliHLTHuffmanNode* l, AliHLTHuffmanNode* r)
122	: AliHLTHuffmanNode()
123	, fBinaryCodeLength(0)
124	, fBinaryCode(0)
125	, fLeft(l)
126	, fRight(r) {
127	if (l && r) {
128	SetWeight(l->GetWeight() + r->GetWeight());
129	} else if (l && !r) {
130	SetWeight(l->GetWeight());
131	} else if (!l && r) {
132	SetWeight(r->GetWeight());
133	}
134	}
135
136	AliHLTHuffmanTreeNode::~AliHLTHuffmanTreeNode()
137	{
138	// nop
139	}
140
141	ClassImp(AliHLTHuffmanTreeNode)
142
143	///////////////////////////////////////////////////////////////////////////////////////////////
144
145	AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode()
146	: AliHLTHuffmanNode()
147	, fBinaryCodeLength(0)
148	, fBinaryCode(0)
149	, fLeft(NULL)
150	, fRight(NULL)
151	{
152	// nop
153	}
154
155	AliHLTHuffmanLeaveNode::AliHLTHuffmanLeaveNode(const AliHLTHuffmanLeaveNode& other)
156	: AliHLTHuffmanNode()
157	, fBinaryCodeLength(other.fBinaryCodeLength)
158	, fBinaryCode(other.fBinaryCode)
159	, fLeft(other.GetLeftChild())
160	, fRight(other.GetRightChild())
161	{
162
163	}
164
165	AliHLTHuffmanLeaveNode& AliHLTHuffmanLeaveNode::operator =(const AliHLTHuffmanLeaveNode& other)
166	{
167	/// assignment operator
168	if (&other==this) return *this;
169	this->fBinaryCodeLength = other.GetBinaryCodeLength();
170	this->fBinaryCode = other.GetBinaryCode();
171	this->fLeft = other.GetLeftChild();
172	this->fRight = other.GetRightChild();
173	AliHLTHuffmanNode::operator=(other);
174	return *this;
175	}
176
177	AliHLTHuffmanLeaveNode::~AliHLTHuffmanLeaveNode()
178	{
179	// nop
180	}
181
182	ClassImp(AliHLTHuffmanLeaveNode)
183
184	///////////////////////////////////////////////////////////////////////////////////////////////
185
186	AliHLTHuffman::AliHLTHuffman()
187	: TNamed()
188	, fMaxBits(0)
189	, fMaxValue(0)
190	, fNodes(0)
191	, fHuffTopNode(NULL)
192	{
193	/// nop
194	}
195
196	AliHLTHuffman::AliHLTHuffman(const AliHLTHuffman& other)
197	: TNamed()
198	, AliHLTLogging()
199	, fMaxBits(other.fMaxBits)
200	, fMaxValue(other.fMaxValue)
201	, fNodes(other.fNodes)
202	, fHuffTopNode(NULL) {
203	/// nop
204	}
205
206	AliHLTHuffman::AliHLTHuffman(const char* name, UInt_t maxBits)
207	: TNamed(name, name)
208	, fMaxBits(maxBits)
209	, fMaxValue((((AliHLTUInt64_t) 1) << maxBits) - 1)
210	, fNodes((((AliHLTUInt64_t) 1) << maxBits))
211	, fHuffTopNode(NULL)
212	{
213	/// standard constructor
214	for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
215	fNodes[i].SetValue(i);
216	}
217	}
218
219	AliHLTHuffman::~AliHLTHuffman() {
220	/// destructor, nop
221	}
222
223	const std::bitset<64>& AliHLTHuffman::Encode(const AliHLTUInt64_t v, AliHLTUInt64_t& codeLength) const {
224	/// encode a value
225	codeLength = 0;
226	if (v <= fMaxValue) {
227	// valid symbol/value
228	if (fHuffTopNode) {
229	// huffman code has been generated
230	codeLength = fNodes[v].GetBinaryCodeLength();
231	return fNodes[v].GetBinaryCode();
232	} else {
233	HLTError("encoder '%s' does not seem to be initialized", GetName());
234	}
235	} else {
236	HLTError("encoder %s: value %llu exceeds range of %d bits", GetName(), v, GetMaxBits());
237	}
238
239	static const std::bitset<64> dummy;
240	return dummy;
241	}
242
243	Bool_t AliHLTHuffman::Decode(std::bitset<64> bits, AliHLTUInt64_t& value) const {
244	// TODO: check decoding logic, righ now it is just as written
245	AliHLTHuffmanNode* currNode = fHuffTopNode;
cac77957	246	if (!currNode) return kFALSE;
6a1b3945	247	if (currNode->GetValue() >= 0) {
	248	// handle case with just one node - also quite unlikely
	249	value = currNode->GetValue();
	250	return kTRUE;
	251	}
	252	while (currNode) {
	253	if (bits[0] && currNode->GetLeftChild()) {
	254	// follow left branch
	255	currNode = currNode->GetLeftChild();
	256	bits >>= 1;
	257	if (currNode->GetValue() >= 0) {
	258	value = currNode->GetValue();
	259	return kTRUE;
	260	}
	261	}
	262	if (!bits[0] && currNode->GetRightChild()) {
	263	currNode = currNode->GetRightChild();
	264	bits >>= 1;
	265	if (currNode->GetValue() >= 0) {
	266	value = currNode->GetValue();
	267	return kTRUE;
	268	}
	269	}
	270	}
	271	value = ((AliHLTUInt64_t)1) << 63;
	272	return kFALSE;
	273	}
	274
	275	Bool_t AliHLTHuffman::AddTrainingValue(const AliHLTUInt64_t value,
84a44d88	276	const Float_t weight) {
6a1b3945	277	if (value > fMaxValue) {
	278	/* TODO: ERROR message */
	279	return kFALSE;
	280	}
	281	fNodes[value].AddWeight(weight);
	282	return kTRUE;
	283	}
	284
	285	Bool_t AliHLTHuffman::GenerateHuffmanTree() {
	286	// insert pointer to nodes into ordered structure to build tree
	287	std::multiset<AliHLTHuffmanNode*, AliHLTHuffmanNode::less> nodeCollection;
	288	// std::copy(fNodes.begin(), fNodes.end(),
	289	// std::inserter(freq_coll, freq_coll.begin()));
	290	for (std::vector<AliHLTHuffmanLeaveNode>::iterator i = fNodes.begin(); i
	291	!= fNodes.end(); ++i) {
	292	nodeCollection.insert(&(*i));
	293	}
	294	while (nodeCollection.size() > 1) {
	295	// insert new node into structure, combining the two with lowest probability
	296	nodeCollection.insert(
	297	new AliHLTHuffmanTreeNode(*nodeCollection.begin(),
	298	*++nodeCollection.begin()));
	299	nodeCollection.erase(nodeCollection.begin());
	300	nodeCollection.erase(nodeCollection.begin());
	301	}
	302	//assign value
	303	fHuffTopNode = *nodeCollection.begin();
	304	fHuffTopNode->AssignCode();
	305	return kTRUE;
	306	}
	307
	308	void AliHLTHuffman::Print(Option_t* option) const {
	309	std::cout << GetName() << endl;
	310	bool bPrintShort=strcmp(option, "short")==0;
	311	if (fHuffTopNode && !bPrintShort) {
	312	std::cout << "Huffman tree:" << endl;
	313	fHuffTopNode->Print();
	314	}
	315	Double_t uncompressedSize = 0;
	316	Double_t compressedSize = 0;
	317	Double_t totalWeight = 0;
	318	if (!bPrintShort)
	319	std::cout << std::endl << "Huffman codes:" << std::endl;
	320	for (AliHLTUInt64_t i = 0; i <= fMaxValue; i++) {
	321	if (!bPrintShort) fNodes[i].Print();
	322	totalWeight += fNodes[i].GetWeight();
	323	uncompressedSize += fNodes[i].GetWeight() * fMaxBits;
	324	compressedSize += fNodes[i].GetWeight()
	325	* fNodes[i].GetBinaryCodeLength();
	326	}
	327	if (uncompressedSize > 0) {
	328	std::cout << "compression ratio: " << compressedSize
	329	/ uncompressedSize << std::endl;
	330	std::cout << "<bits> uncompressed: " << uncompressedSize / totalWeight
	331	<< std::endl;
	332	std::cout << "<bits> compressed: " << compressedSize / totalWeight
	333	<< std::endl;
	334	}
	335	}
	336
	337	AliHLTHuffman& AliHLTHuffman::operator =(const AliHLTHuffman& other) {
	338	fMaxValue = other.fMaxValue;
	339	fNodes = other.fNodes;
	340	fHuffTopNode = NULL;
341	return *this;
342	}
343
344	ClassImp(AliHLTHuffman)
345