Program Listing for File HuffmanWaveletTree.h

↰ Return to documentation for file (ADS/succinct/HuffmanWaveletTree.h)

/*--------------------------------------------------------------------------*/
/*------------------------ File HuffmanWaveletTree.h -----------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/succinct/BitVector.h"
#include "ADS/succinct/CompactRankSelect.h"
#include "ADS/succinct/RankSelect.h"

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <span>
#include <type_traits>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------ CLASS HuffmanWaveletTree ------------------------*/
/*--------------------------------------------------------------------------*/

template< class RS = RankSelect >
class HuffmanWaveletTree {

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

 HuffmanWaveletTree( void ) = default;

 explicit HuffmanWaveletTree( std::span< const std::uint32_t > x ,
                              bool withSelect = true );

 [[nodiscard]] std::size_t size( void ) const { return( f_n ); }

 [[nodiscard]] bool empty( void ) const { return( f_n == 0 ); }

 [[nodiscard]] std::size_t sigma( void ) const { return( f_len.size() ); }

 [[nodiscard]] std::uint32_t access( std::size_t i ) const;

 [[nodiscard]] std::uint32_t operator[]( std::size_t i ) const {
  return( access( i ) );
  }

 [[nodiscard]] std::pair< std::uint32_t , std::size_t > accessRank(
                                                       std::size_t i ) const;

 [[nodiscard]] std::size_t rank( std::uint32_t c , std::size_t i ) const;

 [[nodiscard]] std::pair< std::size_t , std::size_t > rank( std::uint32_t c ,
                                                           std::size_t i ,
                                                           std::size_t j )
  const;

 [[nodiscard]] std::size_t select( std::uint32_t c , std::size_t k ) const;

 [[nodiscard]] int codeLength( std::uint32_t c ) const {
  return( c < f_len.size() ? f_len[ c ] : 0 );
  }

 [[nodiscard]] std::size_t sizeInBits( void ) const;

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

 struct Node {
  std::uint64_t off = 0 , ones = 0;
  std::int32_t child[ 2 ] = { 0 , 0 };
  };

 [[nodiscard]] static RS directory( BitVector b , bool withSelect ) {
  if constexpr( std::is_same_v< RS , RankSelect > )
   return( RS( std::move( b ) , withSelect ? RankSelect::Selects::BOTH
                                           : RankSelect::Selects::NONE ) );
  else return( RS( std::move( b ) ) );
  }

 [[nodiscard]] bool bit( std::uint32_t c , int d ) const {
  return( ( f_code[ c ] >> ( f_len[ c ] - 1 - d ) ) & 1 );
  }

 std::size_t f_n = 0;
 std::vector< std::uint64_t > f_code;
 std::vector< std::uint8_t > f_len;
 std::vector< Node > f_node;
 RS f_B;

 };  // end( class HuffmanWaveletTree )

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

}  // end( namespace ADS )

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

#include "ADS/succinct/impl/HuffmanWaveletTree.tpp"

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

#endif  /* HuffmanWaveletTree.h included */

/*--------------------------------------------------------------------------*/
/*---------------------- End File HuffmanWaveletTree.h ---------------------*/
/*--------------------------------------------------------------------------*/