Boost logo

Boost :

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<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
    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::interator x;
    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().

        int size=(*x).size();
        for(int j=0;j<size;j++)
            cout<<(*x)[j]<<" ";

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.
> or 2.
> HTH,
> m
> 1)
> 2)
> _______________________________________________
> Unsubscribe & other changes:

Boost list run by bdawes at, gregod at, cpdaniel at, john at