On 2013/4/22 17:15, Antony Polukhin wrote:

2013/4/21 Hardy Huang :

...

Hi, this is my proposal for GSOC 2013, please read it and give me some useful information on it, thanks <...>

Thanks, proposal looks good and interesting and has all the chances to be chosen for GSOC.

A good addition to proposal will be some sketch of trie interface: methods and constructors that Trie class will contain.

-- Best regards, Antony Polukhin

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

Thanks for reviewing my proposal. I am very glad to see your positive reply. I have thought of what you say when writing my proposal. Since it will be a good addition, I will reorganize my initial conceivation about Trie and post it as soon as I could.

2013/4/22 Michael Marcin :

On 4/22/2013 7:36 AM, Hardy wrote:

...

Thanks for reviewing my proposal. I am very glad to see your positive reply. I have thought of what you say when writing my proposal. Since it will be a good addition, I will reorganize my initial conceivation about Trie and post it as soon as I could.

If possible implement it as a boost.intrusive container which generally allows things to be trivially adapted into non-intrusive containers.

It works both ways :) So do as *you* think would be better and more useful. (Nobody forbids you to implement it other way later and also propose to Boost) -- Best regards, Antony Polukhin

2013/4/22 Michael Marcin : <...>

You can take a non-intrusive container and make it intrusive?

Black magic?

And how are you going to make intrusive container manage memory and objects lifetime? -- Best regards, Antony Polukhin

2013/4/23 Michael Marcin :

On 4/22/13 11:08 AM, Antony Polukhin wrote:

...

2013/4/22 Michael Marcin : <...>

...

You can take a non-intrusive container and make it intrusive?

Black magic?

And how are you going to make intrusive container manage memory and objects lifetime?

Stefan Strasser said it well not long ago, I'll just quote him.

On 4/6/13 10:08 AM, Stefan Strasser wrote:

...

Zitat von Vadim Stadnik :

...

If Boost.Intrusive containers (and containers based on Boost.Intrusive containers) outperform all other containers, they are the best possible choice. They are winners by both of these important parameters. Otherwise their advantage is not so obvious.

a non-intrusive container that is implemented in terms of an intrusive container is as efficient as any other non-intrusive container. it is a little more work to implement, to provide the Intrusive public interface. However, you can not implement an Intrusive container in terms of a non-intrusive container but have to reimplement the entire data structure. That's why Boost.Intrusive is not based on namespace std containers but are a reimplementation of the algorithms.

The implementation of a non-intrusive container in terms of an intrusive one is as simple as:

struct value_holder : intrusive::hook{ T value; };

and forwarding all calls of the STL container interface.

May be I'm missing something, but Stefan Strasser was talking about STL and Boosts intrusive containers, and his words shall be interpreted in context that we have no access to internals of STL. But when we have access to internals it is a totally different situation: * If we develop a non-intrusive container, we are free to split its implementation to resource management and intrusive logic. * If we develop an intrusive container - we need to add resource management to make a non-intrusive container. In both situations we achieve same results - we have intrusive and non-intrusive containers. So it works both ways *when we have access to internals* . -- Best regards, Antony Polukhin

2013/4/23 Michael Marcin :

On 4/23/2013 1:37 AM, Antony Polukhin wrote:

...

May be I'm missing something

Unfortunately I feel the same.

...

But when we have access to internals it is a totally different situation: * If we develop a non-intrusive container, we are free to split its implementation to resource management and intrusive logic.

By doing this split aren't you making an intrusive container and then layering the resource management ontop of it exactly as I suggested?

...

* If we develop an intrusive container - we need to add resource management to make a non-intrusive container.

Isn't this the same thing?

...

In both situations we achieve same results - we have intrusive and non-intrusive containers.

So it works both ways *when we have access to internals* .

Right if you have a non-intrusive container and access to the source code you can, most likely, refactor it to be an intrusive container but I don't see how that is comparable to being able to layer an non-intrusive interface over top an intrusive container without changing the implementation.

To put it another way if there was only intrusive_trie in boost. And a boost user using boost burned to a cd (read-only) she should be able to make trie in user code by writing a simple non-intrusive adapter.

If there was only trie in boost in the same scenario she would not be able to make use of boost trie to implement intrusive_trie in user code short of copy-paste-modify.

