896104237ee457ce00efa224fce8263b20c01a3c
[u/mrichter/AliRoot.git] / HLT / BASE / AliHLTHuffman.h
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  */
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
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);
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
232         UInt_t GetMaxBits() const {return fMaxBits;}
233         UInt_t GetMaxValue() const {return fMaxValue;}
234
235         /// Return huffman code for a value
236         const std::bitset<64>& Encode(const AliHLTUInt64_t v, AliHLTUInt64_t& codeLength) const;
237
238         /// Return value for bit pattern
239         Bool_t Decode(std::bitset<64> /*bits*/, AliHLTUInt64_t& /*value*/, AliHLTUInt32_t& length, AliHLTUInt32_t& codeLength) const;
240         /// Add a new training value (with optional weight) to the training sample
241         Bool_t AddTrainingValue(const AliHLTUInt64_t value,
242                         const Float_t weight = 1.);
243         /// Generate huffman tree from training sample
244         Bool_t GenerateHuffmanTree();
245         /// Print info about huffman en-/decoder
246         void Print(Option_t* option = "short") const;
247         /// Overload assignment operator
248         AliHLTHuffman& operator =(const AliHLTHuffman& other);
249
250         bool CheckConsistency() const;
251
252 private:
253         UInt_t fMaxBits;    // bit lenght
254         UInt_t fMaxValue;   // maximum value
255         std::vector<AliHLTHuffmanLeaveNode> fNodes; // array of nodes
256         AliHLTHuffmanNode* fHuffTopNode;       // top node
257         bool fReverseCode; // indicate the type of the binary code
258
259 ClassDef(AliHLTHuffman, 2)
260 };
261
262 #endif