KTextEditor

prefixstore.cpp
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(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(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(state);
36
37 m_prefixSet.insert(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(prefix)) {
50 return;
51 }
52 m_prefixSet.remove(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(c.unicode());
60 if (it == hash.end()) {
61 continue;
62 }
63
64 state = (*it).second;
65 if (m_acceptingStates.contains(state) && i == prefix.length() - 1) {
66 m_acceptingStates.remove(state);
67 }
68
69 if ((*it).first <= 1) {
70 hash.erase(it);
71 m_stateFreeList.push_back(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
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];
100 if (it == hash.end()) {
101 return QString();
102 }
103
104 state = (*it).second;
105 if (m_acceptingStates.contains(state)) {
106 return s.mid(start, i + 1 - start);
107 }
108 }
109 return QString();
110}
111
113{
114 unsigned long long state = 0;
115 for (int i = start; i < line.length(); ++i) {
116 QChar c = line.at(i);
117 const CharToOccurrenceStateHash &hash = m_transitionFunction[state];
119 if (it == hash.end()) {
120 return QString();
121 }
122
123 state = (*it).second;
124 if (m_acceptingStates.contains(state)) {
125 return line.string(start, 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(toReturn, (*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}
QString findPrefix(const QString &s, int start=0) const
Returns the shortest prefix of the given string that is contained in this prefix store starting at po...
Class representing a single text line.
QString string(int column, int length) const
Returns the substring with length beginning at the given column.
int length() const
Returns the line's length.
QChar at(int column) const
Returns the character at the given column.
Q_SCRIPTABLE Q_NOREPLY void start()
char16_t & unicode()
void clear()
iterator end()
iterator find(const Key &key)
void clear()
bool isEmpty() const const
void push_back(parameter_type value)
value_type takeFirst()
const_iterator cbegin() const const
const_iterator cend() const const
void clear()
bool contains(const QSet< T > &other) const const
iterator insert(const T &value)
bool remove(const T &value)
const QChar at(qsizetype position) const const
bool isEmpty() const const
qsizetype length() const const
QString mid(qsizetype position, qsizetype n) const const
This file is part of the KDE documentation.
Documentation copyright © 1996-2024 The KDE developers.
Generated on Fri Jun 14 2024 11:57:26 by doxygen 1.10.0 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.