Edinburgh Speech Tools 2.4-release
 
Loading...
Searching...
No Matches
EST_StringTrie.cc
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
47static void (* trie_delete_function)(void *n) = 0;
48
49static inline int char2idx(unsigned char k)
50{
51// return k & 0x7f; // only seven significant bits;
52 return k;
53}
54
55EST_TrieNode::EST_TrieNode(const int width)
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
64EST_TrieNode::~EST_TrieNode()
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
75void *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
111void 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
126EST_StringTrie::EST_StringTrie()
127{
128 tree = new EST_TrieNode(TRIEWIDTH);
129}
130
131void EST_StringTrie::copy(const EST_StringTrie &trie)
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
139EST_StringTrie::~EST_StringTrie()
140{
141 delete tree;
142}
143
144void *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
150void 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
163void 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 add(const EST_String &key, void *item)
Add {\tt item} indexed by {\tt key}, overwriting previous contents.
void * lookup(const EST_String &key) const
Find contents index by {\tt key}, 0 if there is not contents.
void clear(void)
Delete the tree.
void copy_into(EST_StringTrie &trie, const EST_String &path) const
copy all entries in trie node into trie
void * lookup(const unsigned char *key) const
Find the contents for given string, 0 if no current contents.
void add(const unsigned char *key, void *item)
add {\tt item} for {\tt key} overwriting previous contents