sokoban-elements 0.2.0

use itertools::Itertools;

use super::edges::{HorizontalEdge, VerticalEdge};
use super::errors::{BoardSyntaxError, BoardSyntaxErrorKind};
use crate::rle::Rle;
use crate::utilities::is_blank;
use crate::{Tessellation, TileKind};

/// row-major: outer `Vec` is rows (`y`), inner is columns (`x`). Origin `(0, 0)` is top-left, `y`
/// grows downward.
pub(super) type ParsedBoard = Vec<Vec<TileKind>>;

pub struct ParserCommon;

impl ParserCommon {
    pub const BOX: char = '$';
    pub const BOX_ALT1: char = 'b';
    pub const BOX_ON_GOAL: char = '*';
    pub const BOX_ON_GOAL_ALT1: char = 'B';
    pub const FLOOR: char = ' ';
    pub const VISIBLE_FLOOR: char = '-';
    pub const VISIBLE_FLOOR_ALT1: char = '_';
    pub const GOAL: char = '.';
    pub const GOAL_ALT1: char = 'o';
    pub const PUSHER: char = '@';
    pub const PUSHER_ALT1: char = 'p';
    pub const PUSHER_ALT2: char = 'm';
    pub const PUSHER_ON_GOAL: char = '+';
    pub const PUSHER_ON_GOAL_ALT1: char = 'P';
    pub const PUSHER_ON_GOAL_ALT2: char = 'M';
    pub const WALL: char = '#';
    // pub const PUSHER_ON_BOX: char = '!';

    pub const RLE_GROUP_START: char = Rle::GROUP_START;
    pub const RLE_GROUP_END: char = Rle::GROUP_END;
    pub const RLE_EOL: char = Rle::EOL;

    /// Checks if character represents board cell having pusher on it
    pub const fn is_pusher(ch: char) -> bool {
        (ch == Self::PUSHER)
            || (ch == Self::PUSHER_ALT1)
            || (ch == Self::PUSHER_ALT2)
            || (ch == Self::PUSHER_ON_GOAL)
            || (ch == Self::PUSHER_ON_GOAL_ALT1)
            || (ch == Self::PUSHER_ON_GOAL_ALT2)
    }

    /// Checks if character represents board cell having box on it
    pub const fn is_box(ch: char) -> bool {
        (ch == Self::BOX)
            || (ch == Self::BOX_ALT1)
            || (ch == Self::BOX_ON_GOAL)
            || (ch == Self::BOX_ON_GOAL_ALT1)
    }

    /// Checks if character represents board cell having goal on it
    pub const fn is_goal(ch: char) -> bool {
        (ch == Self::GOAL)
            || (ch == Self::GOAL_ALT1)
            || (ch == Self::BOX_ON_GOAL)
            || (ch == Self::BOX_ON_GOAL_ALT1)
            || (ch == Self::PUSHER_ON_GOAL)
            || (ch == Self::PUSHER_ON_GOAL_ALT1)
            || (ch == Self::PUSHER_ON_GOAL_ALT2)
    }

    /// Checks if character represents empty floor board cell
    pub const fn is_empty_floor(ch: char) -> bool {
        (ch == Self::FLOOR) || (ch == Self::VISIBLE_FLOOR) || (ch == Self::VISIBLE_FLOOR_ALT1)
    }

    /// Checks if character represents wall board cell
    pub const fn is_wall(ch: char) -> bool { ch == Self::WALL }
}

/// Tests if `input` contains only characters that are valid in game board strings.
///
/// This method doesn't test if `input` is a valid game board. The only way to do that is
/// to actually [`parse`](GameBoard::parsed()) it.
pub(crate) fn is_board_line(line: &str) -> bool {
    !line
        .chars()
        .all(|c| c.is_whitespace() || c.is_ascii_digit())
        && line.chars().all(|c| {
            c.is_whitespace()
                || c.is_ascii_digit()
                || ParserCommon::is_pusher(c)
                || ParserCommon::is_box(c)
                || ParserCommon::is_goal(c)
                || ParserCommon::is_empty_floor(c)
                || ParserCommon::is_wall(c)
                || (c == ParserCommon::RLE_EOL)
                || (c == ParserCommon::RLE_GROUP_START)
                || (c == ParserCommon::RLE_GROUP_END)
        })
}

/// Asserts the board data invariant that all rows are of equal length.
///
/// Board editing primitives rely on it and are only ever reachable through
/// [`GameBoard`](crate::GameBoard), which upholds it.
pub(super) fn assert_width_normalized(body: &ParsedBoard) {
    assert!(
        body.iter().map(std::vec::Vec::len).all_equal(),
        "expects width-normalized board data"
    );
}

/// Collapses board data that has rows but no columns into the empty board.
///
/// Editing primitives are free to produce rows of zero length on their way to a final result (ie.
/// removing more columns than there are, or adding rows to an empty board). Such data is not a
/// valid [`GameBoard`](crate::GameBoard): a board with no columns is the empty board. See
/// `GameBoard` docs.
///
/// Board data is width-normalized, so testing the first row is enough.
pub(super) fn normalize_dimensions(body: &mut ParsedBoard) {
    assert_width_normalized(body);

    if body.first().is_some_and(Vec::is_empty) {
        body.clear();
    }
}

