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