Integer addition

integerAddition.rs

use std::fmt;

#[deriving(Clone)]
enum MyInteger {
    Zero(Box<MyInteger>),
    One(Box<MyInteger>),
    End
}

/**
 * Show integer
 * >>> show (One $ One $ Zero $ Zero $ Zero $ End)
 * "11000b"
 * >>> show (End)
 * "b"
 */
fn show_my_integer(num : &MyInteger) -> String {
    match num {
        &Zero(box ref rest) => format!("0{}", show_my_integer(rest)),
        &One(box ref rest) => format!("1{}", show_my_integer(rest)),
        &End => format!("b")
    }
}

impl fmt::Show for MyInteger {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "Hi: {}", show_my_integer(self))
    }
}

/**
 * Flip a number so we can add from the right side
 * >>> flipBinary (One $ Zero $ End)
 * 01b
 * >>> flipBinary (One $ One $ Zero $ End)
 * 011b
 * >>> flipBinary (One $ One $ Zero $ Zero $ Zero $ End)
 * 00011b
 * >>> flipBinary (One $ Zero $ Zero $ End)
 * 001b
 */
fn flip_binary(num : &MyInteger) -> MyInteger {
    return flip_binary_carry(num, &End);
}

fn flip_binary_carry(num : &MyInteger, carry : &MyInteger) -> MyInteger {
    match num {
        &Zero(box ref rest) => flip_binary_carry(rest, &(Zero(box carry.clone()))),
        &One(box ref rest) => flip_binary_carry(rest, &(One(box carry.clone()))),
        &End => carry.clone()
    }
}

/**
 * Add two integers together
 * >>> addition (One $ End) (One $ End)
 * 10b
 * >>> addition (One $ Zero $ Zero $ End) (One $ Zero $ Zero $ End)
 * 1000b
 * >>> addition (One $ One $ One $ End) (One $ One $ One $ One $ End)
 * 10110b
 * >>> addition (One $ One $ One $ One $ End) (One $ One $ One $ One $ End)
 * 11110b
 */
fn addition(a : &MyInteger, b : &MyInteger) -> MyInteger {
    return flip_binary(&addition_carry(&flip_binary(a), &flip_binary(b), false));
}
 
fn addition_carry(a : &MyInteger, b : &MyInteger, carry : bool) -> MyInteger {
    match (a, b, carry) {
        (&One(box ref rest_a), &One(box ref rest_b), true) => One(box addition_carry(rest_a, rest_b, true)),
        (&One(box ref rest_a), &Zero(box ref rest_b), true) => Zero(box addition_carry(rest_a, rest_b, true)),
        (&Zero(box ref rest_a), &One(box ref rest_b), true) => Zero(box addition_carry(rest_a, rest_b, true)),
        (&Zero(box ref rest_a), &Zero(box ref rest_b), true) => One(box addition_carry(rest_a, rest_b, false)),

        (&One(box ref rest_a), &One(box ref rest_b), false) => Zero(box addition_carry(rest_a, rest_b, true)),
        (&One(box ref rest_a), &Zero(box ref rest_b), false) => One(box addition_carry(rest_a, rest_b, false)),
        (&Zero(box ref rest_a), &One(box ref rest_b), false) => One(box addition_carry(rest_a, rest_b, false)),
        (&Zero(box ref rest_a), &Zero(box ref rest_b), false) => Zero(box addition_carry(rest_a, rest_b, false)),

        (&One(box ref rest), &End, true) => Zero(box addition_carry(rest, &End, true)),
        (&Zero(box ref rest), &End, true) => One(box addition_carry(rest, &End, false)),
        (&One(box ref rest), &End, false) => One(box addition_carry(rest, &End, false)),
        (&Zero(box ref rest), &End, false) => Zero(box addition_carry(rest, &End, false)),

        (&End, &One(box ref rest), true) => Zero(box addition_carry(rest, &End, true)),
        (&End, &Zero(box ref rest), true) => One(box addition_carry(rest, &End, false)),
        (&End, &One(box ref rest), false) => One(box addition_carry(rest, &End, false)),
        (&End, &Zero(box ref rest), false) => Zero(box addition_carry(rest, &End, false)),

        (&End, &End, true) => One(box End),
        (&End, &End, false) => End
    }
}

fn main() {
    let foo = One(box Zero(box One(box One(box Zero(box End)))));

    println!("Flip binary {} -> {}", foo, flip_binary(&foo));

    println!("Addition {} + {} = {}", foo, foo, addition(&foo, &foo));
}