/// Extends board data to at least `width` columns and `height` rows with
/// [`TileKind::Floor`](crate::TileKind::Floor).
///
/// Callers pass targets already maximized against the current size, so rows are never truncated.
/// The empty board is grown too: it has no rows to widen, and every row it then gains is built at
/// the wanted width.
///
/// This needs no [`BoardResizer`] and no [`Tessellation`] dispatch. Only the Top and Left edges
/// shift existing content, so only they can break tile geometry; growing right and down is
/// dimension-local in every tessellation and never needs a perpendicular padding line.
pub(super) fn grown(body: &mut ParsedBoard, width: usize, height: usize) {
    assert_width_normalized(body);

    for row in body.iter_mut() {
        row.resize(width, TileKind::Floor);
    }

    let missing_rows = height.saturating_sub(body.len());
    body.extend(std::iter::repeat_n(vec![TileKind::Floor; width], missing_rows));
}

pub(super) trait BoardParser {
    fn parse(board: &str) -> Result<ParsedBoard, BoardSyntaxError> {
        if is_blank(board) {
            return Ok(ParsedBoard::new());
        }

        let lines: Vec<String> = match Rle::decode(board, false) {
            Ok(v) => v,
            Err(e) => {
                return Err(BoardSyntaxError::new_with_source(
                    BoardSyntaxErrorKind::RleDecodingFailed,
                    Some(e),
                ));
            }
        }
        .trim_start_matches('\n')
        .trim_end()
        .split('\n')
        .map(str::to_owned)
        .collect();
        let max_width = lines.iter().map(|s| s.chars().count()).max().unwrap_or(0);

        // A board with no columns is the empty board. Reachable for input that is not blank, but
        // RLE-decodes to nothing, ie. "|" or "3 ". No character validation is skipped here:
        // `max_width` of zero means every decoded line was empty.
        if max_width == 0 {
            return Ok(ParsedBoard::new());
        }

        let mut body: ParsedBoard = Vec::with_capacity(lines.len());
        for (row_idx, line) in lines.iter().enumerate() {
            let mut row: Vec<TileKind> = Vec::with_capacity(max_width);
            for (col_idx, ch) in line.chars().enumerate() {
                row.push(Self::tile_kind_from_char(ch, row_idx, col_idx)?);
            }
            // Board data is always width-normalized: shorter rows are padded with floor tiles. See
            // `GameBoard` docs.
            row.resize(max_width, TileKind::Floor);
            body.push(row);
        }

        Ok(body)
    }

    fn tile_kind_from_char(
        c: char, row_idx: usize, col_idx: usize,
    ) -> Result<TileKind, BoardSyntaxError> {
        if c == ParserCommon::BOX || c == ParserCommon::BOX_ALT1 {
            Ok(TileKind::Box)
        } else if c == ParserCommon::BOX_ON_GOAL || c == ParserCommon::BOX_ON_GOAL_ALT1 {
            Ok(TileKind::BoxOnGoal)
        } else if c == ParserCommon::FLOOR
            || c == ParserCommon::VISIBLE_FLOOR
            || c == ParserCommon::VISIBLE_FLOOR_ALT1
        {
            Ok(TileKind::Floor)
        } else if c == ParserCommon::GOAL || c == ParserCommon::GOAL_ALT1 {
            Ok(TileKind::Goal)
        } else if c == ParserCommon::PUSHER
            || c == ParserCommon::PUSHER_ALT1
            || c == ParserCommon::PUSHER_ALT2
        {
            Ok(TileKind::Pusher)
        } else if c == ParserCommon::PUSHER_ON_GOAL
            || c == ParserCommon::PUSHER_ON_GOAL_ALT1
            || c == ParserCommon::PUSHER_ON_GOAL_ALT2
        {
            Ok(TileKind::PusherOnGoal)
        } else if c == ParserCommon::WALL {
            Ok(TileKind::Wall)
        } else {
            Err(BoardSyntaxError::new(BoardSyntaxErrorKind::IllegalCharacter {
                input: c,
                x:     col_idx,
                y:     row_idx,
            }))
        }
    }
}

pub(super) trait BoardPrinter {
    /// # Todo
    ///
    /// If there are empty rows or empty columns in the board, they should always be printed using
    /// visible (non-blank) floor character! Check that this also applies to all types currently
    /// implementing this trait. Can it be enforced in implementors? At least document what
    /// implementors of this method are expected to do.
    fn print(parsed_board: &ParsedBoard, use_visible_floor: bool) -> String {
        let retv: String = parsed_board
            .iter()
            .map(|tiles_vec| -> String {
                tiles_vec
                    .iter()
                    .map(|tile| Self::tile_kind_to_char(*tile, use_visible_floor))
                    .collect()
            })
            .map(|s| -> String {
                if use_visible_floor {
                    s
                } else {
                    s.trim_end_matches(ParserCommon::FLOOR).to_string()
                }
            })
            .collect::<Vec<String>>()
            .join("\n");

        retv
    }

    fn tile_kind_to_char(tile: TileKind, use_visible_floor: bool) -> char {
        match tile {
            TileKind::Box => ParserCommon::BOX,
            TileKind::BoxOnGoal => ParserCommon::BOX_ON_GOAL,
            TileKind::Pusher => ParserCommon::PUSHER,
            TileKind::PusherOnGoal => ParserCommon::PUSHER_ON_GOAL,
            TileKind::Goal => ParserCommon::GOAL,
            TileKind::Wall => ParserCommon::WALL,
            TileKind::Floor => {
                if use_visible_floor {
                    ParserCommon::VISIBLE_FLOOR
                } else {
                    ParserCommon::FLOOR
                }
            }
        }
    }
}

