steiner-tree 0.0.5

// SPDX-FileCopyrightText: 2022 Thomas Kramer <code@tkramer.ch>
//
// SPDX-License-Identifier: GPL-3.0-or-later

use std::ops::{Add, Sub};

use super::point::*;
use super::rectangle::Rect;
use crate::HananCoord;

/// A rectilinear grid which is defined by a set of
/// vertical and horizontal grid lines.
#[derive(Clone, Debug)]
pub struct HananGridWithCoords<T> {
    /// x-coordinates of the vertical grid lines.
    pub xs: Vec<T>,
    /// y-coordinates of the horizontal grid lines.
    pub ys: Vec<T>,
}

impl<T> HananGridWithCoords<T>
where
    T: Ord + Copy + Sub<Output = T> + Add<Output = T>,
{
    pub fn num_x(&self) -> usize {
        self.xs.len()
    }

    pub fn num_y(&self) -> usize {
        self.ys.len()
    }

    /// Distance between horizontal grid line at index `idx` and line at index `idx+1`.
    pub fn edge_weight_h(&self, idx: usize) -> T {
        self.xs[idx + 1] - self.xs[idx]
    }

    /// Distance between vertical grid line at index `idx` and line at index `idx+1`.
    pub fn edge_weight_v(&self, idx: usize) -> T {
        self.ys[idx + 1] - self.ys[idx]
    }
}

/// Hanan grid with unit distances between grid lines.
#[derive(Copy, Clone, Debug)]
pub struct UnitHananGrid {
    rect: Rect<HananCoord>,
}

impl UnitHananGrid {
    pub fn new(rect: Rect<HananCoord>) -> Self {
        Self { rect }
    }

    /// Get the rectangle which defines the boundary of the hanan grid.
    pub fn rect(&self) -> Rect<HananCoord> {
        self.rect
    }

    /// Test if a point is on the boundary of the hanan grid.
    pub fn is_on_boundary(&self, p: Point<HananCoord>) -> bool {
        self.rect.is_on_boundary(p)
    }

    /// Test if a point is on a partial boundary of the hanan grid.
    pub fn is_on_partial_boundary(&self, p: Point<HananCoord>, boundary: Boundary) -> bool {
        self.contains_point(p)
            && match boundary {
                Boundary::Right => p.x == self.upper_right().x,
                Boundary::Top => p.y == self.upper_right().y,
                Boundary::Left => p.x == self.lower_left().x,
                Boundary::Bottom => p.y == self.lower_left().y,
            }
    }

    /// Test if a point is on the corner of the grid.
    pub fn is_corner(&self, p: Point<HananCoord>) -> bool {
        (p.x == self.lower_left().x || p.x == self.upper_right().x)
            && (p.y == self.lower_left().y || p.y == self.upper_right().y)
    }

    pub fn contains_point(&self, p: Point<HananCoord>) -> bool {
        self.rect.contains_point(p)
    }

    /// Endless iterator over boundary points.
    pub fn all_boundary_points(&self, start: Point<HananCoord>) -> HananBoundaryIterator {
        assert!(
            self.is_on_boundary(start),
            "start point must be on the boundary"
        );

        HananBoundaryIterator {
            grid: *self,
            next_point: start,
        }
    }

    /// Iterate over all points of the grid by creating a spiral which starts at `(0, 0)`.
    pub fn all_points_spiral(&self) -> impl Iterator<Item = Point<HananCoord>> + '_ {
        let ur = self.rect.upper_right();
        let ll = self.rect.lower_left();
        let width = ur.x.max(-ll.x);
        let height = ur.y.max(-ll.y);
        let max_spiral_radius = width.max(height);

        /// Iterate over points circles, like onion layers.
        /// Until all the grid points are covered.
        (0..max_spiral_radius + 1)
            .flat_map(|r| {
                debug_assert!(r >= 0);
                let p1 = Point::new(-r, -r);
                let p2 = Point::new(r, r);

                let inner_grid = UnitHananGrid::new(Rect::new(p1, p2));

                inner_grid
                    .all_boundary_points(Point::new(r, 0))
                    .take((r as usize * 8).max(1))
            })
            .filter(|p| self.contains_point(*p))
    }

    pub fn boundary_points(&self, boundary: Boundary) -> HananPartialBoundaryIterator {
        HananPartialBoundaryIterator::new(*self, boundary)
    }

    pub fn lower_left(&self) -> Point<HananCoord> {
        self.rect.lower_left()
    }
    pub fn lower_right(&self) -> Point<HananCoord> {
        self.rect.lower_right()
    }
    pub fn upper_right(&self) -> Point<HananCoord> {
        self.rect.upper_right()
    }
    pub fn upper_left(&self) -> Point<HananCoord> {
        self.rect.upper_left()
    }

    /// Move the given boundary towards the center of the grid.
    /// Panics when the boundary would surpass it's opposite boundary.
    pub fn compact_boundary(&self, boundary: Boundary) -> Self {
        // Sanity check.
        match boundary {
            Boundary::Left | Boundary::Right => assert!(
                self.rect.width() > 0,
                "cannot compact left or right boundary if width is zero"
            ),
            Boundary::Bottom | Boundary::Top => assert!(
                self.rect.height() > 0,
                "cannot compact bottom or top boundary if width is zero"
            ),
        }

        let mut ll = self.rect.lower_left();
        let mut ur = self.rect.upper_right();

        match boundary {
            Boundary::Right => ur.x -= 1,
            Boundary::Top => ur.y -= 1,
            Boundary::Left => ll.x += 1,
            Boundary::Bottom => ll.y += 1,
        }

        Self::new(Rect::new(ll, ur))
    }

    /// Move the given boundary away from the center of the grid.
    pub fn expand_boundary(&self, boundary: Boundary) -> Self {
        let mut ll = self.rect.lower_left();
        let mut ur = self.rect.upper_right();

        match boundary {
            Boundary::Right => ur.x += 1,
            Boundary::Top => ur.y += 1,
            Boundary::Left => ll.x -= 1,
            Boundary::Bottom => ll.y -= 1,
        }

        Self::new(Rect::new(ll, ur))
    }
}

