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