/// 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, labels: Vec, } 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 { 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); }