Program Listing for File SuffixTree.h

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

/*--------------------------------------------------------------------------*/
/*--------------------------- File SuffixTree.h ----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/search/RangeMinimum.h"
#include "ADS/string/SuffixArray.h"

#include <cstddef>
#include <limits>
#include <map>
#include <string_view>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS SuffixTree ----------------------------*/
/*--------------------------------------------------------------------------*/

class SuffixTree {

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

 static constexpr std::size_t npos = std::numeric_limits< std::size_t >::max();

 enum class Build { naive , mcCreight , suffixArray };

 struct Node {
  std::size_t pos = 0;
  std::size_t depth = 0;
  std::size_t parent = npos;
  std::size_t suffix = npos;
  std::size_t leaves = 0;
  std::map< std::size_t , std::size_t > child;
  };

 SuffixTree( void ) = default;

 explicit SuffixTree( std::string_view T , Build b = Build::mcCreight );

 SuffixTree( const Symbols & T , std::size_t K ,
             Build b = Build::mcCreight );

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

 [[nodiscard]] std::size_t root( void ) const { return( 0 ); }

 [[nodiscard]] const Node & node( std::size_t u ) const;

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

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

 [[nodiscard]] std::size_t locus( std::string_view P ) const;
 [[nodiscard]] std::size_t locus( const Symbols & P ) 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::size_t lca( std::size_t u , std::size_t v ) const;

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

 [[nodiscard]] std::pair< std::vector< std::size_t > ,
                          std::vector< std::size_t > > toSuffixArray( void )
                                                                       const;

 [[nodiscard]] std::vector< std::size_t > preorder( void ) const;

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

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

 // a constant view of the nodes, random access, the root first

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

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

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

 void construct( const Symbols & T , std::size_t K , Build b );
 void buildNaive( void );
 void buildMcCreight( void );
 void buildFromSuffixArray( const Symbols & T , std::size_t K );
 void finish( void );

 std::size_t newNode( std::size_t pos , std::size_t depth ,
                      std::size_t parent );

 std::size_t attachLeaf( std::size_t u , std::size_t i );

 std::size_t split( std::size_t u , std::size_t c , std::size_t d );

 [[nodiscard]] bool valid( void ) const;

 Symbols f_T;
 std::vector< Node > f_N;
 std::vector< std::size_t > f_leaf;
 std::vector< std::size_t > f_E;
 std::vector< std::size_t > f_first;
 PlusMinusOneRangeMinimum f_tour;

 };  // end( class SuffixTree )

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

}  // end( namespace ADS )

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

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

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

#endif  /* SuffixTree.h included */

/*--------------------------------------------------------------------------*/
/*------------------------- End File SuffixTree.h --------------------------*/
/*--------------------------------------------------------------------------*/