Program Listing for File FrontCoding.h

↰ Return to documentation for file (ADS/string/FrontCoding.h)

/*--------------------------------------------------------------------------*/
/*-------------------------- File FrontCoding.h ----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/string/PrefixSearch.h"

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <string>
#include <string_view>
#include <utility>
#include <vector>

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

namespace ADS {

using FrontPair = std::pair< std::size_t , std::string >;

[[nodiscard]] inline std::vector< FrontPair > frontCode(
                                       const std::vector< std::string > & D );

[[nodiscard]] inline std::vector< std::string > frontDecode(
                                       const std::vector< FrontPair > & F );

inline void encodeLength( std::uint32_t l , std::string & out );

[[nodiscard]] inline std::uint32_t decodeLength( std::string_view in ,
                                                 std::size_t & pos );

/*--------------------------------------------------------------------------*/
/*---------------------- CLASS FrontCodedDictionary ------------------------*/
/*--------------------------------------------------------------------------*/

class FrontCodedDictionary {

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

 [[nodiscard]] static FrontCodedDictionary bucketed(
                           const std::vector< std::string > & D ,
                           std::size_t b );

 [[nodiscard]] static FrontCodedDictionary localityPreserving(
                           const std::vector< std::string > & D , double c );

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

 [[nodiscard]] std::size_t decodeCost( std::size_t i ) const;

 [[nodiscard]] std::size_t lexicographicPosition( std::string_view Q ) const;

 [[nodiscard]] std::size_t prefixEnd( std::string_view P ) const;

 [[nodiscard]] std::pair< std::size_t , std::size_t > prefixRange(
                                                   std::string_view P ) const;

 [[nodiscard]] std::size_t rankInBucket( std::size_t k , std::string_view P ,
                                         bool upper ) const;

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

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

 [[nodiscard]] std::size_t anchor( std::size_t k ) const;

 [[nodiscard]] std::string_view anchorString( std::size_t k ) const;

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

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

/*------------------------- THE STANDARD INTERFACE -------------------------*/

 // a constant view of the strings in their order, decoded one after the
 // other, forward; *it is the string decoded in the iterator

 class const_iterator {
  public:
  using reference = const std::string &;
  using value_type = std::string;
  using difference_type = std::ptrdiff_t;
  using iterator_concept = std::forward_iterator_tag;
  using iterator_category = std::input_iterator_tag;

  const_iterator( void ) = default;
  const_iterator( const FrontCodedDictionary * d , std::size_t i )
   : f_d( d ) , f_i( i ) { load(); }

  reference operator*( void ) const { return( f_s ); }
  const_iterator & operator++( void ) {
   ++f_i;
   load();
   return( *this );
   }
  const_iterator operator++( int ) { auto t = *this; ++*this; return( t ); }
  bool operator==( const const_iterator & o ) const {
   return( f_i == o.f_i );
   }

  private:
  void load( void ) {
   if( f_d && ( f_i < f_d->size() ) ) {
    f_s.resize( f_d->f_l[ f_i ] );
    f_s.append( f_d->rest( f_i ) );
    }
   }

  const FrontCodedDictionary * f_d = nullptr;
  std::size_t f_i = 0;
  std::string f_s;
  };

 using value_type = std::string;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = const std::string &;
 using const_reference = const std::string &;
 using iterator = const_iterator;

 [[nodiscard]] const_iterator begin( void ) const {
  return( const_iterator( this , 0 ) );
  }
 [[nodiscard]] const_iterator end( void ) const {
  return( const_iterator( this , size() ) );
  }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

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

 FrontCodedDictionary( void ) = default;

 template< class A >
 static FrontCodedDictionary build( const std::vector< std::string > & D ,
                                    A anchor );

 [[nodiscard]] std::string_view rest( std::size_t i ) const;

 [[nodiscard]] std::size_t anchorBefore( std::size_t i ) const;

 [[nodiscard]] std::size_t anchorRank( std::string_view P ,
                                       bool upper ) const;

 std::vector< std::size_t > f_l;
 std::vector< std::size_t > f_off;
 std::string f_chars;
 std::vector< std::size_t > f_a;
 std::size_t f_bytes = 0;

 };  // end( class FrontCodedDictionary )

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

}  // end( namespace ADS )

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

#include "ADS/string/impl/FrontCoding.tpp"

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

#endif  /* FrontCoding.h included */

/*--------------------------------------------------------------------------*/
/*------------------------- End File FrontCoding.h -------------------------*/
/*--------------------------------------------------------------------------*/