Re: [boost] [ boost ] [ Trie ]

Subject: Re: [boost] [ boost ] [ Trie ]
From: Cosmin Boaca (boost.cosmin.boaca_at_[hidden])
Date: 2015-03-07 12:10:05

> I have thought of this task too. I will share with you some ideas in order
> to get some feedback about them.
>
> 1. Value = void specialization for trie_node which would remove pointers
to
> value_list_head/tail, self_value_count.
>
>+1

I have done this task. Also I have done refactoring and cleanup on the
whole project. I have decided to change a couple of things:

1. I have removed all the methods from trie class that created / destroyed
nodes. I have replaced them with calls to new and delete.
2. I have removed the node_allocator / value_allocator from trie class. I
think something like a node factory that would handle only creation /
destruction of nodes is more appropriate if we plan to allow custom
allocators.
3. I have added some methods to the trie_node class in order to share a
common interface between template specializations. Now operations that
query the node internal state (adding / removing values / no_value()) is
now done using those methods.
4. Because the iterator needed to be specialized too in order to handle
trie_node specialization I have decided to delegate the erasure of the
iterator to the iterator itself. This was the only way that could handle
the strucutral difference in terms of members between the specializations.
5. The iterator class now has another template parameter called Enable. I
needed to specialize the iterator for both void / const void and i used
boost::enable_if in order to achieve this with less code. const void
specialization is needed too because of the erase methods from trie. In
trie class there are two erase methods, erase(iterator),
erase(const_iterator). The const iterator coresonding for iterator<Key,
void> is iterator<Key, const void>. If they were the same the erase method
from trie would have been redefined resulting in compile time errors.
6. I have added more tests for trie_set. Now all the features are tested,
find, remove, insert, count_prefix, copy, iterators.
7. A friend of mine has implemented a build system based on cmake.

I have described above all the changes that I needed to do in order to
implement the template specialization. Also, I think now the node and
iterator are abstracted better. Please give me some feedback about the
changes that I have made [0].

[0] https://github.com/cosminBoaca/boost.trie

Thank you,
Cosmin