Monge Array - leftmost minimum for each row

Question

This implementation is the result of solving exercise 4-6 "Monge Arrays" from the book Introduction to algorithms.

Definition of a Monge Array:

An m x n array A of real numbers is a Monge array if for all \$i\,ドル \$j\,ドル \$k\,ドル and \$l\$ such that \1ドル \le i \lt k \le m\$ and \1ドル \le j \lt l \le n\,ドル we have \$A[i, j] + A[k, l] \le A[i, l] + A[k, j]\$.

Relevant parts of problem 4-6:

d. Here is a description of a divide-and-conquer algorithm that computes the left- most minimum element in each row of an m x n Monge array A:

Construct a submatrix A' of A consisting of the even-numbered rows of A. Recursively determine the leftmost minimum for each row of A'. Then compute the leftmost minimum in the odd-numbered rows of A. Explain how to compute the leftmost minimum in the odd-numbered rows of A (given that the leftmost minimum of the even-numbered rows is known) in \$O(m + n)\$ time.

e. Write the recurrence describing the running time of the algorithm described in part (d). Show that its solution is \$O(m + nlog(m))\$.

I am especially interested in making my code more idiomatic and clean although any improvements to the algorithm are also welcome.

fn min(monge: &Vec<i32>, from: usize, to: usize) -> usize{
 let mut min = monge[from];
 (from + 1..to).fold(from, |m,i| {
 if(monge[i] < min){
 min = monge[i]; 
 i 
 } else{ m } 
 })
}
fn minimums(monge: &Vec<i32>, leftmost: & mut Vec<usize>, rows: usize, columns: usize, factor: usize)
{
 if rows == 1 { 
 leftmost[0] = min(monge, 0, columns) % columns;
 }
 else {
 let mid = rows - (rows / 2);
 minimums(monge, leftmost, mid, columns, 2 * factor); 
 let get = |i, j| (i * columns) + j;
 for row in (0..)
 .map(|x| factor * (2 * x + 1))
 .take_while(|&x| x < (rows - 1)) {
 leftmost[row] = min(monge, 
 get(row ,leftmost[row - factor]), 
 get(row, leftmost[row + factor] + 1)) % columns; 
 }
 if rows % 2 == 0 {
 let row = factor * (rows - 1);
 leftmost[row] = min(monge,
 get(row , leftmost[row - factor]),
 get(row, columns)) % columns; 
 }
 }
}
fn main() {
 let row = 7;
 let x = vec!
 [10,17,13,28,23,
 17,22,16,29,23,
 24,28,22,34,24,
 11,13,6,17,7,
 45,44,32,37,23,
 36,33,19,21,6,
 75,66,51,53,34];
 let mut leftmost = vec![0;row];
 minimums(&x, &mut leftmost, row,5, 1);
 for x in leftmost { 
 println!("{}", x); 
 }
}

Answer 1

1. Read compiler warnings and fix them:

   src/main.rs:7:11: 7:27 warning: unnecessary parentheses around `if` condition, #[warn(unused_parens)] on by default
   src/main.rs:7 if(monge[i] < min){
    ^~~~~~~~~~~~~~~~
   

2. Spaces before braces

   fn min(...) -> usize{ // No
   fn min(...) -> usize { // Yes
   

3. Be consistent about brace indentation

   // No
   if {
    1
   } else { 2 }
   // Yes
   if {
    1
   } else {
    2
   }
   

4. mut is stuck to the &

   & mut Vec<usize> // No
   &mut Vec<usize> // Yes
   

5. else lives on the same line as the previous curly brace

   // No
   if true {
    1
   }
   else {
    2
   }
   // Yes
   if true {
    1
   } else {
    2
   }
   

6. No need to leave blank space at the beginning of a block

   // No
   fn foo() {
    let a = 1;
   // Yes
   fn foo() {
    let a = 1;
   

7. Keep the macro braces attached to the macro name, and indent the body if it's going to be multiline. Leave a trailing comma, and use spaces after the comma

   let x = vec![
    10, 17, 13, 28, 23, 
    17, 22, 16, 29, 23, 
    24, 28, 22, 34, 24, 
    11, 13, 6, 17, 7, 
    45, 44, 32, 37, 23, 
    36, 33, 19, 21, 6, 
    75, 66, 51, 53, 34,
   ];
   

8. Leave spaces after commas in function calls as well, but not before

   // No
   get(row ,leftmost[row - factor]),
   // Yes
   get(row, leftmost[row - factor]),
   

9. A single space around =

   leftmost[row] = min(...); // No
   leftmost[row] = min(...); // Yes
   

10. Never take a &Vec<T> as an argument, use a &[T] instead. This allows more types to be provided

11. Your min function is poorly named. The name seems to suggest it will return the minimum value, when it actually returns the index of the minimum value. Rename it to something intention-revealing. Maybe index_of_minimum

12. Space after a ; in an array or vector

    vec![0;row]; // No
    vec![0; row]; // Yes
    

13. Instead of having multiple lines in a for x in y clause, create a variable to store that in.

    // Poor name because I'm not sure what it really is
    let x_rows = (0..)
     .map(|x| factor * (2 * x + 1))
     .take_while(|&x| x < (rows - 1));
    for row in x_rows {
    

14. Eventually, min_by will be stabilized, and you can use it:

    // May be off-by-one errors here
    let (min_index, _) =
     monge.iter()
     .enumerate()
     .skip(from)
     .take(to - from)
     .min_by(|&(_, v)| v)
     .unwrap();
    min_index
    

I'm sure there's more that can be suggested, but my brain is tired for now ^_^.

fn index_of_minimum(monge: &[i32], from: usize, to: usize) -> usize {
 let mut min = monge[from];
 (from + 1..to).fold(from, |m,i| {
 if monge[i] < min {
 min = monge[i];
 i
 } else {
 m
 }
 })
}
fn minimums(monge: &[i32], leftmost: &mut Vec<usize>, rows: usize, columns: usize, factor: usize) {
 if rows == 1 {
 leftmost[0] = index_of_minimum(monge, 0, columns) % columns;
 } else {
 let mid = rows - (rows / 2);
 minimums(monge, leftmost, mid, columns, 2 * factor);
 let get = |i, j| (i * columns) + j;
 let x_rows = (0..)
 .map(|x| factor * (2 * x + 1))
 .take_while(|&x| x < (rows - 1));
 for row in x_rows {
 leftmost[row] = index_of_minimum(monge,
 get(row, leftmost[row - factor]),
 get(row, leftmost[row + factor] + 1)) % columns;
 }
 if rows % 2 == 0 {
 let row = factor * (rows - 1);
 leftmost[row] = index_of_minimum(monge,
 get(row, leftmost[row - factor]),
 get(row, columns)) % columns;
 }
 }
}
fn main() {
 let row = 7;
 let x = vec![
 10, 17, 13, 28, 23,
 17, 22, 16, 29, 23,
 24, 28, 22, 34, 24,
 11, 13, 6, 17, 7,
 45, 44, 32, 37, 23,
 36, 33, 19, 21, 6,
 75, 66, 51, 53, 34,
 ];
 let mut leftmost = vec![0; row];
 minimums(&x, &mut leftmost, row, 5, 1);
 for x in leftmost {
 println!("{}", x);
 }
}