LCOV - code coverage report
Current view: top level - editeng/source/lookuptree - Trie.cxx (source / functions) Hit Total Coverage
Test: commit 10e77ab3ff6f4314137acd6e2702a6e5c1ce1fae Lines: 82 82 100.0 %
Date: 2014-11-03 Functions: 14 15 93.3 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.10