add find_or_insert method to the Map trait

[thestinger]

[graydon]

Agreed. Also several of the other ones that appear on hashmap: find_or_insert_with, insert_or_update_with, reserve_at_least, consume.

[thestinger]

@graydon: I think consume will get replaced with an external iterator, moving the container into the iterator on creation

[davidhalperin]

I'm working on this. I'm trying to add default methods where possible, swap can be implemented in terms of insert_or_update_with for instance. Unfortunately, find_or_insert_with and insert_or_update_with can't quite be implemented in terms of each other. The options for this as far as I can tell are:

• Implementing default methods for one of these inefficiently so it has to find the key twice. (Obviously the maps in std would override both anyway.)
• Not having a default method for both of these so that there are 2 basic insert-like methods that implementations would be forced to provide.
• Adding another most general insert-like method. (Something like insert_with_or_update_with but hopefully with a less cumbersome name.)

Any preferences between those or other suggestions?

[thestinger]

I don't think there should be a default method implementation if it's going to do two searches but I'm fine with both of the other options.

[nikomatsakis]

Perhaps we can just add "mangle" to the map trait and impl the others as default methods based on that?

[davidhalperin]

First, sorry for saying I was going to do this and sitting on it for so long. I keep meaning to make time to try to help out with rust but getting busy with other things. I still plan to try to get this done.

How about changing find_or_insert_with to return (&'a K, &'a mut V) instead of just &'a mut V? It seems like there should be some sort of insert operation where you remember what the key was afterwards, anyway. If we did that, it would mean you could implement insert_or_update_with like so:

fn insert_or_update_with<'a>(&'a mut self, k: K, v: V,
                             f: &fn(&K, &mut V)) -> &'a mut V {
    let cell = Cell::new(v);
    let (k, v) = self.find_or_insert_with(k, |_| cell.take());
    if !cell.is_empty() {
        f(k, v);
    }
    v
}

That seems nicer than mangle to me. I think mangle is a little clunky and poorly named, FWIW. Up to you guys though.

[nikomatsakis]

Interesting thought! I agree that mangle is clunky and awkwardly named (despite being the one who suggested it).

I would also consider just modifying the callback for insert_or_update_with not to take the key. I personally have never once needed it, and I see no code in our repository that does either (though I guess that, in the general case of affine keys, it can be useful).

[TeXitoi]

@davidhalperin : are you still working on that? I am interested in working on this issue. Maybe we can work together?

[davidhalperin]

@TeXitoi sorry for not getting back to you. I have Monday off and I think I should have a good chunk of time to work on this this weekend. By the end of the day on Monday I'll either finish this and put together a pull request or pass what I've done so far on to you to finish up. Sound good?

[TeXitoi]

@davidascher Perfect :)

[davidhalperin]

I got very close to finishing it this weekend. The one thing I couldn't figure out is how to write insert_or_update_with for TreeMap. You can't just make a recursive call and then call skew and split like the current insert does because this insert returns an internal pointer, so the current node stays mutably borrowed and you can't mutably borrow again it to balance the tree. If anyone has any ideas about how to get around that, I should be able to finish this up shortly.

[TeXitoi]

IMHO, it's not possible to do that with safe code without doing an insert and then a find (i.e. with 2 searches). Then, skew and split move the children, so the reference should be valid. The only way I can see to do that with a search is with unsafe code:

fn insert_or_update_with<'a, K: TotalOrd, V>(
    node: &'a mut Option<~TreeNode<K, V>>,
    key: K, value: V,
    f: &fn(&K, &mut V)) -> &'a mut V {
    match *node {
      Some(ref mut save) => {
        match key.cmp(&save.key) {
          Less => {
            let res: *mut V = unsafe {
              transmute(insert_or_update_with(&mut save.left, key, value, f))
            };
            skew(save);
            split(save);
            unsafe{transmute(res)}
          }
          Greater => {
            let res: *mut V = unsafe {
              transmute(insert_or_update_with(&mut save.right, key, value, f))
            };
            skew(save);
            split(save);
            unsafe{transmute(res)}
          }
          Equal => {
            save.key = key;
            f(&save.key, &mut save.value);
            &mut save.value
          }
        }
      }
      None => {
       *node = Some(~TreeNode::new(key, value));
        &mut node.get_mut_ref().value
      }
    }    
}

It compiles, but I didn't try running it and that's the first time I write unsafe code. And that's quite sad to have TreeMap using unsafe code.

I hope I'm wrong and there is another solution.

[davidhalperin]

@TeXitoi I reached the same conclusion and was going to ask for a sanity check. I don't think doing 2 searches would help even if we wanted to sacrifice performance to write safe code. The key gets moved into the map and if you tried to keep a reference while you rebalanced the key, you'd run into exactly the same issue. My implementation uses transmute_mut_region instead of transmute to be a little more specific about how it's being unsafe but is basically the same and it seems to work. Thanks for the help! I will finish this up today.

[nikomatsakis]

That does indeed look hard to type check. It wasn't obvious to me from glancing at the code that it was safe amidst all the unique pointer juggling and so on. @davidhalperin I think doing an insert and then a search would work, if you wanted to keep the code safe? not sure why it matters that key/value are moved into the map.