malachite_nz/natural/
mod.rs

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

malachite_nz/natural/
mod.rs
