typenum.rs

use std::marker::PhantomData;

pub struct NegOne;
pub struct Zero;

pub struct Bit0<N>(PhantomData<N>);
pub struct Bit1<N>(PhantomData<N>);

macro_rules! t {
    ($accum:ty) => {
        $accum
    };
    ($accum:ty,) => {
        $accum
    };
    ($accum:ty, 0 $($rest:tt)*) => {
        t!(Bit0<$accum>, $($rest)*)
    };
    ($accum:ty, 1 $($rest:tt)*) => {
        t!(Bit1<$accum>, $($rest)*)
    }
}

type One = t!(Zero, 1);
type Two = t!(Zero, 1 0);
type Three = t!(Zero, 1 1);
type Four = t!(Zero, 1 0 0);
type Five = t!(Zero, 1 0 1);
type Six = t!(Zero, 1 1 0);
type Seven = t!(Zero, 1 1 1);
type Eight = t!(Zero, 1 0 0 0);
type Nine = t!(Zero, 1 0 0 1);
type Ten = t!(Zero, 1 0 1 0);
type Eleven = t!(Zero, 1 0 1 1);
type Twelve = t!(Zero, 1 1 0 0);
type Thirteen = t!(Zero, 1 1 0 1);
type Fourteen = t!(Zero, 1 1 1 0);
type Fifteen = t!(Zero, 1 1 1 1);
type Sixteen = t!(Zero, 1 0 0 0 0);

type NegTwo = t!(NegOne, 0);
type NegThree = t!(NegOne, 0 1);
type NegFour = t!(NegOne, 0 0);
type NegFive = t!(NegOne, 0 1 1);
type NegSix = t!(NegOne, 0 1 0);
type NegSeven = t!(NegOne, 0 0 1);
type NegEight = t!(NegOne, 0 0 0);
type NegNine = t!(NegOne, 0 1 1 1);
type NegTen = t!(NegOne, 0 1 1 0);
type NegEleven = t!(NegOne, 0 1 0 1);
type NegTwelve = t!(NegOne, 0 1 0 0);
type NegThirteen = t!(NegOne, 0 0 1 1);
type NegFourteen = t!(NegOne, 0 0 1 0);
type NegFifteen = t!(NegOne, 0 0 0 1);
type NegSixteen = t!(NegOne, 0 0 0 0);
type NegSeventeen = t!(NegOne, 0 1 1 1 1);

pub trait Integer: 'static {
    const VALUE: i128;
    type Apply<F: IntegerFunction>: Integer;
}

pub trait IntegerFunction {
    type Zero: Integer;
    type NegOne: Integer;
    type Bit0<N: NotZero>: Integer;
    type Bit1<N: NotNegOne>: Integer;
}

impl Integer for Zero {
    const VALUE: i128 = 0;
    type Apply<F: IntegerFunction> = <F as IntegerFunction>::Zero;
}

impl Integer for NegOne {
    const VALUE: i128 = -1;
    type Apply<F: IntegerFunction> = <F as IntegerFunction>::NegOne;
}

// We require N to be NotZero and not just an Integer in order to only permit canonical integers
impl<N: NotZero> Integer for Bit0<N> {
    const VALUE: i128 = 2 * <N as Integer>::VALUE;
    type Apply<F: IntegerFunction> = <F as IntegerFunction>::Bit0<N>;
}

// We require N to be NotNegOne and not just an Integer in order to only permit canonical integers
impl<N: NotNegOne> Integer for Bit1<N> {
    const VALUE: i128 = <N as Integer>::VALUE * 2 + 1;
    type Apply<F: IntegerFunction> = <F as IntegerFunction>::Bit1<N>;
}

pub trait NotZero: Integer {}
impl NotZero for NegOne {}
impl<N: NotZero> NotZero for Bit0<N> {}
impl<N: NotNegOne> NotZero for Bit1<N> {}

pub trait NotNegOne: Integer {}
impl NotNegOne for Zero {}
impl<N: NotZero> NotNegOne for Bit0<N> {}
impl<N: NotNegOne> NotNegOne for Bit1<N> {}

pub type Apply<F, N> = <N as Integer>::Apply<F>;

pub struct Mul2;
impl IntegerFunction for Mul2 {
    type Zero = Zero;
    type NegOne = NegTwo;
    type Bit0<N: NotZero> = Bit0<Bit0<N>>;
    type Bit1<N: NotNegOne> = Bit0<Bit1<N>>;
}

pub struct Mul2Add1;
impl IntegerFunction for Mul2Add1 {
    type Zero = One;
    type NegOne = NegOne;
    type Bit0<N: NotZero> = Bit1<Bit0<N>>;
    type Bit1<N: NotNegOne> = Bit1<Bit1<N>>;
}

struct Add1;
impl IntegerFunction for Add1 {
    type Zero = One;
    type NegOne = Zero;
    type Bit0<N: NotZero> = Apply<Mul2Add1, N>;
    type Bit1<N: NotNegOne> = Apply<Mul2, Apply<Add1, N>>;
}

struct Sub1;
impl IntegerFunction for Sub1 {
    type Zero = NegOne;
    type NegOne = NegTwo;
    type Bit0<N: NotZero> = Apply<Mul2Add1, Apply<Sub1, N>>;
    type Bit1<N: NotNegOne> = Apply<Mul2, N>;
}

struct Add<N: Integer>(PhantomData<N>);
struct AddTwice<N: Integer>(PhantomData<N>);

impl<N: Integer> IntegerFunction for Add<N> {
    type Zero = N;
    type NegOne = Apply<Sub1, N>;
    type Bit0<M: NotZero> = Apply<AddTwice<M>, N>;
    type Bit1<M: NotNegOne> = Apply<Add1, Apply<AddTwice<M>, N>>;
}

impl<N: Integer> IntegerFunction for AddTwice<N> {
    type Zero = Apply<Mul2, N>;
    type NegOne = Apply<Mul2Add1, Apply<Sub1, N>>;
    type Bit0<M: NotZero> = Apply<Mul2, Apply<Add<M>, N>>;
    type Bit1<M: NotNegOne> = Apply<Mul2Add1, Apply<Add<M>, N>>;
}

macro_rules! combinations {
    ($N:ident, $v:ident, [$(($Ninst:ty, $Vinst:expr)),* $(,)?], $inner:block) => {
        $(
            {
                type $N = $Ninst;
                let $v = $Vinst;
                $inner
            }
        )*
    };
}

macro_rules! standard_combinations {
    ($N:ident, $v:ident, $inner:block) => {
        combinations!(
            $N,
            $v,
            [
                (Zero, 0),
                (One, 1),
                (Two, 2),
                (Three, 3),
                (Four, 4),
                (Five, 5),
                (Six, 6),
                (Seven, 7),
                (Eight, 8),
                (Nine, 9),
                (Ten, 10),
                (Eleven, 11),
                (Twelve, 12),
                (Thirteen, 13),
                (Fourteen, 14),
                (Fifteen, 15),
                (Sixteen, 16),
                (NegOne, -1),
                (NegTwo, -2),
                (NegThree, -3),
                (NegFour, -4),
                (NegFive, -5),
                (NegSix, -6),
                (NegSeven, -7),
                (NegEight, -8),
                (NegNine, -9),
                (NegTen, -10),
                (NegEleven, -11),
                (NegTwelve, -12),
                (NegThirteen, -13),
                (NegFourteen, -14),
                (NegFifteen, -15),
                (NegSixteen, -16),
                (NegSeventeen, -17),
            ],
            $inner
        )
    };
}

#[cfg(test)]
mod tests {
    use std::{any::TypeId, collections::HashMap};

    use super::*;

    #[test]
    fn test_value() {
        let mut seen: HashMap<i128, TypeId> = HashMap::new();

        fn check<N: Integer>(seen: &mut HashMap<i128, TypeId>, expected: i128) {
            assert_eq!(<N as Integer>::VALUE, expected);
            assert_eq!(
                *seen
                    .entry(N::VALUE)
                    .or_insert_with(|| std::any::TypeId::of::<N>()),
                std::any::TypeId::of::<N>()
            );
        }

        standard_combinations!(N, n, {
            check::<N>(&mut seen, n);
            check::<Apply<Mul2, N>>(&mut seen, 2 * n);
            check::<Apply<Mul2Add1, N>>(&mut seen, 2 * n + 1);
            check::<Apply<Add1, N>>(&mut seen, n + 1);
            check::<Apply<Sub1, N>>(&mut seen, n - 1);
            standard_combinations!(M, m, {
                check::<Apply<Add<N>, M>>(&mut seen, n + m);
                check::<Apply<AddTwice<N>, M>>(&mut seen, 2 * n + m);
            });
        });
    }
}