Program Listing for File BurrowsWheeler.h

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

/*--------------------------------------------------------------------------*/
/*------------------------- File BurrowsWheeler.h --------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/compression/CanonicalHuffman.h"
#include "ADS/compression/PackedBits.h"
#include "ADS/string/SuffixArray.h"

#include <algorithm>
#include <bit>
#include <cstddef>
#include <cstdint>
#include <map>
#include <numeric>
#include <span>
#include <string>
#include <string_view>
#include <utility>
#include <vector>

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

namespace ADS {

struct BWT {
 std::string last;
 std::size_t primary;
 friend bool operator==( const BWT & a , const BWT & b ) = default;
 };

[[nodiscard]] inline BWT bwt( std::string_view s );

[[nodiscard]] inline std::vector< std::size_t > lfMapping( const BWT & b );

[[nodiscard]] inline std::string inverseBwt( const BWT & b );

[[nodiscard]] inline std::vector< std::uint8_t > moveToFront(
                              std::string_view s , std::string_view alphabet );

[[nodiscard]] inline std::vector< std::uint8_t > moveToFront(
                                                         std::string_view s );

[[nodiscard]] inline std::string inverseMoveToFront(
                                       const std::vector< std::uint8_t > & x ,
                                       std::string_view alphabet );

[[nodiscard]] inline std::string inverseMoveToFront(
                                      const std::vector< std::uint8_t > & x );

[[nodiscard]] inline std::vector< std::pair< std::size_t , char > >
                                        runLengthEncode( std::string_view s );

[[nodiscard]] inline std::string runLengthDecode(
                   const std::vector< std::pair< std::size_t , char > > & R );

[[nodiscard]] inline std::vector< std::uint32_t > zeroRunEncode(
                                       const std::vector< std::uint8_t > & x );

[[nodiscard]] inline std::vector< std::uint8_t > zeroRunDecode(
                                      const std::vector< std::uint32_t > & y );

[[nodiscard]] inline std::vector< std::uint8_t > bzipCompress(
                            std::string_view s , std::size_t block = 900000 );

[[nodiscard]] inline std::string bzipDecompress(
                                     std::span< const std::uint8_t > code );

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

}  // end( namespace ADS )

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

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

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

#endif  /* BurrowsWheeler.h included */

/*--------------------------------------------------------------------------*/
/*----------------------- End File BurrowsWheeler.h ------------------------*/
/*--------------------------------------------------------------------------*/