Rust Meetup Milano 29/5/2019

lib.rs

fn selle(matrix: &impl MatrixTrait) -> Vec<(usize, usize)> {
    let mut saddles = vec![];
    let (rows, cols) = matrix.size();
    let mins: Vec<_> = (0..cols).map(|c| matrix.col_min(c)).collect();
    for r in 0..rows {
        if let Some(max) = matrix.row_max(r) {
            for c in 0..cols {
                if let Some(min) = mins[c] {
                    if matrix.get(r, c) >= max && matrix.get(r, c) <= min {
                        saddles.push((r, c))
                    }
                }
            }
        }
    }
    saddles
}

impl MatrixTrait for Vec<Vec<u64>> {
    type Data = u64;

    fn get(&self, r: usize, c: usize) -> &u64 {
        &self[r][c]
    }

    fn size(&self) -> (usize, usize) {
        (self.len(), self.first().map(Vec::len ).unwrap_or(0))
    }

    fn row_max(&self, r:usize) -> Option<&u64> {
        self[r].iter().max()
    }

    fn col_min(&self, c:usize) -> Option<&u64> {
        self.iter().map( move |row| &row[c]).min()
    }
}


trait MatrixTrait {
    type Data: PartialOrd;

    fn get(&self, r: usize, c: usize) -> &Self::Data;
    fn size(&self) -> (usize, usize);
    fn row_max(&self, r:usize) -> Option<&Self::Data>;
    fn col_min(&self, c:usize) -> Option<&Self::Data>;
}

impl MatrixTrait for Matrix {
    type Data = u64;

    fn get(&self, r: usize, c: usize) -> &u64 {
        &self.rows[r][c]
    }

    fn size(&self) -> (usize, usize) {
        (self.rows.len(), self.rows.first().map(|row| row.len()).unwrap_or(0))
    }

    fn row_max(&self, r:usize) -> Option<&u64> {
        self.iter_row(r).max()
    }

    fn col_min(&self, c:usize) -> Option<&u64> {
        self.iter_col(c).min()
    }
}

struct Matrix { rows: Vec<Vec<u64>> }

impl Matrix {

    fn iter_row(&self, r: usize) -> std::slice::Iter<u64> {
        self.rows[r].iter()
    }

    fn iter_col(&self, c: usize) -> impl Iterator<Item=&u64> {
        self.rows.iter().map(move|row| &row[c] )
    }
}


#[cfg(test)]
mod tests {
    use super::*;

    fn ordina_selle(matrix: &impl MatrixTrait) -> Vec<(usize, usize)> {
        let mut result = selle(matrix);
        result.sort();
        result
    }

    #[test]
    fn singola_sella() {
        let i = vec![vec![9, 8, 7], vec![5, 3, 2], vec![6, 6, 7]];
        assert_eq!(vec![(1, 0)], selle(&i));
    }

    #[test]
    fn matrice_vuota() {
        let i = vec![vec![], vec![], vec![]];
        let exp: Vec<(usize, usize)> = Vec::new();
        assert_eq!(exp, selle(&i));
    }

    #[test]
    fn nessuna_sella() {
        let i = vec![vec![1, 2, 3], vec![3, 1, 2], vec![2, 3, 1]];
        let exp: Vec<(usize, usize)> = Vec::new();
        assert_eq!(exp, selle(&i));
    }

    #[test]
    fn multiple_selle_in_col() {
        let i = vec![vec![4, 5, 4], vec![3, 5, 5], vec![1, 5, 4]];
        assert_eq!(
            vec![(0, 1), (1, 1), (2, 1)],
            ordina_selle(&i)
        );
    }

    #[test]
    fn multiple_selle_in_riga() {
        let i = vec![vec![6, 7, 8], vec![5, 5, 5], vec![7, 5, 6]];
        assert_eq!(
            vec![(1, 0), (1, 1), (1, 2)],
            ordina_selle(&i)
        );
    }

    #[test]
    fn sella_in_vertice() {
        let i = vec![vec![8, 7, 9], vec![6, 7, 6], vec![3, 2, 5]];
        assert_eq!(vec![(2, 2)], selle(&i));
    }

    #[test]
    fn matrice_rettangolare_alta() {
        let i = vec![vec![1, 5], vec![3, 6], vec![2, 7], vec![3, 8]];
        assert_eq!(vec![(0, 1)], selle(&i));
    }

    #[test]
    fn matrice_rettangolare_larga() {
        let i = vec![vec![3, 1, 3], vec![3, 2, 4]];
        assert_eq!(vec![(0, 0), (0, 2)], ordina_selle(&i));
    }

    #[test]
    fn matrice_colonna() {
        let i = vec![vec![2], vec![1], vec![4], vec![1]];
        assert_eq!(vec![(1, 0), (3, 0)], ordina_selle(&i));
    }

    #[test]
    fn matrice_riga() {
        let i = vec![vec![2, 5, 3, 5]];
        assert_eq!(vec![(0, 1), (0, 3)], ordina_selle(&i));
    }

    #[test]
    fn tutte_selle() {
        let i = vec![vec![5, 5, 5], vec![5, 5, 5], vec![5, 5, 5]];
        assert_eq!(
            vec![
                (0, 0),
                (0, 1),
                (0, 2),
                (1, 0),
                (1, 1),
                (1, 2),
                (2, 0),
                (2, 1),
                (2, 2)
            ],
            ordina_selle(&i)
        );
    }
}