cde/programs/nsgmls/Trie.h

   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 libraries 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: Trie.h /main/1 1996/07/29 17:06:38 cde-hp $ */
  24 // Copyright (c) 1994 James Clark
  25 // See the file COPYING for copying permission.
  26
  27 #ifndef Trie_INCLUDED
  28 #define Trie_INCLUDED 1
  29
  30 #include <limits.h>
  31 #include "types.h"
  32 #include "Boolean.h"
  33 #include "Vector.h"
  34 #include "CopyOwner.h"
  35 #include "Priority.h"
  36
  37 #ifdef SP_NAMESPACE
  38 namespace SP_NAMESPACE {
  39 #endif
  40
  41 class BlankTrie;
  42
  43 class Trie {
  44 public:
  45   Trie() : next_(0), nCodes_(0), token_(0), tokenLength_(0), priority_(Priority::data) { }
  46   Trie(const Trie &);
  47   ~Trie();
  48   Trie &operator=(const Trie &);
  49   const Trie *next(int i) const { return &next_[i]; }
  50   Boolean hasNext() const { return next_ != 0; }
  51   Token token() const { return token_; }
  52   int tokenLength() const { return tokenLength_; }
  53   const BlankTrie *blank() const;
  54   Boolean includeBlanks() const {
  55     return Priority::isBlank(priority_);
  56   }
  57   friend class TrieBuilder;
  58 private:
  59   Trie *next_;
  60   int nCodes_;
  61   unsigned short token_;
  62   unsigned char tokenLength_;
  63   Priority::Type priority_;
  64   CopyOwner<BlankTrie> blank_;
  65 };
  66
  67 class BlankTrie : public Trie {
  68 public:
  69   BlankTrie() : additionalLength_(0), maxBlanksToScan_(0) { }
  70   Boolean codeIsBlank(EquivCode c) const { return codeIsBlank_[c]; }
  71   // maximum number of blanks to scan (minimum is 0)
  72   size_t maxBlanksToScan() const { return maxBlanksToScan_; }
  73   // length to add to tokenLengths in this trie (for those > 0).
  74   int additionalLength() const { return additionalLength_; }
  75   BlankTrie *copy() const { return new BlankTrie(*this); }
  76 private:
  77   unsigned char additionalLength_;
  78   size_t maxBlanksToScan_;
  79   Vector<PackedBoolean> codeIsBlank_;
  80   friend class TrieBuilder;
  81 };
  82
  83 inline
  84 const BlankTrie *Trie::blank() const
  85 {
  86   return blank_.pointer();
  87 }
  88
  89 #ifdef SP_NAMESPACE
  90 }
  91 #endif
  92
  93 #endif /* not Trie_INCLUDED */