search.hpp

Go to the documentation of this file.

//==================================================================================================
/// \file
/// This header-file is part of module \alib_strings of the \aliblong.
///
/// Copyright 2013-2026 A-Worx GmbH, Germany.
/// Published under #"mainpage_license".
//==================================================================================================
ALIB_EXPORT namespace alib {  namespace strings { namespace util  {
 
//==================================================================================================
/// Implements "Knuth-Morris-Pratt" algorithm for searching a substring within a string.
///
/// While the well known "Boyer-Moore-Algorithm" is even faster in the average case, for
/// uni-code characters its implementation would be efficient only with very long haystack strings.
///
/// For convenience, the following alias type names are available:
/// - #"alib::StringSearch",
/// - #"alib::NStringSearch" and
/// - #"alib::WSubstringSearch".
///
/// @tparam TChar        The character type of the haystack and needle strings.
/// @tparam TSensitivity The letter case sensitivity of the search..
//==================================================================================================
template<typename TChar, lang::Case TSensitivity= lang::Case::Sensitive>
class TStringSearch {
  protected:
    /// The needle set Knuth-Morris-Pratt prefix length table.
    TAString<TChar, lang::HeapAllocator>  needle;
 
    /// The Knuth-Morris-Pratt prefix length table.
    integer*                    kmpTable                                                   =nullptr;
 
    /// Length of #"kmpTable".
    integer                     kmpTableLength                                                   =0;
 
  public:
    /// Constructor. Passes the optional parameters to method #".Compile".
    ///
    /// @param pNeedle The string to search.
    ///                Defaults to #"%NULL_STRING" to allow parameterless construction with later
    ///                invocation of #".Compile".
    TStringSearch( const TString<TChar>& pNeedle= nullptr )                  { Compile( pNeedle ); }
 
    /// Destructor.
    ALIB_DLL
    ~TStringSearch();
 
  public:
    /// Resets this object to use the given string as the needle to search.
    /// @param  needle   The needle to search.
    ALIB_DLL
    void Compile( const TString<TChar>& needle );
 
    /// Searches for the needle in \p{haystack} starting at \p{startIdx}.
    ///
    /// @param haystack  The string to search in.
    /// @param startIdx  The start of the search.
    ///                  Defaults to \c 0.
    /// @return The index of the next occurrence of the needle in given \p{haystack}.
    ///         \c -1 if not found.
    ALIB_DLL
    integer   Search( const TString<TChar>& haystack, integer startIdx= 0 );
 
}; // class TStringSearch
 
extern template ALIB_DLL         TStringSearch<nchar, lang::Case::Sensitive>::TStringSearch (const TString<nchar>&);
extern template ALIB_DLL         TStringSearch<nchar, lang::Case::Ignore   >::TStringSearch (const TString<nchar>&);
extern template ALIB_DLL         TStringSearch<wchar, lang::Case::Sensitive>::TStringSearch (const TString<wchar>&);
extern template ALIB_DLL         TStringSearch<wchar, lang::Case::Ignore   >::TStringSearch (const TString<wchar>&);
extern template ALIB_DLL         TStringSearch<nchar, lang::Case::Sensitive>::~TStringSearch();
extern template ALIB_DLL         TStringSearch<nchar, lang::Case::Ignore   >::~TStringSearch();
extern template ALIB_DLL         TStringSearch<wchar, lang::Case::Sensitive>::~TStringSearch();
extern template ALIB_DLL         TStringSearch<wchar, lang::Case::Ignore   >::~TStringSearch();
extern template ALIB_DLL void    TStringSearch<nchar, lang::Case::Sensitive>::Compile             (const TString<nchar>&);
extern template ALIB_DLL void    TStringSearch<nchar, lang::Case::Ignore   >::Compile             (const TString<nchar>&);
extern template ALIB_DLL void    TStringSearch<wchar, lang::Case::Sensitive>::Compile             (const TString<wchar>&);
extern template ALIB_DLL void    TStringSearch<wchar, lang::Case::Ignore   >::Compile             (const TString<wchar>&);
extern template ALIB_DLL integer TStringSearch<nchar, lang::Case::Sensitive>::Search              (const TString<nchar>&, integer);
extern template ALIB_DLL integer TStringSearch<nchar, lang::Case::Ignore   >::Search              (const TString<nchar>&, integer);
extern template ALIB_DLL integer TStringSearch<wchar, lang::Case::Sensitive>::Search              (const TString<wchar>&, integer);
extern template ALIB_DLL integer TStringSearch<wchar, lang::Case::Ignore   >::Search              (const TString<wchar>&, integer);
 
}} // namespace alib[::strings::util]
 
/// Type alias in namespace #"%alib".
template<lang::Case TSensitivity>
using   StringSearch =  strings::util::TStringSearch<character>;
 
 
/// Type alias in namespace #"%alib".
template<lang::Case TSensitivity>
using  NStringSearch =  strings::util::TStringSearch<nchar>;
 
/// Type alias in namespace #"%alib".
template<lang::Case TSensitivity>
using  WSubstringSearch =  strings::util::TStringSearch<wchar>;
 
 
} // namespace alib