EST_StringTrie.h

Go to the documentation of this file.

/*************************************************************************/
/*                                                                       */
/*                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;

/** \class EST_TrieNode
 *  @ingroup containerclasses
 *  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 `item` for `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;
};

/** \class EST_StringTrie
 *  @ingroup containerclasses
 *  \brief 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 `key`, 0 if there is not contents
    void *lookup(const EST_String &key) const;
    /// Add `item` indexed by `key`, overwriting previous contents
    void add(const EST_String &key,void *item);
    /// Delete the tree
    void clear(void);
    /// Delete the tree, apply `deletenote` function to each `contents`
    void clear(void (*deletenode)(void *n));

    ///
    EST_StringTrie & operator = (const EST_StringTrie &a) 
       { copy(a); return *this; }

};

#endif // __EST_STRINGTRIE_H__