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