code cleanup: renaming functions; adding prototype code for later development; no...
[u/mrichter/AliRoot.git] / HLT / BASE / AliHLTHuffman.h
CommitLineData
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
9/// @file AliHLTDataHuffman.h
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 */
34class AliHLTHuffmanNode: public TObject {
35public:
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
100private:
101 AliHLTInt64_t fValue; // value
102 Float_t fWeight; // weight
103
104ClassDef(AliHLTHuffmanNode, 1)
105};
106
107/**
108 * @class AliHLTHuffmanTreeNode
109 * Tree nodes store the childs persistently. The binary code is
110 * a transient member.
111 */
112class AliHLTHuffmanTreeNode: public AliHLTHuffmanNode {
113public:
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
156private:
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
162ClassDef(AliHLTHuffmanTreeNode, 1)
163};
164
165/**
166 * @class AliHLTHuffmanLeaveNode
167 * Leave nodes store the binary code persistently, while the childs are transient
168 */
169class AliHLTHuffmanLeaveNode: public AliHLTHuffmanNode {
170public:
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
210private:
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
216ClassDef(AliHLTHuffmanLeaveNode, 1)
217};
218
219/**
220 * @class AliHLTHuffman
221 * Huffman code generator/encoder/decoder
222 *
223 * @ingroup alihlt_base
224 */
225class AliHLTHuffman: public TNamed, public AliHLTLogging {
226public:
227 AliHLTHuffman();
228 AliHLTHuffman(const AliHLTHuffman& other);
229 AliHLTHuffman(const char* name, UInt_t maxBits);
230 ~AliHLTHuffman();
231
6e848d29 232 UInt_t InitMaxCodeLength();
233
6a1b3945 234 UInt_t GetMaxBits() const {return fMaxBits;}
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;
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 275private:
7227b364 276 AliHuffmanDecodingNode* BuildDecodingNode(AliHLTHuffmanNode* node, vector<AliHuffmanDecodingNode>& decodingnodes) const;
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
285 AliHuffmanDecodingNode* fDecodingTopNode; //! top node of reduced nodes
6a1b3945 286
7227b364 287ClassDef(AliHLTHuffman, 4)
6a1b3945 288};
289
290#endif