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