Mercurial > repos > alg_tools / file revision

/*!
Multi-dimensional cubes.

This module provides the [`Cube`] type for multi-dimensional cubes $∏_{i=1}^N [a_i, b_i)$.

As an example, to create a the two-dimensional cube $[0, 1] × [-1, 1]$, you can
```
# use alg_tools::sets::cube::Cube;
let cube = Cube::new([[0.0, 1.0], [-1.0, 1.0]]);
```
or
```
# use alg_tools::sets::cube::Cube;
# use alg_tools::types::float;
let cube : Cube<float, 2> = [[0.0, 1.0], [-1.0, 1.0]].into();
```
*/

use serde::ser::{Serialize, Serializer, SerializeTupleStruct};
use crate::types::*;
use crate::loc::Loc;
use crate::sets::SetOrd;
use crate::maputil::{
    FixedLength,
    FixedLengthMut,
    map1,
    map1_indexed,
    map2,
};

/// A multi-dimensional cube $∏_{i=1}^N [a_i, b_i)$ with the starting and ending points
/// along $a_i$ and $b_i$ along each dimension of type `U`.
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub struct Cube<U : Num, const N : usize>(pub(super) [[U; 2]; N]);

// Need to manually implement as [F; N] serialisation is provided only for some N.
impl<F : Num + Serialize, const N : usize> Serialize for Cube<F, N>
where
    F: Serialize,
{
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: Serializer,
    {
        let mut ts = serializer.serialize_tuple_struct("Cube", N)?;
        for e in self.0.iter() {
            ts.serialize_field(e)?;
        }
        ts.end()
    }
}

impl<A : Num, const N : usize> FixedLength<N> for Cube<A,N> {
    type Iter = std::array::IntoIter<[A; 2], N>;
    type Elem = [A; 2];
    #[inline]
    fn fl_iter(self) -> Self::Iter {
        self.0.into_iter()
    }
}

impl<A : Num, const N : usize> FixedLengthMut<N> for Cube<A,N> {
    type IterMut<'a> = std::slice::IterMut<'a, [A; 2]>;
    #[inline]
    fn fl_iter_mut(&mut self) -> Self::IterMut<'_> {
        self.0.iter_mut()
    }
}

impl<'a, A : Num, const N : usize> FixedLength<N> for &'a Cube<A,N> {
    type Iter = std::slice::Iter<'a, [A; 2]>;
    type Elem = &'a [A; 2];
    #[inline]
    fn fl_iter(self) -> Self::Iter {
        self.0.iter()
    }
}


/// Iterator for [`Cube`] corners.
pub struct CubeCornersIter<'a, U : Num, const N : usize> {
    index : usize,
    cube : &'a Cube<U, N>,
}

impl<'a, U : Num, const N : usize> Iterator for CubeCornersIter<'a, U, N> {
    type Item = Loc<U, N>;
    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if self.index >= N {
            None
        } else {
            let i = self.index;
            self.index += 1;
            let arr = self.cube.map_indexed(|k, a, b| if (i>>k)&1 == 0 { a } else { b });
            Some(arr.into())
        }
    }
}

impl<U : Num, const N : usize> Cube<U, N> {
    /// Maps `f` over the triples $\\{(i, a\_i, b\_i)\\}\_{i=1}^N$
    /// of the cube $∏_{i=1}^N [a_i, b_i)$.
    #[inline]
    pub fn map_indexed<T>(&self, f : impl Fn(usize, U, U) -> T) -> [T; N] {
        map1_indexed(self, |i, &[a, b]| f(i, a, b))
    }

    /// Maps `f` over the tuples $\\{(a\_i, b\_i)\\}\_{i=1}^N$
    /// of the cube $∏_{i=1}^N [a_i, b_i)$.
    #[inline]
    pub fn map<T>(&self, f : impl Fn(U, U) -> T) -> [T; N] {
        map1(self, |&[a, b]| f(a, b))
    }

    /// Iterates over the start and end coordinates $\{(a_i, b_i)\}_{i=1}^N$ of the cube along 
    /// each dimension.
    #[inline]
    pub fn iter_coords(&self) -> std::slice::Iter<'_, [U; 2]> {
        self.0.iter()
    }

    /// Returns the “start” coordinate $a_i$ of the cube $∏_{i=1}^N [a_i, b_i)$.
    #[inline]
    pub fn start(&self, i : usize) -> U {
        self.0[i][0]
    }

    /// Returns the end coordinate $a_i$ of the cube $∏_{i=1}^N [a_i, b_i)$.
    #[inline]
    pub fn end(&self, i : usize) -> U {
        self.0[i][1]
    }

    /// Returns the “start” $(a_1, … ,a_N)$ of the cube $∏_{i=1}^N [a_i, b_i)$
    /// spanned between $(a_1, … ,a_N)$ and $(b_1, … ,b_N)$.
    #[inline]
    pub fn span_start(&self) -> Loc<U, N> {
        Loc::new(self.map(|a, _b| a))
    }

    /// Returns the end $(b_1, … ,b_N)$ of the cube $∏_{i=1}^N [a_i, b_i)$
    /// spanned between $(a_1, … ,a_N)$ and $(b_1, … ,b_N)$.
    #[inline]
    pub fn span_end(&self) -> Loc<U, N> {
        Loc::new(self.map(|_a, b| b))
    }

    /// Iterates over the corners $\{(c_1, … ,c_N) | c_i ∈ \{a_i, b_i\}\}$ of the cube
    /// $∏_{i=1}^N [a_i, b_i)$.
    #[inline]
    pub fn iter_corners(&self) -> CubeCornersIter<'_, U, N> {
        CubeCornersIter{ index : 0, cube : self }
    }

    /// Returns the width-`N`-tuple $(b_1-a_1, … ,b_N-a_N)$ of the cube $∏_{i=1}^N [a_i, b_i)$.
    #[inline]
    pub fn width(&self) -> Loc<U, N> {
        Loc::new(self.map(|a, b| b-a))
    }

    /// Translates the cube $∏_{i=1}^N [a_i, b_i)$ by the `shift` $(s_1, … , s_N)$ to
    /// $∏_{i=1}^N [a_i+s_i, b_i+s_i)$.
    #[inline]
    pub fn shift(&self, shift : &Loc<U, N>) -> Self {
        let mut cube = self.clone();
        for i in 0..N {
            cube.0[i][0] += shift[i];
            cube.0[i][1] += shift[i];
        }
        cube
    }

    /// Creates a new cube from an array.
    #[inline]
    pub fn new(data : [[U; 2]; N]) -> Self {
        Cube(data)
    }
}

impl<F : Float, const N : usize> Cube<F, N> {
    /// Returns the centre of the cube
    pub fn center(&self) -> Loc<F, N> {
        map1(self, |&[a, b]| (a + b) / F::TWO).into()
    }
}

impl<U : Num> Cube<U, 1> {
    /// Get the corners of the cube.
    ///
    /// TODO: generic implementation once const-generics can be involved in
    /// calculations.
    #[inline]
    pub fn corners(&self) -> [Loc<U, 1>; 2] {
        let [[a, b]] = self.0;
        [a.into(), b.into()]
    }
}

impl<U : Num> Cube<U, 2> {
    /// Get the corners of the cube in counter-clockwise order.
    ///
    /// TODO: generic implementation once const-generics can be involved in
    /// calculations.
    #[inline]
    pub fn corners(&self) -> [Loc<U, 2>; 4] {
        let [[a1, b1], [a2, b2]]=self.0;
        [[a1, a2].into(),
         [b1, a2].into(),
         [b1, b2].into(),
         [a1, b2].into()]
    }
}

impl<U : Num> Cube<U, 3> {
    /// Get the corners of the cube.
    ///
    /// TODO: generic implementation once const-generics can be involved in
    /// calculations.
    #[inline]
    pub fn corners(&self) -> [Loc<U, 3>; 8] {
        let [[a1, b1], [a2, b2], [a3, b3]]=self.0;
        [[a1, a2, a3].into(),
         [b1, a2, a3].into(),
         [b1, b2, a3].into(),
         [a1, b2, a3].into(),
         [a1, b2, b3].into(),
         [b1, b2, b3].into(),
         [b1, a2, b3].into(),
         [a1, a2, b3].into()]
    }
}

// TODO: Implement Add and Sub of Loc to Cube, and Mul and Div by U : Num.

