Add `chmax` / `chmin` functions to standard library

[magurofly]

Hi

I suggest new methods for Ord working like below:

trait Ord {
  fn chmax(&mut self, other: Self) -> bool { ... }
  fn chmin(&mut self, other: Self) -> bool { ... }
}

x.chmax(y);
// x = x.max(y);

x.chmin(y);
// x = x.min(y);

The method chmax replaces self and returns true if self < other, else returns false The method chmin works in same way

Also I suggest adding these methods for Option<T> where T: Ord

impl<T> Option<T> {
  fn chmin(&mut self, other: T) where T: Ord { ... }
  fn chmin(&mut self, other: T) where T: Ord { ... }
}

[steffahn]

What does chmax/chmin stand for?

Option implements Ord, so it seems suboptimal to add methods with the same name both as inherent and as trait methods.

---

It’s good to provide the default implementation with your suggestion (which also helps to demonstrate if the new method is a significant simplification). I suppose x.chmax(y) is something like

if *x < y { *x = y; true } else { false }

If you ignore the return value, it becomes

if *x < y { *x = y }

which isn’t particularly long. A use-case/example that does use the return value would be nice to see as well.

There’s also the option of providing these kinds of methods in a third-party extension trait – the only downside is that you’ll need an extra dependency and implementations can’t override/special-case the implementation. Is there any performance benefits that a specialized implementation for any Ord type could have over the default implementation?

[josh]

If I'm understanding correctly, these are effectively the compound-assignment operators max= and min=?

I don't think these need to be part of Ord. For other kinds of compound assignment operators, such as +=, it makes sense to have a trait that allows implementing them, because sometimes += can be implemented much more efficiently than + by consuming the destination.

For min and max, there's no need to modify-as-you-go and end up with an object that's a combination of two other objects. These operations will always end up either keeping the current object or entirely replacing it with a different object. If there are ways we can optimize that operation that we're not already doing, those optimizations would apply equally well to any other kind of "replace" operation, and we shouldn't make them specific to one particular replacement operation.

[scottmcm]

@magurofly

The method chmax replaces self and returns true if self < other , else returns false

Note that just a bool return like that is suspicious in a language with move semantics. Since String: Ord, for example, one would have to make an owned string to call it, which might then get thrown away.

So consider, if this moves forward, what it could look like such that it returns the other owned value somehow -- either the passed-in one, or the one from replacing self. Or consider exploring versions that use Borrow&ToOwned to allow passing simpler things as other.

[magurofly]

Here's a sample that computes shortest path by Floyd-Warshall algorithm

fn floyd_warshall(mat: &mut Vec<Vec<i64>>) {
  assert!(mat.len() == 0 || mat.len() == mat[0].len());
  for k in 0..mat.len() {
    for i in 0..mat.len() {
      for j in 0..mat.len() {
        let d = mat[i][k] + mat[k][j];
        mat[i][j].chmin(d);
      }
    }
  }
}

[CAD97]

You don't use the return value here; in what way is mat[i][j].chmin(d); notably better/clearer than just writing mat[i][j] = min(mat[i][j], d);? (Or is it max? I'm honestly not sure...)

Such a function could be interestingly useful for types that aren't Copy, but that case might also be better served by a simple written out if < { swap }.

[magurofly]

OK, I'll show another sample that computes shortest path by Dijkstra algorithm

This sample uses Option::chmin and its return value

// graph: Adjacency List
fn dijkstra(graph: &Vec<Vec<(usize, i64)>>, start: usize) -> Vec<Option<i64>> {
  let mut dist = vec![None; graph.len()];
  dist[start] = Some(0);
  let mut heap = BinaryHeap::new();
  heap.push((Reverse(0), start));
  while let Some((Reverse(d), u)) = heap.pop() {
    if dist[u] != Some(d) {
      continue;
    }
    for &(cost, v) in &graph[u] {
      if dist[v].chmin(d + cost) {
        heap.push((Reverse(d + cost), v);
      }
    }
  }
  dist
}

[matt1985]

Not a fan of non-is_* methods (other querying methods like contains are fine too) that return a bool, I always have to look up what the bool is supposed to indicate is true or false

[magurofly]

Thank you

That seems not bad