steiner_tree/

gen_lut.rs

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

//! Generate the lookup-table.

//use rayon::prelude::*;
use std::sync;
use std::time;

use super::lut::*;
use super::marker_types::Canonical;
use super::permutations;
use super::pins::*;
use super::point::*;
use super::position_sequence::*;
use super::rectangle::*;
use super::tree::*;

use super::compaction_expansion::*;
use super::hanan_grid::{Boundary, UnitHananGrid};
use super::wirelength_vector::*;

use super::HananCoord;
use super::MAX_DEGREE;
use itertools::Itertools;
use smallvec::SmallVec;
use std::cmp::Ordering;
use std::collections::HashMap;

/// Generate the lookup-table for all nets with number of pins up to `max_degree`.
pub fn gen_full_lut(max_degree: usize) -> LookupTable {
    let mut cache = Cache::new();

    let sub_lut_by_degree = (2..=max_degree)
        .map(|num_pins| gen_sub_lut(num_pins, &mut cache))
        .collect();

    LookupTable { sub_lut_by_degree }
}

#[test]
fn test_gen_full_lut() {
    let max_degree = 5;
    let lut = gen_full_lut(max_degree);
    assert_eq!(lut.sub_lut_by_degree.len(), max_degree - 1);
}

/// Generate the sub lookup-table for all nets with `num_pins` pins.
fn gen_sub_lut(num_pins: usize, cache: &mut Cache) -> SubLookupTable {
    let pos_sequences = deduplicated_position_sequences(num_pins);

    assert!(num_pins > 0);

    // let mutex_cache = sync::Arc::new(sync::Mutex::new(cache));
    let num_entries = pos_sequences.len();

    let lut_entries: Vec<ValuesOrRedirect> = pos_sequences
        // .into_par_iter()
        .into_iter()
        .enumerate()
        // .map_with(cache, |mut cache, (i, position_sequence)| {
        .map(|(i, position_sequence)| {
            // if i % 1000 == 0 || i+1 == num_entries {
            //     println!("progress: {:.1}%", ((100 * (i + 1)) as f64) / (num_entries as f64));
            // }

            match position_sequence {
                PositionSequenceOrRedirect::PositionSequence(position_sequence) => {
                    // Compute the potential optimal wirelength vectors and trees for this position sequence.
                    let pins = Pins::from_vec(position_sequence.to_points().collect())
                        .into_canonical_form();
                    let grid = UnitHananGrid::new(
                        pins.bounding_box()
                            .unwrap_or(Rect::new((0, 0).into(), (0, 0).into())),
                    );
                    let compaction_stage = CompactionStage::new(grid, pins);

                    let trees = gen_lut(compaction_stage, cache);
                    let values = trees
                        .into_iter()
                        .map(|e| {
                            let grid = e.grid();
                            let mut wv = WirelenghtVector::zero(
                                grid.upper_right().x as usize,
                                grid.upper_right().y as usize,
                            );
                            e.tree().compute_wirelength_vector(&mut wv);
                            (wv, e.into_tree())
                        })
                        .map(|(wv, tree)| LutValue {
                            potential_optimal_wirelength_vector: wv,
                            potential_optimal_steiner_tree: tree.into_canonical_form(),
                        })
                        .collect();
                    ValuesOrRedirect::Values(values)
                }
                PositionSequenceOrRedirect::Redirect {
                    group_index,
                    transform,
                } => ValuesOrRedirect::Redirect {
                    group_index,
                    transform,
                },
            }
        })
        .collect();

    SubLookupTable {
        values: lut_entries,
    }
}

#[test]
fn test_gen_sub_lut() {
    let sub_lut = gen_sub_lut(6, &mut Cache::new());
    assert_eq!(sub_lut.values.len(), 1 * 2 * 3 * 4 * 5 * 6);
}

/// Get a list of all position sequences for the given number of pins.
/// The position sequences are indexed by their 'group index' (which is the rank of the permutation).
/// The position sequences are de-duplicated.
/// Position sequences which are equivalent under rotation (by 90 degrees) and mirroring along an axis form an equivalence class.
/// Only one position sequence is stored per equivalence class. All other members of the class are stored as
/// a link to the first one together with the necessary geometrical transformation.
fn deduplicated_position_sequences(num_pins: usize) -> Vec<PositionSequenceOrRedirect> {
    let num_entries = permutations::factorial(num_pins);

    let mut position_sequences: Vec<_> = (0..num_entries).map(|_| None).collect();

    for positions_sequence in permutations::all_position_sequences(num_pins) {
        let group_index = positions_sequence.group_index();

        if position_sequences[group_index].is_none() {
            let points = Pins::from_vec(positions_sequence.to_points().collect());

            // Store the position sequence.
            assert!(position_sequences[group_index].is_none());
            position_sequences[group_index] = Some(PositionSequenceOrRedirect::PositionSequence(
                positions_sequence,
            ));

            // Create links from equivalent groups (under rotation and mirroring) to this group.
            {
                let mut points = points;
                for mirror in [false, true] {
                    debug_assert_eq!(group_index, points.position_sequence().group_index());
                    if mirror {
                        points = points.mirror_at_y_axis()
                    }
                    for rot in 1..5 {
                        if mirror && rot == 4 {
                            // Skip last transformation. This is equal to the identity again.
                            break;
                        }
                        points = points.rotate_90ccw();

                        let redirected_group = points.position_sequence().group_index();

                        let transform = Transform::new(rot, mirror).inverse();

                        let redirect = PositionSequenceOrRedirect::Redirect {
                            group_index,
                            transform,
                        };

                        // Store the redirection.
                        if position_sequences[redirected_group].is_none() {
                            position_sequences[redirected_group] = Some(redirect)
                        }
                    }
                }
            }
        }
    }

    // Convert to output format.
    position_sequences
        .into_iter()
        .map(|p| p.expect("A group index is not present."))
        .collect()
}

#[test]
fn test_deduplicated_position_sequences() {
    for n in 0..6 + 1 {
        let n_factorial = (1..n + 1).product();
        let dedup_sequences = deduplicated_position_sequences(n);

        assert_eq!(dedup_sequences.len(), n_factorial);

        let num_non_redirects = dedup_sequences.iter().filter(|s| !s.is_redirect()).count();

        assert!(num_non_redirects > 0);

        let non_redirect_ratio = (n_factorial as f64) / (num_non_redirects as f64);
        assert!(non_redirect_ratio <= 4.0); // The number of deduplicated entries is indeed in the order of n!/4.
        assert!(non_redirect_ratio >= 1.0);
    }
}

#[derive(Debug, Clone, Hash, Eq, PartialEq)]
enum PositionSequenceOrRedirect {
    PositionSequence(PositionSequence),
    Redirect {
        /// Target group address.
        group_index: usize,
        /// Transformation that needs to be applied to get from the current group to the redirect.
        transform: Transform,
    },
}

impl PositionSequenceOrRedirect {
    fn is_redirect(&self) -> bool {
        match self {
            PositionSequenceOrRedirect::PositionSequence(_) => false,
            _ => true,
        }
    }
}

/// Generate the lookup-table entries for the given grid and set of pins.
///
/// Corresponds to algorithm 'Gen-LUT(G)' in the paper.
///
fn gen_lut(compaction_stage: CompactionStage, cache: &mut Cache) -> Vec<ExpansionStage> {
    let grid = compaction_stage.grid();

    // Use the cache only for smaller trees. Starting from 6x6 downwards seems to be a good choice.
    // Caching only smaller trees reduces memory usage.
    let use_cache = grid.rect().width() <= 6 && grid.rect().height() <= 6;

    let cache_key = if use_cache {
        let mut normalized_pins = compaction_stage.current_pins().clone();
        normalized_pins.dedup();
        Some(normalized_pins.move_to_origin())
    } else {
        None
    };

    // Check cache.
    if let Some(cache_key) = &cache_key {
        let cache_result: Option<Vec<ExpansionStage>> = cache.with(cache_key, |r| {
            r.map(|trees| {
                // Cache hit.
                let lower_left = grid.lower_left();

                trees
                    .into_iter()
                    .map(|tree| {
                        let mut tree = tree.clone();
                        tree.translate((lower_left.x, lower_left.y));
                        tree
                    })
                    .map(|tree| ExpansionStage::new(compaction_stage.clone(), tree))
                    .collect()
            })
        });

        if let Some(mut cache_result) = cache_result {
            let unpruned_length = cache_result.len();
            debug_assert_eq!(
                {
                    prune_inplace(&mut cache_result);
                    cache_result.len()
                },
                unpruned_length,
                "cache content must be pruned already"
            );

            return cache_result;
        }
    }

    let trees: Vec<ExpansionStage> =
        if let Some(simple_trees) = create_simple_trees(grid, compaction_stage.current_pins()) {
            // Found simple solutions.
            // Convert them to LutValues.

            simple_trees
                .into_iter()
                .map(|tree| ExpansionStage::new(compaction_stage.clone(), tree))
                .collect()
        } else {
            // Compact boundaries and call recursively.
            // Rule 1.
            if let Some(boundary) = find_boundary_with_one_pin(&compaction_stage) {
                // Compact
                let (compacted, expansion_op) = compaction_stage.compact_boundary(boundary);
                // Generate smaller trees.
                let trees = gen_lut(compacted, cache);
                // Expand
                trees
                    .into_iter()
                    .map(|e| e.expand_boundary(&expansion_op))
                    .collect()
            }
            // Rule 2.
            else if let Some((b1, b2)) =
                find_two_adjacent_boundaries_with_shared_pin_in_corner(&compaction_stage)
            {
                let (compacted_b1, expansion_op_b1) = compaction_stage.clone().compact_boundary(b1);
                let (compacted_b2, expansion_op_b2) = compaction_stage.compact_boundary(b2);

                let trees_b1 = gen_lut(compacted_b1, cache);
                let trees_b2 = gen_lut(compacted_b2, cache);

                let expanded_b1 = trees_b1
                    .into_iter()
                    .map(|t| t.expand_boundary(&expansion_op_b1));

                let expanded_b2 = trees_b2
                    .into_iter()
                    .map(|t| t.expand_boundary(&expansion_op_b2));

                let union = expanded_b1.chain(expanded_b2).collect();

                prune(union)
            }
            // Rule 3
            else {
                let num_pins = compaction_stage
                    .current_pins()
                    .pin_locations()
                    .dedup()
                    .count();
                let num_pins_on_boundary = compaction_stage
                    .current_pins()
                    .pin_locations()
                    .filter(|p| grid.is_on_boundary(*p))
                    .dedup()
                    .count();

                let s = if num_pins == 7 && num_pins_on_boundary == 7 {
                    // Create trees with near-ring structure (i.e. a ring around the boundary with one edge removed).
                    create_near_ring_trees(&compaction_stage)
                        .map(|tree| ExpansionStage::new(compaction_stage.clone(), tree))
                        .collect()
                } else if num_pins >= 8 && num_pins_on_boundary >= 7 {
                    // connect_adj_pins
                    let d = num_pins - 3;
                    connect_adj_pins(&compaction_stage, d as HananCoord, cache)
                } else {
                    vec![]
                };

                // Compact+expand on all boundaries.
                let all_boundary_expansions = [
                    Boundary::Left,
                    Boundary::Right,
                    Boundary::Top,
                    Boundary::Bottom,
                ]
                .iter()
                .flat_map(|b| {
                    let (compacted, expansion_op) = compaction_stage.clone().compact_boundary(*b);
                    let trees = gen_lut(compacted, cache);
                    // Expand all.
                    trees
                        .into_iter()
                        .map(move |t| t.expand_boundary(&expansion_op))
                });

                let union = s.into_iter().chain(all_boundary_expansions).collect();

                prune(union)
            }
        };

    if let Some(cache_key) = &cache_key {
        // Store trees to cache.

        let contains_key = cache.with(&cache_key, |r| r.is_some());
        if !contains_key {
            cache.insert(cache_key.clone(), vec![]);
        }

        cache.with_mut(&cache_key, |cache_entry| {
            let cache_entry = cache_entry.unwrap();
            for tree in &trees {
                cache_entry.push(tree.tree().clone().translate_to_origin());
            }
        });
    }

    debug_assert!(
        trees.iter().all(|t| t.tree().is_tree()),
        "generated an invalid tree"
    );

    trees
}

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

    let compaction_stage = CompactionStage::new(grid, pins);

    let trees = gen_lut(compaction_stage, &mut Default::default());
    dbg!(trees.len());
}

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

    let compaction_stage = CompactionStage::new(grid, pins);

    let trees = gen_lut(compaction_stage, &mut Default::default());
    dbg!(trees.len());

    dbg!(trees);
}

fn prune(mut trees: Vec<ExpansionStage>) -> Vec<ExpansionStage> {
    prune_inplace(&mut trees);
    trees
}

/// Deduplicate and remove all trees which are not on the pareto front regarding their wirelength vectors.
fn prune_inplace(trees: &mut Vec<ExpansionStage>) {
    debug_assert!(
        trees.iter().map(|e| e.num_pins()).all_equal(),
        "all trees must have the same number of pins"
    );

    // Compute all wirelength vectors.
    let mut wirelength_vectors: Vec<_> = trees
        .iter()
        .map(|e| {
            let grid = e.grid();
            let mut wv = WirelenghtVector::zero(
                grid.upper_right().x as usize,
                grid.upper_right().y as usize,
            );
            e.tree().compute_wirelength_vector(&mut wv);
            wv
        })
        .collect();

    // Remove non-pareto optimal trees.
    let mut i = 0;
    while i < trees.len() {
        assert_eq!(trees.len(), wirelength_vectors.len());

        let mut j = i + 1;
        while j < wirelength_vectors.len() {
            let wv_i = &wirelength_vectors[i];
            let wv_j = &wirelength_vectors[j];
            let cmp = wv_j.partial_cmp(wv_i);
            if cmp == Some(Ordering::Greater) || cmp == Some(Ordering::Equal) {
                // tree_i makes tree_j redundant or even inferior.
                wirelength_vectors.swap_remove(j);
                trees.swap_remove(j);
                // Don't increment j, because new element has been moved to index j.
            } else if cmp == Some(Ordering::Less) {
                // tree_i is dominated by tree_j.
                trees.swap(i, j);
                wirelength_vectors.swap(i, j);
                trees.swap_remove(j);
                wirelength_vectors.swap_remove(j);

                // Better tree has been moved to i. Need to rewind to i+1 again.
                j = i + 1;
            } else {
                j += 1;
            }
        }

        i += 1;
    }
}

/// Find a boundary which contains exactly one pin (when pins are deduplicated).
/// Returns `None` if none is found.
fn find_boundary_with_one_pin(compaction_stage: &CompactionStage) -> Option<Boundary> {
    let grid = compaction_stage.grid();
    [
        Boundary::Right,
        Boundary::Top,
        Boundary::Left,
        Boundary::Bottom,
    ]
    .into_iter()
    .filter(|&b| {
        let num_pins_on_boundary = compaction_stage
            .current_pins()
            .pin_locations()
            .filter(|&p| grid.is_on_partial_boundary(p, b))
            .dedup() // Can deduplicate because pins are sorted.
            .count();
        num_pins_on_boundary == 1
    })
    .next()
}

/// Find two adjacent boundaries which contain three pins in total and have one pin in the shared corner.
fn find_two_adjacent_boundaries_with_shared_pin_in_corner(
    compaction_stage: &CompactionStage,
) -> Option<(Boundary, Boundary)> {
    let grid = compaction_stage.grid();

    let boundaries = [
        Boundary::Right,
        Boundary::Top,
        Boundary::Left,
        Boundary::Bottom,
    ];
    let corners = [
        grid.upper_right(),
        grid.upper_left(),
        grid.lower_left(),
        grid.lower_right(),
    ];
    let mut boundary_pin_count = [0usize; 4];
    let mut corner_pin_count = [0usize; 4];

    // Iterate over all points and keep track of number of points on boundaries and corners.
    compaction_stage
        .current_pins()
        .pin_locations()
        .dedup()
        .for_each(|p| {
            // Increment all pin counters of boundaries which contain `p`.
            boundary_pin_count
                .iter_mut()
                .zip(&boundaries)
                .filter(|(_, b)| grid.is_on_partial_boundary(p, **b))
                .for_each(|(pin_count, _)| {
                    *pin_count += 1;
                });

            // If `p` is a corner, increment the corner pin count.
            if grid.is_corner(p) {
                // Increment the correct corner counter.
                corners
                    .iter()
                    .zip(corner_pin_count.iter_mut())
                    .find(|(corner, _)| corner == &&p) // Find the correct corner counter.
                    .into_iter()
                    // Increment the counter, if any.
                    .for_each(|(_, count)| {
                        *count += 1;
                    });
            }
        });

    let corners_with_one_pin = corner_pin_count
        .iter()
        .enumerate()
        .filter(|(i, count)| **count == 1)
        .map(|(i, _)| i);

    // Find corner with one pin where adjacent boundaries have two pins (the one in the corner plus another one).
    corners_with_one_pin
        .map(|i| (i, (i + 1) % 4)) // Compute indices of adjacent boundaries.
        .find(|(i1, i2)| boundary_pin_count[*i1] == 2 && boundary_pin_count[*i2] == 2)
        // Convert indices to boundaries.
        .map(|(i1, i2)| (boundaries[i1], boundaries[i2]))
}

fn create_near_ring_trees(compaction_stage: &CompactionStage) -> impl Iterator<Item = Tree> + '_ {
    let grid = compaction_stage.grid();

    let pins = compaction_stage.current_pins();

    debug_assert!(
        pins.pin_locations().all(|p| grid.is_on_boundary(p)),
        "all pins must be on the boundary"
    );

    // Create near-ring trees.
    pins.pin_locations().dedup().map(move |start| {
        let end = grid
            .all_boundary_points(start)
            .rev()
            .skip(1)
            .filter(|p| pins.contains(*p))
            .next()
            .unwrap(); // Unwrap is fine because we know that there's 7 points on the boundary.

        let points_along_boundary = grid.all_boundary_points(start);

        let tree_edges = points_along_boundary
            .clone()
            .take_while(|p| p != &end)
            .zip(points_along_boundary.skip(1));

        let mut tree = Tree::empty();

        for (a, b) in tree_edges {
            let edge = TreeEdge::from_points(a, b).unwrap();
            tree.add_edge_unchecked(edge);
            debug_assert!(tree.is_tree());
        }
        tree
    })
}

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

    let trees: Vec<_> = create_near_ring_trees(&compaction_stage).collect();
    assert_eq!(trees.len(), 3);

    // All pins must be covered by the tree.
    for tree in &trees {
        assert!(pins.pin_locations().all(|p| tree.contains_node(p)))
    }
}

/// If the grid an pins are simple enough, create all potentially optimal steiner trees for them.
/// If they are not simple enough, return `None`.
fn create_simple_trees(grid: UnitHananGrid, pins: &Pins<Canonical>) -> Option<Vec<Tree>> {
    let r = grid.rect();

    debug_assert!(
        pins.pin_locations().all(|p| grid.contains_point(p)),
        "all pins must be contained on the grid"
    );

    if r.width() == 0 && r.height() == 0 {
        // Trivial case.
        Some(vec![Tree::empty()])
    } else if r.width() == 0 && r.height() > 0 {
        // Tree is a vertical line.
        let x = r.lower_left().x;
        let mut tree = Tree::empty_non_canonical();
        for y in r.lower_left().y..r.upper_right().y {
            let p = Point::new(x, y);
            tree.add_edge_unchecked(TreeEdge::new(p, EdgeDirection::Up));
        }
        debug_assert!(tree.is_tree());
        Some(vec![tree])
    } else if r.width() > 0 && r.height() == 0 {
        // Tree is a horizontal line.
        let y = r.lower_left().y;
        let mut tree = Tree::empty_non_canonical();
        for x in r.lower_left().x..r.upper_right().x {
            let p = Point::new(x, y);
            tree.add_edge_unchecked(TreeEdge::new(p, EdgeDirection::Right));
        }
        debug_assert!(tree.is_tree());
        Some(vec![tree])
    } else {
        None
    }
}

