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

#[cfg(feature = "doc-images")]
use embed_doc_image::embed_doc_image;
use malachite_base::comparison::traits::Min;
use malachite_base::named::Named;
use malachite_base::num::basic::traits::{One, Two, Zero};
use malachite_base::slices::slice_trailing_zeros;
use natural::InnerNatural::{Large, Small};
use platform::Limb;

/// 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);

macro_rules! natural_zero {
    () => {
        Natural(Small(0))
    };
}

macro_rules! natural_one {
    () => {
        Natural(Small(1))
    };
}

macro_rules! natural_two {
    () => {
        Natural(Small(2))
    };
}

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_zero!();
}

/// The constant 1.
impl One for Natural {
    const ONE: Natural = natural_one!();
}

/// The constant 2.
impl Two for Natural {
    const TWO: Natural = natural_two!();
}

/// The minimum value of a [`Natural`], 0.
impl Min for Natural {
    const MIN: Natural = natural_zero!();
}

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 logic and bit manipulation.
pub mod logic;
/// Iterators that generate [`Natural`]s randomly.
pub mod random;