Program Listing for File LongestCommonExtension.h

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

/*--------------------------------------------------------------------------*/
/*-------------------- File LongestCommonExtension.h -----------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

#include <concepts>
#include <cstddef>
#include <cstdint>
#include <string>
#include <string_view>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*---------------------------- LceIndex ------------------------------------*/
/*--------------------------------------------------------------------------*/

template< class I = std::uint32_t >
 requires( std::same_as< I , std::uint32_t > ||
           std::same_as< I , std::uint64_t > )
class LceIndex {

/*--------------------------------------------------------------------------*/
/*----------------------- PUBLIC PART OF THE CLASS -------------------------*/
/*--------------------------------------------------------------------------*/

 public:

 explicit LceIndex( std::string_view T );

 [[nodiscard]] std::size_t lce( std::size_t i , std::size_t j ) const;

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

/*--------------------------------------------------------------------------*/
/*--------------------- PRIVATE PART OF THE CLASS --------------------------*/
/*--------------------------------------------------------------------------*/

 private:

#if defined( __GNUC__ ) || defined( __clang__ )
 [[gnu::noinline]]
#endif
 [[nodiscard]] std::size_t longer( std::size_t i , std::size_t j ,
                                   std::size_t far ) const;

 [[nodiscard]] I minimum( std::size_t a , std::size_t c ) const;

 std::string f_T;
 std::size_t f_n = 0;
 std::vector< I > f_rank;
 std::vector< I > f_line;
 std::size_t f_shift = 0;
 std::vector< std::uint16_t > f_word;
 std::vector< I > f_inner;
 std::vector< I > f_top;
 std::size_t f_blocks = 0;
 std::size_t f_groups = 0;

 };  // end( class LceIndex )

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

}  // end( namespace ADS )

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

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

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

#endif  /* LongestCommonExtension.h included */

/*--------------------------------------------------------------------------*/
/*-------------------- End File LongestCommonExtension.h -------------------*/
/*--------------------------------------------------------------------------*/