home *** CD-ROM | disk | FTP | other *** search
/ Amiga ISO Collection / AmigaUtilCD2.iso / Programming / GCC / GERLIB_DEV08B.LHA / gerlib / libg++ / etc / trie-gen / trie.h < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-12  |  1.9 KB  |  50 lines
  1. /* This may look like C code, but it is really -*- C++ -*- */
  2.  
  3. /* Data and member functions for generating a minimal-prefix trie.
  4.  
  5.    Copyright (C) 1989 Free Software Foundation, Inc.
  6.    written by Douglas C. Schmidt (schmidt@ics.uci.edu)
  7.    
  8.    This file is part of GNU TRIE-GEN.
  9.    
  10.    GNU TRIE-GEN is free software; you can redistribute it and/or modify
  11.    it under the terms of the GNU General Public License as published by
  12.    the Free Software Foundation; either version 1, or (at your option)
  13.    any later version.
  14.    
  15.    GNU TRIE-GEN is distributed in the hope that it will be useful,
  16.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  17.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18.    GNU General Public License for more details.
  19.    
  20.    You should have received a copy of the GNU General Public License
  21.    along with GNU trie-gen; see the file COPYING.  If not, write to
  22.    the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
  23.  
  24. #include "compact.h"
  25.  
  26. class Trie
  27. {
  28. public:
  29.   /* N is a guess on the total number of keys. */
  30.                  Trie (int n = 1000): matrix (n), total_size (n) {
  31.              keys = new char *[n]; current_size = 0;
  32.              max_key_len = 0; max_row = 1; }
  33.   void           insert (char *str, int len);
  34.   void           output (void);
  35.   void           sort (void);
  36.  
  37. private:
  38.   Compact_Matrix matrix;           /* Dynamic table encoding the trie DFA. */
  39.   char         **keys;             /* Dynamic resizable table to store input keys. */
  40.   int            total_size;       /* Total size of the keyword table. */
  41.   int            current_size;     /* Current size of the keyword table. */
  42.   int         max_row;       /* Largest row in the trie so far. */
  43.   int            max_key_len;       /* Length of the longest keyword. */
  44.  
  45.   void           resize (int new_size);
  46.   void           build (int hi, int lo = 0, int col = 0);
  47.   static int     cmp (char **s1, char **s2);
  48. };
  49.  
  50.