fastvec/auto_vec.rs
1use alloc::{boxed::Box, vec::Vec};
2use core::{fmt, iter::FusedIterator, ptr};
3
4use crate::StackVec;
5
6#[derive(Clone, Debug)]
7pub enum InnerVec<T, const N: usize> {
8 Stack(StackVec<T, N>),
9 Heap(Vec<T>),
10}
11
12#[derive(Clone, Copy, Debug)]
13pub enum InnerVecRef<'a, T, const N: usize> {
14 Stack(&'a StackVec<T, N>),
15 Heap(&'a Vec<T>),
16}
17
18#[derive(Debug)]
19pub enum InnerVecMut<'a, T, const N: usize> {
20 Stack(&'a mut StackVec<T, N>),
21 Heap(&'a mut Vec<T>),
22}
23
24/// Stack-first vector that moves to the heap when capacity is exceeded.
25///
26/// Useful when data is usually small; avoids heap allocations in the common case.
27/// API mirrors [`Vec`]. Internally stores either a [`StackVec`] or a [`Vec`].
28///
29/// # Example
30///
31/// ```
32/// use fastvec::AutoVec;
33/// use core::iter::Extend;
34///
35/// // Allocate uninitialized space for 5 elements on the stack
36/// let mut vec: AutoVec<&'static str, 5> = AutoVec::new();
37///
38/// assert_eq!(vec.len(), 0);
39/// assert_eq!(vec.capacity(), 5);
40///
41/// // Use like `Vec`; stays on stack while within capacity
42/// vec.push("Hello");
43/// vec.push("world");
44///
45/// assert_eq!(vec, ["Hello", "world"]);
46///
47/// // Exceeding capacity automatically moves data to the heap
48/// vec.extend(["2025", "12", "14", "1:15"]);
49/// assert!(!vec.in_stack());
50/// assert_eq!(vec, ["Hello", "world", "2025", "12", "14", "1:15"]);
51///
52/// // Force move to stack (truncates if needed)
53/// vec.force_to_stack();
54/// assert!(vec.in_stack());
55/// assert_eq!(vec, ["Hello", "world", "2025", "12", "14"]);
56///
57/// // Convert to `Vec` if needed
58/// let vec: Vec<&'static str> = vec.into_vec();
59/// ```
60#[derive(Clone)]
61#[repr(transparent)]
62pub struct AutoVec<T, const N: usize>(InnerVec<T, N>);
63
64impl<T, const N: usize> From<Vec<T>> for AutoVec<T, N> {
65 #[inline]
66 fn from(value: Vec<T>) -> Self {
67 Self(InnerVec::Heap(value))
68 }
69}
70
71impl<T, const N: usize> From<StackVec<T, N>> for AutoVec<T, N> {
72 #[inline]
73 fn from(value: StackVec<T, N>) -> Self {
74 Self(InnerVec::Stack(value))
75 }
76}
77
78/// Creates a [`AutoVec`] containing the arguments.
79///
80/// The syntax is similar to [`vec!`](https://doc.rust-lang.org/std/macro.vec.html) .
81///
82/// You must explicitly specify the container capacity.
83/// If the input elements exceed the capacity, heap storage will be used instead.
84///
85/// When called with no arguments, it can be computed at compile time.
86/// Otherwise, due to the possibility of creating a [`Vec`], it will be delayed until runtime.
87///
88/// # Examples
89///
90/// ```
91/// # use fastvec::{autovec, AutoVec};
92/// let vec: AutoVec<String, 10> = autovec![];
93/// let vec: AutoVec<i64, 10> = autovec![1; 5]; // Need to support Clone.
94/// let vec: AutoVec<_, 10> = autovec![1, 2, 3, 4];
95/// ```
96#[macro_export]
97macro_rules! autovec {
98 [] => { $crate::AutoVec::new() };
99 [$elem:expr; $n:expr] => { $crate::AutoVec::from_elem($elem, $n) };
100 [$($item:expr),+ $(,)?] => { $crate::AutoVec::from_buf([ $($item),+ ]) };
101}
102
103impl<T, const N: usize> AutoVec<T, N> {
104 /// Constructs a new, empty `AutoVec` on the stack with the specified capacity.
105 ///
106 /// The capacity must be provided at compile time via the const generic parameter.
107 ///
108 /// Note that the stack memory is allocated when the `AutoVec` is instantiated.
109 /// The capacity should not be too large to avoid stack overflow.
110 ///
111 /// # Examples
112 ///
113 /// ```
114 /// # use fastvec::{AutoVec, autovec};
115 /// let vec: AutoVec<i32, 8> = AutoVec::new();
116 ///
117 /// // eq to this
118 /// let vec: AutoVec<i32, 8> = autovec![];
119 /// ```
120 #[inline]
121 pub const fn new() -> Self {
122 Self(InnerVec::Stack(StackVec::new()))
123 }
124
125 /// Modify the stack capacity of the container.
126 ///
127 /// This function does not move heap data to the stack.
128 /// But it is possible to move stack data to the heap (if the capacity is insufficient).
129 ///
130 /// Unlike [`StackVec::force_cast`], this function will not delete data.
131 ///
132 /// # Examples
133 ///
134 /// ```
135 /// # use fastvec::{AutoVec, autovec};
136 /// let vec: AutoVec<_, 5> = autovec![1, 2, 3];
137 ///
138 /// let vec: AutoVec<_, 8> = vec.force_cast();
139 /// assert!(vec.in_stack());
140 ///
141 /// let vec: AutoVec<_, 2> = vec.force_cast();
142 /// assert!(!vec.in_stack());
143 /// assert_eq!(vec, [1, 2, 3]);
144 /// ```
145 #[inline]
146 pub fn force_cast<const P: usize>(self) -> AutoVec<T, P> {
147 match self.0 {
148 InnerVec::Stack(mut stack_vec) => {
149 let len = stack_vec.len();
150 let mut res = <AutoVec<T, P>>::with_capacity(len);
151 unsafe {
152 ptr::copy_nonoverlapping(stack_vec.as_ptr(), res.as_mut_ptr(), len);
153 res.set_len(len);
154 stack_vec.set_len(0);
155 }
156 res
157 }
158 InnerVec::Heap(items) => AutoVec::<T, P>(InnerVec::Heap(items)),
159 }
160 }
161
162 /// Return `true` if the data is stored on stack.
163 ///
164 /// # Example
165 ///
166 /// ```
167 /// # use fastvec::{AutoVec, autovec};
168 /// let mut vec: AutoVec<i32, 8> = autovec![];
169 ///
170 /// assert!(vec.in_stack());
171 ///
172 /// vec.reserve(10);
173 /// assert!(!vec.in_stack());
174 /// ```
175 #[inline(always)]
176 pub const fn in_stack(&self) -> bool {
177 match &self.0 {
178 InnerVec::Stack(_) => true,
179 InnerVec::Heap(_) => false,
180 }
181 }
182
183 /// Creates an `AutoVec` directly from a pointer, a length, and a capacity.
184 ///
185 /// This function will create a [`Vec`] internally and store it as heap data.
186 /// (Stack storage is bypassed to ensure maximum safety.)
187 ///
188 /// # Safety
189 ///
190 /// See more information in [`Vec::from_raw_parts`].
191 pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self {
192 // Safety: See [`Vec::from_raw_parts`].
193 unsafe { Vec::from_raw_parts(ptr, length, capacity).into() }
194 }
195
196 /// Creates an `AutoVec` from an array.
197 ///
198 /// If the array length is greater than `N`, heap storage will be used.
199 ///
200 /// # Examples
201 /// ```
202 /// # use fastvec::AutoVec;
203 /// let vec: AutoVec<i32, 5> = AutoVec::from_buf([1, 2, 3]);
204 /// assert_eq!(vec.len(), 3);
205 /// assert!(vec.in_stack());
206 ///
207 /// let vec: AutoVec<i32, 3> = AutoVec::from_buf([1, 2, 3, 4, 5]);
208 /// assert_eq!(vec, [1, 2, 3, 4, 5]);
209 /// assert!(!vec.in_stack());
210 /// ```
211 #[inline]
212 pub fn from_buf<const P: usize>(arr: [T; P]) -> Self {
213 let mut vec;
214
215 if P <= N {
216 vec = Self(InnerVec::Stack(StackVec::new()));
217 } else {
218 vec = Self(InnerVec::Heap(Vec::with_capacity(P)));
219 }
220
221 unsafe {
222 ptr::copy_nonoverlapping(arr.as_ptr(), vec.as_mut_ptr(), P);
223 vec.set_len(P);
224 }
225 core::mem::forget(arr);
226
227 vec
228 }
229
230 /// Constructs a new, empty `AutoVec` with at least the specified capacity.
231 ///
232 /// If the specified capacity is less than or equal to `N`, this is equivalent to [`new`](AutoVec::new),
233 /// and no heap memory will be allocated.
234 ///
235 /// # Examples
236 ///
237 /// ```
238 /// # use fastvec::{AutoVec, autovec};
239 /// let mut data_num = 4;
240 ///
241 /// let vec: AutoVec<i32, 5> = AutoVec::with_capacity(data_num);
242 /// assert!(vec.in_stack());
243 ///
244 /// data_num = 10;
245 /// let vec: AutoVec<i32, 5> = AutoVec::with_capacity(data_num);
246 /// assert!(!vec.in_stack());
247 /// ```
248 #[inline]
249 pub fn with_capacity(capacity: usize) -> Self {
250 if capacity > N {
251 Self(InnerVec::Heap(Vec::with_capacity(capacity)))
252 } else {
253 Self(InnerVec::Stack(StackVec::new()))
254 }
255 }
256
257 /// Forcefully move data to the stack and return mutable reference.
258 ///
259 /// If the length exceeds the capacity, `truncate` will be called.
260 ///
261 /// If the data is already in the stack, it won't do anything.
262 #[inline]
263 pub fn force_to_stack(&mut self) -> &mut StackVec<T, N> {
264 if let InnerVec::Heap(vec) = &mut self.0 {
265 self.0 = InnerVec::Stack(StackVec::from_vec_truncate(vec));
266 }
267 match &mut self.0 {
268 InnerVec::Stack(vec) => vec,
269 _ => unreachable!(),
270 }
271 }
272
273 /// Forcefully move data to the heap and return mutable reference.
274 ///
275 /// The allocated memory is precise.
276 /// If space needs to be reserved, consider using [`reserve`](AutoVec::reserve).
277 ///
278 /// If the data is already in the heap, it won't do anything.
279 #[inline]
280 pub fn force_to_heap(&mut self) -> &mut Vec<T> {
281 if let InnerVec::Stack(vec) = &mut self.0 {
282 self.0 = InnerVec::Heap(vec.into_vec());
283 }
284 match &mut self.0 {
285 InnerVec::Heap(vec) => vec,
286 _ => unreachable!(),
287 }
288 }
289
290 /// Reserves capacity for at least additional more elements to be inserted in the given `AutoVec`.
291 ///
292 /// The collection may reserve more space to speculatively avoid frequent reallocations.
293 ///
294 /// - If the target capacity <= N, this will move the data to the stack.
295 /// - If the target capacity > N, this will move the data to the heap.
296 ///
297 /// # Examples
298 ///
299 /// ```
300 /// # use fastvec::{AutoVec, autovec};
301 /// let mut vec: AutoVec<i32, 8> = autovec![];
302 /// vec.reserve(5);
303 /// assert!(vec.in_stack());
304 ///
305 /// vec.reserve(10);
306 /// assert!(!vec.in_stack());
307 /// assert!(vec.capacity() >= 10);
308 /// ```
309 pub fn reserve(&mut self, additional: usize) {
310 let capacity = self.len() + additional;
311 if capacity > N {
312 match &mut self.0 {
313 InnerVec::Stack(vec) => {
314 // SAFETY: capacity >= len
315 self.0 =
316 InnerVec::Heap(unsafe { vec.into_vec_with_capacity_uncheck(capacity) });
317 }
318 InnerVec::Heap(vec) => vec.reserve(additional),
319 }
320 } else {
321 match &mut self.0 {
322 InnerVec::Stack(_) => return,
323 InnerVec::Heap(vec) => {
324 // SAFETY: capacity >= len
325 self.0 = InnerVec::Stack(unsafe { StackVec::from_vec_uncheck(vec) });
326 }
327 }
328 }
329 }
330
331 /// Reserves capacity for at least additional more elements to be inserted in the given `AutoVec`.
332 ///
333 /// - If the target capacity <= N, this will move the data to the stack.
334 /// - If the target capacity > N, this will move the data to the heap.
335 ///
336 /// # Examples
337 ///
338 /// ```
339 /// # use fastvec::{AutoVec, autovec};
340 /// let mut vec: AutoVec<i32, 8> = autovec![];
341 /// vec.reserve_exact(5);
342 /// assert!(vec.in_stack());
343 ///
344 /// vec.reserve_exact(10);
345 /// assert!(!vec.in_stack());
346 /// assert_eq!(vec.capacity(), 10);
347 /// ```
348 pub fn reserve_exact(&mut self, additional: usize) {
349 let capacity = self.len() + additional;
350 if capacity > N {
351 match &mut self.0 {
352 InnerVec::Stack(vec) => {
353 // SAFETY: Ensure that the capacity is greater than the length.
354 self.0 =
355 InnerVec::Heap(unsafe { vec.into_vec_with_capacity_uncheck(capacity) });
356 }
357 InnerVec::Heap(vec) => vec.reserve_exact(additional),
358 }
359 } else {
360 match &mut self.0 {
361 InnerVec::Stack(_) => return,
362 InnerVec::Heap(vec) => {
363 // SAFETY: Ensure that the capacity is greater than the length.
364 self.0 = InnerVec::Stack(unsafe { StackVec::from_vec_uncheck(vec) });
365 }
366 }
367 }
368 }
369
370 /// Shrinks the capacity of the vector as much as possible.
371 ///
372 /// If the data is already in the stack, it won't do anything.
373 ///
374 /// If the capacity is sufficient, this function will move the data to stack.
375 pub fn shrink_to_fit(&mut self) {
376 match &mut self.0 {
377 InnerVec::Heap(vec) => {
378 if vec.len() > N {
379 vec.shrink_to_fit();
380 } else {
381 // SAFETY: capacity >= len
382 self.0 = InnerVec::Stack(unsafe { StackVec::from_vec_uncheck(vec) });
383 }
384 }
385 InnerVec::Stack(_) => return,
386 }
387 }
388
389 /// Shrinks the capacity of the vector with a lower bound.
390 ///
391 /// If the current capacity is less than the lower limit, it's eq to `shrink_to_fit`.
392 ///
393 /// If the data is already in the stack, it won't do anything.
394 ///
395 /// If the capacity is sufficient, this function will move the data to stack.
396 pub fn shrink_to(&mut self, min_capacity: usize) {
397 match &mut self.0 {
398 InnerVec::Heap(vec) => {
399 if min_capacity.max(vec.len()) > N {
400 vec.shrink_to_fit();
401 } else {
402 // SAFETY: capacity >= len
403 self.0 = InnerVec::Stack(unsafe { StackVec::from_vec_uncheck(vec) });
404 }
405 }
406 InnerVec::Stack(_) => return,
407 }
408 }
409
410 /// Returns a raw pointer to the buffer, or a dangling pointer
411 /// valid for zero-sized reads if `T` is a zero-sized type.
412 #[inline]
413 pub const fn as_ptr(&self) -> *const T {
414 match &self.0 {
415 InnerVec::Stack(vec) => vec.as_ptr(),
416 InnerVec::Heap(vec) => vec.as_ptr(),
417 }
418 }
419
420 /// Returns a raw mutable pointer to the buffer, or a dangling pointer
421 /// valid for zero-sized reads if `T` is a zero-sized type.
422 #[inline]
423 pub const fn as_mut_ptr(&mut self) -> *mut T {
424 match &mut self.0 {
425 InnerVec::Stack(vec) => vec.as_mut_ptr(),
426 InnerVec::Heap(vec) => vec.as_mut_ptr(),
427 }
428 }
429
430 /// Returns the number of elements in the vector, also referred to as its ‘length’.
431 ///
432 /// # Examples
433 ///
434 /// ```
435 /// # use fastvec::{AutoVec, autovec};
436 /// let mut vec: AutoVec<i32, 8> = autovec![1, 2, 3];
437 /// assert_eq!(vec.len(), 3);
438 /// ```
439 #[inline]
440 pub const fn len(&self) -> usize {
441 match &self.0 {
442 InnerVec::Stack(vec) => vec.len(),
443 InnerVec::Heap(vec) => vec.len(),
444 }
445 }
446
447 /// Forces the length of the vector to `new_len`.
448 ///
449 /// # Safety
450 /// - `new_len` needs to be less than or equal to capacity `N`.
451 /// - If the length is increased, it is necessary to ensure that the new element is initialized correctly.
452 /// - If the length is reduced, it is necessary to ensure that the reduced elements can be dropped normally.
453 ///
454 /// See [`Vec::set_len`] and [`StackVec::set_len`] .
455 #[inline]
456 pub unsafe fn set_len(&mut self, new_len: usize) {
457 // SAFETY: See function docs.
458 unsafe {
459 match &mut self.0 {
460 InnerVec::Stack(vec) => vec.set_len(new_len),
461 InnerVec::Heap(vec) => vec.set_len(new_len),
462 }
463 }
464 }
465
466 /// Returns true if the vector contains no elements.
467 ///
468 /// # Examples
469 ///
470 /// ```
471 /// # use fastvec::{AutoVec, autovec};
472 /// let mut vec: AutoVec<i32, 8> = autovec![];
473 /// assert!(vec.is_empty());
474 ///
475 /// vec.push(1);
476 /// assert!(!vec.is_empty());
477 /// ```
478 #[inline]
479 pub const fn is_empty(&self) -> bool {
480 match &self.0 {
481 InnerVec::Stack(vec) => vec.is_empty(),
482 InnerVec::Heap(vec) => vec.is_empty(),
483 }
484 }
485
486 /// Returns the total number of elements the vector can hold without reallocating.
487 ///
488 /// For [`StackVec`], this is always equal to `N` .
489 ///
490 /// # Examples
491 ///
492 /// ```
493 /// # use fastvec::{AutoVec, autovec};
494 /// let mut vec: AutoVec<i32, 3> = autovec![];
495 /// assert_eq!(vec.capacity(), 3);
496 ///
497 /// vec.extend([1, 2, 3, 4]);
498 /// assert!(vec.capacity() >= 4);
499 /// ```
500 #[inline]
501 pub const fn capacity(&self) -> usize {
502 match &self.0 {
503 InnerVec::Stack(vec) => vec.capacity(),
504 InnerVec::Heap(vec) => vec.capacity(),
505 }
506 }
507
508 /// Convert [`AutoVec`] to [`Vec`].
509 ///
510 /// If the data is in the stack, the exact memory will be allocated.
511 /// If the data is in the heap, will not reallocate memory.
512 ///
513 /// Therefore, this function is efficient, but the returned [`Vec`] may not be tight.
514 ///
515 /// # Examples
516 ///
517 /// ```
518 /// # use fastvec::{AutoVec, autovec};
519 /// let vec: AutoVec<i32, 3> = autovec![1, 2];
520 /// assert!(vec.in_stack());
521 /// let vec: Vec<_> = vec.into_vec();
522 /// assert_eq!(vec, [1, 2]);
523 /// assert!(vec.capacity() == 2);
524 ///
525 /// let vec: AutoVec<i32, 3> = autovec![1, 2, 3, 4, 5];
526 /// assert!(!vec.in_stack());
527 /// let vec: Vec<_> = vec.into_vec();
528 /// assert_eq!(vec, [1, 2, 3, 4, 5]);
529 /// assert!(vec.capacity() >= 5);
530 /// ```
531 #[inline]
532 pub fn into_vec(self) -> Vec<T> {
533 match self.0 {
534 InnerVec::Stack(mut vec) => vec.into_vec(),
535 InnerVec::Heap(vec) => vec,
536 }
537 }
538
539 /// Convert [`AutoVec`] to [`Vec`].
540 ///
541 /// If the data is in the stack, the exact memory will be allocated.
542 /// If the data is in the heap, [`Vec::shrink_to_fit`] will be called.
543 #[inline]
544 pub fn shrink_into_vec(self) -> Vec<T> {
545 match self.0 {
546 InnerVec::Stack(mut vec) => vec.into_vec(),
547 InnerVec::Heap(mut vec) => {
548 vec.shrink_to_fit();
549 vec
550 }
551 }
552 }
553
554 /// Forcefully move data to the stack and return mutable reference.
555 ///
556 /// If the length exceeds the capacity, [`truncate`](StackVec::truncate) will be called.
557 ///
558 /// If the data is already in the stack, it won't do anything.
559 ///
560 /// # Examples
561 ///
562 /// ```
563 /// # use fastvec::{AutoVec, autovec};
564 /// let vec: AutoVec<i32, 3> = autovec![1, 2];
565 /// let vec = vec.truncate_into_stack();
566 /// assert_eq!(vec, [1, 2]);
567 ///
568 /// let vec: AutoVec<i32, 3> = autovec![1, 2, 3, 4, 5];
569 /// let vec = vec.truncate_into_stack();
570 /// assert_eq!(vec, [1, 2, 3]);
571 /// ```
572 #[inline]
573 pub fn truncate_into_stack(mut self) -> StackVec<T, N> {
574 if let InnerVec::Heap(vec) = &mut self.0 {
575 self.0 = InnerVec::Stack(StackVec::from_vec_truncate(vec));
576 }
577 match self.0 {
578 InnerVec::Stack(vec) => vec,
579 _ => unreachable!(),
580 }
581 }
582
583 /// Convert to internal container.
584 ///
585 /// # Examples
586 ///
587 /// ```
588 /// # use fastvec::{AutoVec, autovec, auto_vec::InnerVec};
589 /// let vec: AutoVec<i32, 3> = autovec![1, 2];
590 ///
591 /// match vec.into_inner() {
592 /// InnerVec::Stack(stack_vec) => { /* ... */ },
593 /// InnerVec::Heap(vec) => { /* ... */ },
594 /// }
595 /// ```
596 #[inline(always)]
597 pub fn into_inner(self) -> InnerVec<T, N> {
598 self.0
599 }
600
601 /// Return the reference of inner vector.
602 ///
603 /// # Examples
604 ///
605 /// ```
606 /// # use fastvec::{AutoVec, autovec, auto_vec::InnerVecRef};
607 /// let vec: AutoVec<i32, 3> = autovec![1, 2];
608 ///
609 /// match vec.inner_ref() {
610 /// InnerVecRef::Stack(stack_vec) => { /* ... */ },
611 /// InnerVecRef::Heap(vec) => { /* ... */ },
612 /// }
613 /// ```
614 #[inline(always)]
615 pub fn inner_ref(&self) -> InnerVecRef<'_, T, N> {
616 match &self.0 {
617 InnerVec::Stack(stack_vec) => InnerVecRef::Stack(stack_vec),
618 InnerVec::Heap(vec) => InnerVecRef::Heap(vec),
619 }
620 }
621
622 /// Return the mutable reference of inner vector.
623 ///
624 /// # Examples
625 ///
626 /// ```
627 /// # use fastvec::{AutoVec, autovec, auto_vec::InnerVecMut};
628 /// let mut vec: AutoVec<i32, 3> = autovec![1, 2];
629 ///
630 /// match vec.inner_mut() {
631 /// InnerVecMut::Stack(stack_vec) => { /* ... */ },
632 /// InnerVecMut::Heap(vec) => { /* ... */ },
633 /// }
634 /// ```
635 #[inline(always)]
636 pub fn inner_mut(&mut self) -> InnerVecMut<'_, T, N> {
637 match &mut self.0 {
638 InnerVec::Stack(stack_vec) => InnerVecMut::Stack(stack_vec),
639 InnerVec::Heap(vec) => InnerVecMut::Heap(vec),
640 }
641 }
642
643 /// Converts the [`AutoVec`] into [`Box<[T]>`](Box).
644 ///
645 /// This function is eq to [`AutoVec::shrink_into_vec`] + [`Vec::into_boxed_slice`] .
646 #[inline]
647 pub fn into_boxed_slice(self) -> Box<[T]> {
648 match self.0 {
649 InnerVec::Stack(mut vec) => vec.into_boxed_slice(),
650 InnerVec::Heap(vec) => vec.into_boxed_slice(),
651 }
652 }
653
654 /// Shortens the vector, keeping the first `len` elements and dropping the rest.
655 ///
656 /// If `len` is greater or equal to the vector’s current length, this has no effect.
657 ///
658 /// Note that this will not modify the capacity, so it will not move data.
659 ///
660 /// # Examples
661 ///
662 /// ```
663 /// # use fastvec::{AutoVec, autovec};
664 /// let mut vec: AutoVec<i32, 5> = autovec![1, 2, 3, 4];
665 /// vec.truncate(2);
666 /// assert_eq!(vec, [1, 2]);
667 /// assert_eq!(vec.capacity(), 5);
668 /// ```
669 #[inline]
670 pub fn truncate(&mut self, len: usize) {
671 match &mut self.0 {
672 InnerVec::Stack(vec) => vec.truncate(len),
673 InnerVec::Heap(vec) => vec.truncate(len),
674 }
675 }
676
677 /// Extracts a slice containing the entire vector.
678 #[inline]
679 pub const fn as_slice(&self) -> &[T] {
680 match &self.0 {
681 InnerVec::Stack(vec) => vec.as_slice(),
682 InnerVec::Heap(vec) => vec.as_slice(),
683 }
684 }
685
686 /// Extracts a mutable slice of the entire vector.
687 #[inline]
688 pub const fn as_mut_slice(&mut self) -> &mut [T] {
689 match &mut self.0 {
690 InnerVec::Stack(vec) => vec.as_mut_slice(),
691 InnerVec::Heap(vec) => vec.as_mut_slice(),
692 }
693 }
694
695 /// Removes an element from the vector and returns it.
696 ///
697 /// The removed element is replaced by the last element of the vector.
698 ///
699 /// This function does not affect the position (stack/heap) of the data.
700 ///
701 /// # Panics
702 ///
703 /// Panics if `index` is out of bounds.
704 ///
705 /// # Examples
706 ///
707 /// ```
708 /// # use fastvec::{AutoVec, autovec};
709 /// let mut vec: AutoVec<i32, 5> = autovec![0, 1, 2, 3];
710 /// let x = vec.swap_remove(1);
711 /// assert_eq!(x, 1);
712 /// assert_eq!(vec, [0, 3, 2]);
713 /// ```
714 pub fn swap_remove(&mut self, index: usize) -> T {
715 match &mut self.0 {
716 InnerVec::Stack(vec) => vec.swap_remove(index),
717 InnerVec::Heap(vec) => vec.swap_remove(index),
718 }
719 }
720
721 /// Inserts an element at position `index` within the vector, shifting all elements after it to the right.
722 ///
723 /// If the heap is insufficient, it will switch to [`Vec`] and reserve some additional memory.
724 ///
725 /// # Panics
726 /// Panics if `index > len`.
727 ///
728 /// # Examples
729 /// ```
730 /// # use fastvec::{AutoVec, autovec};
731 /// let mut vec: AutoVec<_, 4> = autovec!['a', 'b', 'c'];
732 ///
733 /// vec.insert(1, 'd');
734 /// assert_eq!(vec, ['a', 'd', 'b', 'c']);
735 /// assert!(vec.in_stack());
736 ///
737 /// vec.insert(4, 'e');
738 /// assert_eq!(vec, ['a', 'd', 'b', 'c', 'e']);
739 /// assert!(!vec.in_stack());
740 /// ```
741 #[inline]
742 pub fn insert(&mut self, index: usize, element: T) {
743 match &mut self.0 {
744 InnerVec::Stack(vec) => {
745 assert!(index <= vec.len(), "insertion index should be <= len");
746 if vec.len() < N {
747 // SAFETY: index <= len && len < N
748 unsafe {
749 vec.insert_uncheck(index, element);
750 }
751 } else {
752 let mut new_vec: Vec<T> = Vec::with_capacity(N + { N >> 1 } + 4);
753 let dst_ptr = new_vec.as_mut_ptr();
754 let src_ptr = vec.as_ptr();
755 // SAFETY: enough capacity and valid data.
756 unsafe {
757 ptr::copy_nonoverlapping(src_ptr, dst_ptr, index);
758 ptr::write(dst_ptr.add(index), element);
759 ptr::copy_nonoverlapping(
760 src_ptr.add(index),
761 dst_ptr.add(index + 1),
762 N - index,
763 );
764 vec.set_len(0);
765 new_vec.set_len(N + 1);
766 }
767 self.0 = InnerVec::Heap(new_vec);
768 }
769 }
770 InnerVec::Heap(vec) => vec.insert(index, element),
771 }
772 }
773
774 /// Removes and returns the element at position index within the vector, shifting all elements after it to the left.
775 ///
776 /// Note: Because this shifts over the remaining elements, it has a worst-case performance of O(n).
777 /// If you don’t need the order of elements to be preserved, use [`swap_remove`](AutoVec::swap_remove) instead.
778 ///
779 /// This function does not affect the position (stack/heap) of the data.
780 ///
781 /// # Panics
782 /// Panics if `index` is out of bounds.
783 ///
784 /// # Examples
785 /// ```
786 /// # use fastvec::{AutoVec, autovec};
787 /// let mut v: AutoVec<_, 4> = autovec!['a', 'b', 'c'];
788 /// assert_eq!(v.remove(1), 'b');
789 /// assert_eq!(v, ['a', 'c']);
790 /// ```
791 pub fn remove(&mut self, index: usize) -> T {
792 match &mut self.0 {
793 InnerVec::Stack(vec) => vec.remove(index),
794 InnerVec::Heap(vec) => vec.remove(index),
795 }
796 }
797
798 /// Retains only the elements specified by the predicate.
799 ///
800 /// This function does not affect the position (stack/heap) of the data.
801 ///
802 /// # Time complexity
803 ///
804 /// O(N)
805 ///
806 /// # Examples
807 ///
808 /// ```
809 /// # use fastvec::{AutoVec, autovec};
810 /// let mut vec: AutoVec<_, 4> = autovec![1, 2, 3, 4];
811 /// vec.retain(|v| *v % 2 == 0);
812 /// assert_eq!(vec, [2, 4]);
813 /// ```
814 #[inline]
815 pub fn retain<F: FnMut(&T) -> bool>(&mut self, f: F) {
816 match &mut self.0 {
817 InnerVec::Stack(vec) => vec.retain(f),
818 InnerVec::Heap(vec) => vec.retain(f),
819 }
820 }
821
822 /// Retains only the elements specified by the predicate, passing a mutable reference to it.
823 ///
824 /// This function does not affect the position (stack/heap) of the data.
825 ///
826 /// # Time complexity
827 ///
828 /// O(N)
829 ///
830 /// # Examples
831 ///
832 /// ```
833 /// # use fastvec::{AutoVec, autovec};
834 /// let mut vec: AutoVec<_, 4> = autovec![1, 2, 3, 4];
835 /// vec.retain_mut(|v|{ *v += 10; *v % 2 == 0 });
836 /// assert_eq!(vec, [12, 14]);
837 /// ```
838 #[inline]
839 pub fn retain_mut<F: FnMut(&mut T) -> bool>(&mut self, f: F) {
840 match &mut self.0 {
841 InnerVec::Stack(vec) => vec.retain_mut(f),
842 InnerVec::Heap(vec) => vec.retain_mut(f),
843 }
844 }
845
846 /// Removes all but the first of consecutive elements in the vector that resolve to the same key.
847 ///
848 /// # Time complexity
849 ///
850 /// O(N)
851 ///
852 /// See [`Vec::dedup_by_key`].
853 #[inline]
854 pub fn dedup_by_key<F, K>(&mut self, key: F)
855 where
856 F: FnMut(&mut T) -> K,
857 K: PartialEq,
858 {
859 match &mut self.0 {
860 InnerVec::Stack(vec) => vec.dedup_by_key(key),
861 InnerVec::Heap(vec) => vec.dedup_by_key(key),
862 }
863 }
864
865 /// Removes all but the first of consecutive elements in the vector satisfying a given equality relation.
866 ///
867 /// # Time complexity
868 ///
869 /// O(N)
870 ///
871 /// See [`Vec::dedup_by`].
872 #[inline]
873 pub fn dedup_by<F: FnMut(&mut T, &mut T) -> bool>(&mut self, same_bucket: F) {
874 match &mut self.0 {
875 InnerVec::Stack(vec) => vec.dedup_by(same_bucket),
876 InnerVec::Heap(vec) => vec.dedup_by(same_bucket),
877 }
878 }
879
880 /// Appends an element to the back of a collection.
881 ///
882 /// If the stack capacity is insufficient, it will switch to [`Vec`] and reserve some additional memory.
883 ///
884 /// # Time complexity
885 /// Takes amortized O(1) time. If the vector’s length would exceed its capacity after the push,
886 /// O(capacity) time is taken to copy the vector’s elements to a larger allocation.
887 ///
888 /// # Examples
889 /// ```
890 /// # use fastvec::{AutoVec, autovec};
891 /// let mut vec: AutoVec<_, 4> = autovec![1, 2];
892 /// vec.push(3);
893 /// assert_eq!(vec, [1, 2, 3]);
894 /// ```
895 #[inline]
896 pub fn push(&mut self, value: T) {
897 match &mut self.0 {
898 InnerVec::Stack(vec) => {
899 if vec.len() < N {
900 // SAFETY: len < N
901 unsafe { vec.push_uncheck(value) };
902 } else {
903 let mut new_vec: Vec<T> = Vec::with_capacity(N + { N >> 1 } + 4);
904 let dst_ptr = new_vec.as_mut_ptr();
905 let src_ptr = vec.as_ptr();
906 // SAFETY: enough capacity and valid data.
907 unsafe {
908 ptr::copy_nonoverlapping(src_ptr, dst_ptr, N);
909 ptr::write(dst_ptr.add(N), value);
910 vec.set_len(0);
911 new_vec.set_len(N + 1);
912 }
913 self.0 = InnerVec::Heap(new_vec);
914 }
915 }
916 InnerVec::Heap(vec) => vec.push(value),
917 }
918 }
919
920 /// Removes the last element from a vector and returns it, or None if it is empty.
921 ///
922 /// This function does not affect the position (stack/heap) of the data.
923 ///
924 /// # Time complexity
925 /// O(1)
926 ///
927 /// # Examples
928 /// ```
929 /// # use fastvec::{AutoVec, autovec};
930 /// let mut vec: AutoVec<_, 4> = autovec![1, 2, 3];
931 /// assert_eq!(vec.pop(), Some(3));
932 /// assert_eq!(vec, [1, 2]);
933 /// ```
934 #[inline]
935 pub fn pop(&mut self) -> Option<T> {
936 match &mut self.0 {
937 InnerVec::Stack(vec) => vec.pop(),
938 InnerVec::Heap(vec) => vec.pop(),
939 }
940 }
941
942 /// Removes and returns the last element from a vector if the predicate returns `true`,
943 /// or `None` if the predicate returns false or the vector is empty (the predicate will not be called in that case).
944 ///
945 /// # Time complexity
946 /// O(1)
947 ///
948 /// # Examples
949 /// ```
950 /// # use fastvec::{AutoVec, autovec};
951 /// let mut vec: AutoVec<_, 4> = autovec![1, 2, 3];
952 ///
953 /// assert_eq!(vec.pop_if(|v| *v == 2 ), None);
954 /// assert_eq!(vec, [1, 2, 3]);
955 ///
956 /// assert_eq!(vec.pop_if(|v| *v == 3 ), Some(3));
957 /// assert_eq!(vec, [1, 2]);
958 /// ```
959 #[inline]
960 pub fn pop_if(&mut self, predicate: impl FnOnce(&mut T) -> bool) -> Option<T> {
961 match &mut self.0 {
962 InnerVec::Stack(vec) => vec.pop_if(predicate),
963 InnerVec::Heap(vec) => vec.pop_if(predicate),
964 }
965 }
966
967 /// Moves all the elements of other into self, leaving other empty.
968 ///
969 /// If you want to append other types of arrays, it is recommended to use [`Extend`] trait.
970 ///
971 /// This function does not affect the capacity of **other**,
972 /// so not affect the position (stack/heap) of the other data.
973 ///
974 /// # Examples
975 ///
976 /// ```
977 /// # use fastvec::{AutoVec, autovec};
978 /// let mut vec1: AutoVec<_, 4> = autovec![1, 2, 3];
979 /// let mut vec2: AutoVec<_, 4> = autovec![4, 5, 6];
980 /// vec1.append(&mut vec2);
981 ///
982 /// assert_eq!(vec1, [1, 2, 3, 4, 5, 6]);
983 /// assert_eq!(vec2, []);
984 /// # assert!(!vec1.in_stack());
985 /// # assert!(vec2.in_stack());
986 /// ```
987 #[inline]
988 pub fn append<const P: usize>(&mut self, other: &mut AutoVec<T, P>) {
989 match &mut other.0 {
990 InnerVec::Stack(vec) => {
991 self.append_stack_vec(vec);
992 }
993 InnerVec::Heap(vec) => {
994 self.append_vec(vec);
995 }
996 }
997 }
998
999 /// Moves all the elements of [`StackVec`] into self, leaving [`StackVec`] empty.
1000 ///
1001 /// Because knowing the exact length, this is faster than [`Extend`] .
1002 pub fn append_stack_vec<const P: usize>(&mut self, other: &mut StackVec<T, P>) {
1003 match &mut self.0 {
1004 InnerVec::Stack(vec) => {
1005 if vec.len() + other.len() > N {
1006 let mut vec = vec.into_vec_with_capacity(vec.len() + other.len());
1007 other.append_to_vec(&mut vec);
1008 self.0 = InnerVec::Heap(vec);
1009 } else {
1010 vec.append(other);
1011 }
1012 }
1013 InnerVec::Heap(vec) => {
1014 other.append_to_vec(vec);
1015 }
1016 }
1017 }
1018
1019 /// Moves all the elements of [`Vec`] into self, leaving [`Vec`] empty.
1020 ///
1021 /// Because knowing the exact length, this is faster than [`Extend`] .
1022 pub fn append_vec(&mut self, other: &mut Vec<T>) {
1023 match &mut self.0 {
1024 InnerVec::Stack(vec) => {
1025 if vec.len() + other.len() > N {
1026 let mut vec = vec.into_vec_with_capacity(vec.len() + other.len());
1027 vec.append(other);
1028 self.0 = InnerVec::Heap(vec);
1029 } else {
1030 vec.append_vec(other);
1031 }
1032 }
1033 InnerVec::Heap(vec) => {
1034 vec.append(other);
1035 }
1036 }
1037 }
1038
1039 /// Clears the vector, removing all values.
1040 ///
1041 /// Note that this method has no effect on the allocated capacity of the vector.
1042 ///
1043 /// # Examples
1044 ///
1045 /// ```
1046 /// # use fastvec::{AutoVec, autovec};
1047 /// let mut vec1: AutoVec<_, 4> = autovec![1, 2, 3];
1048 /// vec1.clear();
1049 /// assert!(vec1.is_empty());
1050 ///
1051 /// let mut vec1: AutoVec<_, 4> = autovec![1, 2, 3, 4, 5];
1052 /// assert!(!vec1.in_stack());
1053 /// vec1.clear();
1054 /// assert!(!vec1.in_stack());
1055 /// ```
1056 #[inline]
1057 pub fn clear(&mut self) {
1058 match &mut self.0 {
1059 InnerVec::Stack(vec) => vec.clear(),
1060 InnerVec::Heap(vec) => vec.clear(),
1061 }
1062 }
1063
1064 /// Splits the collection into two at the given index.
1065 ///
1066 /// # Panics
1067 /// Panics if at > len.
1068 ///
1069 /// # Examples
1070 /// ```
1071 /// # use fastvec::{AutoVec, autovec};
1072 /// let mut vec : AutoVec<_, 4> = autovec!['a', 'b', 'c'];
1073 /// let vec2 = vec.split_off(1);
1074 ///
1075 /// assert_eq!(vec.as_slice(), ['a']);
1076 /// assert_eq!(vec2.as_slice(), ['b', 'c']);
1077 /// ```
1078 #[inline]
1079 pub fn split_off(&mut self, at: usize) -> Self {
1080 match &mut self.0 {
1081 InnerVec::Stack(vec) => vec.split_off(at).into(),
1082 InnerVec::Heap(vec) => vec.split_off(at).into(),
1083 }
1084 }
1085
1086 /// Resizes the Vec in-place so that len is equal to new_len.
1087 ///
1088 /// This function may move data from the stack to the heap (if capacity is insufficient),
1089 /// but it will not move data from the heap to the stack.
1090 ///
1091 /// # Examples
1092 ///
1093 /// ```
1094 /// # use fastvec::{AutoVec, autovec};
1095 /// let mut vec : AutoVec<_, 4> = autovec![1, 2, 3];
1096 /// vec.resize_with(5, Default::default);
1097 /// assert_eq!(vec.as_slice(), [1, 2, 3, 0, 0]);
1098 /// assert!(!vec.in_stack());
1099 ///
1100 /// let mut vec : AutoVec<_, 4> = autovec![];
1101 /// let mut p = 1;
1102 /// vec.resize_with(4, || { p *= 2; p });
1103 /// assert_eq!(vec.as_slice(), [2, 4, 8, 16]);
1104 /// assert!(vec.in_stack());
1105 ///
1106 /// let mut vec : AutoVec<_, 3> = autovec![1, 2, 3, 4, 5];
1107 /// vec.resize_with(2, Default::default);
1108 /// assert!(!vec.in_stack());
1109 /// ```
1110 #[inline]
1111 pub fn resize_with<F: FnMut() -> T>(&mut self, new_len: usize, f: F) {
1112 match &mut self.0 {
1113 InnerVec::Stack(vec) => {
1114 if new_len <= N {
1115 vec.resize_with(new_len, f);
1116 } else {
1117 // SAFETY: capacity = new_len > len
1118 let mut vec = unsafe { vec.into_vec_with_capacity_uncheck(new_len) };
1119 vec.resize_with(new_len, f);
1120 self.0 = InnerVec::Heap(vec);
1121 }
1122 }
1123 InnerVec::Heap(vec) => vec.resize_with(new_len, f),
1124 }
1125 }
1126
1127 /// Consumes and leaks the [`AutoVec`], returning a mutable reference to the contents, `&'a mut [T]`.
1128 ///
1129 /// This will pre transfer the data to the heap to ensure the validity of the references.
1130 ///
1131 /// See more information in [`Vec::leak`].
1132 ///
1133 /// # Examples
1134 ///
1135 /// ```
1136 /// # use fastvec::{AutoVec, autovec};
1137 /// let vec : AutoVec<_, 4> = autovec![1, 2, 3];
1138 ///
1139 /// let vec: &'static mut [i32] = vec.leak();
1140 /// vec[1] = 0;
1141 /// assert_eq!(vec, [1, 0, 3]);
1142 /// ```
1143 #[inline]
1144 pub fn leak<'a>(self) -> &'a mut [T] {
1145 self.into_vec().leak()
1146 }
1147
1148 /// Returns the remaining spare capacity of the vector as a slice of `MaybeUninit<T>`.
1149 ///
1150 /// The returned slice can be used to fill the vector with data (e.g. by reading from a file)
1151 /// before marking the data as initialized using the [`set_len`](AutoVec::set_len) method.
1152 ///
1153 /// See [`Vec::spare_capacity_mut`] and [`StackVec::spare_capacity_mut`] .
1154 #[inline]
1155 pub fn spare_capacity_mut(&mut self) -> &mut [core::mem::MaybeUninit<T>] {
1156 match &mut self.0 {
1157 InnerVec::Stack(vec) => vec.spare_capacity_mut(),
1158 InnerVec::Heap(vec) => vec.spare_capacity_mut(),
1159 }
1160 }
1161}
1162
1163impl<T: Clone, const N: usize> AutoVec<T, N> {
1164 /// Creates an `AutoVec` with `num` copies of `elem`.
1165 ///
1166 /// If `num > N`, heap storage will be used.
1167 ///
1168 /// This function requires `T` to implement `Clone`.
1169 ///
1170 /// # Examples
1171 /// ```
1172 /// # use fastvec::AutoVec;
1173 /// let vec: AutoVec<i32, 5> = AutoVec::from_elem(1, 4);
1174 /// assert_eq!(vec.len(), 4);
1175 /// assert!(vec.in_stack());
1176 /// ```
1177 #[inline]
1178 pub fn from_elem(elem: T, num: usize) -> Self {
1179 let mut vec;
1180 if num <= N {
1181 vec = Self(InnerVec::Stack(StackVec::new()));
1182 } else {
1183 vec = Self(InnerVec::Heap(Vec::with_capacity(num)));
1184 }
1185 let base_ptr = vec.as_mut_ptr();
1186 let mut cnt = 1;
1187 unsafe {
1188 while cnt < num {
1189 ptr::write(base_ptr.add(cnt), elem.clone());
1190 cnt += 1;
1191 }
1192 if num != 0 {
1193 // Reduce one copy.
1194 ptr::write(base_ptr, elem);
1195 }
1196 vec.set_len(num);
1197 }
1198 vec
1199 }
1200
1201 /// Resizes the [`AutoVec`] in-place so that len is equal to `new_len`.
1202 ///
1203 /// If `new_len` is greater than `len`, the [`AutoVec`] is extended by the difference,
1204 /// with each additional slot filled with value. If `new_len` is less than `len`, the [`AutoVec`] is simply truncated.
1205 ///
1206 /// This function may move data from the stack to the heap (if capacity is insufficient),
1207 /// but it will not move data from the heap to the stack.
1208 ///
1209 /// # Examples
1210 ///
1211 /// ```
1212 /// # use fastvec::{AutoVec, autovec};
1213 /// let mut vec: AutoVec<_, 5> = autovec!["hello"];
1214 /// vec.resize(3, "world");
1215 /// assert_eq!(vec, ["hello", "world", "world"]);
1216 ///
1217 /// let mut vec: AutoVec<_, 5> = autovec!['a', 'b', 'c', 'd'];
1218 /// vec.resize(2, '_');
1219 /// assert_eq!(vec, ['a', 'b']);
1220 /// ```
1221 #[inline]
1222 pub fn resize(&mut self, new_len: usize, value: T) {
1223 match &mut self.0 {
1224 InnerVec::Stack(vec) => {
1225 if new_len <= N {
1226 vec.resize(new_len, value);
1227 } else {
1228 // SAFETY: capacity == new_len > len
1229 let mut vec = unsafe { vec.into_vec_with_capacity_uncheck(new_len) };
1230 vec.resize(new_len, value);
1231 self.0 = InnerVec::Heap(vec);
1232 }
1233 }
1234 InnerVec::Heap(vec) => vec.resize(new_len, value),
1235 }
1236 }
1237
1238 /// Clones and appends all elements in a slice to the [`AutoVec`].
1239 ///
1240 /// # Examples
1241 /// ```
1242 /// # use fastvec::{AutoVec, autovec};
1243 /// let mut vec: AutoVec<_, 5> = autovec![1];
1244 /// vec.extend_from_slice(&[2, 3, 4]);
1245 /// assert_eq!(vec, [1, 2, 3, 4]);
1246 /// ```
1247 #[inline]
1248 pub fn extend_from_slice(&mut self, other: &[T]) {
1249 match &mut self.0 {
1250 InnerVec::Stack(vec) => {
1251 let capacity = vec.len() + other.len();
1252 if capacity <= N {
1253 vec.extend_from_slice(other);
1254 } else {
1255 // SAFETY: capacity == new_len > len
1256 let mut vec = unsafe { vec.into_vec_with_capacity_uncheck(capacity) };
1257 vec.extend_from_slice(other);
1258 self.0 = InnerVec::Heap(vec);
1259 }
1260 }
1261 InnerVec::Heap(vec) => vec.extend_from_slice(other),
1262 }
1263 }
1264
1265 /// Given a range src, clones a slice of elements in that range and appends it to the end.
1266 ///
1267 /// # Examples
1268 ///
1269 /// ```
1270 /// # use fastvec::{AutoVec, autovec};
1271 /// let mut vec: AutoVec<_, 5> = autovec![0, 1, 2, 3, 4];
1272 /// vec.extend_from_within(1..3);
1273 /// assert_eq!(vec, [0, 1, 2, 3, 4, 1, 2]);
1274 /// ```
1275 #[inline]
1276 pub fn extend_from_within<R: core::ops::RangeBounds<usize>>(&mut self, src: R) {
1277 match &mut self.0 {
1278 InnerVec::Stack(vec) => {
1279 let (start, end) = crate::utils::split_range_bound(&src, vec.len());
1280 let capacity = end - start + vec.len();
1281 if capacity <= N {
1282 vec.extend_from_within(src);
1283 } else {
1284 // SAFETY: capacity == new_len > len
1285 let mut vec = unsafe { vec.into_vec_with_capacity_uncheck(capacity) };
1286 vec.extend_from_within(src);
1287 self.0 = InnerVec::Heap(vec);
1288 }
1289 }
1290 InnerVec::Heap(vec) => vec.extend_from_within(src),
1291 }
1292 }
1293}
1294
1295impl<T: PartialEq, const N: usize> AutoVec<T, N> {
1296 /// Removes consecutive repeated elements in the vector according to the PartialEq trait implementation.
1297 ///
1298 /// # Time Complexity
1299 ///
1300 /// O(N)
1301 ///
1302 /// # Examples
1303 ///
1304 /// ```
1305 /// # use fastvec::{AutoVec, autovec};
1306 /// let mut vec: AutoVec<_, 10> = autovec![0, 0, 1, 2, 2, 0];
1307 /// vec.dedup();
1308 /// assert_eq!(vec, [0, 1, 2, 0]);
1309 /// ```
1310 ///
1311 /// It can be combined with sorting.
1312 ///
1313 /// ```
1314 /// # use fastvec::{AutoVec, autovec};
1315 /// let mut vec: AutoVec<_, 10> = autovec![0, 0, 1, 2, 2, 0, 1, 4];
1316 /// vec.sort();
1317 /// vec.dedup();
1318 /// assert_eq!(vec, [0, 1, 2, 4]);
1319 /// ```
1320 #[inline]
1321 pub fn dedup(&mut self) {
1322 match &mut self.0 {
1323 InnerVec::Stack(vec) => vec.dedup(),
1324 InnerVec::Heap(vec) => vec.dedup(),
1325 }
1326 }
1327}
1328
1329impl<T, const N: usize, const P: usize> AutoVec<[T; P], N> {
1330 /// Takes a `AutoVec<[T; P], N>` and flattens it into a `AutoVec<T, S>`.
1331 ///
1332 /// If the capacity is insufficient, [`Vec`] will be used.
1333 ///
1334 /// # Examples
1335 ///
1336 /// ```
1337 /// # use fastvec::{AutoVec, autovec};
1338 /// let mut vec: AutoVec<_, 2> = autovec![[1, 2, 3], [4, 5, 6], [7, 8, 9]];
1339 /// assert_eq!(vec.pop(), Some([7, 8, 9]));
1340 /// assert!(!vec.in_stack());
1341 ///
1342 /// let mut flattened = vec.into_flattened::<6>();
1343 /// assert_eq!(flattened.as_slice(), [1, 2, 3, 4, 5, 6]);
1344 /// assert!(flattened.in_stack());
1345 ///
1346 /// let mut vec: AutoVec<_, 3> = autovec![[1, 2, 3], [4, 5, 6], [7, 8, 9]];
1347 /// assert_eq!(vec.pop(), Some([7, 8, 9]));
1348 /// assert!(vec.in_stack());
1349 ///
1350 /// let mut flattened = vec.into_flattened::<5>();
1351 /// assert_eq!(flattened.as_slice(), [1, 2, 3, 4, 5, 6]);
1352 /// assert!(!flattened.in_stack());
1353 /// ```
1354 #[inline]
1355 pub fn into_flattened<const S: usize>(self) -> AutoVec<T, S> {
1356 match self.0 {
1357 InnerVec::Stack(mut vec) => {
1358 if S >= P * vec.len() {
1359 vec.into_flattened::<S>().into()
1360 } else {
1361 vec.into_vec().into_flattened().into()
1362 }
1363 }
1364 InnerVec::Heap(vec) => {
1365 if S >= P * vec.len() {
1366 // SAFETY: capasity == S > new_len == P * old_len
1367 unsafe { <StackVec<T, S>>::from_vec_uncheck(&mut vec.into_flattened()).into() }
1368 } else {
1369 vec.into_flattened().into()
1370 }
1371 }
1372 }
1373 }
1374}
1375
1376impl<T, const N: usize> Default for AutoVec<T, N> {
1377 /// Constructs a new, empty [`AutoVec`] on the stack with the specified capacity.
1378 ///
1379 /// It's eq to [`AutoVec::new`] .
1380 #[inline(always)]
1381 fn default() -> Self {
1382 Self::new()
1383 }
1384}
1385
1386impl<'a, T: 'a + Clone, const N: usize> Extend<&'a T> for AutoVec<T, N> {
1387 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
1388 let iter = iter.into_iter();
1389 let (hint, _) = iter.size_hint();
1390 if hint > 0 {
1391 self.reserve(hint);
1392 }
1393
1394 for item in iter {
1395 self.push(item.clone());
1396 }
1397 }
1398}
1399
1400impl<T, const N: usize> Extend<T> for AutoVec<T, N> {
1401 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1402 let iter = iter.into_iter();
1403 let (hint, _) = iter.size_hint();
1404 if hint > 0 {
1405 self.reserve(hint);
1406 }
1407
1408 for item in iter {
1409 self.push(item);
1410 }
1411 }
1412}
1413
1414crate::utils::impl_commen_traits!(AutoVec<T, N>);
1415
1416impl<T, U, const N: usize> core::cmp::PartialEq<AutoVec<U, N>> for AutoVec<T, N>
1417where
1418 T: core::cmp::PartialEq<U>,
1419{
1420 #[inline]
1421 fn eq(&self, other: &AutoVec<U, N>) -> bool {
1422 core::cmp::PartialEq::eq(self.as_slice(), other.as_slice())
1423 }
1424}
1425
1426impl<'a, T: Clone, const N: usize> From<&'a AutoVec<T, N>> for alloc::borrow::Cow<'a, [T]> {
1427 fn from(v: &'a AutoVec<T, N>) -> alloc::borrow::Cow<'a, [T]> {
1428 alloc::borrow::Cow::Borrowed(v.as_slice())
1429 }
1430}
1431
1432impl<'a, T: Clone, const N: usize> From<AutoVec<T, N>> for alloc::borrow::Cow<'a, [T]> {
1433 fn from(v: AutoVec<T, N>) -> alloc::borrow::Cow<'a, [T]> {
1434 alloc::borrow::Cow::Owned(v.into_vec())
1435 }
1436}
1437
1438impl<T: Clone, const N: usize> From<&[T]> for AutoVec<T, N> {
1439 fn from(value: &[T]) -> Self {
1440 if value.len() <= N {
1441 <StackVec<T, N> as From<&[T]>>::from(value).into()
1442 } else {
1443 <Vec<T> as From<&[T]>>::from(value).into()
1444 }
1445 }
1446}
1447
1448impl<T: Clone, const N: usize, const P: usize> From<&[T; P]> for AutoVec<T, N> {
1449 fn from(value: &[T; P]) -> Self {
1450 if P <= N {
1451 <StackVec<T, N> as From<&[T; P]>>::from(value).into()
1452 } else {
1453 <Vec<T> as From<&[T; P]>>::from(value).into()
1454 }
1455 }
1456}
1457
1458impl<T: Clone, const N: usize> From<&mut [T]> for AutoVec<T, N> {
1459 #[inline]
1460 fn from(value: &mut [T]) -> Self {
1461 <Self as From<&[T]>>::from(value)
1462 }
1463}
1464
1465impl<T: Clone, const N: usize, const P: usize> From<&mut [T; P]> for AutoVec<T, N> {
1466 #[inline]
1467 fn from(value: &mut [T; P]) -> Self {
1468 <Self as From<&[T; P]>>::from(value)
1469 }
1470}
1471
1472impl<T, const N: usize, const P: usize> From<[T; P]> for AutoVec<T, N> {
1473 fn from(value: [T; P]) -> Self {
1474 if P <= N {
1475 <StackVec<T, N> as From<[T; P]>>::from(value).into()
1476 } else {
1477 <Vec<T> as From<[T; P]>>::from(value).into()
1478 }
1479 }
1480}
1481
1482impl<T, const N: usize> From<Box<[T]>> for AutoVec<T, N> {
1483 fn from(value: Box<[T]>) -> Self {
1484 if value.len() <= N {
1485 <StackVec<T, N> as From<Box<[T]>>>::from(value).into()
1486 } else {
1487 <Vec<T> as From<Box<[T]>>>::from(value).into()
1488 }
1489 }
1490}
1491
1492impl<T, const N: usize> FromIterator<T> for AutoVec<T, N> {
1493 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
1494 let iter = iter.into_iter();
1495 let (hint, _) = iter.size_hint();
1496
1497 let mut vec = if hint <= N {
1498 Self::new()
1499 } else {
1500 Vec::with_capacity(hint).into()
1501 };
1502
1503 for item in iter {
1504 vec.push(item);
1505 }
1506 vec
1507 }
1508}
1509
1510impl<T, const N: usize> IntoIterator for AutoVec<T, N> {
1511 type Item = T;
1512 type IntoIter = IntoIter<T, N>;
1513
1514 #[inline]
1515 fn into_iter(self) -> Self::IntoIter {
1516 match self.0 {
1517 InnerVec::Stack(vec) => IntoIter::Stack(IntoIterator::into_iter(vec)),
1518 InnerVec::Heap(vec) => IntoIter::Heap(IntoIterator::into_iter(vec)),
1519 }
1520 }
1521}
1522
1523/// An iterator that consumes an [`AutoVec`] and yields its items by value.
1524///
1525/// See [`IntoIterator::into_iter`] .
1526#[derive(Clone)]
1527pub enum IntoIter<T, const N: usize> {
1528 Stack(crate::stack_vec::IntoIter<T, N>),
1529 Heap(alloc::vec::IntoIter<T>),
1530}
1531
1532impl<T, const N: usize> IntoIter<T, N> {
1533 #[inline]
1534 pub fn as_slice(&self) -> &[T] {
1535 match self {
1536 IntoIter::Stack(iter) => iter.as_slice(),
1537 IntoIter::Heap(iter) => iter.as_slice(),
1538 }
1539 }
1540 #[inline]
1541 pub fn as_mut_slice(&mut self) -> &mut [T] {
1542 match self {
1543 IntoIter::Stack(iter) => iter.as_mut_slice(),
1544 IntoIter::Heap(iter) => iter.as_mut_slice(),
1545 }
1546 }
1547}
1548
1549impl<T, const N: usize> Iterator for IntoIter<T, N> {
1550 type Item = T;
1551 #[inline]
1552 fn next(&mut self) -> Option<Self::Item> {
1553 match self {
1554 IntoIter::Stack(iter) => Iterator::next(iter),
1555 IntoIter::Heap(iter) => Iterator::next(iter),
1556 }
1557 }
1558
1559 #[inline]
1560 fn size_hint(&self) -> (usize, Option<usize>) {
1561 match self {
1562 IntoIter::Stack(iter) => Iterator::size_hint(iter),
1563 IntoIter::Heap(iter) => Iterator::size_hint(iter),
1564 }
1565 }
1566}
1567
1568impl<T, const N: usize> DoubleEndedIterator for IntoIter<T, N> {
1569 #[inline]
1570 fn next_back(&mut self) -> Option<Self::Item> {
1571 match self {
1572 IntoIter::Stack(iter) => DoubleEndedIterator::next_back(iter),
1573 IntoIter::Heap(iter) => DoubleEndedIterator::next_back(iter),
1574 }
1575 }
1576}
1577
1578impl<T, const N: usize> ExactSizeIterator for IntoIter<T, N> {}
1579
1580impl<T, const N: usize> FusedIterator for IntoIter<T, N> {}
1581
1582impl<T, const N: usize> Default for IntoIter<T, N> {
1583 fn default() -> Self {
1584 Self::Stack(crate::stack_vec::IntoIter::default())
1585 }
1586}
1587
1588impl<T: fmt::Debug, const N: usize> fmt::Debug for IntoIter<T, N> {
1589 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1590 f.debug_tuple("IntoIter").field(&self.as_slice()).finish()
1591 }
1592}
1593
1594/// An iterator that removes the items from a [`AutoVec`] and yields them by value.
1595///
1596/// See [`AutoVec::drain`] .
1597pub enum Drain<'a, T: 'a, const N: usize> {
1598 Stack(crate::stack_vec::Drain<'a, T, N>),
1599 Heap(alloc::vec::Drain<'a, T>),
1600}
1601
1602impl<T, const N: usize> AutoVec<T, N> {
1603 /// Removes the subslice indicated by the given range from the vector,
1604 /// returning a double-ended iterator over the removed subslice.
1605 ///
1606 /// # Panics
1607 /// Panics if the range has `start_bound > end_bound`, or,
1608 /// if the range is bounded on either end and past the length of the vector.
1609 ///
1610 /// # Leaking
1611 /// If the returned iterator goes out of scope without being dropped (due to [`core::mem::forget`], for example),
1612 /// the vector may have lost and leaked elements arbitrarily, including elements outside the range.
1613 ///
1614 /// # Examples
1615 ///
1616 /// ```
1617 /// # use fastvec::{AutoVec, autovec};
1618 /// let mut v: AutoVec<_, 4> = autovec![1, 2, 3];
1619 /// let u: Vec<_> = v.drain(1..).collect();
1620 /// assert_eq!(v.as_slice(), [1]);
1621 /// assert_eq!(u, [2, 3]);
1622 ///
1623 /// v.drain(..);
1624 /// assert_eq!(v.as_slice(), &[]);
1625 /// ```
1626 #[inline]
1627 pub fn drain<R: core::ops::RangeBounds<usize>>(&mut self, range: R) -> Drain<'_, T, N> {
1628 match &mut self.0 {
1629 InnerVec::Stack(vec) => Drain::Stack(vec.drain(range)),
1630 InnerVec::Heap(vec) => Drain::Heap(vec.drain(range)),
1631 }
1632 }
1633}
1634
1635impl<T, const N: usize> Drain<'_, T, N> {
1636 #[inline]
1637 pub fn as_slice(&self) -> &[T] {
1638 match &self {
1639 Drain::Stack(drain) => drain.as_slice(),
1640 Drain::Heap(drain) => drain.as_slice(),
1641 }
1642 }
1643}
1644
1645impl<T, const N: usize> AsRef<[T]> for Drain<'_, T, N> {
1646 #[inline]
1647 fn as_ref(&self) -> &[T] {
1648 match &self {
1649 Drain::Stack(drain) => drain.as_ref(),
1650 Drain::Heap(drain) => drain.as_ref(),
1651 }
1652 }
1653}
1654
1655impl<T: fmt::Debug, const N: usize> fmt::Debug for Drain<'_, T, N> {
1656 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1657 f.debug_tuple("Drain").field(&self.as_slice()).finish()
1658 }
1659}
1660
1661impl<T, const N: usize> Iterator for Drain<'_, T, N> {
1662 type Item = T;
1663
1664 #[inline]
1665 fn next(&mut self) -> Option<T> {
1666 match self {
1667 Drain::Stack(drain) => drain.next(),
1668 Drain::Heap(drain) => drain.next(),
1669 }
1670 }
1671
1672 #[inline]
1673 fn size_hint(&self) -> (usize, Option<usize>) {
1674 match self {
1675 Drain::Stack(drain) => drain.size_hint(),
1676 Drain::Heap(drain) => drain.size_hint(),
1677 }
1678 }
1679}
1680
1681impl<T, const N: usize> DoubleEndedIterator for Drain<'_, T, N> {
1682 #[inline]
1683 fn next_back(&mut self) -> Option<T> {
1684 match self {
1685 Drain::Stack(drain) => drain.next_back(),
1686 Drain::Heap(drain) => drain.next_back(),
1687 }
1688 }
1689}
1690
1691impl<T, const N: usize> ExactSizeIterator for Drain<'_, T, N> {
1692 #[inline]
1693 fn len(&self) -> usize {
1694 match self {
1695 Drain::Stack(drain) => drain.len(),
1696 Drain::Heap(drain) => drain.len(),
1697 }
1698 }
1699}
1700
1701impl<T, const N: usize> FusedIterator for Drain<'_, T, N> {}
1702
1703/// A splicing iterator for [`AutoVec`].
1704///
1705/// See [`AutoVec::splice`] .
1706pub enum Splice<'a, I: ExactSizeIterator + 'a, const N: usize> {
1707 Stack(crate::stack_vec::Splice<'a, I, N>),
1708 Heap(alloc::vec::Splice<'a, I>),
1709}
1710
1711impl<T, const N: usize> AutoVec<T, N> {
1712 /// Creates a splicing iterator that replaces the specified range in the vector
1713 /// with the given `replace_with` iterator and yields the removed items.
1714 /// `replace_with` does not need to be the same length as `range`.
1715 ///
1716 /// See [`alloc::vec::Splice`] for details; unlike `Vec::splice`, this requires
1717 /// `replace_with` to implement [`ExactSizeIterator`].
1718 ///
1719 /// This is optimal if:
1720 ///
1721 /// * The tail (elements in the vector after `range`) is empty,
1722 /// * or `replace_with` yields elements equal to `range`'s length
1723 ///
1724 /// If the capacity is insufficient, this will first switch to the heap and then call splice.
1725 ///
1726 /// # Examples
1727 ///
1728 /// ```
1729 /// # use fastvec::{autovec, AutoVec};
1730 /// let mut v: AutoVec<_, 4> = autovec![1, 2, 3, 4];
1731 /// let new = [7, 8, 9];
1732 /// let u: Vec<_> = v.splice(1..3, new).collect();
1733 ///
1734 /// assert!(!v.in_stack());
1735 /// assert_eq!(v, [1, 7, 8, 9, 4]);
1736 /// assert_eq!(u, [2, 3]);
1737 /// ```
1738 ///
1739 /// Using `splice` to insert new items into a vector efficiently at a specific position
1740 /// indicated by an empty range:
1741 ///
1742 /// ```
1743 /// # use fastvec::{autovec, AutoVec};
1744 /// let mut v: AutoVec<_, 5> = autovec![1, 5];
1745 /// let new = [2, 3, 4];
1746 /// v.splice(1..1, new);
1747 /// assert_eq!(v, [1, 2, 3, 4, 5]);
1748 /// ```
1749 pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter, N>
1750 where
1751 R: core::ops::RangeBounds<usize>,
1752 I: IntoIterator<Item = T>,
1753 I::IntoIter: ExactSizeIterator,
1754 {
1755 let iter = replace_with.into_iter();
1756 let len = self.len();
1757 let (start, end) = crate::utils::split_range_bound(&range, len);
1758 let capacity = len - end + start + iter.len();
1759
1760 if capacity > N {
1761 Splice::Heap(self.force_to_heap().splice(range, iter))
1762 } else {
1763 match &mut self.0 {
1764 InnerVec::Stack(vec) => Splice::Stack(vec.splice(range, iter)),
1765 InnerVec::Heap(vec) => Splice::Heap(vec.splice(range, iter)),
1766 }
1767 }
1768 }
1769}
1770
1771impl<I: ExactSizeIterator, const N: usize> Iterator for Splice<'_, I, N> {
1772 type Item = I::Item;
1773
1774 #[inline]
1775 fn next(&mut self) -> Option<Self::Item> {
1776 match self {
1777 Splice::Stack(splice) => splice.next(),
1778 Splice::Heap(splice) => splice.next(),
1779 }
1780 }
1781 #[inline]
1782 fn size_hint(&self) -> (usize, Option<usize>) {
1783 match self {
1784 Splice::Stack(splice) => splice.size_hint(),
1785 Splice::Heap(splice) => splice.size_hint(),
1786 }
1787 }
1788}
1789
1790impl<I: ExactSizeIterator, const N: usize> DoubleEndedIterator for Splice<'_, I, N> {
1791 #[inline]
1792 fn next_back(&mut self) -> Option<Self::Item> {
1793 match self {
1794 Splice::Stack(splice) => splice.next_back(),
1795 Splice::Heap(splice) => splice.next_back(),
1796 }
1797 }
1798}
1799
1800impl<I: ExactSizeIterator, const N: usize> ExactSizeIterator for Splice<'_, I, N> {
1801 #[inline]
1802 fn len(&self) -> usize {
1803 match self {
1804 Splice::Stack(splice) => splice.len(),
1805 Splice::Heap(splice) => splice.len(),
1806 }
1807 }
1808}
1809
1810impl<I: fmt::Debug + ExactSizeIterator, const N: usize> fmt::Debug for Splice<'_, I, N>
1811where
1812 I::Item: fmt::Debug,
1813{
1814 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1815 match self {
1816 Self::Stack(splice) => fmt::Debug::fmt(splice, f),
1817 Self::Heap(splice) => fmt::Debug::fmt(splice, f),
1818 }
1819 }
1820}
1821
1822/// An iterator which uses a closure to determine if an element should be removed.
1823///
1824/// See [`AutoVec::extract_if`] .
1825pub enum ExtractIf<'a, T, F: FnMut(&mut T) -> bool, const N: usize> {
1826 Stack(crate::stack_vec::ExtractIf<'a, T, F, N>),
1827 Heap(alloc::vec::ExtractIf<'a, T, F>),
1828}
1829
1830impl<T, const N: usize> AutoVec<T, N> {
1831 /// Creates an iterator which uses a closure to determine if an element in the range should be removed.
1832 ///
1833 /// See more information in [`Vec::extract_if`].
1834 ///
1835 /// # Panics
1836 ///
1837 /// If `range` is out of bounds.
1838 ///
1839 /// # Examples
1840 ///
1841 /// Splitting a vector into even and odd values, reusing the original vector:
1842 ///
1843 /// ```
1844 /// # use fastvec::{autovec, AutoVec};
1845 /// let mut numbers: AutoVec<_, 20> = autovec![1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15];
1846 ///
1847 /// let evens = numbers.extract_if(.., |x| *x % 2 == 0).collect::<AutoVec<_, 10>>();
1848 /// let odds = numbers;
1849 ///
1850 /// assert_eq!(evens, [2, 4, 6, 8, 14]);
1851 /// assert_eq!(odds, [1, 3, 5, 9, 11, 13, 15]);
1852 /// ```
1853 ///
1854 /// Using the range argument to only process a part of the vector:
1855 ///
1856 /// ```
1857 /// # use fastvec::{autovec, AutoVec};
1858 /// let mut items: AutoVec<_, 15> = autovec![0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 2, 1, 2];
1859 /// let ones = items.extract_if(7.., |x| *x == 1).collect::<Vec<_>>();
1860 /// assert_eq!(items, [0, 0, 0, 0, 0, 0, 0, 2, 2, 2]);
1861 /// assert_eq!(ones.len(), 3);
1862 /// ```
1863 pub fn extract_if<F, R>(&mut self, range: R, filter: F) -> ExtractIf<'_, T, F, N>
1864 where
1865 F: FnMut(&mut T) -> bool,
1866 R: core::ops::RangeBounds<usize>,
1867 {
1868 match &mut self.0 {
1869 InnerVec::Stack(vec) => ExtractIf::Stack(vec.extract_if(range, filter)),
1870 InnerVec::Heap(vec) => ExtractIf::Heap(vec.extract_if(range, filter)),
1871 }
1872 }
1873}
1874
1875impl<T, F: FnMut(&mut T) -> bool, const N: usize> Iterator for ExtractIf<'_, T, F, N> {
1876 type Item = T;
1877
1878 #[inline]
1879 fn next(&mut self) -> Option<Self::Item> {
1880 match self {
1881 ExtractIf::Stack(extract_if) => extract_if.next(),
1882 ExtractIf::Heap(extract_if) => extract_if.next(),
1883 }
1884 }
1885
1886 #[inline]
1887 fn size_hint(&self) -> (usize, Option<usize>) {
1888 match self {
1889 ExtractIf::Stack(extract_if) => extract_if.size_hint(),
1890 ExtractIf::Heap(extract_if) => extract_if.size_hint(),
1891 }
1892 }
1893}
1894
1895impl<T: fmt::Debug, F: FnMut(&mut T) -> bool, const N: usize> fmt::Debug
1896 for ExtractIf<'_, T, F, N>
1897{
1898 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1899 match self {
1900 ExtractIf::Stack(extract_if) => fmt::Debug::fmt(extract_if, f),
1901 ExtractIf::Heap(extract_if) => fmt::Debug::fmt(extract_if, f),
1902 }
1903 }
1904}