3b867aac0917140baec4313c82fc64c9a02c1436
[rust-101.git] / src / part06.rs
1 // Rust-101, Part 06: Abstract Datastructure, Testing
2 // ==================================================
3
4 use std::cmp;
5 use std::ops;
6
7 pub struct BigInt {
8     data: Vec<u64>, // least significant digits first. The last block will *not* be 0.
9 }
10
11 impl BigInt {
12     pub fn new(x: u64) -> Self {
13         if x == 0 {
14             BigInt { data: vec![] }
15         } else {
16             BigInt { data: vec![x] }
17         }
18     }
19 }
20
21 /// Add with carry, returning the sum and the carry
22 fn overflowing_add(a: u64, b: u64, carry: bool) -> (u64, bool) {
23     match u64::checked_add(a, b) {
24         Some(sum) if !carry => (sum, false),
25         Some(sum) => { // we have to increment the sum by 1, where it may overflow again
26             match u64::checked_add(sum, 1) {
27                 Some(total_sum) => (total_sum, false),
28                 None => (0, true) // we overflowed incrementing by 1, so we are just "at the edge"
29             }
30         },
31         None => {
32             // Get the remainder, i.e., the wrapping sum. This cannot overflow again by adding just 1, so it is safe
33             // to add the carry here.
34             let rem = u64::wrapping_add(a, b) + if carry { 1 } else { 0 };
35             (rem, true)
36         }
37     }
38 }
39
40 #[test]
41 fn test_overflowing_add() {
42     assert_eq!(overflowing_add(10, 100, false), (110, false));
43     assert_eq!(overflowing_add(10, 100, true), (111, false));
44     assert_eq!(overflowing_add(1 << 63, 1 << 63, false), (0, true));
45     assert_eq!(overflowing_add(1 << 63, 1 << 63, true), (1, true));
46     assert_eq!(overflowing_add(1 << 63, (1 << 63) -1 , true), (0, true));
47 }
48
49 impl ops::Add<BigInt> for BigInt {
50     type Output = BigInt;
51     fn add(self, rhs: BigInt) -> Self::Output {
52         let mut result_vec:Vec<u64> = Vec::with_capacity(cmp::max(self.data.len(), rhs.data.len()));
53         let mut carry:bool = false; // the carry bit
54         for (i, val) in self.data.into_iter().enumerate() {
55             // compute next digit and carry
56             let rhs_val = if i < rhs.data.len() { rhs.data[i] } else { 0 };
57             let (sum, new_carry) = overflowing_add(val, rhs_val, carry);
58             // store them
59             result_vec.push(sum);
60             carry = new_carry;
61         }
62         BigInt { data: result_vec }
63     }
64 }
65
66
67