competitive/num/
decimal.rs

1use super::{IterScan, One, Zero};
2use std::{cmp::Ordering, ops::Neg};
3
4pub mod addsub;
5pub mod convert;
6
7#[derive(PartialEq, PartialOrd, Eq, Ord, Copy, Clone, Debug, Hash)]
8enum Sign {
9    Minus,
10    Zero,
11    Plus,
12}
13
14impl Neg for Sign {
15    type Output = Self;
16
17    fn neg(self) -> Self::Output {
18        match self {
19            Sign::Minus => Sign::Plus,
20            Sign::Zero => Sign::Zero,
21            Sign::Plus => Sign::Minus,
22        }
23    }
24}
25
26const ZERO: Decimal = Decimal {
27    sign: Sign::Zero,
28    integer: Vec::new(),
29    decimal: Vec::new(),
30};
31
32const POW10: [u64; RADIX_LEN + 1] = [
33    1,
34    10,
35    100,
36    1_000,
37    10_000,
38    100_000,
39    1_000_000,
40    10_000_000,
41    100_000_000,
42    1_000_000_000,
43    10_000_000_000,
44    100_000_000_000,
45    1_000_000_000_000,
46    10_000_000_000_000,
47    100_000_000_000_000,
48    1_000_000_000_000_000,
49    10_000_000_000_000_000,
50    100_000_000_000_000_000,
51    1_000_000_000_000_000_000,
52];
53
54const RADIX: u64 = POW10[RADIX_LEN];
55const RADIX_LEN: usize = 18;
56
57#[derive(Clone, Debug, PartialEq, Eq, Hash)]
58pub struct Decimal {
59    sign: Sign,
60    integer: Vec<u64>,
61    decimal: Vec<u64>,
62}
63
64impl Default for Decimal {
65    fn default() -> Self {
66        Decimal::zero()
67    }
68}
69
70impl Zero for Decimal {
71    fn zero() -> Self {
72        ZERO
73    }
74
75    fn is_zero(&self) -> bool {
76        self.sign == Sign::Zero
77    }
78}
79
80impl One for Decimal {
81    fn one() -> Self {
82        Decimal {
83            sign: Sign::Plus,
84            integer: vec![1],
85            decimal: Vec::new(),
86        }
87    }
88}
89
90impl PartialOrd for Decimal {
91    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
92        Some(self.cmp(other))
93    }
94}
95
96impl Ord for Decimal {
97    fn cmp(&self, other: &Self) -> Ordering {
98        self.sign.cmp(&other.sign).then_with(|| match self.sign {
99            Sign::Minus => other.cmp_absolute_parts(self),
100            Sign::Zero => Ordering::Equal,
101            Sign::Plus => self.cmp_absolute_parts(other),
102        })
103    }
104}
105
106impl Neg for Decimal {
107    type Output = Self;
108
109    fn neg(self) -> Self::Output {
110        Self {
111            sign: -self.sign,
112            integer: self.integer,
113            decimal: self.decimal,
114        }
115    }
116}
117
118impl Decimal {
119    fn cmp_absolute_parts(&self, other: &Self) -> Ordering {
120        self.integer
121            .len()
122            .cmp(&other.integer.len())
123            .then_with(|| self.integer.iter().rev().cmp(other.integer.iter().rev()))
124            .then_with(|| self.decimal.iter().cmp(other.decimal.iter()))
125    }
126    fn normalize(&mut self) {
127        if let Some(&0) = self.decimal.last() {
128            let len = self
129                .decimal
130                .iter()
131                .rposition(|&d| d != 0)
132                .map_or(0, |i| i + 1);
133            self.decimal.truncate(len);
134        }
135        if self.decimal.len() < self.decimal.capacity() / 4 {
136            self.decimal.shrink_to_fit();
137        }
138        if let Some(&0) = self.integer.last() {
139            let len = self
140                .integer
141                .iter()
142                .rposition(|&d| d != 0)
143                .map_or(0, |i| i + 1);
144            self.integer.truncate(len);
145        }
146        if self.integer.len() < self.integer.capacity() / 4 {
147            self.integer.shrink_to_fit();
148        }
149        if self.integer.is_empty() && self.decimal.is_empty() {
150            self.sign = Sign::Zero;
151        }
152    }
153}
154
155#[cfg(test)]
156mod tests {
157    use super::*;
158    use test_case::test_case;
159
160    #[test_case("0", "0", Ordering::Equal; "zero")]
161    #[test_case("0", "1", Ordering::Less; "zero vs plus")]
162    #[test_case("0", "-1", Ordering::Greater; "zero vs minus")]
163    #[test_case("1", "0", Ordering::Greater; "plus vs zero")]
164    #[test_case("1", "1", Ordering::Equal; "plus vs plus")]
165    #[test_case("1", "-1", Ordering::Greater; "plus vs minus")]
166    #[test_case("-1", "0", Ordering::Less; "minus vs zero")]
167    #[test_case("-1", "1", Ordering::Less; "minus vs plus")]
168    #[test_case("-1", "-1", Ordering::Equal; "minus vs minus")]
169    #[test_case("1000000000000000000", "1", Ordering::Greater; "long integer")]
170    #[test_case("-1000000000000000000", "-1", Ordering::Less; "negative long integer")]
171    #[test_case("0.1", "0.01", Ordering::Greater; "decimal")]
172    #[test_case("0.1", "0.1", Ordering::Equal; "decimal equal")]
173    #[test_case("0.1", "0.2", Ordering::Less; "decimal less")]
174    #[test_case("0.1", "0.0000000000000000001", Ordering::Greater; "long decimal")]
175    fn test_cmp(a: &str, b: &str, expected: Ordering) {
176        let a = a.parse::<Decimal>().unwrap();
177        let b = b.parse::<Decimal>().unwrap();
178        assert_eq!(a.cmp(&b), expected);
179    }
180
181    #[test_case("0", "0"; "zero")]
182    #[test_case("1", "-1"; "plus")]
183    #[test_case("-1", "1"; "minus")]
184    fn test_neg(a: &str, expected: &str) {
185        let a = a.parse::<Decimal>().unwrap();
186        let expected = expected.parse::<Decimal>().unwrap();
187        assert_eq!(-a, expected);
188    }
189}
competitive/num/decimal.rs

competitive/num/
decimal.rs
