1/*
2 SPDX-FileCopyrightText: 2009 Michel Ludwig <michel.ludwig@kdemail.net>
3
4 SPDX-License-Identifier: LGPL-2.0-or-later
5*/
6
7#include "prefixstore.h"
8
9#include "katepartdebug.h"
10
11void KatePrefixStore::addPrefix(const QString &prefix)
12{
13 if (prefix.isEmpty()) {
14 return;
15 }
16 if (m_prefixSet.contains(value: prefix)) {
17 return;
18 }
19 unsigned long long state = 0;
20 for (int i = 0; i < prefix.length(); ++i) {
21 QChar c = prefix.at(i);
22
23 CharToOccurrenceStateHash &hash = m_transitionFunction[state];
24 CharToOccurrenceStateHash::iterator it = hash.find(key: c.unicode());
25 if (it == hash.end()) {
26 state = nextFreeState();
27 hash[c.unicode()] = QPair<unsigned int, unsigned long long>(1, state);
28 continue;
29 }
30
31 ++(*it).first;
32 state = (*it).second;
33 }
34 // add the last state as accepting state
35 m_acceptingStates.insert(value: state);
36
37 m_prefixSet.insert(value: prefix);
38
39 if (prefix.length() > m_longestPrefixLength) {
40 m_longestPrefixLength = prefix.length();
41 }
42}
43
44void KatePrefixStore::removePrefix(const QString &prefix)
45{
46 if (prefix.isEmpty()) {
47 return;
48 }
49 if (!m_prefixSet.contains(value: prefix)) {
50 return;
51 }
52 m_prefixSet.remove(value: prefix);
53
54 unsigned long long state = 0;
55 for (int i = 0; i < prefix.length(); ++i) {
56 QChar c = prefix.at(i);
57
58 CharToOccurrenceStateHash &hash = m_transitionFunction[state];
59 CharToOccurrenceStateHash::iterator it = hash.find(key: c.unicode());
60 if (it == hash.end()) {
61 continue;
62 }
63
64 state = (*it).second;
65 if (m_acceptingStates.contains(value: state) && i == prefix.length() - 1) {
66 m_acceptingStates.remove(value: state);
67 }
68
69 if ((*it).first <= 1) {
70 hash.erase(it);
71 m_stateFreeList.push_back(t: state);
72 } else {
73 --(*it).first;
74 }
75 }
76
77 if (prefix.length() == m_longestPrefixLength) {
78 m_longestPrefixLength = computeLongestPrefixLength();
79 }
80}
81
82void KatePrefixStore::dump()
83{
84 for (unsigned long long i = 0; i < m_lastAssignedState; ++i) {
85 CharToOccurrenceStateHash &hash = m_transitionFunction[i];
86 for (CharToOccurrenceStateHash::iterator it = hash.begin(); it != hash.end(); ++it) {
87 qCDebug(LOG_KTE) << i << "x" << QChar(it.key()) << "->" << it.value().first << "x" << it.value().second;
88 }
89 }
90 qCDebug(LOG_KTE) << "Accepting states" << m_acceptingStates;
91}
92
93QString KatePrefixStore::findPrefix(const QString &s, int start) const
94{
95 unsigned long long state = 0;
96 for (int i = start; i < s.length(); ++i) {
97 QChar c = s.at(i);
98 const CharToOccurrenceStateHash &hash = m_transitionFunction[state];
99 CharToOccurrenceStateHash::const_iterator it = hash.find(key: c.unicode());
100 if (it == hash.end()) {
101 return QString();
102 }
103
104 state = (*it).second;
105 if (m_acceptingStates.contains(value: state)) {
106 return s.mid(position: start, n: i + 1 - start);
107 }
108 }
109 return QString();
110}
111
112QString KatePrefixStore::findPrefix(const Kate::TextLine &line, int start) const
113{
114 unsigned long long state = 0;
115 for (int i = start; i < line.length(); ++i) {
116 QChar c = line.at(column: i);
117 const CharToOccurrenceStateHash &hash = m_transitionFunction[state];
118 CharToOccurrenceStateHash::const_iterator it = hash.find(key: c.unicode());
119 if (it == hash.end()) {
120 return QString();
121 }
122
123 state = (*it).second;
124 if (m_acceptingStates.contains(value: state)) {
125 return line.string(column: start, length: i + 1 - start);
126 }
127 }
128 return QString();
129}
130
131int KatePrefixStore::longestPrefixLength() const
132{
133 return m_longestPrefixLength;
134}
135
136void KatePrefixStore::clear()
137{
138 m_longestPrefixLength = 0;
139 m_prefixSet.clear();
140 m_transitionFunction.clear();
141 m_acceptingStates.clear();
142 m_stateFreeList.clear();
143 m_lastAssignedState = 0;
144}
145
146int KatePrefixStore::computeLongestPrefixLength()
147{
148 int toReturn = 0;
149 for (QSet<QString>::const_iterator i = m_prefixSet.cbegin(); i != m_prefixSet.cend(); ++i) {
150 qCDebug(LOG_KTE) << "length" << (*i).length();
151 toReturn = qMax(a: toReturn, b: (*i).length());
152 }
153 return toReturn;
154}
155
156unsigned long long KatePrefixStore::nextFreeState()
157{
158 if (!m_stateFreeList.isEmpty()) {
159 return m_stateFreeList.takeFirst();
160 }
161 return ++m_lastAssignedState;
162}
163

source code of ktexteditor/src/spellcheck/prefixstore.cpp