Kyle Isom
389dcf9cc7
- Added benchmarking for GapBuffer and PieceTable (BufferBench, PerformanceSuite). - Implemented `OptimizedSearch` using Boyer-Moore (bad character heuristic). - Introduced `UndoNodePool` for efficient memory management. - Fixed horizontal scrolling and cursor placement in GUI: ensured cursor visibility and improved accuracy for rendered columns.
80 lines
2.0 KiB
C++
80 lines
2.0 KiB
C++
#include "OptimizedSearch.h"
|
|
|
|
#include <algorithm>
|
|
|
|
|
|
void
|
|
OptimizedSearch::build_bad_char(const std::string &pattern)
|
|
{
|
|
if (pattern == last_pat_)
|
|
return;
|
|
last_pat_ = pattern;
|
|
std::fill(bad_char_.begin(), bad_char_.end(), -1);
|
|
for (std::size_t i = 0; i < pattern.size(); ++i) {
|
|
bad_char_[static_cast<unsigned char>(pattern[i])] = static_cast<int>(i);
|
|
}
|
|
}
|
|
|
|
|
|
std::size_t
|
|
OptimizedSearch::find_first(const std::string &text, const std::string &pattern, std::size_t start)
|
|
{
|
|
const std::size_t n = text.size();
|
|
const std::size_t m = pattern.size();
|
|
if (m == 0)
|
|
return start <= n ? start : std::string::npos;
|
|
if (m > n || start >= n)
|
|
return std::string::npos;
|
|
build_bad_char(pattern);
|
|
std::size_t s = start;
|
|
while (s <= n - m) {
|
|
std::size_t j = m;
|
|
while (j > 0 && pattern[j - 1] == text[s + j - 1]) {
|
|
--j;
|
|
}
|
|
if (j == 0) {
|
|
return s; // match found
|
|
}
|
|
unsigned char badc = static_cast<unsigned char>(text[s + j - 1]);
|
|
int bcidx = bad_char_[badc];
|
|
std::size_t shift = (j - 1 > static_cast<std::size_t>(bcidx))
|
|
? (j - 1 - static_cast<std::size_t>(bcidx))
|
|
: 1;
|
|
s += shift;
|
|
}
|
|
return std::string::npos;
|
|
}
|
|
|
|
|
|
std::vector<std::size_t>
|
|
OptimizedSearch::find_all(const std::string &text, const std::string &pattern, std::size_t start)
|
|
{
|
|
std::vector<std::size_t> res;
|
|
const std::size_t n = text.size();
|
|
const std::size_t m = pattern.size();
|
|
if (m == 0)
|
|
return res;
|
|
if (m > n || start >= n)
|
|
return res;
|
|
build_bad_char(pattern);
|
|
std::size_t s = start;
|
|
while (s <= n - m) {
|
|
std::size_t j = m;
|
|
while (j > 0 && pattern[j - 1] == text[s + j - 1]) {
|
|
--j;
|
|
}
|
|
if (j == 0) {
|
|
res.push_back(s);
|
|
s += m; // non-overlapping
|
|
continue;
|
|
}
|
|
unsigned char badc = static_cast<unsigned char>(text[s + j - 1]);
|
|
int bcidx = bad_char_[badc];
|
|
std::size_t shift = (j - 1 > static_cast<std::size_t>(bcidx))
|
|
? (j - 1 - static_cast<std::size_t>(bcidx))
|
|
: 1;
|
|
s += shift;
|
|
}
|
|
return res;
|
|
}
|