#[derive(Clone, Debug)]
pub struct HananPartialBoundaryIterator {
    grid: UnitHananGrid,
    next_point: Point<HananCoord>,
    direction: (HananCoord, HananCoord),
}

impl HananPartialBoundaryIterator {
    fn new(grid: UnitHananGrid, boundary: Boundary) -> Self {
        let (start, direction) = match boundary {
            Boundary::Right => (grid.lower_right(), (0, 1)),
            Boundary::Top => (grid.upper_left(), (1, 0)),
            Boundary::Left => (grid.lower_left(), (0, 1)),
            Boundary::Bottom => (grid.lower_left(), (1, 0)),
        };

        Self {
            grid,
            next_point: start,
            direction,
        }
    }
}

impl Iterator for HananPartialBoundaryIterator {
    type Item = Point<HananCoord>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.grid.contains_point(self.next_point) {
            let p = self.next_point;
            self.next_point.x += self.direction.0;
            self.next_point.y += self.direction.1;
            Some(p)
        } else {
            None
        }
    }
}

/// Iterator which loops endlessly over the boundary points of a hanan grid.
/// Orientation is counter-clock-wise.
#[derive(Clone, Debug)]
pub struct HananBoundaryIterator {
    grid: UnitHananGrid,
    next_point: Point<HananCoord>,
}

impl DoubleEndedIterator for HananBoundaryIterator {
    fn next_back(&mut self) -> Option<Self::Item> {
        let p = self.next_point;

        // Find the new next point.
        self.next_point = {
            let is_left_boundary = p.x == self.grid.lower_left().x;
            let is_right_boundary = p.x == self.grid.upper_right().x;
            let is_bottom_boundary = p.y == self.grid.lower_left().y;
            let is_top_boundary = p.y == self.grid.upper_right().y;

            if is_right_boundary && !is_bottom_boundary {
                Point::new(p.x, p.y - 1)
            } else if is_top_boundary && !is_right_boundary {
                Point::new(p.x + 1, p.y)
            } else if is_left_boundary && !is_top_boundary {
                Point::new(p.x, p.y + 1)
            } else {
                debug_assert!(is_bottom_boundary && !is_left_boundary);
                Point::new(p.x - 1, p.y)
            }
        };

        debug_assert!(self.grid.contains_point(self.next_point));

        Some(p)
    }
}

impl Iterator for HananBoundaryIterator {
    type Item = Point<HananCoord>;

    fn next(&mut self) -> Option<Self::Item> {
        let p = self.next_point;

        // Find the new next point.
        self.next_point = {
            let is_left_boundary = p.x == self.grid.lower_left().x;
            let is_right_boundary = p.x == self.grid.upper_right().x;
            let is_bottom_boundary = p.y == self.grid.lower_left().y;
            let is_top_boundary = p.y == self.grid.upper_right().y;

            if is_right_boundary && !is_top_boundary {
                Point::new(p.x, p.y + 1)
            } else if is_top_boundary && !is_left_boundary {
                Point::new(p.x - 1, p.y)
            } else if is_left_boundary && !is_bottom_boundary {
                Point::new(p.x, p.y - 1)
            } else if is_bottom_boundary && !is_right_boundary {
                Point::new(p.x + 1, p.y)
            } else {
                p
            }
        };

        debug_assert!(self.grid.contains_point(self.next_point));

        Some(p)
    }
}

#[test]
fn test_hanan_boundary_iter() {
    let grid = UnitHananGrid::new(Rect::new((0, 0).into(), (1, 2).into()));
    let start = Point::new(1, 1);
    let boundary_points: Vec<_> = grid.all_boundary_points(start).take(6).collect();
    let expected_boundary_points: Vec<_> = vec![(1, 1), (1, 2), (0, 2), (0, 1), (0, 0), (1, 0)]
        .into_iter()
        .map(|c| c.into())
        .collect();
    assert_eq!(boundary_points, expected_boundary_points,);
}

#[test]
fn test_hanan_grid_spiral_iter() {
    let grid = UnitHananGrid::new(Rect::new((-1, -1).into(), (1, 1).into()));

    let spiral_points: Vec<_> = grid.all_points_spiral().collect();

    let expected: Vec<_> = vec![
        (0, 0),
        (1, 0),
        (1, 1),
        (0, 1),
        (-1, 1),
        (-1, 0),
        (-1, -1),
        (0, -1),
        (1, -1),
    ]
    .into_iter()
    .map(|c| c.into())
    .collect();

    assert_eq!(spiral_points, expected,);
}

/// Identifier for the four boundary edges of the grid.
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
pub enum Boundary {
    Right,
    Top,
    Left,
    Bottom,
}