Puzzle with a BTreeMap, a Borrow and “Sets”

help
1

I'm trying to implement a wrapper on top of BTreeMap which can return first element from a subset represented by the Map:

use std::collections::btree_map::Range;
use std::collections::BTreeMap;
use std::ops::RangeBounds;

trait PopBounded<Key, Value> {
    fn pop_next_bounded(&mut self, range: impl RangeBounds<Key>) -> Option<Value>;
}

impl<Key: Ord, Value> PopBounded<Key, Value> for BTreeMap<Key, Value> {
    fn pop_next_bounded(&mut self, boundaries: impl RangeBounds<Key>) -> Option<Value> {
        let mut range: Range<Key, Value> = self.range(boundaries);
        let (key, _value) = range.next()?;
        self.remove(key)
    }
}

(Playground) I just curious what would be an idiomatic resolution for the following error:

   Compiling playground v0.0.1 (/playground)
error[E0502]: cannot borrow `*self` as mutable because it is also borrowed as immutable
  --> src/lib.rs:13:9
   |
11 |         let mut range: Range<Key, Value> = self.range(boundaries);
   |                                            ---------------------- immutable borrow occurs here
12 |         let (key, _value) = range.next()?;
13 |         self.remove(key)
   |         ^^^^^------^^^^^
   |         |    |
   |         |    immutable borrow later used by call
   |         mutable borrow occurs here

For more information about this error, try `rustc --explain E0502`.
error: could not compile `playground` due to previous error

My goal is to understand how to modify the Map to "extract" entries nearest to the lowest and highest boundaries of a Range.

2

I think to make this work you need a 'borrowing iterator' because you need the next method to borrow the whole hashmap and return a cursor, with mutable access to the original map, then you would probably do el.remove() rather than self.remove(el) because self was borrowed by el.

The solution I would use for this problem is immutable data structures (e.g. the im crate), because this is basically what they're for.

EDIT I should say a little more about the im crate. The advantage of it is that Clone::clone is very cheap. It achieves this by sharing as much structure between the cloned and the new values.

3

Hmm thinking about this more, could you do what you want with the BTreeMap::retain function? Any solution using this method will be O(n) though.

EDIT HashMap -> BTreeMap

4

I'm trying to interact with an Ordered Set of entries. I'm just trying to comprehend how to get first or last element from a specific subset.
It should be O(Log n) by default. Keys are ordered.

5

As far as I can tell, what you want it probably impossible (to do efficiently) using the existing BTreeMap API, unless you start cloning the key that range.next() returned. Impossible not because it’s fundamentally problematic, but just because the API is too limiting.

1 Like
6

If making a copy of the key is inexpensive relative to the other operations, you can write it like this:

impl<Key: Ord+Clone, Value> PopBounded<Key, Value> for BTreeMap<Key, Value> {
    fn pop_next_bounded(&mut self, boundaries: impl RangeBounds<Key>) -> Option<Value> {
        let mut range: Range<Key, Value> = self.range(boundaries);
        let (key, _value) = range.next()?;
        let key = key.clone();
        self.remove(&key)
    }
}

Or, if you only want to support Copy keys (like integers) to eliminate the possibility of expensive clones:

impl<Key: Ord+Copy, Value> PopBounded<Key, Value> for BTreeMap<Key, Value> {
    fn pop_next_bounded(&mut self, boundaries: impl RangeBounds<Key>) -> Option<Value> {
        let mut range: Range<Key, Value> = self.range(boundaries);
        let (&key, _value) = range.next()?;
        self.remove(&key)
    }
}

Both of these options will be O(log n) in the length of the set.

7

A reasonable addition to the API would probably be to add methods to btree_map::{Entry,OccupiedEntry,VacantEntry} to walk forwards and backwards through the map in key order, something like:

fn next_entry(self)->Result<OccupiedEntry, Self>
fn prev_entry(self)->Result<OccupiedEntry, Self>
1 Like
8

If the BTreeMap::append implementation was smarter, you would be able to do this in O(log n) without cloning the key:

  • split_off at the key
  • pop_first to extract your entry
  • append to merge the trees back again (this could be, but isn't currently, O(log n) because the trees aren't overlapping so the merge is easy)
2 Likes
9

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.