type_stuff.rs

struct NegOne;
struct Zero;

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

type One = Bit1<Zero>;
type NegTwo = Bit0<NegOne>;

trait Integer {
    const VALUE: i128;
    type Add1: Integer; // Calculate (N + 1) as a canonical integer
    type Sub1: Integer; // Calculate (N - 1) as a canonical integer
    type Neg: Integer; // Calculate (-N) as a canonical integer
    type Shift: Integer; // Calculate (N << 1) as a canonical integer
    type ShiftAdd1: Integer; // Calculate (N << 1) + 1) as a canonical integer
}

impl Integer for Zero {
    const VALUE: i128 = 0;
    type Add1 = One;
    type Sub1 = NegOne;
    type Neg = Zero;
    type Shift = Zero;
    type ShiftAdd1 = One;
}

impl Integer for NegOne {
    const VALUE: i128 = -1;
    type Add1 = Zero;
    type Sub1 = NegTwo;
    type Neg = One;
    type Shift = NegTwo;
    type ShiftAdd1 = 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 = N::VALUE << 1;
    type Add1 = <N as Integer>::ShiftAdd1;
    type Sub1 = <<N as Integer>::Sub1 as Integer>::ShiftAdd1;
    type Neg = <<N as Integer>::Neg as Integer>::Shift;
    type Shift = Bit0<Bit0<N>>;
    type ShiftAdd1 = Bit1<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::VALUE << 1) | 1;
    type Add1 = <<N as Integer>::Add1 as Integer>::Shift;
    type Sub1 = <N as Integer>::Shift;
    type Neg = <<<N as Integer>::Neg as Integer>::Sub1 as Integer>::ShiftAdd1;
    type Shift = Bit0<Bit1<N>>;
    type ShiftAdd1 = Bit1<Bit1<N>>;
}

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

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

trait Add<Other: Integer>: Integer {
    type Result: Integer;
}

impl<N: Integer> Add<N> for Zero {
    type Result = N;
}

impl<N: Integer> Add<N> for NegOne {
    type Result = <N as Integer>::Sub1;
}

impl<N: NotZero> Add<Zero> for Bit0<N> {
    type Result = Bit0<N>;
}

impl<N: NotZero> Add<NegOne> for Bit0<N> {
    type Result = <<N as Integer>::Sub1 as Integer>::ShiftAdd1;
}

impl<N: NotZero, M: NotZero> Add<Bit0<M>> for Bit0<N>
where
    N: Add<M>,
{
    type Result = <<N as Add<M>>::Result as Integer>::Shift;
}

impl<N: NotZero, M: NotNegOne> Add<Bit1<M>> for Bit0<N>
where
    N: Add<M>,
{
    type Result = <<N as Add<M>>::Result as Integer>::ShiftAdd1;
}

impl<N: NotNegOne> Add<Zero> for Bit1<N> {
    type Result = Bit1<N>;
}

impl<N: NotNegOne> Add<NegOne> for Bit1<N> {
    type Result = <N as Integer>::Shift;
}

impl<N: NotNegOne, M: NotZero> Add<Bit0<M>> for Bit1<N>
where
    N: Add<M>,
{
    type Result = <<N as Add<M>>::Result as Integer>::ShiftAdd1;
}

impl<N: NotNegOne, M: NotNegOne> Add<Bit1<M>> for Bit1<N>
where
    N: Add<M>,
{
    type Result = <<<N as Add<M>>::Result as Integer>::Add1 as Integer>::Shift;
}