From: chintan rao (chintanraoh_at_[hidden])
Date: 2008-03-21 13:08:24
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
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
trie::iterator trie::begin() //gives the beginning ie the
lexicographically least key :)
trie::iterator trie::end() //gives a iterator which is same as
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
trie<vector<int> > t;
x--; //or --x; x now points to "eat" since eat comes before "hello"
x++;//or ++x, x now points to "hello";
x=t.end(); // or x++ will point to t.end().
Please suggest changes to the interface and other things.
Chintan Rao H
On Fri, Mar 21, 2008 at 8:00 PM, Martin Wille <mw8329_at_[hidden]> 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
> Unsubscribe & other changes:
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk