1 // Copyright 2023 Google LLC 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 //! Provides an [`ArrayVecOption`] wrapper implementation over [`ArrayVec`], 16 //! which stores all the elements in an `Option` in order to satisfy 17 //! `ArrayVec`'s requirement that the elements must implement `Default`. 18 19 use tinyvec::{ArrayVec, ArrayVecIterator}; 20 #[cfg(any(test, feature = "alloc"))] 21 extern crate alloc; 22 #[cfg(any(test, feature = "alloc"))] 23 use alloc::vec::Vec; 24 25 /// A wrapper of [`ArrayVec`] that stores it values as [`Option`], in order to 26 /// satisfy `ArrayVec`'s requirement that the elements must implement `Default`. 27 /// The implementation guarantees that any items in the wrapped `ArrayVec` 28 /// within `0..len` is `Some`, and therefore will not panic when unwrapped. 29 #[derive(Debug, Clone, PartialEq, Eq)] 30 pub struct ArrayVecOption<A, const N: usize>(ArrayVec<[Option<A>; N]>); 31 32 // Cannot derive due to https://github.com/rust-lang/rust/issues/74462 33 impl<A, const N: usize> Default for ArrayVecOption<A, N> { default() -> Self34 fn default() -> Self { 35 Self(Default::default()) 36 } 37 } 38 39 /// Iterator type returned by `ArrayVecOption.iter()`, which can be used as 40 /// `impl Iterator<Item = &A>` 41 pub type ArrayVecOptionRefIter<'a, A> = 42 core::iter::Map<core::slice::Iter<'a, Option<A>>, fn(&'a Option<A>) -> &'a A>; 43 44 /// Iterator type returned by `ArrayVecOption.into_iter()`, which can be used as 45 /// `impl Iterator<Item = A>` 46 pub type ArrayVecOptionIntoIter<A, const N: usize> = 47 core::iter::Map<ArrayVecIterator<[Option<A>; N]>, fn(Option<A>) -> A>; 48 49 impl<A, const N: usize> ArrayVecOption<A, N> { 50 /// Returns an iterator over this vec. iter(&self) -> ArrayVecOptionRefIter<A>51 pub fn iter(&self) -> ArrayVecOptionRefIter<A> { 52 self.0 53 .iter() 54 .map(|v| v.as_ref().expect("ArrayVecOption value before .len() should not be None")) 55 } 56 57 /// The length of the vec (in elements). len(&self) -> usize58 pub fn len(&self) -> usize { 59 self.0.len() 60 } 61 62 /// Checks if the length is 0. is_empty(&self) -> bool63 pub fn is_empty(&self) -> bool { 64 self.0.is_empty() 65 } 66 67 /// Returns the first element of the vec, or `None` if it is empty. first(&self) -> Option<&A>68 pub fn first(&self) -> Option<&A> { 69 self.iter().next() 70 } 71 72 /// Place an element onto the end of the vec. 73 /// 74 /// # Panics 75 /// * If the length of the vec would overflow the capacity. push(&mut self, value: A)76 pub fn push(&mut self, value: A) { 77 self.0.push(Some(value)) 78 } 79 80 /// Returns a reference to an element at the given index. get(&self, index: usize) -> Option<&A>81 pub fn get(&self, index: usize) -> Option<&A> { 82 self.0.get(index).and_then(|opt| opt.as_ref()) 83 } 84 85 /// Sorts the slice with a key extraction function, but might not preserve 86 /// the order of equal elements. 87 /// 88 /// This sort is unstable (i.e., may reorder equal elements), in-place 89 /// (i.e., does not allocate), and *O*(*m* \* *n* \* log(*n*)) worst-case, 90 /// where the key function is *O*(*m*). sort_unstable_by_key<K: Ord>(&mut self, f: impl Fn(&A) -> K)91 pub fn sort_unstable_by_key<K: Ord>(&mut self, f: impl Fn(&A) -> K) { 92 self.0.sort_unstable_by_key(|a| { 93 f(a.as_ref().expect("Iterated values in ArrayVecOption should never be None")) 94 }) 95 } 96 97 /// Remove an element, swapping the end of the vec into its place. swap_remove(&mut self, index: usize) -> A98 pub fn swap_remove(&mut self, index: usize) -> A { 99 self.0.swap_remove(index).expect("since index is is bounds, the value at index will always be Some which is safe to unwrap") 100 } 101 102 /// Converts this vector into a regular `Vec`, unwrapping all of the 103 /// `Option` in the process. 104 #[cfg(any(test, feature = "alloc"))] into_vec(self) -> Vec<A>105 pub fn into_vec(self) -> Vec<A> { 106 self.into_iter().collect() 107 } 108 } 109 110 impl<A, const N: usize> IntoIterator for ArrayVecOption<A, N> { 111 type Item = A; 112 type IntoIter = ArrayVecOptionIntoIter<A, N>; into_iter(self) -> Self::IntoIter113 fn into_iter(self) -> Self::IntoIter { 114 self.0 115 .into_iter() 116 .map(|v| v.expect("ArrayVecOption value before .len() should not be None")) 117 } 118 } 119 120 // Implement `FromIterator` to enable `iter.collect::<ArrayVecOption<_>>()` 121 impl<A, const N: usize> FromIterator<A> for ArrayVecOption<A, N> { from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self122 fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self { 123 Self(iter.into_iter().map(Some).collect()) 124 } 125 } 126 127 impl<A, const N: usize> core::ops::Index<usize> for ArrayVecOption<A, N> { 128 type Output = A; index(&self, index: usize) -> &Self::Output129 fn index(&self, index: usize) -> &Self::Output { 130 self.0[index].as_ref().expect("This panics if provided index is out of bounds") 131 } 132 } 133 134 #[cfg(test)] 135 mod test { 136 extern crate std; 137 use super::ArrayVecOption; 138 use std::vec; 139 140 #[test] test_default_array_vec()141 fn test_default_array_vec() { 142 let vec = ArrayVecOption::<u32, 5>::default(); 143 assert_eq!(0, vec.len()); 144 assert_eq!(None, vec.iter().next()); 145 assert!(vec.is_empty()); 146 assert_eq!(None, vec.first()); 147 assert_eq!(None, vec.get(0)); 148 assert_eq!(vec![0_u32; 0], vec.into_vec()); 149 } 150 151 #[test] test_array_vec_with_contents()152 fn test_array_vec_with_contents() { 153 let mut vec = ArrayVecOption::<u32, 5>::default(); 154 vec.push(1); 155 vec.push(2); 156 vec.push(3); 157 vec.push(4); 158 vec.push(5); 159 assert_eq!(5, vec.len()); 160 let mut iter = vec.iter(); 161 assert_eq!(Some(&1_u32), iter.next()); 162 assert_eq!(Some(&2_u32), iter.next()); 163 assert_eq!(Some(&3_u32), iter.next()); 164 assert_eq!(Some(&4_u32), iter.next()); 165 assert_eq!(Some(&5_u32), iter.next()); 166 assert_eq!(None, iter.next()); 167 assert!(!vec.is_empty()); 168 assert_eq!(Some(&1_u32), vec.first()); 169 assert_eq!(Some(&5_u32), vec.get(4)); 170 assert_eq!(vec![1_u32, 2, 3, 4, 5], vec.clone().into_vec()); 171 172 let _ = vec.swap_remove(2); 173 assert_eq!(vec![1_u32, 2, 5, 4], vec.clone().into_vec()); 174 } 175 176 #[test] 177 #[should_panic] test_array_vec_push_overflow()178 fn test_array_vec_push_overflow() { 179 let mut vec = ArrayVecOption::<u32, 5>::default(); 180 vec.push(1); 181 vec.push(2); 182 vec.push(3); 183 vec.push(4); 184 vec.push(5); 185 vec.push(6); 186 } 187 188 #[test] test_sort()189 fn test_sort() { 190 let mut vec = ArrayVecOption::<u32, 5>::default(); 191 vec.push(3); 192 vec.push(1); 193 vec.push(4); 194 vec.push(1); 195 vec.push(2); 196 vec.sort_unstable_by_key(|k| *k); 197 assert_eq!(vec![1_u32, 1, 2, 3, 4], vec.clone().into_vec()); 198 } 199 200 #[test] test_collect()201 fn test_collect() { 202 let vec: ArrayVecOption<u32, 5> = [5_u32, 4, 3, 2, 1].into_iter().collect(); 203 assert_eq!(vec![5_u32, 4, 3, 2, 1], vec.clone().into_vec()); 204 } 205 } 206