Program Listing for File SuffixArray.h

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

/*--------------------------------------------------------------------------*/
/*--------------------------- File SuffixArray.h ---------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/search/RangeMinimum.h"
#include "ADS/sort/RadixSort.h"

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <numeric>
#include <string_view>
#include <tuple>
#include <utility>
#include <vector>

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

namespace ADS {

using Symbols = std::vector< std::size_t >;

[[nodiscard]] inline Symbols toSymbols( std::string_view T );

[[nodiscard]] inline std::vector< std::size_t > suffixArraySorting(
                                                         const Symbols & T );
[[nodiscard]] inline std::vector< std::size_t > suffixArraySorting(
                                                        std::string_view T );

[[nodiscard]] inline std::vector< std::size_t > suffixArrayDoubling(
                                                         const Symbols & T );
[[nodiscard]] inline std::vector< std::size_t > suffixArrayDoubling(
                                                        std::string_view T );

[[nodiscard]] inline std::vector< std::size_t > suffixArrayLarssonSadakane(
                                                         const Symbols & T );
[[nodiscard]] inline std::vector< std::size_t > suffixArrayLarssonSadakane(
                                                        std::string_view T );

[[nodiscard]] inline std::vector< std::size_t > suffixArraySkew(
                                          const Symbols & T , std::size_t K );
[[nodiscard]] inline std::vector< std::size_t > suffixArraySkew(
                                                        std::string_view T );

[[nodiscard]] inline std::vector< std::size_t > suffixArraySais(
                                          const Symbols & T , std::size_t K );
[[nodiscard]] inline std::vector< std::size_t > suffixArraySais(
                                                        std::string_view T );

[[nodiscard]] inline std::vector< std::size_t > suffixArrayScan(
                                          const Symbols & T , std::size_t m );
[[nodiscard]] inline std::vector< std::size_t > suffixArrayScan(
                                       std::string_view T , std::size_t m );

[[nodiscard]] inline std::vector< std::size_t > inversePermutation(
                                       const std::vector< std::size_t > & SA );

[[nodiscard]] inline std::vector< std::size_t > lcpArray(
                   const Symbols & T , const std::vector< std::size_t > & SA );
[[nodiscard]] inline std::vector< std::size_t > lcpArray(
                  std::string_view T , const std::vector< std::size_t > & SA );

/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS SuffixArray ----------------------------*/
/*--------------------------------------------------------------------------*/

class SuffixArray {

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

 SuffixArray( void ) = default;

 explicit SuffixArray( std::string_view T );

 SuffixArray( Symbols T , std::size_t K );

 [[nodiscard]] std::pair< std::size_t , std::size_t > range(
                const Symbols & P , long * comparisons = nullptr ) const;
 [[nodiscard]] std::pair< std::size_t , std::size_t > range(
             std::string_view P , long * comparisons = nullptr ) const;

 [[nodiscard]] std::pair< std::size_t , std::size_t > rangeLcp(
                const Symbols & P , long * comparisons = nullptr ) const;
 [[nodiscard]] std::pair< std::size_t , std::size_t > rangeLcp(
             std::string_view P , long * comparisons = nullptr ) const;

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

 [[nodiscard]] std::vector< std::size_t > locate( std::string_view P ) const;
 [[nodiscard]] std::vector< std::size_t > locate( const Symbols & P ) const;

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

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

 [[nodiscard]] std::size_t operator[]( std::size_t r ) const;

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

 [[nodiscard]] const Symbols & text( void ) const { return( f_T ); }

 [[nodiscard]] const std::vector< std::size_t > & lcp( void ) const {
  return( f_lcp );
  }

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

 // a constant view of SA, random access

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

 [[nodiscard]] const_iterator begin( void ) const { return( f_SA.begin() ); }
 [[nodiscard]] const_iterator end( void ) const { return( f_SA.end() ); }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

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

 void index( void );

 std::size_t build( long L , long R );

 std::pair< std::size_t , bool > compare( const Symbols & P , std::size_t M ,
                                          std::size_t h , bool upper ,
                                          long * comparisons ) const;

 std::size_t bound( const Symbols & P , bool upper , long * c ) const;
 std::size_t boundLcp( const Symbols & P , bool upper , long * c ) const;

 Symbols f_T;
 std::vector< std::size_t > f_SA;
 std::vector< std::size_t > f_rank;
 std::vector< std::size_t > f_lcp;
 std::vector< std::size_t > f_Llcp;
 std::vector< std::size_t > f_Rlcp;
 RangeMinimum< std::size_t > f_rmq;

 };  // end( class SuffixArray )

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

}  // end( namespace ADS )

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

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

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

#endif  /* SuffixArray.h included */

/*--------------------------------------------------------------------------*/
/*------------------------- End File SuffixArray.h -------------------------*/
/*--------------------------------------------------------------------------*/