impl<U : Num, const N : usize> From<[[U; 2]; N]> for Cube<U, N> {
    #[inline]
    fn from(data : [[U; 2]; N]) -> Self {
        Cube(data)
    }
}

impl<U : Num, const N : usize> From<Cube<U, N>> for [[U; 2]; N] {
    #[inline]
    fn from(Cube(data) : Cube<U, N>) -> Self {
        data
    }
}


impl<U, const N : usize> Cube<U, N> where U : Num + PartialOrd {
    /// Checks whether the cube is non-degenerate, i.e., the start coordinate
    /// of each axis is strictly less than the end coordinate.
    #[inline]
    pub fn nondegenerate(&self) -> bool {
        self.0.iter().all(|range| range[0] < range[1])
    }
    
    /// Checks whether the cube intersects some `other` cube.
    /// Matching boundary points are not counted, so `U` is ideally a [`Float`].
    #[inline]
    pub fn intersects(&self, other : &Cube<U, N>) -> bool {
        self.iter_coords().zip(other.iter_coords()).all(|([a1, b1], [a2, b2])| {
            a1 < b2 && a2 < b1
        })
    }

    /// Checks whether the cube contains some `other` cube.
    pub fn contains_set(&self, other : &Cube<U, N>) -> bool {
        self.iter_coords().zip(other.iter_coords()).all(|([a1, b1], [a2, b2])| {
            a1 <= a2 && b1 >= b2
        })
    }

    /// Produces the point of minimum $ℓ^p$-norm within the cube `self` for any $p$-norm.
    /// This is the point where each coordinate is closest to zero.
    #[inline]
    pub fn minnorm_point(&self) -> Loc<U, N> {
        let z = U::ZERO;
        // As always, we assume that a ≤ b.
        self.map(|a, b| {
            debug_assert!(a <= b);
            match (a < z, z < b) {
                (false, _)   => a,
                (_, false)   => b,
                (true, true) => z
            }
        }).into()
    }

    /// Produces the point of maximum $ℓ^p$-norm within the cube `self` for any $p$-norm.
    /// This is the point where each coordinate is furthest from zero.
    #[inline]
    pub fn maxnorm_point(&self) -> Loc<U, N> {
        let z = U::ZERO;
        // As always, we assume that a ≤ b.
        self.map(|a, b| {
            debug_assert!(a <= b);
            match (a < z, z < b) {
                (false, _)   => b,
                (_, false)   => a,
                // A this stage we must have a < 0 (so U must be signed), and want to check
                // whether |a| > |b|. We can do this without assuming U to actually implement
                // `Neg` by comparing whether 0 > a + b.
                (true, true) => if z > a + b { a } else { b }
            }
        }).into()
    }
}

macro_rules! impl_common {
    ($($t:ty)*, $min:ident, $max:ident) => { $(
        impl<const N : usize> SetOrd for Cube<$t, N> {
            #[inline]
            fn common(&self, other : &Self) -> Self {
                map2(self, other, |&[a1, b1], &[a2, b2]| {
                    debug_assert!(a1 <= b1 && a2 <= b2);
                    [a1.$min(a2), b1.$max(b2)]
                }).into()
            }

            #[inline]
            fn intersect(&self, other : &Self) -> Option<Self> {
                let arr = map2(self, other, |&[a1, b1], &[a2, b2]| {
                    debug_assert!(a1 <= b1 && a2 <= b2);
                    [a1.$max(a2), b1.$min(b2)]
                });
                arr.iter().all(|&[a, b]| a >= b).then(|| arr.into())
            }
        }
    )* }
}

impl_common!(u8 u16 u32 u64 u128 usize
             i8 i16 i32 i64 i128 isize, min, max);
// Any NaN yields NaN
impl_common!(f32 f64, minimum, maximum);

impl<U : Num, const N : usize> std::ops::Index<usize> for Cube<U, N> {
    type Output = [U; 2];
    #[inline]
    fn index(&self, index: usize) -> &Self::Output {
        &self.0[index]
    }
}

impl<U : Num, const N : usize> std::ops::IndexMut<usize> for Cube<U, N> {
    #[inline]
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        &mut self.0[index]
    }
}