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
trietest-0.0.1.tar.gz
Description: Binary data
-> 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
AutoComplete-0.0.1.tar.gz
Description: Binary data
------------------------------------------------------------------------------ Meet PCI DSS 3.0 Compliance Requirements with EventLog Analyzer Achieve PCI DSS 3.0 Compliant Status with Out-of-the-box PCI DSS Reports Are you Audit-Ready for PCI DSS 3.0 Compliance? Download White paper Comply to PCI DSS 3.0 Requirement 10 and 11.5 with EventLog Analyzer http://pubads.g.doubleclick.net/gampad/clk?id=154622311&iu=/4140/ostg.clktrk
_______________________________________________ Gambas-user mailing list Gambas-user@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/gambas-user
