KTextEditor

prefixstore.h
1/*
2 SPDX-FileCopyrightText: 2008-2009 Michel Ludwig <michel.ludwig@kdemail.net>
3
4 SPDX-License-Identifier: LGPL-2.0-or-later
5*/
6
7#ifndef PREFIXSTORE_H
8#define PREFIXSTORE_H
9
10#include <QHash>
11#include <QList>
12#include <QPair>
13#include <QSet>
14#include <QString>
15
16#include "katetextline.h"
17
18/**
19 * This class can be used to efficiently search for occurrences of strings in
20 * a given string. Theoretically speaking, a finite deterministic automaton is
21 * constructed which exactly accepts the strings that are to be recognized. In
22 * order to check whether a given string contains one of the strings that are being
23 * searched for the constructed automaton has to applied on each position in the
24 * given string.
25 **/
27{
28public:
30
31 virtual ~KatePrefixStore() = default;
32
33 void addPrefix(const QString &prefix);
34 void removePrefix(const QString &prefix);
35
36 /**
37 * Returns the shortest prefix of the given string that is contained in
38 * this prefix store starting at position 'start'.
39 **/
40 QString findPrefix(const QString &s, int start = 0) const;
41
42 /**
43 * Returns the shortest prefix of the given string that is contained in
44 * this prefix store starting at position 'start'.
45 **/
46 QString findPrefix(const Kate::TextLine &line, int start = 0) const;
47
48 int longestPrefixLength() const;
49
50 void clear();
51
52 void dump();
53
54protected:
55 int m_longestPrefixLength = 0;
56 QSet<QString> m_prefixSet;
57
58 // State x Char -> Nr. of char occurrences in prefixes x State
61 TransitionFunction m_transitionFunction;
62 QSet<unsigned long long> m_acceptingStates;
63 QList<unsigned long long> m_stateFreeList;
64 unsigned long long m_lastAssignedState = 0;
65
66 int computeLongestPrefixLength();
67 unsigned long long nextFreeState();
68 // bool containsPrefixOfLengthEndingWith(int length, const QChar& c);
69};
70
71#endif
This class can be used to efficiently search for occurrences of strings in a given string.
Definition prefixstore.h:27
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.
Q_SCRIPTABLE Q_NOREPLY void start()
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.