Mercurial > repos > alg_tools / file revision

/*!
This module provides various sets and traits for them.
*/

use crate::euclidean::Euclidean;
use crate::instance::{BasicDecomposition, Instance, Space};
use crate::loc::Loc;
use crate::types::*;
use serde::Serialize;
use std::ops::{Range, RangeFrom, RangeFull, RangeInclusive, RangeTo, RangeToInclusive};

pub mod cube;
pub use cube::Cube;

/// Trait for arbitrary sets. The parameter `U` is the element type.
pub trait Set<U>
where
    U: Space,
{
    /// Check for element containment
    fn contains<I: Instance<U>>(&self, item: I) -> bool;
}

/// Additional ordering (besides [`PartialOrd`]) of a subfamily of sets:
/// greatest lower bound and least upper bound.
pub trait SetOrd: Sized {
    /// Returns the smallest set of same class contain both parameters.
    fn common(&self, other: &Self) -> Self;

    /// Returns the greatest set of same class contaied by n both parameter sets.
    fn intersect(&self, other: &Self) -> Option<Self>;
}

impl<U, const N: usize> Set<Loc<N, U>> for Cube<N, U>
where
    U: Num + PartialOrd + Sized,
{
    fn contains<I: Instance<Loc<N, U>>>(&self, item: I) -> bool {
        item.eval_ref_decompose(|r| self.0.iter().zip(r.iter()).all(|(s, x)| s.contains(x)))
    }
}

impl<U: Space> Set<U> for RangeFull {
    fn contains<I: Instance<U>>(&self, _item: I) -> bool {
        true
    }
}

macro_rules! impl_ranges {
    ($($range:ident),*) => { $(
        impl<U,Idx> Set<U> for $range<Idx>
        where
            U : Space<Decomp=BasicDecomposition>,
            U::OwnedSpace : PartialOrd<Idx>,
            Idx : PartialOrd + PartialOrd<U::OwnedSpace>,
        {
            #[inline]
            fn contains<I : Instance<U>>(&self, item : I) -> bool {
                item.eval(|x| $range::contains(&self, x))
            }
        }
    )* }
}

impl_ranges!(RangeFrom, Range, RangeInclusive, RangeTo, RangeToInclusive);

/// Halfspaces described by an orthogonal vector and an offset.
///
/// The halfspace is $H = \\{ t v + a \mid a^⊤ v = 0 \\}$, where $v$ is the orthogonal
/// vector and $t$ the offset.
#[derive(Clone, Copy, Debug, Serialize, Eq, PartialEq)]
pub struct Halfspace<A, F>
where
    A: Euclidean<F>,
    F: Float,
{
    pub orthogonal: A,
    pub offset: F,
}

impl<A, F> Halfspace<A, F>
where
    A: Euclidean<F>,
    F: Float,
{
    #[inline]
    pub fn new(orthogonal: A, offset: F) -> Self {
        Halfspace { orthogonal: orthogonal, offset: offset }
    }
}

/// Trait for generating a halfspace spanned by another set `Self` of elements of type `U`.
pub trait SpannedHalfspace<F>
where
    F: Float,
{
    /// Type of the orthogonal vector describing the halfspace.
    type A: Euclidean<F>;
    /// Returns the halfspace spanned by this set.
    fn spanned_halfspace(&self) -> Halfspace<Self::A, F>;
}

// TODO: Gram-Schmidt for higher N.
impl<F: Float> SpannedHalfspace<F> for [Loc<1, F>; 2] {
    type A = Loc<1, F>;
    fn spanned_halfspace(&self) -> Halfspace<Self::A, F> {
        let (x0, x1) = (self[0], self[1]);
        Halfspace::new(x1 - x0, x0[0])
    }
}

// TODO: Gram-Schmidt for higher N.
impl<F: Float> SpannedHalfspace<F> for [Loc<2, F>; 2] {
    type A = Loc<2, F>;
    fn spanned_halfspace(&self) -> Halfspace<Self::A, F> {
        let (x0, x1) = (&self[0], &self[1]);
        let d = x1 - x0;
        let orthog = loc![d[1], -d[0]]; // We don't normalise for efficiency
        let offset = x0.dot(&orthog);
        Halfspace::new(orthog, offset)
    }
}

impl<A, F> Set<A> for Halfspace<A, F>
where
    A: Euclidean<F>,
    F: Float,
{
    #[inline]
    fn contains<I: Instance<A>>(&self, item: I) -> bool {
        self.orthogonal.dot(item) >= self.offset
    }
}

/// Polygons defined by `N` `Halfspace`s.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct NPolygon<A, const N: usize, F = f64>(pub [Halfspace<A, F>; N])
where
    A: Euclidean<F>,
    F: Float;

impl<A, F, const N: usize> Set<A> for NPolygon<A, N, F>
where
    A: Euclidean<F>,
    F: Float,
{
    fn contains<I: Instance<A>>(&self, item: I) -> bool {
        item.eval_ref_decompose(|r| self.0.iter().all(|halfspace| halfspace.contains(r)))
    }
}