editeng/source/lookuptree/Trie.cxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * This Source Code Form is subject to the terms of the Mozilla Public
   6  * License, v. 2.0. If a copy of the MPL was not distributed with this
   7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   8  */
   9
  10 #include <sal/config.h>
  11
  12 #include <string_view>
  13
  14 #include <editeng/Trie.hxx>
  15
  16 namespace editeng
  17 {
  18
  19 /* TrieNode */
  20
  21 struct TrieNode final
  22 {
  23     static const int LATIN_ARRAY_SIZE = 26;
  24
  25     sal_Unicode             mCharacter;
  26     bool                    mMarker;
  27     std::vector<std::unique_ptr<TrieNode>>  mChildren;
  28     std::unique_ptr<TrieNode> mLatinArray[LATIN_ARRAY_SIZE];
  29
  30     explicit TrieNode(sal_Unicode aCharacter = '\0');
  31
  32     void      markWord();
  33     TrieNode* findChild(sal_Unicode aCharacter);
  34     TrieNode* traversePath(std::u16string_view sPath);
  35     void      addNewChild(TrieNode* pChild);
  36     void      collectSuggestions(std::u16string_view sPath, std::vector<OUString>& rSuggestionList);
  37     static void  collectSuggestionsForCurrentNode(TrieNode* pCurrent, std::u16string_view sPath, std::vector<OUString>& rSuggestionList);
  38 };
  39
  40 TrieNode::TrieNode(sal_Unicode aCharacter) :
  41     mCharacter(aCharacter),
  42     mMarker(false)
  43 {
  44     for (auto & i : mLatinArray)
  45     {
  46         i = nullptr;
  47     }
  48 }
  49
  50 void TrieNode::markWord()
  51 {
  52     mMarker = true;
  53 }
  54
  55 void TrieNode::addNewChild(TrieNode* pChild)
  56 {
  57     if (pChild->mCharacter >= 'a' &&
  58         pChild->mCharacter <= 'z')
  59     {
  60         mLatinArray[pChild->mCharacter - u'a'].reset(pChild);
  61     }
  62     else
  63     {
  64         mChildren.push_back(std::unique_ptr<TrieNode>(pChild));
  65     }
  66 }
  67
  68 TrieNode* TrieNode::findChild(sal_Unicode aInputCharacter)
  69 {
  70     if (aInputCharacter >= 'a' &&
  71         aInputCharacter <= 'z')
  72     {
  73         return mLatinArray[aInputCharacter - u'a'].get();
  74     }
  75
  76     for(auto const & pCurrent : mChildren)
  77     {
  78         if ( pCurrent->mCharacter == aInputCharacter )
  79             return pCurrent.get();
  80     }
  81
  82     return nullptr;
  83 }
  84
  85 void TrieNode::collectSuggestions(std::u16string_view sPath, std::vector<OUString>& rSuggestionList)
  86 {
  87     // first traverse nodes for alphabet characters
  88     for (auto const & pCurrent : mLatinArray)
  89     {
  90         if (pCurrent != nullptr)
  91             collectSuggestionsForCurrentNode(pCurrent.get(), sPath, rSuggestionList);
  92     }
  93
  94     // traverse nodes for other characters
  95     for(auto const & pCurrent : mChildren)
  96     {
  97         if (pCurrent != nullptr)
  98             collectSuggestionsForCurrentNode(pCurrent.get(), sPath, rSuggestionList);
  99     }
 100 }
 101
 102 void TrieNode::collectSuggestionsForCurrentNode(TrieNode* pCurrent, std::u16string_view sPath, std::vector<OUString>& rSuggestionList)
 103 {
 104     OUString aStringPath = sPath + OUStringChar(pCurrent->mCharacter);
 105     if(pCurrent->mMarker)
 106     {
 107         rSuggestionList.push_back(aStringPath);
 108     }
 109     // recursively descend tree
 110     pCurrent->collectSuggestions(aStringPath, rSuggestionList);
 111 }
 112
 113 TrieNode* TrieNode::traversePath(std::u16string_view sPath)
 114 {
 115     TrieNode* pCurrent = this;
 116
 117     for ( const auto aCurrentChar : sPath )
 118     {
 119         pCurrent = pCurrent->findChild(aCurrentChar);
 120         if ( pCurrent == nullptr )
 121             return nullptr;
 122     }
 123
 124     return pCurrent;
 125 }
 126
 127 /* TRIE */
 128
 129 Trie::Trie() :
 130     mRoot(new TrieNode())
 131 {}
 132
 133 Trie::~Trie()
 134 {}
 135
 136 void Trie::insert(std::u16string_view sInputString) const
 137 {
 138     // adding an empty word is not allowed
 139     if ( sInputString.empty() )
 140     {
 141         return;
 142     }
 143
 144     // traverse the input string and modify the tree with new nodes / characters
 145
 146     TrieNode* pCurrent = mRoot.get();
 147
 148     for ( const auto aCurrentChar : sInputString )
 149     {
 150         TrieNode* pChild = pCurrent->findChild(aCurrentChar);
 151         if ( pChild == nullptr )
 152         {
 153             TrieNode* pNewNode = new TrieNode(aCurrentChar);
 154             pCurrent->addNewChild(pNewNode);
 155             pCurrent = pNewNode;
 156         }
 157         else
 158         {
 159             pCurrent = pChild;
 160         }
 161     }
 162
 163     pCurrent->markWord();
 164 }
 165
 166 void Trie::findSuggestions(std::u16string_view sWordPart, std::vector<OUString>& rSuggestionList) const
 167 {
 168     TrieNode* pNode = mRoot->traversePath(sWordPart);
 169
 170     if (pNode != nullptr)
 171     {
 172         pNode->collectSuggestions(sWordPart, rSuggestionList);
 173     }
 174 }
 175
 176 size_t Trie::size() const
 177 {
 178     if (!mRoot)
 179         return 0;
 180     std::vector<OUString> entries;
 181     mRoot->collectSuggestions(std::u16string_view(), entries);
 182     return entries.size();
 183 }
 184
 185 }
 186 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */