steiner-tree 0.0.1

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

//! Compute position sequence from points and create set of points from a position sequence.

use std::cell::RefCell;

use crate::HananCoord;
use super::point::*;
use super::permutations;

/// Representation of the relative ordering of points in the Euclidean plane.
#[derive(Debug, Clone, Hash, PartialEq, Eq)]
pub struct PositionSequence {
    position_sequence: Vec<usize>
}

impl PositionSequence {
    pub(crate) fn new(position_sequence: Vec<usize>) -> Self {
        let s = Self { position_sequence };
        assert!(s.is_valid());
        s
    }

    /// Length of the position sequence.
    pub fn len(&self) -> usize {
        self.position_sequence.len()
    }

    /// Access to the raw position sequence.
    pub fn sequence(&self) -> &[usize] {
        &self.position_sequence
    }

    /// Get the group index of the position sequence.
    /// There is a 1-to-1 mapping between position sequences **of a certain length** and group indices.
    pub fn group_index(&self) -> usize {
        permutations::group_index(self)
    }

    /// Compute the 'position sequence' of the points.
    /// Points are numbered by their ascending x coordinate.
    /// The indices are ordered by the y coordinate of the points. This is the position sequence.
    ///
    /// Ties are broken arbitrarily.
    ///
    /// Note: This function needs two allocations. Use `from_points_noalloc()` to reuse the allocated space of an existing position sequence.
    pub fn from_points<T>(points: &[Point<T>]) -> Self
        where T: Ord + Copy {

        // Sort points by x coordinate.
        let mut points_x_ascending = points.to_vec();
        points_x_ascending.sort_by_key(|p| p.x);

        // Sort the indices by the y coordinate of the points.
        let mut indices: Vec<_> = (0..points.len()).collect();
        indices.sort_by_key(|&idx| points_x_ascending[idx].y);

        Self { position_sequence: indices }
    }

    /// Reuse the allocated space of `reuse` to create a new position sequence.
    pub fn from_points_noalloc<T>(mut reuse: Self, points: &[Point<T>]) -> Self
        where T: Ord + Copy {
        reuse.position_sequence.clear();
        reuse.position_sequence.extend(0..points.len());
        position_sequence_no_alloc(&mut reuse.position_sequence, points);
        reuse
    }

    /// Convert a position sequence to a sequence of points which have the same position sequence.
    /// The points are located on a grid with unit distance between grid lines.
    pub fn to_points(&self) -> impl Iterator<Item=Point<HananCoord>> + '_ {
        debug_assert!(self.is_valid());

        self.position_sequence.iter()
            .enumerate()
            .map(|(y, &x)| Point::new(x as HananCoord, y as HananCoord))
    }

    pub(crate) fn is_valid(&self) -> bool {
        let n = self.position_sequence.len();
        (0..n).all(|i| self.position_sequence.contains(&i))
    }
}


#[test]
fn test_position_sequence_to_points() {
    let seq = PositionSequence::new(vec![0, 4, 3, 1, 5, 2, 6]);
    let points: Vec<_> = seq.to_points().collect();

    assert_eq!(PositionSequence::from_points(&points), seq);
}


/// Compute the 'position sequence' of the points.
/// Points are numbered by their ascending x coordinate.
/// The indices are ordered by the y coordinate of the points. This is the position sequence.
///
/// Ties are broken arbitrarily.
fn position_sequence_no_alloc<T>(position_sequence: &mut [usize], points: &[Point<T>])
    where T: Ord + Copy {
    assert_eq!(position_sequence.len(), points.len(), "sizes of arrays must match");

    // Use a thread local scratch buffer to avoid allocations.
    thread_local! {
        static SCRATCH: RefCell<Vec<usize>> = RefCell::new(vec![]);
    }

    SCRATCH.with(|scratch| {
        let mut scratch = scratch.borrow_mut();

        scratch.clear();
        scratch.extend(0..points.len());

        // Sort points by x coordinate.
        scratch.sort_by_key(|&idx| points[idx].x);

        // Sort the indices by the y coordinate of the points.
        position_sequence.iter_mut()
            .enumerate()
            .for_each(|(i, v)| *v = i);

        position_sequence.sort_by_key(|&idx| points[scratch[idx]].y);
        scratch.clear();
    });
}


#[test]
fn test_position_sequence() {
    let points = vec![(0, 1).into(), (1, 3).into(), (2, 0).into(), (3, 2).into()];

    assert_eq!(PositionSequence::from_points(&points).position_sequence, vec![2, 0, 3, 1]);
}