Re: [boost] [Boost][GSOC] proposal for Trie

On 2013/4/26 18:47, Antony Polukhin wrote:

2013/4/26 Hardy :

...

Firstly, the 'key' here represent a string. The first 'get-key' function is to get a key which corresponds to the iterator(node in Trie), because in order to save space(which is one of Trie's advantages), the whole key string should not store in a single iterator(node), so it is necessary to provide such an interface under my design.

This looks bad. Iterating through elements of 'string' may be a useful feature, but not the main. User will be putting in container 'string' and he will be expecting to retrieve 'string' when dereferencing iterator.

...

Since the relationship between key and string makes you confused, I am now trying to explain more about it. In my current design, a key is a 'string' itself. My idea is to take sequences of anytype as an abstract string in the bottom layer of the lib, in order to extend the capability of Trie. And after thinking on it several times, I now prefer to use 'key' as an element of a 'string', for it is more clear to users. Since it is a crucial and essential problem of the whole Trie project, I want some advices of you on it.

'key' is what we are going to store in container. User shall not care that we store key in parts, so it looks right to treat 'key' close to 'string'.

...

Ok, you mean that I should add this link of our discussion to the 'additional info' of my proposal in GSoC page?

Yes

-- Best regards, Antony Polukhin

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

I agree with you, that is why I design a layer of interfaces as TrieMap, and TrieSet, in my conceivation, it can be used as stl:map and stl:set, with the difference that they retrieve the keys using Trie data structure. So of course user can get 'key' when dereferencing iterator. Meanwhile, I still think that it is useful to provide some classes on lower layer to not store the keys in the iterators, so that users can have a more space-saving application. In conclusion, I adjust my design to the following form: bottom layer: class Trie; The key and value are not in the for as map(pair), so it is space-saving. second layer: typedef TrieMap Trie > The two layers can satisfy different needs of users.