1 mod try_from;
2
3 use core::fmt;
4 use core::hash::{Hash, Hasher};
5 use core::iter::FusedIterator;
6 #[cfg(feature = "std")]
7 use core::mem;
8
9 pub use self::try_from::{TryFrom, TryFromIntError, TryInto};
10 pub use crate::array::TryFromSliceError;
11 use crate::traits::{Integer, Sealed};
12
13 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
14 pub enum Infallible {}
15
16 impl fmt::Debug for Infallible {
fmt(&self, _: &mut fmt::Formatter<'_>) -> fmt::Result17 fn fmt(&self, _: &mut fmt::Formatter<'_>) -> fmt::Result {
18 match *self {}
19 }
20 }
21
22 impl fmt::Display for Infallible {
fmt(&self, _: &mut fmt::Formatter<'_>) -> fmt::Result23 fn fmt(&self, _: &mut fmt::Formatter<'_>) -> fmt::Result {
24 match *self {}
25 }
26 }
27
28 impl Hash for Infallible {
hash<H: Hasher>(&self, _: &mut H)29 fn hash<H: Hasher>(&self, _: &mut H) {
30 match *self {}
31 }
32 }
33
34 #[inline]
from_fn<T, F>(f: F) -> FromFn<F> where F: FnMut() -> Option<T>,35 pub fn from_fn<T, F>(f: F) -> FromFn<F>
36 where
37 F: FnMut() -> Option<T>,
38 {
39 FromFn(f)
40 }
41
42 #[derive(Clone)]
43 pub struct FromFn<F>(F);
44
45 impl<T, F> Iterator for FromFn<F>
46 where
47 F: FnMut() -> Option<T>,
48 {
49 type Item = T;
50
51 #[inline]
next(&mut self) -> Option<Self::Item>52 fn next(&mut self) -> Option<Self::Item> {
53 (self.0)()
54 }
55 }
56
57 impl<F> fmt::Debug for FromFn<F> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result58 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
59 f.debug_struct("FromFn").finish()
60 }
61 }
62
successors<T, F>(first: Option<T>, succ: F) -> Successors<T, F> where F: FnMut(&T) -> Option<T>,63 pub fn successors<T, F>(first: Option<T>, succ: F) -> Successors<T, F>
64 where
65 F: FnMut(&T) -> Option<T>,
66 {
67 Successors { next: first, succ }
68 }
69
70 #[derive(Clone)]
71 pub struct Successors<T, F> {
72 next: Option<T>,
73 succ: F,
74 }
75
76 impl<T, F> Iterator for Successors<T, F>
77 where
78 F: FnMut(&T) -> Option<T>,
79 {
80 type Item = T;
81
82 #[inline]
next(&mut self) -> Option<Self::Item>83 fn next(&mut self) -> Option<Self::Item> {
84 let item = self.next.take()?;
85 self.next = (self.succ)(&item);
86 Some(item)
87 }
88
89 #[inline]
size_hint(&self) -> (usize, Option<usize>)90 fn size_hint(&self) -> (usize, Option<usize>) {
91 if self.next.is_some() {
92 (1, None)
93 } else {
94 (0, Some(0))
95 }
96 }
97 }
98
99 impl<T, F> FusedIterator for Successors<T, F> where F: FnMut(&T) -> Option<T> {}
100
101 impl<T: fmt::Debug, F> fmt::Debug for Successors<T, F> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result102 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
103 f.debug_struct("Successors")
104 .field("next", &self.next)
105 .finish()
106 }
107 }
108
109 pub trait Slice_v1_34<T>: Sealed<[T]> {
sort_by_cached_key<K, F>(&mut self, f: F) where F: FnMut(&T) -> K, K: Ord110 fn sort_by_cached_key<K, F>(&mut self, f: F)
111 where
112 F: FnMut(&T) -> K,
113 K: Ord;
114 }
115
116 #[cfg(feature = "std")]
117 impl<T> Slice_v1_34<T> for [T] {
118 #[inline]
sort_by_cached_key<K, F>(&mut self, f: F) where F: FnMut(&T) -> K, K: Ord,119 fn sort_by_cached_key<K, F>(&mut self, f: F)
120 where
121 F: FnMut(&T) -> K,
122 K: Ord,
123 {
124 macro_rules! sort_by_key {
125 ($t:ty, $slice:ident, $f:ident) => {{
126 let mut indices: Vec<_> = $slice
127 .iter()
128 .map($f)
129 .enumerate()
130 .map(|(i, k)| (k, i as $t))
131 .collect();
132 indices.sort_unstable();
133 for i in 0..$slice.len() {
134 let mut index = indices[i].1;
135 while (index as usize) < i {
136 index = indices[index as usize].1;
137 }
138 indices[i].1 = index;
139 $slice.swap(i, index as usize);
140 }
141 }};
142 }
143
144 let sz_u8 = mem::size_of::<(K, u8)>();
145 let sz_u16 = mem::size_of::<(K, u16)>();
146 let sz_u32 = mem::size_of::<(K, u32)>();
147 let sz_usize = mem::size_of::<(K, usize)>();
148
149 let len = self.len();
150 if len < 2 {
151 return;
152 }
153 if sz_u8 < sz_u16 && len <= (u8::max_value() as usize) {
154 return sort_by_key!(u8, self, f);
155 }
156 if sz_u16 < sz_u32 && len <= (u16::max_value() as usize) {
157 return sort_by_key!(u16, self, f);
158 }
159 if sz_u32 < sz_usize && len <= (u32::max_value() as usize) {
160 return sort_by_key!(u32, self, f);
161 }
162 sort_by_key!(usize, self, f)
163 }
164 }
165
166 pub trait Pow_v1_34: Integer {
checked_pow(self, exp: u32) -> Option<Self>167 fn checked_pow(self, exp: u32) -> Option<Self>;
saturating_pow(self, exp: u32) -> Self168 fn saturating_pow(self, exp: u32) -> Self;
wrapping_pow(self, exp: u32) -> Self169 fn wrapping_pow(self, exp: u32) -> Self;
overflowing_pow(self, exp: u32) -> (Self, bool)170 fn overflowing_pow(self, exp: u32) -> (Self, bool);
171 }
172
173 macro_rules! impl_pow_for_signed {
174 ($($type:ty)+) => {$(
175 impl Pow_v1_34 for $type {
176 #[must_use = "this returns the result of the operation, without modifying the original"]
177 #[inline]
178 fn checked_pow(self, mut exp: u32) -> Option<Self> {
179 let mut base = self;
180 let mut acc: Self = 1;
181
182 while exp > 1 {
183 if (exp & 1) == 1 {
184 acc = acc.checked_mul(base)?;
185 }
186 exp /= 2;
187 base = base.checked_mul(base)?;
188 }
189
190 if exp == 1 {
191 acc = acc.checked_mul(base)?;
192 }
193
194 Some(acc)
195 }
196
197 #[must_use = "this returns the result of the operation, without modifying the original"]
198 #[inline]
199 fn saturating_pow(self, exp: u32) -> Self {
200 match self.checked_pow(exp) {
201 Some(x) => x,
202 None if self < 0 && exp % 2 == 1 => Self::min_value(),
203 None => Self::max_value(),
204 }
205 }
206
207 #[must_use = "this returns the result of the operation, without modifying the original"]
208 #[inline]
209 fn wrapping_pow(self, mut exp: u32) -> Self {
210 let mut base = self;
211 let mut acc: Self = 1;
212
213 while exp > 1 {
214 if (exp & 1) == 1 {
215 acc = acc.wrapping_mul(base);
216 }
217 exp /= 2;
218 base = base.wrapping_mul(base);
219 }
220
221 if exp == 1 {
222 acc = acc.wrapping_mul(base);
223 }
224
225 acc
226 }
227
228 #[must_use = "this returns the result of the operation, without modifying the original"]
229 #[inline]
230 fn overflowing_pow(self, mut exp: u32) -> (Self, bool) {
231 let mut base = self;
232 let mut acc: Self = 1;
233 let mut overflown = false;
234 let mut r;
235
236 while exp > 1 {
237 if (exp & 1) == 1 {
238 r = acc.overflowing_mul(base);
239 acc = r.0;
240 overflown |= r.1;
241 }
242 exp /= 2;
243 r = base.overflowing_mul(base);
244 base = r.0;
245 overflown |= r.1;
246 }
247
248 if exp == 1 {
249 r = acc.overflowing_mul(base);
250 acc = r.0;
251 overflown |= r.1;
252 }
253
254 (acc, overflown)
255 }
256 }
257 )+};
258 }
259
260 impl_pow_for_signed![i8 i16 i32 i64 i128 isize];
261
262 macro_rules! impl_pow_for_unsigned {
263 ($($type:ty)+) => {$(
264 impl Pow_v1_34 for $type {
265 #[must_use = "this returns the result of the operation, without modifying the original"]
266 #[inline]
267 fn checked_pow(self, mut exp: u32) -> Option<Self> {
268 let mut base = self;
269 let mut acc: Self = 1;
270
271 while exp > 1 {
272 if (exp & 1) == 1 {
273 acc = acc.checked_mul(base)?;
274 }
275 exp /= 2;
276 base = base.checked_mul(base)?;
277 }
278
279 if exp == 1 {
280 acc = acc.checked_mul(base)?;
281 }
282
283 Some(acc)
284 }
285
286 #[must_use = "this returns the result of the operation, without modifying the original"]
287 #[inline]
288 fn saturating_pow(self, exp: u32) -> Self {
289 match self.checked_pow(exp) {
290 Some(x) => x,
291 None => Self::max_value(),
292 }
293 }
294
295 #[must_use = "this returns the result of the operation, without modifying the original"]
296 #[inline]
297 fn wrapping_pow(self, mut exp: u32) -> Self {
298 let mut base = self;
299 let mut acc: Self = 1;
300
301 while exp > 1 {
302 if (exp & 1) == 1 {
303 acc = acc.wrapping_mul(base);
304 }
305 exp /= 2;
306 base = base.wrapping_mul(base);
307 }
308
309 if exp == 1 {
310 acc = acc.wrapping_mul(base);
311 }
312
313 acc
314 }
315
316 #[must_use = "this returns the result of the operation, without modifying the original"]
317 #[inline]
318 fn overflowing_pow(self, mut exp: u32) -> (Self, bool) {
319 let mut base = self;
320 let mut acc: Self = 1;
321 let mut overflown = false;
322 let mut r;
323
324 while exp > 1 {
325 if (exp & 1) == 1 {
326 r = acc.overflowing_mul(base);
327 acc = r.0;
328 overflown |= r.1;
329 }
330 exp /= 2;
331 r = base.overflowing_mul(base);
332 base = r.0;
333 overflown |= r.1;
334 }
335
336 if exp == 1 {
337 r = acc.overflowing_mul(base);
338 acc = r.0;
339 overflown |= r.1;
340 }
341
342 (acc, overflown)
343 }
344 }
345 )+};
346 }
347
348 impl_pow_for_unsigned![u8 u16 u32 u64 u128 usize];
349