Created
June 23, 2021 00:20
-
-
Save orez-/ebb07d65bd8a8796a90e185752abf61b to your computer and use it in GitHub Desktop.
an itermut implementation for a BigInt struct
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
const ZERO: u8 = '0' as u8; | |
#[derive(Debug)] | |
pub struct BigInt(Vec<u8>); | |
impl BigInt { | |
pub fn new(mut num: u64) -> Self { // not a good constructor, just for testing | |
let mut digits = Vec::new(); | |
while num != 0 { | |
digits.push((num % 10) as u8); | |
num /= 10; | |
} | |
BigInt(digits) | |
} | |
pub fn to_u64(&self) -> u64 { | |
let mut num = 0; | |
let mut exp = 1; | |
for d in self.0.iter() { | |
num += *d as u64 * exp; | |
exp *= 10; | |
} | |
num | |
} | |
pub fn to_string(&self) -> String { | |
if self.0.is_empty() { return "0".to_string(); } | |
let mut answer = String::with_capacity(self.0.len()); | |
for digit in self.0.iter().rev() { | |
answer.push((digit + ZERO) as char); | |
} | |
answer | |
} | |
fn digits_mut(&mut self) -> BigIntDigits { | |
BigIntDigits::new(self) | |
} | |
pub fn add(&mut self, num: &BigInt) { | |
let mut carry = 0; | |
let mut digits_mut = self.digits_mut(); | |
for d2 in num.0.iter() { | |
let d = digits_mut.next().unwrap(); | |
let digit_total = *d + d2 + carry; | |
*d = digit_total % 10; | |
carry = digit_total / 10; | |
} | |
*digits_mut.next().unwrap() += carry; | |
} | |
} | |
struct BigIntDigits<'a> { | |
data: &'a mut BigInt, | |
idx: usize, | |
} | |
impl<'a> BigIntDigits<'a> { | |
fn new(data: &'a mut BigInt) -> Self { | |
Self { | |
data, | |
idx: 0, | |
} | |
} | |
} | |
impl<'a> Iterator for BigIntDigits<'a> { | |
type Item = &'a mut u8; | |
fn next(&mut self) -> Option<Self::Item> { | |
if self.idx == self.data.0.len() { | |
self.data.0.push(0); | |
} | |
let ptr = std::ptr::addr_of_mut!(self.data.0[self.idx]); | |
self.idx += 1; | |
// SAFETY: haha idk ᖍ(ツ)ᖌ | |
unsafe { Some(&mut *ptr) } | |
} | |
} | |
impl Drop for BigIntDigits<'_> { | |
fn drop(&mut self) { | |
let digits = &mut self.data.0; | |
let len = digits.iter().rposition(|&b| b != 0).map_or(0, |i| i + 1); | |
digits.truncate(len); | |
} | |
} | |
fn main() { | |
let mut num1 = BigInt::new(999); | |
let num2 = BigInt::new(985); | |
num1.add(&num2); | |
println!("999 + 985 = {}", num1.to_string()); | |
let mut num1 = BigInt::new(123); | |
let num2 = BigInt::new(426); | |
num1.add(&num2); | |
println!("123 + 426 = {}", num1.to_string()); | |
let mut num1 = BigInt::new(2); | |
let num2 = BigInt::new(3453899); | |
num1.add(&num2); | |
println!("2 + 3453899 = {}", num1.to_string()); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment