Find neighbor of target in BTreeMap (or any other treemap) in rust

Question

How to efficiently implement below c++ function in rust? The data structure must be tree based (BTree, RBTree, etc).

Given a sorted map m, a key target, and a value val.

Find the lower_bound entry (the first key >= target). return DEFAULT if no such entry.
If the value of the found entry <= val and it has previous entry, return value of previous entry.
If the value of the found entry > val and it has next entry, return value of the next entry.
Otherwise, return the found value.

template<class K, class V>
V find_neighbor(const std::map<K, V>& m, const K& target, const V& val) {
    auto it = m.lower_bound(target);
    if( it == m.end() ) return V{}; // DEFAULT value.
    if( it->second <= val && it != m.begin() )
        return (--it)->value;  // return previous value
    if( it->second > val && it != (--m.end()) )
        return (++it)->value;  // return next value
    return it->second;         // return target value
}

Welcome to stackoverflow! Did you try anything so far, and if yes, can we see your porting attempt? — Finomnis, Jun 11 '22 at 16:01
From my first glance I don't think a functionality similar to `.lower_bound()` exists in `BTreeMap` yet — Finomnis, Jun 11 '22 at 16:17
Open question: Should the function return a copy of the value, or a reference to the value? If analogous to C++, probably a copy, but that's quite non-rusty. In rust, by default, values are non-copyable — Finomnis, Jun 11 '22 at 16:50
Let's assume the value type V is copyable since the input map is const. — azyx, Jun 11 '22 at 16:58
`The input map is const` and `V is copyable` are two completely unrelated statements. — Finomnis, Jun 11 '22 at 17:24

Finomnis · Answer 1 · 2022-06-11T17:33:09.820

Thats what I've got.

Create trait FindNeighbor that adds the function find_neighbor to all BTreeMaps

I'm quite confused what the algorithm does, though, tbh. But it should (tm) behave identical to the C++ version.

If you use this in an actual project though, for the love of god, please write unit tests for it.

use std::{borrow::Borrow, collections::BTreeMap};

trait FindNeighbor<K, V> {
    type Output;

    fn find_neighbor(&self, target: K, val: V) -> Self::Output;
}

impl<K, V, KI, VI> FindNeighbor<K, V> for BTreeMap<KI, VI>
where
    K: Borrow<KI>,
    V: Borrow<VI>,
    KI: Ord,
    VI: Default + PartialOrd + Clone,
{
    type Output = VI;

    fn find_neighbor(&self, target: K, val: V) -> VI {
        let val: &VI = val.borrow();
        let target: &KI = target.borrow();

        let mut it = self.range(target..);
        match it.next() {
            None => VI::default(),
            Some((_, it_value)) => {
                if it_value <= val {
                    match self.range(..target).rev().next() {
                        Some((_, prev_val)) => prev_val.clone(),
                        None => it_value.clone(),
                    }
                } else {
                    match it.next() {
                        Some((_, next_val)) => next_val.clone(),
                        None => it_value.clone(),
                    }
                }
            }
        }
    }
}

fn main() {
    let map = BTreeMap::from([(1, 5), (2, 3), (3, 8)]);
    println!("{:?}", map.find_neighbor(3, 10));
}

Note a couple of differences between C++ and Rust:

Note that there are trait annotations on the generic parameters. Generic functions work a little different than C++ templates. All the capabilities that get used inside of a generic method have to be annotated as trait capabilities. The advantage is that generics are then guaranteed to work with every type they take, no random compiler errors can occur any more. (C++ templates are more like duck-typing, while Rust generics are strongly typed)
We implement a trait that adds new functionality to an external struct. That is something that also doesn't exist in C++, and tbh I really like this mechanic in Rust.

Thanks! It works but not as efficient as the c++ code. Any way to avoid searching for the same key twice? ```self.range(..target).rev()``` — azyx, Jun 11 '22 at 18:07
No, because iterators in Rust [aren't bidirectional](https://stackoverflow.com/questions/38227722/iterating-forward-and-backward). But it's in the same complexity class as the C++ version, so to say "it's not as effective" would merrit a benchmark imo. — Finomnis, Jun 11 '22 at 18:10
I don't think it'll get more efficient than that without writing your own map type, but I'm also not convinced that this is too slow. — Finomnis, Jun 11 '22 at 18:31
Another case shows Rust doesn't have good support for containers: https://stackoverflow.com/questions/40196586/mutable-reference-to-container-object-within-iterator-loop — azyx, Jul 02 '22 at 03:22
@azyx I have no idea what you mean with that statement. The link you provide doesn't mention anything about *support for containers*. — Finomnis, Jul 04 '22 at 21:11

Find neighbor of target in BTreeMap (or any other treemap) in rust

1 Answers1