cde/programs/nsgmls/Trie.h

   1 /* $XConsortium: Trie.h /main/1 1996/07/29 17:06:38 cde-hp $ */
   2 // Copyright (c) 1994 James Clark
   3 // See the file COPYING for copying permission.
   4
   5 #ifndef Trie_INCLUDED
   6 #define Trie_INCLUDED 1
   7
   8 #include <limits.h>
   9 #include "types.h"
  10 #include "Boolean.h"
  11 #include "Vector.h"
  12 #include "CopyOwner.h"
  13 #include "Priority.h"
  14
  15 #ifdef SP_NAMESPACE
  16 namespace SP_NAMESPACE {
  17 #endif
  18
  19 class BlankTrie;
  20
  21 class Trie {
  22 public:
  23   Trie() : next_(0), nCodes_(0) { }
  24   Trie(const Trie &);
  25   ~Trie();
  26   Trie &operator=(const Trie &);
  27   const Trie *next(int i) const { return &next_[i]; }
  28   Boolean hasNext() const { return next_ != 0; }
  29   Token token() const { return token_; }
  30   int tokenLength() const { return tokenLength_; }
  31   const BlankTrie *blank() const;
  32   Boolean includeBlanks() const {
  33     return Priority::isBlank(priority_);
  34   }
  35   friend class TrieBuilder;
  36 private:
  37   Trie *next_;
  38   int nCodes_;
  39   unsigned short token_;
  40   unsigned char tokenLength_;
  41   Priority::Type priority_;
  42   CopyOwner<BlankTrie> blank_;
  43 };
  44
  45 class BlankTrie : public Trie {
  46 public:
  47   BlankTrie() { }
  48   Boolean codeIsBlank(EquivCode c) const { return codeIsBlank_[c]; }
  49   // maximum number of blanks to scan (minimum is 0)
  50   size_t maxBlanksToScan() const { return maxBlanksToScan_; }
  51   // length to add to tokenLengths in this trie (for those > 0).
  52   int additionalLength() const { return additionalLength_; }
  53   BlankTrie *copy() const { return new BlankTrie(*this); }
  54 private:
  55   unsigned char additionalLength_;
  56   size_t maxBlanksToScan_;
  57   Vector<PackedBoolean> codeIsBlank_;
  58   friend class TrieBuilder;
  59 };
  60
  61 inline
  62 const BlankTrie *Trie::blank() const
  63 {
  64   return blank_.pointer();
  65 }
  66
  67 #ifdef SP_NAMESPACE
  68 }
  69 #endif
  70
  71 #endif /* not Trie_INCLUDED */