Program Listing for File Trie.h

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

/*--------------------------------------------------------------------------*/
/*------------------------------ File Trie.h -------------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"

#include <cstddef>
#include <iterator>
#include <map>
#include <memory>
#include <optional>
#include <string>
#include <string_view>
#include <utility>
#include <vector>

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

namespace ADS {

namespace detail {

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS TrieIterator ----------------------------*/
/*--------------------------------------------------------------------------*/

template< class N , class V , bool Labeled >
class TrieIterator {
 public:
 using reference = std::pair< std::string , const V & >;
 using value_type = reference;
 using difference_type = std::ptrdiff_t;
 using iterator_concept = std::forward_iterator_tag;
 using iterator_category = std::input_iterator_tag;

 TrieIterator( void ) = default;

 explicit TrieIterator( const N * root ) {
  if( ! root ) return;
  f_S.push_back( Frame{ root , root->next.begin() , 0 } );
  if( ! root->value ) advance();
  }

 reference operator*( void ) const {
  return( reference( f_key , *f_S.back().node->value ) );
  }

 TrieIterator & operator++( void ) {
  advance();
  return( *this );
  }
 TrieIterator operator++( int ) { auto t = *this; ++*this; return( t ); }

 bool operator==( const TrieIterator & o ) const {
  return( f_S.empty() ? o.f_S.empty()
                      : ( ! o.f_S.empty() &&
                          ( f_S.back().node == o.f_S.back().node ) ) );
  }

 private:
 struct Frame {
  const N * node;
  typename decltype( N::next )::const_iterator child;
  std::size_t length;
  };

 void advance( void ) {
  while( ! f_S.empty() ) {
   Frame & f = f_S.back();
   if( f.child == f.node->next.end() ) {    // its subtree is done
    f_key.resize( f.length );
    f_S.pop_back();
    continue;
    }
   const std::size_t len = f_key.size();
   const auto & [ c , x ] = *f.child++;
   if constexpr( Labeled ) f_key += x->label; else f_key += c;
   f_S.push_back( Frame{ x.get() , x->next.begin() , len } );
   if( x->value ) return;
   }
  }

 std::vector< Frame > f_S;
 std::string f_key;

 };  // end( class TrieIterator )

}  // end( namespace detail )

/*--------------------------------------------------------------------------*/
/*------------------------------ CLASS Trie --------------------------------*/
/*--------------------------------------------------------------------------*/

template< class V >
class Trie {

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

 using Key = std::string;
 using Value = V;

 [[nodiscard]] std::optional< V > lookup( std::string_view k ) const;

 void insert( std::string_view k , const V & v );

 void remove( std::string_view k );

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

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

 [[nodiscard]] std::vector< std::string > keysWithPrefix(
                                                  std::string_view p ) const;

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

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

 struct Node {
  std::map< char , std::unique_ptr< Node > > next;
  std::optional< V > value;
  };

 public:

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

 // a constant view of the pairs ( key , value ) in lexicographic order,
 // forward; the key is rebuilt along the path

 using value_type = std::pair< std::string , const V & >;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = value_type;
 using const_reference = value_type;
 using const_iterator = detail::TrieIterator< Node , V , false >;
 using iterator = const_iterator;

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

 private:

 [[nodiscard]] const Node * find( std::string_view p ) const;

 bool remove( Node * x , std::string_view k , std::size_t d );

 static void collect( const Node * x , std::string & s ,
                      std::vector< std::string > & out );

 static std::size_t count( const Node * x );

 Node f_root;
 std::size_t f_size = 0;

 };  // end( class Trie )

/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS RadixTree -----------------------------*/
/*--------------------------------------------------------------------------*/

template< class V >
class RadixTree {

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

 using Key = std::string;
 using Value = V;

 [[nodiscard]] std::optional< V > lookup( std::string_view k ) const;

 void insert( std::string_view k , const V & v );

 void remove( std::string_view k );

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

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

 [[nodiscard]] std::vector< std::string > keysWithPrefix(
                                                  std::string_view p ) const;

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

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

 struct Node {
  std::string label;
  std::map< char , std::unique_ptr< Node > > next;
  std::optional< V > value;
  };

 public:

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

 // a constant view of the pairs ( key , value ) in lexicographic order,
 // forward; the key is rebuilt along the path

 using value_type = std::pair< std::string , const V & >;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = value_type;
 using const_reference = value_type;
 using const_iterator = detail::TrieIterator< Node , V , true >;
 using iterator = const_iterator;

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

 private:

 bool remove( Node * x , std::string_view k );

 static void compress( Node * x );

 static void collect( const Node * x , std::string & s ,
                      std::vector< std::string > & out );

 static std::size_t count( const Node * x );

 static bool compact( const Node * x , bool root );

 Node f_root;
 std::size_t f_size = 0;

 };  // end( class RadixTree )

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

}  // end( namespace ADS )

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

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

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

#endif  /* Trie.h included */

/*--------------------------------------------------------------------------*/
/*---------------------------- End File Trie.h -----------------------------*/
/*--------------------------------------------------------------------------*/