tinyvec/
arrayvec.rs

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    for i in 0..target.len() {
576      core::mem::swap(&mut item, &mut target[i]);
577    }
578    return None;
579  }
580
581  /// Checks if the length is 0.
582  #[inline(always)]
583  #[must_use]
584  pub fn is_empty(&self) -> bool {
585    self.len == 0
586  }
587
588  /// The length of the `ArrayVec` (in elements).
589  #[inline(always)]
590  #[must_use]
591  pub fn len(&self) -> usize {
592    self.len as usize
593  }
594
595  /// Makes a new, empty `ArrayVec`.
596  #[inline(always)]
597  #[must_use]
598  pub fn new() -> Self {
599    Self::default()
600  }
601
602  /// Remove and return the last element of the vec, if there is one.
603  ///
604  /// ## Failure
605  /// * If the vec is empty you get `None`.
606  ///
607  /// ## Example
608  /// ```rust
609  /// # use tinyvec::*;
610  /// let mut av = array_vec!([i32; 10] => 1, 2);
611  /// assert_eq!(av.pop(), Some(2));
612  /// assert_eq!(av.pop(), Some(1));
613  /// assert_eq!(av.pop(), None);
614  /// ```
615  #[inline]
616  pub fn pop(&mut self) -> Option<A::Item> {
617    if self.len > 0 {
618      self.len -= 1;
619      let out =
620        core::mem::take(&mut self.data.as_slice_mut()[self.len as usize]);
621      Some(out)
622    } else {
623      None
624    }
625  }
626
627  /// Place an element onto the end of the vec.
628  ///
629  /// ## Panics
630  /// * If the length of the vec would overflow the capacity.
631  ///
632  /// ## Example
633  /// ```rust
634  /// # use tinyvec::*;
635  /// let mut av = array_vec!([i32; 2]);
636  /// assert_eq!(&av[..], []);
637  /// av.push(1);
638  /// assert_eq!(&av[..], [1]);
639  /// av.push(2);
640  /// assert_eq!(&av[..], [1, 2]);
641  /// // av.push(3); this would overflow the ArrayVec and panic!
642  /// ```
643  #[inline(always)]
644  pub fn push(&mut self, val: A::Item) {
645    let x = self.try_push(val);
646    assert!(x.is_none(), "ArrayVec::push> capacity overflow!");
647  }
648
649  /// Tries to place an element onto the end of the vec.\
650  /// Returns back the element if the capacity is exhausted,
651  /// otherwise returns None.
652  /// ```rust
653  /// # use tinyvec::*;
654  /// let mut av = array_vec!([i32; 2]);
655  /// assert_eq!(av.as_slice(), []);
656  /// assert_eq!(av.try_push(1), None);
657  /// assert_eq!(&av[..], [1]);
658  /// assert_eq!(av.try_push(2), None);
659  /// assert_eq!(&av[..], [1, 2]);
660  /// assert_eq!(av.try_push(3), Some(3));
661  /// ```
662  #[inline(always)]
663  pub fn try_push(&mut self, val: A::Item) -> Option<A::Item> {
664    debug_assert!(self.len as usize <= A::CAPACITY);
665
666    let itemref = match self.data.as_slice_mut().get_mut(self.len as usize) {
667      None => return Some(val),
668      Some(x) => x,
669    };
670
671    *itemref = val;
672    self.len += 1;
673    return None;
674  }
675
676  /// Removes the item at `index`, shifting all others down by one index.
677  ///
678  /// Returns the removed element.
679  ///
680  /// ## Panics
681  ///
682  /// * If the index is out of bounds.
683  ///
684  /// ## Example
685  ///
686  /// ```rust
687  /// # use tinyvec::*;
688  /// let mut av = array_vec!([i32; 4] => 1, 2, 3);
689  /// assert_eq!(av.remove(1), 2);
690  /// assert_eq!(&av[..], [1, 3]);
691  /// ```
692  #[inline]
693  pub fn remove(&mut self, index: usize) -> A::Item {
694    let targets: &mut [A::Item] = &mut self.deref_mut()[index..];
695    let item = core::mem::take(&mut targets[0]);
696
697    // A previous implementation used rotate_left
698    // rotate_right and rotate_left generate a huge amount of code and fail to
699    // inline; calling them here incurs the cost of all the cases they
700    // handle even though we're rotating a usually-small array by a constant
701    // 1 offset. This swap-based implementation benchmarks much better for
702    // small array lengths in particular.
703
704    for i in 0..targets.len() - 1 {
705      targets.swap(i, i + 1);
706    }
707    self.len -= 1;
708    item
709  }
710
711  /// As [`resize_with`](ArrayVec::resize_with)
712  /// and it clones the value as the closure.
713  ///
714  /// ## Example
715  ///
716  /// ```rust
717  /// # use tinyvec::*;
718  ///
719  /// let mut av = array_vec!([&str; 10] => "hello");
720  /// av.resize(3, "world");
721  /// assert_eq!(&av[..], ["hello", "world", "world"]);
722  ///
723  /// let mut av = array_vec!([i32; 10] => 1, 2, 3, 4);
724  /// av.resize(2, 0);
725  /// assert_eq!(&av[..], [1, 2]);
726  /// ```
727  #[inline]
728  pub fn resize(&mut self, new_len: usize, new_val: A::Item)
729  where
730    A::Item: Clone,
731  {
732    self.resize_with(new_len, || new_val.clone())
733  }
734
735  /// Resize the vec to the new length.
736  ///
737  /// If it needs to be longer, it's filled with repeated calls to the provided
738  /// function. If it needs to be shorter, it's truncated.
739  ///
740  /// ## Example
741  ///
742  /// ```rust
743  /// # use tinyvec::*;
744  ///
745  /// let mut av = array_vec!([i32; 10] => 1, 2, 3);
746  /// av.resize_with(5, Default::default);
747  /// assert_eq!(&av[..], [1, 2, 3, 0, 0]);
748  ///
749  /// let mut av = array_vec!([i32; 10]);
750  /// let mut p = 1;
751  /// av.resize_with(4, || {
752  ///   p *= 2;
753  ///   p
754  /// });
755  /// assert_eq!(&av[..], [2, 4, 8, 16]);
756  /// ```
757  #[inline]
758  pub fn resize_with<F: FnMut() -> A::Item>(
759    &mut self, new_len: usize, mut f: F,
760  ) {
761    match new_len.checked_sub(self.len as usize) {
762      None => self.truncate(new_len),
763      Some(new_elements) => {
764        for _ in 0..new_elements {
765          self.push(f());
766        }
767      }
768    }
769  }
770
771  /// Walk the vec and keep only the elements that pass the predicate given.
772  ///
773  /// ## Example
774  ///
775  /// ```rust
776  /// # use tinyvec::*;
777  ///
778  /// let mut av = array_vec!([i32; 10] => 1, 1, 2, 3, 3, 4);
779  /// av.retain(|&x| x % 2 == 0);
780  /// assert_eq!(&av[..], [2, 4]);
781  /// ```
782  #[inline]
783  pub fn retain<F: FnMut(&A::Item) -> bool>(&mut self, mut acceptable: F) {
784    // Drop guard to contain exactly the remaining elements when the test
785    // panics.
786    struct JoinOnDrop<'vec, Item> {
787      items: &'vec mut [Item],
788      done_end: usize,
789      // Start of tail relative to `done_end`.
790      tail_start: usize,
791    }
792
793    impl<Item> Drop for JoinOnDrop<'_, Item> {
794      fn drop(&mut self) {
795        self.items[self.done_end..].rotate_left(self.tail_start);
796      }
797    }
798
799    let mut rest = JoinOnDrop {
800      items: &mut self.data.as_slice_mut()[..self.len as usize],
801      done_end: 0,
802      tail_start: 0,
803    };
804
805    let len = self.len as usize;
806    for idx in 0..len {
807      // Loop start invariant: idx = rest.done_end + rest.tail_start
808      if !acceptable(&rest.items[idx]) {
809        let _ = core::mem::take(&mut rest.items[idx]);
810        self.len -= 1;
811        rest.tail_start += 1;
812      } else {
813        rest.items.swap(rest.done_end, idx);
814        rest.done_end += 1;
815      }
816    }
817  }
818
819  /// Retains only the elements specified by the predicate, passing a mutable
820  /// reference to it.
821  ///
822  /// In other words, remove all elements e such that f(&mut e) returns false.
823  /// This method operates in place, visiting each element exactly once in the
824  /// original order, and preserves the order of the retained elements.
825  ///
826  ///
827  /// ## Example
828  ///
829  /// ```rust
830  /// # use tinyvec::*;
831  ///
832  /// let mut av = array_vec!([i32; 10] => 1, 1, 2, 3, 3, 4);
833  /// av.retain_mut(|x| if *x % 2 == 0 { *x *= 2; true } else { false });
834  /// assert_eq!(&av[..], [4, 8]);
835  /// ```
836  #[inline]
837  pub fn retain_mut<F>(&mut self, mut acceptable: F)
838  where
839    F: FnMut(&mut A::Item) -> bool,
840  {
841    // Drop guard to contain exactly the remaining elements when the test
842    // panics.
843    struct JoinOnDrop<'vec, Item> {
844      items: &'vec mut [Item],
845      done_end: usize,
846      // Start of tail relative to `done_end`.
847      tail_start: usize,
848    }
849
850    impl<Item> Drop for JoinOnDrop<'_, Item> {
851      fn drop(&mut self) {
852        self.items[self.done_end..].rotate_left(self.tail_start);
853      }
854    }
855
856    let mut rest = JoinOnDrop {
857      items: &mut self.data.as_slice_mut()[..self.len as usize],
858      done_end: 0,
859      tail_start: 0,
860    };
861
862    let len = self.len as usize;
863    for idx in 0..len {
864      // Loop start invariant: idx = rest.done_end + rest.tail_start
865      if !acceptable(&mut rest.items[idx]) {
866        let _ = core::mem::take(&mut rest.items[idx]);
867        self.len -= 1;
868        rest.tail_start += 1;
869      } else {
870        rest.items.swap(rest.done_end, idx);
871        rest.done_end += 1;
872      }
873    }
874  }
875
876  /// Forces the length of the vector to `new_len`.
877  ///
878  /// ## Panics
879  /// * If `new_len` is greater than the vec's capacity.
880  ///
881  /// ## Safety
882  /// * This is a fully safe operation! The inactive memory already counts as
883  ///   "initialized" by Rust's rules.
884  /// * Other than "the memory is initialized" there are no other guarantees
885  ///   regarding what you find in the inactive portion of the vec.
886  #[inline(always)]
887  pub fn set_len(&mut self, new_len: usize) {
888    if new_len > A::CAPACITY {
889      // Note(Lokathor): Technically we don't have to panic here, and we could
890      // just let some other call later on trigger a panic on accident when the
891      // length is wrong. However, it's a lot easier to catch bugs when things
892      // are more "fail-fast".
893      panic!(
894        "ArrayVec::set_len> new length {} exceeds capacity {}",
895        new_len,
896        A::CAPACITY
897      )
898    }
899
900    let new_len: u16 = new_len
901      .try_into()
902      .expect("ArrayVec::set_len> new length is not in range 0..=u16::MAX");
903    self.len = new_len;
904  }
905
906  /// Splits the collection at the point given.
907  ///
908  /// * `[0, at)` stays in this vec
909  /// * `[at, len)` ends up in the new vec.
910  ///
911  /// ## Panics
912  /// * if at > len
913  ///
914  /// ## Example
915  ///
916  /// ```rust
917  /// # use tinyvec::*;
918  /// let mut av = array_vec!([i32; 4] => 1, 2, 3);
919  /// let av2 = av.split_off(1);
920  /// assert_eq!(&av[..], [1]);
921  /// assert_eq!(&av2[..], [2, 3]);
922  /// ```
923  #[inline]
924  pub fn split_off(&mut self, at: usize) -> Self {
925    // FIXME: should this just use drain into the output?
926    if at > self.len() {
927      panic!(
928        "ArrayVec::split_off> at value {} exceeds length of {}",
929        at, self.len
930      );
931    }
932    let mut new = Self::default();
933    let moves = &mut self.as_mut_slice()[at..];
934    let split_len = moves.len();
935    let targets = &mut new.data.as_slice_mut()[..split_len];
936    moves.swap_with_slice(targets);
937
938    /* moves.len() <= u16::MAX, so these are surely in u16 range */
939    new.len = split_len as u16;
940    self.len = at as u16;
941    new
942  }
943
944  /// Creates a splicing iterator that removes the specified range in the
945  /// vector, yields the removed items, and replaces them with elements from
946  /// the provided iterator.
947  ///
948  /// `splice` fuses the provided iterator, so elements after the first `None`
949  /// are ignored.
950  ///
951  /// ## Panics
952  /// * If the start is greater than the end.
953  /// * If the end is past the edge of the vec.
954  /// * If the provided iterator panics.
955  /// * If the new length would overflow the capacity of the array. Because
956  ///   `ArrayVecSplice` adds elements to this vec in its destructor when
957  ///   necessary, this panic would occur when it is dropped.
958  ///
959  /// ## Example
960  /// ```rust
961  /// use tinyvec::*;
962  /// let mut av = array_vec!([i32; 4] => 1, 2, 3);
963  /// let av2: ArrayVec<[i32; 4]> = av.splice(1.., 4..=6).collect();
964  /// assert_eq!(av.as_slice(), &[1, 4, 5, 6][..]);
965  /// assert_eq!(av2.as_slice(), &[2, 3][..]);
966  ///
967  /// av.splice(.., None);
968  /// assert_eq!(av.as_slice(), &[]);
969  /// ```
970  #[inline]
971  pub fn splice<R, I>(
972    &mut self, range: R, replacement: I,
973  ) -> ArrayVecSplice<'_, A, core::iter::Fuse<I::IntoIter>>
974  where
975    R: RangeBounds<usize>,
976    I: IntoIterator<Item = A::Item>,
977  {
978    use core::ops::Bound;
979    let start = match range.start_bound() {
980      Bound::Included(x) => *x,
981      Bound::Excluded(x) => x.saturating_add(1),
982      Bound::Unbounded => 0,
983    };
984    let end = match range.end_bound() {
985      Bound::Included(x) => x.saturating_add(1),
986      Bound::Excluded(x) => *x,
987      Bound::Unbounded => self.len(),
988    };
989    assert!(
990      start <= end,
991      "ArrayVec::splice> Illegal range, {} to {}",
992      start,
993      end
994    );
995    assert!(
996      end <= self.len(),
997      "ArrayVec::splice> Range ends at {} but length is only {}!",
998      end,
999      self.len()
1000    );
1001
1002    ArrayVecSplice {
1003      removal_start: start,
1004      removal_end: end,
1005      parent: self,
1006      replacement: replacement.into_iter().fuse(),
1007    }
1008  }
1009
1010  /// Remove an element, swapping the end of the vec into its place.
1011  ///
1012  /// ## Panics
1013  /// * If the index is out of bounds.
1014  ///
1015  /// ## Example
1016  /// ```rust
1017  /// # use tinyvec::*;
1018  /// let mut av = array_vec!([&str; 4] => "foo", "bar", "quack", "zap");
1019  ///
1020  /// assert_eq!(av.swap_remove(1), "bar");
1021  /// assert_eq!(&av[..], ["foo", "zap", "quack"]);
1022  ///
1023  /// assert_eq!(av.swap_remove(0), "foo");
1024  /// assert_eq!(&av[..], ["quack", "zap"]);
1025  /// ```
1026  #[inline]
1027  pub fn swap_remove(&mut self, index: usize) -> A::Item {
1028    assert!(
1029      index < self.len(),
1030      "ArrayVec::swap_remove> index {} is out of bounds {}",
1031      index,
1032      self.len
1033    );
1034    if index == self.len() - 1 {
1035      self.pop().unwrap()
1036    } else {
1037      let i = self.pop().unwrap();
1038      replace(&mut self[index], i)
1039    }
1040  }
1041
1042  /// Reduces the vec's length to the given value.
1043  ///
1044  /// If the vec is already shorter than the input, nothing happens.
1045  #[inline]
1046  pub fn truncate(&mut self, new_len: usize) {
1047    if new_len >= self.len as usize {
1048      return;
1049    }
1050
1051    if needs_drop::<A::Item>() {
1052      let len = self.len as usize;
1053      self.data.as_slice_mut()[new_len..len]
1054        .iter_mut()
1055        .map(core::mem::take)
1056        .for_each(drop);
1057    }
1058
1059    /* new_len is less than self.len */
1060    self.len = new_len as u16;
1061  }
1062
1063  /// Wraps an array, using the given length as the starting length.
1064  ///
1065  /// If you want to use the whole length of the array, you can just use the
1066  /// `From` impl.
1067  ///
1068  /// ## Failure
1069  ///
1070  /// If the given length is greater than the capacity of the array this will
1071  /// error, and you'll get the array back in the `Err`.
1072  #[inline]
1073  pub fn try_from_array_len(data: A, len: usize) -> Result<Self, A> {
1074    /* Note(Soveu): Should we allow A::CAPACITY > u16::MAX for now? */
1075    if len <= A::CAPACITY {
1076      Ok(Self { data, len: len as u16 })
1077    } else {
1078      Err(data)
1079    }
1080  }
1081}
1082
1083impl<A> ArrayVec<A> {
1084  /// Wraps up an array as a new empty `ArrayVec`.
1085  ///
1086  /// If you want to simply use the full array, use `from` instead.
1087  ///
1088  /// ## Examples
1089  ///
1090  /// This method in particular allows to create values for statics:
1091  ///
1092  /// ```rust
1093  /// # use tinyvec::ArrayVec;
1094  /// static DATA: ArrayVec<[u8; 5]> = ArrayVec::from_array_empty([0; 5]);
1095  /// assert_eq!(DATA.len(), 0);
1096  /// ```
1097  ///
1098  /// But of course it is just an normal empty `ArrayVec`:
1099  ///
1100  /// ```rust
1101  /// # use tinyvec::ArrayVec;
1102  /// let mut data = ArrayVec::from_array_empty([1, 2, 3, 4]);
1103  /// assert_eq!(&data[..], &[]);
1104  /// data.push(42);
1105  /// assert_eq!(&data[..], &[42]);
1106  /// ```
1107  #[inline]
1108  #[must_use]
1109  pub const fn from_array_empty(data: A) -> Self {
1110    Self { data, len: 0 }
1111  }
1112}
1113
1114#[cfg(feature = "grab_spare_slice")]
1115impl<A: Array> ArrayVec<A> {
1116  /// Obtain the shared slice of the array _after_ the active memory.
1117  ///
1118  /// ## Example
1119  /// ```rust
1120  /// # use tinyvec::*;
1121  /// let mut av = array_vec!([i32; 4]);
1122  /// assert_eq!(av.grab_spare_slice().len(), 4);
1123  /// av.push(10);
1124  /// av.push(11);
1125  /// av.push(12);
1126  /// av.push(13);
1127  /// assert_eq!(av.grab_spare_slice().len(), 0);
1128  /// ```
1129  #[inline(always)]
1130  pub fn grab_spare_slice(&self) -> &[A::Item] {
1131    &self.data.as_slice()[self.len as usize..]
1132  }
1133
1134  /// Obtain the mutable slice of the array _after_ the active memory.
1135  ///
1136  /// ## Example
1137  /// ```rust
1138  /// # use tinyvec::*;
1139  /// let mut av = array_vec!([i32; 4]);
1140  /// assert_eq!(av.grab_spare_slice_mut().len(), 4);
1141  /// av.push(10);
1142  /// av.push(11);
1143  /// assert_eq!(av.grab_spare_slice_mut().len(), 2);
1144  /// ```
1145  #[inline(always)]
1146  pub fn grab_spare_slice_mut(&mut self) -> &mut [A::Item] {
1147    &mut self.data.as_slice_mut()[self.len as usize..]
1148  }
1149}
1150
1151#[cfg(feature = "nightly_slice_partition_dedup")]
1152impl<A: Array> ArrayVec<A> {
1153  /// De-duplicates the vec contents.
1154  #[inline(always)]
1155  pub fn dedup(&mut self)
1156  where
1157    A::Item: PartialEq,
1158  {
1159    self.dedup_by(|a, b| a == b)
1160  }
1161
1162  /// De-duplicates the vec according to the predicate given.
1163  #[inline(always)]
1164  pub fn dedup_by<F>(&mut self, same_bucket: F)
1165  where
1166    F: FnMut(&mut A::Item, &mut A::Item) -> bool,
1167  {
1168    let len = {
1169      let (dedup, _) = self.as_mut_slice().partition_dedup_by(same_bucket);
1170      dedup.len()
1171    };
1172    self.truncate(len);
1173  }
1174
1175  /// De-duplicates the vec according to the key selector given.
1176  #[inline(always)]
1177  pub fn dedup_by_key<F, K>(&mut self, mut key: F)
1178  where
1179    F: FnMut(&mut A::Item) -> K,
1180    K: PartialEq,
1181  {
1182    self.dedup_by(|a, b| key(a) == key(b))
1183  }
1184}
1185
1186impl<A> ArrayVec<A> {
1187  /// Returns the reference to the inner array of the `ArrayVec`.
1188  ///
1189  /// This returns the full array, even if the `ArrayVec` length is currently
1190  /// less than that.
1191  #[inline(always)]
1192  #[must_use]
1193  pub const fn as_inner(&self) -> &A {
1194    &self.data
1195  }
1196}
1197
1198/// Splicing iterator for `ArrayVec`
1199/// See [`ArrayVec::splice`](ArrayVec::<A>::splice)
1200pub struct ArrayVecSplice<'p, A: Array, I: Iterator<Item = A::Item>> {
1201  parent: &'p mut ArrayVec<A>,
1202  removal_start: usize,
1203  removal_end: usize,
1204  replacement: I,
1205}
1206
1207impl<'p, A: Array, I: Iterator<Item = A::Item>> Iterator
1208  for ArrayVecSplice<'p, A, I>
1209{
1210  type Item = A::Item;
1211
1212  #[inline]
1213  fn next(&mut self) -> Option<A::Item> {
1214    if self.removal_start < self.removal_end {
1215      match self.replacement.next() {
1216        Some(replacement) => {
1217          let removed = core::mem::replace(
1218            &mut self.parent[self.removal_start],
1219            replacement,
1220          );
1221          self.removal_start += 1;
1222          Some(removed)
1223        }
1224        None => {
1225          let removed = self.parent.remove(self.removal_start);
1226          self.removal_end -= 1;
1227          Some(removed)
1228        }
1229      }
1230    } else {
1231      None
1232    }
1233  }
1234
1235  #[inline]
1236  fn size_hint(&self) -> (usize, Option<usize>) {
1237    let len = self.len();
1238    (len, Some(len))
1239  }
1240}
1241
1242impl<'p, A, I> ExactSizeIterator for ArrayVecSplice<'p, A, I>
1243where
1244  A: Array,
1245  I: Iterator<Item = A::Item>,
1246{
1247  #[inline]
1248  fn len(&self) -> usize {
1249    self.removal_end - self.removal_start
1250  }
1251}
1252
1253impl<'p, A, I> FusedIterator for ArrayVecSplice<'p, A, I>
1254where
1255  A: Array,
1256  I: Iterator<Item = A::Item>,
1257{
1258}
1259
1260impl<'p, A, I> DoubleEndedIterator for ArrayVecSplice<'p, A, I>
1261where
1262  A: Array,
1263  I: Iterator<Item = A::Item> + DoubleEndedIterator,
1264{
1265  #[inline]
1266  fn next_back(&mut self) -> Option<A::Item> {
1267    if self.removal_start < self.removal_end {
1268      match self.replacement.next_back() {
1269        Some(replacement) => {
1270          let removed = core::mem::replace(
1271            &mut self.parent[self.removal_end - 1],
1272            replacement,
1273          );
1274          self.removal_end -= 1;
1275          Some(removed)
1276        }
1277        None => {
1278          let removed = self.parent.remove(self.removal_end - 1);
1279          self.removal_end -= 1;
1280          Some(removed)
1281        }
1282      }
1283    } else {
1284      None
1285    }
1286  }
1287}
1288
1289impl<'p, A: Array, I: Iterator<Item = A::Item>> Drop
1290  for ArrayVecSplice<'p, A, I>
1291{
1292  #[inline]
1293  fn drop(&mut self) {
1294    for _ in self.by_ref() {}
1295
1296    // FIXME: reserve lower bound of size_hint
1297
1298    for replacement in self.replacement.by_ref() {
1299      self.parent.insert(self.removal_end, replacement);
1300      self.removal_end += 1;
1301    }
1302  }
1303}
1304
1305impl<A: Array> AsMut<[A::Item]> for ArrayVec<A> {
1306  #[inline(always)]
1307  #[must_use]
1308  fn as_mut(&mut self) -> &mut [A::Item] {
1309    &mut *self
1310  }
1311}
1312
1313impl<A: Array> AsRef<[A::Item]> for ArrayVec<A> {
1314  #[inline(always)]
1315  #[must_use]
1316  fn as_ref(&self) -> &[A::Item] {
1317    &*self
1318  }
1319}
1320
1321impl<A: Array> Borrow<[A::Item]> for ArrayVec<A> {
1322  #[inline(always)]
1323  #[must_use]
1324  fn borrow(&self) -> &[A::Item] {
1325    &*self
1326  }
1327}
1328
1329impl<A: Array> BorrowMut<[A::Item]> for ArrayVec<A> {
1330  #[inline(always)]
1331  #[must_use]
1332  fn borrow_mut(&mut self) -> &mut [A::Item] {
1333    &mut *self
1334  }
1335}
1336
1337impl<A: Array> Extend<A::Item> for ArrayVec<A> {
1338  #[inline]
1339  fn extend<T: IntoIterator<Item = A::Item>>(&mut self, iter: T) {
1340    for t in iter {
1341      self.push(t)
1342    }
1343  }
1344}
1345
1346impl<A: Array> From<A> for ArrayVec<A> {
1347  #[inline(always)]
1348  #[must_use]
1349  /// The output has a length equal to the full array.
1350  ///
1351  /// If you want to select a length, use
1352  /// [`from_array_len`](ArrayVec::from_array_len)
1353  fn from(data: A) -> Self {
1354    let len: u16 = data
1355      .as_slice()
1356      .len()
1357      .try_into()
1358      .expect("ArrayVec::from> length must be in range 0..=u16::MAX");
1359    Self { len, data }
1360  }
1361}
1362
1363/// The error type returned when a conversion from a slice to an [`ArrayVec`]
1364/// fails.
1365#[derive(Debug, Copy, Clone)]
1366pub struct TryFromSliceError(());
1367
1368impl core::fmt::Display for TryFromSliceError {
1369  #[inline]
1370  fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
1371    f.write_str("could not convert slice to ArrayVec")
1372  }
1373}
1374
1375#[cfg(feature = "std")]
1376impl std::error::Error for TryFromSliceError {}
1377
1378impl<T, A> TryFrom<&'_ [T]> for ArrayVec<A>
1379where
1380  T: Clone + Default,
1381  A: Array<Item = T>,
1382{
1383  type Error = TryFromSliceError;
1384
1385  #[inline]
1386  /// The output has a length equal to that of the slice, with the same capacity
1387  /// as `A`.
1388  fn try_from(slice: &[T]) -> Result<Self, Self::Error> {
1389    if slice.len() > A::CAPACITY {
1390      Err(TryFromSliceError(()))
1391    } else {
1392      let mut arr = ArrayVec::new();
1393      // We do not use ArrayVec::extend_from_slice, because it looks like LLVM
1394      // fails to deduplicate all the length-checking logic between the
1395      // above if and the contents of that method, thus producing much
1396      // slower code. Unlike many of the other optimizations in this
1397      // crate, this one is worth keeping an eye on. I see no reason, for
1398      // any element type, that these should produce different code. But
1399      // they do. (rustc 1.51.0)
1400      arr.set_len(slice.len());
1401      arr.as_mut_slice().clone_from_slice(slice);
1402      Ok(arr)
1403    }
1404  }
1405}
1406
1407impl<A: Array> FromIterator<A::Item> for ArrayVec<A> {
1408  #[inline]
1409  #[must_use]
1410  fn from_iter<T: IntoIterator<Item = A::Item>>(iter: T) -> Self {
1411    let mut av = Self::default();
1412    for i in iter {
1413      av.push(i)
1414    }
1415    av
1416  }
1417}
1418
1419/// Iterator for consuming an `ArrayVec` and returning owned elements.
1420pub struct ArrayVecIterator<A: Array> {
1421  base: u16,
1422  tail: u16,
1423  data: A,
1424}
1425
1426impl<A: Array> ArrayVecIterator<A> {
1427  /// Returns the remaining items of this iterator as a slice.
1428  #[inline]
1429  #[must_use]
1430  pub fn as_slice(&self) -> &[A::Item] {
1431    &self.data.as_slice()[self.base as usize..self.tail as usize]
1432  }
1433}
1434impl<A: Array> FusedIterator for ArrayVecIterator<A> {}
1435impl<A: Array> Iterator for ArrayVecIterator<A> {
1436  type Item = A::Item;
1437  #[inline]
1438  fn next(&mut self) -> Option<Self::Item> {
1439    let slice =
1440      &mut self.data.as_slice_mut()[self.base as usize..self.tail as usize];
1441    let itemref = slice.first_mut()?;
1442    self.base += 1;
1443    return Some(core::mem::take(itemref));
1444  }
1445  #[inline(always)]
1446  #[must_use]
1447  fn size_hint(&self) -> (usize, Option<usize>) {
1448    let s = self.tail - self.base;
1449    let s = s as usize;
1450    (s, Some(s))
1451  }
1452  #[inline(always)]
1453  fn count(self) -> usize {
1454    self.size_hint().0
1455  }
1456  #[inline]
1457  fn last(mut self) -> Option<Self::Item> {
1458    self.next_back()
1459  }
1460  #[inline]
1461  fn nth(&mut self, n: usize) -> Option<A::Item> {
1462    let slice = &mut self.data.as_slice_mut();
1463    let slice = &mut slice[self.base as usize..self.tail as usize];
1464
1465    if let Some(x) = slice.get_mut(n) {
1466      /* n is in range [0 .. self.tail - self.base) so in u16 range */
1467      self.base += n as u16 + 1;
1468      return Some(core::mem::take(x));
1469    }
1470
1471    self.base = self.tail;
1472    return None;
1473  }
1474}
1475
1476impl<A: Array> DoubleEndedIterator for ArrayVecIterator<A> {
1477  #[inline]
1478  fn next_back(&mut self) -> Option<Self::Item> {
1479    let slice =
1480      &mut self.data.as_slice_mut()[self.base as usize..self.tail as usize];
1481    let item = slice.last_mut()?;
1482    self.tail -= 1;
1483    return Some(core::mem::take(item));
1484  }
1485
1486  #[inline]
1487  fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
1488    let base = self.base as usize;
1489    let tail = self.tail as usize;
1490    let slice = &mut self.data.as_slice_mut()[base..tail];
1491    let n = n.saturating_add(1);
1492
1493    if let Some(n) = slice.len().checked_sub(n) {
1494      let item = &mut slice[n];
1495      /* n is in [0..self.tail - self.base] range, so in u16 range */
1496      self.tail = self.base + n as u16;
1497      return Some(core::mem::take(item));
1498    }
1499
1500    self.tail = self.base;
1501    return None;
1502  }
1503}
1504
1505impl<A: Array> ExactSizeIterator for ArrayVecIterator<A> {
1506  #[inline]
1507  fn len(&self) -> usize {
1508    self.size_hint().0
1509  }
1510}
1511
1512impl<A: Array> Debug for ArrayVecIterator<A>
1513where
1514  A::Item: Debug,
1515{
1516  #[allow(clippy::missing_inline_in_public_items)]
1517  fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
1518    f.debug_tuple("ArrayVecIterator").field(&self.as_slice()).finish()
1519  }
1520}
1521
1522impl<A: Array> IntoIterator for ArrayVec<A> {
1523  type Item = A::Item;
1524  type IntoIter = ArrayVecIterator<A>;
1525  #[inline(always)]
1526  #[must_use]
1527  fn into_iter(self) -> Self::IntoIter {
1528    ArrayVecIterator { base: 0, tail: self.len, data: self.data }
1529  }
1530}
1531
1532impl<'a, A: Array> IntoIterator for &'a mut ArrayVec<A> {
1533  type Item = &'a mut A::Item;
1534  type IntoIter = core::slice::IterMut<'a, A::Item>;
1535  #[inline(always)]
1536  #[must_use]
1537  fn into_iter(self) -> Self::IntoIter {
1538    self.iter_mut()
1539  }
1540}
1541
1542impl<'a, A: Array> IntoIterator for &'a ArrayVec<A> {
1543  type Item = &'a A::Item;
1544  type IntoIter = core::slice::Iter<'a, A::Item>;
1545  #[inline(always)]
1546  #[must_use]
1547  fn into_iter(self) -> Self::IntoIter {
1548    self.iter()
1549  }
1550}
1551
1552impl<A: Array> PartialEq for ArrayVec<A>
1553where
1554  A::Item: PartialEq,
1555{
1556  #[inline]
1557  #[must_use]
1558  fn eq(&self, other: &Self) -> bool {
1559    self.as_slice().eq(other.as_slice())
1560  }
1561}
1562impl<A: Array> Eq for ArrayVec<A> where A::Item: Eq {}
1563
1564impl<A: Array> PartialOrd for ArrayVec<A>
1565where
1566  A::Item: PartialOrd,
1567{
1568  #[inline]
1569  #[must_use]
1570  fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
1571    self.as_slice().partial_cmp(other.as_slice())
1572  }
1573}
1574impl<A: Array> Ord for ArrayVec<A>
1575where
1576  A::Item: Ord,
1577{
1578  #[inline]
1579  #[must_use]
1580  fn cmp(&self, other: &Self) -> core::cmp::Ordering {
1581    self.as_slice().cmp(other.as_slice())
1582  }
1583}
1584
1585impl<A: Array> PartialEq<&A> for ArrayVec<A>
1586where
1587  A::Item: PartialEq,
1588{
1589  #[inline]
1590  #[must_use]
1591  fn eq(&self, other: &&A) -> bool {
1592    self.as_slice().eq(other.as_slice())
1593  }
1594}
1595
1596impl<A: Array> PartialEq<&[A::Item]> for ArrayVec<A>
1597where
1598  A::Item: PartialEq,
1599{
1600  #[inline]
1601  #[must_use]
1602  fn eq(&self, other: &&[A::Item]) -> bool {
1603    self.as_slice().eq(*other)
1604  }
1605}
1606
1607impl<A: Array> Hash for ArrayVec<A>
1608where
1609  A::Item: Hash,
1610{
1611  #[inline]
1612  fn hash<H: Hasher>(&self, state: &mut H) {
1613    self.as_slice().hash(state)
1614  }
1615}
1616
1617#[cfg(feature = "experimental_write_impl")]
1618impl<A: Array<Item = u8>> core::fmt::Write for ArrayVec<A> {
1619  fn write_str(&mut self, s: &str) -> core::fmt::Result {
1620    let my_len = self.len();
1621    let str_len = s.as_bytes().len();
1622    if my_len + str_len <= A::CAPACITY {
1623      let remainder = &mut self.data.as_slice_mut()[my_len..];
1624      let target = &mut remainder[..str_len];
1625      target.copy_from_slice(s.as_bytes());
1626      Ok(())
1627    } else {
1628      Err(core::fmt::Error)
1629    }
1630  }
1631}
1632
1633// // // // // // // //
1634// Formatting impls
1635// // // // // // // //
1636
1637impl<A: Array> Binary for ArrayVec<A>
1638where
1639  A::Item: Binary,
1640{
1641  #[allow(clippy::missing_inline_in_public_items)]
1642  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1643    write!(f, "[")?;
1644    if f.alternate() {
1645      write!(f, "\n    ")?;
1646    }
1647    for (i, elem) in self.iter().enumerate() {
1648      if i > 0 {
1649        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1650      }
1651      Binary::fmt(elem, f)?;
1652    }
1653    if f.alternate() {
1654      write!(f, ",\n")?;
1655    }
1656    write!(f, "]")
1657  }
1658}
1659
1660impl<A: Array> Debug for ArrayVec<A>
1661where
1662  A::Item: Debug,
1663{
1664  #[allow(clippy::missing_inline_in_public_items)]
1665  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1666    write!(f, "[")?;
1667    if f.alternate() && !self.is_empty() {
1668      write!(f, "\n    ")?;
1669    }
1670    for (i, elem) in self.iter().enumerate() {
1671      if i > 0 {
1672        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1673      }
1674      Debug::fmt(elem, f)?;
1675    }
1676    if f.alternate() && !self.is_empty() {
1677      write!(f, ",\n")?;
1678    }
1679    write!(f, "]")
1680  }
1681}
1682
1683impl<A: Array> Display for ArrayVec<A>
1684where
1685  A::Item: Display,
1686{
1687  #[allow(clippy::missing_inline_in_public_items)]
1688  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1689    write!(f, "[")?;
1690    if f.alternate() {
1691      write!(f, "\n    ")?;
1692    }
1693    for (i, elem) in self.iter().enumerate() {
1694      if i > 0 {
1695        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1696      }
1697      Display::fmt(elem, f)?;
1698    }
1699    if f.alternate() {
1700      write!(f, ",\n")?;
1701    }
1702    write!(f, "]")
1703  }
1704}
1705
1706impl<A: Array> LowerExp for ArrayVec<A>
1707where
1708  A::Item: LowerExp,
1709{
1710  #[allow(clippy::missing_inline_in_public_items)]
1711  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1712    write!(f, "[")?;
1713    if f.alternate() {
1714      write!(f, "\n    ")?;
1715    }
1716    for (i, elem) in self.iter().enumerate() {
1717      if i > 0 {
1718        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1719      }
1720      LowerExp::fmt(elem, f)?;
1721    }
1722    if f.alternate() {
1723      write!(f, ",\n")?;
1724    }
1725    write!(f, "]")
1726  }
1727}
1728
1729impl<A: Array> LowerHex for ArrayVec<A>
1730where
1731  A::Item: LowerHex,
1732{
1733  #[allow(clippy::missing_inline_in_public_items)]
1734  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1735    write!(f, "[")?;
1736    if f.alternate() {
1737      write!(f, "\n    ")?;
1738    }
1739    for (i, elem) in self.iter().enumerate() {
1740      if i > 0 {
1741        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1742      }
1743      LowerHex::fmt(elem, f)?;
1744    }
1745    if f.alternate() {
1746      write!(f, ",\n")?;
1747    }
1748    write!(f, "]")
1749  }
1750}
1751
1752impl<A: Array> Octal for ArrayVec<A>
1753where
1754  A::Item: Octal,
1755{
1756  #[allow(clippy::missing_inline_in_public_items)]
1757  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1758    write!(f, "[")?;
1759    if f.alternate() {
1760      write!(f, "\n    ")?;
1761    }
1762    for (i, elem) in self.iter().enumerate() {
1763      if i > 0 {
1764        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1765      }
1766      Octal::fmt(elem, f)?;
1767    }
1768    if f.alternate() {
1769      write!(f, ",\n")?;
1770    }
1771    write!(f, "]")
1772  }
1773}
1774
1775impl<A: Array> Pointer for ArrayVec<A>
1776where
1777  A::Item: Pointer,
1778{
1779  #[allow(clippy::missing_inline_in_public_items)]
1780  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1781    write!(f, "[")?;
1782    if f.alternate() {
1783      write!(f, "\n    ")?;
1784    }
1785    for (i, elem) in self.iter().enumerate() {
1786      if i > 0 {
1787        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1788      }
1789      Pointer::fmt(elem, f)?;
1790    }
1791    if f.alternate() {
1792      write!(f, ",\n")?;
1793    }
1794    write!(f, "]")
1795  }
1796}
1797
1798impl<A: Array> UpperExp for ArrayVec<A>
1799where
1800  A::Item: UpperExp,
1801{
1802  #[allow(clippy::missing_inline_in_public_items)]
1803  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1804    write!(f, "[")?;
1805    if f.alternate() {
1806      write!(f, "\n    ")?;
1807    }
1808    for (i, elem) in self.iter().enumerate() {
1809      if i > 0 {
1810        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1811      }
1812      UpperExp::fmt(elem, f)?;
1813    }
1814    if f.alternate() {
1815      write!(f, ",\n")?;
1816    }
1817    write!(f, "]")
1818  }
1819}
1820
1821impl<A: Array> UpperHex for ArrayVec<A>
1822where
1823  A::Item: UpperHex,
1824{
1825  #[allow(clippy::missing_inline_in_public_items)]
1826  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1827    write!(f, "[")?;
1828    if f.alternate() {
1829      write!(f, "\n    ")?;
1830    }
1831    for (i, elem) in self.iter().enumerate() {
1832      if i > 0 {
1833        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1834      }
1835      UpperHex::fmt(elem, f)?;
1836    }
1837    if f.alternate() {
1838      write!(f, ",\n")?;
1839    }
1840    write!(f, "]")
1841  }
1842}
1843
1844#[cfg(feature = "alloc")]
1845use alloc::vec::Vec;
1846
1847#[cfg(all(feature = "alloc", feature = "rustc_1_57"))]
1848use alloc::collections::TryReserveError;
1849
1850#[cfg(feature = "alloc")]
1851impl<A: Array> ArrayVec<A> {
1852  /// Drains all elements to a Vec, but reserves additional space
1853  /// ```
1854  /// # use tinyvec::*;
1855  /// let mut av = array_vec!([i32; 7] => 1, 2, 3);
1856  /// let v = av.drain_to_vec_and_reserve(10);
1857  /// assert_eq!(v, &[1, 2, 3]);
1858  /// assert_eq!(v.capacity(), 13);
1859  /// ```
1860  pub fn drain_to_vec_and_reserve(&mut self, n: usize) -> Vec<A::Item> {
1861    let cap = n + self.len();
1862    let mut v = Vec::with_capacity(cap);
1863    let iter = self.iter_mut().map(core::mem::take);
1864    v.extend(iter);
1865    self.set_len(0);
1866    return v;
1867  }
1868
1869  /// Tries to drain all elements to a Vec, but reserves additional space.
1870  ///
1871  /// # Errors
1872  ///
1873  /// If the allocator reports a failure, then an error is returned.
1874  ///
1875  /// ```
1876  /// # use tinyvec::*;
1877  /// let mut av = array_vec!([i32; 7] => 1, 2, 3);
1878  /// let v = av.try_drain_to_vec_and_reserve(10);
1879  /// assert!(matches!(v, Ok(_)));
1880  /// let v = v.unwrap();
1881  /// assert_eq!(v, &[1, 2, 3]);
1882  /// assert_eq!(v.capacity(), 13);
1883  /// ```
1884  #[cfg(feature = "rustc_1_57")]
1885  pub fn try_drain_to_vec_and_reserve(
1886    &mut self, n: usize,
1887  ) -> Result<Vec<A::Item>, TryReserveError> {
1888    let cap = n + self.len();
1889    let mut v = Vec::new();
1890    v.try_reserve(cap)?;
1891    let iter = self.iter_mut().map(core::mem::take);
1892    v.extend(iter);
1893    self.set_len(0);
1894    return Ok(v);
1895  }
1896
1897  /// Drains all elements to a Vec
1898  /// ```
1899  /// # use tinyvec::*;
1900  /// let mut av = array_vec!([i32; 7] => 1, 2, 3);
1901  /// let v = av.drain_to_vec();
1902  /// assert_eq!(v, &[1, 2, 3]);
1903  /// assert_eq!(v.capacity(), 3);
1904  /// ```
1905  pub fn drain_to_vec(&mut self) -> Vec<A::Item> {
1906    self.drain_to_vec_and_reserve(0)
1907  }
1908
1909  /// Tries to drain all elements to a Vec.
1910  ///
1911  /// # Errors
1912  ///
1913  /// If the allocator reports a failure, then an error is returned.
1914  ///
1915  /// ```
1916  /// # use tinyvec::*;
1917  /// let mut av = array_vec!([i32; 7] => 1, 2, 3);
1918  /// let v = av.try_drain_to_vec();
1919  /// assert!(matches!(v, Ok(_)));
1920  /// let v = v.unwrap();
1921  /// assert_eq!(v, &[1, 2, 3]);
1922  /// // Vec may reserve more than necessary in order to prevent more future allocations.
1923  /// assert!(v.capacity() >= 3);
1924  /// ```
1925  #[cfg(feature = "rustc_1_57")]
1926  pub fn try_drain_to_vec(&mut self) -> Result<Vec<A::Item>, TryReserveError> {
1927    self.try_drain_to_vec_and_reserve(0)
1928  }
1929}
1930
1931#[cfg(feature = "serde")]
1932struct ArrayVecVisitor<A: Array>(PhantomData<A>);
1933
1934#[cfg(feature = "serde")]
1935impl<'de, A: Array> Visitor<'de> for ArrayVecVisitor<A>
1936where
1937  A::Item: Deserialize<'de>,
1938{
1939  type Value = ArrayVec<A>;
1940
1941  fn expecting(
1942    &self, formatter: &mut core::fmt::Formatter,
1943  ) -> core::fmt::Result {
1944    formatter.write_str("a sequence")
1945  }
1946
1947  fn visit_seq<S>(self, mut seq: S) -> Result<Self::Value, S::Error>
1948  where
1949    S: SeqAccess<'de>,
1950  {
1951    let mut new_arrayvec: ArrayVec<A> = Default::default();
1952
1953    let mut idx = 0usize;
1954    while let Some(value) = seq.next_element()? {
1955      if new_arrayvec.len() >= new_arrayvec.capacity() {
1956        return Err(DeserializeError::invalid_length(idx, &self));
1957      }
1958      new_arrayvec.push(value);
1959      idx = idx + 1;
1960    }
1961
1962    Ok(new_arrayvec)
1963  }
1964}
1965
1966#[cfg(test)]
1967mod test {
1968  use super::*;
1969
1970  #[test]
1971  fn retain_mut_empty_vec() {
1972    let mut av: ArrayVec<[i32; 4]> = ArrayVec::new();
1973    av.retain_mut(|&mut x| x % 2 == 0);
1974    assert_eq!(av.len(), 0);
1975  }
1976
1977  #[test]
1978  fn retain_mut_all_elements() {
1979    let mut av: ArrayVec<[i32; 4]> = array_vec!([i32; 4] => 2, 4, 6, 8);
1980    av.retain_mut(|&mut x| x % 2 == 0);
1981    assert_eq!(av.len(), 4);
1982    assert_eq!(av.as_slice(), &[2, 4, 6, 8]);
1983  }
1984
1985  #[test]
1986  fn retain_mut_some_elements() {
1987    let mut av: ArrayVec<[i32; 4]> = array_vec!([i32; 4] => 1, 2, 3, 4);
1988    av.retain_mut(|&mut x| x % 2 == 0);
1989    assert_eq!(av.len(), 2);
1990    assert_eq!(av.as_slice(), &[2, 4]);
1991  }
1992
1993  #[test]
1994  fn retain_mut_no_elements() {
1995    let mut av: ArrayVec<[i32; 4]> = array_vec!([i32; 4] => 1, 3, 5, 7);
1996    av.retain_mut(|&mut x| x % 2 == 0);
1997    assert_eq!(av.len(), 0);
1998  }
1999
2000  #[test]
2001  fn retain_mut_zero_capacity() {
2002    let mut av: ArrayVec<[i32; 0]> = ArrayVec::new();
2003    av.retain_mut(|&mut x| x % 2 == 0);
2004    assert_eq!(av.len(), 0);
2005  }
2006}
tinyvec/arrayvec.rs

tinyvec/
arrayvec.rs