#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub(super) struct BoardRect {
    pub(super) left:   usize,
    pub(super) top:    usize,
    pub(super) width:  usize,
    pub(super) height: usize,
}

fn to_i64(value: usize) -> i64 { i64::try_from(value).unwrap_or(i64::MAX) }

fn copied_rect(
    body: &ParsedBoard, source: BoardRect, destination_left: usize, destination_top: usize,
) -> ParsedBoard {
    assert_width_normalized(body);
    let body_width = body.first().map_or(0, Vec::len);
    assert!(source.left.saturating_add(source.width) <= body_width);
    assert!(source.top.saturating_add(source.height) <= body.len());

    if source.width == 0 || source.height == 0 {
        return ParsedBoard::new();
    }

    let destination_width = destination_left.saturating_add(source.width);
    let destination_height = destination_top.saturating_add(source.height);
    let mut destination = vec![vec![TileKind::Floor; destination_width]; destination_height];

    for (source_row, destination_row) in body
        .iter()
        .skip(source.top)
        .take(source.height)
        .zip(destination.iter_mut().skip(destination_top))
    {
        destination_row[destination_left..destination_left + source.width]
            .copy_from_slice(&source_row[source.left..source.left + source.width]);
    }

    destination
}

fn best_crop_offset(tessellation: Tessellation, source: BoardRect) -> (usize, usize) {
    let mut best: Option<(usize, usize, usize)> = None;

    for (extra_left, extra_top) in [(0_usize, 0_usize), (1, 0), (0, 1), (1, 1)] {
        let dx = to_i64(extra_left) - to_i64(source.left);
        let dy = to_i64(extra_top) - to_i64(source.top);
        if !tessellation.is_rigid_translation(dx, dy) {
            continue;
        }

        let area = source
            .width
            .saturating_add(extra_left)
            .saturating_mul(source.height.saturating_add(extra_top));
        if best.is_none_or(|(_, _, best_area)| area < best_area) {
            best = Some((extra_left, extra_top, area));
        }
    }

    // Every supported integer translation lattice has period at most two on each axis.
    best.map_or((0, 0), |(extra_left, extra_top, _)| (extra_left, extra_top))
}

/// Resizes boards in one batch while preserving the tessellation's tile geometry.
pub(super) trait BoardResizer {
    const TESSELLATION: Tessellation;

    fn width(body: &ParsedBoard) -> usize {
        assert_width_normalized(body);
        if body.is_empty() { 0 } else { body[0].len() }
    }

    fn height(body: &ParsedBoard) -> usize {
        assert_width_normalized(body);

        body.len()
    }

    fn add_rows_top(body: &mut ParsedBoard, count: usize) {
        let source = BoardRect {
            left:   0,
            top:    0,
            width:  Self::width(body),
            height: Self::height(body),
        };
        let extra_left = usize::from(!Self::TESSELLATION.is_rigid_translation(0, to_i64(count)));
        *body = copied_rect(body, source, extra_left, count);
    }

    fn add_rows_bottom(body: &mut ParsedBoard, count: usize) {
        let width = Self::width(body);
        body.extend(std::iter::repeat_n(vec![TileKind::Floor; width], count));
    }

    fn add_columns_left(body: &mut ParsedBoard, count: usize) {
        let source = BoardRect {
            left:   0,
            top:    0,
            width:  Self::width(body),
            height: Self::height(body),
        };
        let extra_top = usize::from(!Self::TESSELLATION.is_rigid_translation(to_i64(count), 0));
        *body = copied_rect(body, source, count, extra_top);
    }

    fn add_columns_right(body: &mut ParsedBoard, count: usize) {
        assert_width_normalized(body);
        let new_width = Self::width(body).saturating_add(count);
        for row in body {
            row.resize(new_width, TileKind::Floor);
        }
    }

    fn remove_rows_top(body: &mut ParsedBoard, count: usize) {
        let count = count.min(Self::height(body));
        if count == 0 {
            return;
        }
        let source = BoardRect {
            left:   0,
            top:    count,
            width:  Self::width(body),
            height: Self::height(body) - count,
        };
        let extra_left = usize::from(!Self::TESSELLATION.is_rigid_translation(0, -to_i64(count)));
        *body = copied_rect(body, source, extra_left, 0);
    }

    fn remove_rows_bottom(body: &mut ParsedBoard, count: usize) {
        assert_width_normalized(body);
        body.truncate(body.len().saturating_sub(count));
    }

    fn remove_columns_left(body: &mut ParsedBoard, count: usize) {
        let width = Self::width(body);
        let count = count.min(width);
        if count == 0 {
            return;
        }
        let source = BoardRect {
            left:   count,
            top:    0,
            width:  width.saturating_sub(count),
            height: Self::height(body),
        };
        let extra_top = usize::from(!Self::TESSELLATION.is_rigid_translation(-to_i64(count), 0));
        *body = copied_rect(body, source, 0, extra_top);
    }

    fn remove_columns_right(body: &mut ParsedBoard, count: usize) {
        assert_width_normalized(body);
        let new_width = Self::width(body).saturating_sub(count);
        for row in body {
            row.truncate(new_width);
        }
    }

    fn add_rows(body: &mut ParsedBoard, edge: HorizontalEdge, count: usize) -> usize {
        if Self::width(body) == 0 || count == 0 {
            return 0;
        }
        match edge {
            HorizontalEdge::Top => Self::add_rows_top(body, count),
            HorizontalEdge::Bottom => Self::add_rows_bottom(body, count),
        }
        count
    }

    /// Removing more rows than board has removes all of them.
    fn remove_rows(body: &mut ParsedBoard, edge: HorizontalEdge, count: usize) -> usize {
        let count = count.min(Self::height(body));
        if count == 0 {
            return 0;
        }
        match edge {
            HorizontalEdge::Top => Self::remove_rows_top(body, count),
            HorizontalEdge::Bottom => Self::remove_rows_bottom(body, count),
        }
        count
    }

    fn add_columns(body: &mut ParsedBoard, edge: VerticalEdge, count: usize) -> usize {
        if Self::height(body) == 0 || count == 0 {
            return 0;
        }
        match edge {
            VerticalEdge::Left => Self::add_columns_left(body, count),
            VerticalEdge::Right => Self::add_columns_right(body, count),
        }
        count
    }

    /// Removing more columns than board has removes all of them, leaving rows of zero length.
    /// [`GameBoard`](crate::GameBoard) collapses those into the empty board.
    fn remove_columns(body: &mut ParsedBoard, edge: VerticalEdge, count: usize) -> usize {
        let count = count.min(Self::width(body));
        if count == 0 {
            return 0;
        }
        match edge {
            VerticalEdge::Left => Self::remove_columns_left(body, count),
            VerticalEdge::Right => Self::remove_columns_right(body, count),
        }
        count
    }

    fn crop(body: &mut ParsedBoard, source: BoardRect) {
        let (extra_left, extra_top) = best_crop_offset(Self::TESSELLATION, source);
        *body = copied_rect(body, source, extra_left, extra_top);
    }

    fn trim(body: &mut ParsedBoard) {
        assert_width_normalized(body);

        let mut left = Self::width(body);
        let mut top = Self::height(body);
        let mut right = 0;
        let mut bottom = 0;
        let mut found = false;

        for (y, row) in body.iter().enumerate() {
            for (x, tile) in row.iter().enumerate() {
                if !tile.is_empty_floor() {
                    found = true;
                    left = left.min(x);
                    top = top.min(y);
                    right = right.max(x);
                    bottom = bottom.max(y);
                }
            }
        }

        if !found {
            body.clear();
            return;
        }

        Self::crop(
            body,
            BoardRect {
                left,
                top,
                width: right - left + 1,
                height: bottom - top + 1,
            },
        );
    }
}

#[cfg(test)]
mod tests {
    use std::collections::{HashMap, HashSet};

    use indoc::indoc;

    use super::*;
    use crate::{GameBoard, Size2D};

    /// Board data invariant: all rows have exactly `width()` tiles and a board with no columns is
    /// the empty board.
    fn assert_invariant(board: &GameBoard) {
        assert!(
            board.data.iter().all(|row| row.len() == board.width()),
            "rows are not width-normalized: {:?}",
            board.data
        );
        assert_eq!(
            board.width() == 0,
            board.height() == 0,
            "board is {}x{}, but a board with no columns must have no rows",
            board.width(),
            board.height()
        );
        assert_eq!(board.iter().count(), board.width() * board.height());
    }

    fn assert_empty(board: &GameBoard) {
        assert_invariant(board);
        assert_eq!(board.width(), 0);
        assert_eq!(board.height(), 0);
        assert!(board.data.is_empty());
        assert!(board.iter().next().is_none());
    }

    fn content_signature(board: &GameBoard) -> Vec<(usize, usize, TileKind)> {
        let non_floor: Vec<_> = board
            .iter()
            .filter(|(_, tile)| *tile != TileKind::Floor)
            .collect();
        let min_x = non_floor.iter().map(|((x, _), _)| *x).min().unwrap_or(0);
        let min_y = non_floor.iter().map(|((_, y), _)| *y).min().unwrap_or(0);
        non_floor
            .into_iter()
            .map(|((x, y), tile)| (x - min_x, y - min_y, tile))
            .collect()
    }

    fn adjacency_signature(
        board: &GameBoard, markers: &[TileKind],
    ) -> Vec<(TileKind, HashSet<TileKind>)> {
        markers
            .iter()
            .map(|marker| {
                let (position, _) = board.iter().find(|(_, tile)| *tile == *marker).unwrap();
                let neighbors = board
                    .tessellation()
                    .known_directions()
                    .iter()
                    .filter_map(|direction| {
                        board.tessellation().neighbor(
                            position.0,
                            position.1,
                            *direction,
                            board.width(),
                            board.height(),
                        )
                    })
                    .map(|neighbor| board[neighbor])
                    .filter(|tile| *tile != TileKind::Floor)
                    .collect();
                (*marker, neighbors)
            })
            .collect()
    }

    /// The default `BoardParser::parse` / `BoardPrinter::print` bodies, exercised through
    /// Sokoban - the tessellation that overrides nothing.
    mod test_parsing {
        use super::*;

