Set version to v1.1
[mverbiste] / verbiste / Trie.h
1 /*  $Id: Trie.h,v 1.15 2011/01/08 19:07:36 sarrazip Exp $
2     Trie.h - 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 #ifndef _H_Trie
24 #define _H_Trie
25
26 #include <string>
27 #include <vector>
28
29
30 namespace verbiste {
31
32
33 /** Tree structure for (wide character) string storage.
34     @param        T     type of the user data attached to the stored strings;
35                         pointers to objects of type T will be stored in the
36                         trie, but no T object will be created, copied,
37                         assigned or destroyed by the trie.
38 */
39 template <class T>
40 class Trie
41 {
42 public:
43
44     /** Constructs an empty trie.
45         @param        userDataFromNew   determines if the destructor
46                                         must assume that all "user data"
47                                         pointers come from new and must
48                                         thus be destroyed with delete
49     */
50     Trie(bool userDataFromNew);
51
52
53     /** Destroys the trie and its contents.
54     */
55     virtual ~Trie();
56
57
58     /** Adds the given (wide character) key and associates it with
59         the given user data pointer.
60         @returns        the user data previously associated with the key,
61                         or NULL is no user data was associated
62     */
63     T *add(const std::wstring &key, T *userData);
64
65
66     /** Searches the trie with the given (wide character) key.
67         Invokes the virtual function onFoundPrefixWithUserData()
68         for each find.
69         @param  key         wide character string to search for
70         @returns            a pointer to the user data pointer
71                             associated with 'key', or NULL if
72                             nothing was found
73     */
74     T *get(const std::wstring &key) const;
75
76
77     T *getWithDefault(const std::wstring &key, T *deFault = NULL);
78
79
80     /** Obtains the address of the user data associated with 'key'
81         and adds an entry if necessary.
82         @returns        a non-null pointer to the user data pointer
83                         associated with 'key';
84                         if a new entry was created, the T * is null.
85     */
86     T **getUserDataPointer(const std::wstring &key);
87
88
89     /** Callback invoked by the Trie<>::get() method.
90         This callback will be called for each prefix of the searched
91         string for which the trie has some user data.
92         This method does nothing if it is not overridden in a derived class.
93         @param  key         the searched string
94         @param  index       length of the prefix
95         @param  userData    user data that is associated with the prefix
96     */
97     virtual void onFoundPrefixWithUserData(const std::wstring &/*key*/,
98                                         std::wstring::size_type /*index*/,
99                                         const T * /*userData*/) const
100                                                         throw()
101     {
102     }
103
104     /** Computes and returns the number of memory bytes consumed by
105         this object, excluding the size of the user data instances.
106         @returns                        number of bytes
107     */
108     size_t computeMemoryConsumption() const;
109
110 private:
111
112     class Row;
113
114     class Descriptor
115     {
116     public:
117         /** Constructs a descriptor that can point to an inferior row.
118             @param        inferior        pointer to the inferior row
119                                             (may be NULL);
120                                         this pointer must have been obtained
121                                         through operator new
122         */
123         Descriptor(Row *inferior = NULL);
124
125         Descriptor(const Descriptor &d) : inferiorRow(d.inferiorRow), userData(d.userData) {}
126         Descriptor &operator = (const Descriptor &d)
127         {
128             if (&d != this) { inferiorRow = d.inferiorRow; userData = d.userData; }
129             return *this;
130         }
131
132         /** Destroys this object and calls operator delete on the inferior row.
133             Does not call operator delete on userData.
134         */
135         ~Descriptor();
136
137         /** Calls recursiveDelete() on *inferiorRow if inferiorRow is not NULL.
138             Then, calls operator delete that row and sets inferiorRow to NULL.
139             @param        deleteUserData        if true, operator delete is called
140                                             on userData (which may be NULL)
141         */
142         void recursiveDelete(bool deleteUserData);
143
144         /** Computes and returns the number of memory bytes consumed by
145             this object, excluding the size of the user data.
146             @returns                        number of bytes
147         */
148         size_t computeMemoryConsumption() const;
149
150         Row *inferiorRow;
151         T *userData;
152     };
153
154     struct CharDesc
155     {
156         wchar_t unichar;  // Unicode character code
157         Descriptor desc;
158
159         CharDesc(wchar_t u) : unichar(u), desc() {}
160
161         /** Computes and returns the number of memory bytes consumed by
162             this object, excluding the size of the Descriptor's user data.
163             @returns                        number of bytes
164         */
165         size_t computeMemoryConsumption() const;
166     };
167
168     class Row
169     {
170     public:
171         Row()
172           : elements()
173         {
174         }
175
176         /** Calls recursiveDelete() on each Descriptor in this row.
177             Then empties this row.
178             @param        deleteUserData        if true, operator delete is called
179                                             on the userData field of the
180                                         Descriptor objects
181         */
182         void recursiveDelete(bool deleteUserData);
183
184
185         /** Finds an element of this row whose (wide) character field is
186             equal to 'unichar'.
187             Returns NULL if no such element exists.
188         */
189         Descriptor *find(wchar_t unichar);
190
191         /** Finds or creates an element of this row whose char. field is 'unichar'.
192             If no such element exists, one is created using the
193             default constructor of the Descriptor class.
194         */
195         Descriptor &operator [] (wchar_t unichar);
196
197         /** Computes and returns the number of memory bytes consumed by
198             this object, excluding the size of the Descriptors' user data.
199             @returns                        number of bytes
200         */
201         size_t computeMemoryConsumption() const;
202
203     private:
204         std::vector<CharDesc> elements;  // average size should be about 1.4
205     };
206
207
208     Descriptor *getDesc(Row *row,
209                         const std::wstring &key,
210                         std::wstring::size_type index,
211                         bool create,
212                         bool callFoundPrefixCallback);
213
214
215     T *lambda;  // user data associated with the empty string key
216     Row *firstRow;  // must be created by operator new
217     bool userDataFromNew;
218
219
220     // Forbidden operations:
221     Trie(const Trie &);
222     Trie &operator = (const Trie &);
223
224 };
225
226
227 }  // namespace verbiste
228
229
230 #include "Trie.cpp"
231
232
233 #endif  /* _H_Trie */