1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107

use crate::{Position, SquareMatrix, WeightNum, Weights};

#[derive(Debug)]
pub struct WeightMatrix<T: WeightNum> {
    c: SquareMatrix<T>,
}

impl<T: WeightNum> Weights for WeightMatrix<T> {
    type T = T;

    #[inline(always)]
    fn n(&self) -> usize {
        self.c.shape()[0]
    }

    #[inline]
    fn element_at(&self, pos: Position) -> T {
        self.c[(pos.row, pos.column)]
    }

    // for each row, subtracts the minimum of that row from each other value in the
    // row.
    fn sub_min_of_each_row(&mut self) {
        for row in 0..self.n() {
            let min = self.min_of_row(row);
            self.sub_row(row, min);
        }
    }

    // Add `val` to every element in row `row`.
    fn add_row(&mut self, row: usize, val: T) {
        self.c
            .row_mut(row)
            .mapv_inplace(|cur| cur.add_if_valid(val));
    }

    // Subtract `val` from every element in column `col`.
    fn sub_column(&mut self, col: usize, val: T) {
        self.c
            .column_mut(col)
            .mapv_inplace(|cur| cur.sub_if_valid(val));
    }

    fn is_solvable(&self) -> bool {
        for row in self.c.genrows() {
            if row.iter().all(|c| !c.is_valid()) {
                return false;
            }
        }
        true
    }
}

impl<T: WeightNum> WeightMatrix<T> {
    pub fn from_row_vec(n: usize, data: Vec<T>) -> WeightMatrix<T> {
        WeightMatrix {
            c: SquareMatrix::from_shape_vec((n, n), data).unwrap(),
        }
    }

    pub fn from_fn<F: Fn((usize, usize)) -> T>(n: usize, f: F) -> WeightMatrix<T> {
        assert!(n > 0);
        WeightMatrix {
            c: SquareMatrix::from_shape_fn((n, n), f),
        }
    }

    /// Return the minimum element of row `row`.
    fn min_of_row(&self, row: usize) -> T {
        let row_iter = self.c.row(row);
        let mut valid_iter = row_iter.iter().filter(|cost| cost.is_valid()).cloned();
        let first_min = valid_iter.next().unwrap();
        valid_iter.fold(
            first_min,
            |total_min, val| if val < total_min { val } else { total_min },
        )
    }

    // Subtract `val` from every element in row `row`.
    fn sub_row(&mut self, row: usize, val: T) {
        self.c
            .row_mut(row)
            .mapv_inplace(|cur| cur.sub_if_valid(val));
    }

    pub fn as_slice(&self) -> &[T] {
        self.c.as_slice().unwrap()
    }
}

#[test]
fn test_weight_matrix() {
    assert_eq!(0, WeightMatrix::from_row_vec(1, vec![0]).min_of_row(0));
    assert_eq!(1, WeightMatrix::from_row_vec(1, vec![1]).min_of_row(0));
    assert_eq!(
        1,
        WeightMatrix::from_row_vec(2, vec![5, 1, 0, 0]).min_of_row(0)
    );

    let mut mat = WeightMatrix::from_row_vec(2, vec![0, 1, 2, 3]);
    mat.sub_row(1, 1);
    assert_eq!(&[0, 1, 1, 2], mat.as_slice());

    let mut mat = WeightMatrix::from_row_vec(2, vec![5, 3, 2, 3]);
    mat.sub_min_of_each_row();
    assert_eq!(&[2, 0, 0, 1], mat.as_slice());
}