steiner-tree 0.0.1

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

//! Representation for the set of pins of a net.

use super::{HananCoord, Point};
use super::rectangle::Rect;
use super::hanan_grid::{UnitHananGrid, Boundary};
use super::marker_types::*;
use super::position_sequence::*;
use std::marker::PhantomData;
use smallvec::SmallVec;
use std::hash::{Hash, Hasher};

/// Representation for the set of pins of a net.
#[derive(Debug, Clone)]
pub struct Pins<C: CanonicalMarker = NonCanonical> {
    pin_locations: SmallVec<[Point<HananCoord>; crate::MAX_DEGREE]>,
    _canonical: PhantomData<C>,
}

impl PartialEq for Pins<Canonical> {
    fn eq(&self, other: &Self) -> bool {
        self.pin_locations.eq(&other.pin_locations)
    }
}

impl Eq for Pins<Canonical> {}

impl Hash for Pins<Canonical> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.pin_locations.hash(state)
    }
}

impl Pins<NonCanonical> {
    pub fn new(locations: SmallVec<[Point<HananCoord>; crate::MAX_DEGREE]>) -> Self {
        Pins {
            pin_locations: locations,
            _canonical: Default::default(),
        }
    }
    pub fn from_vec(locations: Vec<Point<HananCoord>>) -> Self {
        Self::new(locations.into())
    }
}

impl<C: CanonicalMarker> Pins<C> {
    pub fn into_non_canonical(self) -> Pins<NonCanonical> {
        Pins {
            pin_locations: self.pin_locations,
            _canonical: Default::default(),
        }
    }

    fn into_canonical_unchecked(self) -> Pins<Canonical> {
        let locations = self.pin_locations;
        // Check that is indeed canonical.
        debug_assert!(
            locations.iter().zip(locations.iter().skip(1)).all(|(a, b)| a <= b),
            "poins must be sorted."
        );

        Pins {
            pin_locations: locations,
            _canonical: Default::default(),
        }
    }

    /// Number of pins (counting duplicates).
    pub fn len(&self) -> usize {
        self.pin_locations.len()
    }

    pub fn contains(&self, p: Point<HananCoord>) -> bool {
        // TODO: Can use binary search if pin locations are sorted.
        self.pin_locations.contains(&p)
    }

    pub fn position_sequence(&self) -> PositionSequence {
        PositionSequence::from_points(&self.pin_locations)
    }

    /// Shift the all pin locations by the vector `(dx, dy)`.
    pub fn translate(mut self, (dx, dy): (HananCoord, HananCoord)) -> Self {
        self.pin_locations.iter_mut()
            .for_each(|p| {
                p.x += dx;
                p.y += dy;
            });
        self
    }

    /// Rotate the pin locations around the origin by 90 degrees counter-clock-wise.
    pub fn rotate_90ccw(mut self) -> Pins<NonCanonical> {
        self.pin_locations.iter_mut()
            .for_each(|p| *p = p.rotate_ccw90());
        self.into_non_canonical()
    }

    /// Mirror the pin locations at the y axis.
    pub fn mirror_at_y_axis(mut self) -> Pins<NonCanonical> {
        self.pin_locations.iter_mut()
            .for_each(|p| p.x = -p.x);
        self.into_non_canonical()
    }

    /// Compute the corners of the minimal bounding box of all pins.
    /// Returns none if the set of pins is empty.
    pub fn bounding_box(&self) -> Option<Rect<HananCoord>> {
        let mut nodes = self.pin_locations.iter().copied();
        nodes.next()
            .map(|first_node| {
                let mut lower_left = first_node;
                let mut upper_right = first_node;

                for n in nodes {
                    lower_left.x = lower_left.x.min(n.x);
                    lower_left.y = lower_left.y.min(n.y);
                    upper_right.x = upper_right.x.max(n.x);
                    upper_right.y = upper_right.y.max(n.y);
                }

                Rect::new(lower_left, upper_right)
            })
    }

    /// Convert to canonical form.
    pub fn into_canonical_form(mut self) -> Pins<Canonical> {
        if !C::is_canonical() {
            self.pin_locations.sort_unstable();
        }
        self.into_canonical_unchecked()
    }

    /// Remove duplicate pins.
    pub fn dedup(&mut self) {
        if !C::is_canonical() {
            self.pin_locations.sort_unstable();
        }
        self.pin_locations.dedup();
    }

    /// Move lower left corner to `(0, 0)`.
    pub fn move_to_origin(mut self) -> Self {
        if let Some(bb) = self.bounding_box() {
            let ll = bb.lower_left();
            self.translate((-ll.x, -ll.y))
        } else {
            self
        }
    }

    /// Compact the pins on a given boundary by shifting them by `1` in the opposite direction of the normal vector.
    /// Return the compaction result and a list of the pins which have been moved during this compaction.
    pub(crate) fn compact_boundary(mut self, grid: UnitHananGrid, boundary: Boundary)
        -> (Pins<NonCanonical>, SmallVec<[Point<HananCoord>; crate::MAX_DEGREE]>) {

        // Find translation direction of the boundary.
        let compaction_direction = match boundary {
            Boundary::Right => (-1, 0),
            Boundary::Top => (0, -1),
            Boundary::Left => (1, 0),
            Boundary::Bottom => (0, 1),
        };

        // Keep track of which points have been moved.
        let mut moved_points = SmallVec::new();

        self.pin_locations.iter_mut()
            .filter(|p| grid.is_on_partial_boundary(**p, boundary))
            .for_each(|p| {
                p.x += compaction_direction.0;
                p.y += compaction_direction.1;
                moved_points.push(*p);
            });

        (self.into_non_canonical(), moved_points)
    }

    pub fn pin_locations(&self) -> impl Iterator<Item=Point<HananCoord>> + '_ {
        self.pin_locations.iter().copied()
    }

    pub fn remove_pins<F>(&mut self, f: F)
        where F: Fn(&Point<HananCoord>) -> bool {
        self.pin_locations.retain(|p| !f(p))
    }

    pub fn add_pin(&mut self, p: Point<HananCoord>) {
        if C::is_canonical() {
            // Preserve ordering.
            let found = self.pin_locations.binary_search(&p);

            let insertion_idx = match found {
                Ok(i) => i,
                Err(i) => i,
            };

            self.pin_locations.insert(insertion_idx, p);
        } else {
            self.pin_locations.push(p);
        }
    }
}

impl Pins<NonCanonical> {
    pub fn pin_locations_mut(&mut self) -> impl Iterator<Item=&mut Point<HananCoord>> + '_ {
        self.pin_locations.iter_mut()
    }
}

#[test]
fn test_boundary_compaction() {
    let pins = Pins::from_vec(vec![(0, 0).into(), (1, 1).into(), (2, 2).into()]);
    let expected_compaction_result = Pins::from_vec(vec![(0, 0).into(), (1, 1).into(), (2, 1).into()]).into_canonical_form();

    // Compact top boundary.
    let grid = UnitHananGrid::new(pins.bounding_box().unwrap());
    let (compacted, moved_points) = pins.compact_boundary(grid, Boundary::Top);

    assert_eq!(compacted.into_canonical_form(), expected_compaction_result);
    assert_eq!(moved_points.to_vec(), vec![(2, 1).into()]);
}