[Feature Request] Support Gob (Encoding & Decoding)

[apanag]

Hello there and really appreciate your work implementing the adaptive radix trie.

Due to the fact that there are no exported fields in the structs (Tree, Node, Item etc.) it is not possible for the Gob encoder to encode the Tree into binary.

As an example the following simple code:

rt := radixtree.New[string]()
rt.Put("tomato", "TOMATO")

var byt bytes.Buffer
writer := gob.NewEncoder(&byt)

err := writer.Encode(rt)
if err != nil {
  panic(err)
}

Exits with a panic error message:

panic: gob: type radixtree.Tree[string] has no exported fields

From my point of view to support gob, there are two ways to achieve that:

1. Convert all the fields from unexported to exported and gob will be supported out of the box:

// Tree is a radix tree of bytes keys and any values.
type Tree[T any] struct {
	Root radixNode[T] // instead of root
	Size int          // instead of size
}

2. Implement a custom encoder and decoder for each struct (Tree, Node, Item etc.). As an example the Tree struct needs to implement the following two methods (the same should happen for each struct):

func (t *Tree[T any]) GobEncode() ([]byte, error) {
        // implement custom logic
	return nil, nil
}

func (t *Tree[T any]) GobDecode(data []byte) error {
        // implement custom logic
	return nil
}

Please let me know your thoughts.

[gammazero]

As far as the preferred approach... as a library maintainer I would prefer implementing custom logic so as to avoid exporting additional public API than must be maintained and cannot change easily. Here is said implementation: #29

Why encode the radix tree, instead of dumping a set of key-value pairs from which a radix tree can be built?

I am finding it difficult to answer this question. Here are some possible reasons, any why they do not work:

• Encoded radix tree may be smaller than key-value pairs due to deduplication of very large common prefixes?
  • Amount of data in common prefixes would have to be large relative to overall data size for this to offer space saving.
  • Even if above true, does not matter if key-value pairs are stored in compressed format (e.g. gzip).
• Deserializing the tree may be faster than rebuilding it?
  • Not useful if there is a need to ensure the validity of the tree.
  • Unlikely to be faster. Benchmark, using a dictionary, comparing reload from encoded vs rebuild from data:

    BenchmarkRebuildVsReload/Reload_from_encoded-10         1    5646625000 ns/op
    BenchmarkRebuildVsReload/Rebuild_from_dictionary-10    32      36089326 ns/op
    

@apanag What are your reasons for encoding a radix tree instead of rebuilding from key-value pairs?