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: */
|
