inf_add 0.1.0

//! # Inf add
//!
//! `inf_add` desribes a struct and related functions which
//! allow you to infinitely add and subtract to/from a positive
//! number. The number is stored as a vector of u128 unsigned
//! integers, and converted to base 10 for displaying (as such,
//! larger numbers have larger computation cost, especially
//! for displaying).

use std::{fmt, ops};

#[derive(Clone)]
pub struct InfInt(pub Vec<u128>);

impl InfInt {
    pub fn new(var: u128) -> Self {
        InfInt(vec![var])
    }

    pub fn add_destroy(&mut self, other: &InfInt) {
        if self.0.len() == 0 {
            self.0 = other.0.clone();
            return; //self is empty, copy other
        }
        let mut carry = false;
        //loop through every item the other array
        let mut idx = 0;
        while idx < other.0.len() {
            if idx > self.0.len() - 1 {
                //if no matching item in self
                self.0.push(0);
            }
            //add actual values together
            let (res_temp, car_temp1) = u128::add_and_carry(self.0[idx], other.0[idx]);
            //add carry to result
            (self.0[idx], carry) = u128::add_and_carry(res_temp, carry as u128);
            //set carry (only one carry can be true at once)
            carry = car_temp1 || carry;
            idx += 1;
        }
        //propogate carry throughout rest of self
        while carry {
            if idx >= self.0.len() {
                //if no matching item in self, add new item
                self.0.push(1);
                break;
            }
            (self.0[idx], carry) = u128::add_and_carry(self.0[idx], 1);
            idx += 1;
        }
    }

    pub fn subtract_destroy(&mut self, other: &InfInt) {
        if other.0.len() > self.0.len() {
            // subtracting more than in number, return 0
            self.0 = vec![0];
        }
        //
        let mut carry = false;
        //loop through every item in other array
        let mut idx = 0;
        while idx < other.0.len() {
            //subtract main values
            let mut temp_carry = self.0[idx] < other.0[idx];
            self.0[idx] = self.0[idx].wrapping_sub(other.0[idx]);
            //subtract carry value
            temp_carry = temp_carry || (self.0[idx] == 0);
            self.0[idx] = self.0[idx].wrapping_sub(carry as u128);
            carry = temp_carry;
            idx += 1;
        }
        if carry {
            //propogate carry through rest of self
            loop {
                if idx >= self.0.len() {
                    // subtracting more than in number, return 0
                    self.0 = vec![0];
                    break;
                } else if self.0[idx] == 0 {
                    //carry
                    self.0[idx] = u128::MAX;
                } else {
                    //no carry
                    self.0[idx] -= 1;
                    break;
                }
                idx += 1;
            }
        }

        //remove trailing 0s
        while self.0.len() > 1 && *self.0.last().unwrap() == 0 {
            self.0.pop();
        }
    }

    pub fn to_base_10_array(&self) -> Vec<u8> {
        let mut array_out = vec![0];
        //
        //for every u128
        for i in 0..self.0.len() {
            //
            //convert each digit of the current item
            for j in 0..128 {
                //if bit is set
                if ((self.0[i] >> j) & 1) == 1 {
                    let mut new_value = vec![1];
                    //construct base 10 array from bit by multiply base 10 by 2 the appropriate amount of times
                    for _ in 0..((i * 128) + j) {
                        //double first digit
                        let (mut res, mut carry) =
                            base_10_add_and_carry(new_value[0], new_value[0]);
                        new_value[0] = res;
                        //
                        //double rest of digits
                        for k in 1..new_value.len() {
                            let temp_carry = carry;
                            (res, carry) = base_10_add_and_carry(new_value[k], new_value[k]);
                            //doubled value will always be even, so carry can be added without considering overflow
                            new_value[k] = res + temp_carry as u8;
                        }
                        //
                        if carry {
                            new_value.push(1);
                        }
                    }
                    //
                    //add base 10 array to array_out
                    let mut carry = false;
                    let mut k = 0;
                    while k < new_value.len() {
                        if k > array_out.len() - 1 {
                            array_out.push(0);
                        }
                        //add newly create base 10 digit value to out array
                        let (res, car_temp) = base_10_add_and_carry(array_out[k], new_value[k]);
                        //add carry from previous loop
                        (array_out[k], carry) = base_10_add_and_carry(res, carry as u8);
                        //set carry (only one carry can be true at once)
                        carry = car_temp || carry;
                        k += 1;
                    }
                    //propagate carry throughout array_out
                    while carry {
                        if k > array_out.len() - 1 {
                            array_out.push(0);
                        }
                        (array_out[k], carry) = base_10_add_and_carry(array_out[k], 1);
                        k += 1;
                    }
                }
            }
        }
        //
        array_out
    }
}

pub trait AddAndCarry<T, Output = (T, bool)> {
    fn add_and_carry(a: T, b: T) -> Output;
}

