C++ Generierung von Elias Gamma Kodewörtern

#ifndef ELIASGAMMACODE_H
#define ELIASGAMMACODE_H

#include <string>

#include <boost/unordered_map.hpp>

class EliasGammaCode {

/***************************************************************************/
public:

//---------------------------------------------------------------------------
//  Public class methods
//---------------------------------------------------------------------------

  // Erzeugt den Gamma-Kode zu der uebergebenen Zahl in lesbarer Form.
  static std::string const gammaCode(const uint32_t number);

  // Dekodiert ein Elias-Gamma-Kodewort zur zugrunde liegenden Zahl.
  static uint32_t gammaDecode(const std::string & codeword);

  // Errechnet die Laenge der Gamma-Kode-Darstellung einer Zahl in Bit.
  static uint8_t gammaCodeLength(const uint32_t number);

/***************************************************************************/

private:

//---------------------------------------------------------------------------
//  Private class methods
//---------------------------------------------------------------------------

  // Berechnet die Darstellung einer Zahl als Gamma-Kode.
  inline static std::string calcNewGammaCode(const uint32_t number);

  // Berechnet die zugrunde liegende Zahl einer Gamma-kodierten Darstellung.
  inline static uint32_t calcNewDecodedGamma(const std::string & codeword);

  // Berechnet die Laenge einer Zahl kodiert mit Elias-Gamma-Kode.
  inline static uint8_t calcNewGammaCodeLength(const uint32_t number);

//---------------------------------------------------------------------------
//  Private class variables
//---------------------------------------------------------------------------

  // Eine lookup-table fuer zu generierende Gamma-Codes.
  static boost::unordered_map<const uint32_t, const std::string> gammaCodeLookupTable;
  static boost::unordered_map<const uint32_t, const std::string>::const_iterator gammaCodeLUTIterator;

  // Eine lookup-table fuer dekodierte Gamma-Codes.
  static boost::unordered_map<const std::string, const uint32_t> gammaDecodeLookupTable;
  static boost::unordered_map<const std::string, const uint32_t>::const_iterator gammaDecodeLUTIterator;

  // Eine lookup-table fuer die Laenge von Gamma-Codes.
  static boost::unordered_map<const uint32_t, const uint8_t> gammaCodeLengthLookupTable;
  static boost::unordered_map<const uint32_t, const uint8_t>::const_iterator gammaCodeLengthLUTIterator;
};

#endif // ELIASGAMMACODE_H

/** @class EliasGammaCode
 *
 * Die Klasse dient als Utility-Klasse und enthaelt ausschliesslich statische
 * Methoden, die im Zusammenhang mit der Gamma-Kodierung von Repeats stehen.
 *
 * Neben der Berechnung des Elias-Gamma-Kodes einer Zahl erlaubt sie die
 * Ermittlung der Laenge einer solchen Darstellung in Bits und deren Dekodierung.
 **/

//---------------------------------------------------------------------------
//  Includes
//---------------------------------------------------------------------------

#include "BinaryCode.h"
#include "EliasGammaCode.h"

boost::unordered_map<const uint32_t, const std::string> EliasGammaCode::gammaCodeLookupTable;
boost::unordered_map<const uint32_t, const std::string>::const_iterator EliasGammaCode::gammaCodeLUTIterator;

boost::unordered_map<const std::string, const uint32_t> EliasGammaCode::gammaDecodeLookupTable;
boost::unordered_map<const std::string, const uint32_t>::const_iterator EliasGammaCode::gammaDecodeLUTIterator;

boost::unordered_map<const uint32_t, const uint8_t> EliasGammaCode::gammaCodeLengthLookupTable;
boost::unordered_map<const uint32_t, const uint8_t>::const_iterator EliasGammaCode::gammaCodeLengthLUTIterator;

/***************************************************************************\
                           Public Class Methods
\***************************************************************************/

