Edinburgh Speech Tools  2.1-release
EST_StringTrie.cc
Go to the documentation of this file.
1 /*************************************************************************/
2 /* */
3 /* Centre for Speech Technology Research */
4 /* University of Edinburgh, UK */
5 /* Copyright (c) 1996 */
6 /* All Rights Reserved. */
7 /* */
8 /* Permission is hereby granted, free of charge, to use and distribute */
9 /* this software and its documentation without restriction, including */
10 /* without limitation the rights to use, copy, modify, merge, publish, */
11 /* distribute, sublicense, and/or sell copies of this work, and to */
12 /* permit persons to whom this work is furnished to do so, subject to */
13 /* the following conditions: */
14 /* 1. The code must retain the above copyright notice, this list of */
15 /* conditions and the following disclaimer. */
16 /* 2. Any modifications must be clearly marked as such. */
17 /* 3. Original authors' names are not deleted. */
18 /* 4. The authors' names are not used to endorse or promote products */
19 /* derived from this software without specific prior written */
20 /* permission. */
21 /* */
22 /* THE UNIVERSITY OF EDINBURGH AND THE CONTRIBUTORS TO THIS WORK */
23 /* DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING */
24 /* ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT */
25 /* SHALL THE UNIVERSITY OF EDINBURGH NOR THE CONTRIBUTORS BE LIABLE */
26 /* FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES */
27 /* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN */
28 /* AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, */
29 /* ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF */
30 /* THIS SOFTWARE. */
31 /* */
32 /*************************************************************************/
33 /* Author : Alan W Black */
34 /* Date : June 1996 */
35 /*-----------------------------------------------------------------------*/
36 /* */
37 /* A class for building EST_String (char-based) tries for indexing */
38 /* arbitrary objects by Strings */
39 /* */
40 /*=======================================================================*/
41 #include "EST_String.h"
42 #include "EST_StringTrie.h"
43 #include <cstring>
44 
45 #define TRIEWIDTH 256
46 
47 static void (* trie_delete_function)(void *n) = 0;
48 
49 static inline int char2idx(unsigned char k)
50 {
51 // return k & 0x7f; // only seven significant bits;
52  return k;
53 }
54 
56 {
57  // Initialise a node of given width
58  w=width;
59  d= new EST_TrieNode *[w];
60  contents=0;
61  memset(d,0,w*sizeof(EST_TrieNode *));
62 }
63 
65 {
66  int i;
67 
68  if (trie_delete_function != 0) /* user supplied delete function */
69  trie_delete_function(contents);
70  for (i=0; i<w; i++)
71  delete d[i];
72  delete [] d;
73 }
74 
75 void *EST_TrieNode::lookup(const unsigned char *key) const
76 {
77  // find key in EST_TrieNode, 0 if not found
78 
79  if (*key == '\0')
80  return contents; // base case
81  else
82  {
83  int idx = char2idx(*key);
84  if (d[idx] == 0)
85  return 0; // not there
86  else
87  return d[idx]->lookup(key+1);
88  }
89 }
90 
92  const EST_String &path) const
93 {
94  // find all items and add them to trie
95 
96  if (contents != 0)
97  trie.add(path,contents);
98 
99  for (int i=0; i < w; i++)
100  {
101  if (d[i] != 0)
102  {
103  char tail[2];
104  tail[0] = (char)i;
105  tail[1] = '\0';
106  d[i]->copy_into(trie,path+tail);
107  }
108  }
109 }
110 
111 void EST_TrieNode::add(const unsigned char *key,void *value)
112 {
113  // add this value
114 
115  if (*key == '\0')
116  contents = value;
117  else
118  {
119  int idx = char2idx(*key);
120  if (d[idx] == 0) // need new subnode
121  d[idx] = new EST_TrieNode(w);
122  d[idx]->add(key+1,value);
123  }
124 }
125 
127 {
128  tree = new EST_TrieNode(TRIEWIDTH);
129 }
130 
132 {
133  // This can't work because of the void* pointers in contents
134  delete tree;
135  tree = new EST_TrieNode(TRIEWIDTH);
136  trie.tree->copy_into(*this,"");
137 }
138 
140 {
141  delete tree;
142 }
143 
144 void *EST_StringTrie::lookup(const EST_String &key) const
145 {
146  const unsigned char *ckey = (const unsigned char *)(void *)(const char *)key;
147  return tree->lookup(ckey);
148 }
149 
150 void EST_StringTrie::add(const EST_String &key,void *item)
151 {
152  const unsigned char *ckey = (const unsigned char *)(void *)(const char *)key;
153  tree->add(ckey,item);
154  return;
155 }
156 
158 {
159  delete tree;
160  tree = new EST_TrieNode(TRIEWIDTH);
161 }
162 
163 void EST_StringTrie::clear(void (*deletenode)(void *n))
164 {
165  // This wont work if we go multi-thread
166  trie_delete_function = deletenode;
167  delete tree;
168  trie_delete_function = 0;
169  tree = new EST_TrieNode(TRIEWIDTH);
170 }
171 
void * lookup(const unsigned char *key) const
Find the contents for given string, 0 if no current contents.
void add(const EST_String &key, void *item)
Add item indexed by key, overwriting previous contents.
void clear(void)
Delete the tree.
void add(const unsigned char *key, void *item)
add item for key overwriting previous contents
#define TRIEWIDTH
void copy(const EST_StringTrie &trie)
A string tree index class for indexing arbitrary objects by strings of characters.
void copy_into(EST_StringTrie &trie, const EST_String &path) const
copy all entries in trie node into trie
int tree
Definition: rxp.c:21
void * lookup(const EST_String &key) const
Find contents index by key, 0 if there is not contents.