points_between 0.1.0

use points::*;

/// A trait implemented by integer types to get all discrete points between two N-dimensional
/// points.
pub trait Between<T: Into<f64>, const N: usize> {
    type Output;

    fn points_between(start: [T; N], end: [T; N]) -> Vec<[Self::Output; N]>;
}

macro_rules! implement {
    ($type:ty, $internal:ty) => (
        impl<T: Into<f64>, const N: usize> Between<T, N> for $type {
            type Output = $type;

            fn points_between(start: [T; N], end: [T; N]) -> Vec<[Self::Output; N]> {
                let start = start.map(|n| n.into());
                let end = end.map(|n| n.into());
                <$internal>::points_between(start, end)
            }
        }
        )
}

implement!(i8, DiscreteI8<N>);
implement!(u8, DiscreteU8<N>);

implement!(i16, DiscreteI16<N>);
implement!(u16, DiscreteU16<N>);

implement!(i32, DiscreteI32<N>);
implement!(u32, DiscreteU32<N>);


#[cfg(test)]
fn adjacent<T: Into<i64>, const N: usize>(a: [T; N], b: [T; N]) -> bool {
    let a = a.map(|e| e.into());
    let b = b.map(|e| e.into());

    if a == b { return false; }

    a.iter().zip(b.iter())
        .map(|(a, b)| a.abs_diff(*b))
        .all(|n| n <= 1)
}


#[cfg(test)]
mod tests {
    use super::*;

    macro_rules! sub_u8 {
        ($n:ident + $m:ident) => ((($n as i16) + $m) as u8)
    }



    #[test]
    #[ignore]
    fn adjacency() {
        let range: std::ops::RangeInclusive<u8> = 1..=254;

        for r in range.clone(){ for g in range.clone(){ for b in range.clone(){

        let p = [r, g, b];

        for r_mod in -1..=1 {
            for g_mod in -1..=1 {
                for b_mod in -1..=1 {
                    let neighbor = 
                        [
                            sub_u8!(r + r_mod),
                            sub_u8!(g + g_mod),
                            sub_u8!(b + b_mod)
                        ];

                    let are = adjacent(p, neighbor);
                    assert!((r_mod == 0 && g_mod == 0 && b_mod == 0) ^ are);
                }
            }
        }
        
        }}}
    }

    #[test]
    fn between_completeness() {
        let start = [22, 13, 5];
        let end = [100, 210, 178];

        let v = u8::points_between(start, end);

        let mut prev = start;
        for p in v {
            assert!(adjacent(prev, p));
            prev = p;
        }

        assert!(adjacent(prev, end));
    }
}

mod points {
    #[cfg(test)]
    use super::{ adjacent, Between };

    use core::convert::From;
    use std::cmp::Ordering;
    use std::collections::BTreeSet;
    use std::ops::{Add, Mul};

    #[derive(Clone, Copy, Debug)]
    pub struct RawPoint<const N: usize>([f64; N]);

    impl<const N: usize, T: Into<f64>> From<[T; N]> for RawPoint<N> {
        fn from(it: [T; N]) -> Self {
            Self(it.map(|item| item.into()))
        }
    }

    impl<const N: usize> Add for RawPoint<N> {
        type Output = Self;

        fn add(self, rhs: Self) -> Self::Output {
            let mut arr = [0f64; N];
            for i in 0..N {
                arr[i] = self.0[i] + rhs.0[i];
            }

            Self(arr)
        }
    }

    impl<const N: usize> Mul<f64> for RawPoint<N> {
        type Output = Self;

        fn mul(self, rhs: f64) -> Self::Output {
            Self(self.0.clone().map(|x| x * rhs))
        }
    }

    impl<const N: usize> RawPoint<N> {
        fn at(start: &Self, end: &Self, t: f64) -> Self {
            assert!(t >= 0.0 && t <= 1.0);

            (*start * (1.0 - t)) + (*end * t)
        }

        fn distance(&self, other: &Self) -> f64 {
            self.0.iter().zip(other.0.iter())
                .map(|(a, b)| (a - b).powi(2))
                .reduce(|acc, x| acc + x).unwrap()
                .sqrt()
        }
    }

