1use super::*;
2
3use alloc::vec::{self, Vec};
4use core::convert::TryFrom;
5use tinyvec_macros::impl_mirrored;
6
7#[cfg(feature = "rustc_1_57")]
8use alloc::collections::TryReserveError;
9
10#[cfg(feature = "serde")]
11use core::marker::PhantomData;
12#[cfg(feature = "serde")]
13use serde::de::{Deserialize, Deserializer, SeqAccess, Visitor};
14#[cfg(feature = "serde")]
15use serde::ser::{Serialize, SerializeSeq, Serializer};
16
17#[macro_export]
36#[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
37macro_rules! tiny_vec {
38 ($array_type:ty => $($elem:expr),* $(,)?) => {
39 {
40 const INVOKED_ELEM_COUNT: usize = 0 $( + { let _ = stringify!($elem); 1 })*;
42 match $crate::TinyVec::constructor_for_capacity(INVOKED_ELEM_COUNT) {
45 $crate::TinyVecConstructor::Inline(f) => {
46 f($crate::array_vec!($array_type => $($elem),*))
47 }
48 $crate::TinyVecConstructor::Heap(f) => {
49 f(vec!($($elem),*))
50 }
51 }
52 }
53 };
54 ($array_type:ty) => {
55 $crate::TinyVec::<$array_type>::default()
56 };
57 ($($elem:expr),*) => {
58 $crate::tiny_vec!(_ => $($elem),*)
59 };
60 ($elem:expr; $n:expr) => {
61 $crate::TinyVec::from([$elem; $n])
62 };
63 () => {
64 $crate::tiny_vec!(_)
65 };
66}
67
68#[doc(hidden)] pub enum TinyVecConstructor<A: Array> {
70 Inline(fn(ArrayVec<A>) -> TinyVec<A>),
71 Heap(fn(Vec<A::Item>) -> TinyVec<A>),
72}
73
74#[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
96pub enum TinyVec<A: Array> {
97 #[allow(missing_docs)]
98 Inline(ArrayVec<A>),
99 #[allow(missing_docs)]
100 Heap(Vec<A::Item>),
101}
102
103impl<A> Clone for TinyVec<A>
104where
105 A: Array + Clone,
106 A::Item: Clone,
107{
108 #[inline]
109 fn clone(&self) -> Self {
110 match self {
111 TinyVec::Heap(v) => TinyVec::Heap(v.clone()),
112 TinyVec::Inline(v) => TinyVec::Inline(v.clone()),
113 }
114 }
115
116 #[inline]
117 fn clone_from(&mut self, o: &Self) {
118 if o.len() > self.len() {
119 self.reserve(o.len() - self.len());
120 } else {
121 self.truncate(o.len());
122 }
123 let (start, end) = o.split_at(self.len());
124 for (dst, src) in self.iter_mut().zip(start) {
125 dst.clone_from(src);
126 }
127 self.extend_from_slice(end);
128 }
129}
130
131impl<A: Array> Default for TinyVec<A> {
132 #[inline]
133 fn default() -> Self {
134 TinyVec::Inline(ArrayVec::default())
135 }
136}
137
138impl<A: Array> Deref for TinyVec<A> {
139 type Target = [A::Item];
140
141 impl_mirrored! {
142 type Mirror = TinyVec;
143 #[inline(always)]
144 #[must_use]
145 fn deref(self: &Self) -> &Self::Target;
146 }
147}
148
149impl<A: Array> DerefMut for TinyVec<A> {
150 impl_mirrored! {
151 type Mirror = TinyVec;
152 #[inline(always)]
153 #[must_use]
154 fn deref_mut(self: &mut Self) -> &mut Self::Target;
155 }
156}
157
158impl<A: Array, I: SliceIndex<[A::Item]>> Index<I> for TinyVec<A> {
159 type Output = <I as SliceIndex<[A::Item]>>::Output;
160 #[inline(always)]
161 fn index(&self, index: I) -> &Self::Output {
162 &self.deref()[index]
163 }
164}
165
166impl<A: Array, I: SliceIndex<[A::Item]>> IndexMut<I> for TinyVec<A> {
167 #[inline(always)]
168 fn index_mut(&mut self, index: I) -> &mut Self::Output {
169 &mut self.deref_mut()[index]
170 }
171}
172
173#[cfg(feature = "std")]
174#[cfg_attr(docs_rs, doc(cfg(feature = "std")))]
175impl<A: Array<Item = u8>> std::io::Write for TinyVec<A> {
176 #[inline(always)]
177 fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
178 self.extend_from_slice(buf);
179 Ok(buf.len())
180 }
181
182 #[inline(always)]
183 fn flush(&mut self) -> std::io::Result<()> {
184 Ok(())
185 }
186}
187
188#[cfg(feature = "serde")]
189#[cfg_attr(docs_rs, doc(cfg(feature = "serde")))]
190impl<A: Array> Serialize for TinyVec<A>
191where
192 A::Item: Serialize,
193{
194 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
195 where
196 S: Serializer,
197 {
198 let mut seq = serializer.serialize_seq(Some(self.len()))?;
199 for element in self.iter() {
200 seq.serialize_element(element)?;
201 }
202 seq.end()
203 }
204}
205
206#[cfg(feature = "serde")]
207#[cfg_attr(docs_rs, doc(cfg(feature = "serde")))]
208impl<'de, A: Array> Deserialize<'de> for TinyVec<A>
209where
210 A::Item: Deserialize<'de>,
211{
212 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
213 where
214 D: Deserializer<'de>,
215 {
216 deserializer.deserialize_seq(TinyVecVisitor(PhantomData))
217 }
218}
219
220#[cfg(feature = "borsh")]
221#[cfg_attr(docs_rs, doc(cfg(feature = "borsh")))]
222impl<A: Array> borsh::BorshSerialize for TinyVec<A>
223where
224 <A as Array>::Item: borsh::BorshSerialize,
225{
226 fn serialize<W: borsh::io::Write>(
227 &self, writer: &mut W,
228 ) -> borsh::io::Result<()> {
229 <usize as borsh::BorshSerialize>::serialize(&self.len(), writer)?;
230 for elem in self.iter() {
231 <<A as Array>::Item as borsh::BorshSerialize>::serialize(elem, writer)?;
232 }
233 Ok(())
234 }
235}
236
237#[cfg(feature = "borsh")]
238#[cfg_attr(docs_rs, doc(cfg(feature = "borsh")))]
239impl<A: Array> borsh::BorshDeserialize for TinyVec<A>
240where
241 <A as Array>::Item: borsh::BorshDeserialize,
242{
243 fn deserialize_reader<R: borsh::io::Read>(
244 reader: &mut R,
245 ) -> borsh::io::Result<Self> {
246 let len = <usize as borsh::BorshDeserialize>::deserialize_reader(reader)?;
247 let mut new_tinyvec = Self::with_capacity(len);
248
249 for _ in 0..len {
250 new_tinyvec.push(
251 <<A as Array>::Item as borsh::BorshDeserialize>::deserialize_reader(
252 reader,
253 )?,
254 )
255 }
256
257 Ok(new_tinyvec)
258 }
259}
260
261#[cfg(feature = "arbitrary")]
262#[cfg_attr(docs_rs, doc(cfg(feature = "arbitrary")))]
263impl<'a, A> arbitrary::Arbitrary<'a> for TinyVec<A>
264where
265 A: Array,
266 A::Item: arbitrary::Arbitrary<'a>,
267{
268 fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
269 let v = Vec::arbitrary(u)?;
270 let mut tv = TinyVec::Heap(v);
271 tv.shrink_to_fit();
272 Ok(tv)
273 }
274}
275
276impl<A: Array> TinyVec<A> {
277 #[inline(always)]
279 #[must_use]
280 pub fn is_heap(&self) -> bool {
281 match self {
282 TinyVec::Heap(_) => true,
283 TinyVec::Inline(_) => false,
284 }
285 }
286 #[inline(always)]
288 #[must_use]
289 pub fn is_inline(&self) -> bool {
290 !self.is_heap()
291 }
292
293 #[inline]
305 pub fn shrink_to_fit(&mut self) {
306 let vec = match self {
307 TinyVec::Inline(_) => return,
308 TinyVec::Heap(h) => h,
309 };
310
311 if vec.len() > A::CAPACITY {
312 return vec.shrink_to_fit();
313 }
314
315 let moved_vec = core::mem::take(vec);
316
317 let mut av = ArrayVec::default();
318 let mut rest = av.fill(moved_vec);
319 debug_assert!(rest.next().is_none());
320 *self = TinyVec::Inline(av);
321 }
322
323 #[allow(clippy::missing_inline_in_public_items)]
332 pub fn move_to_the_heap(&mut self) {
333 let arr = match self {
334 TinyVec::Heap(_) => return,
335 TinyVec::Inline(a) => a,
336 };
337
338 let v = arr.drain_to_vec();
339 *self = TinyVec::Heap(v);
340 }
341
342 #[inline]
357 #[cfg(feature = "rustc_1_57")]
358 pub fn try_move_to_the_heap(&mut self) -> Result<(), TryReserveError> {
359 let arr = match self {
360 TinyVec::Heap(_) => return Ok(()),
361 TinyVec::Inline(a) => a,
362 };
363
364 let v = arr.try_drain_to_vec()?;
365 *self = TinyVec::Heap(v);
366 return Ok(());
367 }
368
369 #[inline]
380 pub fn move_to_the_heap_and_reserve(&mut self, n: usize) {
381 let arr = match self {
382 TinyVec::Heap(h) => return h.reserve(n),
383 TinyVec::Inline(a) => a,
384 };
385
386 let v = arr.drain_to_vec_and_reserve(n);
387 *self = TinyVec::Heap(v);
388 }
389
390 #[inline]
406 #[cfg(feature = "rustc_1_57")]
407 pub fn try_move_to_the_heap_and_reserve(
408 &mut self, n: usize,
409 ) -> Result<(), TryReserveError> {
410 let arr = match self {
411 TinyVec::Heap(h) => return h.try_reserve(n),
412 TinyVec::Inline(a) => a,
413 };
414
415 let v = arr.try_drain_to_vec_and_reserve(n)?;
416 *self = TinyVec::Heap(v);
417 return Ok(());
418 }
419
420 #[inline]
431 pub fn reserve(&mut self, n: usize) {
432 let arr = match self {
433 TinyVec::Heap(h) => return h.reserve(n),
434 TinyVec::Inline(a) => a,
435 };
436
437 if n > arr.capacity() - arr.len() {
438 let v = arr.drain_to_vec_and_reserve(n);
439 *self = TinyVec::Heap(v);
440 }
441
442 return;
444 }
445
446 #[inline]
462 #[cfg(feature = "rustc_1_57")]
463 pub fn try_reserve(&mut self, n: usize) -> Result<(), TryReserveError> {
464 let arr = match self {
465 TinyVec::Heap(h) => return h.try_reserve(n),
466 TinyVec::Inline(a) => a,
467 };
468
469 if n > arr.capacity() - arr.len() {
470 let v = arr.try_drain_to_vec_and_reserve(n)?;
471 *self = TinyVec::Heap(v);
472 }
473
474 return Ok(());
476 }
477
478 #[inline]
496 pub fn reserve_exact(&mut self, n: usize) {
497 let arr = match self {
498 TinyVec::Heap(h) => return h.reserve_exact(n),
499 TinyVec::Inline(a) => a,
500 };
501
502 if n > arr.capacity() - arr.len() {
503 let v = arr.drain_to_vec_and_reserve(n);
504 *self = TinyVec::Heap(v);
505 }
506
507 return;
509 }
510
511 #[inline]
533 #[cfg(feature = "rustc_1_57")]
534 pub fn try_reserve_exact(&mut self, n: usize) -> Result<(), TryReserveError> {
535 let arr = match self {
536 TinyVec::Heap(h) => return h.try_reserve_exact(n),
537 TinyVec::Inline(a) => a,
538 };
539
540 if n > arr.capacity() - arr.len() {
541 let v = arr.try_drain_to_vec_and_reserve(n)?;
542 *self = TinyVec::Heap(v);
543 }
544
545 return Ok(());
547 }
548
549 #[inline]
564 #[must_use]
565 pub fn with_capacity(cap: usize) -> Self {
566 if cap <= A::CAPACITY {
567 TinyVec::Inline(ArrayVec::default())
568 } else {
569 TinyVec::Heap(Vec::with_capacity(cap))
570 }
571 }
572
573 #[inline]
599 #[must_use]
600 pub fn into_boxed_slice(self) -> alloc::boxed::Box<[A::Item]> {
601 self.into_vec().into_boxed_slice()
602 }
603
604 #[inline]
627 #[must_use]
628 pub fn into_vec(self) -> Vec<A::Item> {
629 self.into()
630 }
631}
632
633impl<A: Array> TinyVec<A> {
634 #[inline]
636 pub fn append(&mut self, other: &mut Self) {
637 self.reserve(other.len());
638
639 match (self, other) {
641 (TinyVec::Heap(sh), TinyVec::Heap(oh)) => sh.append(oh),
642 (TinyVec::Inline(a), TinyVec::Heap(h)) => a.extend(h.drain(..)),
643 (ref mut this, TinyVec::Inline(arr)) => this.extend(arr.drain(..)),
644 }
645 }
646
647 impl_mirrored! {
648 type Mirror = TinyVec;
649
650 #[inline]
667 pub fn swap_remove(self: &mut Self, index: usize) -> A::Item;
668
669 #[inline]
674 pub fn pop(self: &mut Self) -> Option<A::Item>;
675
676 #[inline]
693 pub fn remove(self: &mut Self, index: usize) -> A::Item;
694
695 #[inline(always)]
697 #[must_use]
698 pub fn len(self: &Self) -> usize;
699
700 #[inline(always)]
705 #[must_use]
706 pub fn capacity(self: &Self) -> usize;
707
708 #[inline]
712 pub fn truncate(self: &mut Self, new_len: usize);
713
714 #[inline(always)]
720 #[must_use]
721 pub fn as_mut_ptr(self: &mut Self) -> *mut A::Item;
722
723 #[inline(always)]
729 #[must_use]
730 pub fn as_ptr(self: &Self) -> *const A::Item;
731 }
732
733 #[inline]
745 pub fn retain<F: FnMut(&A::Item) -> bool>(&mut self, acceptable: F) {
746 match self {
747 TinyVec::Inline(i) => i.retain(acceptable),
748 TinyVec::Heap(h) => h.retain(acceptable),
749 }
750 }
751
752 #[inline]
765 #[cfg(feature = "rustc_1_61")]
766 pub fn retain_mut<F: FnMut(&mut A::Item) -> bool>(&mut self, acceptable: F) {
767 match self {
768 TinyVec::Inline(i) => i.retain_mut(acceptable),
769 TinyVec::Heap(h) => h.retain_mut(acceptable),
770 }
771 }
772
773 #[inline(always)]
775 #[must_use]
776 pub fn as_mut_slice(&mut self) -> &mut [A::Item] {
777 self.deref_mut()
778 }
779
780 #[inline(always)]
782 #[must_use]
783 pub fn as_slice(&self) -> &[A::Item] {
784 self.deref()
785 }
786
787 #[inline(always)]
789 pub fn clear(&mut self) {
790 self.truncate(0)
791 }
792
793 #[cfg(feature = "nightly_slice_partition_dedup")]
795 #[inline(always)]
796 pub fn dedup(&mut self)
797 where
798 A::Item: PartialEq,
799 {
800 self.dedup_by(|a, b| a == b)
801 }
802
803 #[cfg(feature = "nightly_slice_partition_dedup")]
805 #[inline(always)]
806 pub fn dedup_by<F>(&mut self, same_bucket: F)
807 where
808 F: FnMut(&mut A::Item, &mut A::Item) -> bool,
809 {
810 let len = {
811 let (dedup, _) = self.as_mut_slice().partition_dedup_by(same_bucket);
812 dedup.len()
813 };
814 self.truncate(len);
815 }
816
817 #[cfg(feature = "nightly_slice_partition_dedup")]
819 #[inline(always)]
820 pub fn dedup_by_key<F, K>(&mut self, mut key: F)
821 where
822 F: FnMut(&mut A::Item) -> K,
823 K: PartialEq,
824 {
825 self.dedup_by(|a, b| key(a) == key(b))
826 }
827
828 #[inline]
852 pub fn drain<R: RangeBounds<usize>>(
853 &mut self, range: R,
854 ) -> TinyVecDrain<'_, A> {
855 match self {
856 TinyVec::Inline(i) => TinyVecDrain::Inline(i.drain(range)),
857 TinyVec::Heap(h) => TinyVecDrain::Heap(h.drain(range)),
858 }
859 }
860
861 #[inline]
869 pub fn extend_from_slice(&mut self, sli: &[A::Item])
870 where
871 A::Item: Clone,
872 {
873 self.reserve(sli.len());
874 match self {
875 TinyVec::Inline(a) => a.extend_from_slice(sli),
876 TinyVec::Heap(h) => h.extend_from_slice(sli),
877 }
878 }
879
880 #[inline]
888 #[must_use]
889 #[allow(clippy::match_wild_err_arm)]
890 pub fn from_array_len(data: A, len: usize) -> Self {
891 match Self::try_from_array_len(data, len) {
892 Ok(out) => out,
893 Err(_) => {
894 panic!("TinyVec: length {} exceeds capacity {}!", len, A::CAPACITY)
895 }
896 }
897 }
898
899 #[inline(always)]
903 #[doc(hidden)]
904 pub fn constructor_for_capacity(cap: usize) -> TinyVecConstructor<A> {
905 if cap <= A::CAPACITY {
906 TinyVecConstructor::Inline(TinyVec::Inline)
907 } else {
908 TinyVecConstructor::Heap(TinyVec::Heap)
909 }
910 }
911
912 #[inline]
928 pub fn insert(&mut self, index: usize, item: A::Item) {
929 assert!(
930 index <= self.len(),
931 "insertion index (is {}) should be <= len (is {})",
932 index,
933 self.len()
934 );
935
936 let arr = match self {
937 TinyVec::Heap(v) => return v.insert(index, item),
938 TinyVec::Inline(a) => a,
939 };
940
941 if let Some(x) = arr.try_insert(index, item) {
942 let mut v = Vec::with_capacity(arr.len() * 2);
943 let mut it = arr.iter_mut().map(core::mem::take);
944 v.extend(it.by_ref().take(index));
945 v.push(x);
946 v.extend(it);
947 *self = TinyVec::Heap(v);
948 }
949 }
950
951 #[inline(always)]
953 #[must_use]
954 pub fn is_empty(&self) -> bool {
955 self.len() == 0
956 }
957
958 #[inline(always)]
960 #[must_use]
961 pub fn new() -> Self {
962 Self::default()
963 }
964
965 #[inline]
967 pub fn push(&mut self, val: A::Item) {
968 #[cold]
978 fn drain_to_heap_and_push<A: Array>(
979 arr: &mut ArrayVec<A>, val: A::Item,
980 ) -> TinyVec<A> {
981 let mut v = arr.drain_to_vec_and_reserve(arr.len());
983 v.push(val);
984 TinyVec::Heap(v)
985 }
986
987 match self {
988 TinyVec::Heap(v) => v.push(val),
989 TinyVec::Inline(arr) => {
990 if let Some(x) = arr.try_push(val) {
991 *self = drain_to_heap_and_push(arr, x);
992 }
993 }
994 }
995 }
996
997 #[inline]
1016 pub fn resize(&mut self, new_len: usize, new_val: A::Item)
1017 where
1018 A::Item: Clone,
1019 {
1020 self.resize_with(new_len, || new_val.clone());
1021 }
1022
1023 #[inline]
1046 pub fn resize_with<F: FnMut() -> A::Item>(&mut self, new_len: usize, f: F) {
1047 match new_len.checked_sub(self.len()) {
1048 None => return self.truncate(new_len),
1049 Some(n) => self.reserve(n),
1050 }
1051
1052 match self {
1053 TinyVec::Inline(a) => a.resize_with(new_len, f),
1054 TinyVec::Heap(v) => v.resize_with(new_len, f),
1055 }
1056 }
1057
1058 #[inline]
1076 pub fn split_off(&mut self, at: usize) -> Self {
1077 match self {
1078 TinyVec::Inline(a) => TinyVec::Inline(a.split_off(at)),
1079 TinyVec::Heap(v) => TinyVec::Heap(v.split_off(at)),
1080 }
1081 }
1082
1083 #[inline]
1107 pub fn splice<R, I>(
1108 &mut self, range: R, replacement: I,
1109 ) -> TinyVecSplice<'_, A, core::iter::Fuse<I::IntoIter>>
1110 where
1111 R: RangeBounds<usize>,
1112 I: IntoIterator<Item = A::Item>,
1113 {
1114 use core::ops::Bound;
1115 let start = match range.start_bound() {
1116 Bound::Included(x) => *x,
1117 Bound::Excluded(x) => x.saturating_add(1),
1118 Bound::Unbounded => 0,
1119 };
1120 let end = match range.end_bound() {
1121 Bound::Included(x) => x.saturating_add(1),
1122 Bound::Excluded(x) => *x,
1123 Bound::Unbounded => self.len(),
1124 };
1125 assert!(
1126 start <= end,
1127 "TinyVec::splice> Illegal range, {} to {}",
1128 start,
1129 end
1130 );
1131 assert!(
1132 end <= self.len(),
1133 "TinyVec::splice> Range ends at {} but length is only {}!",
1134 end,
1135 self.len()
1136 );
1137
1138 TinyVecSplice {
1139 removal_start: start,
1140 removal_end: end,
1141 parent: self,
1142 replacement: replacement.into_iter().fuse(),
1143 }
1144 }
1145
1146 #[inline]
1156 pub fn try_from_array_len(data: A, len: usize) -> Result<Self, A> {
1157 let arr = ArrayVec::try_from_array_len(data, len)?;
1158 Ok(TinyVec::Inline(arr))
1159 }
1160}
1161
1162#[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
1166pub enum TinyVecDrain<'p, A: Array> {
1167 #[allow(missing_docs)]
1168 Inline(ArrayVecDrain<'p, A::Item>),
1169 #[allow(missing_docs)]
1170 Heap(vec::Drain<'p, A::Item>),
1171}
1172
1173impl<'p, A: Array> Iterator for TinyVecDrain<'p, A> {
1174 type Item = A::Item;
1175
1176 impl_mirrored! {
1177 type Mirror = TinyVecDrain;
1178
1179 #[inline]
1180 fn next(self: &mut Self) -> Option<Self::Item>;
1181 #[inline]
1182 fn nth(self: &mut Self, n: usize) -> Option<Self::Item>;
1183 #[inline]
1184 fn size_hint(self: &Self) -> (usize, Option<usize>);
1185 #[inline]
1186 fn last(self: Self) -> Option<Self::Item>;
1187 #[inline]
1188 fn count(self: Self) -> usize;
1189 }
1190
1191 #[inline]
1192 fn for_each<F: FnMut(Self::Item)>(self, f: F) {
1193 match self {
1194 TinyVecDrain::Inline(i) => i.for_each(f),
1195 TinyVecDrain::Heap(h) => h.for_each(f),
1196 }
1197 }
1198}
1199
1200impl<'p, A: Array> DoubleEndedIterator for TinyVecDrain<'p, A> {
1201 impl_mirrored! {
1202 type Mirror = TinyVecDrain;
1203
1204 #[inline]
1205 fn next_back(self: &mut Self) -> Option<Self::Item>;
1206
1207 #[inline]
1208 fn nth_back(self: &mut Self, n: usize) -> Option<Self::Item>;
1209 }
1210}
1211
1212#[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
1215pub struct TinyVecSplice<'p, A: Array, I: Iterator<Item = A::Item>> {
1216 parent: &'p mut TinyVec<A>,
1217 removal_start: usize,
1218 removal_end: usize,
1219 replacement: I,
1220}
1221
1222impl<'p, A, I> Iterator for TinyVecSplice<'p, A, I>
1223where
1224 A: Array,
1225 I: Iterator<Item = A::Item>,
1226{
1227 type Item = A::Item;
1228
1229 #[inline]
1230 fn next(&mut self) -> Option<A::Item> {
1231 if self.removal_start < self.removal_end {
1232 match self.replacement.next() {
1233 Some(replacement) => {
1234 let removed = core::mem::replace(
1235 &mut self.parent[self.removal_start],
1236 replacement,
1237 );
1238 self.removal_start += 1;
1239 Some(removed)
1240 }
1241 None => {
1242 let removed = self.parent.remove(self.removal_start);
1243 self.removal_end -= 1;
1244 Some(removed)
1245 }
1246 }
1247 } else {
1248 None
1249 }
1250 }
1251
1252 #[inline]
1253 fn size_hint(&self) -> (usize, Option<usize>) {
1254 let len = self.len();
1255 (len, Some(len))
1256 }
1257}
1258
1259impl<'p, A, I> ExactSizeIterator for TinyVecSplice<'p, A, I>
1260where
1261 A: Array,
1262 I: Iterator<Item = A::Item>,
1263{
1264 #[inline]
1265 fn len(&self) -> usize {
1266 self.removal_end - self.removal_start
1267 }
1268}
1269
1270impl<'p, A, I> FusedIterator for TinyVecSplice<'p, A, I>
1271where
1272 A: Array,
1273 I: Iterator<Item = A::Item>,
1274{
1275}
1276
1277impl<'p, A, I> DoubleEndedIterator for TinyVecSplice<'p, A, I>
1278where
1279 A: Array,
1280 I: Iterator<Item = A::Item> + DoubleEndedIterator,
1281{
1282 #[inline]
1283 fn next_back(&mut self) -> Option<A::Item> {
1284 if self.removal_start < self.removal_end {
1285 match self.replacement.next_back() {
1286 Some(replacement) => {
1287 let removed = core::mem::replace(
1288 &mut self.parent[self.removal_end - 1],
1289 replacement,
1290 );
1291 self.removal_end -= 1;
1292 Some(removed)
1293 }
1294 None => {
1295 let removed = self.parent.remove(self.removal_end - 1);
1296 self.removal_end -= 1;
1297 Some(removed)
1298 }
1299 }
1300 } else {
1301 None
1302 }
1303 }
1304}
1305
1306impl<'p, A: Array, I: Iterator<Item = A::Item>> Drop
1307 for TinyVecSplice<'p, A, I>
1308{
1309 #[inline]
1310 fn drop(&mut self) {
1311 for _ in self.by_ref() {}
1312
1313 let (lower_bound, _) = self.replacement.size_hint();
1314 self.parent.reserve(lower_bound);
1315
1316 for replacement in self.replacement.by_ref() {
1317 self.parent.insert(self.removal_end, replacement);
1318 self.removal_end += 1;
1319 }
1320 }
1321}
1322
1323impl<A: Array> AsMut<[A::Item]> for TinyVec<A> {
1324 #[inline(always)]
1325 fn as_mut(&mut self) -> &mut [A::Item] {
1326 &mut *self
1327 }
1328}
1329
1330impl<A: Array> AsRef<[A::Item]> for TinyVec<A> {
1331 #[inline(always)]
1332 fn as_ref(&self) -> &[A::Item] {
1333 &*self
1334 }
1335}
1336
1337impl<A: Array> Borrow<[A::Item]> for TinyVec<A> {
1338 #[inline(always)]
1339 fn borrow(&self) -> &[A::Item] {
1340 &*self
1341 }
1342}
1343
1344impl<A: Array> BorrowMut<[A::Item]> for TinyVec<A> {
1345 #[inline(always)]
1346 fn borrow_mut(&mut self) -> &mut [A::Item] {
1347 &mut *self
1348 }
1349}
1350
1351impl<A: Array> Extend<A::Item> for TinyVec<A> {
1352 #[inline]
1353 fn extend<T: IntoIterator<Item = A::Item>>(&mut self, iter: T) {
1354 let iter = iter.into_iter();
1355 let (lower_bound, _) = iter.size_hint();
1356 self.reserve(lower_bound);
1357
1358 let a = match self {
1359 TinyVec::Heap(h) => return h.extend(iter),
1360 TinyVec::Inline(a) => a,
1361 };
1362
1363 let mut iter = a.fill(iter);
1364 let maybe = iter.next();
1365
1366 let surely = match maybe {
1367 Some(x) => x,
1368 None => return,
1369 };
1370
1371 let mut v = a.drain_to_vec_and_reserve(a.len());
1372 v.push(surely);
1373 v.extend(iter);
1374 *self = TinyVec::Heap(v);
1375 }
1376}
1377
1378impl<A: Array> From<ArrayVec<A>> for TinyVec<A> {
1379 #[inline(always)]
1380 fn from(arr: ArrayVec<A>) -> Self {
1381 TinyVec::Inline(arr)
1382 }
1383}
1384
1385impl<A: Array> From<A> for TinyVec<A> {
1386 #[inline]
1387 fn from(array: A) -> Self {
1388 TinyVec::Inline(ArrayVec::from(array))
1389 }
1390}
1391
1392impl<T, A> From<&'_ [T]> for TinyVec<A>
1393where
1394 T: Clone + Default,
1395 A: Array<Item = T>,
1396{
1397 #[inline]
1398 fn from(slice: &[T]) -> Self {
1399 if let Ok(arr) = ArrayVec::try_from(slice) {
1400 TinyVec::Inline(arr)
1401 } else {
1402 TinyVec::Heap(slice.into())
1403 }
1404 }
1405}
1406
1407impl<T, A> From<&'_ mut [T]> for TinyVec<A>
1408where
1409 T: Clone + Default,
1410 A: Array<Item = T>,
1411{
1412 #[inline]
1413 fn from(slice: &mut [T]) -> Self {
1414 Self::from(&*slice)
1415 }
1416}
1417
1418impl<A: Array> FromIterator<A::Item> for TinyVec<A> {
1419 #[inline]
1420 fn from_iter<T: IntoIterator<Item = A::Item>>(iter: T) -> Self {
1421 let mut av = Self::default();
1422 av.extend(iter);
1423 av
1424 }
1425}
1426
1427impl<A: Array> Into<Vec<A::Item>> for TinyVec<A> {
1428 #[inline]
1473 fn into(self) -> Vec<A::Item> {
1474 match self {
1475 Self::Heap(inner) => inner,
1476 Self::Inline(mut inner) => inner.drain_to_vec(),
1477 }
1478 }
1479}
1480
1481#[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
1483pub enum TinyVecIterator<A: Array> {
1484 #[allow(missing_docs)]
1485 Inline(ArrayVecIterator<A>),
1486 #[allow(missing_docs)]
1487 Heap(alloc::vec::IntoIter<A::Item>),
1488}
1489
1490impl<A: Array> TinyVecIterator<A> {
1491 impl_mirrored! {
1492 type Mirror = TinyVecIterator;
1493 #[inline]
1495 #[must_use]
1496 pub fn as_slice(self: &Self) -> &[A::Item];
1497 }
1498}
1499
1500impl<A: Array> FusedIterator for TinyVecIterator<A> {}
1501
1502impl<A: Array> Iterator for TinyVecIterator<A> {
1503 type Item = A::Item;
1504
1505 impl_mirrored! {
1506 type Mirror = TinyVecIterator;
1507
1508 #[inline]
1509 fn next(self: &mut Self) -> Option<Self::Item>;
1510
1511 #[inline(always)]
1512 #[must_use]
1513 fn size_hint(self: &Self) -> (usize, Option<usize>);
1514
1515 #[inline(always)]
1516 fn count(self: Self) -> usize;
1517
1518 #[inline]
1519 fn last(self: Self) -> Option<Self::Item>;
1520
1521 #[inline]
1522 fn nth(self: &mut Self, n: usize) -> Option<A::Item>;
1523 }
1524}
1525
1526impl<A: Array> DoubleEndedIterator for TinyVecIterator<A> {
1527 impl_mirrored! {
1528 type Mirror = TinyVecIterator;
1529
1530 #[inline]
1531 fn next_back(self: &mut Self) -> Option<Self::Item>;
1532
1533 #[inline]
1534 fn nth_back(self: &mut Self, n: usize) -> Option<Self::Item>;
1535 }
1536}
1537
1538impl<A: Array> ExactSizeIterator for TinyVecIterator<A> {
1539 impl_mirrored! {
1540 type Mirror = TinyVecIterator;
1541 #[inline]
1542 fn len(self: &Self) -> usize;
1543 }
1544}
1545
1546impl<A: Array> Debug for TinyVecIterator<A>
1547where
1548 A::Item: Debug,
1549{
1550 #[allow(clippy::missing_inline_in_public_items)]
1551 fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
1552 f.debug_tuple("TinyVecIterator").field(&self.as_slice()).finish()
1553 }
1554}
1555
1556impl<A: Array> IntoIterator for TinyVec<A> {
1557 type Item = A::Item;
1558 type IntoIter = TinyVecIterator<A>;
1559 #[inline(always)]
1560 fn into_iter(self) -> Self::IntoIter {
1561 match self {
1562 TinyVec::Inline(a) => TinyVecIterator::Inline(a.into_iter()),
1563 TinyVec::Heap(v) => TinyVecIterator::Heap(v.into_iter()),
1564 }
1565 }
1566}
1567
1568impl<'a, A: Array> IntoIterator for &'a mut TinyVec<A> {
1569 type Item = &'a mut A::Item;
1570 type IntoIter = core::slice::IterMut<'a, A::Item>;
1571 #[inline(always)]
1572 fn into_iter(self) -> Self::IntoIter {
1573 self.iter_mut()
1574 }
1575}
1576
1577impl<'a, A: Array> IntoIterator for &'a TinyVec<A> {
1578 type Item = &'a A::Item;
1579 type IntoIter = core::slice::Iter<'a, A::Item>;
1580 #[inline(always)]
1581 fn into_iter(self) -> Self::IntoIter {
1582 self.iter()
1583 }
1584}
1585
1586impl<A: Array> PartialEq for TinyVec<A>
1587where
1588 A::Item: PartialEq,
1589{
1590 #[inline]
1591 fn eq(&self, other: &Self) -> bool {
1592 self.as_slice().eq(other.as_slice())
1593 }
1594}
1595impl<A: Array> Eq for TinyVec<A> where A::Item: Eq {}
1596
1597impl<A: Array> PartialOrd for TinyVec<A>
1598where
1599 A::Item: PartialOrd,
1600{
1601 #[inline]
1602 fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
1603 self.as_slice().partial_cmp(other.as_slice())
1604 }
1605}
1606impl<A: Array> Ord for TinyVec<A>
1607where
1608 A::Item: Ord,
1609{
1610 #[inline]
1611 fn cmp(&self, other: &Self) -> core::cmp::Ordering {
1612 self.as_slice().cmp(other.as_slice())
1613 }
1614}
1615
1616impl<A: Array> PartialEq<&A> for TinyVec<A>
1617where
1618 A::Item: PartialEq,
1619{
1620 #[inline]
1621 fn eq(&self, other: &&A) -> bool {
1622 self.as_slice().eq(other.as_slice())
1623 }
1624}
1625
1626impl<A: Array> PartialEq<&[A::Item]> for TinyVec<A>
1627where
1628 A::Item: PartialEq,
1629{
1630 #[inline]
1631 fn eq(&self, other: &&[A::Item]) -> bool {
1632 self.as_slice().eq(*other)
1633 }
1634}
1635
1636impl<A: Array> Hash for TinyVec<A>
1637where
1638 A::Item: Hash,
1639{
1640 #[inline]
1641 fn hash<H: Hasher>(&self, state: &mut H) {
1642 self.as_slice().hash(state)
1643 }
1644}
1645
1646impl<A: Array> Binary for TinyVec<A>
1651where
1652 A::Item: Binary,
1653{
1654 #[allow(clippy::missing_inline_in_public_items)]
1655 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1656 write!(f, "[")?;
1657 if f.alternate() {
1658 write!(f, "\n ")?;
1659 }
1660 for (i, elem) in self.iter().enumerate() {
1661 if i > 0 {
1662 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1663 }
1664 Binary::fmt(elem, f)?;
1665 }
1666 if f.alternate() {
1667 write!(f, ",\n")?;
1668 }
1669 write!(f, "]")
1670 }
1671}
1672
1673impl<A: Array> Debug for TinyVec<A>
1674where
1675 A::Item: Debug,
1676{
1677 #[allow(clippy::missing_inline_in_public_items)]
1678 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1679 write!(f, "[")?;
1680 if f.alternate() && !self.is_empty() {
1681 write!(f, "\n ")?;
1682 }
1683 for (i, elem) in self.iter().enumerate() {
1684 if i > 0 {
1685 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1686 }
1687 Debug::fmt(elem, f)?;
1688 }
1689 if f.alternate() && !self.is_empty() {
1690 write!(f, ",\n")?;
1691 }
1692 write!(f, "]")
1693 }
1694}
1695
1696impl<A: Array> Display for TinyVec<A>
1697where
1698 A::Item: Display,
1699{
1700 #[allow(clippy::missing_inline_in_public_items)]
1701 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1702 write!(f, "[")?;
1703 if f.alternate() {
1704 write!(f, "\n ")?;
1705 }
1706 for (i, elem) in self.iter().enumerate() {
1707 if i > 0 {
1708 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1709 }
1710 Display::fmt(elem, f)?;
1711 }
1712 if f.alternate() {
1713 write!(f, ",\n")?;
1714 }
1715 write!(f, "]")
1716 }
1717}
1718
1719impl<A: Array> LowerExp for TinyVec<A>
1720where
1721 A::Item: LowerExp,
1722{
1723 #[allow(clippy::missing_inline_in_public_items)]
1724 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1725 write!(f, "[")?;
1726 if f.alternate() {
1727 write!(f, "\n ")?;
1728 }
1729 for (i, elem) in self.iter().enumerate() {
1730 if i > 0 {
1731 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1732 }
1733 LowerExp::fmt(elem, f)?;
1734 }
1735 if f.alternate() {
1736 write!(f, ",\n")?;
1737 }
1738 write!(f, "]")
1739 }
1740}
1741
1742impl<A: Array> LowerHex for TinyVec<A>
1743where
1744 A::Item: LowerHex,
1745{
1746 #[allow(clippy::missing_inline_in_public_items)]
1747 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1748 write!(f, "[")?;
1749 if f.alternate() {
1750 write!(f, "\n ")?;
1751 }
1752 for (i, elem) in self.iter().enumerate() {
1753 if i > 0 {
1754 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1755 }
1756 LowerHex::fmt(elem, f)?;
1757 }
1758 if f.alternate() {
1759 write!(f, ",\n")?;
1760 }
1761 write!(f, "]")
1762 }
1763}
1764
1765impl<A: Array> Octal for TinyVec<A>
1766where
1767 A::Item: Octal,
1768{
1769 #[allow(clippy::missing_inline_in_public_items)]
1770 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1771 write!(f, "[")?;
1772 if f.alternate() {
1773 write!(f, "\n ")?;
1774 }
1775 for (i, elem) in self.iter().enumerate() {
1776 if i > 0 {
1777 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1778 }
1779 Octal::fmt(elem, f)?;
1780 }
1781 if f.alternate() {
1782 write!(f, ",\n")?;
1783 }
1784 write!(f, "]")
1785 }
1786}
1787
1788impl<A: Array> Pointer for TinyVec<A>
1789where
1790 A::Item: Pointer,
1791{
1792 #[allow(clippy::missing_inline_in_public_items)]
1793 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1794 write!(f, "[")?;
1795 if f.alternate() {
1796 write!(f, "\n ")?;
1797 }
1798 for (i, elem) in self.iter().enumerate() {
1799 if i > 0 {
1800 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1801 }
1802 Pointer::fmt(elem, f)?;
1803 }
1804 if f.alternate() {
1805 write!(f, ",\n")?;
1806 }
1807 write!(f, "]")
1808 }
1809}
1810
1811impl<A: Array> UpperExp for TinyVec<A>
1812where
1813 A::Item: UpperExp,
1814{
1815 #[allow(clippy::missing_inline_in_public_items)]
1816 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1817 write!(f, "[")?;
1818 if f.alternate() {
1819 write!(f, "\n ")?;
1820 }
1821 for (i, elem) in self.iter().enumerate() {
1822 if i > 0 {
1823 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1824 }
1825 UpperExp::fmt(elem, f)?;
1826 }
1827 if f.alternate() {
1828 write!(f, ",\n")?;
1829 }
1830 write!(f, "]")
1831 }
1832}
1833
1834impl<A: Array> UpperHex for TinyVec<A>
1835where
1836 A::Item: UpperHex,
1837{
1838 #[allow(clippy::missing_inline_in_public_items)]
1839 fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1840 write!(f, "[")?;
1841 if f.alternate() {
1842 write!(f, "\n ")?;
1843 }
1844 for (i, elem) in self.iter().enumerate() {
1845 if i > 0 {
1846 write!(f, ",{}", if f.alternate() { "\n " } else { " " })?;
1847 }
1848 UpperHex::fmt(elem, f)?;
1849 }
1850 if f.alternate() {
1851 write!(f, ",\n")?;
1852 }
1853 write!(f, "]")
1854 }
1855}
1856
1857#[cfg(feature = "serde")]
1858#[cfg_attr(docs_rs, doc(cfg(feature = "alloc")))]
1859struct TinyVecVisitor<A: Array>(PhantomData<A>);
1860
1861#[cfg(feature = "serde")]
1862impl<'de, A: Array> Visitor<'de> for TinyVecVisitor<A>
1863where
1864 A::Item: Deserialize<'de>,
1865{
1866 type Value = TinyVec<A>;
1867
1868 fn expecting(
1869 &self, formatter: &mut core::fmt::Formatter,
1870 ) -> core::fmt::Result {
1871 formatter.write_str("a sequence")
1872 }
1873
1874 fn visit_seq<S>(self, mut seq: S) -> Result<Self::Value, S::Error>
1875 where
1876 S: SeqAccess<'de>,
1877 {
1878 let mut new_tinyvec = match seq.size_hint() {
1879 Some(expected_size) => TinyVec::with_capacity(expected_size),
1880 None => Default::default(),
1881 };
1882
1883 while let Some(value) = seq.next_element()? {
1884 new_tinyvec.push(value);
1885 }
1886
1887 Ok(new_tinyvec)
1888 }
1889}