path: root/src/bitmap.rs

use std::{
    collections::HashSet,
    convert::{From, Into, TryFrom},
    ops::{Add, Sub},
};

#[derive(Debug)]
pub struct Pixmap<T> {
    pub width: u32,
    pub height: u32,
    pub data: Vec<T>,
}

#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
pub struct MapPoint {
    pub x: u32,
    pub y: u32,
}

impl From<(u32, u32)> for MapPoint {
    fn from((x, y): (u32, u32)) -> MapPoint {
        MapPoint { x, y }
    }
}

impl TryFrom<(i32, i32)> for MapPoint {
    type Error = ();
    fn try_from((x, y): (i32, i32)) -> Result<Self, Self::Error> {
        if x < 0 || y < 0 {
            return Err(());
        } else {
            Ok(MapPoint {
                x: x as u32,
                y: y as u32,
            })
        }
    }
}

impl TryFrom<(i64, i64)> for MapPoint {
    type Error = ();
    fn try_from((x, y): (i64, i64)) -> Result<Self, Self::Error> {
        if x < 0 || y < 0 {
            return Err(());
        } else {
            Ok(MapPoint {
                x: x as u32,
                y: y as u32,
            })
        }
    }
}

impl Add for MapPoint {
    type Output = Self;
    fn add(self, rhs: Self) -> Self::Output {
        MapPoint {
            x: self.x.saturating_add(rhs.x),
            y: self.y.saturating_add(rhs.y),
        }
    }
}

impl Sub for MapPoint {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self::Output {
        MapPoint {
            x: self.x.saturating_sub(rhs.x),
            y: self.y.saturating_sub(rhs.y),
        }
    }
}

#[derive(Debug, Copy, Clone)]
pub enum Axis {
    X,
    Y,
}

#[derive(Debug, Copy, Clone)]
pub enum Quadrant {
    I,
    II,
    III,
    IV,
}

impl MapPoint {
    #[inline]
    pub fn scale(self, c: u32) -> MapPoint {
        MapPoint {
            x: self.x * c,
            y: self.y * c,
        }
    }

    #[inline]
    pub fn mirror_about(self, line: u32, axis: Axis) -> MapPoint {
        let MapPoint { x, y } = self;
        match axis {
            Axis::X => MapPoint {
                x,
                y: (2 * line).saturating_sub(y),
            },
            Axis::Y => MapPoint {
                x: (2 * line).saturating_sub(x),
                y,
            },
        }
    }

    #[inline]
    pub fn reflect(self, around: MapPoint) -> MapPoint {
        around.scale(2) - self
    }

    #[inline]
    pub fn quadrant(self, origin: MapPoint) -> Quadrant {
        match (self, origin) {
            _ if self.x >= origin.x && self.y >= origin.y => Quadrant::I,
            _ if self.x < origin.x && self.y >= origin.y => Quadrant::II,
            _ if self.x < origin.x && self.y < origin.y => Quadrant::III,
            _ if self.x >= origin.x && self.y < origin.y => Quadrant::IV,
            _ => unreachable!("unexpected quadrant!"),
        }
    }
}

