Mercurial > repos > alg_tools / file revision

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

use std::ops::{RangeFull,RangeFrom,Range,RangeInclusive,RangeTo,RangeToInclusive};
use std::marker::PhantomData;
use crate::types::*;
use crate::loc::Loc;
use crate::euclidean::Dot;
use serde::Serialize;

mod cube;
pub use cube::Cube;

/// Trait for arbitrary sets. The parameter `U` is the element type.
pub trait Set<U> where U : ?Sized {
    /// Check for element containment
    fn contains(&self, item : &U) -> 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<U, N>>
for Cube<U,N>
where U : Num + PartialOrd + Sized {
    fn contains(&self, item : &Loc<U, N>) -> bool {
        self.0.iter().zip(item.iter()).all(|(s, x)| s.contains(x))
    }
}

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

macro_rules! impl_ranges {
    ($($range:ident),*) => { $(
        impl<U,Idx> Set<U>
        for $range<Idx>
        where Idx : PartialOrd<U>, U : PartialOrd<Idx> + ?Sized, Idx : PartialOrd {
            #[inline]
            fn contains(&self, item : &U) -> bool { $range::contains(&self, item) }
        }
    )* }
}

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.
///
/// `U` is the element type, `F` the floating point number type, and `A` the type of the
/// orthogonal (dual) vectors. They need implement [`Dot<U, F>`].
#[derive(Clone,Copy,Debug,Serialize,Eq,PartialEq)]
pub struct Halfspace<A, F, U> where A : Dot<U, F>, F : Float {
    pub orthogonal : A,
    pub offset : F,
    _phantom : PhantomData<U>,
}

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

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

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

// TODO: Gram-Schmidt for higher N.
impl<F : Float> SpannedHalfspace<F,Loc<F, 2>> for [Loc<F, 2>; 2] {
    type A = Loc<F, 2>;
    fn spanned_halfspace(&self) -> Halfspace<Self::A, F, Loc<F, 2>> {
        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,U,F> Set<U> for Halfspace<A,F,U> where A : Dot<U,F>, F : Float {
    #[inline]
    fn contains(&self, item : &U) -> bool {
        self.orthogonal.dot(item) >= self.offset
    }
}

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

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