Skip to content

Instantly share code, notes, and snippets.

@orez-
Created June 23, 2021 00:20
Show Gist options
  • Save orez-/ebb07d65bd8a8796a90e185752abf61b to your computer and use it in GitHub Desktop.
Save orez-/ebb07d65bd8a8796a90e185752abf61b to your computer and use it in GitHub Desktop.
an itermut implementation for a BigInt struct
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