Get next value in ordered tree

Question

Given an ordered map (like BTreeMap) and a value in the map, how do you get the "next" larger (or smaller) value in the map?

There are many ordered tree libraries. It would be amazing to get an answer for:

1. BTreeMap
2. rudy::rudymap::RudyMap (https://docs.rs/rudy/latest/rudy/)
3. art_tree (https://docs.rs/art-tree/latest/art_tree/)
4. judy arrays

Answer 1

You can get the next smaller or larger key of a BTreeMap by using an iterator from .range(..):

use std::ops::Bound;
use std::collections::BTreeMap;

fn main() {
    let map: BTreeMap<&str, i32> = [
        ("a", 1),
        ("c", 4),
        ("h", 0),
        ("m", 2),
        ("z", 5),
    ].into_iter().collect();
    
    let mut iter = map.range(.."h");
    let next_smaller = iter.next_back();
    
    let mut iter = map.range::<&str, _>((Bound::Excluded("h"), Bound::Unbounded));
    let next_larger = iter.next();
    
    println!("next_smaller: {:?}", next_smaller);
    println!("next_larger : {:?}", next_larger);
}

next_smaller: Some(("c", 4))
next_larger : Some(("m", 2))

Getting the next larger looks a bit gnarly since there is no "h".. range syntax that excludes "h". You can of course use "h".. if you want to, but you'd have to call .next() an additional time to skip over the known element.