Hi, I was thinking of implementing trie and various variation of tries, namely Ternary trees, Suffix trees and DAWG(Directed Acyclic Word Graphs) , for Google Soc. I was thinking something like this This is the abstract of the interface for trie Interface: trie<type_2> something; trie[string key]=type2 value; // O(key.size()); value trie::delete(string key); // O(key.size()); trie::iterator trie::find(string key); // O(key.size())' int trie::size() // O(1) time. Gives the total no of elements in the trie trie::iterator trie::begin() //gives the beginning ie the lexicographically least key :) trie::iterator trie::end() //gives a iterator which is same as x=x+trie.size(); string trie::get_key(iterator x) gets the key pointed to by iterator x; trie::iterator x; //worst case O(height of tree) x++; // traverses the tree left to right and goes to the "next" node x--; // traverses the tree right to left and goes to "prev" node *x // referrences the value of the key x is pointing to. trie.delete(x) // deletes the key pointed to by x; trie.count_prefix(string key) // counts the no of keys with prefix key Examples: trie::interator x; trie<vector<int> > t; t["hello"].push_back(9); t["eat"].push_back(10); x=t.find("hello"); x--; //or --x; x now points to "eat" since eat comes before "hello" lexicographically; cout<<(*x)[0]<<endl; x++;//or ++x, x now points to "hello"; x=t.end(); // or x++ will point to t.end(). do { x--; int size=(*x).size(); cout<<t.get_key(x)<<endl; for(int j=0;j<size;j++) cout<<(*x)[j]<<" "; cout<<endl; } while(x!=t.begin()); Please suggest changes to the interface and other things. Regards, Chintan Rao H On Fri, Mar 21, 2008 at 8:00 PM, Martin Wille <mw8329@yahoo.com.au> wrote:
chintan rao wrote:
Hi, I would like to know if there is Trie implementation in Boost.
There's a TST implementation. TSTs are related to tries. However, the implementation is well hidden in Spirit (inside the symbol table implementation) and it only has a subset of the desirable interface.
Maybe, you're interested in that TST implementation.
If not is it going to implemented soon?
There has been an undertaking to separate the TST code from Spirit into a library of its own and to complete the interface. That effort apparently is stalled for quite some time now.
I don't know how much progress the effort made. I suspect it hit the magical 90%-done barrier.
Would it be a good idea to start TST all this from scratch and implement a general thing for Boost?
I suggest you search the Spirit developer mailing list for relevant messages if you're interested. Starting points could be 1. http://tinyurl.com/37gcgp or 2. http://tinyurl.com/2e3jzn
HTH, m
1)
2)
http://sourceforge.net/mailarchive/message.php?msg_name=cs431t%24duo%241%40s...
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost