twmap 0.3.0

use crate::map::*;
use crate::constants::{
    vanilla_opaque_tables::VANILLA_EXTERNAL_IMAGES,
    ddnet_opaque_tables::DDNET_EXTERNAL_IMAGES
};
use crate::map_checks::PhysicsLayerChecking;
use crate::convert::{To, TryTo};

use image::{RgbaImage, Pixel};
use itertools::Itertools;
use ndarray::{s, Array2};

use std::io;
use std::fs;
use std::path::Path;
use std::convert::TryFrom;
use std::cmp::min;

impl TwMap {
    /// Returns a reference to the specified physics layer, if the map contains it.
    /// Note that every map must have a Game layer to pass the checks.
    pub fn find_physics_layer<T: PhysicsLayerChecking>(&self) -> Option<&T> {
        match self.physics_group().layers.iter()
            .rev()
            .find(|l| l.kind() == T::kind()) {
            None => None,
            Some(l) => T::get(l),
        }
    }
}

impl LayerKind {
    // returns index suitable for checking for duplicates
    fn duplicate_index(&self) -> usize {
        match self {
            LayerKind::Game => 0,
            LayerKind::Front => 1,
            LayerKind::Switch => 2,
            LayerKind::Tele => 3,
            LayerKind::Speedup => 4,
            LayerKind::Tune => 5,
            _ => panic!(), // may exist multiple times
        }
    }
}

impl TwMap {
    pub fn parse_path_unchecked<P: AsRef<Path>>(path: P) -> Result<Self, Error> {
        let path = path.as_ref();

        let metadata = fs::metadata(path)?;
        if metadata.is_file() {
            TwMap::parse_file_unchecked(path)
        }
        else if metadata.is_dir() {
            TwMap::parse_dir_unchecked(path)
        }
        else {
            Err(io::Error::new(io::ErrorKind::InvalidData, "Neither a file nor directory").into())
        }
    }

    /// Parses binary as well as MapDir maps.
    pub fn parse_path<P: AsRef<Path>>(path: P) -> Result<Self, Error> {
        let map = TwMap::parse_path_unchecked(&path)?;
        map.check()?;
        Ok(map)
    }
}

// takes care of multiple physics layers of the same type
impl TwMap {
    /// Removes duplicate physics layers of each type.
    /// Note that every map must have at most 1 physics layer of each type to pass the checks.
    /// The removal process prioritizes removing the layers in front.
    pub fn remove_duplicate_physics_layers(&mut self) -> u16 {
        let mut does_exist = [false; 7];
        let mut removed = 0;

        for group in self.groups.iter_mut().rev() {
            for i in (0..group.layers.len()).rev() {
                let variant = group.layers[i].kind();
                if variant.is_physics_layer() {
                    if does_exist[variant.duplicate_index()] {
                        group.layers.remove(i);
                        removed += 1;
                    }
                    does_exist[variant.duplicate_index()] = true;
                }
            }
        }

        removed
    }
}

fn all_tiles_default<T: AnyTile>(tiles: &Array2<T>) -> bool {
    tiles.iter()
        .all(|t| *t == T::default())
}

impl Layer {
    /// Returns `true` if the layer has no content.
    /// - Tile map layers -> all tiles zeroed
    /// - Quads layers -> no Quads
    /// - Sounds layers -> no SoundSources
    pub fn is_empty(&self) -> bool {
        use Layer::*;
        match self {
            Game(_) => false, // Game layer must not be removed
            Tiles(l) => all_tiles_default(l.tiles.unwrap_ref()),
            Quads(l) => l.quads.is_empty(),
            Front(l) => all_tiles_default(l.tiles.unwrap_ref()),
            Tele(l) => all_tiles_default(l.tiles.unwrap_ref()),
            Speedup(l) => all_tiles_default(l.tiles.unwrap_ref()),
            Switch(l) => all_tiles_default(l.tiles.unwrap_ref()),
            Tune(l) => all_tiles_default(l.tiles.unwrap_ref()),
            Sounds(l) => l.sources.is_empty(),
            Invalid(_) => false,
        }
    }
}

impl TwMap {
    /// Combination of every other `remove_unused` method.
    pub fn remove_everything_unused(&mut self) -> u32 {
        let mut removed = 0;
        removed += self.remove_unused_layers().to::<u32>();
        removed += self.remove_unused_groups().to::<u32>();
        let (removed_external, removed_embedded) = self.remove_unused_images();
        removed += removed_external.to::<u32>();
        removed += removed_embedded.to::<u32>();
        removed += self.remove_unused_envelopes().to::<u32>();
        removed += self.remove_unused_sounds().to::<u32>();
        removed
    }

    /// Removes all layers for which [`is_empty`](enum.Layer.html#method.is_empty) returns `true`.
    pub fn remove_unused_layers(&mut self) -> u16 {
        let mut removed = 0;
        for group in &mut self.groups {
            let mut i = 0;
            while i < group.layers.len() {
                if group.layers[i].is_empty() && group.layers[i].kind() != LayerKind::Game {
                    removed += 1;
                    group.layers.remove(i);
                }
                else {
                    i += 1;
                }
            }
        }
        removed
    }

    /// Removes all groups that contain zero layers.
    pub fn remove_unused_groups(&mut self) -> u16 {
        let mut removed = 0;
        let mut i = 0;
        while i > self.groups.len() {
            if self.groups[i].layers.is_empty() {
                removed += 1;
                self.groups.remove(i);
            }
            else {
                i += 1;
            }
        }
        removed
    }

    /// Returns `true` if the image index is set for a tiles layer or a quad.
    pub fn is_image_in_use(&self, index: u16) -> bool {
        for group in &self.groups {
            for layer in &group.layers {
                match layer {
                    Layer::Tiles(l) => if l.image == Some(index) { return true },
                    Layer::Quads(l) => if l.image == Some(index) { return true },
                    _ => {}
                }
            }
        }
        false
    }

    /// For easy remapping of all image indices in tiles layers and quads.
    pub fn edit_image_indices(&mut self, edit_fn: impl Fn(Option<u16>) -> Option<u16>) {
        for group in &mut self.groups {
            for layer in &mut group.layers {
                match layer {
                    Layer::Tiles(l) => l.image = edit_fn(l.image),
                    Layer::Quads(l) => l.image = edit_fn(l.image),
                    _ => {}
                }
            }
        }
    }

    /// Removes all images for which [`is_image_in_use`](struct.TwMap.html#method.is_image_in_use) returns `true`.
    /// Return value: (count of removed external images, count of removed embedded images)
    pub fn remove_unused_images(&mut self) -> (u16, u16) {
        let mut removed_external = 0;
        let mut removed_embedded = 0;
        let mut i = 0;
        while i < self.images.len() {
            if self.is_image_in_use(i.try_to()) {
                i += 1;
            }
            else {
                let removed_image = self.images.remove(i);
                match removed_image {
                    Image::External(_) => removed_external += 1,
                    Image::Embedded(_) => removed_embedded += 1,
                }
                self.edit_image_indices(|index| {
                    index.map(|index| if index.to::<usize>() > i { index - 1 } else { index })
                })
            }
        }
        (removed_external, removed_embedded)
    }

    /// Returns `true` if the sound index is set for a sounds layer.
    pub fn is_sound_in_use(&self, index: u16) -> bool {
        for group in &self.groups {
            for layer in &group.layers {
                match layer {
                    Layer::Sounds(l) => if l.sound == Some(index) { return true },
                    _ => {}
                }
            }
        }
        false
    }

    /// For easy remapping of all sound indices in sounds layers.
    pub fn edit_sound_indices(&mut self, edit_fn: impl Fn(Option<u16>) -> Option<u16>) {
        for group in &mut self.groups {
            for layer in &mut group.layers {
                match layer {
                    Layer::Sounds(l) => l.sound = edit_fn(l.sound),
                    _ => {}
                }
            }
        }
    }

    /// Removes all sounds for which [`is_sound_in_use`](struct.TwMap.html#method.is_sound_in_use) returns `true`.
    pub fn remove_unused_sounds(&mut self) -> u16 {
        let mut removed = 0;
        let mut i = 0;
        while i < self.sounds.len() {
            if self.is_sound_in_use(i.try_to()) {
                i += 1;
            }
            else {
                removed += 1;
                self.sounds.remove(i);
                self.edit_sound_indices(|index| {
                    index.map(|index| if index.to::<usize>() > i { index - 1 } else { index })
                })
            }
        }
        removed
    }

    /// Returns `true` if the envelope index is in use.
    pub fn is_env_in_use(&self, index: u16) -> bool {
        for group in &self.groups {
            for layer in &group.layers {
                use Layer::*;
                match layer {
                    Tiles(l) => {
                        if l.color_env == Some(index) {
                            return true;
                        }
                    }
                    Quads(l) => {
                        for quad in &l.quads {
                            if quad.color_env == Some(index) {
                                return true;
                            }
                            if quad.position_env == Some(index) {
                                return true;
                            }
                        }
                    }
                    Sounds(l) => {
                        for source in &l.sources {
                            if source.position_env == Some(index) {
                                return true;
                            }
                            if source.sound_env == Some(index) {
                                return true;
                            }
                        }
                    }
                    _ => {},
                }
            }
        }
        false
    }

    /// For easy remapping of all envelope indices in tiles, quads and sounds layers.
    pub fn edit_env_indices(&mut self, edit_fn: impl Fn(Option<u16>) -> Option<u16>) {
        for group in &mut self.groups {
            for layer in &mut group.layers {
                use Layer::*;
                match layer {
                    Tiles(l) => l.color_env = edit_fn(l.color_env),
                    Quads(l) => {
                        for quad in &mut l.quads {
                            quad.color_env = edit_fn(quad.color_env);
                            quad.position_env = edit_fn(quad.position_env);
                        }
                    }
                    Sounds(l) => {
                        for source in &mut l.sources {
                            source.position_env = edit_fn(source.position_env);
                            source.sound_env = edit_fn(source.sound_env);
                        }
                    }
                    _ => {},
                }
            }
        }
    }

    /// Removes all sounds for which [`is_env_in_use`](struct.TwMap.html#method.is_env_in_use) returns `true`.
    pub fn remove_unused_envelopes(&mut self) -> u16 {
        let mut removed = 0;
        let mut i = 0;
        while i < self.envelopes.len() {
            if self.is_env_in_use(i.try_to()) {
                i += 1;
            }
            else {
                removed += 1;
                self.envelopes.remove(i);
                self.edit_env_indices(|index| {
                    index.map(|index| if index.to::<usize>() > i { index - 1 } else { index })
                })
            }
        }
        removed
    }
}

/// Returns the table for the OPAQUE tile flag, derived from the image data
pub fn calc_opaque_table(image: &RgbaImage) -> [[bool; 16]; 16] {
    let tile_width = image.width() / 16;
    let tile_height = image.height() / 16;
    let mut table = [[false; 16]; 16];
    if tile_width != tile_height {
        return table;
    }

    for tile_y in 0..16 {
        let tile_y_pos = tile_y * tile_width;
        for tile_x in 0..16 {
            let tile_x_pos = tile_x * tile_width;
            let mut opaque = true;

            'outer: for pixel_y in 0..tile_width {
                for pixel_x in 0..tile_width {
                    let y = tile_y_pos + pixel_y;
                    let x = tile_x_pos + pixel_x;
                    if image.get_pixel(x, y).channels()[3] < 250 {
                        opaque = false;
                        break 'outer;
                    }
                }
            }

            table[tile_y.try_to::<usize>()][tile_x.try_to::<usize>()] = opaque;
        }
    }
    table[0][0] = false; // top left tile is manually emptied
    table
}

impl Image {
    /// Returns the table for the OPAQUE tile flag of the image.
    pub fn calc_opaque_table(&self, version: Version) -> [[bool; 16]; 16] {
        match self {
            Image::External(image) => {
                let opaque_tables = match version {
                    Version::Teeworlds07 => VANILLA_EXTERNAL_IMAGES.to_vec(),
                    Version::DDNet06 => DDNET_EXTERNAL_IMAGES.to_vec(),
                };
                match opaque_tables.into_iter()
                    .find(|table| table.0 == image.name) {
                    None => [[false; 16]; 16],
                    Some(opaque_table) => opaque_table.1,
                }
            }
            Image::Embedded(image) => calc_opaque_table(image.image.unwrap_ref())
        }
    }
}

impl TwMap {
    /// Fill in all OPAQUE tile flags.
    pub fn process_tile_flag_opaque(&mut self) {
        let tables: Vec<[[bool; 16]; 16]> = self.images.iter()
            .map(|image| image.calc_opaque_table(self.version))
            .collect();
        for group in &mut self.groups {
            for layer in &mut group.layers {
                if let Layer::Tiles(layer) = layer {
                    let opaque_table = match layer.image {
                        None => &[[false; 16]; 16],
                        Some(index) => &tables[index.to::<usize>()],
                    };
                    let tiles = layer.tiles.unwrap_mut();
                    for tile in tiles {
                        let opaque_value = opaque_table[tile.id.to::<usize>() / 16][tile.id.to::<usize>() % 16];
                        tile.flags.set(TileFlags::OPAQUE, opaque_value);
                    }
                }
            }
        }
    }
}

pub trait ZeroUnusedTileParts: AnyTile {
    /// Unused as in 'not editable by common tools'
    fn zero_unused_tile_parts(&mut self) -> usize { 0 }
}

impl TileFlags {
    fn clear_unused(&mut self) -> bool {
        let cleared = *self & TileFlags::all();
        if cleared != * self {
            *self = cleared;
            true
        }
        else {
            false
        }
    }

    fn clear_unused_and_opaque(&mut self) -> bool {
        let cleared = *self & (TileFlags::all() - TileFlags::OPAQUE);
        if cleared != * self {
            *self = cleared;
            true
        }
        else {
            false
        }
    }
}

impl ZeroUnusedTileParts for Tile {
    fn zero_unused_tile_parts(&mut self) -> usize {
        let mut changed = 0;
        if self.skip != 0 {
            changed += 1;
            self.skip = 0;
        }
        if self.unused != 0 {
            changed += 1;
            self.unused = 0;
        }
        if self.flags.clear_unused() {
            changed += 1;
        }
        changed
    }
}

impl ZeroUnusedTileParts for GameTile {
    fn zero_unused_tile_parts(&mut self) -> usize {
        let mut changed = 0;
        if self.skip != 0 {
            changed += 1;
            self.skip = 0;
        }
        if self.unused != 0 {
            changed += 1;
            self.unused = 0;
        }
        if self.flags.clear_unused_and_opaque() {
            changed += 1;
        }
        changed
    }
}

impl ZeroUnusedTileParts for Speedup {
    fn zero_unused_tile_parts(&mut self) -> usize {
        if self.unused_padding != 0 {
            self.unused_padding = 0;
            1
        }
        else {
            0
        }
    }
}

impl ZeroUnusedTileParts for Tele {}

impl ZeroUnusedTileParts for Switch {
    fn zero_unused_tile_parts(&mut self) -> usize {
        let mut changed = 0;
        if self.flags.clear_unused_and_opaque() {
            changed += 1;
        }
        changed
    }
}

impl ZeroUnusedTileParts for Tune {}

fn zero_unused_tile_parts<T: ZeroUnusedTileParts>(tiles: &mut Array2<T>) -> usize {
    let mut changed = 0;
    tiles.iter_mut()
        .for_each(|tile| changed += tile.zero_unused_tile_parts());
    changed
}

impl TwMap {
    pub fn zero_unused_tile_parts(&mut self) -> usize {
        let mut changed = 0;
        for group in &mut self.groups {
            for layer in &mut group.layers {
                use Layer::*;
                changed += match layer {
                    Game(l) => zero_unused_tile_parts(l.tiles.unwrap_mut()),
                    Tiles(l) => zero_unused_tile_parts(l.tiles.unwrap_mut()),
                    Front(l) => zero_unused_tile_parts(l.tiles.unwrap_mut()),
                    Tele(l) => zero_unused_tile_parts(l.tiles.unwrap_mut()),
                    Speedup(l) => zero_unused_tile_parts(l.tiles.unwrap_mut()),
                    Switch(l) => zero_unused_tile_parts(l.tiles.unwrap_mut()),
                    Tune(l) => zero_unused_tile_parts(l.tiles.unwrap_mut()),
                    Sounds(_) | Invalid(_) | Quads(_) => 0
                }
            }
        }
        changed
    }
}

fn extend_ndarray<T: Default + Copy>(ndarray: &Array2<T>, up: usize, down: usize, left: usize, right: usize) -> Array2<T> {
    let old_height = ndarray.nrows();
    let new_height = old_height.checked_add(up).unwrap().checked_add(down).unwrap();
    let old_width = ndarray.ncols();
    let new_width = old_width.checked_add(left).unwrap().checked_add(right).unwrap();
    let mut new_ndarray = Array2::default((new_height, new_width));
    // copy old layer into the new one
    new_ndarray.slice_mut(s![up..up + ndarray.nrows(), left..left + ndarray.ncols()]).assign(ndarray);
    // copy the corner of the old ndarray into the corner region of the new one
    let corners = vec![
        ((0..up, 0..left), ndarray[(0, 0)]), // top left
        ((0..up, new_width - right..new_width), ndarray[(0, old_width - 1)]), // top right
        ((new_height - down..new_height, 0..left), ndarray[(old_height - 1, 0)]), // bottom
        ((new_height - down..new_height, new_width - right..new_width), ndarray[(old_height - 1, old_width -1)]),
    ];
    for ((y_slice, x_slice), corner) in corners {
        new_ndarray.slice_mut(s![y_slice, x_slice]).map_inplace(|e| *e = corner);
    }
    // copy the old outermost rows/columns into the new area
    let vertical_edge_ranges = vec![
        (ndarray.row(0), (0..up, left..left + old_width)), // upper edge
        (ndarray.row(old_height - 1), (up + old_height..new_height, left..left + old_width)), // lower edge
    ];
    let horizontal_edge_ranges = vec![
        (ndarray.column(0), (up..up + old_height, 0..left)), // left edge
        (ndarray.column(old_width - 1), (up..up + old_height, left + old_width..new_width)), // right edge
    ];
    for (edge, (y_slice, x_slice)) in vertical_edge_ranges {
        new_ndarray.slice_mut(s![y_slice, x_slice]).genrows_mut()
            .into_iter()
            .for_each(|mut row| row.assign(&edge))
    }
    for (edge, (y_slice, x_slice)) in horizontal_edge_ranges {
        new_ndarray.slice_mut(s![y_slice, x_slice]).gencolumns_mut()
            .into_iter()
            .for_each(|mut row| row.assign(&edge))
    }
    new_ndarray
}

fn extend_layer<T: TileMapLayer>(layer: &mut T, up: usize, down: usize, left: usize, right: usize) {
    *layer.tiles_mut().unwrap_mut() = extend_ndarray(layer.tiles().unwrap_ref(), up, down, left, right);
}

impl Point {
    fn reposition(&self, vertical: i32, horizontal: i32) -> Option<Point> {
        Some(Point {
            x: self.x.checked_add(horizontal)?,
            y: self.y.checked_add(vertical)?,
        })
    }
}

impl QuadsLayer {
    // TODO: somehow make atomic + the return value reasonable
    fn reposition(&mut self, vertical: i32, horizontal: i32) -> Option<()> {
        for quad in &mut self.quads {
            quad.position = quad.position.reposition(vertical, horizontal)?;
            for corner in &mut quad.corners {
                *corner = corner.reposition(vertical, horizontal)?;
            }
        }
        Some(())
    }
}

impl SoundsLayer {
    // TODO: somehow make the return value reasonable
    fn reposition(&mut self, vertical: i32, horizontal: i32) -> Option<()> {
        for source in &mut self.sources {
            source.position = source.position.reposition(vertical, horizontal)?;
        }
        Some(())
    }
}

/// Increases the size of the tilemap layers by the specified tile amount in each direction.
/// To keep the look of the map the same, this also moves the quads in quads layers and adjust the offset of groups as well as their clipping.
impl TwMap {
    pub fn extend_layers(mut self, up: u16, down: u16, left: u16, right: u16) -> Option<TwMap> {
        for group in &mut self.groups {
            for layer in &mut group.layers {
                let object_vertical_shift = up.to::<i32>() * 32 * 1024;
                let object_horizontal_shift = left.to::<i32>() * 32 * 1024;
                use Layer::*;
                match layer {
                    Game(l) => extend_layer(l, up.to(), down.to(), left.to(), right.to()),
                    Tiles(l) => extend_layer(l, up.to(), down.to(), left.to(), right.to()),
                    Quads(l) => l.reposition(object_vertical_shift, object_horizontal_shift)?,
                    Front(l) => extend_layer(l, up.to(), down.to(), left.to(), right.to()),
                    Tele(l) => extend_layer(l, up.to(), down.to(), left.to(), right.to()),
                    Speedup(l) => extend_layer(l, up.to(), down.to(), left.to(), right.to()),
                    Switch(l) => extend_layer(l, up.to(), down.to(), left.to(), right.to()),
                    Tune(l) => extend_layer(l, up.to(), down.to(), left.to(), right.to()),
                    Sounds(l) => l.reposition(object_vertical_shift, object_horizontal_shift)?,
                    Invalid(_) => {}
                }
            }
            let up_shift_in_offset_units = (up.to::<i32>() * 32)
                .checked_mul(group.parallax_y)?
                .checked_div(100)?;
            let left_shift_in_offset_units = (left.to::<i32>() * 32)
                .checked_mul(group.parallax_x)?
                .checked_div(100)?;
            group.offset_y = group.offset_y.checked_add(up.to::<i32>() * 32)?
                .checked_sub(up_shift_in_offset_units)?;
            group.offset_x = group.offset_x.checked_add(left.to::<i32>() * 32)?
                .checked_sub(left_shift_in_offset_units)?;
            if !group.is_physics_group() {
                group.clip_x = group.clip_x.checked_add(left.to::<i32>() * 32)?;
                group.clip_y = group.clip_y.checked_add(up.to::<i32>() * 32)?;
            }
        }
        Some(self)
    }
}

/// up - down - left - right
fn ndarray_shrink<T: Default + Clone>(ndarray: &Array2<T>, up: usize, down: usize, left: usize, right: usize) -> Option<Array2<T>> {
    let height = ndarray.nrows().checked_sub(up)?.checked_sub(down)?;
    let width = ndarray.ncols().checked_sub(left)?.checked_sub(right)?;
    Some(ndarray.slice(s![up..up + height, left..left + width]).to_owned())
}

trait TileMapLayerManipulation: TileMapLayer {
    // Panics if up, down, left, right shrink the tiles into the negative
    fn checked_shrink(mut self, up: usize, down: usize, left: usize, right: usize) -> Option<Self> {
        *self.tiles_mut().unwrap_mut() = ndarray_shrink(self.tiles().unwrap_ref(), up, down, left, right)?.into();
        Some(self)
    }
}


impl<T: TileMapLayer> TileMapLayerManipulation for T {}

impl Layer {
    fn shrink(self, up: usize, down: usize, left: usize, right: usize) -> Option<Layer> {
        use Layer::*;
        Some(match self {
            Game(l) => Game(l.checked_shrink(up, down, left, right)?),
            Tiles(l) => Tiles(l.checked_shrink(up, down, left, right)?),
            Quads(mut l) => {
                l.reposition(i32::try_from(up).ok()?.checked_mul(-32 * 1024)?, i32::try_from(left).ok()?.checked_mul(-32 * 1024)?)?;
                Quads(l)
            },
            Front(l) => Front(l.checked_shrink(up, down, left, right)?),
            Tele(l) => Tele(l.checked_shrink(up, down, left, right)?),
            Speedup(l) => Speedup(l.checked_shrink(up, down, left, right)?),
            Switch(l) => Switch(l.checked_shrink(up, down, left, right)?),
            Tune(l) => Tune(l.checked_shrink(up, down, left, right)?),
            Sounds(mut l) => {
                l.reposition(i32::try_from(up).ok()?.checked_mul(-32 * 1024)?, i32::try_from(left).ok()?.checked_mul(-32 * 1024)?)?;
                Sounds(l)
            },
            Invalid(l) => Invalid(l),
        })
    }
}

// For every direction, this function will return the amount of rows/columns that are duplicates of the innermost one
// Use this function with caution, since for example layers with the same tile everywhere can be shrunken into nothingness in each direction
fn lossless_shrink_distances<T: Default + Clone + PartialEq>(ndarray: &Array2<T>) -> (usize, usize, usize, usize) {
    let rows: Vec<_> = ndarray.genrows()
        .into_iter()
        .collect();
    let up = match rows.windows(2)
        .position(|rows| rows[0] != rows[1]) {
        Some(pos) => pos,
        None => ndarray.nrows(),
    };
    let down = match rows.windows(2).rev()
        .position(|rows| rows[0] != rows[1]) {
        Some(pos) => pos,
        None => ndarray.nrows(),
    };

    let columns: Vec<_> = ndarray.gencolumns()
        .into_iter()
        .collect();
    let left = match columns.windows(2)
        .position(|rows| rows[0] != rows[1]) {
        Some(pos) => pos,
        None => ndarray.ncols(),
    };
    let right = match columns.windows(2).rev()
        .position(|rows| rows[0] != rows[1]) {
        Some(pos) => pos,
        None => ndarray.ncols(),
    };
    return (up, down, left, right)
}

impl Layer {
    fn lossless_shrink_distances(&self) -> Option<(usize, usize, usize, usize)> {
        use Layer::*;
        match self {
            Game(l) => Some(lossless_shrink_distances(l.tiles.unwrap_ref())),
            Tiles(l) => Some(lossless_shrink_distances(l.tiles.unwrap_ref())),
            Quads(_) => None,
            Front(l) => Some(lossless_shrink_distances(l.tiles.unwrap_ref())),
            Tele(l) => Some(lossless_shrink_distances(l.tiles.unwrap_ref())),
            Speedup(l) => Some(lossless_shrink_distances(l.tiles.unwrap_ref())),
            Switch(l) => Some(lossless_shrink_distances(l.tiles.unwrap_ref())),
            Tune(l) => Some(lossless_shrink_distances(l.tiles.unwrap_ref())),
            Sounds(_) => None,
            Invalid(_) => None,
        }
    }
}

impl Group {
    fn lossless_tiles_layer_shrink(mut self) -> Option<Group> {
        if self.layers.iter().all(|layer| layer.kind() != LayerKind::Tiles) {
            return Some(self); // no tiles layer -> nothing to shrink
        }
        let shrink_distances: Vec<_> = self.layers.iter()
            .map(|layer| layer.lossless_shrink_distances())
            .collect();

        let smallest_layer_height = self.layers.iter()
            .filter_map(|layer| layer.shape().map(|shape| shape.0))
            .min().unwrap();
        let smallest_layer_width = self.layers.iter()
            .filter_map(|layer| layer.shape().map(|shape| shape.1))
            .min().unwrap();
        let mut lowest_up_shrink = 0;
        let mut lowest_left_shrink = 0;
        if !self.is_physics_group() {
            // all layers in a group must shrink by the same amount from the left and up, since you can't offset single layers
            lowest_up_shrink = shrink_distances.iter()
                .filter_map(|&d| d.map(|dirs| dirs.0))
                .min().unwrap();
            lowest_left_shrink = shrink_distances.iter()
                .filter_map(|&d| d.map(|dirs| dirs.2))
                .min().unwrap();
            // ensure that the layers are at least 2 blocks high and wide
            lowest_up_shrink = min(lowest_up_shrink, smallest_layer_height.checked_sub(2)?);
            lowest_left_shrink = min(lowest_left_shrink, smallest_layer_width.checked_sub(2)?);
        }
        self.layers = self.layers.into_iter().zip(shrink_distances)
            .map(|(layer, dirs)| {
                if layer.kind().is_physics_layer() {
                    Some(layer)
                }
                else {
                    let mut down = dirs.map(|d| d.1).unwrap_or(0);
                    let mut right = dirs.map(|d| d.3).unwrap_or(0);
                    // ensure that the layers are at least 2 blocks high and wide
                    if let Some((height, width)) = layer.shape() {
                        down = min(down, height.checked_sub(lowest_up_shrink + 2)?);
                        right = min(right, width.checked_sub(lowest_left_shrink + 2)?);
                    }
                    layer.shrink(lowest_up_shrink, down, lowest_left_shrink, right)
                }
            })
            .collect::<Option<_>>()?;

        let lowest_up_shrink = i32::try_from(lowest_up_shrink).ok()?;
        let lowest_left_shrink = i32::try_from(lowest_left_shrink).ok()?;
        // shrinking the layers from up and left moves them, so the offset has to correct that
        self.offset_y = self.offset_y.checked_sub(lowest_up_shrink.checked_mul(32)?)?
            .checked_mul(self.parallax_y)?
            .checked_div(100)?;
        self.offset_x = self.offset_x.checked_sub(lowest_left_shrink.checked_mul(32)?)?
            .checked_mul(self.parallax_x)?
            .checked_div(100)?;
        Some(self)
    }

    fn lossless_layer_shrink(mut self) -> Option<Group> {
        if self.layers.iter().all(|layer| !layer.kind().is_tile_map_layer()) {
            return Some(self); // no tile map layer -> nothing to shrink
        }
        let shrink_distances: Vec<_> = self.layers.iter()
            .map(|layer| layer.lossless_shrink_distances())
            .collect();

        let smallest_layer_height = self.layers.iter()
            .filter_map(|layer| layer.shape().map(|shape| shape.0))
            .min().unwrap();
        let smallest_layer_width = self.layers.iter()
            .filter_map(|layer| layer.shape().map(|shape| shape.1))
            .min().unwrap();
        // all layers in a group must shrink by the same amount from the left and up, since you can't offset single layers
        let mut lowest_up_shrink = shrink_distances.iter()
            .filter_map(|&d| d.map(|dirs| dirs.0))
            .min().unwrap();
        let mut lowest_left_shrink = shrink_distances.iter()
            .filter_map(|&d| d.map(|dirs| dirs.2))
            .min().unwrap();
        // ensure that the layers are at least 2 blocks high and wide
        lowest_up_shrink = min(lowest_up_shrink, smallest_layer_height.checked_sub(2)?);
        lowest_left_shrink = min(lowest_left_shrink, smallest_layer_width.checked_sub(2)?);
        // all physics layers must shrink by the same amount from the right and down, since they must be the same size
        let physics_layer_down_shrink = self.layers.iter()
            .filter_map(|l| {
                if l.kind().is_physics_layer() {
                    l.lossless_shrink_distances()
                }
                else {
                    None
                }
            })
            .map(|d| d.1)
            .min();
        let physics_layer_right_shrink = self.layers.iter()
            .filter_map(| l| {
                if l.kind().is_physics_layer() {
                    l.lossless_shrink_distances()
                }
                else {
                    None
                }
            })
            .map(|d| d.3)
            .min();
        self.layers = self.layers.into_iter().zip(shrink_distances)
            .map(|(layer, dirs)| {
                let (mut down, mut right) = match layer.kind().is_physics_layer() {
                    true => (physics_layer_down_shrink.unwrap(), physics_layer_right_shrink.unwrap()),
                    false => (dirs.map(|d| d.1).unwrap_or(0), dirs.map(|d| d.3).unwrap_or(0)),
                };
                // ensure that the layers are at least 2 blocks high and wide
                if let Some((height, width)) = layer.shape() {
                    down = min(down, height.checked_sub(lowest_up_shrink + 2)?);
                    right = min(right, width.checked_sub(lowest_left_shrink + 2)?);
                }
                layer.shrink(lowest_up_shrink, down, lowest_left_shrink, right)
            })
            .collect::<Option<_>>()?;

        let lowest_up_shrink = i32::try_from(lowest_up_shrink).ok()?;
        let lowest_left_shrink = i32::try_from(lowest_left_shrink).ok()?;
        // shrinking the layers from up and left moves them, so the offset has to correct that
        self.offset_y = self.offset_y.checked_sub(lowest_up_shrink.checked_mul(32)?)?
            .checked_mul(self.parallax_y)?
            .checked_div(100)?;
        self.offset_x = self.offset_x.checked_sub(lowest_left_shrink.checked_mul(32)?)?
            .checked_mul(self.parallax_x)?
            .checked_div(100)?;
        Some(self)
    }
}

impl TwMap {
    /// Downsizes all tile map layers as much as possible.
    /// Note that this will also reduce the size of physics layers and thereby moves the world border!
    pub fn lossless_shrink_layers(mut self) -> Option<TwMap> {
        self.groups = self.groups.into_iter()
            .map(|group| group.lossless_layer_shrink())
            .collect::<Option<_>>()?;
        // when the physics group shrinks from the left or up, it gets offset, so we must correct that
        let physics_group = self.physics_group();
        let offset_y_shift = physics_group.offset_y;
        let offset_x_shift = physics_group.offset_x;
        for group in &mut self.groups {
            group.offset_y = group.offset_y.checked_sub(offset_y_shift.checked_mul(group.parallax_y)?.checked_div(100)?)?;
            group.offset_x = group.offset_x.checked_sub(offset_x_shift.checked_mul(group.parallax_x)?.checked_div(100)?)?;
            if !group.is_physics_group() {
                group.clip_y = group.clip_y.checked_add(offset_y_shift)?;
                group.clip_x = group.clip_x.checked_add(offset_x_shift)?;
            }
        }
        Some(self)
    }

    /// Downsizes all tiles layers as much as possible.
    pub fn lossless_shrink_tiles_layers(mut self) -> Option<TwMap> {
        self.groups = self.groups.into_iter()
            .map(|group| {
                group.lossless_tiles_layer_shrink()
            })
            .collect::<Option<_>>()?;
        Some(self)
    }
}

fn mirror_tiles<T: TileFlipping>(tiles: &Array2<T>, align_width: i32) -> Array2<T> {
    let align_width = align_width.try_to::<usize>();
    if tiles.ncols() > align_width {
        panic!("Array width too large, can't align to smaller width")
    }

    let default = T::default();
    let mirrored_shape_vec: Vec<T> = tiles.outer_iter()
        .flat_map(|row| row.into_iter()
            .pad_using(align_width, |_| &default)
            .rev())
        .map(|tile| {
            let mut mirrored_tile = tile.clone();
            T::mirror_tile(&mut mirrored_tile);
            mirrored_tile
        })
        .collect();
    Array2::from_shape_vec((tiles.nrows(), align_width), mirrored_shape_vec).unwrap()
}

fn mirror_tile_layer<T: TileMapLayer>(mut layer: T, align_width: i32) -> T
    where T::TileType: TileFlipping {
    let mirrored_tiles = mirror_tiles(layer.tiles().unwrap_ref(), align_width);
    *layer.tiles_mut().unwrap_mut() = mirrored_tiles.into();
    layer
}

fn rotate_tile_map_right<T: TileFlipping>(tiles: &Array2<T>, align_height: i32) -> Array2<T> {
    let align_height = align_height.try_to::<usize>();
    if tiles.nrows() > align_height {
        panic!("Array width too large, can't align to smaller height")
    }

    let mut rotated_shape_vec = Vec::new();
    for i in 0..tiles.ncols() {
        if tiles.nrows() < align_height {
            for _ in 0..align_height - tiles.nrows() {
                rotated_shape_vec.push(T::default())
            }
        }
        for row in tiles.outer_iter().rev() {
            rotated_shape_vec.push({
                let mut rotated_tile = row[i].clone();
                T::rotate_tile_right(&mut rotated_tile);
                rotated_tile
            });
        }
    }
    Array2::from_shape_vec((tiles.ncols(), align_height), rotated_shape_vec).unwrap()
}

fn rotate_tile_layer<T: TileMapLayer>(mut layer: T, align_height: i32) -> T
    where T::TileType: TileFlipping {
    let rotated_tiles = rotate_tile_map_right(layer.tiles().unwrap_ref(), align_height);
    *layer.tiles_mut().unwrap_mut() = rotated_tiles.into();
    layer
}

pub trait TileFlipping: AnyTile {
    fn mirror_tile(&mut self);

    fn rotate_tile_right(&mut self);
}

impl TileFlags {
    fn mirror(&mut self) {
        match self.contains(TileFlags::ROTATE) {
            false => self.toggle(TileFlags::FLIP_V),
            true => self.toggle(TileFlags::FLIP_H),
        }
    }

    // rotates sideways blocks by rotating them by 180°, required for some game/front/switch layer tiles
    fn mirror_rotate(&mut self) {
        if self.contains(TileFlags::ROTATE) {
            self.toggle(TileFlags::FLIP_H | TileFlags::FLIP_V);
        }
    }

    fn rotate_right(&mut self) {
        if self.contains(TileFlags::ROTATE) {
            self.toggle(TileFlags::FLIP_H | TileFlags::FLIP_V);
        }
        self.toggle(TileFlags::ROTATE);
    }
}

impl TileFlipping for Tile {
    fn mirror_tile(&mut self) {
        self.flags.mirror()
    }

    fn rotate_tile_right(&mut self) {
        self.flags.rotate_right();
    }
}

impl TileFlipping for GameTile {
    fn mirror_tile(&mut self) {
        match self.id {
            60 | 61 | 64 | 65 | 67 | 224 | 225 => self.flags.mirror_rotate(),
            _ => self.flags.mirror(),
        }
        // mirror rotating lasers by using the corresponding mirrored tile
        if self.id >= 203 && self.id <= 205 {
            self.id += (206 - self.id) * 2;
        }
        else if self.id >= 207 && self.id <= 209 {
            self.id -= (self.id - 206) * 2;
        }
    }

    fn rotate_tile_right(&mut self) {
        self.flags.rotate_right();
    }
}

impl TileFlipping for Tele {
    fn mirror_tile(&mut self) {}

    fn rotate_tile_right(&mut self) {}
}

impl TileFlipping for Speedup {
    fn mirror_tile(&mut self) {
        let mut angle = i16::from(self.angle);
        angle = 180 - angle;
        if angle < 0 {
            angle += 360;
        }
        self.angle= angle.into();
    }

    fn rotate_tile_right(&mut self) {
        let mut angle = i16::from(self.angle);
        angle += 90;
        angle %= 360;
        self.angle= angle.into();
    }
}

impl TileFlipping for Switch {
    fn mirror_tile(&mut self) {
        match self.id {
            224 | 225 => self.flags.mirror_rotate(),
            _ => self.flags.mirror(),
        }
        // mirror rotating lasers by using the corresponding mirrored tile
        if self.id >= 203 && self.id <= 205 {
            self.id += (206 - self.id) * 2;
        }
        else if self.id >= 207 && self.id <= 209 {
            self.id -= (self.id - 206) * 2;
        }
    }

    fn rotate_tile_right(&mut self) {
        self.flags.rotate_right();
    }
}

impl TileFlipping for Tune {
    fn mirror_tile(&mut self) {}

    fn rotate_tile_right(&mut self) {}
}

impl TwMap {
    /// Mirrors the map. Switches left and right.
    pub fn mirror(mut self) -> Option<TwMap> {
        self.isolate_physics_layers();
        // x_shift is the x-difference between the old and new origin
        let origin_x_shift = self.physics_group().layers.iter()
            .filter_map(|layer| layer.shape())
            .map(|shape| shape.1.try_to::<i32>())
            .max().unwrap();
        self.groups = self.groups.into_iter()
            .map(|group| group.mirror(origin_x_shift))
            .collect::<Option<_>>()?;
        self.envelopes = self.envelopes.into_iter()
            .map(|env| env.mirror())
            .collect::<Option<_>>()?;
        Some(self)
    }

    /// Rotates the map clockwise.
    pub fn rotate_right(mut self) -> Option<TwMap> {
        self.isolate_physics_layers();
        let origin_y_shift = self.physics_group().layers.iter()
            .filter_map(|layer| layer.shape())
            .map(|shape| shape.0.try_to::<i32>())
            .max().unwrap();
        self.groups = self.groups.into_iter()
            .map(|group| group.rotate_right(origin_y_shift))
            .collect::<Option<_>>()?;
        self.envelopes = self.envelopes.into_iter()
            .map(|env| env.rotate_right())
            .collect::<Option<_>>()?;
        Some(self)
    }
}

impl Point {
    fn mirror(&self, origin_x_shift: i32) -> Option<Point> {
        Some(Point {
            x: origin_x_shift.checked_sub(self.x)?,
            y: self.y,
        })
    }

    fn rotate_right(&self, origin_y_shift: i32) -> Option<Point> {
        Some(Point {
            x: origin_y_shift.checked_sub(self.y)?,
            y: self.x,
        })
    }
}

impl QuadsLayer {
    fn mirror(mut self, align_width: i32) -> Option<QuadsLayer> {
        for quad in &mut self.quads {
            quad.position = quad.position.mirror(align_width)?;
            for corner in &mut quad.corners {
                *corner = corner.mirror(align_width)?;
            }
        }
        Some(self)
    }

    fn rotate_right(mut self, align_height: i32) -> Option<QuadsLayer> {
        for quad in &mut self.quads {
            quad.position = quad.position.rotate_right(align_height)?;
            for corner in &mut quad.corners {
                *corner = corner.rotate_right(align_height)?;
            }
        }
        Some(self)
    }
}

impl SoundsLayer {
    fn mirror(mut self, align_width: i32) -> Option<SoundsLayer> {
        for source in &mut self.sources {
            source.position = source.position.mirror(align_width)?;
        }
        Some(self)
    }

    fn rotate_right(mut self, align_height: i32) -> Option<SoundsLayer> {
        for source in &mut self.sources {
            source.position = source.position.rotate_right(align_height)?;
            if let SoundShape::Rectangle {width, height} = source.shape {
                source.shape = SoundShape::Rectangle { width: height, height: width }
            }
        }
        Some(self)
    }
}

fn calc_new_offset(former_offset: i32, origin_shift: i32, parallax: i32, align_size: i32) -> Option<i32> {
    let origin_shift_in_units = origin_shift.checked_mul(32)?;
    let origin_shift_parallaxed = origin_shift_in_units.checked_mul(parallax)?
        .checked_div(100)?;
    let align_size_in_units = align_size.checked_mul(32)?;
    let offset_offset = origin_shift_parallaxed.checked_sub(align_size_in_units)?;
    former_offset.checked_add(offset_offset)?.checked_mul(-1)
}

fn calc_new_clip_pos(align_size: i32, clip_pos: i32, clip_size: i32) -> Option<i32> {
    let align_size_in_units = align_size.checked_mul(32)?;
    let new_clip_corner_pos = clip_pos.checked_add(clip_size)?;
    align_size_in_units.checked_sub(new_clip_corner_pos)
}

impl Layer {
    fn mirror(self, align_width: i32) -> Option<Layer> {
        use Layer::*;
        let align_width_in_quads_units = align_width.checked_mul(32)?
            .checked_mul(1024)?;
        Some(match self {
            Game(l) => Game(mirror_tile_layer(l, align_width)),
            Tiles(l) => Tiles(mirror_tile_layer(l, align_width)),
            Quads(l) => Quads(l.mirror(align_width_in_quads_units)?),
            Front(l) => Front(mirror_tile_layer(l, align_width)),
            Tele(l) => Tele(mirror_tile_layer(l, align_width)),
            Speedup(l) => Speedup(mirror_tile_layer(l, align_width)),
            Switch(l) => Switch(mirror_tile_layer(l, align_width)),
            Tune(l) => Tune(mirror_tile_layer(l, align_width)),
            Sounds(l) => Sounds(l.mirror(align_width_in_quads_units)?),
            Invalid(l) => Invalid(l),
        })
    }

    fn rotate(self, align_height: i32) -> Option<Layer> {
        use Layer::*;
        let align_height_in_quads_units = align_height.checked_mul(32)?
            .checked_mul(1024)?;
        Some(match self {
            Game(l) => Game(rotate_tile_layer(l, align_height)),
            Tiles(l) => Tiles(rotate_tile_layer(l, align_height)),
            Quads(l) => Quads(l.rotate_right(align_height_in_quads_units)?),
            Front(l) => Front(rotate_tile_layer(l, align_height)),
            Tele(l) => Tele(rotate_tile_layer(l, align_height)),
            Speedup(l) => Speedup(rotate_tile_layer(l, align_height)),
            Switch(l) => Switch(rotate_tile_layer(l, align_height)),
            Tune(l) => Tune(rotate_tile_layer(l, align_height)),
            Sounds(l) => Sounds(l.rotate_right(align_height_in_quads_units)?),
            Invalid(l) => Invalid(l),
        })
    }
}

impl Group {
    fn mirror(mut self, origin_x_shift: i32) -> Option<Group> {
        let align_width = match self.layers.iter()
            .filter_map(|layer| layer.shape())
            .map(|shape| shape.1)
            .max() {
            None => origin_x_shift,
            Some(width) => width.try_to::<i32>(),
        };
        self.offset_x = calc_new_offset(self.offset_x, origin_x_shift, self.parallax_x, align_width)?;

        if !self.is_physics_group() {
            self.clip_x = calc_new_clip_pos(origin_x_shift, self.clip_x, self.clip_width)?;
        }
        self.layers = self.layers.into_iter()
            .map(|layer| layer.mirror(align_width))
            .collect::<Option<_>>()?;
        Some(self)
    }

    fn rotate_right(mut self, origin_y_shift: i32) -> Option<Group> {
        let align_height = match self.layers.iter()
            .filter_map(|layer| layer.shape())
            .map(|shape| shape.0)
            .max() {
            None => origin_y_shift,
            Some(height) => height.try_to::<i32>(),
        };
        let original_offset_x = self.offset_x;
        self.offset_x = calc_new_offset(self.offset_y, origin_y_shift, self.parallax_y, align_height)?;
        self.offset_y = original_offset_x;

        if !self.is_physics_group() {
            let original_clip_x = self.clip_x;
            self.clip_x = calc_new_clip_pos(origin_y_shift, self.clip_y, self.clip_height)?;
            self.clip_y = original_clip_x;
        }

        let original_clip_width = self.clip_width;
        self.clip_width = self.clip_height;
        self.clip_height = original_clip_width;

        let original_parallax_x = self.parallax_x;
        self.parallax_x = self.parallax_y;
        self.parallax_y = original_parallax_x;

        self.layers = self.layers.into_iter()
            .map(|layer| layer.rotate(align_height))
            .collect::<Option<_>>()?;
        Some(self)
    }
}

impl Envelope {
    fn mirror(mut self) -> Option<Envelope> {
        match &mut self {
            Envelope::Position(env) => {
                for point in &mut env.points {
                    point.content.x = point.content.x.checked_mul(-1)?;
                    point.content.rotation = point.content.rotation.checked_mul(-1)?;
                }
            }
            Envelope::Color(_) => {}
            Envelope::Sound(_) => {}
        }
        Some(self)
    }

    fn rotate_right(mut self) -> Option<Envelope> {
        match &mut self {
            Envelope::Position(env) => {
                for point in &mut env.points {
                    let original_x = point.content.x;
                    point.content.x = point.content.y.checked_mul(-1)?;
                    point.content.y = original_x;
                }
            }
            Envelope::Color(_) => {}
            Envelope::Sound(_) => {}
        }
        Some(self)
    }
}

impl TwMap {
    // move cosmetic layers from the game group in a group before/after the game group, depending on position relative to the game layer
    fn isolate_physics_layers(&mut self) {
        let index = self.groups.iter().position(|g| g.is_physics_group()).unwrap();
        let game_group = &mut self.groups[index];
        let mut front_group = Group { name: String::from("GameFront"), ..Group::default() };
        let mut back_group = Group { name: String::from("GameBack"), ..Group::default() };
        let mut i = 0;
        let mut after = false;
        while i < game_group.layers.len() {
            if !game_group.layers[i].kind().is_physics_layer() {
                if after {
                    back_group.layers.push(game_group.layers.remove(i));
                }
                else {
                    front_group.layers.push(game_group.layers.remove(i));
                }
            }
            else {
                if game_group.layers[i].kind() == LayerKind::Game {
                    after = true;
                }
                i += 1;
            }
        }
        if !back_group.layers.is_empty() {
            self.groups.insert(index + 1, back_group);
        }
        if !front_group.layers.is_empty() {
            self.groups.insert(index, front_group);
        }
    }
}