Re: [boost] Boost Trie

From: chintan rao (chintanraoh_at_[hidden])
Date: 2008-03-21 13:08:24

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_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
>
>
>
> HTH,
> m
>
>
> 1)
>
> http://sourceforge.net/mailarchive/forum.php?thread_name=2084b47d05090905432484f5ca%40mail.gmail.com&forum_name=spirit-devel
>
> 2)
>
> http://sourceforge.net/mailarchive/message.php?msg_name=cs431t%24duo%241%40sea.gmane.org
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>