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

//-*- Mode: C++ -*-
// $Id$
#ifndef ALIHLTHUFFMAN_H
#define ALIHLTHUFFMAN_H
//* This file is property of and copyright by the ALICE HLT Project        *
//* ALICE Experiment at CERN, All rights reserved.                         *
//* See cxx source for full Copyright notice                               *

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

#include "AliHLTLogging.h"

#include "TNamed.h"

#include <vector>
#include <bitset>
#include <string>

/**
 * @class AliHLTHuffmanNode
 * Huffman code nodes. This is the base class for two types of nodes,
 * AliHLTHuffmanTreeNode and AliHLTHuffmanLeaveNode. The latter nodes
 * represent the index array of values to huffman codes. The former are
 * used in a tree reaching from the value of highest occuremce to all
 * leaves. The two node types are defined in order to optimize the storage
 * format for the huffman table. Leave nodes don't need persistent pointers
 * to childs, tree nodes don't need persistent binary code values.
 *
 * @ingroup alihlt_base
 */
class AliHLTHuffmanNode: public TObject {
public:
	/// default constructor
	AliHLTHuffmanNode();
	/// copy constructor
	AliHLTHuffmanNode(const AliHLTHuffmanNode& other);
	/// assignment operator
	AliHLTHuffmanNode& operator=(const AliHLTHuffmanNode& other);
	/// destructor
	virtual ~AliHLTHuffmanNode();

	/// set symbol value of node
	void SetValue(AliHLTInt64_t v) {
		fValue = v;
	}
	/// add weight to node
	void AddWeight(Float_t w) {
		fWeight += w;
	}
	/// set weight of node
	void SetWeight(Float_t w) {
		fWeight = w;
	}
	/// return symbol value of node
	AliHLTInt64_t GetValue() const {
		return fValue;
	}
	/// return weight of node
	Float_t GetWeight() const {
		return fWeight;
	}

        /// assign huffman code to this node and its children
        /// bReverse = true the bit corresponding to the parent is shifted and
        /// decoding needs to start from the MSB of the code
	void AssignCode(bool bReverse=false);
	/// set binary huffman code and length of node
	virtual void SetBinaryCode(AliHLTUInt64_t length, std::bitset<64> code) = 0;
	/// set pointer to left child
	virtual void SetLeftChild(AliHLTHuffmanNode* n) = 0;
	/// set pointer to right child
	virtual void SetRightChild(AliHLTHuffmanNode* n) = 0;
	/// Return length of huffman code
	virtual AliHLTUInt64_t GetBinaryCodeLength() const = 0;
	/// Return binary huffman code
	virtual const std::bitset<64>& GetBinaryCode() const = 0;
	/// Return pointer to left Child
	virtual AliHLTHuffmanNode* GetLeftChild() const = 0;
	/// Return pointer to right Child
	virtual AliHLTHuffmanNode* GetRightChild() const = 0;

	/// Print information about node
	void Print(Option_t* option = "") const;
	/// Overload less operator, based on node weights
	Bool_t operator <(const AliHLTHuffmanNode& other) const {
		return (this->GetWeight() < other.GetWeight());
	}
	class less {
	public:
		bool operator()(const AliHLTHuffmanNode* i1,
				const AliHLTHuffmanNode* i2) const {
			//reverse sort, less likely to most likely
			return ((*i1) < (*i2));
		}
	};

private:
	AliHLTInt64_t fValue;        // value
	Float_t fWeight;             // weight

ClassDef(AliHLTHuffmanNode, 1)
};

/**
 * @class AliHLTHuffmanTreeNode
 * Tree nodes store the childs persistently. The binary code is
 * a transient member.
 */
