fdo#55315 Added simple Trie lookup tree for autocomplete words storage

Added simple Trie lookup tree which is more tailored to what is needed
in autocomplete implementation, but still has the speed of the
LatinLookupTree that has been used till now. As the implementation
is much simpler it should be more managable and easier fixable.

For now two actions: insert (word) and findSuggestions are supported.
Acttion findSuggestion returns all words in a list for a searched
sub-word, it also fixes fdo#62945.

Change-Id: I63b69c30d28b4e1c465c2122ebc537f7f75a033a

1 files changed, 59 insertions, 0 deletions

diff --git a/include/editeng/Trie.hxx b/include/editeng/Trie.hxx
new file mode 100644
index 000000000000..2ac76aee380c
--- /dev/null
+++ b/include/editeng/Trie.hxx
@@ -0,0 +1,59 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ */
+
+#ifndef TRIE_HXX
+#define TRIE_HXX
+
+#include <sal/types.h>
+#include <rtl/ustring.hxx>
+#include <vector>
+#include <editeng/editengdllapi.h>
+
+namespace editeng
+{
+
+struct TrieNode
+{
+    static const int LATIN_ARRAY_SIZE = 26;
+
+    sal_Unicode             mCharacter;
+    bool                    mMarker;
+    std::vector<TrieNode*>  mChildren;
+    TrieNode*               mLatinArray[LATIN_ARRAY_SIZE];
+
+
+    TrieNode(sal_Unicode aCharacter = '\0');
+    virtual ~TrieNode();
+
+    void      markWord();
+    TrieNode* findChild(sal_Unicode aCharacter);
+    TrieNode* traversePath(OUString sPath);
+    void      addNewChild(TrieNode* pChild);
+    void      collectSuggestions(OUString sPath, std::vector<OUString>& rSuggestionList);
+};
+
+class EDITENG_DLLPUBLIC Trie
+{
+private:
+    TrieNode* mRoot;
+
+public:
+    Trie();
+    virtual ~Trie();
+
+    void insert(OUString sInputString) const;
+    void findSuggestions(OUString sWordPart, std::vector<OUString>& rSuggesstionList) const;
+
+};
+
+}
+
+#endif // TRIE_HXX
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */