File indexing completed on 2024-04-28 15:30:45

 /*
     SPDX-FileCopyrightText: 2009 Michel Ludwig <michel.ludwig@kdemail.net>
 
     SPDX-License-Identifier: LGPL-2.0-or-later
 */
 
 #include "prefixstore.h"
 
 #include "katepartdebug.h"
 
 void KatePrefixStore::addPrefix(const QString &prefix)
 {
     if (prefix.isEmpty()) {
         return;
     }
     if (m_prefixSet.contains(prefix)) {
         return;
     }
     unsigned long long state = 0;
     for (int i = 0; i < prefix.length(); ++i) {
         QChar c = prefix.at(i);
 
         CharToOccurrenceStateHash &hash = m_transitionFunction[state];
         CharToOccurrenceStateHash::iterator it = hash.find(c.unicode());
         if (it == hash.end()) {
             state = nextFreeState();
             hash[c.unicode()] = QPair<unsigned int, unsigned long long>(1, state);
             continue;
         }
 
         ++(*it).first;
         state = (*it).second;
     }
     // add the last state as accepting state
     m_acceptingStates.insert(state);
 
     m_prefixSet.insert(prefix);
 
     if (prefix.length() > m_longestPrefixLength) {
         m_longestPrefixLength = prefix.length();
     }
 }
 
 void KatePrefixStore::removePrefix(const QString &prefix)
 {
     if (prefix.isEmpty()) {
         return;
     }
     if (!m_prefixSet.contains(prefix)) {
         return;
     }
     m_prefixSet.remove(prefix);
 
     unsigned long long state = 0;
     for (int i = 0; i < prefix.length(); ++i) {
         QChar c = prefix.at(i);
 
         CharToOccurrenceStateHash &hash = m_transitionFunction[state];
         CharToOccurrenceStateHash::iterator it = hash.find(c.unicode());
         if (it == hash.end()) {
             continue;
         }
 
         state = (*it).second;
         if (m_acceptingStates.contains(state) && i == prefix.length() - 1) {
             m_acceptingStates.remove(state);
         }
 
         if ((*it).first <= 1) {
             hash.erase(it);
             m_stateFreeList.push_back(state);
         } else {
             --(*it).first;
         }
     }
 
     if (prefix.length() == m_longestPrefixLength) {
         m_longestPrefixLength = computeLongestPrefixLength();
     }
 }
 
 void KatePrefixStore::dump()
 {
     for (unsigned long long i = 0; i < m_lastAssignedState; ++i) {
         CharToOccurrenceStateHash &hash = m_transitionFunction[i];
         for (CharToOccurrenceStateHash::iterator it = hash.begin(); it != hash.end(); ++it) {
             qCDebug(LOG_KTE) << i << "x" << QChar(it.key()) << "->" << it.value().first << "x" << it.value().second;
         }
     }
     qCDebug(LOG_KTE) << "Accepting states" << m_acceptingStates;
 }
 
 QString KatePrefixStore::findPrefix(const QString &s, int start) const
 {
     unsigned long long state = 0;
     for (int i = start; i < s.length(); ++i) {
         QChar c = s.at(i);
         const CharToOccurrenceStateHash &hash = m_transitionFunction[state];
         CharToOccurrenceStateHash::const_iterator it = hash.find(c.unicode());
         if (it == hash.end()) {
             return QString();
         }
 
         state = (*it).second;
         if (m_acceptingStates.contains(state)) {
             return s.mid(start, i + 1 - start);
         }
     }
     return QString();
 }
 
 QString KatePrefixStore::findPrefix(const Kate::TextLine &line, int start) const
 {
     unsigned long long state = 0;
     for (int i = start; i < line->length(); ++i) {
         QChar c = line->at(i);
         const CharToOccurrenceStateHash &hash = m_transitionFunction[state];
         CharToOccurrenceStateHash::const_iterator it = hash.find(c.unicode());
         if (it == hash.end()) {
             return QString();
         }
 
         state = (*it).second;
         if (m_acceptingStates.contains(state)) {
             return line->string(start, i + 1 - start);
         }
     }
     return QString();
 }
 
 int KatePrefixStore::longestPrefixLength() const
 {
     return m_longestPrefixLength;
 }
 
 void KatePrefixStore::clear()
 {
     m_longestPrefixLength = 0;
     m_prefixSet.clear();
     m_transitionFunction.clear();
     m_acceptingStates.clear();
     m_stateFreeList.clear();
     m_lastAssignedState = 0;
 }
 
 int KatePrefixStore::computeLongestPrefixLength()
 {
     int toReturn = 0;
     for (QSet<QString>::const_iterator i = m_prefixSet.cbegin(); i != m_prefixSet.cend(); ++i) {
         qCDebug(LOG_KTE) << "length" << (*i).length();
         toReturn = qMax(toReturn, (*i).length());
     }
     return toReturn;
 }
 
 unsigned long long KatePrefixStore::nextFreeState()
 {
     if (!m_stateFreeList.isEmpty()) {
         return m_stateFreeList.takeFirst();
     }
     return ++m_lastAssignedState;
 }