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();
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()
ushort unicode() const const
void clear()
QHash::iterator end()
QHash::iterator find(const Key &key)
void clear()
bool isEmpty() const const
void push_back(const T &value)
T takeFirst()
QSet::const_iterator cbegin() const const
QSet::const_iterator cend() const const
void clear()
bool contains(const T &value) const const
QSet::iterator insert(const T &value)
bool remove(const T &value)
const QChar at(int position) const const
bool isEmpty() const const
int length() const const
QString mid(int position, int n) const const
This file is part of the KDE documentation.
Documentation copyright © 1996-2024 The KDE developers.
Generated on Sat Feb 24 2024 20:00:58 by doxygen 1.10.0 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.