    macro_rules! discrete {
        ($structure:ident, $type:ty) => (

            #[derive(Clone, Copy, Debug)]
            pub struct $structure<const N: usize> {
                arr: [$type; N],
                distance: f64
            }

            impl<const N: usize> PartialEq for $structure<N> {
                fn eq(&self, other: &Self) -> bool {
                    self.arr.iter().zip(other.arr.iter()).all(|(a, b)| a == b)
                }
            }

            impl<const N: usize> Eq for $structure<N> {}

            impl<const N: usize> Ord for $structure<N> {
                fn cmp(&self, other: &Self) -> Ordering {
                    self.distance.total_cmp(&other.distance)
                }
            }

            impl<const N: usize> PartialOrd for $structure<N> {
                fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
                    Some(self.cmp(other))
                }
            }

            impl<const N: usize> $structure<N> {
                pub fn arr(self) -> [$type; N] {
                    self.arr
                }


                fn from_raw(raw: RawPoint<N>, origin: &RawPoint<N>) -> Self {
                    Self::new(raw.0.map(|x| x as $type), *origin)
                }

                pub fn new<T: Into<$type>, U: Into<RawPoint<N>>>(arr: [T; N], origin: U) -> Self {
                    let arr = arr.map(|e| e.into());
                    let distance = 
                        origin.into().distance(&RawPoint::from(arr));

                    Self{ arr, distance }
                }

                pub fn points_between(p1: [f64; N], p2: [f64; N]) -> Vec<[$type; N]> {
                    let p1 = RawPoint(p1);
                    let p2 = RawPoint(p2);
                    let mut set = BTreeSet::<Self>::new();

                    Self::pb_rec(&(&p1, &p2), (&p1, &p2), 0.5, 0.5, &mut set);

                    set.into_iter().map(|p| p.arr()).collect()
                }

                fn pb_rec(
                    endpoints: &(&RawPoint<N>, &RawPoint<N>),
                    parents: (&RawPoint<N>, &RawPoint<N>,),
                    t: f64, t_last_inc: f64,
                    set: &mut BTreeSet<Self>) {
        
                    let new_raw = RawPoint::at(endpoints.0, endpoints.1, t);
                    let new = $structure::from_raw(new_raw.clone(), endpoints.0);


                    let p1 = $structure::from_raw(parents.0.clone(), endpoints.0);
                    let p2 = $structure::from_raw(parents.1.clone(), endpoints.0);
                    if new != p1 && new != p2 {
                        set.insert(new);

                        let half_t = t_last_inc * 0.5;

                        Self::pb_rec(endpoints, (parents.0, &new_raw), t - half_t, half_t, set);
                        Self::pb_rec(endpoints, (&new_raw, parents.1), t + half_t, half_t, set);
                    }
                }
            }
        )
    }

    discrete!(DiscreteI8, i8);
    discrete!(DiscreteU8, u8);

    discrete!(DiscreteI16, i16);
    discrete!(DiscreteU16, u16);

    discrete!(DiscreteI32, i32);
    discrete!(DiscreteU32, u32);

    /*discrete!(DiscreteI64, i64);
    discrete!(DiscreteU64, u64);
    
    discrete!(DiscreteIsize, isize);
    discrete!(DiscreteUsize, usize);*/



    #[cfg(test)]
    mod tests {
        use super::*;

        #[test]
        fn raw_from() {
            let rgb = [1, 2, 5];
            let raw = RawPoint::from(rgb);

            let raw_x = raw.0[0].to_bits();
            let raw_y = raw.0[1].to_bits();
            let raw_z = raw.0[2].to_bits();

            let rgb_x = (rgb[0] as f64).to_bits();
            let rgb_y = (rgb[1] as f64).to_bits();
            let rgb_z = (rgb[2] as f64).to_bits();

            assert_eq!((raw_x, raw_y, raw_z), (rgb_x, rgb_y, rgb_z));
        }

        #[test]
        fn ordering() {
            let origin = RawPoint::from([1, 1, 1]);

            let c1 = [10, 11, 13];
            let c2 = [11, 13, 10];
            let c3 = [5, 3, 2];

            let p1 = DiscreteU8::new(c1, origin);
            let p2 = DiscreteU8::new(c2, origin);
            let p3 = DiscreteU8::new(c3, origin);

            assert_eq!(p1.distance, p2.distance);
            assert_eq!(p1.cmp(&p2), Ordering::Equal);

            assert!(p1.distance > p3.distance);
            assert!(p2.distance > p3.distance);

            assert_ne!(p1, p2);
        }

        #[test]
        fn self_distance() {
            let color = [11, 15, 16];
            let p = DiscreteU8::new(color, color);
            assert_eq!(p.distance, 0.0);
        }

        #[test]
        fn between_completeness() {
            let start = [10, 30, 2];
            let end = [201, 55, 76];

            /*let start = DiscreteU8::new(start, start);
            let end = DiscreteU8::new(end, start.color());*/

            let v = u8::points_between(start, end);
            //println!("{:?}", v);
            let mut prev = start;
            for p in v {
                assert!(adjacent(prev, p));
                
                prev = p;
            }

            assert!(adjacent(prev, end));
        }
    }
}