~mht/cra

ref: 9cd196f46fa4a5acca5b18ba32bea2a50e0a9df6 cra/cra/src/main.rs -rw-r--r-- 3.3 KiB
9cd196f4 — Martin Hafskjold Thoresen Initial commit 2 years ago
                                                                                
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
129
130
131
132
133
134
135
136
/// Square root of a usize, rounded down.
fn sqrt_usize(u: usize) -> usize {
    (u as f64).sqrt() as usize
}



/// A column-major matrix.
struct Matrix {
    data: Vec<u8>,
    labels: Vec<char>,
}


fn test() -> Matrix {
    // We have five verts, seven edges, and two faces:
    //          a
    //     1-------2
    //     |\     /|
    //    b| \c d/ |e
    //     |A \ / B|
    //     3---4---5
    //       f   g
    let mut v = Vec::with_capacity(15 * 15);
    // empty set
    for _ in 0..15 { v.push(0); }
    // five verts
    for _ in 0..5 { v.push(1); for _ in 0..14 { v.push(0); } }
    // seven edges
    let indices = [
        (1, 2), // a
        (1, 3), // b
        (1, 4), // c
        (2, 4), // d
        (3, 4), // f
        (2, 5), // e
        (4, 5), // g
    ];
    for &(from, to) in &indices {
        for i in 0..15 { 
            if i == from || i == to { v.push(1); }
            else { v.push(0); } 
        }
    }
    // Two faces
    let indices = [
        (1, 2, 5), // A
        (3, 4, 6), // B
    ];
    let start_vert_ind = 6;
    for &(a, b, c) in &indices {
        let a = a + start_vert_ind;
        let b = b + start_vert_ind;
        let c = c + start_vert_ind;
        for i in 0..15 {
            if i == a || i == b || i == c { v.push(1); }
            else { v.push(0); }
        }
    }
    Matrix { 
        data: v,
        labels: vec!['e', '1', '2', '3', '4', '5', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'A', 'B'],
    }
}


/// Prints out the matrix with the labels given.
fn print(matrix: &Matrix) {
    let size = sqrt_usize(matrix.data.len());
    print!(" |");
    for i in 0..size {
        print!("{} ", matrix.labels[i]);
    }
    println!();
    print!("-");
    for i in 0..size {
        print!("--");
    }
    println!();
    for j in 0..size { 
        print!("{}|", matrix.labels[j]);
        for i in 0..size {
            let n = matrix.data[i * size + j];
            let c = if n == 1 { matrix.labels[j] } else { '.' };
            print!("{} ", c);
        }
        println!();
    }
}

/// Return the largest index i s.t. matrix[column][i] == 1.
fn low(matrix: &Matrix, column: usize) -> Option<usize> {
    let size = sqrt_usize(matrix.data.len());
    let start_i = column * size;
    let end_i = (column + 1) * size;
    for i in (start_i..end_i).rev() {
        if matrix.data[i] == 1 { return Some(i % size); }
    }
    return None
}

fn column_reduction_ex(matrix: &mut Matrix) {
    let m = sqrt_usize(matrix.data.len());
    'column: for j in 0..m {
        let j_low = low(&matrix, j);
        if j_low.is_none() { continue; }
        let mut j_low = j_low.unwrap();
        for l in (0..j).rev() {
            let l_low = match low(&matrix, l) {
                None => continue,
                Some(l) => l,
            };
            // if l_low < j_low { continue 'outer; }
            if matrix.data[j * m + l_low] == 1 {
                // Add l into j:
                for i in 0..m {
                    matrix.data[j * m + i] ^= matrix.data[l * m + i];
                }
                j_low = match low(&matrix, j) {
                    Some(l) => l,
                    None => continue 'column
                };
            }
        }
    }

}


fn main() {
    let mut m = test();
    print(&m);
    println!("\n\n");
    column_reduction_ex(&mut m);
    print(&m);
}