steiner-tree 0.0.1

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

//! Implementation of boundary compaction and expansion.

use crate::HananCoord;
use super::pins::*;
use super::tree::*;
use super::point::*;
use super::marker_types::Canonical;

use super::hanan_grid::{Boundary, UnitHananGrid};
use itertools::Itertools;
use smallvec::SmallVec;

#[derive(Debug, Clone)]
pub(crate) struct CompactionStage {
    grid: UnitHananGrid,
    current_pins: Pins<Canonical>,
}

/// Defines necessary operation to undo a compaction by expanding the pins.
pub struct ExpansionOp {
    /// The boundary which was compacted and now must be expanded.
    boundary: Boundary,
    /// Pins that need to be moved with the boundary.
    pins_to_expand: SmallVec<[Point<HananCoord>; crate::MAX_DEGREE]>
}

impl CompactionStage {
    pub fn new(grid: UnitHananGrid, pins: Pins<Canonical>) -> CompactionStage {
        debug_assert_eq!(Some(grid.rect()), pins.bounding_box(), "grid boundary must be equal to the bounding box of the pins.");

        Self {
            grid,
            current_pins: pins,
        }
    }
}


impl CompactionStage {
    pub fn grid(&self) -> UnitHananGrid {
        self.grid
    }

    pub fn current_pins(&self) -> &Pins<Canonical> {
        &self.current_pins
    }

    pub fn compact_boundary(mut self, boundary: Boundary) -> (Self, ExpansionOp) {

        // Compact the pins.
        let (new_pins, moved_pins) = self.current_pins.compact_boundary(self.grid, boundary);
        self.current_pins = new_pins.into_canonical_form();

        // Compact the grid.
        self.grid = self.grid.compact_boundary(boundary);

        // Sanity check:
        debug_assert_eq!(
            self.current_pins.bounding_box(), Some(self.grid.rect()),
            "the bounding box of all pins must be the same as the grid dimension"
        );

        // Store information necessary to do the expansion.
        let expansion_op = ExpansionOp {
            boundary,
            pins_to_expand: moved_pins
        };

        (self, expansion_op)
    }
}

#[test]
fn test_compaction() {
    let pins = Pins::from_vec(vec![(0, 0).into(), (2, 2).into()]).into_canonical_form();
    let grid = UnitHananGrid::new(pins.bounding_box().unwrap());
    let compaction_stage = CompactionStage::new(grid, pins);

    let (compacted, _) = compaction_stage.compact_boundary(Boundary::Top);


    assert_eq!(compacted.grid.rect(), compacted.current_pins.bounding_box().unwrap());

    assert_eq!(
        compacted.current_pins.into_canonical_form(),
        Pins::from_vec(vec![(0, 0).into(), (2, 1).into()]).into_canonical_form()
    );
}

#[derive(Debug)]
pub(crate) struct ExpansionStage {
    grid: UnitHananGrid,
    current_pins: Pins<Canonical>,
    tree: Tree,
}

impl ExpansionStage {
    pub fn new(compaction_stage: CompactionStage, initial_tree: Tree) -> ExpansionStage {
        debug_assert!(
            {
                let num_dedup_pins = compaction_stage.current_pins.pin_locations()
                    .dedup()
                    .count();
                num_dedup_pins == 1 || compaction_stage.current_pins.pin_locations()
                    .all(|p| initial_tree.contains_node(p))
            },
            "initial tree must connect all compacted pins"
        );

        Self {
            grid: compaction_stage.grid,
            current_pins: compaction_stage.current_pins.into_canonical_form(),
            tree: initial_tree,
        }
    }


    pub fn grid(&self) -> UnitHananGrid {
        self.grid
    }

    pub fn tree(&self) -> &Tree {
        &self.tree
    }

    pub fn current_pins(&self) -> &Pins<Canonical> {
        &self.current_pins
    }

    pub fn into_tree(self) -> Tree {
        self.tree
    }

    pub fn num_pins(&self) -> usize {
        self.current_pins.len()
    }

    /// Undo the compaction operation on the top of the stack and construct the tree.
    pub fn expand_boundary(mut self, expansion_op: &ExpansionOp) -> Self {

        let boundary = expansion_op.boundary;
        let points_to_be_moved = &expansion_op.pins_to_expand;


        debug_assert!(
          points_to_be_moved.iter()
              .zip(points_to_be_moved.iter().skip(1))
              .all(|(a, b)| a <= b),
              "points must be sorted"
        );

        if !self.tree.is_empty() {
            debug_assert_eq!(
                self.tree.bounding_box(), Some(self.grid.rect()),
                "the bounding box of the tree must be the same as the grid dimension"
            );
        }

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


        // Find the pins which are on the boundary which gets expanded.

        // Compute multi-set difference: D = 'current points on boundary' - 'original points on boundary'
        // Points in D will be shifted with the boundary and create new edges in the tree.

        // Important: The points are sorted because the `Pins` is in canonical form.
        let mut current_pins = self.current_pins.into_non_canonical();
        let current_pins_on_boundary = current_pins
            .pin_locations_mut()
            .filter(|p| self.grid.is_on_partial_boundary(**p, boundary));


        let mut pins_to_be_moved = points_to_be_moved.into_iter()
            .copied()
            .peekable();

        // Remember last tree edge to avoid creating duplicates.
        let mut last_added_tree_edge = None;

        for current_pin in current_pins_on_boundary {
            if let Some(to_be_moved) = pins_to_be_moved.peek().clone() {
                debug_assert!(to_be_moved >= current_pin);
            }

            if Some(&*current_pin) == pins_to_be_moved.peek() {
                // Current pin should be moved.

                // Move the pin with the boundary.
                let current_pin_before = *current_pin;
                {
                    current_pin.x += expansion_direction.0;
                    current_pin.y += expansion_direction.1;
                }

                // Create a tree edge.
                {
                    let edge = match boundary {
                        Boundary::Left => TreeEdge::new(*current_pin, EdgeDirection::Right),
                        Boundary::Bottom => TreeEdge::new(*current_pin, EdgeDirection::Up),
                        Boundary::Right => TreeEdge::new(current_pin_before, EdgeDirection::Right),
                        Boundary::Top => TreeEdge::new(current_pin_before, EdgeDirection::Up),
                    };

                    if Some(edge) != last_added_tree_edge {
                        self.tree.add_edge_unchecked(edge);
                        debug_assert!(self.tree.is_tree())
                    } else {
                        // Tree edge is already inserted.
                    }

                    last_added_tree_edge = Some(edge);
                }

                // Done, drop the pin.
                pins_to_be_moved.next();
            }
        }

        self.current_pins = current_pins.into_canonical_form();

        // Enlarge the grid.
        self.grid = self.grid.expand_boundary(boundary);

        // Sanity checks:
        debug_assert_eq!(
            self.current_pins.bounding_box(), Some(self.grid.rect()),
            "the bounding box of all pins must be the same as the grid dimension"
        );
        debug_assert_eq!(
            self.tree.bounding_box(), Some(self.grid.rect()),
            "the bounding box of the tree must be the same as the grid dimension"
        );
        debug_assert!(
            self.current_pins.pin_locations().all(|p| self.tree.contains_node(p)),
            "all current pins must be covered by the tree"
        );

        self
    }
}

#[test]
fn test_compaction_then_expansion() {
    // Pin locations:
    //          x
    //
    // x
    let pins = Pins::from_vec(vec![(0, 0).into(), (2, 2).into()]).into_canonical_form();
    let grid = UnitHananGrid::new(pins.bounding_box().unwrap());

    let boundary = Boundary::Top;

    let compaction_stage = CompactionStage::new(grid, pins.clone());
    let (compacted1, expansion_op1) = compaction_stage.compact_boundary(boundary);
    let (compacted2, expansion_op2) = compacted1.compact_boundary(boundary);
    // Pin locations after compaction:
    // x        x

    // Initial tree:
    // x--------x
    let mut initial_tree = Tree::empty_non_canonical();
    initial_tree.add_edge(TreeEdge::new((0, 0).into(), EdgeDirection::Right))
        .add_edge(TreeEdge::new((1, 0).into(), EdgeDirection::Right));


    let expansion_stage = ExpansionStage::new(compacted2, initial_tree);
    let expanded = expansion_stage
        .expand_boundary(&expansion_op2)
        .expand_boundary(&expansion_op1);

    // Should be back to the original state now.
    assert_eq!(&pins, &expanded.current_pins);

    // Expected tree:
    //          x
    //          |
    // x--------|
    let mut expected_tree = Tree::empty_non_canonical();
    expected_tree.add_edge(TreeEdge::new((0, 0).into(), EdgeDirection::Right))
        .add_edge(TreeEdge::new((1, 0).into(), EdgeDirection::Right))
        .add_edge(TreeEdge::new((2, 0).into(), EdgeDirection::Up))
        .add_edge(TreeEdge::new((2, 1).into(), EdgeDirection::Up));
    assert_eq!(expanded.tree.into_canonical_form(), expected_tree.into_canonical_form());
}