/**
 * @param number Eine Ganzzahl >= 0.
 *
 * Erzeugt den Gamma-Kode zu der uebergebenen Zahl als Folge von "0"- und "1"-Symbolen.
 *
 * z.B. gammaCode(146) = 000000010010011
**/
std::string const EliasGammaCode::gammaCode(const uint32_t number) {
  std::string sresult;
  gammaCodeLUTIterator = EliasGammaCode::gammaCodeLookupTable.find(number);

  // pruefe, ob der Code berechnet wurde; wenn nicht, berechne neu
  if (gammaCodeLUTIterator == EliasGammaCode::gammaCodeLookupTable.end()) {
    sresult = EliasGammaCode::calcNewGammaCode(number);
    EliasGammaCode::gammaCodeLookupTable.insert(std::make_pair(number, sresult));
  } else {
    sresult = gammaCodeLUTIterator->second;
  }

  return sresult;
}

/**
 * @brief EliasGammaCode::gammaDecode
 *
 * @param codeword Ein Gamma-kodiertes Kodewort, bestehend aus einer Folge von "0"-
 * und "1"-Symbolen.
 *
 * @throw std::invalid_argument Wird ausgeloest, wenn ein leeres Kodewort angegeben wird.
 *
 * Dekodiert ein Elias-Gamma-Kodewort und liefert die urspruengliche Zahl >= 0.
**/
uint32_t EliasGammaCode::gammaDecode(const std::string & codeword) {
  if (codeword.empty()) {
    throw std::invalid_argument("# EliasGammaCode::gammaDecode - zu dekodierendes Kodewort ist leer.");
  }

  uint32_t result = 0;
  gammaDecodeLUTIterator = EliasGammaCode::gammaDecodeLookupTable.find(codeword);

  // Pruefe, ob die Zahl schon berechnet wurde; wenn nicht, berechne neu
  if (gammaDecodeLUTIterator == EliasGammaCode::gammaDecodeLookupTable.end()) {
    result = EliasGammaCode::calcNewDecodedGamma(codeword);
    EliasGammaCode::gammaDecodeLookupTable.insert(std::make_pair(codeword, result));
  } else {
    result = gammaDecodeLUTIterator->second;
  }

  return result;
}

/**
 * @param number Eine Ganzzahl >= 0.
 *
 * Errechnet die Laenge der Gamma-Kode-Darstellung einer Zahl in Bit.
**/
uint8_t EliasGammaCode::gammaCodeLength(const uint32_t number) {
  uint8_t result = 0;
  gammaCodeLengthLUTIterator = EliasGammaCode::gammaCodeLengthLookupTable.find(number);

  // pruefe, ob die Laenge berechnet wurde; wenn nicht, berechne neu
  if (gammaCodeLengthLUTIterator == EliasGammaCode::gammaCodeLengthLookupTable.end()) {
    result = EliasGammaCode::calcNewGammaCodeLength(number);
    EliasGammaCode::gammaCodeLengthLookupTable.insert(std::make_pair(number, result));
  } else {
    result = gammaCodeLengthLUTIterator->second;
  }

  return result;
}

/***************************************************************************\
                           Private Class Methods
\***************************************************************************/

// Berechnet einen neuen Elias-Gamma-Kode.
inline std::string EliasGammaCode::calcNewGammaCode(const uint32_t number) {
  const uint32_t calc = number +1;
  std::string result;

  const uint8_t binaryCodeLength = BinaryCode::binCodeLength(calc);
  const boost::dynamic_bitset<> bitRepresentation(binaryCodeLength, calc);
  boost::to_string(bitRepresentation, result);

  const uint8_t bitsToPrepend = bitRepresentation.size() -1;
  const std::string zeros(bitsToPrepend, '0');
  result.insert(0, zeros);

  return result;
}

// Berechnet die zugrunde liegende Zahl einer Gamma-kodierten Darstellung.
inline uint32_t EliasGammaCode::calcNewDecodedGamma(const std::string & codeword) {
  const uint8_t positionOfFirst1 = codeword.find_first_of("1");
  const std::string codedNumber(codeword.substr(positionOfFirst1));
  const boost::dynamic_bitset<> bitRepresentation(codedNumber);

  return bitRepresentation.to_ulong() -1;
}

// Berechnet die Laenge einer Zahl kodiert mit Elias-Gamma-Kode.
inline uint8_t EliasGammaCode::calcNewGammaCodeLength(const uint32_t number) {
  const uint32_t calc = number +1;

  const uint8_t binaryCodeLength = BinaryCode::binCodeLength(calc);
  const boost::dynamic_bitset<> bitRepresentation(binaryCodeLength, calc);

  return bitRepresentation.size() + bitRepresentation.size() -1;
}