1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152
// Copyright © 2024 Mikhail Hogrefe
//
// This file is part of Malachite.
//
// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
use crate::natural::InnerNatural::{Large, Small};
use crate::platform::Limb;
use alloc::string::String;
use alloc::vec::Vec;
#[cfg(feature = "doc-images")]
use embed_doc_image::embed_doc_image;
use malachite_base::comparison::traits::Min;
use malachite_base::named::Named;
#[cfg(feature = "float_helpers")]
use malachite_base::num::basic::integers::PrimitiveInt;
use malachite_base::num::basic::traits::{One, Two, Zero};
use malachite_base::slices::slice_trailing_zeros;
/// A natural (non-negative) integer.
///
/// Any `Natural` small enough to fit into a [`Limb`](crate#limbs) is represented inline. Only
/// `Natural`s outside this range incur the costs of heap-allocation. Here's a diagram of a slice of
/// `Natural`s (using 32-bit limbs) containing the first 8 values of [Sylvester's
/// sequence](https://oeis.org/A000058):
///
/// ![Natural memory layout][natural-mem-layout]
#[cfg_attr(
feature = "doc-images",
embed_doc_image("natural-mem-layout", "images/natural-mem-layout.svg")
)]
#[derive(Clone, Eq, Hash, PartialEq)]
#[cfg_attr(feature = "serde", derive(Deserialize, Serialize))]
#[cfg_attr(
feature = "serde",
serde(try_from = "SerdeNatural", into = "SerdeNatural")
)]
pub struct Natural(pub(crate) InnerNatural);
// We want to limit the visibility of the `Small` and `Large` constructors to within this crate. To
// do this, we wrap the `InnerNatural` enum in a struct that gets compiled away.
#[derive(Clone, Eq, Hash, PartialEq)]
pub(crate) enum InnerNatural {
Small(Limb),
Large(Vec<Limb>),
}
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[cfg_attr(feature = "serde", serde(transparent))]
pub(crate) struct SerdeNatural(String);
impl Natural {
// If a `Natural` is `Large` but is small enough to be `Small`, make it `Small`.
fn demote_if_small(&mut self) {
if let Natural(Large(ref limbs)) = self {
match limbs.len() {
0 => *self = Natural::ZERO,
1 => *self = Natural(Small(limbs[0])),
_ => {}
}
}
}
// If a `Natural` is `Small`, make it `Large`. Return a reference to the `Limb` vector.
pub(crate) fn promote_in_place(&mut self) -> &mut Vec<Limb> {
if let Natural(Small(x)) = self {
*self = Natural(Large(vec![*x]));
}
if let Natural(Large(ref mut xs)) = self {
xs
} else {
unreachable!();
}
}
pub(crate) fn trim(&mut self) {
if let Natural(Large(ref mut limbs)) = *self {
let trailing_zero_count = slice_trailing_zeros(limbs);
if trailing_zero_count != 0 {
let len = limbs.len();
limbs.truncate(len - trailing_zero_count);
}
}
self.demote_if_small();
}
// Returns true iff `self` is valid. To be valid,
//
// `self` can only be `Large` when it is at least $2^W$, and cannot have leading zero limbs. All
// `Natural`s must be valid.
#[cfg(feature = "test_build")]
pub fn is_valid(&self) -> bool {
match *self {
Natural(Small(_)) => true,
Natural(Large(ref xs)) => xs.len() > 1 && *xs.last().unwrap() != 0,
}
}
}
/// The constant 0.
impl Zero for Natural {
const ZERO: Natural = Natural(Small(0));
}
/// The constant 1.
impl One for Natural {
const ONE: Natural = Natural(Small(1));
}
/// The constant 2.
impl Two for Natural {
const TWO: Natural = Natural(Small(2));
}
/// The minimum value of a [`Natural`], 0.
impl Min for Natural {
const MIN: Natural = Natural::ZERO;
}
#[cfg(feature = "float_helpers")]
impl Natural {
pub const HIGH_BIT: Natural = Natural(Small(1 << (Limb::WIDTH - 1)));
}
impl Default for Natural {
/// The default value of a [`Natural`], 0.
fn default() -> Natural {
Natural::ZERO
}
}
// Implements `Named` for `Natural`.
impl_named!(Natural);
/// Traits for arithmetic.
pub mod arithmetic;
/// Traits for comparing [`Natural`]s for equality or order.
pub mod comparison;
/// Traits for converting to and from [`Natural`]s, converting to and from strings, and extracting
/// digits.
pub mod conversion;
/// Iterators that generate [`Natural`]s without repetition.
pub mod exhaustive;
/// Traits for generating primes, primality testing, and factorization (TODO!)
pub mod factorization;
/// Traits for logic and bit manipulation.
pub mod logic;
#[cfg(feature = "random")]
/// Iterators that generate [`Natural`]s randomly.
pub mod random;