Logo Search packages:      
Sourcecode: verbiste version File versions

Trie.cpp

/*  $Id: Trie.cpp,v 1.6 2005/03/13 04:03:26 sarrazip Exp $
    Trie.cpp - Tree structure for string storage

    verbiste - French conjugation system
    Copyright (C) 2003-2005 Pierre Sarrazin <http://sarrazip.com/>

    This program is free software; you can redistribute it and/or
    modify it under the terms of the GNU General Public License
    as published by the Free Software Foundation; either version 2
    of the License, or (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
    02111-1307, USA.
*/

#include "Trie.h"

#include <assert.h>
#include <list>

using namespace std;


namespace verbiste {


template <class T>
00035 Trie<T>::Trie(bool _userDataFromNew)
  : lambda(),
    firstRow(new Row()),
    userDataFromNew(_userDataFromNew)
{
}


template <class T>
00044 Trie<T>::~Trie()
{
    firstRow->recursiveDelete(userDataFromNew);
    delete firstRow;
}


template <class T>
Trie<T>::Descriptor::Descriptor(Row *inferior /*= NULL*/)
  : inferiorRow(inferior),
    userData(NULL)
{
}


template <class T>
Trie<T>::Descriptor::~Descriptor()
{
}


template <class T>
void
Trie<T>::Descriptor::recursiveDelete(bool deleteUserData)
{
    if (deleteUserData)
    {
      delete userData;
      userData = NULL;
    }
    if (inferiorRow != NULL)
    {
      inferiorRow->recursiveDelete(deleteUserData);
      delete inferiorRow;
      inferiorRow = NULL;
    }
}


template <class T>
void
Trie<T>::Row::recursiveDelete(bool deleteUserData)
{
    for (typename vector<CharDesc>::iterator it = elements.begin();
                              it != elements.end(); it++)
      it->desc.recursiveDelete(deleteUserData);
    elements.clear();
}


template <class T>
typename Trie<T>::Descriptor *
Trie<T>::Row::find(unsigned char c)
{
    for (typename vector<CharDesc>::iterator it = elements.begin();
                              it != elements.end(); it++)
      if (it->c == c)
          return &it->desc;

    return NULL;
}


template <class T>
typename Trie<T>::Descriptor &
Trie<T>::Row::operator [] (unsigned char c)
{
    Descriptor *pd = find(c);
    if (pd != NULL)
      return *pd;

    elements.push_back(CharDesc(c));
    return elements.back().desc;
}


template <class T>
T *
Trie<T>::add(const string &key, T *userData)
{
    if (key.empty())
    {
      T *old = lambda;
      lambda = userData;
      return old;
    }

    Descriptor *d = getDesc(firstRow, key, 0, true, false);
    assert(d != NULL);
    T *old = d->userData;
    d->userData = userData;
    return old;
}


template <class T>
T *
Trie<T>::get(const string &key) const
{
    if (lambda != NULL)
      onFoundPrefixWithUserData(key, 0, lambda);

    if (key.empty())
      return lambda;

    Descriptor *d = ((Trie<T> *) this)->getDesc(firstRow, key, 0, false, true);
    return (d != NULL ? d->userData : NULL);
}


template <class T>
T *
Trie<T>::getWithDefault(const string &key, T *deFault)
{
    if (key.empty())
    {
      if (lambda == NULL)
          lambda = deFault;
      return lambda;
    }

    Descriptor *d = getDesc(firstRow, key, 0, true, false);
    assert(d != NULL);
    if (d->userData == NULL)
      d->userData = deFault;
    return d->userData;
}


template <class T>
T **
Trie<T>::getUserDataPointer(const string &key)
{
    if (key.empty())
      return &lambda;

    Descriptor *d = getDesc(firstRow, key, 0, true, false);
    assert(d != NULL);
    return &d->userData;
}


template <class T>
typename Trie<T>::Descriptor *
Trie<T>::getDesc(Row *row,
            const string &key,
            string::size_type index,
            bool create,
            bool callFoundPrefixCallback)
{
    assert(index < key.length());
    unsigned char c = (unsigned char) key[index];  // the "expected" character
    Descriptor *pd = row->find(c);

    if (pd == NULL)  // if expected character not found
    {
      if (!create)
          return NULL;

      Descriptor &newDesc = (*row)[c];

      if (index + 1 == key.length())  // if last char of string
          return &newDesc;

      // Create new descriptor that points to a new inferior row:
      newDesc.inferiorRow = new Row();
      return getDesc(newDesc.inferiorRow,
                  key, index + 1, create, callFoundPrefixCallback);
    }

    if (index + 1 == key.length())
    {
      if (callFoundPrefixCallback && pd->userData != NULL)
          onFoundPrefixWithUserData(key, index + 1, pd->userData);
      return pd;
    }

    if (callFoundPrefixCallback && pd->userData != NULL)
      onFoundPrefixWithUserData(key, index + 1, pd->userData);

    if (pd->inferiorRow == NULL)  // if d is a leaf:
    {
      if (!create)
          return NULL;  // not found

      pd->inferiorRow = new Row();
    }

    return getDesc(pd->inferiorRow,
                  key, index + 1, create, callFoundPrefixCallback);
}


}  // namespace verbiste

Generated by  Doxygen 1.6.0   Back to index