Re: [boost] [ boost ] [ Trie ]

Subject: Re: [boost] [ boost ] [ Trie ]
From: Antony Polukhin (antoshkka_at_[hidden])
Date: 2015-05-02 10:34:42

2015-04-30 22:42 GMT+03:00 Cosmin Boaca <boost.cosmin.boaca_at_[hidden]>:

> Hello,
>
> I'm sorry for my high delayed answers but my coursework load it's keeping
> me busy all the time.
>

No need to worry. I'm also slow on answers :)

> > * move `key`, `children` and `parent` to to a separate base class. Define
> > `operator<` and `comparator` only for that base class
> > * make all the accesses to `parent` member through functions
> > (`set_parent()`, `get_parent()`). This will simplify future
> > node-minimization work
> >
>
> I have one question here. The intrusive set that keeps the children of the
> node will be of type intrusive_set<node_base> ?
> If so, I should cast the iterator return value to trie_node everywhere
> shouldn't I ?
>

I've missed that, so probably it's better to leave it as is right now.

There are big things to do:

* create a `leaf` node, that contains the remaining part of the value. For
example, if we have two values in trie "hello word" and "hell's bells",
then the trie would look like:
node['h']->node['e']->node['l']->node['l']->(leaf["o world"] | leaf['''s
bells']);

In worst case, when all the trie values have unique beginnings, this will
make the trie performace same as std::map performance.

* make sure that trie works with user specified comparators. For example,
make shure that it works right with std::greater<> and keys "abba" and
"anna" are sorted in reverse order ("anna", "abba")

-- 
Best regards,
Antony Polukhin