impl<T> Pixmap<T>
where
    T: Copy + Clone + Default + PartialEq,
{
    pub fn new(width: u32, height: u32) -> Self {
        let data = vec![Default::default(); (width * height) as usize];
        Pixmap {
            width,
            height,
            data,
        }
    }

    pub fn new_with(width: u32, height: u32, data: Vec<T>) -> Self {
        Pixmap {
            width,
            height,
            data,
        }
    }

    pub fn contains<P: Into<MapPoint>>(&self, pt: P) -> bool {
        let MapPoint { x, y } = pt.into();
        x < self.width && y < self.height
    }

    pub fn idx<P: Into<MapPoint>>(&self, pt: P) -> usize {
        let MapPoint { x, y } = pt.into();
        (y * self.width + x) as usize
    }

    pub fn get<P: Into<MapPoint>>(&self, pt: P) -> T {
        let idx = self.idx(pt);
        self.data[idx]
    }

    pub fn set<P: Into<MapPoint>>(&mut self, pt: P, new_val: T) -> T {
        let pt = pt.into();
        let old_val = self.get(pt);
        let idx = self.idx(pt);
        self.data[idx] = new_val;
        old_val
    }

    pub fn get_circle<P: Into<MapPoint>>(
        &self,
        center: P,
        radius: u32,
        filled: bool,
    ) -> Vec<MapPoint> {
        let mut circle: Vec<(i64, i64)> = vec![];
        let MapPoint { x, y } = center.into();
        let x = x as i64;
        let y = y as i64;
        let (mut dx, mut dy, mut err) = (radius as i64, 0i64, 1 - radius as i64);
        while dx >= dy {
            circle.push((x + dx, y + dy));
            circle.push((x - dx, y + dy));
            circle.push((x + dx, y - dy));
            circle.push((x - dx, y - dy));
            circle.push((x + dy, y + dx));
            circle.push((x - dy, y + dx));
            circle.push((x + dy, y - dx));
            circle.push((x - dy, y - dx));
            if filled {
                circle.extend((x - dx.abs() + 1..x + dx.abs()).map(|x| (x, y + dy)));
                circle.extend((x - dx.abs() + 1..x + dx.abs()).map(|x| (x, y - dy)));
                circle.extend((x - dy.abs() + 1..x + dy.abs()).map(|x| (x, y + dx)));
                circle.extend((x - dy.abs() + 1..x + dy.abs()).map(|x| (x, y - dx)));
            }
            dy = dy + 1;
            if err < 0 {
                err = err + 2 * dy + 1;
            } else {
                dx -= 1;
                err += 2 * (dy - dx) + 1;
            }
        }
        circle
            .into_iter()
            .flat_map(|pt| MapPoint::try_from(pt))
            .filter(|&pt| self.contains(pt))
            .collect()
    }

    pub fn get_line<P: Into<MapPoint>>(&self, start: P, end: P) -> Vec<MapPoint> {
        let MapPoint { x: x1, y: y1 } = start.into();
        let MapPoint { x: x2, y: y2 } = end.into();
        let mut coordinates = vec![];
        let dx = abs_difference(x1, x2) as i64;
        let dy = abs_difference(y1, y2) as i64;
        let sx = {
            if x1 < x2 {
                1
            } else {
                -1
            }
        };
        let sy = {
            if y1 < y2 {
                1
            } else {
                -1
            }
        };
        let mut err: i64 = dx - dy;
        let mut current_x = x1 as i64;
        let mut current_y = y1 as i64;
        loop {
            coordinates.push((current_x, current_y));
            if current_x == x2 as i64 && current_y == y2 as i64 {
                break;
            }
            let e2 = 2 * err;
            if e2 > -dy {
                err -= dy;
                current_x += sx;
            }
            if e2 < dx {
                err += dx;
                current_y += sy;
            }
        }
        coordinates
            .into_iter()
            .flat_map(|pt| MapPoint::try_from(pt))
            .filter(|&pt| self.contains(pt))
            .collect()
    }

    pub fn flood_fill(&mut self, start: MapPoint, target: T, replacement: T) -> Vec<MapPoint> {
        let mut queue = vec![start];
        let mut area = HashSet::new();
        loop {
            if queue.is_empty() {
                break area.drain().collect();
            } else {
                let last = queue.pop().unwrap();
                area.insert(last);
                [(1, 0), (0, 1), (-1, 0), (0, -1)]
                    .iter()
                    .filter_map(|(x, y)| {
                        MapPoint::try_from((last.x as i64 + x, last.y as i64 + y)).ok()
                    })
                    .filter(|&pt| {
                        self.contains(pt)
                            && self.get(pt) == target
                            && self.get(pt) != replacement
                            && !area.contains(&pt)
                    })
                    .for_each(|pt| queue.push(pt));
            }
        }
    }
}

impl Pixmap<bool> {
    pub fn invert(&mut self) {
        for px in self.data.iter_mut() {
            *px = !(*px);
        }
    }
}

fn abs_difference<T: Sub<Output = T> + Ord>(x: T, y: T) -> T {
    if x < y {
        y - x
    } else {
        x - y
    }
}

pub fn mirror_figure(figure: &[MapPoint], line: u32, axis: Axis) -> Vec<MapPoint> {
    figure
        .iter()
        .map(|pt| pt.mirror_about(line, axis))
        .collect()
}

pub fn reflect_figure(figure: &[MapPoint], around: MapPoint) -> Vec<MapPoint> {
    figure.iter().map(|pt| pt.reflect(around)).collect()
}

pub fn positive_angle_with_x(start: MapPoint, end: MapPoint) -> u32 {
    if end.x == start.x {
        return 90;
    }
    let numer = (end.y as f64 - start.y as f64).abs();
    let denum = (end.x as f64 - start.x as f64).abs();
    (numer / denum).atan().to_degrees() as u32
}