1use super::*;
2use core::convert::{TryFrom, TryInto};
3
4#[cfg(feature = "serde")]
5use core::marker::PhantomData;
6#[cfg(feature = "serde")]
7use serde::de::{
8 Deserialize, Deserializer, Error as DeserializeError, SeqAccess, Visitor,
9};
10#[cfg(feature = "serde")]
11use serde::ser::{Serialize, SerializeSeq, Serializer};
12
13/// Helper to make an `ArrayVec`.
14///
15/// You specify the backing array type, and optionally give all the elements you
16/// want to initially place into the array.
17///
18/// ```rust
19/// use tinyvec::*;
20///
21/// // The backing array type can be specified in the macro call
22/// let empty_av = array_vec!([u8; 16]);
23/// let some_ints = array_vec!([i32; 4] => 1, 2, 3);
24///
25/// // Or left to inference
26/// let empty_av: ArrayVec<[u8; 10]> = array_vec!();
27/// let some_ints: ArrayVec<[u8; 10]> = array_vec!(5, 6, 7, 8);
28/// ```
29#[macro_export]
30macro_rules! array_vec {
31 ($array_type:ty => $($elem:expr),* $(,)?) => {
32 {
33 let mut av: $crate::ArrayVec<$array_type> = Default::default();
34 $( av.push($elem); )*
35 av
36 }
37 };
38 ($array_type:ty) => {
39 $crate::ArrayVec::<$array_type>::default()
40 };
41 ($($elem:expr),*) => {
42 $crate::array_vec!(_ => $($elem),*)
43 };
44 ($elem:expr; $n:expr) => {
45 $crate::ArrayVec::from([$elem; $n])
46 };
47 () => {
48 $crate::array_vec!(_)
49 };
50}
51
52/// An array-backed, vector-like data structure.
53///
54/// * `ArrayVec` has a fixed capacity, equal to the minimum of the array size
55/// and `u16::MAX`. Note that not all capacities are necessarily supported by
56/// default. See comments in [`Array`].
57/// * `ArrayVec` has a variable length, as you add and remove elements. Attempts
58/// to fill the vec beyond its capacity will cause a panic.
59/// * All of the vec's array slots are always initialized in terms of Rust's
60/// memory model. When you remove a element from a location, the old value at
61/// that location is replaced with the type's default value.
62///
63/// The overall API of this type is intended to, as much as possible, emulate
64/// the API of the [`Vec`](https://doc.rust-lang.org/alloc/vec/struct.Vec.html)
65/// type.
66///
67/// ## Construction
68///
69/// You can use the `array_vec!` macro similarly to how you might use the `vec!`
70/// macro. Specify the array type, then optionally give all the initial values
71/// you want to have.
72/// ```rust
73/// # use tinyvec::*;
74/// let some_ints = array_vec!([i32; 4] => 1, 2, 3);
75/// assert_eq!(some_ints.len(), 3);
76/// ```
77///
78/// The [`default`](ArrayVec::new) for an `ArrayVec` is to have a default
79/// array with length 0. The [`new`](ArrayVec::new) method is the same as
80/// calling `default`
81/// ```rust
82/// # use tinyvec::*;
83/// let some_ints = ArrayVec::<[i32; 7]>::default();
84/// assert_eq!(some_ints.len(), 0);
85///
86/// let more_ints = ArrayVec::<[i32; 7]>::new();
87/// assert_eq!(some_ints, more_ints);
88/// ```
89///
90/// If you have an array and want the _whole thing_ so count as being "in" the
91/// new `ArrayVec` you can use one of the `from` implementations. If you want
92/// _part of_ the array then you can use
93/// [`from_array_len`](ArrayVec::from_array_len):
94/// ```rust
95/// # use tinyvec::*;
96/// let some_ints = ArrayVec::from([5, 6, 7, 8]);
97/// assert_eq!(some_ints.len(), 4);
98///
99/// let more_ints = ArrayVec::from_array_len([5, 6, 7, 8], 2);
100/// assert_eq!(more_ints.len(), 2);
101///
102/// let no_ints: ArrayVec<[u8; 5]> = ArrayVec::from_array_empty([1, 2, 3, 4, 5]);
103/// assert_eq!(no_ints.len(), 0);
104/// ```
105#[repr(C)]
106pub struct ArrayVec<A> {
107 len: u16,
108 pub(crate) data: A,
109}
110
111impl<A> Clone for ArrayVec<A>
112where
113 A: Array + Clone,
114 A::Item: Clone,
115{
116 #[inline]
117 fn clone(&self) -> Self {
118 Self { data: self.data.clone(), len: self.len }
119 }
120
121 #[inline]
122 fn clone_from(&mut self, o: &Self) {
123 let iter = self
124 .data
125 .as_slice_mut()
126 .iter_mut()
127 .zip(o.data.as_slice())
128 .take(self.len.max(o.len) as usize);
129 for (dst, src) in iter {
130 dst.clone_from(src)
131 }
132 if let Some(to_drop) =
133 self.data.as_slice_mut().get_mut((o.len as usize)..(self.len as usize))
134 {
135 to_drop.iter_mut().for_each(|x| drop(core::mem::take(x)));
136 }
137 self.len = o.len;
138 }
139}
140
141impl<A> Copy for ArrayVec<A>
142where
143 A: Array + Copy,
144 A::Item: Copy,
145{
146}
147
148impl<A: Array> Default for ArrayVec<A> {
149 #[inline]
150 fn default() -> Self {
151 Self { len: 0, data: A::default() }
152 }
153}
154
155impl<A: Array> Deref for ArrayVec<A> {
156 type Target = [A::Item];
157 #[inline(always)]
158 #[must_use]
159 fn deref(&self) -> &Self::Target {
160 &self.data.as_slice()[..self.len as usize]
161 }
162}
163
164impl<A: Array> DerefMut for ArrayVec<A> {
165 #[inline(always)]
166 #[must_use]
167 fn deref_mut(&mut self) -> &mut Self::Target {
168 &mut self.data.as_slice_mut()[..self.len as usize]
169 }
170}
171
172impl<A: Array, I: SliceIndex<[A::Item]>> Index<I> for ArrayVec<A> {
173 type Output = <I as SliceIndex<[A::Item]>>::Output;
174 #[inline(always)]
175 #[must_use]
176 fn index(&self, index: I) -> &Self::Output {
177 &self.deref()[index]
178 }
179}
180
181impl<A: Array, I: SliceIndex<[A::Item]>> IndexMut<I> for ArrayVec<A> {
182 #[inline(always)]
183 #[must_use]
184 fn index_mut(&mut self, index: I) -> &mut Self::Output {
185 &mut self.deref_mut()[index]
186 }
187}
188
189#[cfg(feature = "serde")]
190#[cfg_attr(docs_rs, doc(cfg(feature = "serde")))]
191impl<A: Array> Serialize for ArrayVec<A>
192where
193 A::Item: Serialize,
194{
195 #[must_use]
196 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
197 where
198 S: Serializer,
199 {
200 let mut seq = serializer.serialize_seq(Some(self.len()))?;
201 for element in self.iter() {
202 seq.serialize_element(element)?;
203 }
204 seq.end()
205 }
206}
207
208#[cfg(feature = "serde")]
209#[cfg_attr(docs_rs, doc(cfg(feature = "serde")))]
210impl<'de, A: Array> Deserialize<'de> for ArrayVec<A>
211where
212 A::Item: Deserialize<'de>,
213{
214 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
215 where
216 D: Deserializer<'de>,
217 {
218 deserializer.deserialize_seq(ArrayVecVisitor(PhantomData))
219 }
220}
221
222#[cfg(feature = "arbitrary")]
223#[cfg_attr(docs_rs, doc(cfg(feature = "arbitrary")))]
224impl<'a, A> arbitrary::Arbitrary<'a> for ArrayVec<A>
225where
226 A: Array,
227 A::Item: arbitrary::Arbitrary<'a>,
228{
229 fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
230 let max_len = A::CAPACITY.min(u16::MAX as usize) as u16;
231 let len = u.int_in_range::<u16>(0..=max_len)?;
232 let mut self_: Self = Default::default();
233 for _ in 0..len {
234 self_.push(u.arbitrary()?);
235 }
236 Ok(self_)
237 }
238
239 fn size_hint(depth: usize) -> (usize, Option<usize>) {
240 arbitrary::size_hint::recursion_guard(depth, |depth| {
241 let max_len = A::CAPACITY.min(u16::MAX as usize);
242 let inner = A::Item::size_hint(depth).1;
243 (0, inner.map(|inner| 2 + max_len * inner))
244 })
245 }
246}
247
248impl<A: Array> ArrayVec<A> {
249 /// Move all values from `other` into this vec.
250 ///
251 /// ## Panics
252 /// * If the vec overflows its capacity
253 ///
254 /// ## Example
255 /// ```rust
256 /// # use tinyvec::*;
257 /// let mut av = array_vec!([i32; 10] => 1, 2, 3);
258 /// let mut av2 = array_vec!([i32; 10] => 4, 5, 6);
259 /// av.append(&mut av2);
260 /// assert_eq!(av, &[1, 2, 3, 4, 5, 6][..]);
261 /// assert_eq!(av2, &[][..]);
262 /// ```
263 #[inline]
264 pub fn append(&mut self, other: &mut Self) {
265 assert!(
266 self.try_append(other).is_none(),
267 "ArrayVec::append> total length {} exceeds capacity {}!",
268 self.len() + other.len(),
269 A::CAPACITY
270 );
271 }
272
273 /// Move all values from `other` into this vec.
274 /// If appending would overflow the capacity, Some(other) is returned.
275 /// ## Example
276 /// ```rust
277 /// # use tinyvec::*;
278 /// let mut av = array_vec!([i32; 7] => 1, 2, 3);
279 /// let mut av2 = array_vec!([i32; 7] => 4, 5, 6);
280 /// av.append(&mut av2);
281 /// assert_eq!(av, &[1, 2, 3, 4, 5, 6][..]);
282 /// assert_eq!(av2, &[][..]);
283 ///
284 /// let mut av3 = array_vec!([i32; 7] => 7, 8, 9);
285 /// assert!(av.try_append(&mut av3).is_some());
286 /// assert_eq!(av, &[1, 2, 3, 4, 5, 6][..]);
287 /// assert_eq!(av3, &[7, 8, 9][..]);
288 /// ```
289 #[inline]
290 pub fn try_append<'other>(
291 &mut self, other: &'other mut Self,
292 ) -> Option<&'other mut Self> {
293 let new_len = self.len() + other.len();
294 if new_len > A::CAPACITY {
295 return Some(other);
296 }
297
298 let iter = other.iter_mut().map(core::mem::take);
299 for item in iter {
300 self.push(item);
301 }
302
303 other.set_len(0);
304
305 return None;
306 }
307
308 /// A `*mut` pointer to the backing array.
309 ///
310 /// ## Safety
311 ///
312 /// This pointer has provenance over the _entire_ backing array.
313 #[inline(always)]
314 #[must_use]
315 pub fn as_mut_ptr(&mut self) -> *mut A::Item {
316 self.data.as_slice_mut().as_mut_ptr()
317 }
318
319 /// Performs a `deref_mut`, into unique slice form.
320 #[inline(always)]
321 #[must_use]
322 pub fn as_mut_slice(&mut self) -> &mut [A::Item] {
323 self.deref_mut()
324 }
325
326 /// A `*const` pointer to the backing array.
327 ///
328 /// ## Safety
329 ///
330 /// This pointer has provenance over the _entire_ backing array.
331 #[inline(always)]
332 #[must_use]
333 pub fn as_ptr(&self) -> *const A::Item {
334 self.data.as_slice().as_ptr()
335 }
336
337 /// Performs a `deref`, into shared slice form.
338 #[inline(always)]
339 #[must_use]
340 pub fn as_slice(&self) -> &[A::Item] {
341 self.deref()
342 }
343
344 /// The capacity of the `ArrayVec`.
345 ///
346 /// This is fixed based on the array type, but can't yet be made a `const fn`
347 /// on Stable Rust.
348 #[inline(always)]
349 #[must_use]
350 pub fn capacity(&self) -> usize {
351 // Note: This shouldn't use A::CAPACITY, because unsafe code can't rely on
352 // any Array invariants. This ensures that at the very least, the returned
353 // value is a valid length for a subslice of the backing array.
354 self.data.as_slice().len().min(u16::MAX as usize)
355 }
356
357 /// Truncates the `ArrayVec` down to length 0.
358 #[inline(always)]
359 pub fn clear(&mut self) {
360 self.truncate(0)
361 }
362
363 /// Creates a draining iterator that removes the specified range in the vector
364 /// and yields the removed items.
365 ///
366 /// ## Panics
367 /// * If the start is greater than the end
368 /// * If the end is past the edge of the vec.
369 ///
370 /// ## Example
371 /// ```rust
372 /// # use tinyvec::*;
373 /// let mut av = array_vec!([i32; 4] => 1, 2, 3);
374 /// let av2: ArrayVec<[i32; 4]> = av.drain(1..).collect();
375 /// assert_eq!(av.as_slice(), &[1][..]);
376 /// assert_eq!(av2.as_slice(), &[2, 3][..]);
377 ///
378 /// av.drain(..);
379 /// assert_eq!(av.as_slice(), &[]);
380 /// ```
381 #[inline]
382 pub fn drain<R>(&mut self, range: R) -> ArrayVecDrain<'_, A::Item>
383 where
384 R: RangeBounds<usize>,
385 {
386 ArrayVecDrain::new(self, range)
387 }
388
389 /// Returns the inner array of the `ArrayVec`.
390 ///
391 /// This returns the full array, even if the `ArrayVec` length is currently
392 /// less than that.
393 ///
394 /// ## Example
395 ///
396 /// ```rust
397 /// # use tinyvec::{array_vec, ArrayVec};
398 /// let mut favorite_numbers = array_vec!([i32; 5] => 87, 48, 33, 9, 26);
399 /// assert_eq!(favorite_numbers.clone().into_inner(), [87, 48, 33, 9, 26]);
400 ///
401 /// favorite_numbers.pop();
402 /// assert_eq!(favorite_numbers.into_inner(), [87, 48, 33, 9, 0]);
403 /// ```
404 ///
405 /// A use for this function is to build an array from an iterator by first
406 /// collecting it into an `ArrayVec`.
407 ///
408 /// ```rust
409 /// # use tinyvec::ArrayVec;
410 /// let arr_vec: ArrayVec<[i32; 10]> = (1..=3).cycle().take(10).collect();
411 /// let inner = arr_vec.into_inner();
412 /// assert_eq!(inner, [1, 2, 3, 1, 2, 3, 1, 2, 3, 1]);
413 /// ```
414 #[inline]
415 pub fn into_inner(self) -> A {
416 self.data
417 }
418
419 /// Clone each element of the slice into this `ArrayVec`.
420 ///
421 /// ## Panics
422 /// * If the `ArrayVec` would overflow, this will panic.
423 #[inline]
424 pub fn extend_from_slice(&mut self, sli: &[A::Item])
425 where
426 A::Item: Clone,
427 {
428 if sli.is_empty() {
429 return;
430 }
431
432 let new_len = self.len as usize + sli.len();
433 assert!(
434 new_len <= A::CAPACITY,
435 "ArrayVec::extend_from_slice> total length {} exceeds capacity {}!",
436 new_len,
437 A::CAPACITY
438 );
439
440 let target = &mut self.data.as_slice_mut()[self.len as usize..new_len];
441 target.clone_from_slice(sli);
442 self.set_len(new_len);
443 }
444
445 /// Fill the vector until its capacity has been reached.
446 ///
447 /// Successively fills unused space in the spare slice of the vector with
448 /// elements from the iterator. It then returns the remaining iterator
449 /// without exhausting it. This also allows appending the head of an
450 /// infinite iterator.
451 ///
452 /// This is an alternative to `Extend::extend` method for cases where the
453 /// length of the iterator can not be checked. Since this vector can not
454 /// reallocate to increase its capacity, it is unclear what to do with
455 /// remaining elements in the iterator and the iterator itself. The
456 /// interface also provides no way to communicate this to the caller.
457 ///
458 /// ## Panics
459 /// * If the `next` method of the provided iterator panics.
460 ///
461 /// ## Example
462 ///
463 /// ```rust
464 /// # use tinyvec::*;
465 /// let mut av = array_vec!([i32; 4]);
466 /// let mut to_inf = av.fill(0..);
467 /// assert_eq!(&av[..], [0, 1, 2, 3]);
468 /// assert_eq!(to_inf.next(), Some(4));
469 /// ```
470 #[inline]
471 pub fn fill<I: IntoIterator<Item = A::Item>>(
472 &mut self, iter: I,
473 ) -> I::IntoIter {
474 // If this is written as a call to push for each element in iter, the
475 // compiler emits code that updates the length for every element. The
476 // additional complexity from that length update is worth nearly 2x in
477 // the runtime of this function.
478 let mut iter = iter.into_iter();
479 let mut pushed = 0;
480 let to_take = self.capacity() - self.len();
481 let target = &mut self.data.as_slice_mut()[self.len as usize..];
482 for element in iter.by_ref().take(to_take) {
483 target[pushed] = element;
484 pushed += 1;
485 }
486 self.len += pushed as u16;
487 iter
488 }
489
490 /// Wraps up an array and uses the given length as the initial length.
491 ///
492 /// If you want to simply use the full array, use `from` instead.
493 ///
494 /// ## Panics
495 ///
496 /// * The length specified must be less than or equal to the capacity of the
497 /// array.
498 #[inline]
499 #[must_use]
500 #[allow(clippy::match_wild_err_arm)]
501 pub fn from_array_len(data: A, len: usize) -> Self {
502 match Self::try_from_array_len(data, len) {
503 Ok(out) => out,
504 Err(_) => panic!(
505 "ArrayVec::from_array_len> length {} exceeds capacity {}!",
506 len,
507 A::CAPACITY
508 ),
509 }
510 }
511
512 /// Inserts an item at the position given, moving all following elements +1
513 /// index.
514 ///
515 /// ## Panics
516 /// * If `index` > `len`
517 /// * If the capacity is exhausted
518 ///
519 /// ## Example
520 /// ```rust
521 /// use tinyvec::*;
522 /// let mut av = array_vec!([i32; 10] => 1, 2, 3);
523 /// av.insert(1, 4);
524 /// assert_eq!(av.as_slice(), &[1, 4, 2, 3]);
525 /// av.insert(4, 5);
526 /// assert_eq!(av.as_slice(), &[1, 4, 2, 3, 5]);
527 /// ```
528 #[inline]
529 pub fn insert(&mut self, index: usize, item: A::Item) {
530 let x = self.try_insert(index, item);
531 assert!(x.is_none(), "ArrayVec::insert> capacity overflow!");
532 }
533
534 /// Tries to insert an item at the position given, moving all following
535 /// elements +1 index.
536 /// Returns back the element if the capacity is exhausted,
537 /// otherwise returns None.
538 ///
539 /// ## Panics
540 /// * If `index` > `len`
541 ///
542 /// ## Example
543 /// ```rust
544 /// use tinyvec::*;
545 /// let mut av = array_vec!([&'static str; 4] => "one", "two", "three");
546 /// av.insert(1, "four");
547 /// assert_eq!(av.as_slice(), &["one", "four", "two", "three"]);
548 /// assert_eq!(av.try_insert(4, "five"), Some("five"));
549 /// ```
550 #[inline]
551 pub fn try_insert(
552 &mut self, index: usize, mut item: A::Item,
553 ) -> Option<A::Item> {
554 assert!(
555 index <= self.len as usize,
556 "ArrayVec::try_insert> index {} is out of bounds {}",
557 index,
558 self.len
559 );
560
561 // A previous implementation used self.try_push and slice::rotate_right
562 // rotate_right and rotate_left generate a huge amount of code and fail to
563 // inline; calling them here incurs the cost of all the cases they
564 // handle even though we're rotating a usually-small array by a constant
565 // 1 offset. This swap-based implementation benchmarks much better for
566 // small array lengths in particular.
567
568 if (self.len as usize) < A::CAPACITY {
569 self.len += 1;
570 } else {
571 return Some(item);
572 }
573
574 let target = &mut self.as_mut_slice()[index..];
575 #[allow(clippy::needless_range_loop)]
576 for i in 0..target.len() {
577 core::mem::swap(&mut item, &mut target[i]);
578 }
579 return None;
580 }
581
582 /// Checks if the length is 0.
583 #[inline(always)]
584 #[must_use]
585 pub fn is_empty(&self) -> bool {
586 self.len == 0
587 }
588
589 /// The length of the `ArrayVec` (in elements).
590 #[inline(always)]
591 #[must_use]
592 pub fn len(&self) -> usize {
593 self.len as usize
594 }
595
596 /// Makes a new, empty `ArrayVec`.
597 #[inline(always)]
598 #[must_use]
599 pub fn new() -> Self {
600 Self::default()
601 }
602
603 /// Remove and return the last element of the vec, if there is one.
604 ///
605 /// ## Failure
606 /// * If the vec is empty you get `None`.
607 ///
608 /// ## Example
609 /// ```rust
610 /// # use tinyvec::*;
611 /// let mut av = array_vec!([i32; 10] => 1, 2);
612 /// assert_eq!(av.pop(), Some(2));
613 /// assert_eq!(av.pop(), Some(1));
614 /// assert_eq!(av.pop(), None);
615 /// ```
616 #[inline]
617 pub fn pop(&mut self) -> Option<A::Item> {
618 if self.len > 0 {
619 self.len -= 1;
620 let out =
621 core::mem::take(&mut self.data.as_slice_mut()[self.len as usize]);
622 Some(out)
623 } else {
624 None
625 }
626 }
627
628 /// Place an element onto the end of the vec.
629 ///
630 /// ## Panics
631 /// * If the length of the vec would overflow the capacity.
632 ///
633 /// ## Example
634 /// ```rust
635 /// # use tinyvec::*;
636 /// let mut av = array_vec!([i32; 2]);
637 /// assert_eq!(&av[..], []);
638 /// av.push(1);
639 /// assert_eq!(&av[..], [1]);
640 /// av.push(2);
641 /// assert_eq!(&av[..], [1, 2]);
642 /// // av.push(3); this would overflow the ArrayVec and panic!
643 /// ```
644 #[inline(always)]
645 pub fn push(&mut self, val: A::Item) {
646 let x = self.try_push(val);
647 assert!(x.is_none(), "ArrayVec::push> capacity overflow!");
648 }
649
650 /// Tries to place an element onto the end of the vec.\
651 /// Returns back the element if the capacity is exhausted,
652 /// otherwise returns None.
653 /// ```rust
654 /// # use tinyvec::*;
655 /// let mut av = array_vec!([i32; 2]);
656 /// assert_eq!(av.as_slice(), []);
657 /// assert_eq!(av.try_push(1), None);
658 /// assert_eq!(&av[..], [1]);
659 /// assert_eq!(av.try_push(2), None);
660 /// assert_eq!(&av[..], [1, 2]);
661 /// assert_eq!(av.try_push(3), Some(3));
662 /// ```
663 #[inline(always)]
664 pub fn try_push(&mut self, val: A::Item) -> Option<A::Item> {
665 debug_assert!(self.len as usize <= A::CAPACITY);
666
667 let itemref = match self.data.as_slice_mut().get_mut(self.len as usize) {
668 None => return Some(val),
669 Some(x) => x,
670 };
671
672 *itemref = val;
673 self.len += 1;
674 return None;
675 }
676
677 /// Removes the item at `index`, shifting all others down by one index.
678 ///
679 /// Returns the removed element.
680 ///
681 /// ## Panics
682 ///
683 /// * If the index is out of bounds.
684 ///
685 /// ## Example
686 ///
687 /// ```rust
688 /// # use tinyvec::*;
689 /// let mut av = array_vec!([i32; 4] => 1, 2, 3);
690 /// assert_eq!(av.remove(1), 2);
691 /// assert_eq!(&av[..], [1, 3]);
692 /// ```
693 #[inline]
694 pub fn remove(&mut self, index: usize) -> A::Item {
695 let targets: &mut [A::Item] = &mut self.deref_mut()[index..];
696 let item = core::mem::take(&mut targets[0]);
697
698 // A previous implementation used rotate_left
699 // rotate_right and rotate_left generate a huge amount of code and fail to
700 // inline; calling them here incurs the cost of all the cases they
701 // handle even though we're rotating a usually-small array by a constant
702 // 1 offset. This swap-based implementation benchmarks much better for
703 // small array lengths in particular.
704
705 for i in 0..targets.len() - 1 {
706 targets.swap(i, i + 1);
707 }
708 self.len -= 1;
709 item
710 }
711
712 /// As [`resize_with`](ArrayVec::resize_with)
713 /// and it clones the value as the closure.
714 ///
715 /// ## Example
716 ///
717 /// ```rust
718 /// # use tinyvec::*;
719 ///
720 /// let mut av = array_vec!([&str; 10] => "hello");
721 /// av.resize(3, "world");
722 /// assert_eq!(&av[..], ["hello", "world", "world"]);
723 ///
724 /// let mut av = array_vec!([i32; 10] => 1, 2, 3, 4);
725 /// av.resize(2, 0);
726 /// assert_eq!(&av[..], [1, 2]);
727 /// ```
728 #[inline]
729 pub fn resize(&mut self, new_len: usize, new_val: A::Item)
730 where
731 A::Item: Clone,
732 {
733 self.resize_with(new_len, || new_val.clone())
734 }
735
736 /// Resize the vec to the new length.
737 ///
738 /// If it needs to be longer, it's filled with repeated calls to the provided
739 /// function. If it needs to be shorter, it's truncated.
740 ///
741 /// ## Example
742 ///
743 /// ```rust
744 /// # use tinyvec::*;
745 ///
746 /// let mut av = array_vec!([i32; 10] => 1, 2, 3);
747 /// av.resize_with(5, Default::default);
748 /// assert_eq!(&av[..], [1, 2, 3, 0, 0]);
749 ///
750 /// let mut av = array_vec!([i32; 10]);
751 /// let mut p = 1;
752 /// av.resize_with(4, || {
753 /// p *= 2;
754 /// p
755 /// });
756 /// assert_eq!(&av[..], [2, 4, 8, 16]);
757 /// ```
758 #[inline]
759 pub fn resize_with<F: FnMut() -> A::Item>(
760 &mut self, new_len: usize, mut f: F,
761 ) {
762 match new_len.checked_sub(self.len as usize) {
763 None => self.truncate(new_len),
764 Some(new_elements) => {
765 for _ in 0..new_elements {
766 self.push(f());
767 }
768 }
769 }
770 }
771
772 /// Walk the vec and keep only the elements that pass the predicate given.
773 ///
774 /// ## Example
775 ///
776 /// ```rust
777 /// # use tinyvec::*;
778 ///
779 /// let mut av = array_vec!([i32; 10] => 1, 1, 2, 3, 3, 4);
780 /// av.retain(|&x| x % 2 == 0);
781 /// assert_eq!(&av[..], [2, 4]);
782 /// ```
783 #[inline]
784 pub fn retain<F: FnMut(&A::Item) -> bool>(&mut self, mut acceptable: F) {
785 // Drop guard to contain exactly the remaining elements when the test
786 // panics.
787 struct JoinOnDrop<'vec, Item> {
788 items: &'vec mut [Item],
789 done_end: usize,
790 // Start of tail relative to `done_end`.
791 tail_start: usize,
792 }
793
794 impl<Item> Drop for JoinOnDrop<'_, Item> {
795 fn drop(&mut self) {
796 self.items[self.done_end..].rotate_left(self.tail_start);
797 }
798 }
799
800 let mut rest = JoinOnDrop {
801 items: &mut self.data.as_slice_mut()[..self.len as usize],
802 done_end: 0,
803 tail_start: 0,
804 };
805
806 let len = self.len as usize;
807 for idx in 0..len {
808 // Loop start invariant: idx = rest.done_end + rest.tail_start
809 if !acceptable(&rest.items[idx]) {
810 let _ = core::mem::take(&mut rest.items[idx]);
811 self.len -= 1;
812 rest.tail_start += 1;
813 } else {
814 rest.items.swap(rest.done_end, idx);
815 rest.done_end += 1;
816 }
817 }
818 }
819
820 /// Retains only the elements specified by the predicate, passing a mutable
821 /// reference to it.
822 ///
823 /// In other words, remove all elements e such that f(&mut e) returns false.
824 /// This method operates in place, visiting each element exactly once in the
825 /// original order, and preserves the order of the retained elements.
826 ///
827 ///
828 /// ## Example
829 ///
830 /// ```rust
831 /// # use tinyvec::*;
832 ///
833 /// let mut av = array_vec!([i32; 10] => 1, 1, 2, 3, 3, 4);
834 /// av.retain_mut(|x| if *x % 2 == 0 { *x *= 2; true } else { false });
835 /// assert_eq!(&av[..], [4, 8]);
836 /// ```
837 #[inline]
838 pub fn retain_mut<F>(&mut self, mut acceptable: F)
839 where
840 F: FnMut(&mut A::Item) -> bool,
841 {
842 // Drop guard to contain exactly the remaining elements when the test
843 // panics.
844 struct JoinOnDrop<'vec, Item> {
845 items: &'vec mut [Item],
846 done_end: usize,
847 // Start of tail relative to `done_end`.
848 tail_start: usize,
849 }
850
851 impl<Item> Drop for JoinOnDrop<'_, Item> {
852 fn drop(&mut self) {
853 self.items[self.done_end..].rotate_left(self.tail_start);
854 }
855 }
856
857 let mut rest = JoinOnDrop {
858 items: &mut self.data.as_slice_mut()[..self.len as usize],
859 done_end: 0,
860 tail_start: 0,
861 };
862
863 let len = self.len as usize;
864 for idx in 0..len {
865 // Loop start invariant: idx = rest.done_end + rest.tail_start
866 if !acceptable(&mut rest.items[idx]) {
867 let _ = core::mem::take(&mut rest.items[idx]);
868 self.len -= 1;
869 rest.tail_start += 1;
870 } else {
871 rest.items.swap(rest.done_end, idx);
872 rest.done_end += 1;
873 }
874 }
875 }
876
877 /// Forces the length of the vector to `new_len`.
878 ///
879 /// ## Panics
880 /// * If `new_len` is greater than the vec's capacity.
881 ///
882 /// ## Safety
883 /// * This is a fully safe operation! The inactive memory already counts as
884 /// "initialized" by Rust's rules.
885 /// * Other than "the memory is initialized" there are no other guarantees
886 /// regarding what you find in the inactive portion of the vec.
887 #[inline(always)]
888 pub fn set_len(&mut self, new_len: usize) {
889 if new_len > A::CAPACITY {
890 // Note(Lokathor): Technically we don't have to panic here, and we could
891 // just let some other call later on trigger a panic on accident when the
892 // length is wrong. However, it's a lot easier to catch bugs when things
893 // are more "fail-fast".
894 panic!(
895 "ArrayVec::set_len> new length {} exceeds capacity {}",
896 new_len,
897 A::CAPACITY
898 )
899 }
900
901 let new_len: u16 = new_len
902 .try_into()
903 .expect("ArrayVec::set_len> new length is not in range 0..=u16::MAX");
904 self.len = new_len;
905 }
906
907 /// Splits the collection at the point given.
908 ///
909 /// * `[0, at)` stays in this vec
910 /// * `[at, len)` ends up in the new vec.
911 ///
912 /// ## Panics
913 /// * if at > len
914 ///
915 /// ## Example
916 ///
917 /// ```rust
918 /// # use tinyvec::*;
919 /// let mut av = array_vec!([i32; 4] => 1, 2, 3);
920 /// let av2 = av.split_off(1);
921 /// assert_eq!(&av[..], [1]);
922 /// assert_eq!(&av2[..], [2, 3]);
923 /// ```
924 #[inline]
925 pub fn split_off(&mut self, at: usize) -> Self {
926 // FIXME: should this just use drain into the output?
927 if at > self.len() {
928 panic!(
929 "ArrayVec::split_off> at value {} exceeds length of {}",
930 at, self.len
931 );
932 }
933 let mut new = Self::default();
934 let moves = &mut self.as_mut_slice()[at..];
935 let split_len = moves.len();
936 let targets = &mut new.data.as_slice_mut()[..split_len];
937 moves.swap_with_slice(targets);
938
939 /* moves.len() <= u16::MAX, so these are surely in u16 range */
940 new.len = split_len as u16;
941 self.len = at as u16;
942 new
943 }
944
945 /// Creates a splicing iterator that removes the specified range in the
946 /// vector, yields the removed items, and replaces them with elements from
947 /// the provided iterator.
948 ///
949 /// `splice` fuses the provided iterator, so elements after the first `None`
950 /// are ignored.
951 ///
952 /// ## Panics
953 /// * If the start is greater than the end.
954 /// * If the end is past the edge of the vec.
955 /// * If the provided iterator panics.
956 /// * If the new length would overflow the capacity of the array. Because
957 /// `ArrayVecSplice` adds elements to this vec in its destructor when
958 /// necessary, this panic would occur when it is dropped.
959 ///
960 /// ## Example
961 /// ```rust
962 /// use tinyvec::*;
963 /// let mut av = array_vec!([i32; 4] => 1, 2, 3);
964 /// let av2: ArrayVec<[i32; 4]> = av.splice(1.., 4..=6).collect();
965 /// assert_eq!(av.as_slice(), &[1, 4, 5, 6][..]);
966 /// assert_eq!(av2.as_slice(), &[2, 3][..]);
967 ///
968 /// av.splice(.., None);
969 /// assert_eq!(av.as_slice(), &[]);
970 /// ```
971 #[inline]
972 pub fn splice<R, I>(
973 &mut self, range: R, replacement: I,
974 ) -> ArrayVecSplice<'_, A, core::iter::Fuse<I::IntoIter>>
975 where
976 R: RangeBounds<usize>,
977 I: IntoIterator<Item = A::Item>,
978 {
979 use core::ops::Bound;
980 let start = match range.start_bound() {
981 Bound::Included(x) => *x,
982 Bound::Excluded(x) => x.saturating_add(1),
983 Bound::Unbounded => 0,
984 };
985 let end = match range.end_bound() {
986 Bound::Included(x) => x.saturating_add(1),
987 Bound::Excluded(x) => *x,
988 Bound::Unbounded => self.len(),
989 };
990 assert!(
991 start <= end,
992 "ArrayVec::splice> Illegal range, {} to {}",
993 start,
994 end
995 );
996 assert!(
997 end <= self.len(),
998 "ArrayVec::splice> Range ends at {} but length is only {}!",
999 end,
1000 self.len()
1001 );
1002
1003 ArrayVecSplice {
1004 removal_start: start,
1005 removal_end: end,
1006 parent: self,
1007 replacement: replacement.into_iter().fuse(),
1008 }
1009 }
1010
1011 /// Remove an element, swapping the end of the vec into its place.
1012 ///
1013 /// ## Panics
1014 /// * If the index is out of bounds.
1015 ///
1016 /// ## Example
1017 /// ```rust
1018 /// # use tinyvec::*;
1019 /// let mut av = array_vec!([&str; 4] => "foo", "bar", "quack", "zap");
1020 ///
1021 /// assert_eq!(av.swap_remove(1), "bar");
1022 /// assert_eq!(&av[..], ["foo", "zap", "quack"]);
1023 ///
1024 /// assert_eq!(av.swap_remove(0), "foo");
1025 /// assert_eq!(&av[..], ["quack", "zap"]);
1026 /// ```
1027 #[inline]
1028 pub fn swap_remove(&mut self, index: usize) -> A::Item {
1029 assert!(
1030 index < self.len(),
1031 "ArrayVec::swap_remove> index {} is out of bounds {}",
1032 index,
1033 self.len
1034 );
1035 if index == self.len() - 1 {
1036 self.pop().unwrap()
1037 } else {
1038 let i = self.pop().unwrap();
1039 replace(&mut self[index], i)
1040 }
1041 }
1042
1043 /// Reduces the vec's length to the given value.
1044 ///
1045 /// If the vec is already shorter than the input, nothing happens.
1046 #[inline]
1047 pub fn truncate(&mut self, new_len: usize) {
1048 if new_len >= self.len as usize {
1049 return;
1050 }
1051
1052 if needs_drop::<A::Item>() {
1053 let len = self.len as usize;
1054 self.data.as_slice_mut()[new_len..len]
1055 .iter_mut()
1056 .map(core::mem::take)
1057 .for_each(drop);
1058 }
1059
1060 /* new_len is less than self.len */
1061 self.len = new_len as u16;
1062 }
1063
1064 /// Wraps an array, using the given length as the starting length.
1065 ///
1066 /// If you want to use the whole length of the array, you can just use the
1067 /// `From` impl.
1068 ///
1069 /// ## Failure
1070 ///
1071 /// If the given length is greater than the capacity of the array this will
1072 /// error, and you'll get the array back in the `Err`.
1073 #[inline]
1074 pub fn try_from_array_len(data: A, len: usize) -> Result<Self, A> {
1075 /* Note(Soveu): Should we allow A::CAPACITY > u16::MAX for now? */
1076 if len <= A::CAPACITY {
1077 Ok(Self { data, len: len as u16 })
1078 } else {
1079 Err(data)
1080 }
1081 }
1082}
1083
1084impl<A> ArrayVec<A> {
1085 /// Wraps up an array as a new empty `ArrayVec`.
1086 ///
1087 /// If you want to simply use the full array, use `from` instead.
1088 ///
1089 /// ## Examples
1090 ///
1091 /// This method in particular allows to create values for statics:
1092 ///
1093 /// ```rust
1094 /// # use tinyvec::ArrayVec;
1095 /// static DATA: ArrayVec<[u8; 5]> = ArrayVec::from_array_empty([0; 5]);
1096 /// assert_eq!(DATA.len(), 0);
1097 /// ```
1098 ///
1099 /// But of course it is just an normal empty `ArrayVec`:
1100 ///
1101 /// ```rust
1102 /// # use tinyvec::ArrayVec;
1103 /// let mut data = ArrayVec::from_array_empty([1, 2, 3, 4]);
1104 /// assert_eq!(&data[..], &[]);
1105 /// data.push(42);
1106 /// assert_eq!(&data[..], &[42]);
1107 /// ```
1108 #[inline]
1109 #[must_use]
1110 pub const fn from_array_empty(data: A) -> Self {
1111 Self { data, len: 0 }
1112 }
1113}
1114
1115#[cfg(feature = "grab_spare_slice")]
1116impl<A: Array> ArrayVec<A> {
1117 /// Obtain the shared slice of the array _after_ the active memory.
1118 ///
1119 /// ## Example
1120 /// ```rust
1121 /// # use tinyvec::*;
1122 /// let mut av = array_vec!([i32; 4]);
1123 /// assert_eq!(av.grab_spare_slice().len(), 4);
1124 /// av.push(10);
1125 /// av.push(11);
1126 /// av.push(12);
1127 /// av.push(13);
1128 /// assert_eq!(av.grab_spare_slice().len(), 0);
1129 /// ```
1130 #[inline(always)]
1131 pub fn grab_spare_slice(&self) -> &[A::Item] {
1132 &self.data.as_slice()[self.len as usize..]
1133 }
1134
1135 /// Obtain the mutable slice of the array _after_ the active memory.
1136 ///
1137 /// ## Example
1138 /// ```rust
1139 /// # use tinyvec::*;
1140 /// let mut av = array_vec!([i32; 4]);
1141 /// assert_eq!(av.grab_spare_slice_mut().len(), 4);
1142 /// av.push(10);
1143 /// av.push(11);
1144 /// assert_eq!(av.grab_spare_slice_mut().len(), 2);
1145 /// ```
1146 #[inline(always)]
1147 pub fn grab_spare_slice_mut(&mut self) -> &mut [A::Item] {
1148 &mut self.data.as_slice_mut()[self.len as usize..]
1149 }
1150}
1151
1152#[cfg(feature = "nightly_slice_partition_dedup")]
1153impl<A: Array> ArrayVec<A> {
1154 /// De-duplicates the vec contents.
1155 #[inline(always)]
1156 pub fn dedup(&mut self)
1157 where
1158 A::Item: PartialEq,
1159 {
1160 self.dedup_by(|a, b| a == b)
1161 }
1162
1163 /// De-duplicates the vec according to the predicate given.
1164 #[inline(always)]
1165 pub fn dedup_by<F>(&mut self, same_bucket: F)
1166 where
1167 F: FnMut(&mut A::Item, &mut A::Item) -> bool,
1168 {
1169 let len = {
1170 let (dedup, _) = self.as_mut_slice().partition_dedup_by(same_bucket);
1171 dedup.len()
1172 };
1173 self.truncate(len);
1174 }
1175
1176 /// De-duplicates the vec according to the key selector given.
1177 #[inline(always)]
1178 pub fn dedup_by_key<F, K>(&mut self, mut key: F)
1179 where
1180 F: FnMut(&mut A::Item) -> K,
1181 K: PartialEq,
1182 {
1183 self.dedup_by(|a, b| key(a) == key(b))
1184 }
1185}
1186
1187impl<A> ArrayVec<A> {
1188 /// Returns the reference to the inner array of the `ArrayVec`.
1189 ///
1190 /// This returns the full array, even if the `ArrayVec` length is currently
1191 /// less than that.
1192 #[inline(always)]
1193 #[must_use]
1194 pub const fn as_inner(&self) -> &A {
1195 &self.data
1196 }
1197}
1198
1199/// Splicing iterator for `ArrayVec`
1200/// See [`ArrayVec::splice`](ArrayVec::<A>::splice)
1201pub struct ArrayVecSplice<'p, A: Array, I: Iterator<Item = A::Item>> {
1202 parent: &'p mut ArrayVec<A>,
1203 removal_start: usize,
1204 removal_end: usize,
1205 replacement: I,
1206}
1207
1208impl<'p, A: Array, I: Iterator<Item = A::Item>> Iterator
1209 for ArrayVecSplice<'p, A, I>
1210{
1211 type Item = A::Item;
1212
1213 #[inline]
1214 fn next(&mut self) -> Option<A::Item> {
1215 if self.removal_start < self.removal_end {
1216 match self.replacement.next() {
1217 Some(replacement) => {
1218 let removed = core::mem::replace(
1219 &mut self.parent[self.removal_start],
1220 replacement,
1221 );
1222 self.removal_start += 1;
1223 Some(removed)
1224 }
1225 None => {
1226 let removed = self.parent.remove(self.removal_start);
1227 self.removal_end -= 1;
1228 Some(removed)
1229 }
1230 }
1231 } else {
1232 None
1233 }
1234 }
1235
1236 #[inline]
1237 fn size_hint(&self) -> (usize, Option<usize>) {
1238 let len = self.len();
1239 (len, Some(len))
1240 }
1241}
1242
1243impl<'p, A, I> ExactSizeIterator for ArrayVecSplice<'p, A, I>
1244where
1245 A: Array,
1246 I: Iterator<Item = A::Item>,
1247{
1248 #[inline]
1249 fn len(&self) -> usize {
1250 self.removal_end - self.removal_start
1251 }
1252}
1253
1254impl<'p, A, I> FusedIterator for ArrayVecSplice<'p, A, I>
1255where
1256 A: Array,
1257 I: Iterator<Item = A::Item>,
1258{
1259}
1260
1261impl<'p, A, I> DoubleEndedIterator for ArrayVecSplice<'p, A, I>
1262where
1263 A: Array,
1264 I: Iterator<Item = A::Item> + DoubleEndedIterator,
1265{
1266 #[inline]
1267 fn next_back(&mut self) -> Option<A::Item> {
1268 if self.removal_start < self.removal_end {
1269 match self.replacement.next_back() {
1270 Some(replacement: ::Item) => {
1271 let removed: ::Item = core::mem::replace(
1272 &mut self.parent[self.removal_end - 1],
1273 src:replacement,
1274 );
1275 self.removal_end -= 1;
1276 Some(removed)
1277 }
1278 None => {
1279 let removed: ::Item = self.parent.remove(self.removal_end - 1);
1280 self.removal_end -= 1;
1281 Some(removed)
1282 }
1283 }
1284 } else {
1285 None
1286 }
1287 }
1288}
1289
1290impl<'p, A: Array, I: Iterator<Item = A::Item>> Drop
1291 for ArrayVecSplice<'p, A, I>
1292{
1293 #[inline]
1294 fn drop(&mut self) {
1295 for _ in self.by_ref() {}
1296
1297 // FIXME: reserve lower bound of size_hint
1298
1299 for replacement: ::Item in self.replacement.by_ref() {
1300 self.parent.insert(self.removal_end, item:replacement);
1301 self.removal_end += 1;
1302 }
1303 }
1304}
1305
1306impl<A: Array> AsMut<[A::Item]> for ArrayVec<A> {
1307 #[inline(always)]
1308 #[must_use]
1309 fn as_mut(&mut self) -> &mut [A::Item] {
1310 &mut *self
1311 }
1312}
1313
1314impl<A: Array> AsRef<[A::Item]> for ArrayVec<A> {
1315 #[inline(always)]
1316 #[must_use]
1317 fn as_ref(&self) -> &[A::Item] {
1318 &*self
1319 }
1320}
1321
1322impl<A: Array> Borrow<[A::Item]> for ArrayVec<A> {
1323 #[inline(always)]
1324 #[must_use]
1325 fn borrow(&self) -> &[A::Item] {
1326 &*self
1327 }
1328}
1329
1330impl<A: Array> BorrowMut<[A::Item]> for ArrayVec<A> {
1331 #[inline(always)]
1332 #[must_use]
1333 fn borrow_mut(&mut self) -> &mut [A::Item] {
1334 &mut *self
1335 }
1336}
1337
1338impl<A: Array> Extend<A::Item> for ArrayVec<A> {
1339 #[inline]
1340 fn extend<T: IntoIterator<Item = A::Item>>(&mut self, iter: T) {
1341 for t: ::Item in iter {
1342 self.push(val:t)
1343 }
1344 }
1345}
1346
1347impl<A: Array> From<A> for ArrayVec<A> {
1348 #[inline(always)]
1349 #[must_use]
1350 /// The output has a length equal to the full array.
1351 ///
1352 /// If you want to select a length, use
1353 /// [`from_array_len`](ArrayVec::from_array_len)
1354 fn from(data: A) -> Self {
1355 let len: u16 = data
1356 .as_slice()
1357 .len()
1358 .try_into()
1359 .expect(msg:"ArrayVec::from> length must be in range 0..=u16::MAX");
1360 Self { len, data }
1361 }
1362}
1363
1364/// The error type returned when a conversion from a slice to an [`ArrayVec`]
1365/// fails.
1366#[derive(Debug, Copy, Clone)]
1367pub struct TryFromSliceError(());
1368
1369impl core::fmt::Display for TryFromSliceError {
1370 #[inline]
1371 fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
1372 f.write_str(data:"could not convert slice to ArrayVec")
1373 }
1374}
1375
1376#[cfg(feature = "std")]
1377impl std::error::Error for TryFromSliceError {}
1378
1379impl<T, A> TryFrom<&'_ [T]> for ArrayVec<A>
1380where
1381 T: Clone + Default,
1382 A: Array<Item = T>,
1383{
1384 type Error = TryFromSliceError;
1385
1386 #[inline]
1387 /// The output has a length equal to that of the slice, with the same capacity
1388 /// as `A`.
1389 fn try_from(slice: &[T]) -> Result<Self, Self::Error> {
1390 if slice.len() > A::CAPACITY {
1391 Err(TryFromSliceError(()))
1392 } else {
1393 let mut arr: ArrayVec = ArrayVec::new();
1394 // We do not use ArrayVec::extend_from_slice, because it looks like LLVM
1395 // fails to deduplicate all the length-checking logic between the
1396 // above if and the contents of that method, thus producing much
1397 // slower code. Unlike many of the other optimizations in this
1398 // crate, this one is worth keeping an eye on. I see no reason, for
1399 // any element type, that these should produce different code. But
1400 // they do. (rustc 1.51.0)
1401 arr.set_len(new_len:slice.len());
1402 arr.as_mut_slice().clone_from_slice(src:slice);
1403 Ok(arr)
1404 }
1405 }
1406}
1407
1408impl<A: Array> FromIterator<A::Item> for ArrayVec<A> {
1409 #[inline]
1410 #[must_use]
1411 fn from_iter<T: IntoIterator<Item = A::Item>>(iter: T) -> Self {
1412 let mut av: ArrayVec = Self::default();
1413 for i: ::Item in iter {
1414 av.push(val:i)
1415 }
1416 av
1417 }
1418}
1419
1420/// Iterator for consuming an `ArrayVec` and returning owned elements.
1421pub struct ArrayVecIterator<A: Array> {
1422 base: u16,
1423 tail: u16,
1424 data: A,
1425}
1426
1427impl<A: Array> ArrayVecIterator<A> {
1428 /// Returns the remaining items of this iterator as a slice.
1429 #[inline]
1430 #[must_use]
1431 pub fn as_slice(&self) -> &[A::Item] {
1432 &self.data.as_slice()[self.base as usize..self.tail as usize]
1433 }
1434}
1435impl<A: Array> FusedIterator for ArrayVecIterator<A> {}
1436impl<A: Array> Iterator for ArrayVecIterator<A> {
1437 type Item = A::Item;
1438 #[inline]
1439 fn next(&mut self) -> Option<Self::Item> {
1440 let slice =
1441 &mut self.data.as_slice_mut()[self.base as usize..self.tail as usize];
1442 let itemref = slice.first_mut()?;
1443 self.base += 1;
1444 return Some(core::mem::take(itemref));
1445 }
1446 #[inline(always)]
1447 #[must_use]
1448 fn size_hint(&self) -> (usize, Option<usize>) {
1449 let s = self.tail - self.base;
1450 let s = s as usize;
1451 (s, Some(s))
1452 }
1453 #[inline(always)]
1454 fn count(self) -> usize {
1455 self.size_hint().0
1456 }
1457 #[inline]
1458 fn last(mut self) -> Option<Self::Item> {
1459 self.next_back()
1460 }
1461 #[inline]
1462 fn nth(&mut self, n: usize) -> Option<A::Item> {
1463 let slice = &mut self.data.as_slice_mut();
1464 let slice = &mut slice[self.base as usize..self.tail as usize];
1465
1466 if let Some(x) = slice.get_mut(n) {
1467 /* n is in range [0 .. self.tail - self.base) so in u16 range */
1468 self.base += n as u16 + 1;
1469 return Some(core::mem::take(x));
1470 }
1471
1472 self.base = self.tail;
1473 return None;
1474 }
1475}
1476
1477impl<A: Array> DoubleEndedIterator for ArrayVecIterator<A> {
1478 #[inline]
1479 fn next_back(&mut self) -> Option<Self::Item> {
1480 let slice =
1481 &mut self.data.as_slice_mut()[self.base as usize..self.tail as usize];
1482 let item = slice.last_mut()?;
1483 self.tail -= 1;
1484 return Some(core::mem::take(item));
1485 }
1486
1487 #[inline]
1488 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
1489 let base = self.base as usize;
1490 let tail = self.tail as usize;
1491 let slice = &mut self.data.as_slice_mut()[base..tail];
1492 let n = n.saturating_add(1);
1493
1494 if let Some(n) = slice.len().checked_sub(n) {
1495 let item = &mut slice[n];
1496 /* n is in [0..self.tail - self.base] range, so in u16 range */
1497 self.tail = self.base + n as u16;
1498 return Some(core::mem::take(item));
1499 }
1500
1501 self.tail = self.base;
1502 return None;
1503 }
1504}
1505
1506impl<A: Array> ExactSizeIterator for ArrayVecIterator<A> {
1507 #[inline]
1508 fn len(&self) -> usize {
1509 self.size_hint().0
1510 }
1511}
1512
1513impl<A: Array> Debug for ArrayVecIterator<A>
1514where
1515 A::Item: Debug,
1516{
1517 #[allow(clippy::missing_inline_in_public_items)]
1518 fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
1519 f.debug_tuple(name:"ArrayVecIterator").field(&self.as_slice()).finish()
1520 }
1521}
1522
1523impl<A: Array> IntoIterator for ArrayVec<A> {
1524 type Item = A::Item;
1525 type IntoIter = ArrayVecIterator<A>;
1526 #[inline(always)]
1527 #[must_use]
1528 fn into_iter(self) -> Self::IntoIter {
1529 ArrayVecIterator { base: 0, tail: self.len, data: self.data }
1530 }
1531}
1532
1533impl<'a, A: Array> IntoIterator for &'a mut ArrayVec<A> {
1534 type Item = &'a mut A::Item;
1535 type IntoIter = core::slice::IterMut<'a, A::Item>;
1536 #[inline(always)]
1537 #[must_use]
1538 fn into_iter(self) -> Self::IntoIter {
1539 self.iter_mut()
1540 }
1541}
1542
1543impl<'a, A: Array> IntoIterator for &'a ArrayVec<A> {
1544 type Item = &'a A::Item;
1545 type IntoIter = core::slice::Iter<'a, A::Item>;
1546 #[inline(always)]
1547 #[must_use]
1548 fn into_iter(self) -> Self::IntoIter {
1549 self.iter()
1550 }
1551}
1552
1553impl<A: Array> PartialEq for ArrayVec<A>
1554where
1555 A::Item: PartialEq,
1556{
1557 #[inline]
1558 #[must_use]
1559 fn eq(&self, other: &Self) -> bool {
1560 self.as_slice().eq(other.as_slice())
1561 }
1562}
1563impl<A: Array> Eq for ArrayVec<A> where A::Item: Eq {}
1564
1565impl<A: Array> PartialOrd for ArrayVec<A>
1566where
1567 A::Item: PartialOrd,
1568{
1569 #[inline]
1570 #[must_use]
1571 fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
1572 self.as_slice().partial_cmp(other.as_slice())
1573 }
1574}
1575impl<A: Array> Ord for ArrayVec<A>
1576where
1577 A::Item: Ord,
1578{
1579 #[inline]
1580 #[must_use]
1581 fn cmp(&self, other: &Self) -> core::cmp::Ordering {
1582 self.as_slice().cmp(other.as_slice())
1583 }
1584}
1585
1586impl<A: Array> PartialEq<&A> for ArrayVec<A>
1587where
1588 A::Item: PartialEq,
1589{
1590 #[inline]
1591 #[must_use]
1592 fn eq(&self, other: &&A) -> bool {
1593 self.as_slice().eq(other.as_slice())
1594 }
1595}
1596
1597impl<A: Array> PartialEq<&[A::Item]> for ArrayVec<A>
1598where
1599 A::Item: PartialEq,
1600{
1601 #[inline]
1602 #[must_use]
1603 fn eq(&self, other: &&[A::Item]) -> bool {
1604 self.as_slice().eq(*other)
1605 }
1606}
1607
1608impl<A: Array> Hash for ArrayVec<A>
1609where
1610 A::Item: Hash,
1611{
1612 #[inline]
1613 fn hash<H: Hasher>(&self, state: &mut H) {
1614 self.as_slice().hash(state)
1615 }
1616}
1617
1618#[cfg(feature = "experimental_write_impl")]
1619impl<A: Array<Item = u8>> core::fmt::Write for ArrayVec<A> {
1620 fn write_str(&mut self, s: &str) -> core::fmt::Result {
1621 let my_len = self.len();
1622 let str_len = s.as_bytes().len();
1623 if my_len + str_len <= A::CAPACITY {
1624 let remainder = &mut self.data.as_slice_mut()[my_len..];
1625 let target = &mut remainder[..str_len];
1626 target.copy_from_slice(s.as_bytes());
1627 Ok(())
1628 } else {
1629 Err(core::fmt::Error)
1630 }
1631 }
1632}
1633
1634// // // // // // // //
1635// Formatting impls
1636// // // // // // // //
1637
1638impl<A: Array> Binary for ArrayVec<A>
1639where
1640 A::Item: Binary,
1641{
1642 #[allow(clippy::missing_inline_in_public_items)]
1643 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1644 write!(f, "[")?;
1645 if f.alternate() {
1646 write!(f, "\n ")?;
1647 }
1648 for (i: usize, elem: &impl Binary) in self.iter().enumerate() {
1649 if i > 0 {
1650 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1651 }
1652 Binary::fmt(self:elem, f)?;
1653 }
1654 if f.alternate() {
1655 write!(f, ",\n")?;
1656 }
1657 write!(f, "]")
1658 }
1659}
1660
1661impl<A: Array> Debug for ArrayVec<A>
1662where
1663 A::Item: Debug,
1664{
1665 #[allow(clippy::missing_inline_in_public_items)]
1666 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1667 write!(f, "[")?;
1668 if f.alternate() && !self.is_empty() {
1669 write!(f, "\n ")?;
1670 }
1671 for (i: usize, elem: &impl Debug) in self.iter().enumerate() {
1672 if i > 0 {
1673 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1674 }
1675 Debug::fmt(self:elem, f)?;
1676 }
1677 if f.alternate() && !self.is_empty() {
1678 write!(f, ",\n")?;
1679 }
1680 write!(f, "]")
1681 }
1682}
1683
1684impl<A: Array> Display for ArrayVec<A>
1685where
1686 A::Item: Display,
1687{
1688 #[allow(clippy::missing_inline_in_public_items)]
1689 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1690 write!(f, "[")?;
1691 if f.alternate() {
1692 write!(f, "\n ")?;
1693 }
1694 for (i: usize, elem: &impl Display) in self.iter().enumerate() {
1695 if i > 0 {
1696 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1697 }
1698 Display::fmt(self:elem, f)?;
1699 }
1700 if f.alternate() {
1701 write!(f, ",\n")?;
1702 }
1703 write!(f, "]")
1704 }
1705}
1706
1707impl<A: Array> LowerExp for ArrayVec<A>
1708where
1709 A::Item: LowerExp,
1710{
1711 #[allow(clippy::missing_inline_in_public_items)]
1712 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1713 write!(f, "[")?;
1714 if f.alternate() {
1715 write!(f, "\n ")?;
1716 }
1717 for (i: usize, elem: &impl LowerExp) in self.iter().enumerate() {
1718 if i > 0 {
1719 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1720 }
1721 LowerExp::fmt(self:elem, f)?;
1722 }
1723 if f.alternate() {
1724 write!(f, ",\n")?;
1725 }
1726 write!(f, "]")
1727 }
1728}
1729
1730impl<A: Array> LowerHex for ArrayVec<A>
1731where
1732 A::Item: LowerHex,
1733{
1734 #[allow(clippy::missing_inline_in_public_items)]
1735 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1736 write!(f, "[")?;
1737 if f.alternate() {
1738 write!(f, "\n ")?;
1739 }
1740 for (i: usize, elem: &impl LowerHex) in self.iter().enumerate() {
1741 if i > 0 {
1742 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1743 }
1744 LowerHex::fmt(self:elem, f)?;
1745 }
1746 if f.alternate() {
1747 write!(f, ",\n")?;
1748 }
1749 write!(f, "]")
1750 }
1751}
1752
1753impl<A: Array> Octal for ArrayVec<A>
1754where
1755 A::Item: Octal,
1756{
1757 #[allow(clippy::missing_inline_in_public_items)]
1758 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1759 write!(f, "[")?;
1760 if f.alternate() {
1761 write!(f, "\n ")?;
1762 }
1763 for (i: usize, elem: &impl Octal) in self.iter().enumerate() {
1764 if i > 0 {
1765 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1766 }
1767 Octal::fmt(self:elem, f)?;
1768 }
1769 if f.alternate() {
1770 write!(f, ",\n")?;
1771 }
1772 write!(f, "]")
1773 }
1774}
1775
1776impl<A: Array> Pointer for ArrayVec<A>
1777where
1778 A::Item: Pointer,
1779{
1780 #[allow(clippy::missing_inline_in_public_items)]
1781 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1782 write!(f, "[")?;
1783 if f.alternate() {
1784 write!(f, "\n ")?;
1785 }
1786 for (i: usize, elem: &impl Pointer) in self.iter().enumerate() {
1787 if i > 0 {
1788 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1789 }
1790 Pointer::fmt(self:elem, f)?;
1791 }
1792 if f.alternate() {
1793 write!(f, ",\n")?;
1794 }
1795 write!(f, "]")
1796 }
1797}
1798
1799impl<A: Array> UpperExp for ArrayVec<A>
1800where
1801 A::Item: UpperExp,
1802{
1803 #[allow(clippy::missing_inline_in_public_items)]
1804 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1805 write!(f, "[")?;
1806 if f.alternate() {
1807 write!(f, "\n ")?;
1808 }
1809 for (i: usize, elem: &impl UpperExp) in self.iter().enumerate() {
1810 if i > 0 {
1811 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1812 }
1813 UpperExp::fmt(self:elem, f)?;
1814 }
1815 if f.alternate() {
1816 write!(f, ",\n")?;
1817 }
1818 write!(f, "]")
1819 }
1820}
1821
1822impl<A: Array> UpperHex for ArrayVec<A>
1823where
1824 A::Item: UpperHex,
1825{
1826 #[allow(clippy::missing_inline_in_public_items)]
1827 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1828 write!(f, "[")?;
1829 if f.alternate() {
1830 write!(f, "\n ")?;
1831 }
1832 for (i: usize, elem: &impl UpperHex) in self.iter().enumerate() {
1833 if i > 0 {
1834 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1835 }
1836 UpperHex::fmt(self:elem, f)?;
1837 }
1838 if f.alternate() {
1839 write!(f, ",\n")?;
1840 }
1841 write!(f, "]")
1842 }
1843}
1844
1845#[cfg(feature = "alloc")]
1846use alloc::vec::Vec;
1847
1848#[cfg(all(feature = "alloc", feature = "rustc_1_57"))]
1849use alloc::collections::TryReserveError;
1850
1851#[cfg(feature = "alloc")]
1852impl<A: Array> ArrayVec<A> {
1853 /// Drains all elements to a Vec, but reserves additional space
1854 /// ```
1855 /// # use tinyvec::*;
1856 /// let mut av = array_vec!([i32; 7] => 1, 2, 3);
1857 /// let v = av.drain_to_vec_and_reserve(10);
1858 /// assert_eq!(v, &[1, 2, 3]);
1859 /// assert_eq!(v.capacity(), 13);
1860 /// ```
1861 #[inline]
1862 pub fn drain_to_vec_and_reserve(&mut self, n: usize) -> Vec<A::Item> {
1863 let cap = n + self.len();
1864 let mut v = Vec::with_capacity(cap);
1865 let iter = self.iter_mut().map(core::mem::take);
1866 v.extend(iter);
1867 self.set_len(0);
1868 return v;
1869 }
1870
1871 /// Tries to drain all elements to a Vec, but reserves additional space.
1872 ///
1873 /// # Errors
1874 ///
1875 /// If the allocator reports a failure, then an error is returned.
1876 ///
1877 /// ```
1878 /// # use tinyvec::*;
1879 /// let mut av = array_vec!([i32; 7] => 1, 2, 3);
1880 /// let v = av.try_drain_to_vec_and_reserve(10);
1881 /// assert!(matches!(v, Ok(_)));
1882 /// let v = v.unwrap();
1883 /// assert_eq!(v, &[1, 2, 3]);
1884 /// assert_eq!(v.capacity(), 13);
1885 /// ```
1886 #[cfg(feature = "rustc_1_57")]
1887 pub fn try_drain_to_vec_and_reserve(
1888 &mut self, n: usize,
1889 ) -> Result<Vec<A::Item>, TryReserveError> {
1890 let cap = n + self.len();
1891 let mut v = Vec::new();
1892 v.try_reserve(cap)?;
1893 let iter = self.iter_mut().map(core::mem::take);
1894 v.extend(iter);
1895 self.set_len(0);
1896 return Ok(v);
1897 }
1898
1899 /// Drains all elements to a Vec
1900 /// ```
1901 /// # use tinyvec::*;
1902 /// let mut av = array_vec!([i32; 7] => 1, 2, 3);
1903 /// let v = av.drain_to_vec();
1904 /// assert_eq!(v, &[1, 2, 3]);
1905 /// assert_eq!(v.capacity(), 3);
1906 /// ```
1907 #[inline]
1908 pub fn drain_to_vec(&mut self) -> Vec<A::Item> {
1909 self.drain_to_vec_and_reserve(0)
1910 }
1911
1912 /// Tries to drain all elements to a Vec.
1913 ///
1914 /// # Errors
1915 ///
1916 /// If the allocator reports a failure, then an error is returned.
1917 ///
1918 /// ```
1919 /// # use tinyvec::*;
1920 /// let mut av = array_vec!([i32; 7] => 1, 2, 3);
1921 /// let v = av.try_drain_to_vec();
1922 /// assert!(matches!(v, Ok(_)));
1923 /// let v = v.unwrap();
1924 /// assert_eq!(v, &[1, 2, 3]);
1925 /// // Vec may reserve more than necessary in order to prevent more future allocations.
1926 /// assert!(v.capacity() >= 3);
1927 /// ```
1928 #[cfg(feature = "rustc_1_57")]
1929 pub fn try_drain_to_vec(&mut self) -> Result<Vec<A::Item>, TryReserveError> {
1930 self.try_drain_to_vec_and_reserve(0)
1931 }
1932}
1933
1934#[cfg(feature = "serde")]
1935struct ArrayVecVisitor<A: Array>(PhantomData<A>);
1936
1937#[cfg(feature = "serde")]
1938impl<'de, A: Array> Visitor<'de> for ArrayVecVisitor<A>
1939where
1940 A::Item: Deserialize<'de>,
1941{
1942 type Value = ArrayVec<A>;
1943
1944 fn expecting(
1945 &self, formatter: &mut core::fmt::Formatter,
1946 ) -> core::fmt::Result {
1947 formatter.write_str("a sequence")
1948 }
1949
1950 fn visit_seq<S>(self, mut seq: S) -> Result<Self::Value, S::Error>
1951 where
1952 S: SeqAccess<'de>,
1953 {
1954 let mut new_arrayvec: ArrayVec<A> = Default::default();
1955
1956 let mut idx = 0usize;
1957 while let Some(value) = seq.next_element()? {
1958 if new_arrayvec.len() >= new_arrayvec.capacity() {
1959 return Err(DeserializeError::invalid_length(idx, &self));
1960 }
1961 new_arrayvec.push(value);
1962 idx = idx + 1;
1963 }
1964
1965 Ok(new_arrayvec)
1966 }
1967}
1968
1969#[cfg(test)]
1970mod test {
1971 use super::*;
1972
1973 #[test]
1974 fn retain_mut_empty_vec() {
1975 let mut av: ArrayVec<[i32; 4]> = ArrayVec::new();
1976 av.retain_mut(|&mut x| x % 2 == 0);
1977 assert_eq!(av.len(), 0);
1978 }
1979
1980 #[test]
1981 fn retain_mut_all_elements() {
1982 let mut av: ArrayVec<[i32; 4]> = array_vec!([i32; 4] => 2, 4, 6, 8);
1983 av.retain_mut(|&mut x| x % 2 == 0);
1984 assert_eq!(av.len(), 4);
1985 assert_eq!(av.as_slice(), &[2, 4, 6, 8]);
1986 }
1987
1988 #[test]
1989 fn retain_mut_some_elements() {
1990 let mut av: ArrayVec<[i32; 4]> = array_vec!([i32; 4] => 1, 2, 3, 4);
1991 av.retain_mut(|&mut x| x % 2 == 0);
1992 assert_eq!(av.len(), 2);
1993 assert_eq!(av.as_slice(), &[2, 4]);
1994 }
1995
1996 #[test]
1997 fn retain_mut_no_elements() {
1998 let mut av: ArrayVec<[i32; 4]> = array_vec!([i32; 4] => 1, 3, 5, 7);
1999 av.retain_mut(|&mut x| x % 2 == 0);
2000 assert_eq!(av.len(), 0);
2001 }
2002
2003 #[test]
2004 fn retain_mut_zero_capacity() {
2005 let mut av: ArrayVec<[i32; 0]> = ArrayVec::new();
2006 av.retain_mut(|&mut x| x % 2 == 0);
2007 assert_eq!(av.len(), 0);
2008 }
2009}
2010