Program Listing for File PatriciaTrie.h

↰ Return to documentation for file (ADS/dictionary/PatriciaTrie.h)

/*--------------------------------------------------------------------------*/
/*-------------------------- File PatriciaTrie.h ---------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

#include <algorithm>
#include <cstddef>
#include <functional>
#include <string>
#include <string_view>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS PatriciaTrie ---------------------------*/
/*--------------------------------------------------------------------------*/

class PatriciaTrie {

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

 explicit PatriciaTrie( std::vector< std::string > D );

 [[nodiscard]] std::size_t lexicographicPosition( std::string_view P ) 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 blindLeaf( std::string_view P ) const;

 [[nodiscard]] bool contains( std::string_view P ) const;

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

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

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

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

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

 // a constant view of the strings in their order, contiguous

 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 const_iterator = std::vector< std::string >::const_iterator;
 using iterator = const_iterator;

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

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

 struct Node {
  std::size_t depth;
  std::size_t lo , hi;
  bool leaf;
  std::vector< std::pair< int , std::size_t > > child;
  };

 [[nodiscard]] static int at( std::string_view s , std::size_t i );

 [[nodiscard]] std::size_t childOf( std::size_t x , int c ) const;

 void descend( std::string_view P , int term ,
               std::vector< std::size_t > & path ) const;

 [[nodiscard]] std::size_t blind( std::string_view P , int term ,
                                  std::vector< std::size_t > & path ) const;

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

 static constexpr std::size_t kNone = ~std::size_t( 0 );

 std::vector< std::string > f_D;
 std::vector< Node > f_N;

 };  // end( class PatriciaTrie )

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

}  // end( namespace ADS )

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

#include "ADS/dictionary/impl/PatriciaTrie.tpp"

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

#endif  /* PatriciaTrie.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File PatriciaTrie.h -------------------------*/
/*--------------------------------------------------------------------------*/