ALib C++ Library
Library Version: 2510 R0
Documentation generated by doxygen
Loading...
Searching...
No Matches
search.cpp
1// #################################################################################################
2// ALib C++ Library
3//
4// Copyright 2013-2025 A-Worx GmbH, Germany
5// Published under 'Boost Software License' (a free software license, see LICENSE.txt)
6// #################################################################################################
7#include "alib_precompile.hpp"
8#if !defined(ALIB_C20_MODULES) || ((ALIB_C20_MODULES != 0) && (ALIB_C20_MODULES != 1))
9# error "Symbol ALIB_C20_MODULES has to be given to the compiler as either 0 or 1"
10#endif
11#if ALIB_C20_MODULES
12 module;
13#endif
14// ====================================== Global Fragment ======================================
16// =========================================== Module ==========================================
17#if ALIB_C20_MODULES
20#else
22# include "ALib.Strings.Search.H"
23#endif
24// ====================================== Implementation =======================================
25namespace alib { namespace strings { namespace util {
26
27template<typename TChar, lang::Case TSensitivity>
29
30template<typename TChar, lang::Case TSensitivity>
32{
33 if (pNeedle.IsNull() )
34 {
35 needle.SetNull();
36 return;
37 }
38 needle.Reset( pNeedle );
39 if( needle.Length() == 0 )
40 return;
41
42 if( kmpTableLength < needle.Length() )
43 {
44 if( kmpTable )
45 delete[] kmpTable;
46
47 kmpTable= new integer[size_t( needle.Length() + 1 )];
48 kmpTableLength= needle.Length();
49 }
50 integer needleIdx= 0;
51 integer pfxLen= kmpTable[0]= -1;
52 for (;;)
53 {
54 while ((pfxLen != -1) && !characters::Equal<TChar,TSensitivity>(needle.Buffer()[needleIdx], needle.Buffer()[pfxLen]))
55 pfxLen= kmpTable[pfxLen];
56 ++needleIdx;
57 if (needleIdx == needle.Length())
58 break;
59
60 ++pfxLen;
61 kmpTable[needleIdx]= characters::Equal<TChar,TSensitivity>(needle.Buffer()[needleIdx], needle.Buffer()[pfxLen]) ? kmpTable[pfxLen] : pfxLen;
62 }
63 kmpTable[needleIdx]= pfxLen;
64}
65
66template<typename TChar, lang::Case TSensitivity>
68{
69 if ( needle.IsNull() )
70 return -1;
71 if ( haystackIdx < 0 ) haystackIdx= 0;
72 if ( haystackIdx + needle.Length() > haystack.Length() ) return -1;
73
74 if( needle.Length() == 0 )
75 return haystackIdx;
76
77 integer needleIdx = 0;
78 while (haystackIdx != haystack.Length())
79 {
80 while ((needleIdx != -1) && !characters::Equal<TChar,TSensitivity>( haystack.Buffer()[haystackIdx],
81 needle .Buffer()[needleIdx] ) )
82 needleIdx= kmpTable[needleIdx];
83 ++haystackIdx;
84 ++needleIdx;
85 if ( needleIdx >= needle.Length() )
86 return (haystackIdx - needleIdx);
87 }
88
89 return -1;
90}
91
92//! @cond NO_DOX
109//! @endcond
110
111
112}}} // namespace [alib::strings::util]
113
constexpr integer Length() const
Definition string.inl:318
constexpr const TChar * Buffer() const
Definition string.inl:313
constexpr bool IsNull() const
Definition string.inl:352
TStringSearch(const TString< TChar > &pNeedle=nullptr)
Definition search.inl:45
TAString< TChar, lang::HeapAllocator > needle
The needle set Knuth-Morris-Pratt prefix length table.
Definition search.inl:29
ALIB_DLL integer Search(const TString< TChar > &haystack, integer startIdx=0)
Definition search.cpp:67
integer kmpTableLength
Length of kmpTable.
Definition search.inl:35
ALIB_DLL ~TStringSearch()
Destructor.
Definition search.cpp:28
ALIB_DLL void Compile(const TString< TChar > &needle)
Definition search.cpp:31
integer * kmpTable
The Knuth-Morris-Pratt prefix length table.
Definition search.inl:32
bool Equal(TChar lhs, TRhs rhs)
Definition functions.inl:62
lang::integer integer
Type alias in namespace alib.
Definition integers.inl:149