fn connect_adj_pins(
    compaction_stage: &CompactionStage,
    d: HananCoord,
    cache: &mut Cache,
) -> Vec<ExpansionStage> {
    let grid = compaction_stage.grid();

    // Find pins on a boundary which have no more than `d` distance between eachother.
    let boundaries = [
        Boundary::Right,
        Boundary::Top,
        Boundary::Left,
        Boundary::Bottom,
    ];

    // Container for results.
    let mut connect_adj_trees = vec![];

    for boundary in boundaries {
        let pins_on_boundary: SmallVec<[Point<HananCoord>; MAX_DEGREE]> = compaction_stage
            .current_pins()
            .pin_locations()
            .dedup()
            .filter(|p| grid.is_on_partial_boundary(*p, boundary))
            .collect();

        // Find `(start_index, end_index)` tuples which mark consecutive lines of pins along the edge with span-length <= d.
        let d_span_indices = pins_on_boundary
            .iter()
            .enumerate()
            // Start from each point...
            .filter_map(|(start_idx, start_p)| {
                // ... and continue for as many points as the distance is <= d.
                let end_idx = pins_on_boundary[start_idx + 1..]
                    .iter()
                    .enumerate()
                    .take_while(|(end_idx, end)| start_p.manhattan_distance(end) <= d)
                    .map(|(end_idx, _)| end_idx + start_idx) // Correct offset.
                    .last();

                // If endpoint was found, output a tuple of the indices.
                end_idx.map(|end_idx| (start_idx, end_idx))
            })
            .filter(|(start_idx, end_idx)| end_idx > start_idx);

        // Counter-clock-wise travel direction on the boundary.
        // Used to iterate over points on the d-width spans.
        let boundary_direction = match boundary {
            Boundary::Right | Boundary::Left => (0, 1),
            Boundary::Top | Boundary::Bottom => (1, 0),
        };

        for (start_idx, end_idx) in d_span_indices {
            // All pins of this d-width line.
            let pins_in_span = &pins_on_boundary[start_idx..end_idx + 1];

            let start_p = pins_on_boundary[start_idx];
            let end_p = pins_on_boundary[end_idx];

            // Remove the selected pins on the edge.
            let pins_with_removed_span = {
                let mut pins_with_removed_span = compaction_stage.current_pins().clone();
                pins_with_removed_span.dedup();

                pins_with_removed_span.remove_pins(|p| pins_in_span.contains(p));
                pins_with_removed_span
            };

            // Replace the removed line by a point somewhere that line.
            // Get candidate replacement points.
            let replacement_points = {
                let end_p_inclusive = end_p.translate(boundary_direction); // Next point after the end point.

                (0..)
                    .map(|i| (boundary_direction.0 * i, boundary_direction.1 * i))
                    .map(|off| start_p.translate(off))
                    .take_while(move |p| *p != end_p_inclusive)
            };

            // Create the subtree which covers the removed nodes on the edge with a straight line.
            // Will then be merged with the sub-steiner-tree.
            let sub_tree_on_boundary = {
                let mut sub_tree = Tree::empty_non_canonical();

                let tree_edge_start_points = (0..)
                    .map(|i| (boundary_direction.0 * i, boundary_direction.1 * i))
                    .map(|off| start_p.translate(off))
                    .take_while(|p| *p != end_p);

                let edge_direction = match boundary {
                    Boundary::Right | Boundary::Left => EdgeDirection::Up,
                    Boundary::Top | Boundary::Bottom => EdgeDirection::Right,
                };

                for p in tree_edge_start_points {
                    sub_tree.add_edge_unchecked(TreeEdge::new(p, edge_direction));
                }
                debug_assert!(sub_tree.is_tree());

                sub_tree
            };

            // Substitute the removed pins by a single pin, compute the corresponding steiner trees (of smaller degree),
            // add to them the removed pins. And connect them with a straight line.
            for replacement in replacement_points {
                let mut simplified_pins = pins_with_removed_span.clone();
                if !simplified_pins.contains(replacement) {
                    simplified_pins.add_pin(replacement);
                }

                assert!(sub_tree_on_boundary.contains_node(replacement));

                let grid = UnitHananGrid::new(simplified_pins.bounding_box().unwrap());

                // Generate steiner-trees of smaller degree.
                let smaller_trees = gen_lut(CompactionStage::new(grid, simplified_pins), cache);

                // Add the removed pins to the smaller trees. Connect the pins by a straight line.
                let merged_trees =
                    smaller_trees
                        .into_iter()
                        .map(|e| e.into_tree())
                        .map(|mut tree| {
                            // Construct tree edges which cover the removed pins.
                            tree.merge(&sub_tree_on_boundary)
                                .expect("trees cannot be merged");
                            tree
                        });

                // Append merged trees to the result.
                let expansion_stages = merged_trees
                    // Convert trees into expansion stages.
                    .map(|t| ExpansionStage::new(compaction_stage.clone(), t));

                connect_adj_trees.extend(expansion_stages);
            }
        }
    }

    connect_adj_trees
}

#[derive(Default)]
struct Cache {
    data: HashMap<Pins<Canonical>, Vec<Tree>>,
}

impl Cache {
    fn new() -> Self {
        Self {
            data: Default::default(),
        }
    }

    fn with<F, R>(&self, key: &Pins<Canonical>, f: F) -> R
    where
        F: Fn(Option<&Vec<Tree>>) -> R,
    {
        f(self.data.get(key))
    }

    fn with_mut<F, R>(&mut self, key: &Pins<Canonical>, f: F) -> R
    where
        F: Fn(Option<&mut Vec<Tree>>) -> R,
    {
        f(self.data.get_mut(key))
    }

    fn insert(&mut self, key: Pins<Canonical>, data: Vec<Tree>) -> Option<Vec<Tree>> {
        self.data.insert(key, data)
    }
}