subtree or view of tree

[Kyle Bolton]

I have an implementation where I have a container of words on whose sub-branches I recurse thus narrowing the possibilities for the next level of recursion. How difficult would it be to implement a method taking a prefix and returning a subtree from the ConcurrentRadixTree implementation?

[Niall Gallagher]

Hi Kyle,

Well it would be easy to implement a method which returns another instance of the RadixTree interface (say a RadixTreeView object), which is a view onto the main radix tree.

AFAICS there are two main ways to implement a RadixTreeView object:

(1) The RadixTreeView object has a constructor which takes the original radix tree, and a prefix as its arguments.

It implements the methods in the RadixTree interface so that they transparently just delegate to the original radix tree, but it prefixes the arguments with the prefix which was supplied to its constructor. So in this way, the view would represent a way to make additional queries on some branches of the original tree by transparently adding a prefix. However remember that any given prefix is not guaranteed to map directly to a node in the original tree: because a prefix can end in the middle of a node. Nonetheless, this approach should work fine AFAICS.

(2) The RadixTreeView object has a constructor which takes a reference to an intermediate node in the original radix tree.

However, this might not work as you wish. The RadixTreeView in this case would not be guaranteed to reflect all changes made subsequently to that branch in the original tree. This is because in the original tree, nodes are actually detached from the tree all the time. If the node wrapped by the RadixTreeView object was detached from the main tree, then the view would start to get out of sync with changes made to the main tree.

So your mileage may vary I guess. I’m not 100% familiar with your use case, but maybe option 1 could work for you.

Hope that helps,

Niall

On 29 Mar 2016, at 18:51, Kyle Bolton <kyle.doug...@gmail.com> wrote:

I have an implementation where I have a container of words on whose sub-branches I recurse thus narrowing the possibilities for the next level of recursion. How difficult would it be to implement a method taking a prefix and returning a subtree from the ConcurrentRadixTree implementation?

--
-- You received this message because you are subscribed to the "concurrent-trees-discuss" group.
http://groups.google.com/group/concurrent-trees-discuss
---
You received this message because you are subscribed to the Google Groups "concurrent-trees-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to concurrent-trees-d...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Kyle Bolton]

What. A. Boss!  Thank you for such a great answer. I had not thought of option #1 which will work well for my problem. I had been thinking along the lines of something akin to option #2 acting like NavigableSet.subset, but #1 is much easier for me to implement. Thanks again for the guidance.

-Kyle

[Niall]

No problem, glad it helped!