KTextEditor

prefixstore.cpp
1 /* SPDX-License-Identifier: LGPL-2.0-or-later
2 
3  Copyright (C) 2009 by Michel Ludwig <[email protected]>
4 
5  This library is free software; you can redistribute it and/or
6  modify it under the terms of the GNU Library General Public
7  License as published by the Free Software Foundation; either
8  version 2 of the License, or (at your option) any later version.
9 
10  This library is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  Library General Public License for more details.
14 
15  You should have received a copy of the GNU Library General Public License
16  along with this library; see the file COPYING.LIB. If not, write to
17  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18  Boston, MA 02110-1301, USA.
19 */
20 
21 #include "prefixstore.h"
22 
23 #include "katepartdebug.h"
24 
25 #include "katetextline.h"
26 
27 KatePrefixStore::KatePrefixStore()
28 {
29 }
30 
31 KatePrefixStore::~KatePrefixStore()
32 {
33 }
34 
35 void KatePrefixStore::addPrefix(const QString &prefix)
36 {
37  if (prefix.isEmpty()) {
38  return;
39  }
40  if (m_prefixSet.contains(prefix)) {
41  return;
42  }
43  unsigned long long state = 0;
44  for (int i = 0; i < prefix.length(); ++i) {
45  QChar c = prefix.at(i);
46 
47  CharToOccurrenceStateHash &hash = m_transitionFunction[state];
48  CharToOccurrenceStateHash::iterator it = hash.find(c.unicode());
49  if (it == hash.end()) {
50  state = nextFreeState();
52  continue;
53  }
54 
55  ++(*it).first;
56  state = (*it).second;
57  }
58  // add the last state as accepting state
59  m_acceptingStates.insert(state);
60 
61  m_prefixSet.insert(prefix);
62 
63  if (prefix.length() > m_longestPrefixLength) {
64  m_longestPrefixLength = prefix.length();
65  }
66 }
67 
68 void KatePrefixStore::removePrefix(const QString &prefix)
69 {
70  if (prefix.isEmpty()) {
71  return;
72  }
73  if (!m_prefixSet.contains(prefix)) {
74  return;
75  }
76  m_prefixSet.remove(prefix);
77 
78  unsigned long long state = 0;
79  for (int i = 0; i < prefix.length(); ++i) {
80  QChar c = prefix.at(i);
81 
82  CharToOccurrenceStateHash &hash = m_transitionFunction[state];
83  CharToOccurrenceStateHash::iterator it = hash.find(c.unicode());
84  if (it == hash.end()) {
85  continue;
86  }
87 
88  state = (*it).second;
89  if (m_acceptingStates.contains(state) && i == prefix.length() - 1) {
90  m_acceptingStates.remove(state);
91  }
92 
93  if ((*it).first <= 1) {
94  hash.erase(it);
95  m_stateFreeList.push_back(state);
96  } else {
97  --(*it).first;
98  }
99  }
100 
101  if (prefix.length() == m_longestPrefixLength) {
102  m_longestPrefixLength = computeLongestPrefixLength();
103  }
104 }
105 
106 void KatePrefixStore::dump()
107 {
108  for (unsigned long long i = 0; i < m_lastAssignedState; ++i) {
109  CharToOccurrenceStateHash &hash = m_transitionFunction[i];
110  for (CharToOccurrenceStateHash::iterator it = hash.begin(); it != hash.end(); ++it) {
111  qCDebug(LOG_KTE) << i << "x" << QChar(it.key()) << "->" << it.value().first << "x" << it.value().second;
112  }
113  }
114  qCDebug(LOG_KTE) << "Accepting states" << m_acceptingStates;
115 }
116 
117 QString KatePrefixStore::findPrefix(const QString &s, int start) const
118 {
119  unsigned long long state = 0;
120  for (int i = start; i < s.length(); ++i) {
121  QChar c = s.at(i);
122  const CharToOccurrenceStateHash &hash = m_transitionFunction[state];
124  if (it == hash.end()) {
125  return QString();
126  }
127 
128  state = (*it).second;
129  if (m_acceptingStates.contains(state)) {
130  return s.mid(start, i + 1 - start);
131  }
132  }
133  return QString();
134 }
135 
137 {
138  unsigned long long state = 0;
139  for (int i = start; i < line->length(); ++i) {
140  QChar c = line->at(i);
141  const CharToOccurrenceStateHash &hash = m_transitionFunction[state];
143  if (it == hash.end()) {
144  return QString();
145  }
146 
147  state = (*it).second;
148  if (m_acceptingStates.contains(state)) {
149  return line->string(start, i + 1 - start);
150  }
151  }
152  return QString();
153 }
154 
155 int KatePrefixStore::longestPrefixLength() const
156 {
157  return m_longestPrefixLength;
158 }
159 
160 void KatePrefixStore::clear()
161 {
162  m_longestPrefixLength = 0;
163  m_prefixSet.clear();
164  m_transitionFunction.clear();
165  m_acceptingStates.clear();
166  m_stateFreeList.clear();
167  m_lastAssignedState = 0;
168 }
169 
170 int KatePrefixStore::computeLongestPrefixLength()
171 {
172  int toReturn = 0;
173  for (QSet<QString>::iterator i = m_prefixSet.begin(); i != m_prefixSet.end(); ++i) {
174  qCDebug(LOG_KTE) << "length" << (*i).length();
175  toReturn = qMax(toReturn, (*i).length());
176  }
177  return toReturn;
178 }
179 
180 unsigned long long KatePrefixStore::nextFreeState()
181 {
182  if (!m_stateFreeList.isEmpty()) {
183  return m_stateFreeList.takeFirst();
184  }
185  return ++m_lastAssignedState;
186 }
void clear()
void push_back(const T &value)
QSet::iterator insert(const T &value)
bool isEmpty() const const
bool isEmpty() const const
ushort unicode() const const
void clear()
QHash::iterator find(const Key &key)
QSet::iterator begin()
bool contains(const T &value) const const
QString mid(int position, int n) const const
bool remove(const T &value)
T takeFirst()
QSet::iterator end()
const QChar at(int position) const const
int length() const const
QHash::iterator end()
void clear()
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...
This file is part of the KDE documentation.
Documentation copyright © 1996-2020 The KDE developers.
Generated on Sun May 24 2020 23:10:51 by doxygen 1.8.11 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.