cde/programs/nsgmls/TrieBuilder.C

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   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)
  10  * any later version.
  11  *
  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
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  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.
  26
  27 #ifdef __GNUG__
  28 #pragma implementation
  29 #endif
  30 #include "splib.h"
  31 #include "types.h"
  32 #include "macros.h"
  33 #include "StringOf.h"
  34 #include "Trie.h"
  35 #include "TrieBuilder.h"
  36 #include "Priority.h"
  37 #include <stdlib.h>
  38
  39 #ifdef SP_NAMESPACE
  40 namespace SP_NAMESPACE {
  41 #endif
  42
  43 Trie::~Trie()
  44 {
  45   if (next_)
  46     delete [] next_;
  47 }
  48
  49 Trie::Trie(const Trie &t)
  50 : nCodes_(t.nCodes_),
  51   token_(t.token_),
  52   tokenLength_(t.tokenLength_),
  53   priority_(t.priority_),
  54   blank_(t.blank_)
  55 {
  56   if (t.next_) {
  57     next_ = new Trie[nCodes_];
  58     for (int i = 0; i < nCodes_; i++)
  59       next_[i] = t.next_[i];
  60   }
  61   else
  62     next_ = 0;
  63 }
  64
  65 Trie &Trie::operator=(const Trie &t)
  66 {
  67   if (next_)
  68     delete [] next_;
  69   nCodes_ = t.nCodes_;
  70   token_ = t.token_;
  71   tokenLength_ = t.tokenLength_;
  72   priority_ = t.priority_;
  73   blank_ = t.blank_;
  74   if (t.next_) {
  75     next_ = new Trie[nCodes_];
  76     for (int i = 0; i < nCodes_; i++)
  77       next_[i] = t.next_[i];
  78   }
  79   else
  80     next_ = 0;
  81   return *this;
  82 }
  83
  84 TrieBuilder::TrieBuilder(int nCodes)
  85 : nCodes_(nCodes), root_(new Trie)
  86 {
  87   root_->token_ = 0;
  88   root_->tokenLength_ = 0;
  89   root_->priority_ = Priority::data;
  90   root_->nCodes_ = nCodes;
  91 }
  92
  93 void TrieBuilder::recognize(const String<EquivCode> &chars,
  94                             Token t,
  95                             Priority::Type priority,
  96                             TokenVector &ambiguities)
  97 {
  98   setToken(extendTrie(root_.pointer(), chars), chars.size(), t, priority,
  99            ambiguities);
 100 }
 101
 102 void TrieBuilder::recognize(const String<EquivCode> &chars,
 103                             const String<EquivCode> &set,
 104                             Token t,
 105                             Priority::Type priority,
 106                             TokenVector &ambiguities)
 107 {
 108   Trie *trie = extendTrie(root_.pointer(), chars);
 109
 110   for (size_t i = 0; i < set.size(); i++)
 111     setToken(forceNext(trie, set[i]), chars.size() + 1, t, priority,
 112              ambiguities);
 113 }
 114
 115 void TrieBuilder::recognizeB(const String<EquivCode> &chars,
 116                              int bSequenceLength,
 117                              size_t maxBlankSequence,
 118                              const String<EquivCode> &blankCodes,
 119                              const String<EquivCode> &chars2,
 120                              Token token,
 121                              TokenVector &ambiguities)
 122 {
 123   doB(extendTrie(root_.pointer(), chars),
 124       chars.size(),
 125       bSequenceLength,
 126       maxBlankSequence,
 127       blankCodes,
 128       chars2,
 129       token,
 130       Priority::blank(bSequenceLength),
 131       ambiguities);
 132 }
 133
 134 void TrieBuilder::recognizeEE(EquivCode code, Token t)
 135 {
 136   Trie *trie = forceNext(root_.pointer(), code);
 137   trie->tokenLength_ = 0;       // it has length 0 in the buffer
 138   trie->token_ = t;
 139   trie->priority_ = Priority::data;
 140 }
 141
 142 void TrieBuilder::doB(Trie *trie,
 143                       int tokenLength,
 144                       int minBLength,
 145                       size_t maxLength,
 146                       const String<EquivCode> &blankCodes,
 147                       const String<EquivCode> &chars2,
 148                       Token token,
 149                       Priority::Type pri,
 150                       TokenVector &ambiguities)
 151 {
 152   if (minBLength == 0 && trie->next_ == 0) {
 153     if (!trie->blank_) {
 154       BlankTrie *b = new BlankTrie;
 155       trie->blank_ = b;
 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;
 161       b->tokenLength_ = 0;
 162       b->token_ = 0;
 163       b->priority_ = Priority::data;
 164       b->nCodes_ = nCodes_;
 165     }
 166     else {
 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);
 172     }
 173     if (chars2.size() == 0)
 174       setToken(trie, tokenLength, token, pri, ambiguities);
 175     else
 176       setToken(extendTrie(trie->blank_.pointer(), chars2),
 177                chars2.size(),
 178                token,
 179                pri,
 180                ambiguities);
 181   }
 182   else {
 183     if (minBLength == 0)
 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]),
 188           tokenLength + 1,
 189           minBLength == 0 ? 0 : minBLength - 1,
 190           maxLength - 1,
 191           blankCodes,
 192           chars2,
 193           token,
 194           pri,
 195           ambiguities);
 196   }
 197 }
 198
 199 Trie *TrieBuilder::extendTrie(Trie *trie, const String<EquivCode> &s)
 200 {
 201   for (size_t i = 0; i < s.size(); i++)
 202     trie = forceNext(trie, s[i]);
 203   return trie;
 204 }
 205
 206 void TrieBuilder::setToken(Trie *trie,
 207                            int tokenLength,
 208                            Token token,
 209                            Priority::Type pri,
 210                            TokenVector &ambiguities)
 211 {
 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;
 218   }
 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);
 225   }
 226   if (trie->hasNext()) {
 227     for (int i = 0; i < nCodes_; i++)
 228       setToken(&trie->next_[i], tokenLength, token, pri, ambiguities);
 229   }
 230 }
 231
 232 void TrieBuilder::copyInto(Trie *into, const Trie *from, int additionalLength)
 233 {
 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);
 239   }
 240   if (from->hasNext())
 241     for (int i = 0; i < nCodes_; i++)
 242       copyInto(forceNext(into, i), &from->next_[i], additionalLength);
 243 }
 244
 245 Trie *TrieBuilder::forceNext(Trie *trie, EquivCode c)
 246 {
 247   if (!trie->hasNext()) {
 248     trie->next_ = new Trie[nCodes_];
 249     if (trie->blank_) {
 250       trie->blank_->additionalLength_ += 1;
 251       trie->blank_->maxBlanksToScan_ -= 1;
 252     }
 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_;
 265     }
 266     if (b)
 267       // -1 because 1 was added above
 268       copyInto(trie, b, b->additionalLength_ - 1);
 269   }
 270   return &trie->next_[c];
 271 }
 272
 273 #ifdef SP_NAMESPACE
 274 }
 275 #endif