111 lines
5.0 KiB
C++
111 lines
5.0 KiB
C++
/*************************************************************************/
|
|
/* */
|
|
/* Centre for Speech Technology Research */
|
|
/* University of Edinburgh, UK */
|
|
/* Copyright (c) 1996 */
|
|
/* All Rights Reserved. */
|
|
/* */
|
|
/* Permission is hereby granted, free of charge, to use and distribute */
|
|
/* this software and its documentation without restriction, including */
|
|
/* without limitation the rights to use, copy, modify, merge, publish, */
|
|
/* distribute, sublicense, and/or sell copies of this work, and to */
|
|
/* permit persons to whom this work is furnished to do so, subject to */
|
|
/* the following conditions: */
|
|
/* 1. The code must retain the above copyright notice, this list of */
|
|
/* conditions and the following disclaimer. */
|
|
/* 2. Any modifications must be clearly marked as such. */
|
|
/* 3. Original authors' names are not deleted. */
|
|
/* 4. The authors' names are not used to endorse or promote products */
|
|
/* derived from this software without specific prior written */
|
|
/* permission. */
|
|
/* */
|
|
/* THE UNIVERSITY OF EDINBURGH AND THE CONTRIBUTORS TO THIS WORK */
|
|
/* DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING */
|
|
/* ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT */
|
|
/* SHALL THE UNIVERSITY OF EDINBURGH NOR THE CONTRIBUTORS BE LIABLE */
|
|
/* FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES */
|
|
/* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN */
|
|
/* AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, */
|
|
/* ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF */
|
|
/* THIS SOFTWARE. */
|
|
/* */
|
|
/*************************************************************************/
|
|
/* Author : Alan W Black */
|
|
/* Date : June 1996 */
|
|
/*-----------------------------------------------------------------------*/
|
|
/* */
|
|
/* A class for building EST_String (char-based) tries for indexing */
|
|
/* arbitrary objects by Strings */
|
|
/* */
|
|
/*=======================================================================*/
|
|
#ifndef __EST_STRINGTRIE_H__
|
|
#define __EST_STRINGTRIE_H__
|
|
|
|
#include "EST_String.h"
|
|
|
|
class EST_StringTrie;
|
|
|
|
/** An internal class for \Ref{EST_StringTrie} used to hold represent the
|
|
node in an string index tree.
|
|
|
|
This basically represents a 128-branching node (on for each character)
|
|
plus a contents field for strings ending at this point.
|
|
|
|
@author Alan W Black (awb@cstr.ed.ac.uk): June 1996
|
|
*/
|
|
class EST_TrieNode {
|
|
private:
|
|
int w;
|
|
EST_TrieNode **d;
|
|
void *contents;
|
|
// will use EST_TrieContents when I have a list of contents
|
|
public:
|
|
///
|
|
EST_TrieNode() {w=0; d=0; contents=0;}
|
|
///
|
|
EST_TrieNode(const int width);
|
|
///
|
|
~EST_TrieNode();
|
|
/// Find the contents for given string, 0 if no current contents
|
|
void *lookup(const unsigned char *key) const;
|
|
/// add {\tt item} for {\tt key} overwriting previous contents
|
|
void add(const unsigned char *key,void *item);
|
|
/// copy all entries in trie node into trie
|
|
void copy_into(EST_StringTrie &trie, const EST_String &path) const;
|
|
};
|
|
|
|
/** A string tree index class for indexing arbitrary objects by
|
|
strings of characters.
|
|
|
|
Note this only deals with 7 but characters, and can only hold
|
|
one item per index key.
|
|
*/
|
|
class EST_StringTrie {
|
|
private:
|
|
EST_TrieNode *tree;
|
|
public:
|
|
///
|
|
EST_StringTrie();
|
|
///
|
|
EST_StringTrie(const EST_StringTrie &trie) { copy(trie); }
|
|
///
|
|
~EST_StringTrie();
|
|
///
|
|
void copy(const EST_StringTrie &trie);
|
|
/// Find contents index by {\tt key}, 0 if there is not contents
|
|
void *lookup(const EST_String &key) const;
|
|
/// Add {\tt item} indexed by {\tt key}, overwriting previous contents
|
|
void add(const EST_String &key,void *item);
|
|
/// Delete the tree
|
|
void clear(void);
|
|
/// Delete the tree, apply {\tt deletenote} function to each {\tt contents}
|
|
void clear(void (*deletenode)(void *n));
|
|
|
|
///
|
|
EST_StringTrie & operator = (const EST_StringTrie &a)
|
|
{ copy(a); return *this; }
|
|
|
|
};
|
|
|
|
#endif // __EST_STRINGTRIE_H__
|