git.maemo.org Git - mverbiste/blob - verbiste/Trie.cpp

   1 /*  $Id: Trie.cpp,v 1.11 2011/01/08 19:07:36 sarrazip Exp $
   2     Trie.cpp - Tree structure for string storage
   3
   4     verbiste - French conjugation system
   5     Copyright (C) 2003-2005 Pierre Sarrazin <http://sarrazip.com/>
   6
   7     This program is free software; you can redistribute it and/or
   8     modify it under the terms of the GNU General Public License
   9     as published by the Free Software Foundation; either version 2
  10     of the License, or (at your option) any later version.
  11
  12     This program is distributed in the hope that it will be useful,
  13     but WITHOUT ANY WARRANTY; without even the implied warranty of
  14     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15     GNU General Public License for more details.
  16
  17     You should have received a copy of the GNU General Public License
  18     along with this program; if not, write to the Free Software
  19     Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  20     02111-1307, USA.
  21 */
  22
  23 #include "Trie.h"
  24
  25 #include <assert.h>
  26 #include <stdlib.h>
  27 #include <list>
  28 #include <iostream>
  29
  30
  31 namespace verbiste {
  32
  33
  34 template <class T>
  35 Trie<T>::Trie(bool _userDataFromNew)
  36   : lambda(),
  37     firstRow(new Row()),
  38     userDataFromNew(_userDataFromNew)
  39 {
  40 }
  41
  42
  43 template <class T>
  44 Trie<T>::~Trie()
  45 {
  46     firstRow->recursiveDelete(userDataFromNew);
  47     delete firstRow;
  48 }
  49
  50
  51 template <class T>
  52 Trie<T>::Descriptor::Descriptor(Row *inferior /*= NULL*/)
  53   : inferiorRow(inferior),
  54     userData(NULL)
  55 {
  56 }
  57
  58
  59 template <class T>
  60 Trie<T>::Descriptor::~Descriptor()
  61 {
  62 }
  63
  64
  65 template <class T>
  66 void
  67 Trie<T>::Descriptor::recursiveDelete(bool deleteUserData)
  68 {
  69     if (deleteUserData)
  70     {
  71         delete userData;
  72         userData = NULL;
  73     }
  74     if (inferiorRow != NULL)
  75     {
  76         inferiorRow->recursiveDelete(deleteUserData);
  77         delete inferiorRow;
  78         inferiorRow = NULL;
  79     }
  80 }
  81
  82
  83 template <class T>
  84 size_t
  85 Trie<T>::Descriptor::computeMemoryConsumption() const
  86 {
  87     return sizeof(*this) + (inferiorRow != NULL ? inferiorRow->computeMemoryConsumption() : 0);
  88 }
  89
  90
  91 template <class T>
  92 size_t
  93 Trie<T>::CharDesc::computeMemoryConsumption() const
  94 {
  95     return (sizeof(*this) - sizeof(desc)) + desc.computeMemoryConsumption();
  96 }
  97
  98
  99 template <class T>
 100 size_t
 101 Trie<T>::Row::computeMemoryConsumption() const
 102 {
 103     size_t sum = 0;
 104     for (typename std::vector<CharDesc>::const_iterator it = elements.begin(); it != elements.end(); ++it)
 105         sum += it->computeMemoryConsumption();
 106     return sizeof(*this) + sum;
 107 }
 108
 109
 110 template <class T>
 111 void
 112 Trie<T>::Row::recursiveDelete(bool deleteUserData)
 113 {
 114     for (typename std::vector<CharDesc>::iterator it = elements.begin();
 115                                         it != elements.end(); it++)
 116         it->desc.recursiveDelete(deleteUserData);
 117     elements.clear();
 118 }
 119
 120
 121 template <class T>
 122 typename Trie<T>::Descriptor *
 123 Trie<T>::Row::find(wchar_t unichar)
 124 {
 125     for (typename std::vector<CharDesc>::iterator it = elements.begin();
 126                                         it != elements.end(); it++)
 127         if (it->unichar == unichar)
 128             return &it->desc;
 129
 130     return NULL;
 131 }
 132
 133
 134 template <class T>
 135 typename Trie<T>::Descriptor &
 136 Trie<T>::Row::operator [] (wchar_t unichar)
 137 {
 138     Descriptor *pd = find(unichar);
 139     if (pd != NULL)
 140         return *pd;
 141
 142     elements.push_back(CharDesc(unichar));
 143     assert(elements.back().unichar == unichar);
 144     return elements.back().desc;
 145 }
 146
 147
 148 ///////////////////////////////////////////////////////////////////////////////
 149
 150
 151 template <class T>
 152 T *
 153 Trie<T>::add(const std::wstring &key, T *userData)
 154 {
 155     if (key.empty())
 156     {
 157         T *old = lambda;
 158         lambda = userData;
 159         return old;
 160     }
 161
 162     Descriptor *d = getDesc(firstRow, key, 0, true, false);
 163     assert(d != NULL);
 164     T *old = d->userData;
 165     d->userData = userData;
 166     return old;
 167 }
 168
 169
 170 template <class T>
 171 T *
 172 Trie<T>::get(const std::wstring &key) const
 173 {
 174     if (lambda != NULL)
 175         onFoundPrefixWithUserData(key, 0, lambda);
 176
 177     if (key.empty())
 178         return lambda;
 179
 180     Descriptor *d = const_cast<Trie<T> *>(this)->getDesc(firstRow, key, 0, false, true);
 181     return (d != NULL ? d->userData : NULL);
 182 }
 183
 184
 185 template <class T>
 186 T *
 187 Trie<T>::getWithDefault(const std::wstring &key, T *deFault)
 188 {
 189     if (key.empty())
 190     {
 191         if (lambda == NULL)
 192             lambda = deFault;
 193         return lambda;
 194     }
 195
 196     Descriptor *d = getDesc(firstRow, key, 0, true, false);
 197     assert(d != NULL);
 198     if (d->userData == NULL)
 199         d->userData = deFault;
 200     return d->userData;
 201 }
 202
 203
 204 template <class T>
 205 T **
 206 Trie<T>::getUserDataPointer(const std::wstring &key)
 207 {
 208     if (key.empty())
 209         return &lambda;
 210
 211     // Get descriptor associated with 'key' (and create a new entry
 212     // if the key is not known).
 213     //
 214     Descriptor *d = getDesc(firstRow, key, 0, true, false);
 215     assert(d != NULL);
 216     return &d->userData;
 217 }
 218
 219
 220 template <class T>
 221 typename Trie<T>::Descriptor *
 222 Trie<T>::getDesc(Row *row,
 223                 const std::wstring &key,
 224                 std::wstring::size_type index,
 225                 bool create,
 226                 bool callFoundPrefixCallback)
 227 {
 228     assert(row != NULL);
 229     assert(index < key.length());
 230
 231     wchar_t unichar = key[index];  // the "expected" character
 232     assert(unichar != '\0');
 233
 234     Descriptor *pd = row->find(unichar);
 235
 236     static bool trieTrace = getenv("TRACE") != NULL;
 237     if (trieTrace)
 238         std::wcout << "getDesc(row=" << row
 239                    << ", key='" << key << "' (len=" << key.length()
 240                    << "), index=" << index
 241                    << ", create=" << create
 242                    << ", call=" << callFoundPrefixCallback
 243                    << "): unichar=" << unichar << ", pd=" << pd << "\n";
 244
 245     if (pd == NULL)  // if expected character not found
 246     {
 247         if (!create)
 248             return NULL;
 249
 250         Descriptor &newDesc = (*row)[unichar];
 251         assert(row->find(unichar) != NULL);
 252         assert(row->find(unichar) == &newDesc);
 253
 254         if (index + 1 == key.length())  // if last char of string
 255             return &newDesc;
 256
 257         // Create new descriptor that points to a new inferior row:
 258         newDesc.inferiorRow = new Row();
 259         assert(row->find(unichar)->inferiorRow == newDesc.inferiorRow);
 260
 261         return getDesc(newDesc.inferiorRow,
 262                         key, index + 1, create, callFoundPrefixCallback);
 263     }
 264
 265     if (trieTrace)
 266         std::wcout << "getDesc: userData=" << pd->userData
 267                    << ", inferiorRow=" << pd->inferiorRow
 268                    << "\n";
 269
 270     if (callFoundPrefixCallback && pd->userData != NULL)
 271         onFoundPrefixWithUserData(key, index + 1, pd->userData);  // virtual call
 272
 273     if (index + 1 == key.length())  // if reached end of key
 274     {
 275         if (trieTrace)
 276             std::wcout << "getDesc: reached end of key\n";
 277         return pd;
 278     }
 279
 280     if (pd->inferiorRow == NULL)  // if pd is a leaf:
 281     {
 282         if (!create)
 283             return NULL;  // not found
 284
 285         pd->inferiorRow = new Row();
 286     }
 287
 288     return getDesc(pd->inferiorRow,
 289                         key, index + 1, create, callFoundPrefixCallback);
 290 }
 291
 292
 293 template <class T>
 294 size_t
 295 Trie<T>::computeMemoryConsumption() const
 296 {
 297     return sizeof(*this) + (firstRow != NULL ? firstRow->computeMemoryConsumption() : 0);
 298 }
 299
 300
 301 }  // namespace verbiste