iter branch

[miekg]

Hi,

I've created an Iter() function, which I need in code using this radix tree, i.e I want to be able to "walk the tree" and do something with each node. See https://github.com/miekg/dns/blob/dev/zone.go for instance.

The problem I have now is that Iter() works and return *Radix, but each *Radix.key is only partial (that's the beauty of radix tree), but I need the full key... Any bright ideas on how to proceed? May a func (r *Radix) FullKey() function or something?

If this works, we can drop FindKey and let Find return an *Radix. Value needs to be exported again, so callers can see/modify it.

[miekg]

I think we need to leave this up to the caller and supply Key() and Children() methods so that a caller can create their own iterator...

[sauerbraten]

Just so I understand what Iter() is doing: it returns a channel where all the children of the caller node arrive at? why a channel?

How about just a function func SubTree(prefix string) *Radix that returns the sub tree containing all the nodes starting after prefix, and "" would give you the root radix? Then you could use the Do() function, or just manually walk down the tree.

As to the 'full key' problem: add parent *Radix to the Radix struct, and when you need the whole key you walk up that way til the root radix. You would have to link/unlink these on every Insert() or Remove(), though, but that shouldn't be too much work.

A combination of both should work for you, right?

Edit: Oh I just realized: we already have such a SubTree() function: find(). Maybe just rename it (export it) and change Find() to Get() and add a comment that Get() is just a wrapper for data storage convenience :)

[miekg]

I've commited some more stuff to this branch. I think I "cracked" it.

About adding a parent pointer, yes you can do that, but the beauty of radix trees is that they are memory efficient, so keeping *Radix small is worth while.

[sauerbraten]

Yep that were my thoughts when writing it in the first place :).

I'm starting to think that for your use case it would be a lot easier to just have the fields Value, Key and Children exported. Also, right now Find() is completely useless ;). Just rename find() to Find() or Get() (which I think would fit better).

[miekg]

renamed find to Find. Get() sound too much like the Getter/Setter stuff from Java... I like Find() better :-)

Shall I merge branch iter with master?

[sauerbraten]

yup looks good

[miekg]

ok, done