        #[test]
        fn it_carefully_preserves_original_newlines() -> Result<(), BoardSyntaxError> {
            let src: String = [
                " ##########\n    \n\n",
                " ## @ *   #\n\n",
                "##  $ ####\n\n",
                "# $.+ #\n\n",
                "#######\n\n",
            ]
            .join("");

            let result = indoc! {"-##########
                              -----------
                              -----------
                              -##-@-*---#
                              -----------
                              ##--$-####-
                              -----------
                              #-$.+-#----
                              -----------
                              #######----"};

            let board = GameBoard::parsed(&src, Tessellation::Sokoban)?;
            assert_eq!(board.width(), 11);
            assert_eq!(board.height(), 10);
            assert_eq!(board.printed(true), result);

            Ok(())
        }

        #[test]
        fn it_correctly_parses_board_with_internal_blank_rows() -> Result<(), BoardSyntaxError> {
            // ```
            // ::   The first and the last non-empty square in each row  ::
            // ::   must be a wall or a box on a goal. An empty interior ::
            // ::   row is written with at least one "-" or "_".         ::
            // ```
            //
            // Notice that our parser is correct even without that one "-" or "_"

            let src1: String = [
                " ##########\n    \n",
                " ## @ *   #\n",
                "##  $ ####\n",
                "# $.+ #\n",
                "#######\n",
            ]
            .join("");

            let src2: String = [
                " ##########\n  - \n",
                " ## @ *   #\n",
                "##  $ ####\n",
                "# $.+ #\n",
                "#######\n",
            ]
            .join("");

            let result = indoc! {"-##########
                              -----------
                              -##-@-*---#
                              ##--$-####-
                              #-$.+-#----
                              #######----"};

            for src in [src1, src2] {
                let board = GameBoard::parsed(&src, Tessellation::Sokoban)?;
                assert_eq!(board.width(), 11);
                assert_eq!(board.height(), 6);
                assert_eq!(board.printed(true), result);
            }

            Ok(())
        }

        #[test]
        fn it_parses_rle_encoded_board() -> Result<(), BoardSyntaxError> {
            // ```
            // ::   The first and the last non-empty square in each row  ::
            // ::   must be a wall or a box on a goal. An empty interior ::
            // ::   row is written with at least one "-" or "_".         ::
            // ```
            //
            // Notice that our parser can go even without that on "-" or "_"

            let src1: String = [
                " ##########   |",
                " ## @ *   #|",
                "##  $ ####|",
                "# $.+ #|||",
                "#######   |",
            ]
            .join("");

            let src2: String = [
                " ##########   |",
                " ## @ *   #|",
                "##  $ ####|",
                "# $.+ #|||",
                "#######   |",
            ]
            .join("");

            let result = indoc! {"-##########---
                              -##-@-*---#---
                              ##--$-####----
                              #-$.+-#-------
                              --------------
                              --------------
                              #######-------"};

            for src in [src1, src2] {
                let board = GameBoard::parsed(&src, Tessellation::Sokoban)?;
                assert_eq!(board.width(), 14);
                assert_eq!(board.height(), 7);
                assert_eq!(board.printed(true), result);
            }

            Ok(())
        }
    }

    /// Return values of the `BoardResizer` entry points: additions apply `count` exactly,
    /// removals saturate at what is available.
    mod test_resizing {
        use super::*;

        #[test]
        fn top_and_left_resizing_applies_the_exact_count() {
            for tessellation in Tessellation::ALL {
                let mut rows = GameBoard::new(5, 5, tessellation);
                assert_eq!(rows.remove_rows(HorizontalEdge::Top, 1), 1, "{tessellation:?}");

                let mut columns = GameBoard::new(5, 5, tessellation);
                assert_eq!(columns.add_columns(VerticalEdge::Left, 1), 1, "{tessellation:?}");
            }
        }

        #[test]
        fn bottom_and_right_resizing_applies_the_exact_available_count() {
            let mut board = GameBoard::new(5, 5, Tessellation::Octoban);
            assert_eq!(board.add_rows(HorizontalEdge::Bottom, 1), 1);
            assert_eq!(board.add_columns(VerticalEdge::Right, 3), 3);
            assert_eq!(board.remove_rows(HorizontalEdge::Bottom, 2), 2);
            assert_eq!(board.remove_columns(VerticalEdge::Right, 42), 8);
        }

        #[test]
        fn saturated_removal_does_not_pad_an_empty_result() {
            for tessellation in Tessellation::ALL {
                let mut rows = GameBoard::new(3, 2, tessellation);
                assert_eq!(rows.remove_rows(HorizontalEdge::Top, 42), 2);
                assert_empty(&rows);

                let mut columns = GameBoard::new(3, 2, tessellation);
                assert_eq!(columns.remove_columns(VerticalEdge::Left, 42), 3);
                assert_empty(&columns);
            }
        }
    }

    /// A Top or Left edit shifts existing content, so on a parity-sensitive tiling it must be
    /// compensated with one perpendicular padding line. Trioban and Octoban share the rule -
    /// `is_rigid_translation` is `(dx + dy) % 2 == 0` for both - which is why these sweep the
    /// two together rather than living beside either tessellation.
    ///
    /// See `doc/dev-notes/board-geometry-and-transformations.md` sections 6 and 7.
    mod test_parity_padding {
        use super::*;

        #[test]
        fn odd_top_resizing_adds_one_left_column_on_trioban_and_octoban()
        -> Result<(), BoardSyntaxError> {
            let markers = [
                TileKind::Wall,
                TileKind::Pusher,
                TileKind::Box,
                TileKind::Goal,
            ];

            for tessellation in [Tessellation::Trioban, Tessellation::Octoban] {
                let mut added = GameBoard::parsed_from_tiles(&markers, 2, 2, tessellation)?;
                assert_eq!(added.add_rows(HorizontalEdge::Top, 1), 1);
                assert_eq!(added.size(), Size2D::new(3, 3));
                for y in 0..2 {
                    for x in 0..2 {
                        assert_eq!(added[(x + 1, y + 1)], markers[y * 2 + x]);
                    }
                }

                let mut removed = GameBoard::new(2, 3, tessellation);
                for (index, marker) in markers.iter().enumerate() {
                    removed[(index % 2, index / 2 + 1)] = *marker;
                }
                assert_eq!(removed.remove_rows(HorizontalEdge::Top, 1), 1);
                assert_eq!(removed.size(), Size2D::new(3, 2));
                for y in 0..2 {
                    for x in 0..2 {
                        assert_eq!(removed[(x + 1, y)], markers[y * 2 + x]);
                    }
                }
            }

            Ok(())
        }

        #[test]
        fn odd_left_resizing_adds_one_top_row_on_trioban_and_octoban()
        -> Result<(), BoardSyntaxError> {
            let markers = [
                TileKind::Wall,
                TileKind::Pusher,
                TileKind::Box,
                TileKind::Goal,
            ];

            for tessellation in [Tessellation::Trioban, Tessellation::Octoban] {
                let mut added = GameBoard::parsed_from_tiles(&markers, 2, 2, tessellation)?;
                assert_eq!(added.add_columns(VerticalEdge::Left, 1), 1);
                assert_eq!(added.size(), Size2D::new(3, 3));
                for y in 0..2 {
                    for x in 0..2 {
                        assert_eq!(added[(x + 1, y + 1)], markers[y * 2 + x]);
                    }
                }

                let mut removed = GameBoard::new(3, 2, tessellation);
                for (index, marker) in markers.iter().enumerate() {
                    removed[(index % 2 + 1, index / 2)] = *marker;
                }
                assert_eq!(removed.remove_columns(VerticalEdge::Left, 1), 1);
                assert_eq!(removed.size(), Size2D::new(2, 3));
                for y in 0..2 {
                    for x in 0..2 {
                        assert_eq!(removed[(x, y + 1)], markers[y * 2 + x]);
                    }
                }
            }

            Ok(())
        }

        #[test]
        fn even_top_and_left_resizing_needs_no_perpendicular_padding() {
            for tessellation in [Tessellation::Trioban, Tessellation::Octoban] {
                let mut rows = GameBoard::new(3, 2, tessellation);
                assert_eq!(rows.add_rows(HorizontalEdge::Top, 2), 2);
                assert_eq!(rows.size(), Size2D::new(3, 4));

                let mut columns = GameBoard::new(3, 2, tessellation);
                assert_eq!(columns.add_columns(VerticalEdge::Left, 2), 2);
                assert_eq!(columns.size(), Size2D::new(5, 2));
            }
        }

        #[test]
        fn even_batch_differs_from_two_odd_resizes_on_trioban_and_octoban()
        -> Result<(), BoardSyntaxError> {
            let markers = [
                TileKind::Wall,
                TileKind::Pusher,
                TileKind::Box,
                TileKind::Goal,
            ];

            for tessellation in [Tessellation::Trioban, Tessellation::Octoban] {
                let original = GameBoard::parsed_from_tiles(&markers, 2, 2, tessellation)?;
                let mut batched = original.clone();
                let mut sequential = original;

                batched.add_rows(HorizontalEdge::Top, 2);
                sequential.add_rows(HorizontalEdge::Top, 1);
                sequential.add_rows(HorizontalEdge::Top, 1);

                assert_eq!(batched.size(), Size2D::new(2, 4));
                assert_eq!(sequential.size(), Size2D::new(4, 4));
                assert_eq!(content_signature(&batched), content_signature(&sequential));

                let original = GameBoard::parsed_from_tiles(&markers, 2, 2, tessellation)?;
                let mut batched = original.clone();
                let mut sequential = original;
                batched.add_columns(VerticalEdge::Left, 2);
                sequential.add_columns(VerticalEdge::Left, 1);
                sequential.add_columns(VerticalEdge::Left, 1);

                assert_eq!(batched.size(), Size2D::new(4, 2));
                assert_eq!(sequential.size(), Size2D::new(4, 4));
                assert_eq!(content_signature(&batched), content_signature(&sequential));
            }

            Ok(())
        }

        #[test]
        fn perpendicular_padding_depends_on_dimensions_not_content() {
            for tessellation in [Tessellation::Trioban, Tessellation::Octoban] {
                let mut odd_rows = GameBoard::new(3, 2, tessellation);
                let mut even_rows = odd_rows.clone();
                let mut odd_columns = odd_rows.clone();

                odd_rows.add_rows(HorizontalEdge::Top, 1);
                even_rows.add_rows(HorizontalEdge::Top, 2);
                odd_columns.add_columns(VerticalEdge::Left, 1);

                assert_eq!(odd_rows.size(), Size2D::new(4, 3));
                assert_eq!(even_rows.size(), Size2D::new(3, 4));
                assert_eq!(odd_columns.size(), Size2D::new(4, 3));
                assert!(odd_rows.is_blank() && even_rows.is_blank() && odd_columns.is_blank());
            }
        }

        #[test]
        fn odd_resizing_still_compensates_when_one_source_dimension_is_one() {
            for tessellation in [Tessellation::Trioban, Tessellation::Octoban] {
                let mut added_rows = GameBoard::new(3, 1, tessellation);
                added_rows.add_rows(HorizontalEdge::Top, 1);
                assert_eq!(added_rows.size(), Size2D::new(4, 2));

                let mut removed_rows = GameBoard::new(3, 2, tessellation);
                removed_rows.remove_rows(HorizontalEdge::Top, 1);
                assert_eq!(removed_rows.size(), Size2D::new(4, 1));

                let mut added_columns = GameBoard::new(1, 3, tessellation);
                added_columns.add_columns(VerticalEdge::Left, 1);
                assert_eq!(added_columns.size(), Size2D::new(2, 4));

                let mut removed_columns = GameBoard::new(2, 3, tessellation);
                removed_columns.remove_columns(VerticalEdge::Left, 1);
                assert_eq!(removed_columns.size(), Size2D::new(1, 4));
            }
        }

        #[test]
        fn odd_batched_resizing_preserves_adjacency_and_tile_shapes() -> Result<(), BoardSyntaxError>
        {
            let markers = [
                TileKind::Wall,
                TileKind::Pusher,
                TileKind::Box,
                TileKind::Goal,
                TileKind::BoxOnGoal,
                TileKind::PusherOnGoal,
            ];

            for tessellation in [Tessellation::Trioban, Tessellation::Octoban] {
                let original = GameBoard::parsed_from_tiles(&markers, 3, 2, tessellation)?;
                let expected_adjacency = adjacency_signature(&original, &markers);
                let expected_shapes: Vec<_> = original
                    .iter()
                    .map(|((x, y), tile)| (tile, tessellation.tile_shape_from_pos(x, y)))
                    .collect();

                for add_top in [true, false] {
                    let mut resized = original.clone();
                    let operation = if add_top {
                        resized.add_rows(HorizontalEdge::Top, 1);
                        "Top"
                    } else {
                        resized.add_columns(VerticalEdge::Left, 1);
                        "Left"
                    };

                    let actual_shapes: Vec<_> = resized
                        .iter()
                        .filter(|(_, tile)| *tile != TileKind::Floor)
                        .map(|((x, y), tile)| (tile, tessellation.tile_shape_from_pos(x, y)))
                        .collect();
                    assert_eq!(actual_shapes, expected_shapes, "{tessellation:?} {operation}");
                    assert_eq!(
                        adjacency_signature(&resized, &markers),
                        expected_adjacency,
                        "{tessellation:?} {operation}"
                    );
                }
            }

            Ok(())
        }

        #[test]
        fn every_trioban_and_octoban_top_or_left_batch_is_rigid_and_injective() {
            #[derive(Debug, Copy, Clone)]
            enum Operation {
                AddTop,
                RemoveTop,
                AddLeft,
                RemoveLeft,
            }

            let sizes = [(1, 1), (1, 2), (2, 1), (3, 4), (4, 3)];
            let operations = [
                Operation::AddTop,
                Operation::RemoveTop,
                Operation::AddLeft,
                Operation::RemoveLeft,
            ];

            for tessellation in [Tessellation::Trioban, Tessellation::Octoban] {
                for (width, height) in sizes {
                    for count in [1, 2] {
                        for operation in operations {
                            let mut board = GameBoard::new(width, height, tessellation);
                            let mut positions = HashMap::new();

                            for y in 0..height {
                                for x in 0..width {
                                    let mapped = match operation {
                                        Operation::AddTop => Some((x + count % 2, y + count)),
                                        Operation::RemoveTop if y >= count.min(height) => {
                                            Some((x + count.min(height) % 2, y - count.min(height)))
                                        }
                                        Operation::AddLeft => Some((x + count, y + count % 2)),
                                        Operation::RemoveLeft if x >= count.min(width) => {
                                            Some((x - count.min(width), y + count.min(width) % 2))
                                        }
                                        Operation::RemoveTop | Operation::RemoveLeft => None,
                                    };
                                    if let Some(mapped) = mapped {
                                        positions.insert((x, y), mapped);
                                    }
                                }
                            }

                            match operation {
                                Operation::AddTop => {
                                    board.add_rows(HorizontalEdge::Top, count);
                                }
                                Operation::RemoveTop => {
                                    board.remove_rows(HorizontalEdge::Top, count);
                                }
                                Operation::AddLeft => {
                                    board.add_columns(VerticalEdge::Left, count);
                                }
                                Operation::RemoveLeft => {
                                    board.remove_columns(VerticalEdge::Left, count);
                                }
                            }

                            let image: HashSet<_> = positions.values().copied().collect();
                            assert_eq!(image.len(), positions.len());
                            for (source, destination) in &positions {
                                assert_eq!(
                                    tessellation.tile_shape_from_pos(source.0, source.1),
                                    tessellation.tile_shape_from_pos(destination.0, destination.1),
                                    "{tessellation:?} {width}x{height} {operation:?} {count}"
                                );

                                let mapped_neighbors: HashSet<_> = tessellation
                                    .known_directions()
                                    .iter()
                                    .filter_map(|direction| {
                                        tessellation
                                            .neighbor(source.0, source.1, *direction, width, height)
                                    })
                                    .filter_map(|neighbor| positions.get(&neighbor).copied())
                                    .collect();
                                let destination_neighbors: HashSet<_> = tessellation
                                    .known_directions()
                                    .iter()
                                    .filter_map(|direction| {
                                        tessellation.neighbor(
                                            destination.0,
                                            destination.1,
                                            *direction,
                                            board.width(),
                                            board.height(),
                                        )
                                    })
                                    .filter(|neighbor| image.contains(neighbor))
                                    .collect();
                                assert_eq!(
                                    mapped_neighbors, destination_neighbors,
                                    "{tessellation:?} {width}x{height} {operation:?} {count}: \
                                 {source:?} -> {destination:?}"
                                );
                            }
                        }
                    }
                }
            }
        }

        #[test]
        fn resized_trioban_and_octoban_round_trip_through_text() -> Result<(), BoardSyntaxError> {
            let markers = [
                TileKind::Wall,
                TileKind::Pusher,
                TileKind::Box,
                TileKind::Goal,
                TileKind::BoxOnGoal,
                TileKind::PusherOnGoal,
            ];

            for tessellation in [Tessellation::Trioban, Tessellation::Octoban] {
                let mut board = GameBoard::parsed_from_tiles(&markers, 3, 2, tessellation)?;
                board.add_rows(HorizontalEdge::Top, 1);
                board.add_columns(VerticalEdge::Left, 1);

                assert_eq!(GameBoard::parsed(&board.printed(true), tessellation)?, board);
            }

            Ok(())
        }
    }

    /// `BoardResizer::trim` crops all four edges together and picks the smallest rigid anchor,
    /// adding a column when the areas tie.
    mod test_trimming {
        use super::*;

        #[test]
        fn it_trims_empty_outer_rows_and_columns() -> Result<(), BoardSyntaxError> {
            let src = indoc! {"------------------------
                           ------------------------
                           ------#####-------------
                           ------#---#-------------
                           ------#$--#-------------
                           ----###--$##------------
                           ----#--$-$-#------------
                           --###-#-##-#---######---
                           --#---#-##-#####--..#---
                           --#-$--$----------..#---
                           --#####-###-#@##--..#---
                           ------#-----#########---
                           ------#######-----------
                           ------------------------
                           ------------------------
                           ------------------------"};

            let result = indoc! {"----#####----------
                              ----#---#----------
                              ----#$--#----------
                              --###--$##---------
                              --#--$-$-#---------
                              ###-#-##-#---######
                              #---#-##-#####--..#
                              #-$--$----------..#
                              #####-###-#@##--..#
                              ----#-----#########
                              ----#######--------"};

            let mut board = GameBoard::parsed(src, Tessellation::Sokoban)?;

            board.trim();

            assert_eq!(board.printed(true), result);
            assert_eq!(board.width(), 19);
            assert_eq!(board.height(), 11);

            Ok(())
        }

        #[test]
        fn trim_keeps_goal_only_and_pusher_only_edge_lines() -> Result<(), BoardSyntaxError> {
            // Every one of these is the whole board, so nothing may be cropped.
            for source in ["@--#", ".--#", "#--@", "#--.", "@", ".", "$", "*", "+"] {
                let mut board = GameBoard::parsed(source, Tessellation::Sokoban)?;
                board.trim();
                assert_eq!(board.printed(true), source, "{source}");
            }

            let source = indoc! {"--.--
                              -----
                              -###-
                              -----"};
            let result = indoc! {"-.-
                              ---
                              ###"};
            let mut board = GameBoard::parsed(source, Tessellation::Sokoban)?;
            board.trim();
            assert_eq!(board.printed(true), result);

            Ok(())
        }

        #[test]
        fn trim_preserves_tile_shapes_on_parity_sensitive_boards() {
            for tessellation in [Tessellation::Trioban, Tessellation::Octoban] {
                let mut board = GameBoard::new(6, 6, tessellation);
                board[(2, 2)] = TileKind::Wall;
                board[(3, 2)] = TileKind::Box;
                board[(2, 3)] = TileKind::BoxOnGoal;
                board[(4, 3)] = TileKind::Goal;
                board[(3, 4)] = TileKind::Pusher;
                let before: Vec<_> = board
                    .iter()
                    .filter(|(_, tile)| !tile.is_empty_floor())
                    .map(|((x, y), tile)| (tile, tessellation.tile_shape_from_pos(x, y)))
                    .collect();

                board.trim();

                let after: Vec<_> = board
                    .iter()
                    .filter(|(_, tile)| !tile.is_empty_floor())
                    .map(|((x, y), tile)| (tile, tessellation.tile_shape_from_pos(x, y)))
                    .collect();
                assert_eq!(after, before, "{tessellation:?}");
            }
        }

        #[test]
        fn trim_chooses_the_smallest_parity_compensation() {
            for tessellation in [Tessellation::Trioban, Tessellation::Octoban] {
                let mut wide = GameBoard::new(8, 4, tessellation);
                wide[(1, 0)] = TileKind::Wall;
                wide[(5, 1)] = TileKind::BoxOnGoal;
                let wide_shape = tessellation.tile_shape_from_pos(1, 0);
                wide.trim();
                assert_eq!(wide.size(), Size2D::new(6, 2));
                assert_eq!(wide[(1, 0)], TileKind::Wall);
                assert_eq!(tessellation.tile_shape_from_pos(1, 0), wide_shape);

                let mut tall = GameBoard::new(5, 8, tessellation);
                tall[(1, 0)] = TileKind::Wall;
                tall[(2, 4)] = TileKind::BoxOnGoal;
                let tall_shape = tessellation.tile_shape_from_pos(1, 0);
                tall.trim();
                assert_eq!(tall.size(), Size2D::new(2, 6));
                assert_eq!(tall[(0, 1)], TileKind::Wall);
                assert_eq!(tessellation.tile_shape_from_pos(0, 1), tall_shape);

                let mut tied = GameBoard::new(6, 5, tessellation);
                tied[(1, 0)] = TileKind::Wall;
                tied[(3, 2)] = TileKind::BoxOnGoal;
                tied.trim();
                assert_eq!(tied.size(), Size2D::new(4, 3));
                assert_eq!(tied[(1, 0)], TileKind::Wall);
            }
        }
    }
}