steiner-tree 0.0.1

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

use super::MAX_DEGREE;
use std::cmp::Ordering;

type EdgeCountT = u8;

#[derive(Clone, Debug, Hash, PartialEq, Eq)]
pub struct WirelenghtVector {
    num_horizontal_edges: usize,
    num_vertical_edges: usize,
    /// Edge counts.
    /// First half is the horizontal edges, second half is the vertical edges.
    edge_counts: [EdgeCountT; MAX_DEGREE*2]
}

impl PartialOrd for WirelenghtVector {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        if self.num_horizontal_edges() == other.num_horizontal_edges() &&
            self.num_vertical_edges() == other.num_vertical_edges() {

            // A vector a is smaller or equal b if there is no `a[i] > b[i]`.

            let mut elementwise_compare = self.edge_counts.iter()
                .zip(other.edge_counts.iter())
                .map(|(a, b)| a.cmp(b))
                .filter(|o| !o.is_eq()); // Ignore equal elements.

            // Find first unequality.
            let first_unequality = elementwise_compare
                .next()
                .unwrap_or(Ordering::Equal); // No unequality.

            let all_comparisons_equal = elementwise_compare
                .filter(|c| *c != first_unequality)
                .next().is_none();

            if all_comparisons_equal {
                Some(first_unequality)
            } else {
                None
            }

        } else {
            None
        }
    }
}

#[test]
fn test_compare_wirelength_vector_both_empty() {
    let w1 = WirelenghtVector::zero(0, 0);
    let w2 = WirelenghtVector::zero(0, 0);
    assert_eq!(w1.partial_cmp(&w2), Some(Ordering::Equal));
}

#[test]
fn test_compare_wirelength_vector_both_zero() {
    let w1 = WirelenghtVector::zero(2, 2);
    let w2 = WirelenghtVector::zero(2, 2);
    assert_eq!(w1.partial_cmp(&w2), Some(Ordering::Equal));
}

#[test]
fn test_compare_wirelength_vector_larger() {
    let mut w1 = WirelenghtVector::zero(2, 2);
    let w2 = WirelenghtVector::zero(2, 2);
    let (h1, _v1) = w1.hv_vectors_mut();
    h1[0] = 1;
    assert_eq!(w1.partial_cmp(&w2), Some(Ordering::Greater));
}

#[test]
fn test_compare_wirelength_vector_unordered() {
    let mut w1 = WirelenghtVector::zero(2, 2);
    let mut w2 = WirelenghtVector::zero(2, 2);
    let (h1, _v1) = w1.hv_vectors_mut();
    let (_h2, v2) = w2.hv_vectors_mut();
    h1[0] = 1;
    v2[1] = 1;
    assert_eq!(w1.partial_cmp(&w2), None);
}

impl WirelenghtVector {
    /// Create a new zero-valued vector with `degree` horizontal edge counts and `degree` vertical edge counts.
    pub(crate) fn zero(num_horizontal_edges: usize, num_vertical_edges: usize) -> Self {
        Self {
            num_horizontal_edges,
            num_vertical_edges,
            edge_counts: [0; MAX_DEGREE*2]
        }
    }

    /// Number horizontal edge counts.
    pub fn num_horizontal_edges(&self) -> usize {
        self.num_horizontal_edges
    }

    pub fn num_vertical_edges(&self) -> usize {
        self.num_vertical_edges
    }

    pub fn edge_counts(&self) -> &[EdgeCountT] {
        &self.edge_counts[0..self.num_vertical_edges + self.num_horizontal_edges]
    }

    /// Get `(horizontal edge counts, vertical edge counts)`.
    pub fn hv_vectors(&self) -> (&[EdgeCountT], &[EdgeCountT]) {
        self.edge_counts[0..self.num_vertical_edges + self.num_horizontal_edges].split_at(self.num_horizontal_edges)
    }

    /// Get `(horizontal edge counts, vertical edge counts)`.
    pub fn hv_vectors_mut(&mut self) -> (&mut [EdgeCountT], &mut [EdgeCountT]) {
        self.edge_counts[0..self.num_vertical_edges + self.num_horizontal_edges]
            .split_at_mut(self.num_horizontal_edges)
    }
}