mitsein/
array_vec1.rs

1//! A non-empty [`ArrayVec`].
2
3#![cfg(feature = "arrayvec")]
4#![cfg_attr(docsrs, doc(cfg(feature = "arrayvec")))]
5
6#[cfg(feature = "arbitrary")]
7use arbitrary::{Arbitrary, Unstructured};
8use arrayvec::{ArrayVec, CapacityError};
9use core::borrow::{Borrow, BorrowMut};
10use core::cmp::Ordering;
11use core::error::Error;
12use core::fmt::{self, Debug, Display, Formatter};
13use core::iter::{Skip, Take};
14use core::mem;
15use core::num::NonZeroUsize;
16use core::ops::{Deref, DerefMut, RangeBounds};
17use core::slice;
18#[cfg(feature = "schemars")]
19use {
20    alloc::borrow::Cow,
21    schemars::{JsonSchema, Schema, SchemaGenerator},
22};
23#[cfg(feature = "std")]
24use {
25    std::cmp,
26    std::io::{self, Write},
27};
28
29use crate::array1::Array1;
30use crate::iter1::{self, Extend1, FromIterator1, IntoIterator1, Iterator1};
31use crate::safety::{self, ArrayVecExt as _, OptionExt as _};
32use crate::segment::range::{self, IndexRange, Project, RangeError};
33use crate::segment::{self, Query, Segmentation, Tail};
34use crate::slice1::Slice1;
35use crate::take;
36use crate::{Cardinality, EmptyError, FromMaybeEmpty, MaybeEmpty, NonEmpty};
37
38type ItemFor<K, const N: usize> = <K as ClosedArrayVec<N>>::Item;
39
40// TODO: At time of writing, Rust does not support generic parameters in `const` expressions and
41//       operatations, so `N` is an input of this trait. When support lands, factor `N` into the
42//       trait:
43//
44//       pub trait ClosedArrayVec {
45//           ...
46//           const N: usize;
47//
48//           fn as_array_vec(&self) -> &ArrayVec<Self::Item, { Self::N }>;
49//       }
50//
51//       This factorization applies to many types and implementations below as well.
52pub trait ClosedArrayVec<const N: usize> {
53    type Item;
54
55    fn as_array_vec(&self) -> &ArrayVec<Self::Item, N>;
56}
57
58impl<T, const N: usize> ClosedArrayVec<N> for ArrayVec<T, N> {
59    type Item = T;
60
61    fn as_array_vec(&self) -> &ArrayVec<Self::Item, N> {
62        self
63    }
64}
65
66impl<T, const N: usize> Extend1<T> for ArrayVec<T, N>
67where
68    // This bound isn't necessary for memory safety here, because an `ArrayVec` with no capacity
69    // panics when any item is inserted, so `extend_non_empty` panics. However, this bound is
70    // logically appropriate and prevents the definition of a function that always panics and has a
71    // nonsense output type.
72    [T; N]: Array1,
73{
74    fn extend_non_empty<I>(mut self, items: I) -> ArrayVec1<T, N>
75    where
76        I: IntoIterator1<Item = T>,
77    {
78        self.extend(items);
79        // SAFETY: The bound `[T; N]: Array1` guarantees that capacity is non-zero, input iterator
80        //         `items` is non-empty, and `extend` either pushes one or more items or panics, so
81        //         `self` must be non-empty here.
82        unsafe { ArrayVec1::from_array_vec_unchecked(self) }
83    }
84}
85
86unsafe impl<T, const N: usize> MaybeEmpty for ArrayVec<T, N> {
87    fn cardinality(&self) -> Option<Cardinality<(), ()>> {
88        match self.len() {
89            0 => None,
90            1 => Some(Cardinality::One(())),
91            _ => Some(Cardinality::Many(())),
92        }
93    }
94}
95
96impl<T, R, const N: usize> Query<usize, R> for ArrayVec<T, N>
97where
98    R: RangeBounds<usize>,
99{
100    type Range = IndexRange;
101    type Error = RangeError<usize>;
102
103    fn segment(&mut self, range: R) -> Result<Segment<'_, Self, N>, Self::Error> {
104        let n = self.len();
105        Segment::intersected(self, n, range)
106    }
107}
108
109impl<T, const N: usize> Segmentation for ArrayVec<T, N> {
110    type Kind = Self;
111    type Target = Self;
112}
113
114impl<T, const N: usize> Tail for ArrayVec<T, N> {
115    type Range = IndexRange;
116
117    fn tail(&mut self) -> Segment<'_, Self, N> {
118        let n = self.len();
119        Segment::from_tail_range(self, n)
120    }
121
122    fn rtail(&mut self) -> Segment<'_, Self, N> {
123        let n = self.len();
124        Segment::from_rtail_range(self, n)
125    }
126}
127
128#[derive(Clone, Copy, Eq, PartialEq)]
129pub enum CardinalityError<T> {
130    Empty(EmptyError<T>),
131    // Unlike `EmptyError`, the input type parameter and payload of `CapacityError` is meant to
132    // represent an item rather than a collection, so this parameter is always the unit type here.
133    Capacity(CapacityError<()>),
134}
135
136impl<T> CardinalityError<T> {
137    pub fn empty(self) -> Option<EmptyError<T>> {
138        match self {
139            CardinalityError::Empty(error) => Some(error),
140            _ => None,
141        }
142    }
143
144    pub fn capacity(self) -> Option<CapacityError<()>> {
145        match self {
146            CardinalityError::Capacity(error) => Some(error),
147            _ => None,
148        }
149    }
150}
151
152impl<T> Debug for CardinalityError<T> {
153    fn fmt(&self, formatter: &mut Formatter) -> fmt::Result {
154        match self {
155            CardinalityError::Empty(error) => formatter.debug_tuple("Empty").field(error).finish(),
156            CardinalityError::Capacity(error) => {
157                formatter.debug_tuple("Capacity").field(error).finish()
158            },
159        }
160    }
161}
162
163impl<T> Display for CardinalityError<T> {
164    fn fmt(&self, formatter: &mut Formatter) -> fmt::Result {
165        match self {
166            CardinalityError::Empty(error) => write!(formatter, "{error}"),
167            CardinalityError::Capacity(error) => write!(formatter, "{error}"),
168        }
169    }
170}
171
172impl<T> From<CapacityError<()>> for CardinalityError<T> {
173    fn from(error: CapacityError<()>) -> Self {
174        CardinalityError::Capacity(error)
175    }
176}
177
178impl<T> From<EmptyError<T>> for CardinalityError<T> {
179    fn from(error: EmptyError<T>) -> Self {
180        CardinalityError::Empty(error)
181    }
182}
183
184impl<T> Error for CardinalityError<T> {}
185
186type TakeIfMany<'a, T, U, M, const N: usize> = take::TakeIfMany<'a, ArrayVec<T, N>, U, M>;
187
188pub type PopIfMany<'a, K, const N: usize> = TakeIfMany<'a, ItemFor<K, N>, ItemFor<K, N>, (), N>;
189
190pub type SwapPopIfMany<'a, K, const N: usize> =
191    TakeIfMany<'a, ItemFor<K, N>, Option<ItemFor<K, N>>, usize, N>;
192
193pub type RemoveIfMany<'a, K, const N: usize> =
194    TakeIfMany<'a, ItemFor<K, N>, ItemFor<K, N>, usize, N>;
195
196impl<'a, T, M, const N: usize> TakeIfMany<'a, T, T, M, N>
197where
198    [T; N]: Array1,
199{
200    pub fn or_get_only(self) -> Result<T, &'a T> {
201        self.take_or_else(|items, _| items.first())
202    }
203
204    pub fn or_replace_only(self, replacement: T) -> Result<T, T> {
205        self.or_else_replace_only(move || replacement)
206    }
207
208    pub fn or_else_replace_only<F>(self, f: F) -> Result<T, T>
209    where
210        F: FnOnce() -> T,
211    {
212        self.take_or_else(move |items, _| mem::replace(items.first_mut(), f()))
213    }
214}
215
216impl<'a, T, const N: usize> TakeIfMany<'a, T, T, usize, N>
217where
218    [T; N]: Array1,
219{
220    pub fn or_get(self) -> Result<T, &'a T> {
221        self.take_or_else(|items, index| &items[index])
222    }
223
224    pub fn or_replace(self, replacement: T) -> Result<T, T> {
225        self.or_else_replace(move || replacement)
226    }
227
228    pub fn or_else_replace<F>(self, f: F) -> Result<T, T>
229    where
230        F: FnOnce() -> T,
231    {
232        self.take_or_else(move |items, index| mem::replace(&mut items[index], f()))
233    }
234}
235
236impl<'a, T, const N: usize> TakeIfMany<'a, T, Option<T>, usize, N>
237where
238    [T; N]: Array1,
239{
240    pub fn or_get(self) -> Option<Result<T, &'a T>> {
241        self.try_take_or_else(|items, index| items.get(index))
242    }
243
244    pub fn or_replace(self, replacement: T) -> Option<Result<T, T>> {
245        self.or_else_replace(move || replacement)
246    }
247
248    pub fn or_else_replace<F>(self, f: F) -> Option<Result<T, T>>
249    where
250        F: FnOnce() -> T,
251    {
252        self.try_take_or_else(move |items, index| {
253            items.get_mut(index).map(|item| mem::replace(item, f()))
254        })
255    }
256}
257
258pub type ArrayVec1<T, const N: usize> = NonEmpty<ArrayVec<T, N>>;
259
260impl<T, const N: usize> ArrayVec1<T, N>
261where
262    [T; N]: Array1,
263{
264    /// # Safety
265    ///
266    /// `items` must be non-empty. For example, it is unsound to call this function with the
267    /// immediate output of [`ArrayVec::new()`][`ArrayVec::new`].
268    ///
269    /// [`ArrayVec::new`]: arrayvec::ArrayVec::new
270    pub unsafe fn from_array_vec_unchecked(items: ArrayVec<T, N>) -> Self {
271        unsafe { FromMaybeEmpty::from_maybe_empty_unchecked(items) }
272    }
273
274    pub fn from_one(item: T) -> Self {
275        unsafe {
276            // SAFETY: `items` must contain `item` and therefore is non-empty here.
277            ArrayVec1::from_array_vec_unchecked({
278                let mut items = ArrayVec::new();
279                // SAFETY: The bound on `[T; N]: Array1` guarantees that `items` has vacancy for a
280                //         first item here.
281                items.push_maybe_unchecked(item);
282                items
283            })
284        }
285    }
286
287    pub fn from_head_and_tail<I>(head: T, tail: I) -> Self
288    where
289        I: IntoIterator<Item = T>,
290    {
291        iter1::head_and_tail(head, tail).collect1()
292    }
293
294    pub fn from_tail_and_head<I>(tail: I, head: T) -> Self
295    where
296        I: IntoIterator<Item = T>,
297    {
298        iter1::tail_and_head(tail, head).collect1()
299    }
300
301    pub fn into_head_and_tail(mut self) -> (T, ArrayVec<T, N>) {
302        let head = self.items.remove(0);
303        (head, self.items)
304    }
305
306    pub fn into_tail_and_head(mut self) -> (ArrayVec<T, N>, T) {
307        // SAFETY: `self` must be non-empty.
308        let head = unsafe { self.items.pop().unwrap_maybe_unchecked() };
309        (self.items, head)
310    }
311
312    pub fn into_array_vec(self) -> ArrayVec<T, N> {
313        self.items
314    }
315
316    pub fn try_into_array(self) -> Result<[T; N], Self> {
317        self.items
318            .into_inner()
319            // SAFETY: `self` must be non-empty.
320            .map_err(|items| unsafe { ArrayVec1::from_array_vec_unchecked(items) })
321    }
322
323    /// # Safety
324    ///
325    /// The `ArrayVec1` must be saturated (length equals capacity), otherwise the output is
326    /// uninitialized and unsound.
327    pub unsafe fn into_array_unchecked(self) -> [T; N] {
328        unsafe { self.items.into_inner_unchecked() }
329    }
330
331    pub fn try_retain<F>(self, f: F) -> Result<Self, EmptyError<ArrayVec<T, N>>>
332    where
333        F: FnMut(&mut T) -> bool,
334    {
335        self.and_then_try(|items| items.retain(f))
336    }
337
338    pub fn retain_until_only<F>(&mut self, mut f: F) -> Option<&'_ T>
339    where
340        F: FnMut(&T) -> bool,
341    {
342        self.rtail().retain(|item| f(item));
343        if self.len().get() == 1 {
344            let last = self.last();
345            if f(last) { None } else { Some(last) }
346        }
347        else {
348            if !f(self.last()) {
349                // The last item is **not** retained and there is more than one item.
350                self.pop_if_many().or_none();
351            }
352            None
353        }
354    }
355
356    pub fn try_extend_from_slice(&mut self, items: &[T]) -> Result<(), CapacityError>
357    where
358        T: Copy,
359    {
360        self.items.try_extend_from_slice(items)
361    }
362
363    pub fn push(&mut self, item: T) {
364        self.items.push(item)
365    }
366
367    pub fn try_push(&mut self, item: T) -> Result<(), CapacityError<T>> {
368        self.items.try_push(item)
369    }
370
371    /// # Safety
372    ///
373    /// The `ArrayVec1` must have vacancy (available capacity) for the given item. Calling this
374    /// function against a saturated `ArrayVec1` is undefined behavior.
375    pub unsafe fn push_unchecked(&mut self, item: T) {
376        unsafe { self.items.push_unchecked(item) }
377    }
378
379    pub fn pop_if_many(&mut self) -> PopIfMany<'_, Self, N> {
380        // SAFETY: `with` executes this closure only if `self` contains more than one item.
381        TakeIfMany::with(self, (), |items, _| unsafe {
382            items.items.pop().unwrap_maybe_unchecked()
383        })
384    }
385
386    pub fn swap_pop_if_many(&mut self, index: usize) -> SwapPopIfMany<'_, Self, N> {
387        TakeIfMany::with(self, index, |items, index| items.items.swap_pop(index))
388    }
389
390    pub fn insert(&mut self, index: usize, item: T) {
391        self.items.insert(index, item)
392    }
393
394    pub fn try_insert(&mut self, index: usize, item: T) -> Result<(), CapacityError<T>> {
395        self.items.try_insert(index, item)
396    }
397
398    pub fn remove_if_many(&mut self, index: usize) -> RemoveIfMany<'_, Self, N> {
399        TakeIfMany::with(self, index, |items, index| items.items.remove(index))
400    }
401
402    pub fn swap_remove_if_many(&mut self, index: usize) -> RemoveIfMany<'_, Self, N> {
403        TakeIfMany::with(self, index, |items, index| items.items.swap_remove(index))
404    }
405
406    pub const fn len(&self) -> NonZeroUsize {
407        // SAFETY: `self` must be non-empty.
408        unsafe { safety::non_zero_from_usize_maybe_unchecked(self.items.len()) }
409    }
410
411    pub const fn capacity(&self) -> NonZeroUsize {
412        // SAFETY: `self` must be non-empty.
413        unsafe { safety::non_zero_from_usize_maybe_unchecked(self.items.capacity()) }
414    }
415
416    pub const fn as_array_vec(&self) -> &ArrayVec<T, N> {
417        &self.items
418    }
419
420    /// # Safety
421    ///
422    /// The [`ArrayVec`] behind the returned mutable reference **must not** be empty when the
423    /// reference is dropped. Consider the following example:
424    ///
425    /// ```rust,no_run
426    /// use mitsein::array_vec1::ArrayVec1;
427    ///
428    /// let mut xs = ArrayVec1::from([0i32, 1, 2, 3]);
429    /// // This block is unsound. The `&mut ArrayVec` is dropped in the block and so `xs` can be
430    /// // freely manipulated after the block despite violation of the non-empty guarantee.
431    /// unsafe {
432    ///     xs.as_mut_array_vec().clear();
433    /// }
434    /// let x = xs.first(); // Undefined behavior!
435    /// ```
436    pub const unsafe fn as_mut_array_vec(&mut self) -> &mut ArrayVec<T, N> {
437        &mut self.items
438    }
439
440    pub fn as_slice1(&self) -> &Slice1<T> {
441        // SAFETY: `self` must be non-empty.
442        unsafe { Slice1::from_slice_unchecked(self.items.as_slice()) }
443    }
444
445    pub fn as_mut_slice1(&mut self) -> &mut Slice1<T> {
446        // SAFETY: `self` must be non-empty.
447        unsafe { Slice1::from_mut_slice_unchecked(self.items.as_mut_slice()) }
448    }
449
450    pub fn as_ptr(&self) -> *const T {
451        self.items.as_ptr()
452    }
453
454    pub fn as_mut_ptr(&mut self) -> *mut T {
455        self.items.as_mut_ptr()
456    }
457}
458
459#[cfg(feature = "arbitrary")]
460#[cfg_attr(docsrs, doc(cfg(feature = "arbitrary")))]
461impl<'a, T, const N: usize> Arbitrary<'a> for ArrayVec1<T, N>
462where
463    [T; N]: Array1,
464    T: Arbitrary<'a>,
465{
466    fn arbitrary(unstructured: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
467        iter1::head_and_tail(
468            T::arbitrary(unstructured),
469            unstructured.arbitrary_iter()?.take(N - 1),
470        )
471        .collect1()
472    }
473
474    fn size_hint(depth: usize) -> (usize, Option<usize>) {
475        let item = T::size_hint(depth).0;
476        (item, Some(item.saturating_mul(N)))
477    }
478}
479
480impl<T, const N: usize> AsMut<[T]> for ArrayVec1<T, N> {
481    fn as_mut(&mut self) -> &mut [T] {
482        self.items.as_mut()
483    }
484}
485
486impl<T, const N: usize> AsMut<Slice1<T>> for ArrayVec1<T, N>
487where
488    [T; N]: Array1,
489{
490    fn as_mut(&mut self) -> &mut Slice1<T> {
491        self.as_mut_slice1()
492    }
493}
494
495impl<T, const N: usize> AsRef<[T]> for ArrayVec1<T, N> {
496    fn as_ref(&self) -> &[T] {
497        self.items.as_ref()
498    }
499}
500
501impl<T, const N: usize> AsRef<Slice1<T>> for ArrayVec1<T, N>
502where
503    [T; N]: Array1,
504{
505    fn as_ref(&self) -> &Slice1<T> {
506        self.as_slice1()
507    }
508}
509
510impl<T, const N: usize> Borrow<[T]> for ArrayVec1<T, N>
511where
512    [T; N]: Array1,
513{
514    fn borrow(&self) -> &[T] {
515        self.items.borrow()
516    }
517}
518
519impl<T, const N: usize> Borrow<Slice1<T>> for ArrayVec1<T, N>
520where
521    [T; N]: Array1,
522{
523    fn borrow(&self) -> &Slice1<T> {
524        self.as_slice1()
525    }
526}
527
528impl<T, const N: usize> BorrowMut<[T]> for ArrayVec1<T, N>
529where
530    [T; N]: Array1,
531{
532    fn borrow_mut(&mut self) -> &mut [T] {
533        self.items.borrow_mut()
534    }
535}
536
537impl<T, const N: usize> BorrowMut<Slice1<T>> for ArrayVec1<T, N>
538where
539    [T; N]: Array1,
540{
541    fn borrow_mut(&mut self) -> &mut Slice1<T> {
542        self.as_mut_slice1()
543    }
544}
545
546impl<T, const N: usize> ClosedArrayVec<N> for ArrayVec1<T, N>
547where
548    [T; N]: Array1,
549{
550    type Item = T;
551
552    fn as_array_vec(&self) -> &ArrayVec<Self::Item, N> {
553        self.as_ref()
554    }
555}
556
557impl<T, const N: usize> Debug for ArrayVec1<T, N>
558where
559    [T; N]: Array1,
560    T: Debug,
561{
562    fn fmt(&self, formatter: &mut Formatter<'_>) -> fmt::Result {
563        formatter.debug_list().entries(self.items.iter()).finish()
564    }
565}
566
567impl<T, const N: usize> Deref for ArrayVec1<T, N>
568where
569    [T; N]: Array1,
570{
571    type Target = Slice1<T>;
572
573    fn deref(&self) -> &Self::Target {
574        self.as_slice1()
575    }
576}
577
578impl<T, const N: usize> DerefMut for ArrayVec1<T, N>
579where
580    [T; N]: Array1,
581{
582    fn deref_mut(&mut self) -> &mut Self::Target {
583        self.as_mut_slice1()
584    }
585}
586
587impl<T, const N: usize> Extend<T> for ArrayVec1<T, N> {
588    fn extend<I>(&mut self, extension: I)
589    where
590        I: IntoIterator<Item = T>,
591    {
592        self.items.extend(extension)
593    }
594}
595
596impl<T, const N: usize> From<[T; N]> for ArrayVec1<T, N>
597where
598    [T; N]: Array1,
599{
600    fn from(items: [T; N]) -> Self {
601        // SAFETY: `items` is non-empty.
602        unsafe { ArrayVec1::from_array_vec_unchecked(ArrayVec::from(items)) }
603    }
604}
605
606impl<'a, T, const N: usize> From<&'a [T; N]> for ArrayVec1<T, N>
607where
608    [T; N]: Array1,
609    T: Copy,
610{
611    fn from(items: &'a [T; N]) -> Self {
612        // SAFETY: `items` is non-empty.
613        unsafe { ArrayVec1::from_array_vec_unchecked(items.iter().copied().collect()) }
614    }
615}
616
617impl<T, const N: usize> From<ArrayVec1<T, N>> for ArrayVec<T, N> {
618    fn from(items: ArrayVec1<T, N>) -> Self {
619        items.items
620    }
621}
622
623// NOTE: Panics on overflow.
624impl<T, const N: usize> FromIterator1<T> for ArrayVec1<T, N>
625where
626    [T; N]: Array1,
627{
628    fn from_iter1<I>(items: I) -> Self
629    where
630        I: IntoIterator1<Item = T>,
631    {
632        // SAFETY: `items` is non-empty.
633        unsafe { ArrayVec1::from_array_vec_unchecked(items.into_iter().collect()) }
634    }
635}
636
637impl<T, const N: usize> IntoIterator for ArrayVec1<T, N> {
638    type Item = T;
639    type IntoIter = arrayvec::IntoIter<T, N>;
640
641    fn into_iter(self) -> Self::IntoIter {
642        self.items.into_iter()
643    }
644}
645
646impl<'a, T, const N: usize> IntoIterator for &'a ArrayVec1<T, N> {
647    type Item = &'a T;
648    type IntoIter = slice::Iter<'a, T>;
649
650    fn into_iter(self) -> Self::IntoIter {
651        self.items.iter()
652    }
653}
654
655impl<'a, T, const N: usize> IntoIterator for &'a mut ArrayVec1<T, N> {
656    type Item = &'a mut T;
657    type IntoIter = slice::IterMut<'a, T>;
658
659    fn into_iter(self) -> Self::IntoIter {
660        self.items.iter_mut()
661    }
662}
663
664impl<T, const N: usize> IntoIterator1 for ArrayVec1<T, N>
665where
666    [T; N]: Array1,
667{
668    fn into_iter1(self) -> Iterator1<Self::IntoIter> {
669        // SAFETY: `self` must be non-empty.
670        unsafe { Iterator1::from_iter_unchecked(self.items) }
671    }
672}
673
674impl<T, const N: usize> IntoIterator1 for &'_ ArrayVec1<T, N>
675where
676    [T; N]: Array1,
677{
678    fn into_iter1(self) -> Iterator1<Self::IntoIter> {
679        self.iter1()
680    }
681}
682
683impl<T, const N: usize> IntoIterator1 for &'_ mut ArrayVec1<T, N>
684where
685    [T; N]: Array1,
686{
687    fn into_iter1(self) -> Iterator1<Self::IntoIter> {
688        self.iter1_mut()
689    }
690}
691
692impl<T, const N: usize> PartialEq<[T]> for ArrayVec1<T, N>
693where
694    [T; N]: Array1,
695    T: PartialEq<T>,
696{
697    fn eq(&self, other: &[T]) -> bool {
698        PartialEq::eq(self.as_array_vec(), other)
699    }
700}
701
702#[cfg(feature = "schemars")]
703#[cfg_attr(docsrs, doc(cfg(feature = "schemars")))]
704impl<T, const N: usize> JsonSchema for ArrayVec1<T, N>
705where
706    [T; N]: Array1,
707    T: JsonSchema,
708{
709    fn schema_name() -> Cow<'static, str> {
710        ArrayVec::<T, N>::schema_name()
711    }
712
713    fn json_schema(generator: &mut SchemaGenerator) -> Schema {
714        use crate::schemars;
715
716        schemars::json_subschema_with_non_empty_property_for::<ArrayVec<T, N>>(
717            schemars::NON_EMPTY_KEY_ARRAY,
718            generator,
719        )
720    }
721
722    fn inline_schema() -> bool {
723        ArrayVec::<T, N>::inline_schema()
724    }
725
726    fn schema_id() -> Cow<'static, str> {
727        ArrayVec::<T, N>::schema_id()
728    }
729}
730
731impl<T, R, const N: usize> Query<usize, R> for ArrayVec1<T, N>
732where
733    [T; N]: Array1,
734    R: RangeBounds<usize>,
735{
736    type Range = IndexRange;
737    type Error = RangeError<usize>;
738
739    fn segment(&mut self, range: R) -> Result<Segment<'_, Self, N>, Self::Error> {
740        let n = self.items.len();
741        Segment::intersected_strict_subset(&mut self.items, n, range)
742    }
743}
744
745impl<T, const N: usize> Segmentation for ArrayVec1<T, N>
746where
747    [T; N]: Array1,
748{
749    type Kind = Self;
750    type Target = ArrayVec<T, N>;
751}
752
753impl<T, const N: usize> Tail for ArrayVec1<T, N>
754where
755    [T; N]: Array1,
756{
757    type Range = IndexRange;
758
759    fn tail(&mut self) -> Segment<'_, Self, N> {
760        self.items.tail().rekind()
761    }
762
763    fn rtail(&mut self) -> Segment<'_, Self, N> {
764        self.items.rtail().rekind()
765    }
766}
767
768impl<'a, T, const N: usize> TryFrom<&'a [T]> for ArrayVec1<T, N>
769where
770    [T; N]: Array1,
771    T: Clone,
772{
773    type Error = CardinalityError<&'a [T]>;
774
775    fn try_from(items: &'a [T]) -> Result<Self, Self::Error> {
776        Slice1::try_from_slice(items)
777            .map_err(From::from)
778            .and_then(|items| ArrayVec1::try_from(items).map_err(From::from))
779    }
780}
781
782impl<'a, T, const N: usize> TryFrom<&'a Slice1<T>> for ArrayVec1<T, N>
783where
784    [T; N]: Array1,
785    T: Clone,
786{
787    type Error = CapacityError;
788
789    fn try_from(items: &'a Slice1<T>) -> Result<Self, Self::Error> {
790        ArrayVec::try_from(items.as_slice())
791            // SAFETY: `items` is non-empty.
792            .map(|items| unsafe { ArrayVec1::from_array_vec_unchecked(items) })
793    }
794}
795
796impl<T, const N: usize> TryFrom<ArrayVec<T, N>> for ArrayVec1<T, N>
797where
798    [T; N]: Array1,
799{
800    type Error = EmptyError<ArrayVec<T, N>>;
801
802    fn try_from(items: ArrayVec<T, N>) -> Result<Self, Self::Error> {
803        FromMaybeEmpty::try_from_maybe_empty(items)
804    }
805}
806
807#[cfg(feature = "std")]
808#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
809impl<const N: usize> Write for ArrayVec1<u8, N>
810where
811    [u8; N]: Array1,
812{
813    fn write(&mut self, buffer: &[u8]) -> io::Result<usize> {
814        let len = cmp::min(self.items.capacity() - self.items.len(), buffer.len());
815        self.items.extend(buffer.iter().take(len).copied());
816        Ok(len)
817    }
818
819    fn flush(&mut self) -> io::Result<()> {
820        Ok(())
821    }
822}
823
824pub type Segment<'a, K, const N: usize> =
825    segment::Segment<'a, K, ArrayVec<ItemFor<K, N>, N>, IndexRange>;
826
827impl<K, T, const N: usize> Segment<'_, K, N>
828where
829    K: ClosedArrayVec<N, Item = T> + Segmentation<Target = ArrayVec<T, N>>,
830{
831    pub fn truncate(&mut self, len: usize) {
832        if let Some(range) = self.range.truncate_from_end(len) {
833            self.items.drain(range);
834        }
835    }
836
837    pub fn retain<F>(&mut self, f: F)
838    where
839        F: FnMut(&mut T) -> bool,
840    {
841        self.items.retain(self.range.retain_mut_from_end(f))
842    }
843
844    pub fn insert(&mut self, index: usize, item: T) {
845        let index = self
846            .range
847            .project(index)
848            .unwrap_or_else(|_| range::panic_index_out_of_bounds());
849        self.items.insert(index, item);
850        self.range.put_from_end(1);
851    }
852
853    pub fn insert_back(&mut self, item: T) {
854        self.items.insert(self.range.end(), item);
855        self.range.put_from_end(1);
856    }
857
858    pub fn remove(&mut self, index: usize) -> T {
859        let index = self
860            .range
861            .project(index)
862            .unwrap_or_else(|_| range::panic_index_out_of_bounds());
863        let item = self.items.remove(index);
864        self.range.take_from_end(1);
865        item
866    }
867
868    pub fn remove_back(&mut self) -> Option<T> {
869        if self.range.is_empty() {
870            None
871        }
872        else {
873            let item = self.items.remove(self.range.end() - 1);
874            self.range.take_from_end(1);
875            Some(item)
876        }
877    }
878
879    pub fn swap_remove(&mut self, index: usize) -> T {
880        if self.range.is_empty() {
881            panic!("index out of bounds")
882        }
883        else {
884            let index = self
885                .range
886                .project(index)
887                .unwrap_or_else(|_| range::panic_index_out_of_bounds());
888            let swapped = self.range.end() - 1;
889            self.items.as_mut_slice().swap(index, swapped);
890            let item = self.items.remove(swapped);
891            self.range.take_from_end(1);
892            item
893        }
894    }
895
896    pub fn clear(&mut self) {
897        self.items.drain(self.range.get_and_clear_from_end());
898    }
899
900    pub fn len(&self) -> usize {
901        self.range.len()
902    }
903
904    pub fn iter(&self) -> Take<Skip<slice::Iter<'_, T>>> {
905        self.items.iter().skip(self.range.start()).take(self.len())
906    }
907
908    pub fn iter_mut(&mut self) -> Take<Skip<slice::IterMut<'_, T>>> {
909        let body = self.len();
910        self.items.iter_mut().skip(self.range.start()).take(body)
911    }
912
913    pub fn as_slice(&self) -> &[T] {
914        &self.items.as_slice()[self.range.start()..self.range.end()]
915    }
916
917    pub fn as_mut_slice(&mut self) -> &mut [T] {
918        &mut self.items.as_mut_slice()[self.range.start()..self.range.end()]
919    }
920
921    pub fn as_ptr(&self) -> *const T {
922        self.as_slice().as_ptr()
923    }
924
925    pub fn as_mut_ptr(&mut self) -> *mut T {
926        self.as_mut_slice().as_mut_ptr()
927    }
928
929    pub fn is_empty(&self) -> bool {
930        self.len() == 0
931    }
932}
933
934impl<K, T, const N: usize> AsMut<[T]> for Segment<'_, K, N>
935where
936    K: ClosedArrayVec<N, Item = T> + Segmentation<Target = ArrayVec<T, N>>,
937{
938    fn as_mut(&mut self) -> &mut [T] {
939        self.as_mut_slice()
940    }
941}
942
943impl<K, T, const N: usize> AsRef<[T]> for Segment<'_, K, N>
944where
945    K: ClosedArrayVec<N, Item = T> + Segmentation<Target = ArrayVec<T, N>>,
946{
947    fn as_ref(&self) -> &[T] {
948        self.as_slice()
949    }
950}
951
952impl<K, T, const N: usize> Borrow<[T]> for Segment<'_, K, N>
953where
954    K: ClosedArrayVec<N, Item = T> + Segmentation<Target = ArrayVec<T, N>>,
955{
956    fn borrow(&self) -> &[T] {
957        self.as_slice()
958    }
959}
960
961impl<K, T, const N: usize> BorrowMut<[T]> for Segment<'_, K, N>
962where
963    K: ClosedArrayVec<N, Item = T> + Segmentation<Target = ArrayVec<T, N>>,
964{
965    fn borrow_mut(&mut self) -> &mut [T] {
966        self.as_mut_slice()
967    }
968}
969
970impl<K, T, const N: usize> Deref for Segment<'_, K, N>
971where
972    K: ClosedArrayVec<N, Item = T> + Segmentation<Target = ArrayVec<T, N>>,
973{
974    type Target = [T];
975
976    fn deref(&self) -> &Self::Target {
977        self.as_slice()
978    }
979}
980
981impl<K, T, const N: usize> DerefMut for Segment<'_, K, N>
982where
983    K: ClosedArrayVec<N, Item = T> + Segmentation<Target = ArrayVec<T, N>>,
984{
985    fn deref_mut(&mut self) -> &mut Self::Target {
986        self.as_mut_slice()
987    }
988}
989
990impl<K, T, const N: usize> Eq for Segment<'_, K, N>
991where
992    K: ClosedArrayVec<N, Item = T> + Segmentation<Target = ArrayVec<T, N>>,
993    T: Eq,
994{
995}
996
997impl<K, T, const N: usize> Extend<T> for Segment<'_, K, N>
998where
999    K: ClosedArrayVec<N, Item = T> + Segmentation<Target = ArrayVec<T, N>>,
1000{
1001    fn extend<I>(&mut self, items: I)
1002    where
1003        I: IntoIterator<Item = T>,
1004    {
1005        let n = self.items.len();
1006        // Split off the remainder beyond the segment to avoid spurious inserts and copying. This
1007        // comes at the cost of a necessary array on the stack and bulk copy.
1008        let tail: ArrayVec<_, N> = self.items.drain(self.range.end()..).collect();
1009        self.items.extend(items);
1010        self.items.extend(tail);
1011        let n = self.items.len() - n;
1012        self.range.put_from_end(n);
1013    }
1014}
1015
1016impl<K, T, const N: usize> Ord for Segment<'_, K, N>
1017where
1018    K: ClosedArrayVec<N, Item = T> + Segmentation<Target = ArrayVec<T, N>>,
1019    T: Ord,
1020{
1021    fn cmp(&self, other: &Self) -> Ordering {
1022        self.as_slice().cmp(other.as_slice())
1023    }
1024}
1025
1026impl<K, T, const N: usize> PartialEq<Self> for Segment<'_, K, N>
1027where
1028    K: ClosedArrayVec<N, Item = T> + Segmentation<Target = ArrayVec<T, N>>,
1029    T: PartialEq<T>,
1030{
1031    fn eq(&self, other: &Self) -> bool {
1032        self.as_slice().eq(other.as_slice())
1033    }
1034}
1035
1036impl<K, T, const N: usize> PartialOrd<Self> for Segment<'_, K, N>
1037where
1038    K: ClosedArrayVec<N, Item = T> + Segmentation<Target = ArrayVec<T, N>>,
1039    T: PartialOrd<T>,
1040{
1041    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1042        self.as_slice().partial_cmp(other.as_slice())
1043    }
1044}
1045
1046impl<K, T, R, const N: usize> Query<usize, R> for Segment<'_, K, N>
1047where
1048    IndexRange: Project<R, Output = IndexRange, Error = RangeError<usize>>,
1049    K: ClosedArrayVec<N, Item = T> + Segmentation<Target = ArrayVec<T, N>>,
1050    R: RangeBounds<usize>,
1051{
1052    type Range = IndexRange;
1053    type Error = RangeError<usize>;
1054
1055    fn segment(&mut self, range: R) -> Result<Segment<'_, K, N>, Self::Error> {
1056        self.project_and_intersect(range)
1057    }
1058}
1059
1060impl<K, T, const N: usize> Tail for Segment<'_, K, N>
1061where
1062    K: ClosedArrayVec<N, Item = T> + Segmentation<Target = ArrayVec<T, N>>,
1063{
1064    type Range = IndexRange;
1065
1066    fn tail(&mut self) -> Segment<'_, K, N> {
1067        self.project_tail_range()
1068    }
1069
1070    fn rtail(&mut self) -> Segment<'_, K, N> {
1071        let n = self.len();
1072        self.project_rtail_range(n)
1073    }
1074}
1075
1076#[cfg(test)]
1077pub mod harness {
1078    use rstest::fixture;
1079
1080    use crate::array_vec1::ArrayVec1;
1081    use crate::iter1::{self, FromIterator1};
1082
1083    pub const CAPACITY: usize = 10;
1084
1085    #[fixture]
1086    pub fn xs1(#[default(4)] end: u8) -> ArrayVec1<u8, CAPACITY> {
1087        ArrayVec1::from_iter1(iter1::harness::xs1(end))
1088    }
1089}
1090
1091#[cfg(test)]
1092mod tests {
1093    use rstest::rstest;
1094    #[cfg(feature = "serde")]
1095    use {arrayvec::ArrayVec, serde_test::Token};
1096
1097    use crate::array_vec1::ArrayVec1;
1098    use crate::array_vec1::harness::{self, CAPACITY};
1099    #[cfg(feature = "schemars")]
1100    use crate::schemars;
1101    use crate::segment::Tail;
1102    #[cfg(feature = "serde")]
1103    use crate::{
1104        array_vec1::harness::xs1,
1105        serde::{self, harness::sequence},
1106    };
1107
1108    #[rstest]
1109    #[case::empty_tail(harness::xs1(0))]
1110    #[case::one_tail(harness::xs1(1))]
1111    #[case::many_tail(harness::xs1(2))]
1112    fn clear_tail_of_array_vec1_then_array_vec1_eq_head(#[case] mut xs1: ArrayVec1<u8, CAPACITY>) {
1113        xs1.tail().clear();
1114        assert_eq!(xs1.as_slice(), &[0]);
1115    }
1116
1117    #[rstest]
1118    #[case::empty_rtail(harness::xs1(0))]
1119    #[case::one_rtail(harness::xs1(1))]
1120    #[case::many_rtail(harness::xs1(2))]
1121    fn clear_rtail_of_array_vec1_then_array_vec1_eq_tail(#[case] mut xs1: ArrayVec1<u8, CAPACITY>) {
1122        let tail = *xs1.last();
1123        xs1.rtail().clear();
1124        assert_eq!(xs1.as_slice(), &[tail]);
1125    }
1126
1127    #[rstest]
1128    #[case::empty_tail(harness::xs1(0))]
1129    #[case::one_tail_empty_rtail(harness::xs1(1))]
1130    #[case::many_tail_one_rtail(harness::xs1(2))]
1131    #[case::many_tail_many_rtail(harness::xs1(3))]
1132    fn clear_tail_rtail_of_array_vec1_then_array_vec1_eq_head_and_tail(
1133        #[case] mut xs1: ArrayVec1<u8, CAPACITY>,
1134    ) {
1135        let n = xs1.len().get();
1136        let head_and_tail = [0, *xs1.last()];
1137        xs1.tail().rtail().clear();
1138        assert_eq!(
1139            xs1.as_slice(),
1140            if n > 1 {
1141                &head_and_tail[..]
1142            }
1143            else {
1144                &head_and_tail[..1]
1145            }
1146        );
1147    }
1148
1149    #[cfg(feature = "schemars")]
1150    #[rstest]
1151    fn array_vec1_json_schema_has_non_empty_property() {
1152        schemars::harness::assert_json_schema_has_non_empty_property::<ArrayVec1<u8, 5>>(
1153            schemars::NON_EMPTY_KEY_ARRAY,
1154        );
1155    }
1156
1157    #[cfg(feature = "serde")]
1158    #[rstest]
1159    fn de_serialize_array_vec1_into_and_from_tokens_eq(
1160        xs1: ArrayVec1<u8, CAPACITY>,
1161        sequence: impl Iterator<Item = Token>,
1162    ) {
1163        serde::harness::assert_into_and_from_tokens_eq::<_, ArrayVec<_, 16>>(xs1, sequence)
1164    }
1165
1166    #[cfg(feature = "serde")]
1167    #[rstest]
1168    fn deserialize_array_vec1_from_empty_tokens_then_empty_error(
1169        #[with(0)] sequence: impl Iterator<Item = Token>,
1170    ) {
1171        serde::harness::assert_deserialize_error_eq_empty_error::<ArrayVec1<u8, 1>, ArrayVec<_, 16>>(
1172            sequence,
1173        )
1174    }
1175}
mitsein/array_vec1.rs

mitsein/
array_vec1.rs
