File indexing completed on 2024-04-28 15:30:45
0001 /* 0002 SPDX-FileCopyrightText: 2008-2009 Michel Ludwig <michel.ludwig@kdemail.net> 0003 0004 SPDX-License-Identifier: LGPL-2.0-or-later 0005 */ 0006 0007 #ifndef PREFIXSTORE_H 0008 #define PREFIXSTORE_H 0009 0010 #include <QHash> 0011 #include <QList> 0012 #include <QPair> 0013 #include <QSet> 0014 #include <QString> 0015 #include <QVector> 0016 0017 #include "katetextline.h" 0018 0019 /** 0020 * This class can be used to efficiently search for occurrences of strings in 0021 * a given string. Theoretically speaking, a finite deterministic automaton is 0022 * constructed which exactly accepts the strings that are to be recognized. In 0023 * order to check whether a given string contains one of the strings that are being 0024 * searched for the constructed automaton has to applied on each position in the 0025 * given string. 0026 **/ 0027 class KatePrefixStore 0028 { 0029 public: 0030 typedef QPair<bool, bool> BooleanPair; 0031 0032 virtual ~KatePrefixStore() = default; 0033 0034 void addPrefix(const QString &prefix); 0035 void removePrefix(const QString &prefix); 0036 0037 /** 0038 * Returns the shortest prefix of the given string that is contained in 0039 * this prefix store starting at position 'start'. 0040 **/ 0041 QString findPrefix(const QString &s, int start = 0) const; 0042 0043 /** 0044 * Returns the shortest prefix of the given string that is contained in 0045 * this prefix store starting at position 'start'. 0046 **/ 0047 QString findPrefix(const Kate::TextLine &line, int start = 0) const; 0048 0049 int longestPrefixLength() const; 0050 0051 void clear(); 0052 0053 void dump(); 0054 0055 protected: 0056 int m_longestPrefixLength = 0; 0057 QSet<QString> m_prefixSet; 0058 0059 // State x Char -> Nr. of char occurrences in prefixes x State 0060 typedef QHash<unsigned short, QPair<unsigned int, unsigned long long>> CharToOccurrenceStateHash; 0061 typedef QHash<unsigned long long, CharToOccurrenceStateHash> TransitionFunction; 0062 TransitionFunction m_transitionFunction; 0063 QSet<unsigned long long> m_acceptingStates; 0064 QList<unsigned long long> m_stateFreeList; 0065 unsigned long long m_lastAssignedState = 0; 0066 0067 int computeLongestPrefixLength(); 0068 unsigned long long nextFreeState(); 0069 // bool containsPrefixOfLengthEndingWith(int length, const QChar& c); 0070 }; 0071 0072 #endif