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(OUString sPath);
35 : void addNewChild(TrieNode* pChild);
36 : void collectSuggestions(OUString sPath, std::vector<OUString>& rSuggestionList);
37 : void collectSuggestionsForCurrentNode(TrieNode* pCurrent, OUString sPath, vector<OUString>& rSuggestionList);
38 : };
39 :
40 16916 : TrieNode::TrieNode(sal_Unicode aCharacter) :
41 : mCharacter(aCharacter),
42 16916 : mMarker(false)
43 : {
44 456732 : for (int i=0; i<LATIN_ARRAY_SIZE; i++)
45 : {
46 439816 : mLatinArray[i] = NULL;
47 : }
48 16916 : }
49 :
50 50748 : TrieNode::~TrieNode()
51 : {
52 16916 : vector<TrieNode*>::iterator iNode;
53 32743 : for(iNode = mChildren.begin(); iNode != mChildren.end(); ++iNode)
54 : {
55 15827 : delete *iNode;
56 : }
57 :
58 456732 : for (int i=0; i<LATIN_ARRAY_SIZE; i++)
59 : {
60 439816 : delete mLatinArray[i];
61 : }
62 33832 : }
63 :
64 4478 : void TrieNode::markWord()
65 : {
66 4478 : mMarker = true;
67 4478 : }
68 :
69 16882 : void TrieNode::addNewChild(TrieNode* pChild)
70 : {
71 17938 : if (pChild->mCharacter >= sal_Unicode('a') &&
72 1056 : pChild->mCharacter <= sal_Unicode('z'))
73 : {
74 1055 : mLatinArray[pChild->mCharacter - sal_Unicode('a')] = pChild;
75 : }
76 : else
77 : {
78 15827 : mChildren.push_back(pChild);
79 : }
80 16882 : }
81 :
82 64176 : TrieNode* TrieNode::findChild(sal_Unicode aInputCharacter)
83 : {
84 64176 : if (aInputCharacter >= sal_Unicode('a') &&
85 : aInputCharacter <= sal_Unicode('z'))
86 : {
87 15759 : return mLatinArray[aInputCharacter - sal_Unicode('a')];
88 : }
89 :
90 48417 : vector<TrieNode*>::iterator iNode;
91 :
92 101618 : for(iNode = mChildren.begin(); iNode != mChildren.end(); ++iNode)
93 : {
94 85791 : TrieNode* pCurrent = *iNode;
95 85791 : if ( pCurrent->mCharacter == aInputCharacter )
96 32590 : return pCurrent;
97 : }
98 :
99 15827 : return NULL;
100 : }
101 :
102 151 : void TrieNode::collectSuggestions(OUString sPath, vector<OUString>& rSuggestionList)
103 : {
104 : // first traverse nodes for alphabet characters
105 4077 : for (int i=0; i<LATIN_ARRAY_SIZE; i++)
106 : {
107 3926 : TrieNode* pCurrent = mLatinArray[i];
108 3926 : if (pCurrent != NULL)
109 117 : collectSuggestionsForCurrentNode(pCurrent, sPath, rSuggestionList);
110 : }
111 :
112 : // traverse nodes for other characters
113 151 : vector<TrieNode*>::iterator iNode;
114 173 : for(iNode = mChildren.begin(); iNode != mChildren.end(); ++iNode)
115 : {
116 22 : TrieNode* pCurrent = *iNode;
117 22 : if (pCurrent != NULL)
118 22 : collectSuggestionsForCurrentNode(pCurrent, sPath, rSuggestionList);
119 : }
120 151 : }
121 :
122 139 : void TrieNode::collectSuggestionsForCurrentNode(TrieNode* pCurrent, OUString sPath, vector<OUString>& rSuggestionList)
123 : {
124 139 : OUString aStringPath = sPath + OUString(pCurrent->mCharacter);
125 139 : if(pCurrent->mMarker)
126 : {
127 21 : rSuggestionList.push_back(aStringPath);
128 : }
129 : // recursivly descend tree
130 139 : pCurrent->collectSuggestions(aStringPath, rSuggestionList);
131 139 : }
132 :
133 14 : TrieNode* TrieNode::traversePath(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 34 : Trie::Trie() :
151 34 : mRoot(new TrieNode())
152 34 : {}
153 :
154 34 : Trie::~Trie()
155 34 : {}
156 :
157 4479 : void Trie::insert(OUString sInputString) const
158 : {
159 : // adding an empty word is not allowed
160 4479 : if ( sInputString.isEmpty() )
161 : {
162 4480 : return;
163 : }
164 :
165 : // traverse the input string and modify the tree with new nodes / characters
166 :
167 4478 : TrieNode* pCurrent = mRoot.get();
168 : sal_Unicode aCurrentChar;
169 :
170 68637 : for ( sal_Int32 i = 0; i < sInputString.getLength(); i++ )
171 : {
172 64159 : aCurrentChar = sInputString[i];
173 64159 : TrieNode* pChild = pCurrent->findChild(aCurrentChar);
174 64159 : if ( pChild == NULL )
175 : {
176 16882 : TrieNode* pNewNode = new TrieNode(aCurrentChar);
177 16882 : pCurrent->addNewChild(pNewNode);
178 16882 : pCurrent = pNewNode;
179 : }
180 : else
181 : {
182 47277 : pCurrent = pChild;
183 : }
184 : }
185 :
186 4478 : pCurrent->markWord();
187 : }
188 :
189 14 : void Trie::findSuggestions(OUString sWordPart, vector<OUString>& rSuggesstionList) const
190 : {
191 14 : TrieNode* pNode = mRoot->traversePath(sWordPart);
192 :
193 14 : if (pNode != NULL)
194 : {
195 12 : pNode->collectSuggestions(sWordPart, rSuggesstionList);
196 : }
197 14 : }
198 :
199 : }
200 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