impl AddAndCarry<u128> for u128 {
    fn add_and_carry(a: u128, b: u128) -> (u128, bool) {
        let result = a.wrapping_add(b);
        let carry = result < a || result < b;
        (result, carry)
    }
}

impl AddAndCarry<u8> for u8 {
    fn add_and_carry(a: u8, b: u8) -> (u8, bool) {
        let result = a.wrapping_add(b);
        let carry = result < a || result < b;
        (result, carry)
    }
}

fn base_10_add_and_carry(a: u8, b: u8) -> (u8, bool) {
    let result = a + b;
    let carry = result > 9;
    (result % 10, carry)
}

impl fmt::Debug for InfInt {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut result = String::new();
        let base_10_version = self.to_base_10_array();
        for number in base_10_version.iter().rev() {
            result.push_str(&number.to_string());
        }
        write!(f, "{}", result)
    }
}

impl ops::Add<InfInt> for InfInt {
    type Output = InfInt;

    fn add(self, other: InfInt) -> InfInt {
        let mut result = self.clone();
        result.add_destroy(&other);
        result
    }
}

impl ops::Add<u128> for InfInt {
    type Output = InfInt;

    fn add(self, other: u128) -> InfInt {
        let mut result = self.clone();
        result.add_destroy(&InfInt::new(other));
        result
    }
}

impl PartialEq for InfInt {
    fn eq(&self, other: &Self) -> bool {
        self.0 == other.0
    }
}

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

    #[test]
    fn test_add_and_carry() {
        let (result, carry) = u128::add_and_carry(1, 2);
        assert_eq!(result, 3);
        assert!(!carry);

        let (result, carry) = u128::add_and_carry(u128::MAX, 1);
        assert_eq!(result, 0);
        assert!(carry);
    }

    #[test]
    fn test_add_destroy() {
        let mut a = InfInt::new(1);
        let b = InfInt::new(2);
        a.add_destroy(&b);
        assert_eq!(a, InfInt::new(3));
    }

    #[test]
    fn add_new_item() {
        let mut a = InfInt::new(1);
        a.add_destroy(&InfInt::new(u128::MAX));
        //
        let mut answer = InfInt::new(0);
        answer.0.push(1);
        //
        println!("a: {:?}", a);
        println!("answer: {:?}", answer);
        //
        assert_eq!(a, answer);
    }

    #[test]
    fn add_two_items() {
        let mut a = InfInt::new(5);
        a.add_destroy(&InfInt::new(u128::MAX));
        a.add_destroy(&InfInt::new(u128::MAX));
        let mut b = InfInt::new(3);
        b.0.push(2);
        assert_eq!(a, b);
    }

    #[test]
    fn add_with_long_carry() {
        let mut a = InfInt::new(u128::MAX);
        a.0.push(u128::MAX);
        a.0.push(u128::MAX);
        a.add_destroy(&InfInt::new(1));
        //
        let mut answer = InfInt::new(0);
        answer.0.push(0);
        answer.0.push(0);
        answer.0.push(1);
        //
        assert_eq!(a, answer);
    }

    #[test]
    fn test_subtract_destroy() {
        let mut a = InfInt::new(5);
        let b = InfInt::new(2);
        a.subtract_destroy(&b);
        assert_eq!(a, InfInt::new(3));
    }

    #[test]
    fn test_subtract_bigger() {
        let mut a = InfInt::new(5);
        let b = InfInt::new(10);
        a.subtract_destroy(&b);
        assert_eq!(a, InfInt::new(0)); // should return 0
    }

    #[test]
    fn test_to_base_10_array() {
        let a = InfInt::new(123456789);
        let base_10_array = a.to_base_10_array();
        assert_eq!(base_10_array, vec![9, 8, 7, 6, 5, 4, 3, 2, 1]); // should match the digits in reverse order
    }

    #[test]
    fn test_small_to_base_10_array() {
        let a = InfInt::new(5);
        let base_10_array = a.to_base_10_array();
        assert_eq!(base_10_array, vec![5]);
    }

    #[test]
    fn test_carry_to_base_10_array() {
        let a = InfInt::new(10);
        let base_10_array = a.to_base_10_array();
        assert_eq!(base_10_array, vec![0, 1]);
    }

    #[test]
    fn test_subtract_carry() {
        let mut a = InfInt::new(0);
        a.0.push(1);
        let b = InfInt::new(1);
        a.subtract_destroy(&b);

        assert_eq!(a, InfInt::new(u128::MAX));
        assert_eq!(a.0.len(), InfInt::new(u128::MAX).0.len());
    }

    #[test]
    fn test_add_and_subtract() {
        let mut a = InfInt::new(10);
        a.add_destroy(&InfInt::new(5));
        assert_eq!(a, InfInt::new(15));

        a.subtract_destroy(&InfInt::new(12));
        assert_eq!(a, InfInt::new(3));
    }
}