steiner-tree 0.0.1

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

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

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

#[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()
    }

    pub fn edge_weight_h(&self, idx: usize) -> T {
        self.xs[idx + 1] - self.xs[idx]
    }

    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)
    }

    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,
        }
    }

    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 {
                debug_assert!(is_bottom_boundary && !is_right_boundary);
                Point::new(p.x + 1, p.y)
            }
        };

        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,
    );
}

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