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