munkres 0.5.2

Kuhn-Munkres (aka Hungarian) algorithm for solving the Assignment Problem in O(n^3)
Documentation 
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

use crate::{Position, SquareMatrix};

#[derive(Debug)]
pub struct MarkMatrix {
    marks: SquareMatrix<Mark>,
}

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[repr(u8)]
enum Mark {
    None,
    Star,
    Prime,
}

impl MarkMatrix {
    pub fn new(n: usize) -> Self {
        Self {
            marks: SquareMatrix::from_shape_fn((n, n), |_| Mark::None),
        }
    }

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

    #[inline]
    fn get_mark(&self, pos: Position) -> Mark {
        self.marks[(pos.row, pos.column)]
    }

    #[inline]
    fn set_mark(&mut self, pos: Position, mark: Mark) {
        self.marks[(pos.row, pos.column)] = mark;
    }

    pub fn toggle_star(&mut self, pos: Position) {
        let cell = self.marks.get_mut((pos.row, pos.column)).unwrap();
        if *cell == Mark::Star {
            *cell = Mark::None;
        } else {
            *cell = Mark::Star;
        }
    }

    pub fn star(&mut self, pos: Position) {
        self.set_mark(pos, Mark::Star);
    }

    pub fn prime(&mut self, pos: Position) {
        self.set_mark(pos, Mark::Prime);
    }

    pub fn is_star(&self, pos: Position) -> bool {
        match self.get_mark(pos) {
            Mark::Star => true,
            _ => false,
        }
    }

    pub fn is_prime(&self, pos: Position) -> bool {
        match self.get_mark(pos) {
            Mark::Prime => true,
            _ => false,
        }
    }

    #[cfg(test)]
    pub fn is_none(&self, pos: Position) -> bool {
        match self.get_mark(pos) {
            Mark::None => true,
            _ => false,
        }
    }

    #[inline]
    pub fn each_star<F>(&self, mut f: F)
    where
        F: FnMut(Position),
    {
        for (row, row_data) in self.marks.genrows().into_iter().enumerate() {
            for (column, &cell) in row_data.iter().enumerate() {
                if cell == Mark::Star {
                    f(Position { row, column });
                }
            }
        }
    }

    fn find_first_mark_in_row(&self, row: usize, mark: Mark) -> Option<usize> {
        self.marks
            .row(row)
            .iter()
            .enumerate()
            .find(|(_, &cell)| cell == mark)
            .map(|(column, _)| column)
    }

    fn find_first_mark_in_column(&self, column: usize, mark: Mark) -> Option<usize> {
        self.marks
            .column(column)
            .iter()
            .enumerate()
            .find(|(_, &cell)| cell == mark)
            .map(|(row, _)| row)
    }

    pub fn find_first_star_in_row(&self, row: usize) -> Option<usize> {
        self.find_first_mark_in_row(row, Mark::Star)
    }

    pub fn find_first_prime_in_row(&self, row: usize) -> Option<usize> {
        self.find_first_mark_in_row(row, Mark::Prime)
    }

    pub fn find_first_star_in_column(&self, column: usize) -> Option<usize> {
        self.find_first_mark_in_column(column, Mark::Star)
    }

    pub fn clear_primes(&mut self) {
        for cell in self.marks.iter_mut() {
            if *cell == Mark::Prime {
                *cell = Mark::None
            }
        }
    }
}