Aggiunte le Classi "Trie" e "TriePrefix" a gb.data con la rev. 6506

[vuott]

Vi segnalo questa comunicazione:


" n revision #6506, I added two classes to gb.data: Trie and TriePrefix.
Together they implement a Patricia Trie
http://en.wikipedia.org/wiki/Radix_tree
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. "

[vuott]

...continua...


" It's a shame that apparently "trie" is the usual name of that data
structure, because it's not a true name, and nobody knows how to
pronounce it (like "tree" or "try"?).

The common "Radix tree" is better imho.

But I'm far from being a tree specialist, so you will tell me.

The interface seems perfect. It's just the name "Trie" that I find ugly. :-)

Another point on the implementation: you should not use malloc(), free()
and realloc(), but the functions provided by the interpreter API, i.e.
GB.Alloc(), GB.Free() and GB.Realloc().

They are usually faster, especially if you allocate small chunks of data.

Moreover, they can detect memory leaks by checking that every allocation
has been freed at the end of the program.

If you can compare with malloc() easily, don't hesitate not to trust me and check. :-)

--
Benoît Minisini "


" I pronounce it like "try". RadixTree or PrefixTree would be options for the
container -- nothing against that -- but what about the other class?
RadixTreePrefix or even PrefixTreePrefix? :-) Naming it Patricia (from the
acronym) would be fun but even more confusing, right?

The trie.c and trie.h are from another library I wrote. (That's why I
double-tested the projects with valgrind.) It should not be a problem
to convert the uses of malloc()/free() now.

Regards,
Tobi "