[Gambas-user] gb.data: Trie class

[Tobias Boege]

Hi,

in revision #6506, I added two classes to gb.data: Trie and TriePrefix.
Together they implement a Patricia Trie[0] a.k.a. Radix tree a.k.a. Prefix
tree.

Trie is the data container. It works just like a Collection. TriePrefix can
be used to limit searches to a common prefix. This way you can start doing
things way into the Trie and have to deal with less nodes.

Since the commit adds lots of new code, I would like people to test it with
the attached project. I will also attach the expected output in a text file.
(JFTR: There are no memory errors/leaks with it on my system.)

Also, Benoit: tell me what you think about the interface. I documented
everything in the source code (c_trie.c).

For the adventurous, I attach a simplistic command line interpreter which
shows the major deal with tries: the ability to search through a set of
strings simultaneously and doing fast (!) auto-completion of input among a
number of strings. (NB: I haven't tested this project thoroughly.)

Regards,
Tobi

PS: Please take revision #6507 which already corrects a bug.

[0] http://en.wikipedia.org/wiki/Radix_tree

-- 
"There's an old saying: Don't change anything... ever!" -- Mr. Monk
-------------- next part --------------
A non-text attachment was scrubbed...
Name: trietest-0.0.1.tar.gz
Type: application/octet-stream
Size: 4071 bytes
Desc: not available
URL: <http://lists.gambas-basic.org/pipermail/user/attachments/20140923/3b4eb5e8/attachment.obj>
-------------- next part --------------
 -> root
q -> p
tall -> small
term -> 2+3
test -> tomorrow
text -> words
texte -> french

texte+ -> french

text+ -> words
text+e -> french

tex+t -> words
tex+te -> french

te+rm -> 2+3
te+st -> tomorrow
te+xt -> words
te+xte -> french

t+all -> small
t+erm -> 2+3
t+est -> tomorrow
t+ext -> words
t+exte -> french

+ -> root
+q -> p
+tall -> small
+term -> 2+3
+test -> tomorrow
+text -> words
+texte -> french

t
text
tall
-------------- next part --------------
A non-text attachment was scrubbed...
Name: AutoComplete-0.0.1.tar.gz
Type: application/octet-stream
Size: 5949 bytes
Desc: not available
URL: <http://lists.gambas-basic.org/pipermail/user/attachments/20140923/3b4eb5e8/attachment-0001.obj>