− #[derive(Debug)]
− pub struct BoolGrid {
− width: usize,
− content: Vec<bool>,
− }
−
− impl BoolGrid {
− pub fn new() -> Self {
− Self {
− width: 0,
− content: Vec::new(),
− }
− }
−
− pub fn column(&self, x: usize) -> BoolColumn<'_> {
− BoolColumn::new(self, x)
− }
−
− pub fn row(&self, y: usize) -> BoolRow<'_> {
− BoolRow::new(self, y)
− }
−
− pub fn set_transitive(
− &mut self,
− x: usize,
− y: usize,
− ) -> Vec<(usize, usize)> {
− use std::collections::VecDeque;
− let mut q = VecDeque::new();
− q.push_back((x, y));
− let mut result = Vec::new();
− while let Some((x, y)) = q.pop_front() {
− let t = &mut self[(x, y)];
− if !*t {
− *t = true;
− result.push((x, y));
− for (c, v) in self.row(x).enumerate() {
− if v {
− q.push_back((c, y));
− }
− }
− for (c, v) in self.column(y).enumerate() {
− if v {
− q.push_back((x, c));
− }
− }
− }
− }
− result
− }
−
− pub fn compare(&self, x: usize, y: usize) -> Option<std::cmp::Ordering> {
− use std::cmp::Ordering::*;
− if x == y {
− Some(Equal)
− } else {
− match (self[(x, y)], self[(y, x)]) {
− (true, true) => Some(Equal),
− (true, false) => Some(Greater),
− (false, true) => Some(Less),
− (false, false) => None,
− }
− }
− }
− }
−
− #[test]
− fn transitive_works() {
− let mut grid = BoolGrid::new();
− grid.set_transitive(1, 2);
− grid.set_transitive(14, 15);
− grid.set_transitive(2, 3);
− grid.set_transitive(10, 11);
− grid.set_transitive(4, 5);
− grid.set_transitive(12, 13);
− grid.set_transitive(15, 16);
− grid.set_transitive(6, 7);
− grid.set_transitive(13, 14);
− grid.set_transitive(5, 6);
− grid.set_transitive(9, 10);
− grid.set_transitive(11, 12);
− grid.set_transitive(8, 9);
− for x in 0..=16 {
− for y in 0..=16 {
− assert_eq!(
− x < y
− && [1..=3, 4..=7, 8..=16]
− .into_iter()
− .any(|i| i.contains(&x) && i.contains(&y)),
− grid[(x, y)]
− );
− }
− }
− }
−
− #[test]
− fn row_iterator() {
− let mut grid = BoolGrid::new();
− grid[(5, 4)] = true;
− let row: Vec<_> = grid.row(4).collect();
− assert_eq!(&row[..], &[false, false, false, false, false, true]);
− assert!(grid.row(5).all(|v| !v));
− }
−
− #[test]
− fn col_iterator() {
− let mut grid = BoolGrid::new();
− grid[(5, 4)] = true;
− let row: Vec<_> = grid.column(5).collect();
− assert_eq!(&row[..], &[false, false, false, false, true]);
− assert!(grid.column(6).all(|v| !v));
− }
−
− #[test]
− fn test_compare() {
− use std::cmp::Ordering::*;
− let mut grid = BoolGrid::new();
− let mut set = Vec::new();
− set.extend(grid.set_transitive(1, 2).into_iter());
− set.extend(grid.set_transitive(2, 3).into_iter());
− assert_eq!(grid.compare(3, 4), None);
− assert_eq!(grid.compare(1, 3), Some(Greater));
− assert_eq!(grid.compare(3, 1), Some(Less));
− assert_eq!(grid.compare(2, 2), Some(Equal));
− assert!(set.iter().all(|(a, b)| a < b));
− }
−
− #[test]
− fn test_transitive_bug() {
− let mut grid = BoolGrid::new();
− let mut set = Vec::new();
− for (a, b) in [(1, 4), (4, 2), (8, 4), (3, 4), (4, 7), (4, 6), (4, 12)] {
− set.extend(grid.set_transitive(a, b));
− }
− for (a, b) in set {
− assert!(a != 11);
− assert!(b != 11);
− }
− for x in 1..=12 {
− assert!(!grid[(11, x)]);
− assert!(!grid[(x, 11)]);
− }
− }
−
− #[test]
− fn test_rows_cols_bug() {
− use std::collections::HashSet;
− let mut grid = BoolGrid::new();
− let mut set = HashSet::new();
− grid.set_transitive(1, 4);
− set.insert((1, 4));
− for x in 0..=5 {
− for y in 0..=5 {
− assert_eq!(grid[(x, y)], (x, y) == (1, 4));
− }
− }
− let c: Vec<_> = grid.column(3).collect();
− println!("column 3: {:?}", c);
− for x in 0..12 {
− for (y, v) in grid.column(x).enumerate() {
− if v != set.contains(&(x, y)) {
− panic!("x: {}, y: {}, v: {}", x, y, v);
− }
− }
− }
− }
−
− static OFF_GRID: bool = false;
−
− impl std::ops::Index<(usize, usize)> for BoolGrid {
− type Output = bool;
− fn index(&self, (x, y): (usize, usize)) -> &bool {
− if x >= self.width {
− return &OFF_GRID;
− }
− let ix = self.width * y + x;
− if ix >= self.content.len() {
− return &OFF_GRID;
− }
− <Vec<bool> as std::ops::Index<usize>>::index(&self.content, ix)
− }
− }
−
− impl std::ops::IndexMut<(usize, usize)> for BoolGrid {
− fn index_mut(&mut self, (x, y): (usize, usize)) -> &mut bool {
− let height = self.content.len() / self.width.max(1);
− let rq_width = self.width.max(x + 1);
− let rq_height = (y + 1).max(height);
− if (self.width, height) != (rq_width, rq_height) {
− struct Resize {
− old_content: Vec<bool>,
− old_width: usize,
− new_width: usize,
− new_height: usize,
− x: usize,
− y: usize,
− }
− impl Resize {
− fn new(
− content: Vec<bool>,
− old_width: usize,
− new_width: usize,
− new_height: usize,
− ) -> Self {
− Self {
− old_content: content,
− old_width,
− new_width,
− new_height,
− x: 0,
− y: 0,
− }
− }
− }
− impl Iterator for Resize {
− type Item = bool;
− fn next(&mut self) -> Option<bool> {
− if self.y >= self.new_height {
− return None;
− }
− let result = if self.x >= self.old_width {
− Some(false)
− } else {
− let ix = self.y * self.old_width + self.x;
− if ix >= self.old_content.len() {
− Some(false)
− } else {
− Some(self.old_content[ix])
− }
− };
− let z = if self.x < self.new_width - 1 {
− (self.x + 1, self.y)
− } else {
− (0, self.y + 1)
− };
− self.x = z.0;
− self.y = z.1;
− result
− }
− fn size_hint(&self) -> (usize, Option<usize>) {
− let r =
− self.new_width * (self.new_height - self.y) - self.x;
− (r, Some(r))
− }
− }
− self.content = Resize::new(
− std::mem::take(&mut self.content),
− self.width,
− rq_width,
− rq_height,
− )
− .collect();
− self.width = rq_width;
− }
− <Vec<bool> as std::ops::IndexMut<usize>>::index_mut(
− &mut self.content,
− self.width * y + x,
− )
− }
− }
−
− pub struct BoolColumn<'a> {
− grid: &'a BoolGrid,
− ix: usize,
− }
−
− impl<'a> BoolColumn<'a> {
− fn new(grid: &'a BoolGrid, x: usize) -> Self {
− if x < grid.width {
− Self { grid, ix: x }
− } else {
− Self {
− grid,
− ix: usize::MAX,
− }
− }
− }
− }
−
− impl<'a> Iterator for BoolColumn<'a> {
− type Item = bool;
− fn next(&mut self) -> Option<bool> {
− if self.ix < self.grid.content.len() {
− let result = self.grid.content[self.ix];
− self.ix += self.grid.width;
− Some(result)
− } else {
− None
− }
− }
− fn size_hint(&self) -> (usize, Option<usize>) {
− let len = self.grid.content.len();
− let result = (len - self.ix) / len;
− (result, Some(result))
− }
− }
−
− pub struct BoolRow<'a> {
− grid: &'a BoolGrid,
− ix: usize,
− end: usize,
− }
−
− impl<'a> BoolRow<'a> {
− fn new(grid: &'a BoolGrid, y: usize) -> Self {
− Self {
− grid,
− ix: y * grid.width,
− end: (y + 1) * grid.width,
− }
− }
− }
−
− impl<'a> Iterator for BoolRow<'a> {
− type Item = bool;
− fn next(&mut self) -> Option<bool> {
− if self.ix < self.end && self.ix < self.grid.content.len() {
− let result = self.grid.content[self.ix];
− self.ix += 1;
− Some(result)
− } else {
− None
− }
− }
− fn size_hint(&self) -> (usize, Option<usize>) {
− let result = self.end - self.ix;
− (result, Some(result))
− }
− }