Program Listing for File CanonicalHuffman.h

↰ Return to documentation for file (ADS/compression/CanonicalHuffman.h)

/*--------------------------------------------------------------------------*/
/*------------------------ File CanonicalHuffman.h -------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_CanonicalHuffman
 #define __ADS_CanonicalHuffman
                      /* self-identification: #endif constant */

/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/Contract.h"
#include "ADS/compression/PackedBits.h"
#include "ADS/string/Huffman.h"

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <map>
#include <span>
#include <string>
#include <type_traits>
#include <vector>

/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/

namespace ADS {

template< class C , class F >
[[nodiscard]] std::map< C , int > huffmanLengths(
                                            const std::map< C , F > & freq );

template< class C , class F >
[[nodiscard]] std::map< C , int > limitedLengths(
                                     const std::map< C , F > & freq , int L );

/*--------------------------------------------------------------------------*/
/*------------------------- CLASS CanonicalHuffman -------------------------*/
/*--------------------------------------------------------------------------*/

template< class C >
class CanonicalHuffman {

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

 using symbol_type = C;

 explicit CanonicalHuffman( const std::map< C , int > & lengths );

 template< class F >
 [[nodiscard]] static CanonicalHuffman fromFrequencies(
                                            const std::map< C , F > & freq );

 [[nodiscard]] const std::map< C , int > & lengths( void ) const {
  return( f_len );
  }

 [[nodiscard]] int maxLength( void ) const { return( f_max ); }

 [[nodiscard]] std::uint64_t firstCode( int l ) const;

 [[nodiscard]] std::string code( const C & c ) const;

 void encode( const C & c , PackedBitWriter & w ) const;

 [[nodiscard]] std::vector< std::uint8_t > encode(
                                         std::span< const C > text ) const;

 [[nodiscard]] C decode( PackedBitReader & r ) const;

 [[nodiscard]] std::vector< C > decode(
         const std::vector< std::uint8_t > & bits , std::size_t n ) const;

/*--------------------------------------------------------------------------*/
 private:

 std::map< C , int > f_len;
 std::map< C , std::uint64_t > f_code;
 std::vector< std::uint64_t > f_fc;
 std::vector< std::vector< C > > f_symb;
 int f_max = 0;

 };  // end( class CanonicalHuffman )

/*--------------------------------------------------------------------------*/

}  // end( namespace ADS )

/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/compression/impl/CanonicalHuffman.tpp"

/*--------------------------------------------------------------------------*/

#endif  /* CanonicalHuffman.h included */

/*--------------------------------------------------------------------------*/
/*---------------------- End File CanonicalHuffman.h -----------------------*/
/*--------------------------------------------------------------------------*/