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