2 * CDE - Common Desktop Environment
4 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
6 * These libraries and programs are free software; you can
7 * redistribute them and/or modify them under the terms of the GNU
8 * Lesser General Public License as published by the Free Software
9 * Foundation; either version 2 of the License, or (at your option)
12 * These libraries and programs are distributed in the hope that
13 * they will be useful, but WITHOUT ANY WARRANTY; without even the
14 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15 * PURPOSE. See the GNU Lesser General Public License for more
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with these libraries and programs; if not, write
20 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
21 * Floor, Boston, MA 02110-1301 USA
23 /* $XConsortium: TrieBuilder.C /main/1 1996/07/29 17:06:43 cde-hp $ */
24 // Copyright (c) 1994 James Clark
25 // See the file COPYING for copying permission.
28 #pragma implementation
35 #include "TrieBuilder.h"
40 namespace SP_NAMESPACE {
49 Trie::Trie(const Trie &t)
52 tokenLength_(t.tokenLength_),
53 priority_(t.priority_),
57 next_ = new Trie[nCodes_];
58 for (int i = 0; i < nCodes_; i++)
59 next_[i] = t.next_[i];
65 Trie &Trie::operator=(const Trie &t)
71 tokenLength_ = t.tokenLength_;
72 priority_ = t.priority_;
75 next_ = new Trie[nCodes_];
76 for (int i = 0; i < nCodes_; i++)
77 next_[i] = t.next_[i];
84 TrieBuilder::TrieBuilder(int nCodes)
85 : nCodes_(nCodes), root_(new Trie)
88 root_->tokenLength_ = 0;
89 root_->priority_ = Priority::data;
90 root_->nCodes_ = nCodes;
93 void TrieBuilder::recognize(const String<EquivCode> &chars,
95 Priority::Type priority,
96 TokenVector &ambiguities)
98 setToken(extendTrie(root_.pointer(), chars), chars.size(), t, priority,
102 void TrieBuilder::recognize(const String<EquivCode> &chars,
103 const String<EquivCode> &set,
105 Priority::Type priority,
106 TokenVector &ambiguities)
108 Trie *trie = extendTrie(root_.pointer(), chars);
110 for (size_t i = 0; i < set.size(); i++)
111 setToken(forceNext(trie, set[i]), chars.size() + 1, t, priority,
115 void TrieBuilder::recognizeB(const String<EquivCode> &chars,
117 size_t maxBlankSequence,
118 const String<EquivCode> &blankCodes,
119 const String<EquivCode> &chars2,
121 TokenVector &ambiguities)
123 doB(extendTrie(root_.pointer(), chars),
130 Priority::blank(bSequenceLength),
134 void TrieBuilder::recognizeEE(EquivCode code, Token t)
136 Trie *trie = forceNext(root_.pointer(), code);
137 trie->tokenLength_ = 0; // it has length 0 in the buffer
139 trie->priority_ = Priority::data;
142 void TrieBuilder::doB(Trie *trie,
146 const String<EquivCode> &blankCodes,
147 const String<EquivCode> &chars2,
150 TokenVector &ambiguities)
152 if (minBLength == 0 && trie->next_ == 0) {
154 BlankTrie *b = new BlankTrie;
156 b->maxBlanksToScan_ = maxLength;
157 b->additionalLength_ = tokenLength;
158 b->codeIsBlank_.assign(nCodes_, 0);
159 for (size_t i = 0; i < blankCodes.size(); i++)
160 b->codeIsBlank_[blankCodes[i]] = 1;
163 b->priority_ = Priority::data;
164 b->nCodes_ = nCodes_;
167 // A B sequence is not allowed to be adjacent to a character
168 // that can occur in a blank sequence, so maxLength will be
169 // the same at a node, no matter how we got there.
170 ASSERT(trie->blank_->maxBlanksToScan_ == maxLength);
171 ASSERT(trie->blank_->additionalLength_ == tokenLength);
173 if (chars2.size() == 0)
174 setToken(trie, tokenLength, token, pri, ambiguities);
176 setToken(extendTrie(trie->blank_.pointer(), chars2),
184 setToken(extendTrie(trie, chars2), tokenLength + chars2.size(),
185 token, pri, ambiguities);
186 for (size_t i = 0; i < blankCodes.size(); i++)
187 doB(forceNext(trie, blankCodes[i]),
189 minBLength == 0 ? 0 : minBLength - 1,
199 Trie *TrieBuilder::extendTrie(Trie *trie, const String<EquivCode> &s)
201 for (size_t i = 0; i < s.size(); i++)
202 trie = forceNext(trie, s[i]);
206 void TrieBuilder::setToken(Trie *trie,
210 TokenVector &ambiguities)
212 if (tokenLength > trie->tokenLength_
213 || (tokenLength == trie->tokenLength_
214 && pri > trie->priority_)) {
215 trie->tokenLength_ = tokenLength;
216 trie->token_ = token;
217 trie->priority_ = pri;
219 else if (trie->tokenLength_ == tokenLength
220 && trie->priority_ == pri
221 && trie->token_ != token
222 && trie->token_ != 0) {
223 ambiguities.push_back(Token(trie->token_));
224 ambiguities.push_back(token);
226 if (trie->hasNext()) {
227 for (int i = 0; i < nCodes_; i++)
228 setToken(&trie->next_[i], tokenLength, token, pri, ambiguities);
232 void TrieBuilder::copyInto(Trie *into, const Trie *from, int additionalLength)
234 if (from->token_ != 0) {
235 TokenVector ambiguities;
236 setToken(into, from->tokenLength_ + additionalLength, from->token_,
237 from->priority_, ambiguities);
238 ASSERT(ambiguities.size() == 0);
241 for (int i = 0; i < nCodes_; i++)
242 copyInto(forceNext(into, i), &from->next_[i], additionalLength);
245 Trie *TrieBuilder::forceNext(Trie *trie, EquivCode c)
247 if (!trie->hasNext()) {
248 trie->next_ = new Trie[nCodes_];
250 trie->blank_->additionalLength_ += 1;
251 trie->blank_->maxBlanksToScan_ -= 1;
253 Owner<BlankTrie> blankOwner(trie->blank_.extract());
254 const BlankTrie *b = blankOwner.pointer();
255 for (int i = 0; i < nCodes_; i++) {
256 Trie *p = &trie->next_[i];
257 if (b && b->codeIsBlank(i))
258 trie->next_[i].blank_ = (blankOwner
259 ? blankOwner.extract()
260 : new BlankTrie(*b));
261 p->token_ = trie->token_;
262 p->tokenLength_ = trie->tokenLength_;
263 p->priority_ = trie->priority_;
264 p->nCodes_ = nCodes_;
267 // -1 because 1 was added above
268 copyInto(trie, b, b->additionalLength_ - 1);
270 return &trie->next_[c];