1use std::cmp::Ordering;
13use std::fmt;
14use std::sync::Arc;
15
16use num_bigint::BigInt;
17use num_integer::Integer as _;
18use num_traits::{One, Signed, ToPrimitive};
19
20use crate::ctx::IntMode;
21use crate::error::{ErrorKind, Result, ValueError};
22
23#[derive(Clone)]
28pub enum Int {
29 Small(i64),
31 Big(Arc<BigInt>),
33}
34
35const MAX_POW_BITS: u64 = 1 << 26;
38
39fn overflow(what: &str) -> ValueError {
40 ValueError::new(
41 ErrorKind::Overflow,
42 format!("Overflow when computing {what}"),
43 )
44}
45
46impl Int {
47 pub const ZERO: Self = Self::Small(0);
49 pub const ONE: Self = Self::Small(1);
51
52 #[must_use]
54 pub fn from_big(b: BigInt) -> Self {
55 match b.to_i64() {
56 Some(v) => Self::Small(v),
57 None => Self::Big(Arc::new(b)),
58 }
59 }
60
61 #[must_use]
63 pub fn to_i64(&self) -> Option<i64> {
64 match self {
65 Self::Small(v) => Some(*v),
66 Self::Big(b) => b.to_i64(),
67 }
68 }
69
70 #[must_use]
72 pub fn to_i32(&self) -> Option<i32> {
73 self.to_i64().and_then(|v| i32::try_from(v).ok())
74 }
75
76 #[must_use]
78 pub fn to_big(&self) -> BigInt {
79 match self {
80 Self::Small(v) => BigInt::from(*v),
81 Self::Big(b) => (**b).clone(),
82 }
83 }
84
85 #[must_use]
87 pub fn is_negative(&self) -> bool {
88 match self {
89 Self::Small(v) => *v < 0,
90 Self::Big(b) => b.is_negative(),
91 }
92 }
93
94 pub fn from_literal(digits: &str, mode: IntMode) -> Result<Self> {
103 if digits.is_empty() || !digits.bytes().all(|b| b.is_ascii_digit()) {
104 return Err(ValueError::new(
105 ErrorKind::Argument,
106 format!("Not a decimal numeral: {digits}"),
107 ));
108 }
109 let big: BigInt = digits.parse().map_err(|_| {
110 ValueError::new(
111 ErrorKind::Argument,
112 format!("Not a decimal numeral: {digits}"),
113 )
114 })?;
115 Self::from_literal_value(big, digits, mode)
116 }
117
118 pub fn from_literal_value(value: BigInt, text: &str, mode: IntMode) -> Result<Self> {
124 let v = Self::from_big(value);
125 if mode == IntMode::Tlc && v.to_i32().is_none() {
126 return Err(ValueError::new(
127 ErrorKind::IntegerTooBig,
128 format!("TLC can't handle a number this big.\n{text}"),
129 ));
130 }
131 Ok(v)
132 }
133
134 fn tlc_operand(&self) -> Result<i32> {
135 self.to_i32().ok_or_else(|| {
136 ValueError::new(
137 ErrorKind::Overflow,
138 format!("Overflow when computing {self} (not a 32-bit TLC integer)"),
139 )
140 })
141 }
142
143 pub fn add(&self, other: &Self, mode: IntMode) -> Result<Self> {
148 match mode {
149 IntMode::Tlc => {
150 let (a, b) = (self.tlc_operand()?, other.tlc_operand()?);
151 a.checked_add(b)
152 .map(|r| Self::Small(i64::from(r)))
153 .ok_or_else(|| overflow(&format!("{a}+{b}")))
154 }
155 IntMode::Big => Ok(match (self, other) {
156 (Self::Small(a), Self::Small(b)) => match a.checked_add(*b) {
157 Some(r) => Self::Small(r),
158 None => Self::from_big(BigInt::from(*a) + b),
159 },
160 _ => Self::from_big(self.to_big() + other.to_big()),
161 }),
162 }
163 }
164
165 pub fn sub(&self, other: &Self, mode: IntMode) -> Result<Self> {
170 match mode {
171 IntMode::Tlc => {
172 let (a, b) = (self.tlc_operand()?, other.tlc_operand()?);
173 a.checked_sub(b)
174 .map(|r| Self::Small(i64::from(r)))
175 .ok_or_else(|| overflow(&format!("{a}-{b}")))
176 }
177 IntMode::Big => Ok(match (self, other) {
178 (Self::Small(a), Self::Small(b)) => match a.checked_sub(*b) {
179 Some(r) => Self::Small(r),
180 None => Self::from_big(BigInt::from(*a) - b),
181 },
182 _ => Self::from_big(self.to_big() - other.to_big()),
183 }),
184 }
185 }
186
187 pub fn mul(&self, other: &Self, mode: IntMode) -> Result<Self> {
192 match mode {
193 IntMode::Tlc => {
194 let (a, b) = (self.tlc_operand()?, other.tlc_operand()?);
195 a.checked_mul(b)
196 .map(|r| Self::Small(i64::from(r)))
197 .ok_or_else(|| overflow(&format!("{a}*{b}")))
198 }
199 IntMode::Big => Ok(match (self, other) {
200 (Self::Small(a), Self::Small(b)) => match a.checked_mul(*b) {
201 Some(r) => Self::Small(r),
202 None => Self::from_big(BigInt::from(*a) * b),
203 },
204 _ => Self::from_big(self.to_big() * other.to_big()),
205 }),
206 }
207 }
208
209 pub fn neg(&self, mode: IntMode) -> Result<Self> {
215 match mode {
216 IntMode::Tlc => {
217 let a = self.tlc_operand()?;
218 a.checked_neg()
219 .map(|r| Self::Small(i64::from(r)))
220 .ok_or_else(|| overflow("--2147483648"))
221 }
222 IntMode::Big => Ok(match self {
223 Self::Small(a) => match a.checked_neg() {
224 Some(r) => Self::Small(r),
225 None => Self::from_big(-BigInt::from(*a)),
226 },
227 Self::Big(b) => Self::from_big(-(**b).clone()),
228 }),
229 }
230 }
231
232 pub fn div(&self, other: &Self, mode: IntMode) -> Result<Self> {
238 if other.is_zero() {
239 return Err(ValueError::new(
240 ErrorKind::DivisionByZero,
241 "The second argument of \\div is 0.",
242 ));
243 }
244 match mode {
245 IntMode::Tlc => {
246 let (a, b) = (self.tlc_operand()?, other.tlc_operand()?);
247 if a == i32::MIN && b == -1 {
248 return Err(overflow("-2147483648 \\div -1"));
249 }
250 Ok(Self::Small(i64::from(num_integer::Integer::div_floor(
251 &a, &b,
252 ))))
253 }
254 IntMode::Big => Ok(match (self, other) {
255 (Self::Small(a), Self::Small(b)) if !(*a == i64::MIN && *b == -1) => {
256 Self::Small(num_integer::Integer::div_floor(a, b))
257 }
258 _ => Self::from_big(self.to_big().div_floor(&other.to_big())),
259 }),
260 }
261 }
262
263 pub fn div_naturals(&self, other: &Self, mode: IntMode) -> Result<Self> {
286 match mode {
287 IntMode::Tlc => {
288 if other.is_zero() {
289 return self.div(other, mode);
290 }
291 let (a, b) = (self.tlc_operand()?, other.tlc_operand()?);
292 let mut q = a.wrapping_div(b);
293 if q < 0 && q.wrapping_mul(b) != a {
294 q -= 1;
295 }
296 Ok(Self::Small(i64::from(q)))
297 }
298 IntMode::Big => self.div(other, mode),
299 }
300 }
301
302 pub fn rem(&self, other: &Self, mode: IntMode) -> Result<Self> {
307 if !other.is_positive() {
308 return Err(ValueError::new(
309 ErrorKind::Argument,
310 format!(
311 "The second argument of % should be a positive number, but instead it is:\n{other}"
312 ),
313 ));
314 }
315 match mode {
316 IntMode::Tlc => {
317 let (a, b) = (self.tlc_operand()?, other.tlc_operand()?);
318 Ok(Self::Small(i64::from(num_integer::Integer::mod_floor(
319 &a, &b,
320 ))))
321 }
322 IntMode::Big => Ok(match (self, other) {
323 (Self::Small(a), Self::Small(b)) => {
324 Self::Small(num_integer::Integer::mod_floor(a, b))
325 }
326 _ => Self::from_big(self.to_big().mod_floor(&other.to_big())),
327 }),
328 }
329 }
330
331 pub fn pow(&self, other: &Self, mode: IntMode) -> Result<Self> {
338 if other.is_negative() {
339 return Err(ValueError::new(
340 ErrorKind::Argument,
341 format!(
342 "The second argument of ^ should be a natural number, but instead it is:\n{other}"
343 ),
344 ));
345 }
346 if other.is_zero() {
347 if self.is_zero() {
348 return Err(ValueError::new(
349 ErrorKind::NullPowerNull,
350 "0^0 is undefined.",
351 ));
352 }
353 return Ok(Self::ONE);
354 }
355 match mode {
356 IntMode::Tlc => {
357 let (a, b) = (self.tlc_operand()?, other.tlc_operand()?);
358 let mut res = i64::from(a);
359 for _ in 1..b {
360 if a.unsigned_abs() <= 1 {
363 res = if a == -1 && b % 2 == 0 {
364 1
365 } else {
366 i64::from(a)
367 };
368 break;
369 }
370 res *= i64::from(a);
371 if res < i64::from(i32::MIN) || res > i64::from(i32::MAX) {
372 return Err(overflow(&format!("{a}^{b}")));
373 }
374 }
375 Ok(Self::Small(res))
376 }
377 IntMode::Big => {
378 let base = self.to_big();
379 if base.abs() <= BigInt::one() {
380 let odd = other.to_big().is_odd();
381 return Ok(if base.is_negative() && !odd {
382 Self::ONE
383 } else {
384 self.clone()
385 });
386 }
387 let exp = other.to_i64().and_then(|e| u64::try_from(e).ok());
388 let bits = base.bits();
389 match exp {
390 Some(e) if e.saturating_mul(bits) <= MAX_POW_BITS => {
391 let e = u32::try_from(e).unwrap_or(u32::MAX);
392 Ok(Self::from_big(num_traits::Pow::pow(base, e)))
393 }
394 _ => Err(ValueError::new(
395 ErrorKind::DiveLimit,
396 format!(
397 "The value of {self}^{other} is too large: it exceeds dive's limit of {MAX_POW_BITS} bits."
398 ),
399 )),
400 }
401 }
402 }
403 }
404
405 fn is_zero(&self) -> bool {
406 matches!(self, Self::Small(0))
407 }
408
409 fn is_positive(&self) -> bool {
410 match self {
411 Self::Small(v) => *v > 0,
412 Self::Big(b) => b.is_positive(),
413 }
414 }
415}
416
417impl From<i64> for Int {
418 fn from(v: i64) -> Self {
419 Self::Small(v)
420 }
421}
422
423impl From<i32> for Int {
424 fn from(v: i32) -> Self {
425 Self::Small(i64::from(v))
426 }
427}
428
429impl Ord for Int {
432 fn cmp(&self, other: &Self) -> Ordering {
433 match (self, other) {
434 (Self::Small(a), Self::Small(b)) => a.cmp(b),
435 _ => self.to_big().cmp(&other.to_big()),
436 }
437 }
438}
439
440impl PartialEq for Int {
441 fn eq(&self, other: &Self) -> bool {
442 self.cmp(other) == Ordering::Equal
443 }
444}
445
446impl Eq for Int {}
447
448impl std::hash::Hash for Int {
449 fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
450 match self.to_i64() {
451 Some(v) => v.hash(state),
452 None => self.to_big().hash(state),
453 }
454 }
455}
456
457impl PartialOrd for Int {
458 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
459 Some(self.cmp(other))
460 }
461}
462
463impl fmt::Display for Int {
464 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
465 match self {
466 Self::Small(v) => write!(f, "{v}"),
467 Self::Big(b) => write!(f, "{b}"),
468 }
469 }
470}
471
472impl fmt::Debug for Int {
473 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
474 fmt::Display::fmt(self, f)
475 }
476}