datrie/darray.h

   1 /* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * libdatrie - Double-Array Trie Library
   4  * Copyright (C) 2006  Theppitak Karoonboonyanan <theppitak@gmail.com>
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19  */
  20
  21 /*
  22  * darray.h - Double-array trie structure
  23  * Created: 2006-08-11
  24  * Author:  Theppitak Karoonboonyanan <theppitak@gmail.com>
  25  */
  26
  27 #ifndef __DARRAY_H
  28 #define __DARRAY_H
  29
  30 #include "triedefs.h"
  31 #include "trie-string.h"
  32
  33 /**
  34  * @file darray.h
  35  * @brief Double-array trie structure
  36  */
  37
  38 /**
  39  * @brief Symbol set structure type
  40  */
  41 typedef struct _Symbols Symbols;
  42
  43 void         symbols_free (Symbols *syms);
  44 int          symbols_num (const Symbols *syms);
  45 TrieChar     symbols_get (const Symbols *syms, int index);
  46
  47 /**
  48  * @brief Double-array structure type
  49  */
  50 typedef struct _DArray  DArray;
  51
  52
  53 DArray * da_new ();
  54
  55 DArray * da_fread (FILE *file);
  56
  57 void     da_free (DArray *d);
  58
  59 int      da_fwrite (const DArray *d, FILE *file);
  60
  61
  62 TrieIndex  da_get_root (const DArray *d);
  63
  64
  65 TrieIndex  da_get_base (const DArray *d, TrieIndex s);
  66
  67 TrieIndex  da_get_check (const DArray *d, TrieIndex s);
  68
  69
  70 void       da_set_base (DArray *d, TrieIndex s, TrieIndex val);
  71
  72 void       da_set_check (DArray *d, TrieIndex s, TrieIndex val);
  73
  74 Bool       da_walk (const DArray *d, TrieIndex *s, TrieChar c);
  75
  76 Symbols *  da_output_symbols  (const DArray *d, TrieIndex s);
  77
  78 /**
  79  * @brief Test walkability in double-array structure
  80  *
  81  * @param d : the double-array structure
  82  * @param s : current state
  83  * @param c : the input character
  84  *
  85  * @return boolean indicating walkability
  86  *
  87  * Test if there is a transition from state @a s with input character @a c.
  88  */
  89 /*
  90 Bool       da_is_walkable (DArray *d, TrieIndex s, TrieChar c);
  91 */
  92 #define    da_is_walkable(d,s,c) \
  93     (da_get_check ((d), da_get_base ((d), (s)) + (c)) == (s))
  94
  95 TrieIndex  da_insert_branch (DArray *d, TrieIndex s, TrieChar c);
  96
  97 void       da_prune (DArray *d, TrieIndex s);
  98
  99 void       da_prune_upto (DArray *d, TrieIndex p, TrieIndex s);
 100
 101 TrieIndex  da_first_separate (DArray *d, TrieIndex root, TrieString *keybuff);
 102
 103 TrieIndex  da_next_separate (DArray     *d,
 104                              TrieIndex   root,
 105                              TrieIndex   sep,
 106                              TrieString *keybuff);
 107
 108 #endif  /* __DARRAY_H */
 109
 110 /*
 111 vi:ts=4:ai:expandtab
 112 */