support search_covering

[stevenjoezhang]

Thank you for creating such a convenient and useful Rust library! I am doing research about BGP routing, and previously, I implemented an algorithm using the py-radix library in Python, but it had serious efficiency issues (the program needed to process millions of prefixes and ASN data and perform complex calculations), so I rewrote it in Rust. Most of the algorithms could find equivalent replacements in prefix-trie, which is great. However, a method called search_covering from the py-radix library does not have a corresponding implementation in prefix-trie, so I would like to add it. This method would return a vec of all nodes that cover a given prefix.

[tiborschneider]

Thanks for the PR. It looks good. However, I have a couple of suggestions:

• Document that prefix itself will also be returned if present, and that all elements will be sorted according to the depth in the tree.
• Add the same function also for PrefixSet
• Add functions to not only get the values, but also the prefixes (or both).
• How about not returning a Vec, but returning an Iterator instead? Allows the user to collect into whatever data structure they like, and abort after prefixes of a specific length, etc...

In other words, let's add the following functions (and names that match with rust's naming convention of maps):

• PrefixSet::cover to return Vec<&'a P>
• PrefixMap::cover_keys to return Vec<&'a P>
• PrefixMap::cover_values to return Vec<&'a T>
• PrefixMap::cover to return Vec<(&'a P, &'a T)>

Do you have time to implement those changes? If not, I can also take care of them.

[tiborschneider]

I will close this PR now, as I implemented it myself in #5 with my comments above.

Small remark: There was a bug in your implementation that the root node would never be returned.

[stevenjoezhang]

Thanks, your implementation is more elegant! And I must admit that I am still a Rust newbie 😂