What would be proper API for index.get()?

I am creating llrb-index, an in-memory-store, for parametrised <K, V> pairs.
Ref: GitHub - bnclabs/llrb-index: Left Leaning Red Black Tree in Rust.

After going through the documentation under

I am having a dilemma in choosing API for get() method.

    /// Get the value for key.
    pub fn get<Q>(&self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {

or,

    /// Get the value for key.
    pub fn get(&self, key: &K) -> Option<V> {

or,

    /// Get the value for key.
    pub fn get(&self, key: &Q) -> Option<V>
    where
        Q: AsRef<K>
    {

What would be appropriate ?

Thanks,

The first one is the best in general. Standard library choose it for the maximum flexibility in caller side. For example, you can .get() over HashMap<String, T> using &static str, which is not possible if the api follows the second or the third way.

Thanks for the suggestion.

Two drawbacks I see with first option is that:

a. It is complex for someone getting started with Rust.

b. Will there be any performance impact borrowing every
node down the path. Get implementation is as follows:

let mut node = self.root.as_ref().map(Deref::deref);
while let Some(nref) = node {
    node = match nref.key.borrow().cmp(key) {
        Ordering::Less => nref.right_deref(),
        Ordering::Greater => nref.left_deref(),
        Ordering::Equal => return Some(nref.value.clone()),
    };
}

Actually my current implementation uses something similar to stdlib.
But llrb-index also have range() API, like:

pub fn range(&self, low: Bound<&K>, high: Bound<&K>) -> Range<K, V> {

And it looks like an overkill to go with first option for range(),
and I am tempted to keep the APIs uniform.

Complexity is not something that can be easily measured on a single axis. While it may be more complex to read and understand the function signature it also makes usage of the function simpler. The complexity is also something just about every rust user is going to encounter since the standard collections use this technique. Diverging from the standard container API can actually add unnecessary complexity for users that are already familiar with those API's.

In terms of your range API, I would suggest you look at BTreeMap for inspiration. It has a similar range API, but rather than accepting two arguments it accepts anything that implements RangeBounds for the borrowed key. This provides a lot of flexibility.

2 Likes

@ggriffiniii thanks for the suggestion. The get() and range() APIs from std lib's collection was useful. Now llrb-index follow similar API giving importance to flexibility without compromising on performance.

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.