diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 09:06:44 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 09:06:44 +0000 |
commit | ed5640d8b587fbcfed7dd7967f3de04b37a76f26 (patch) | |
tree | 7a5f7c6c9d02226d7471cb3cc8fbbf631b415303 /editeng/source/lookuptree/Trie.cxx | |
parent | Initial commit. (diff) | |
download | libreoffice-upstream.tar.xz libreoffice-upstream.zip |
Adding upstream version 4:7.4.7.upstream/4%7.4.7upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'editeng/source/lookuptree/Trie.cxx')
-rw-r--r-- | editeng/source/lookuptree/Trie.cxx | 189 |
1 files changed, 189 insertions, 0 deletions
diff --git a/editeng/source/lookuptree/Trie.cxx b/editeng/source/lookuptree/Trie.cxx new file mode 100644 index 000000000..c994fa7cf --- /dev/null +++ b/editeng/source/lookuptree/Trie.cxx @@ -0,0 +1,189 @@ +/* -*- 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/. + */ + +#include <sal/config.h> + +#include <string_view> + +#include <editeng/Trie.hxx> + +namespace editeng +{ + +/* TrieNode */ + +struct TrieNode final +{ + static const int LATIN_ARRAY_SIZE = 26; + + sal_Unicode mCharacter; + bool mMarker; + std::vector<std::unique_ptr<TrieNode>> mChildren; + std::unique_ptr<TrieNode> mLatinArray[LATIN_ARRAY_SIZE]; + + explicit TrieNode(sal_Unicode aCharacter = '\0'); + + void markWord(); + TrieNode* findChild(sal_Unicode aCharacter); + TrieNode* traversePath(const OUString& sPath); + void addNewChild(TrieNode* pChild); + void collectSuggestions(std::u16string_view sPath, std::vector<OUString>& rSuggestionList); + static void collectSuggestionsForCurrentNode(TrieNode* pCurrent, std::u16string_view sPath, std::vector<OUString>& rSuggestionList); +}; + +TrieNode::TrieNode(sal_Unicode aCharacter) : + mCharacter(aCharacter), + mMarker(false) +{ + for (auto & i : mLatinArray) + { + i = nullptr; + } +} + +void TrieNode::markWord() +{ + mMarker = true; +} + +void TrieNode::addNewChild(TrieNode* pChild) +{ + if (pChild->mCharacter >= 'a' && + pChild->mCharacter <= 'z') + { + mLatinArray[pChild->mCharacter - u'a'].reset(pChild); + } + else + { + mChildren.push_back(std::unique_ptr<TrieNode>(pChild)); + } +} + +TrieNode* TrieNode::findChild(sal_Unicode aInputCharacter) +{ + if (aInputCharacter >= 'a' && + aInputCharacter <= 'z') + { + return mLatinArray[aInputCharacter - u'a'].get(); + } + + for(auto const & pCurrent : mChildren) + { + if ( pCurrent->mCharacter == aInputCharacter ) + return pCurrent.get(); + } + + return nullptr; +} + +void TrieNode::collectSuggestions(std::u16string_view sPath, std::vector<OUString>& rSuggestionList) +{ + // first traverse nodes for alphabet characters + for (auto const & pCurrent : mLatinArray) + { + if (pCurrent != nullptr) + collectSuggestionsForCurrentNode(pCurrent.get(), sPath, rSuggestionList); + } + + // traverse nodes for other characters + for(auto const & pCurrent : mChildren) + { + if (pCurrent != nullptr) + collectSuggestionsForCurrentNode(pCurrent.get(), sPath, rSuggestionList); + } +} + +void TrieNode::collectSuggestionsForCurrentNode(TrieNode* pCurrent, std::u16string_view sPath, std::vector<OUString>& rSuggestionList) +{ + OUString aStringPath = sPath + OUStringChar(pCurrent->mCharacter); + if(pCurrent->mMarker) + { + rSuggestionList.push_back(aStringPath); + } + // recursively descend tree + pCurrent->collectSuggestions(aStringPath, rSuggestionList); +} + +TrieNode* TrieNode::traversePath(const OUString& sPath) +{ + TrieNode* pCurrent = this; + + for ( sal_Int32 i = 0; i < sPath.getLength(); i++ ) + { + sal_Unicode aCurrentChar = sPath[i]; + pCurrent = pCurrent->findChild(aCurrentChar); + if ( pCurrent == nullptr ) + return nullptr; + } + + return pCurrent; +} + +/* TRIE */ + +Trie::Trie() : + mRoot(new TrieNode()) +{} + +Trie::~Trie() +{} + +void Trie::insert(const OUString& sInputString) const +{ + // adding an empty word is not allowed + if ( sInputString.isEmpty() ) + { + return; + } + + // traverse the input string and modify the tree with new nodes / characters + + TrieNode* pCurrent = mRoot.get(); + sal_Unicode aCurrentChar; + + for ( sal_Int32 i = 0; i < sInputString.getLength(); i++ ) + { + aCurrentChar = sInputString[i]; + TrieNode* pChild = pCurrent->findChild(aCurrentChar); + if ( pChild == nullptr ) + { + TrieNode* pNewNode = new TrieNode(aCurrentChar); + pCurrent->addNewChild(pNewNode); + pCurrent = pNewNode; + } + else + { + pCurrent = pChild; + } + } + + pCurrent->markWord(); +} + +void Trie::findSuggestions(const OUString& sWordPart, std::vector<OUString>& rSuggestionList) const +{ + TrieNode* pNode = mRoot->traversePath(sWordPart); + + if (pNode != nullptr) + { + pNode->collectSuggestions(sWordPart, rSuggestionList); + } +} + +size_t Trie::size() const +{ + if (!mRoot) + return 0; + std::vector<OUString> entries; + mRoot->collectSuggestions(std::u16string_view(), entries); + return entries.size(); +} + +} +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ |