How to modify/partially remove a range from a BTre

Question

I'm trying to build a RangeSet out of a BTreeMap (where the keys are lower bounds and the values are upper bounds). This works quite well as long as I'm only looking up stuff. However, the first mutating method has me stumped:

If I want to insert a range to my set, I need to check a Range of my BTreeMap from the upper bound of the range from tail to head until the value in question is below the inserted range's lower bound, all contained ranges should be removed and overlapping ranges merged. However, even using .range_mut(..) which is currently unstable, I cannot find a way to delete an entry (because the map is still borrowed from by the range).

Am I using the wrong tool for the job? Can I make it work anyway – and if so, how? My current solution in pseudocode (I also use my own Cut type because Bounds are not Ord):

fn insert(&mut self, range: &Range) {
    for entry in self.map.range_mut(Cut::Unbounded, range.upper).rev() {
         if entry.1 < range.lower {
             break;
         } else if entry.0 > range.lower {
             delete entry
         } else {
             merge entry with range
         }
     }
}

Answer 1

You need to do this in two passes, collecting the keys you want to delete, and then iterate over that list and call remove.

Note that since while iterating over a tree you get references, you'll have to clone/copy the key because you'll have a reference to a key inside the map, which means you cannot borrow the map as mutable.

The reason for this is largely because the memory and ordering semantics get a bit wonky while deleting entries in the middle of an iteration. It's pretty difficult to delete entries in a tree while iterating over it. This is exacerbated by it being a map, which means the keys are ordered in some way in the tree, meaning that nodes may end up rotating their children, so you may have previously visited your left child and now suddenly that's your current node, or right child. It's difficult to keep track of where you are.

In addition, B-Tree nodes are lists of subnodes that have dynamics for when nodes need to merge and split, it's even more of a headache to do that in the middle of an iteration.

Some of this is due to manual memory semanics. The keys and values are stored within the nodes, not on the heap, so memory is going to be bouncing all over the place and making sure it's not invalidated is non-trivial. Especially if the user was collecting references to entries in the tree elsewhere in the loop.

Edit: And, regardless of possibility, the fact of the matter is that an iterator borrows the Map, which means you can't borrow it again to delete things. This might be different if the iterator returned something like an Entry, but as far as I know no iterator that does this exists.