malachite_base/rational_sequences/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::slices::min_repeating_len;
10use alloc::vec::Vec;
11use core::iter::{Chain, Cycle};
12
13fn rational_sequence_reduce<T: Eq>(non_repeating: &mut Vec<T>, repeating: &mut Vec<T>) {
14 if repeating.is_empty() {
15 return;
16 }
17 repeating.truncate(min_repeating_len(repeating));
18 if non_repeating.is_empty() {
19 return;
20 }
21 let extra_non_repeating = non_repeating
22 .iter()
23 .rev()
24 .zip(repeating.iter().rev().cycle())
25 .take_while(|(x, y)| x == y)
26 .count();
27 if extra_non_repeating != 0 {
28 non_repeating.truncate(non_repeating.len() - extra_non_repeating);
29 let len = repeating.len();
30 repeating.rotate_right(extra_non_repeating % len);
31 }
32}
33
34pub_test! {rational_sequence_is_reduced<T: Eq>(non_repeating: &[T], repeating: &[T]) -> bool {
35 if repeating.is_empty() {
36 return true;
37 }
38 if min_repeating_len(repeating) != repeating.len() {
39 return false;
40 }
41 if non_repeating.is_empty() {
42 return true;
43 }
44 non_repeating
45 .iter()
46 .rev()
47 .zip(repeating.iter().rev().cycle())
48 .take_while(|(x, y)| x == y)
49 .count()
50 == 0
51}}
52
53/// A `RationalSequence` is a sequence that is either finite or eventually repeating, just like the
54/// digits of a rational number.
55///
56/// In testing, the set of rational sequences may be used as a proxy for the set of all sequences,
57/// which is too large to work with.
58#[derive(Clone, Default, Eq, Hash, PartialEq)]
59pub struct RationalSequence<T: Eq> {
60 non_repeating: Vec<T>,
61 repeating: Vec<T>,
62}
63
64impl<T: Eq> RationalSequence<T> {
65 /// Returns whether this `RationalSequence` is empty.
66 ///
67 /// # Worst-case complexity
68 /// Constant time and additional memory.
69 ///
70 /// # Examples
71 /// ```
72 /// use malachite_base::rational_sequences::RationalSequence;
73 ///
74 /// assert_eq!(RationalSequence::<u8>::from_slice(&[]).is_empty(), true);
75 /// assert_eq!(
76 /// RationalSequence::<u8>::from_slice(&[1, 2, 3]).is_empty(),
77 /// false
78 /// );
79 /// assert_eq!(
80 /// RationalSequence::<u8>::from_slices(&[], &[3, 4]).is_empty(),
81 /// false
82 /// );
83 /// assert_eq!(
84 /// RationalSequence::<u8>::from_slices(&[1, 2], &[3, 4]).is_empty(),
85 /// false
86 /// );
87 /// ```
88 pub fn is_empty(&self) -> bool {
89 self.non_repeating.is_empty() && self.repeating.is_empty()
90 }
91
92 /// Returns whether this `RationalSequence` is finite (has no repeating part).
93 ///
94 /// # Worst-case complexity
95 /// Constant time and additional memory.
96 ///
97 /// # Examples
98 /// ```
99 /// use malachite_base::rational_sequences::RationalSequence;
100 ///
101 /// assert_eq!(RationalSequence::<u8>::from_slice(&[]).is_finite(), true);
102 /// assert_eq!(
103 /// RationalSequence::<u8>::from_slice(&[1, 2, 3]).is_finite(),
104 /// true
105 /// );
106 /// assert_eq!(
107 /// RationalSequence::<u8>::from_slices(&[], &[3, 4]).is_finite(),
108 /// false
109 /// );
110 /// assert_eq!(
111 /// RationalSequence::<u8>::from_slices(&[1, 2], &[3, 4]).is_finite(),
112 /// false
113 /// );
114 /// ```
115 pub fn is_finite(&self) -> bool {
116 self.repeating.is_empty()
117 }
118
119 /// Returns the length of this `RationalSequence`. If the sequence is infinite, `None` is
120 /// returned.
121 ///
122 /// For a measure of length that always exists, try [`component_len`](Self::component_len).
123 ///
124 /// # Worst-case complexity
125 /// Constant time and additional memory.
126 ///
127 /// # Examples
128 /// ```
129 /// use malachite_base::rational_sequences::RationalSequence;
130 ///
131 /// assert_eq!(RationalSequence::<u8>::from_slice(&[]).len(), Some(0));
132 /// assert_eq!(
133 /// RationalSequence::<u8>::from_slice(&[1, 2, 3]).len(),
134 /// Some(3)
135 /// );
136 /// assert_eq!(
137 /// RationalSequence::<u8>::from_slices(&[], &[3, 4]).len(),
138 /// None
139 /// );
140 /// assert_eq!(
141 /// RationalSequence::<u8>::from_slices(&[1, 2], &[3, 4]).len(),
142 /// None
143 /// );
144 /// ```
145 pub fn len(&self) -> Option<usize> {
146 if self.repeating.is_empty() {
147 Some(self.non_repeating.len())
148 } else {
149 None
150 }
151 }
152
153 /// Returns the sum of the lengths of the non-repeating and repeating parts of this
154 /// `RationalSequence`.
155 ///
156 /// This is often a more useful way of measuring the complexity of a sequence than
157 /// [`len`](Self::len).
158 ///
159 /// # Worst-case complexity
160 /// Constant time and additional memory.
161 ///
162 /// # Examples
163 /// ```
164 /// use malachite_base::rational_sequences::RationalSequence;
165 ///
166 /// assert_eq!(RationalSequence::<u8>::from_slice(&[]).component_len(), 0);
167 /// assert_eq!(
168 /// RationalSequence::<u8>::from_slice(&[1, 2, 3]).component_len(),
169 /// 3
170 /// );
171 /// assert_eq!(
172 /// RationalSequence::<u8>::from_slices(&[], &[3, 4]).component_len(),
173 /// 2
174 /// );
175 /// assert_eq!(
176 /// RationalSequence::<u8>::from_slices(&[1, 2], &[3, 4]).component_len(),
177 /// 4
178 /// );
179 /// ```
180 pub fn component_len(&self) -> usize {
181 self.non_repeating.len() + self.repeating.len()
182 }
183
184 /// Returns an iterator of references to the elements of this sequence.
185 ///
186 /// # Worst-case complexity
187 /// Constant time and additional memory.
188 ///
189 /// # Examples
190 /// ```
191 /// use itertools::Itertools;
192 /// use malachite_base::rational_sequences::RationalSequence;
193 ///
194 /// let empty: &[u8] = &[];
195 /// assert_eq!(
196 /// RationalSequence::<u8>::from_slice(empty)
197 /// .iter()
198 /// .cloned()
199 /// .collect_vec(),
200 /// empty
201 /// );
202 /// assert_eq!(
203 /// RationalSequence::<u8>::from_slice(&[1, 2, 3])
204 /// .iter()
205 /// .cloned()
206 /// .collect_vec(),
207 /// &[1, 2, 3]
208 /// );
209 /// assert_eq!(
210 /// RationalSequence::<u8>::from_slices(&[], &[3, 4])
211 /// .iter()
212 /// .cloned()
213 /// .take(10)
214 /// .collect_vec(),
215 /// &[3, 4, 3, 4, 3, 4, 3, 4, 3, 4]
216 /// );
217 /// assert_eq!(
218 /// RationalSequence::<u8>::from_slices(&[1, 2], &[3, 4])
219 /// .iter()
220 /// .cloned()
221 /// .take(10)
222 /// .collect_vec(),
223 /// &[1, 2, 3, 4, 3, 4, 3, 4, 3, 4]
224 /// );
225 /// ```
226 pub fn iter(&self) -> Chain<core::slice::Iter<T>, Cycle<core::slice::Iter<T>>> {
227 self.non_repeating
228 .iter()
229 .chain(self.repeating.iter().cycle())
230 }
231}
232
233impl<T: Clone + Eq> RationalSequence<T> {
234 // Returns true iff `self` is valid.
235 //
236 // To be valid, the non-repeating and repeating parts must be reduced. For example, `[1, 2]` and
237 // `[3, 4]` is a reduced pair. On the other hand, `[1, 2]` and `[3, 4, 3, 4]` is a non-reduced
238 // pair representing the same sequence, as is `[1, 2, 3]` and `[4, 3]`. All `RationalSequence`s
239 // must be valid.
240 #[cfg(feature = "test_build")]
241 pub fn is_valid(&self) -> bool {
242 rational_sequence_is_reduced(&self.non_repeating, &self.repeating)
243 }
244}
245
246/// Functions for getting and setting elements in a [`RationalSequence`].
247pub mod access;
248/// Functions for comparing [`RationalSequence`]s.
249pub mod cmp;
250/// Functions for converting a [`RationalSequence`]s to and from a [`Vec`] or a slice.
251pub mod conversion;
252/// Functions for generating all [`RationalSequence`]s over a set of elements.
253pub mod exhaustive;
254#[cfg(feature = "random")]
255/// Functions for generating random [`RationalSequence`]s from a set of elements.
256pub mod random;
257/// Functions for displaying a [`RationalSequence`].
258pub mod to_string;