class AliHLTHuffmanTreeNode: public AliHLTHuffmanNode {
public:
	/// default constructor
	AliHLTHuffmanTreeNode();
	/// copy constructor
	AliHLTHuffmanTreeNode(const AliHLTHuffmanTreeNode& other);
	/// assignment operator
	AliHLTHuffmanTreeNode& operator=(const AliHLTHuffmanTreeNode& other);
	/// constructor for internal nodes, based on two input nodes (leaves or internal nodes)
	AliHLTHuffmanTreeNode(AliHLTHuffmanNode* l, AliHLTHuffmanNode* r);
	/// desstructor
	~AliHLTHuffmanTreeNode();

	/// set binary huffman code and length of node
	void SetBinaryCode(AliHLTUInt64_t length, std::bitset<64> code) {
	        fBinaryCodeLength = length;
	        fBinaryCode = code;
	}

	/// set pointer to left child
	void SetLeftChild(AliHLTHuffmanNode* n) {
		fLeft = n;
	}
	/// set pointer to right child
	void SetRightChild(AliHLTHuffmanNode* n) {
		fRight = n;
	}
	/// Return length of huffman code
	AliHLTUInt64_t GetBinaryCodeLength() const {
		return fBinaryCodeLength;
	}
	/// Return binary huffman code
	const std::bitset<64>& GetBinaryCode() const {
		return fBinaryCode;
	}
	/// Return pointer to left Child
	AliHLTHuffmanNode* GetLeftChild() const {
		return fLeft;
	}
	/// Return pointer to right Child
	AliHLTHuffmanNode* GetRightChild() const {
		return fRight;
	}

private:
	AliHLTUInt8_t fBinaryCodeLength; //! code length
	std::bitset<64> fBinaryCode; //! WARNING: this fixed the maximum code length to 128
	AliHLTHuffmanNode* fLeft;    // left neighbor
	AliHLTHuffmanNode* fRight;   // right neighbor

ClassDef(AliHLTHuffmanTreeNode, 1)
};

/**
 * @class AliHLTHuffmanLeaveNode
 * Leave nodes store the binary code persistently, while the childs are transient
 */
class AliHLTHuffmanLeaveNode: public AliHLTHuffmanNode {
public:
	/// default constructor
	AliHLTHuffmanLeaveNode();
	/// copy constructor
	AliHLTHuffmanLeaveNode(const AliHLTHuffmanLeaveNode& other);
	/// assignment operator
	AliHLTHuffmanLeaveNode& operator=(const AliHLTHuffmanLeaveNode& other);
	/// destructor
	~AliHLTHuffmanLeaveNode();

	/// set binary huffman code and length of node
	void SetBinaryCode(AliHLTUInt64_t length, std::bitset<64> code) {
	        fBinaryCodeLength = length;
	        fBinaryCode = code;
	}
	/// set pointer to left child
	void SetLeftChild(AliHLTHuffmanNode* n) {
		fLeft = n;
	}
	/// set pointer to right child
	void SetRightChild(AliHLTHuffmanNode* n) {
		fRight = n;
	}
	/// Return length of huffman code
	AliHLTUInt64_t GetBinaryCodeLength() const {
		return fBinaryCodeLength;
	}
	/// Return binary huffman code
	const std::bitset<64>& GetBinaryCode() const {
		return fBinaryCode;
	}
	/// Return pointer to left Child
	AliHLTHuffmanNode* GetLeftChild() const {
		return fLeft;
	}
	/// Return pointer to right Child
	AliHLTHuffmanNode* GetRightChild() const {
		return fRight;
	}

private:
	AliHLTUInt8_t fBinaryCodeLength; // code length
	std::bitset<64> fBinaryCode; // WARNING: this fixed the maximum code length to 128
	AliHLTHuffmanNode* fLeft;    //! left neighbor
	AliHLTHuffmanNode* fRight;   //! right neighbor

ClassDef(AliHLTHuffmanLeaveNode, 1)
};

/**
 * @class AliHLTHuffman
 * Huffman code generator/encoder/decoder
 *
 * @ingroup alihlt_base
 */
