File indexing completed on 2024-04-21 05:44:41
0001 /* 0002 * SPDX-FileCopyrightText: 2020 Andreas Cord-Landwehr <cordlandwehr@kde.org> 0003 * 0004 * SPDX-License-Identifier: GPL-2.0-only OR GPL-3.0-only OR LicenseRef-KDE-Accepted-GPL 0005 */ 0006 0007 #ifndef SKIPPARSER_H 0008 #define SKIPPARSER_H 0009 0010 #include <QMap> 0011 #include <QObject> 0012 #include <QRegularExpression> 0013 #include <QVector> 0014 #include <optional> 0015 0016 class SkipParser 0017 { 0018 public: 0019 std::optional<std::pair<int, int>> findMatch(QString text, QString pattern) const; 0020 0021 /** 0022 * @brief obtiain first matching pattern position 0023 * @param text 0024 * @param pattern 0025 * @return position, if found 0026 */ 0027 std::optional<std::pair<int, int>> findMatch(QString text, QVector<QString> pattern) const; 0028 0029 private: 0030 /** 0031 * @brief computeKmpPrefix 0032 * @param prunedPattern pattern must not contain any skip character, no additional pruning here 0033 * @return 0034 */ 0035 std::vector<int> computeKmpPrefix(const QString &prunedPattern) const; 0036 0037 std::pair<std::vector<QChar>, std::vector<int>> computeTextSkipPrefix(const QString &text) const; 0038 0039 std::optional<std::pair<int, int>> findMatchKMP(std::vector<QChar> prunedText, std::vector<int> textSkipPrefix, QString pattern) const; 0040 std::optional<std::pair<int, int>> findMatchNaive(QString text, QString pattern) const; 0041 static const QRegularExpression sSkipCharDetection; 0042 mutable QHash<QString, std::vector<int>> mPrefixCache; 0043 }; 0044 0045 #endif