Now I get it... I was talking about intrusive/non-intusive with full access to sources (in my head Boosters were doing one container from another), you were talking about user that has no access to internals of implementation.

From your point of view intrusive containers provide better code reuse, from my point of view Boosters/GSOC will do both implementations and there is no big difference from where to start.

Using your point of view: Code reuse is times better, but users (including me) are usually lazy and more of them will prefer to work with non-intrusive container, which makes intrusive less popular. -- Best regards, Antony Polukhin

On 2013/4/23 16:52, Antony Polukhin wrote:

2013/4/23 Michael Marcin :

...

On 4/23/2013 1:37 AM, Antony Polukhin wrote:

...

May be I'm missing something

Unfortunately I feel the same.

...

But when we have access to internals it is a totally different situation: * If we develop a non-intrusive container, we are free to split its implementation to resource management and intrusive logic.

By doing this split aren't you making an intrusive container and then layering the resource management ontop of it exactly as I suggested?

...

* If we develop an intrusive container - we need to add resource management to make a non-intrusive container.

Isn't this the same thing?

...

In both situations we achieve same results - we have intrusive and non-intrusive containers.

So it works both ways *when we have access to internals* .

Right if you have a non-intrusive container and access to the source code you can, most likely, refactor it to be an intrusive container but I don't see how that is comparable to being able to layer an non-intrusive interface over top an intrusive container without changing the implementation.

To put it another way if there was only intrusive_trie in boost. And a boost user using boost burned to a cd (read-only) she should be able to make trie in user code by writing a simple non-intrusive adapter.

If there was only trie in boost in the same scenario she would not be able to make use of boost trie to implement intrusive_trie in user code short of copy-paste-modify.

Now I get it...

I was talking about intrusive/non-intusive with full access to sources (in my head Boosters were doing one container from another), you were talking about user that has no access to internals of implementation.

From your point of view intrusive containers provide better code reuse, from my point of view Boosters/GSOC will do both implementations and there is no big difference from where to start.

Using your point of view: Code reuse is times better, but users (including me) are usually lazy and more of them will prefer to work with non-intrusive container, which makes intrusive less popular.

-- Best regards, Antony Polukhin

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

Your discussion above help me understand the design of libraries better, but meanwhile I am a little confused about how I can give a good addition to my proposal as your early advice - "A good addition to proposal will be some sketch of trie interface: methods and constructors that Trie class will contain." Could you give me some examples or more advices on that? What I think out now are something like STL set, map, and with some specific methods and variables of Trie.

On 2013/4/23 20:59, Antony Polukhin wrote:

2013/4/23 Hardy :

...

"A good addition to proposal will be some sketch of trie interface: methods and constructors that Trie class will contain." Could you give me some examples or more advices on that? What I think out now are something like STL set, map, and with some specific methods and variables of Trie.

You are right, it is better to be as close to STL interface as possible. You may also say something like:

" Trie interface will have all the typedefs and methods of std::set excluding: iterator insert (const_iterator position, const value_type& val); ... It will additionally have the following methods:

pair prefix_range (const value_type& prefix) const; - returns range of elements starting from `prefix`. ... " You may also add some notes that you think will be interesting or just affect design, like "trie implementation will be storing it's size as a separate field to allow getting size in constant time" or "won't be storing it's size leading to liner complexity of size() function"... Some more examples of containers features: http://www.boost.org/doc/libs/1_53_0/doc/html/container/other_features.html

-- Best regards, Antony Polukhin

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

That's very kind of you. I will try my best to refine my design as soon as possible.

On 2013/4/23 20:59, Antony Polukhin wrote:

2013/4/23 Hardy :

...

"A good addition to proposal will be some sketch of trie interface: methods and constructors that Trie class will contain." Could you give me some examples or more advices on that? What I think out now are something like STL set, map, and with some specific methods and variables of Trie.

You are right, it is better to be as close to STL interface as possible. You may also say something like:

" Trie interface will have all the typedefs and methods of std::set excluding: iterator insert (const_iterator position, const value_type& val); ... It will additionally have the following methods:

pair prefix_range (const value_type& prefix) const; - returns range of elements starting from `prefix`. ... " You may also add some notes that you think will be interesting or just affect design, like "trie implementation will be storing it's size as a separate field to allow getting size in constant time" or "won't be storing it's size leading to liner complexity of size() function"... Some more examples of containers features: http://www.boost.org/doc/libs/1_53_0/doc/html/container/other_features.html

-- Best regards, Antony Polukhin

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

Hi, the following is what I conceive of Trie, which I will put to the 'description of work' in my proposal, because of its unmaturity, I will be happy to discuss on it with you, please give me some advice on it so that I can finish it and submit my application on the GSOC site. Thank you very much. ==description== Trie(Radix Tree) is an efficient in memory data structure to deal with string storing and searching. It can be used in many applications, and in comparison to hashtables, it has better expandability and stability. It is a data structure of great importance and wide usage. C++ has already had powerful common key-value containers such as set and map(I will only use map to make the comparison later), but when the keys are strings, map will take O(logN * length(string)) to lookup a key which has a worse performance when handling long strings and large amount of data, and stores every key as a full string which also wastes space. Besides, it is hard to use map traverse some keys with common prefix. Trie is good at handling strings especially the above tasks, so it is needed to improve the performance of handling key-value storage with the type of key being string. The basic interface of Trie will have similar typedefs and methods to stl::map, with some differences: pair prefix_range (const key_type& prefix) const; - returns range of elements starting from ‘prefix’ void prefix_erase(const key_type& prefix) const; - erases elements with keys starting with ‘prefix’ void prefix_count(const key_type& prefix) const; - returns the number of elements with keys starting with ‘prefix’ key_type get_key(const_iterator position); - returns the key of the iterator on position, because I think it is a waste of space to store the complete key, so users cannot get the key directly by iterator. vector get_keys(const Trie &trie); - returns the keys of all elements in Trie vector get_keys(const key_type& prefix); - returns the keys of all elements in starting with ‘prefix’ vector get_keys(const_iterator left, const_iterator right); - returns the keys between iterator left and right. Besides, considering that traditional Trie has limited scale of using, I want to design my Trie in 3 layers: The bottom one can provide the user-definition key type, which uses like RawTrie, in which the key can be a sequence of some type(maybe an array of anything can be a key), and every node of Trie can be taken as a root of sub RawTrie, which gives convenience to add Trie into it and even swap a sub Trie. And the second layer will be a specific Trie with the key of chars(when handling lookup and insert, both string and char[] can be adapted to it). And the feature of sub Trie is provided. The class is like Trie. And the third layer will be a Trie without so much freedom of operating as the above two. I will just provide the basic interface as I list above. And the last two layers of Trie will have a version of compressed storage of strings. More specifically, the classes of last two layers can include TrieSet and TrieMap to give users more convenience. (The idea is inspired by the patl http://code.google.com/p/patl/)

On 2013/4/26 16:15, Antony Polukhin wrote:

2013/4/25 Hardy :

...

On 2013/4/23 20:59, Antony Polukhin wrote:

...

2013/4/23 Hardy :

...

"A good addition to proposal will be some sketch of trie interface: methods and constructors that Trie class will contain." Could you give me some examples or more advices on that? What I think out now are something like STL set, map, and with some specific methods and variables of Trie.

You are right, it is better to be as close to STL interface as possible. You may also say something like:

" Trie interface will have all the typedefs and methods of std::set excluding: iterator insert (const_iterator position, const value_type& val); ... It will additionally have the following methods:

pair prefix_range (const value_type& prefix) const; - returns range of elements starting from `prefix`. ... " You may also add some notes that you think will be interesting or just affect design, like "trie implementation will be storing it's size as a separate field to allow getting size in constant time" or "won't be storing it's size leading to liner complexity of size() function"... Some more examples of containers features:

http://www.boost.org/doc/libs/1_53_0/doc/html/container/other_features.html

-- Best regards, Antony Polukhin

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

Hi, the following is what I conceive of Trie, which I will put to the 'description of work' in my proposal, because of its unmaturity, I will be happy to discuss on it with you, please give me some advice on it so that I can finish it and submit my application on the GSOC site. Thank you very much.

==description== Trie(Radix Tree) is an efficient in memory data structure to deal with string storing and searching. It can be used in many applications, and in comparison to hashtables, it has better expandability and stability. It is a data structure of great importance and wide usage. C++ has already had powerful common key-value containers such as set and map(I will only use map to make the comparison later), but when the keys are strings, map will take O(logN * length(string)) to lookup a key which has a worse performance when handling long strings and large amount of data, and stores every key as a full string which also wastes space. Besides, it is hard to use map traverse some keys with common prefix. Trie is good at handling strings especially the above tasks, so it is needed to improve the performance of handling key-value storage with the type of key being string.

The basic interface of Trie will have similar typedefs and methods to stl::map, with some differences:

pair prefix_range (const key_type& prefix) const; - returns range of elements starting from ‘prefix’ void prefix_erase(const key_type& prefix) const; - erases elements with keys starting with ‘prefix’ void prefix_count(const key_type& prefix) const; - returns the number of elements with keys starting with ‘prefix’

Pretty good!

...

key_type get_key(const_iterator position); - returns the key of the iterator on position, because I think it is a waste of space to store the complete key, so users cannot get the key directly by iterator. vector get_keys(const Trie &trie); - returns the keys of all elements in Trie vector get_keys(const key_type& prefix); - returns the keys of all elements in starting with ‘prefix’ vector get_keys(const_iterator left, const_iterator right); - returns the keys between iterator left and right.

Did not get the idea. Dereferencing an iterator what shall return? Do you mean 'key' here as a character of substring or 'key' here is a string itself?

Sorry for not stating my design clearly. 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. So I think it is not difficult to understand the last three function prototypes here is to show all the keys in different ranges. 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.

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.

On 2013/4/27 1:20, Antony Polukhin wrote:

2013/4/26 Hardy :

...

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.

Duplicating data is bad. If we have an iterator pointing to leaf node we can restore the whole key, without storing it one more time (leaf node == final element of whole key).

In Trie a non-leaf node can be the ending of a string, so you thought here confused me. How will your design handle this situation? A pointer to a single leaf node from the non-leaf node to it?

In my head node looks like this:

template <class Element> struct node { node* next_on_same_level_; node* deeper_or_parent_; // points to parent if next_on_same_level_ is NULL

Element value_; };

If next_on_same_level_ is NULL - we are in leaf node. To retrieve key we need to move to root, gathering elements.

And it looks like it is possible to get rid of one of the pointers using http://en.wikipedia.org/wiki/XOR_linked_list technique.

That is an amzazing trick, it is good to see such a beautiful method implementing linked list.

On 2013/4/28 0:54, Antony Polukhin wrote:

2013/4/27 Hardy :

...

On 2013/4/27 1:20, Antony Polukhin wrote:

...

2013/4/26 Hardy :

...

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.

Duplicating data is bad. If we have an iterator pointing to leaf node we can restore the whole key, without storing it one more time (leaf node == final element of whole key).

In Trie a non-leaf node can be the ending of a string, so you thought here confused me. How will your design handle this situation? A pointer to a single leaf node from the non-leaf node to it?

How about a node, that has no value and only shows that this is the end of substring:

struct node_base { node* next_on_same_level_; node* deeper_or_parent_; // points to parent if next_on_same_level_ is NULL };

template <class Element> struct node_nonleaf: public node_base { Element value_; };

struct node_leaf: public node_base {}; // next_on_same_level_ is always NULL

So sting 'abc' in trie would look like node_nonleaf('a') -> node_nonleaf('b') -> node_nonleaf('c') -> node_leaf Now if we add string 'ab' our structure will look like node_nonleaf('a') -> node_nonleaf('b') -> [node_nonleaf('c'), node_leaf] -> node_leaf

...

...

In my head node looks like this:

template <class Element> struct node { node* next_on_same_level_; node* deeper_or_parent_; // points to parent if next_on_same_level_ is NULL

Element value_; };

...

If next_on_same_level_ is NULL - we are in leaf node. To retrieve key we need to move to root, gathering elements.

And it looks like it is possible to get rid of one of the pointers using http://en.wikipedia.org/wiki/XOR_linked_list technique.

That is an amzazing trick, it is good to see such a beautiful method implementing linked list.

There are some more tricks, that allow to hide a few bits of information in XORed value. But generic implementation first, optimizations later.

-- Best regards, Antony Polukhin

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

Ok, thanks, I will digest your idea, and continue optimizing my design. BTW, I've submitted a version of my proposal which shows the result of our discussions till now. And I will refine it carefully when we have further discussion.