class AliHLTHuffman: public TNamed, public AliHLTLogging {
public:
	AliHLTHuffman();
	AliHLTHuffman(const AliHLTHuffman& other);
	AliHLTHuffman(const char* name, UInt_t maxBits);
	~AliHLTHuffman();

	UInt_t InitMaxCodeLength();

	UInt_t GetMaxBits() const {return fMaxBits;}
	UInt_t GetMaxValue() const {return fMaxValue;}
	UInt_t GetMaxCodeLength() const {return fMaxCodeLength;}

	/// Return huffman code for a value
	const std::bitset<64>& Encode(const AliHLTUInt64_t v, AliHLTUInt64_t& codeLength) const;

	/// Return value for bit pattern, LSB first
        Bool_t DecodeLSB(std::bitset<64> /*bits*/, AliHLTUInt64_t& /*value*/, AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const;
	/// Return value for bit pattern, MSB first
        Bool_t DecodeMSB(std::bitset<64> /*bits*/, AliHLTUInt64_t& /*value*/, AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const;
	/// Return value for bit pattern using decoder node array, MSB first
        Bool_t FastDecodeMSB(std::bitset<64> bits, AliHLTUInt64_t& value,
			     AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const;

	/// Add a new training value (with optional weight) to the training sample
	Bool_t AddTrainingValue(const AliHLTUInt64_t value,
			const Float_t weight = 1.);
	/// Generate huffman tree from training sample
	Bool_t GenerateHuffmanTree();
	/// Print info about huffman en-/decoder
	void Print(Option_t* option = "short") const;
	/// Overload assignment operator
	AliHLTHuffman& operator =(const AliHLTHuffman& other);

        bool CheckConsistency() const;

        /**
         * Binary structure for fast access of node information
         * in the decoding
         */
        struct AliHuffmanDecodingNode {
	  AliHLTHuffmanNode* fParent;      // parent
          AliHLTInt64_t fValue;            // value
          AliHuffmanDecodingNode* fLeft;    // left neighbor
          AliHuffmanDecodingNode* fRight;   // right neighbor
          AliHLTUInt8_t fBinaryCodeLength; // code length
        };

        int EnableDecodingMap();

private:
        AliHuffmanDecodingNode* BuildDecodingNode(AliHLTHuffmanNode* node, vector<AliHuffmanDecodingNode>& decodingnodes) const;

	UInt_t fMaxBits;    // bit lenght
	UInt_t fMaxValue;   // maximum value
	std::vector<AliHLTHuffmanLeaveNode> fNodes; // array of nodes
	AliHLTHuffmanNode* fHuffTopNode;       // top node
	bool fReverseCode; // indicate the type of the binary code
	UInt_t fMaxCodeLength; //! maximum code length
	std::vector<AliHuffmanDecodingNode> fDecodingNodes; //! array of reduced nodes
	AliHuffmanDecodingNode* fDecodingTopNode; //! top node of reduced nodes

ClassDef(AliHLTHuffman, 4)
};

#endif
Commit	Line	Data
6a1b3945	1	//-- Mode: C++ --
	2	// $Id$
	3	#ifndef ALIHLTHUFFMAN_H
	4	#define ALIHLTHUFFMAN_H
	5	//* This file is property of and copyright by the ALICE HLT Project *
	6	//* ALICE Experiment at CERN, All rights reserved. *
	7	//* See cxx source for full Copyright notice *
	8
ebf7a8e8	9	/// @file AliHLTHuffman.h
6a1b3945	10	/// @author Thorsten Kollegger, Matthias Richter
	11	/// @date 2011-08-14
	12	/// @brief Huffman code generator/encoder/decode
	13
	14	#include "AliHLTLogging.h"
	15
	16	#include "TNamed.h"
	17
	18	#include <vector>
	19	#include <bitset>
	20	#include <string>
	21
	22	/**
	23	* @class AliHLTHuffmanNode
	24	* Huffman code nodes. This is the base class for two types of nodes,
	25	* AliHLTHuffmanTreeNode and AliHLTHuffmanLeaveNode. The latter nodes
	26	* represent the index array of values to huffman codes. The former are
	27	* used in a tree reaching from the value of highest occuremce to all
	28	* leaves. The two node types are defined in order to optimize the storage
	29	* format for the huffman table. Leave nodes don't need persistent pointers
	30	* to childs, tree nodes don't need persistent binary code values.
	31	*
	32	* @ingroup alihlt_base
	33	*/
	34	class AliHLTHuffmanNode: public TObject {
	35	public:
	36	/// default constructor
	37	AliHLTHuffmanNode();
	38	/// copy constructor
	39	AliHLTHuffmanNode(const AliHLTHuffmanNode& other);
	40	/// assignment operator
	41	AliHLTHuffmanNode& operator=(const AliHLTHuffmanNode& other);
	42	/// destructor
	43	virtual ~AliHLTHuffmanNode();
	44
	45	/// set symbol value of node
	46	void SetValue(AliHLTInt64_t v) {
	47	fValue = v;
	48	}
	49	/// add weight to node
	50	void AddWeight(Float_t w) {
	51	fWeight += w;
	52	}
	53	/// set weight of node
	54	void SetWeight(Float_t w) {
	55	fWeight = w;
	56	}
	57	/// return symbol value of node
	58	AliHLTInt64_t GetValue() const {
	59	return fValue;
	60	}
	61	/// return weight of node
	62	Float_t GetWeight() const {
	63	return fWeight;
	64	}
	65
9409b4b1	66	/// assign huffman code to this node and its children
	67	/// bReverse = true the bit corresponding to the parent is shifted and
	68	/// decoding needs to start from the MSB of the code
	69	void AssignCode(bool bReverse=false);
6a1b3945	70	/// set binary huffman code and length of node
	71	virtual void SetBinaryCode(AliHLTUInt64_t length, std::bitset<64> code) = 0;
	72	/// set pointer to left child
	73	virtual void SetLeftChild(AliHLTHuffmanNode* n) = 0;
	74	/// set pointer to right child
	75	virtual void SetRightChild(AliHLTHuffmanNode* n) = 0;
	76	/// Return length of huffman code
	77	virtual AliHLTUInt64_t GetBinaryCodeLength() const = 0;
	78	/// Return binary huffman code
	79	virtual const std::bitset<64>& GetBinaryCode() const = 0;
	80	/// Return pointer to left Child
	81	virtual AliHLTHuffmanNode* GetLeftChild() const = 0;
	82	/// Return pointer to right Child
	83	virtual AliHLTHuffmanNode* GetRightChild() const = 0;
	84
	85	/// Print information about node
	86	void Print(Option_t* option = "") const;
	87	/// Overload less operator, based on node weights
	88	Bool_t operator <(const AliHLTHuffmanNode& other) const {
	89	return (this->GetWeight() < other.GetWeight());
	90	}
	91	class less {
	92	public:
	93	bool operator()(const AliHLTHuffmanNode* i1,
	94	const AliHLTHuffmanNode* i2) const {
	95	//reverse sort, less likely to most likely
	96	return ((i1) < (i2));
	97	}
	98	};
	99
	100	private:
	101	AliHLTInt64_t fValue; // value
	102	Float_t fWeight; // weight
	103
	104	ClassDef(AliHLTHuffmanNode, 1)
	105	};
	106
	107	/**
	108	* @class AliHLTHuffmanTreeNode
	109	* Tree nodes store the childs persistently. The binary code is
	110	* a transient member.
	111	*/
	112	class AliHLTHuffmanTreeNode: public AliHLTHuffmanNode {
	113	public:
	114	/// default constructor
	115	AliHLTHuffmanTreeNode();
	116	/// copy constructor
	117	AliHLTHuffmanTreeNode(const AliHLTHuffmanTreeNode& other);
	118	/// assignment operator
	119	AliHLTHuffmanTreeNode& operator=(const AliHLTHuffmanTreeNode& other);
	120	/// constructor for internal nodes, based on two input nodes (leaves or internal nodes)
	121	AliHLTHuffmanTreeNode(AliHLTHuffmanNode* l, AliHLTHuffmanNode* r);
	122	/// desstructor
	123	~AliHLTHuffmanTreeNode();
	124
	125	/// set binary huffman code and length of node
	126	void SetBinaryCode(AliHLTUInt64_t length, std::bitset<64> code) {
	127	fBinaryCodeLength = length;
	128	fBinaryCode = code;
	129	}
	130
	131	/// set pointer to left child
	132	void SetLeftChild(AliHLTHuffmanNode* n) {
	133	fLeft = n;
134	}
135	/// set pointer to right child
136	void SetRightChild(AliHLTHuffmanNode* n) {
137	fRight = n;
138	}
139	/// Return length of huffman code
140	AliHLTUInt64_t GetBinaryCodeLength() const {
141	return fBinaryCodeLength;
142	}
143	/// Return binary huffman code
144	const std::bitset<64>& GetBinaryCode() const {
145	return fBinaryCode;
146	}
147	/// Return pointer to left Child
148	AliHLTHuffmanNode* GetLeftChild() const {
149	return fLeft;
150	}
151	/// Return pointer to right Child
152	AliHLTHuffmanNode* GetRightChild() const {
153	return fRight;
154	}
155
156	private:
157	AliHLTUInt8_t fBinaryCodeLength; //! code length
158	std::bitset<64> fBinaryCode; //! WARNING: this fixed the maximum code length to 128
159	AliHLTHuffmanNode* fLeft; // left neighbor
160	AliHLTHuffmanNode* fRight; // right neighbor
161
162	ClassDef(AliHLTHuffmanTreeNode, 1)
163	};
164
165	/**
166	* @class AliHLTHuffmanLeaveNode
167	* Leave nodes store the binary code persistently, while the childs are transient
168	*/
169	class AliHLTHuffmanLeaveNode: public AliHLTHuffmanNode {
170	public:
171	/// default constructor
172	AliHLTHuffmanLeaveNode();
173	/// copy constructor
174	AliHLTHuffmanLeaveNode(const AliHLTHuffmanLeaveNode& other);
175	/// assignment operator
176	AliHLTHuffmanLeaveNode& operator=(const AliHLTHuffmanLeaveNode& other);
177	/// destructor
178	~AliHLTHuffmanLeaveNode();
179
180	/// set binary huffman code and length of node
181	void SetBinaryCode(AliHLTUInt64_t length, std::bitset<64> code) {
182	fBinaryCodeLength = length;
183	fBinaryCode = code;
184	}
185	/// set pointer to left child
186	void SetLeftChild(AliHLTHuffmanNode* n) {
187	fLeft = n;
188	}
189	/// set pointer to right child
190	void SetRightChild(AliHLTHuffmanNode* n) {
191	fRight = n;
192	}
193	/// Return length of huffman code
194	AliHLTUInt64_t GetBinaryCodeLength() const {
195	return fBinaryCodeLength;
196	}
197	/// Return binary huffman code
198	const std::bitset<64>& GetBinaryCode() const {
199	return fBinaryCode;
200	}
201	/// Return pointer to left Child
202	AliHLTHuffmanNode* GetLeftChild() const {
203	return fLeft;
204	}
205	/// Return pointer to right Child
206	AliHLTHuffmanNode* GetRightChild() const {
207	return fRight;
208	}
209
210	private:
211	AliHLTUInt8_t fBinaryCodeLength; // code length
212	std::bitset<64> fBinaryCode; // WARNING: this fixed the maximum code length to 128
213	AliHLTHuffmanNode* fLeft; //! left neighbor
214	AliHLTHuffmanNode* fRight; //! right neighbor
215
216	ClassDef(AliHLTHuffmanLeaveNode, 1)
217	};
218
219	/**
220	* @class AliHLTHuffman
221	* Huffman code generator/encoder/decoder
222	*
223	* @ingroup alihlt_base
224	*/
225	class AliHLTHuffman: public TNamed, public AliHLTLogging {
226	public:
227	AliHLTHuffman();
228	AliHLTHuffman(const AliHLTHuffman& other);
229	AliHLTHuffman(const char* name, UInt_t maxBits);
230	~AliHLTHuffman();
231
6e848d29	232	UInt_t InitMaxCodeLength();
6e848d29	233
6a1b3945	234	UInt_t GetMaxBits() const {return fMaxBits;}
6a1b3945	235	UInt_t GetMaxValue() const {return fMaxValue;}
6e848d29	236	UInt_t GetMaxCodeLength() const {return fMaxCodeLength;}
6a1b3945	237
	238	/// Return huffman code for a value
	239	const std::bitset<64>& Encode(const AliHLTUInt64_t v, AliHLTUInt64_t& codeLength) const;
	240
6e848d29	241	/// Return value for bit pattern, LSB first
7227b364	242	Bool_t DecodeLSB(std::bitset<64> /bits/, AliHLTUInt64_t& /value/, AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const;
6e848d29	243	/// Return value for bit pattern, MSB first
7227b364	244	Bool_t DecodeMSB(std::bitset<64> /bits/, AliHLTUInt64_t& /value/, AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const;
	245	/// Return value for bit pattern using decoder node array, MSB first
	246	Bool_t FastDecodeMSB(std::bitset<64> bits, AliHLTUInt64_t& value,
	247	AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const;
6e848d29	248
6a1b3945	249	/// Add a new training value (with optional weight) to the training sample
	250	Bool_t AddTrainingValue(const AliHLTUInt64_t value,
	251	const Float_t weight = 1.);
	252	/// Generate huffman tree from training sample
	253	Bool_t GenerateHuffmanTree();
	254	/// Print info about huffman en-/decoder
	255	void Print(Option_t* option = "short") const;
	256	/// Overload assignment operator
	257	AliHLTHuffman& operator =(const AliHLTHuffman& other);
	258
9409b4b1	259	bool CheckConsistency() const;
9409b4b1	260
7227b364	261	/**
	262	* Binary structure for fast access of node information
	263	* in the decoding
	264	*/
	265	struct AliHuffmanDecodingNode {
	266	AliHLTHuffmanNode* fParent; // parent
	267	AliHLTInt64_t fValue; // value
	268	AliHuffmanDecodingNode* fLeft; // left neighbor
	269	AliHuffmanDecodingNode* fRight; // right neighbor
	270	AliHLTUInt8_t fBinaryCodeLength; // code length
	271	};
	272
	273	int EnableDecodingMap();
	274
6a1b3945	275	private:
7227b364	276	AliHuffmanDecodingNode* BuildDecodingNode(AliHLTHuffmanNode* node, vector<AliHuffmanDecodingNode>& decodingnodes) const;
7227b364	277
6a1b3945	278	UInt_t fMaxBits; // bit lenght
	279	UInt_t fMaxValue; // maximum value
	280	std::vector<AliHLTHuffmanLeaveNode> fNodes; // array of nodes
	281	AliHLTHuffmanNode* fHuffTopNode; // top node
9409b4b1	282	bool fReverseCode; // indicate the type of the binary code
6e848d29	283	UInt_t fMaxCodeLength; //! maximum code length
7227b364	284	std::vector<AliHuffmanDecodingNode> fDecodingNodes; //! array of reduced nodes
7227b364	285	AliHuffmanDecodingNode* fDecodingTopNode; //! top node of reduced nodes
6a1b3945	286
7227b364	287	ClassDef(AliHLTHuffman, 4)
6a1b3945	288	};
	289
	290	#endif